Как работает erase в c
Идиома remove-erase idiom призвана решить проблему удаления элементов из контейнера, поскольку данная проблема может представлять нетривиальную задачу, чреватую возникновением ошибок. Данная идиома предполагает применение алгоритма remove() или remove_if() , за которым следует вызов функции erase() контейнера.
При применении алгоритмов remove() и remove_if() те элементы, которые надо сохранить, помещаются в начало контейнера, а функции remove() и remove_if() возвращают итератор на первый удаляемый элемент. Затем этот итератор передается в функцию erase() , которая собственно и удаляет элементы. Реализация идиомы:
#include #include #include void print (const std::vector& data) < for(const auto& n: data) < std::cout std::cout bool is_negative(int n) < return n < 0;>int main() < std::vectornumbers ; // применяем алгоритм remove_if() для удаления всех элементов, которые не соответствуют условию auto iter< std::remove_if(begin(numbers), end(numbers), is_negative) >; print(numbers); // 0 1 2 3 4 5 1 2 3 4 5 // удаляем все элементы, начиная с итератора first_to_erase numbers.erase(iter, end(numbers)); print(numbers); // 0 1 2 3 4 5 >
Здесь для примера удаляем из вектора все отрицательные числа. Для этого сначала вызываем функцию std::remove_if() :
auto iter< std::remove_if(begin(numbers), end(numbers), is_negative) >; print(numbers);
В качестве первого и второго параметров она принимает итераторы на начало и конец диапазона, из которого надо удалить числа. Здесь диапазон определяется итераторами на начало и конец вектора. В качестве третьего параметра передается условие. Условие должно представлять функцию, которая принимает некоторое значение и возвращает значение типа bool — true , если значение соответствует условию, и false — если не соответствует. В данном случае в качестве такого условия передаем функцию is_negative, которая вычисляет, является ли число отрицательным. То есть мы удаляем отрицательные числа.
Для вывода вектора на консоль применяется функция print. После выполнения remove_if на консоль будет выведено
0 1 2 3 4 5 1 2 3 4 5
В результате remove_if() просто перемещает все элементы, которые нужно сохранить (0 и положительные числа), в начало диапазона. При этом часть из этих чисел остается в конце вектора, но это не имеет значения, поскольку эта часть вектора будет удалена. А сама функция возвращает итератор iter, который указывает на первый удаляемый элемент. Далее удаляем все элементы, которые начинаются с этого итератора:
numbers.erase(iter, end(numbers)); print(numbers);
Теперь консольный вывод будет следующим:
0 1 2 3 4 5
std::erase_if()
Поскольку безопасное удаление из контейнеров представляет довольно часто встречаемую задачу, то начиная со стандарта C++20 в язык С++ были добавлены функции std::erase() и std::erase_if()
Функция std::erase() удаляет отдельное значение из контейнера (не применяется к std::set и std::map):
std::erase(Container, Value)
Функция std::erase_if() удаляет значения из контейнера, которые соответствуют условию:
std::erase_if(Container, Function)
Так, перепишем предыдущий пример с помощью функции std::erase_if :
#include #include void print (const std::vector& data) < for(const auto& n: data) < std::cout std::cout bool is_negative(int n) < return n < 0;>int main() < std::vectornumbers ; std::erase_if(numbers, is_negative); print(numbers); // 0 1 2 3 4 5 >
Вектора в C++ (часть 4)
В вектор можно добавлять элементы с помощью указателей, для этого используется функция vector::data() . Вывод вектора так же можно осуществить при помощи указателя, пример:
#include #include using namespace std; int main() < vectorvecInt(5); int i; int *pointer=vecInt.data();///создание указателя for( i=0;i <5;++i) < pointer[i]=i;///равносильно vecInt[i]=I; >cout cout cout return 0; >
CppStudio.com
First output: 0 1 2 3 4
Second output: 0 1 2 3 4
Third output: 0 1 2 3 4
В 7 строке мы объявили вектор vecInt размером на 5 элементов типа int . В 9 строке создаем указатель pointer , указывающий на нулевой элемент вектора. С 10-13 строки производим заполнение вектора при помощи указателя pointer . Вывод нашего вектора можно выполнить тремя различными способами. В строках с 16-19 выполняется первый вариант вывода. Этот вариант вывода равносилен выводу массива с использованием указателей, так, что нечего необычного и непонятного для Вас быть не должно.
Следующий вариант вывода описан в строках 23-27. Поскольку расположение элементов вектора в памяти производится последовательно один за другим, то в строке 25 указатель указывает на ячейку в памяти, где расположен i -тый элемент вектора (вывод которого мы и осуществляем) . В 26 строке используя постфиксную форму, мы увеличиваем значение указателя на единицу, указатель указывает на следующий элемент вектора. Третий вывод самый обычный, описан с 31-34 строку, с ним тоже вопросов быть не должно.
В вектора можно вставлять элемент, как в начало вектора, так и в конец, при помощи функций vector::emplace() и vector::emplace_back() , рассмотрим пример:
#include #include using namespace std; int main() < vectorvecInt; vector::iterator it; for(int i=0;i <5;++i)///заполнение вектора значениями 0-4 < vecInt.push_back(i); >///итератор указывает на нулевой элемент вектора it=vecInt.begin(); vecInt.emplace(it,10);///вставляем нулевым элементом число 10 в вектор it=vecInt.begin()+2;///итератор указывает на второй элемент вектора vecInt.emplace(it,10);///вставляем вторым элементом число 10 в вектор vecInt.emplace_back(10);///вставляем в конец вектора число 10 cout return 0; >
CppStudio.com
Vector contains: 10 0 10 1 2 3 4 10
Работу программы в строках с 6-12, думаю, описывать не стоит. В 15 строке итератор it указывает на начало нашего вектора, а в 17 строке при помощи функции vector::emplace() и итератора it , мы помещаем число 10 в начало вектора, т. е. vector::emplace() принимает два аргумента, первый, это позиция куда будет помещен элемент (в нашем случае vecInt.begin() или нулевой элемент вектора), второе, сам элемент (в нашем случае число 10).
В 19 строке итератор указывает на второй элемент в векторе vecInt[2] . Назначение строки 21 равносильно строке 17. В 23 строке с помощью функции vector::emplace_back() , мы помещаем число 10 в конец вектора. Эта запись равносильна vecInt.push_back(10). В строках 26-29 производится вывод вектора на экран с помощью итератора it .
Вектора имеют функцию, которая позволяет определить пустой ли вектор, позволяет удалить определенный элемент, получить доступ к нулевому и последнему элементу, пример:
#include #include using namespace std; int main() < vectorvecIntFirst, vecIntSecond; for(int i=0;i <10;++i)///заполняем вектор vecIntSecond значениями 0-9 < vecIntSecond.push_back(i); >cout vecIntFirst.empty()?cout cout
CppStudio.com
vecIntSecond contains: 0 1 2 3 4 5 6 7 8 9
vecIntFirst is empty
vecIntSecond is not empty
vecIntSecond contains: 0 2 7 8 9
first element in vector: 0
last element in vector: 9
first-last: -9
Думаю до строки 19, объяснять работу программы не стоит. В 19 и 20 строке мы знакомимся с новым оператором vector::empty() который возвращает значение true если пустой вектор и false если полон. В строках 19 и 20 используется тернарный оператор ( ? : ), который равносилен конструкции if() else() . Строку 19 можно прочитать так: если vecIntFirst пуст, то выведи сообщение, что он пуст, иначе выведи сообщение, что он не пуст. 20 строка равносильна 19 строке. В строке 23 с использованием функции vector:erase() , мы стираем первый элемент вектора (не забывайте, что вектора как и массивы нумеруются с нулевого элемента).
Функции vector:erase() мы указываем, что бы она удаляла элемент в позиции vecIntSecond.begin() который у нас равен нулевому элементу, плюс один элемент. Иначе говоря 0+1=1 (удален первый элемент). В строке 24 я хотел показать, что можно удалять не только один элемент вектора, но так же и группу элементов. Тут функция vector:erase() принимает два аргумента: первый – элемент, с которого начнется удаление (он будет удален) и второй – элемент по который будет производиться удаление, последний элемент (не будет удален).
Функции vector:erase() можно задавать не только координаты начала вектора vecIntSecond.begin() , но так же и координаты конца вектора vecIntSecond.end() , тогда нумерация пойдет с конца. В строках 27-30 производится вывод на экран, а в строке 33 мы с помощью функции vector::front() обращаемся к нулевому элементу вектора и выводим ее на экран. В 34 строке соответственно к последнему элементу вектора и тоже выводим ее на экран. В 35 строке мы вычитаем из первого элемента, последний элемент и выводим разницу.
Операции с векторами в STL
Размер вектора можно узнать при помощи универсального метода size() , возвращающего для всех контейнеров в STL их размер. Также есть метод empty() , возвращающий логическое значение ( true , если вектор пустой).
Размер вектора можно изменить в любой момент, при помощи метода resize . У этого метода может быть один или два параметра. Вызов метода resize(n) изменяет размер вектора до n элементов (длина вектора может как уменьшится, так и увеличиться). Вызов метода resize(n, val) изменяет размер вектора до n элементов, и если при этом размер вектора увеличивается, то новые элементы получают значение, равное val.
Очень часто бывает полезно добавлять элементы в конец вектора по одному и удалять элементы из конца вектора по одному. Для добавления нового элемента, равного val в конец вектора используется метод push_back(val) . Для удаления последнего элемента вектора используется метод pop_back() — он не возвращает значения.
Добавление элемента в конец вектора осуществляется в среднем за O(1). Это реализовано за счет того, что память для хранения элементов вектора выделяется “с запасом”, то есть можно будет добавлять элементы по одному, пока не кончится запас памяти. Если запас памяти исчерпан, выделяется новая память, при этом «запас» размера вектора удваивается.
Очистить вектор можно при помощи метода clear() .
Вставка и удаление элементов в середину вектора
Для удаления и вставки элементов в середину вектора используются методы erase и insert . В качестве параметра им нужно передавать итератор, поэтому просто покажем на примере, как их использовать.
Итератор — специальный объект, указывающий на элемент вектора (или другой структуры данных). Итератор на элемент с индексом i можно получить при помощи выражения a.begin() + i . Кроме того, можно при помощи итератора a.end() “отсчитывать” элементы, начиная с конца. При этом a.end() будет итератором на элемент, следующий за последним, a.end() будет итератором на последний элемент, то есть то же самое, что a.begin() + a.size() — 1 , a.end() — 2 — второй элемент с конца и т.д.
Удаление элементов: метод erase
Метод erase позволяет удалять из середины вектора один или несколько элементов. Если вызвать метод erase с одним параметром–итератором, то будет удален соответствующий элемент из вектора, то есть для удаления элемента с индексом i из вектора a нужно вызвать метод следующим образом:
a.erase(a.begin() + i);
Методу erase передать два итератора на начало и конец удаляемого фрагмента, например:
a.erase(a.begin() + i, a.begin() + j);
В этом случае будут удалены элементы с индексами от i (включительно) до j не включительно, то есть элементы a[i] , a[i + 1] , . a[j — 1] . Всего будет удалено j — i элементов.
Методу erase можно передавать и итераторы, полученные относительно итератора end . Например, удалить из вектора три последних элемента можно так:
a.erase(a.end() - 3, a.end());
Подробней про его использование можно прочитать в документации.
Вставка элементов: метод insert
Метод insert позволяет вставлять в середину вектора новый элемент, или несколько равных элементов, или другой вектор, или фрагмент другого вектора. Этот метод также работает с итераторами и про его использование можно прочитать в документации.
Примеры использования метода insert :
Вставка одного элемента со значением val в позицию с индексом i :
a.insert(a.begin() + i, val);
Вставка нескольких равных (количеством count ) элементов со значением val в позицию с индексом i :
a.insert(a.begin() + i, count, val);
Вставка в вектор a в позицию с индексом i фрагмент вектора b с индексами от start включительно до finish не включительно:
a.insert(a.begin() + i, b.begin() + start, b.begin() + finish);
В качестве параметром могут использоваться произвольные итераторы. Рассмотрим несколько примеров:
Весь вектор b добавить в конец вектора a :
a.insert(a.end(), b.begin(), b.end());
Последние 5 элементов вектора b вставить в начало вектора a :
a.insert(a.begin(), b.end() - 5, b.end());
Поскольку вставка и удаление элементов требуют сдвига других элементов вектора, эти операции имеют линейную сложность, то есть выполняются за время, пропорциональное длине вектора.
Присваивание и сравнение векторов
Содержимое одного вектора можно целиком скопировать в другой вектор при помощи операции присваивания. При этом размер вектора A автоматически изменится и будет равен размеру вектора B . A = B .
Также векторы можно сравнивать на равенство и неравенство ( A == B , A != B ), и сравнивать их содержимое в лексикографическом порядке ( A < B , A B , A >= B ).
vector::erase в C++ (с примерами)
Здравствуйте! Сегодня мы обсудим часто используемую функцию в C++ для управления элементами в векторе — erase . Начнем с изучения этой функции, узнаем, как правильно ее использовать, и рассмотрим практические примеры. К концу статьи у вас будет твердое понимание этого важного инструмента.
Удаление элементов из вектора в C++
Векторы в C++ — это динамические массивы, которые могут увеличиваться и уменьшаться в размере. Иногда нам нужно удалить элементы из вектора, будь то один элемент или диапазон. Здесь на помощь приходит функция erase .
Функция erase выглядит так:
vector::erase(iterator position); vector::erase(iterator first, iterator last);- Функция принимает итераторы первого и последнего удаляемых элементов.
- Она возвращает итератор, указывающий на следующий элемент после удаленного (или удаленных). Если был удален последний элемент, итератор указывает на конец вектора.
Рассмотрим ее на примере простой программы:
#include #include int main() std::vectorint> my_vector; // Добавляем значения от 1 до 10 for (int i=1; i10; i++) my_vector.push_back(i); // Удаляем 6-й элемент my_vector.erase(my_vector.begin()+5); // Удаляем первые 3 элемента my_vector.erase(my_vector.begin(),my_vector.begin()+3); std::cout <"my_vector содержит:"; for (unsigned i=0; imy_vector.size(); ++i) std::cout <' ' [ i]; std::cout <'\n'; return 0; >Выходные данные программы:
my_vector содержит: 4 5 7 8 9 10Когда вы удаляете элемент (или несколько элементов) из вектора:
- Размер вектора уменьшается на количество удаленных элементов.
- Если вы не удаляете элементы с конца, вектор сдвигает все элементы после удаленных на новые позиции. Это не так быстро, как в некоторых других контейнерах, таких как list или forward_list .
Время выполнения зависит от двух вещей: количества удаляемых элементов и количества элементов после удаляемых. Последние перемещаются на новые позиции.
Будьте осторожны с вашими итераторами! Если они указывают на удаленный элемент или на любой элемент после него, они будут работать не так, как вы ожидаете. Но итераторы до удаленных элементов остаются действительными.
Безопасность и исключения
Используя erase , вы изменяете вектор. Но элементы до удаленных не затрагиваются. Так что безопасно обращаться или изменять их при использовании erase . Если вы ошибочно передаете неправильную позицию или диапазон в erase , результат может быть непредсказуемым, будьте внимательны.
Так же, как функц