На этом шаге мы рассмотрим алгоритмы удаления элементов с заданным значением.
Начиная с этого шага, мы будем рассматривать алгоритмы, которые удаляют элементы из интервала по заданному значению или критерию. Однако следует помнить, что эти алгоритмы не могут изменить количество элементов. Они всего лишь заменяют "удаленные" элементы следующими элементами, которые не были удалены, и возвращают новый логический конец интервала (позицию за последним элементом, который не был удален).
Удаление элементов с заданным значением
Для выполнения этого действия используются следующие алгоритмы:
ForwardIterator
remove (ForwardIterator beg, ForwardIterator end,
const T& value)
ForwardIterator
remove_if (ForwardIterator beg. ForwardIterator end,
UnaryPredicate op)
Алгоритм remove() удаляет в интервале [beg,end) все элементы, значение которых равно value.
Алгоритм remove_if() удаляет в интервале [beg,end) все элементы, для которых унарный предикат op(elem) возвращает true.
Оба алгоритма возвращают новый логический конец модифицированного интервала (то есть позицию за последним элементом, который не был удален).
Алгоритмы заменяют "удаленные" элементы следующими элементами, которые не были удалены.
Алгоритмы сохраняют порядок следования элементов, которые не были удалены.
Вызывающая сторона должна использовать новый логический конец интервала вместо исходного конца end.
Предикат ор не должен изменять свое состояние во время вызова.
Алгоритм remove_if() обычно копирует унарный предикат внутри алгоритма и использует его дважды. Из-за этого могут возникнуть проблемы, если предикат изменяет свое состояние при вызове функции.
Вследствие модификации эти алгоритмы не могут использоваться с ассоциативными контейнерами (смотри 108 шаг), однако в классах ассоциативных контейнеров определена аналогичная функция erase() (смотри 203 шаг).
Для списков определена аналогичная функция remove(), которая часто работает более эффективно, поскольку она меняет внутренние указатели вместо присваивания значений элементам (смотри 203 шаг).
Сложность линейная (numberOfElements сравнений или вызовов ор соответственно).
Пример использования алгоритмов remove() и remove_if():
//--------------------------------------------------------------------------- #include <vcl.h> #include <iterator> #include "algostuff.hpp" #include <conio.h> //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) { char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; } int main() { vector<int> coll; INSERT_ELEMENTS(coll,2,6); INSERT_ELEMENTS(coll,4,9); INSERT_ELEMENTS(coll,1,7); PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Удаление всех элементов со значением 5 vector<int>::iterator pos; pos = remove(coll.begin(), coll.end(), // Интервал 5); // Удаляемое значение PRINT_ELEMENTS(coll,"Коллекция не изменилась:\n"); // Стирание "удаленных" элементов из контейнера coll.erase(pos, coll.end()); PRINT_ELEMENTS(coll,"А теперь изменилась:\n"); // Удаление всех элементов со значением меньше 4 coll.erase(remove_if(coll.begin(), coll.end(), // Интервал bind2nd(less<int>(),4)), // Критерий удаления coll.end()); PRINT_ELEMENTS(coll,"Удаление всех элементов со значением меньше 4:\n"); getch(); return 0; } //---------------------------------------------------------------------------
Результат выполнения программы выглядит так:
Рис.1. Результат работы приложения
На следующем шаге мы рассмотрим удаление элементов при копировании.
