Скотт Мейерс - Эффективное использование STL

v.reserve(10); // числами 1-10 (вызов reserve описан

for (int i=1; i<=10; ++i){ // в совете 14)

v.push_back(i);

};

cout << v.size(); // Выводится число 10

v[3]=v[5]=v[9]=99; // Присвоить 3 элементам значение 99

remove(v.begin(), v.end(), 99); // Удалить все элементы со значением 99

cout << v.size(); // Все равно выводится 10!

Чтобы понять смысл происходящего, необходимо запомнить следующее: Алгоритм remove «по настоящему» ничего не удаляет, потому что не может. На всякий случай повторю: … потому что не может!

Алгоритм removeне знает, из какого контейнера он должен удалять элементы, а без этого он не может вызвать функцию «настоящего» удаления.

Итак, теперь вы знаете, чего алгоритм removeсделать не может и по каким причинам. Остается понять, что же он все-таки делает.

В общих чертах removeперемещает элементы в заданном интервале до тех пор, пока все «оставшиеся» элементы не окажутся в начале интервала (с сохранением их относительного порядка). Алгоритм возвращает итератор, указывающий на позицию за последним «оставшимся» элементом. Таким образом, возвращаемое значение можно интерпретировать как новый «логический конец» интервала.

В рассмотренном выше примере вектор vперед вызовом removeвыглядел следующим образом:

Предположим, возвращаемое значение removeсохраняется в новом итераторе с именем newEnd:

vector::iterator newEnd(remove(v.begin(), v.end(), 99));

После вызова вектор vпринимает следующий вид:

Вопросительными знаками отмечены значения элементов, «концептуально» удаленных из v, но продолжающих благополучно существовать.

Раз «оставшиеся» элементы v находятся между v.begin()и newEnd, было бы логично предположить, что «удаленные» элементы будут находиться между newEndи v.end(). Но это не так! Присутствие «удаленных» элементов в v вообще не гарантировано. Алгоритм removeне изменяет порядок элементов в интервале так, чтобы «удаленные» элементы сгруппировались в конце — он перемещает «остающиеся» элементы в начало. Хотя в Стандарте такое требование отсутствует, элементы за новым логическим концом интервала обычно сохраняют свои старые значения. Во всех известных мне реализациях после вызова removeвектор vвыглядит так:

Как видите, два значения «99», ранее существовавших в v, исчезли, а одно осталось. В общем случае после вызова removeэлементы, удаленные из интервала, могут остаться в нем, а могут исчезнуть. Многие программисты находят это странным, но почему? Вы просите removeубрать некоторые элементы, алгоритм выполняет вашу просьбу. Вы же не просили разместить удаленные значения в особом месте для последующего использования… Так в чем проблема? (Чтобы предотвратить потерю значений, вместо remove лучше воспользоваться алгоритмом partition, описанным в совете 31.)

На первый взгляд поведение remove выглядит довольно странно, но оно является прямым следствием принципа работы алгоритма. Во внутренней реализации removeперебирает содержимое интервала и перезаписывает «удаляемые» значения «сохраняемыми». Перезапись реализуется посредством присваивания.

Алгоритм removeможно рассматривать как разновидность уплотнения, при этом удаляемые значения играют роль «пустот», заполняемых в процессе уплотнения. Опишем, что происходит с вектором v из нашего примера.

1. Алгоритм removeанализирует v[0], видит, что данный элемент не должен удаляться, и перемещается к v[1]. То же самое происходит с элементами v[1]и v[2].

2. Алгоритм определяет, что элемент v[3]подлежит удалению, запоминает этот факт и переходит к v[4]. Фактически v[3]рассматривается как «дыра», подлежащая заполнению.

3. Значение v[4]необходимо сохранить, поэтому алгоритм присваивает v[4]элементу v[3], запоминает, что v[4]подлежит перезаписи, и переходит к v[5]. Если продолжить аналогию с уплотнением, элемент v[3]«заполняется» значением v[4], а на месте v[4]образуется новая «дыра».