объясняется тот удивительный факт, что вызов remove не изменяет количества элементов в контейнере:

vector<int> v: v.reserve(lO); forCint i=l;i<=10:++i){ v.push back(i);

cout V.sizeO: v[3]=v[5]=v[9]=99: remove( V.beginO, V.endO, 99): cout V. SizeO:

Создать vector<int> и заполнить его числами 1-10 (вызов reserve описан в совете 14)

Выводится число 10 Присвоить 3 элементам значение 99 Удалить все элементы со значением 99 Все равно выводится 10!

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

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

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

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

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

V.beginO

99 7

v.endQ

9 99

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

vector<int>::iterator newEnd(remove(v.begin().v.end().99)):

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

V.beginO

V.endO

newEnd

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

Раз оставшиеся элементы v находятся между v.beginO и newEnd, было бы логично предположить, что удаленные элементы будут находиться между newEnd и V.endO. Но это не так\ Присутствие удаленных элементов в v вообще не

newEnd

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

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

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

1. Алгоритм remove анализирует v[0], видит, что данный элемент не должен удаляться, и перемещается к v[l]. То же самое происходит с элементами v[l] HV[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] образуется новая дыра .

4. Элемент v[5] исключается, поэтому алгоритм игнорирует его и переходит к v[6]. При этом он продолжает помнить, что на месте v[4] остается дыра , которую нужно заполнить.

5. Элемент v[6] сохраняется, поэтому алгоритм присваивает v[6] элементу v[4], вспоминает, что следующая дыра находится на месте v[5], и переходит к v[7].

гарантировано. Алгоритм remove не изменяет порядок элементов в интервале так, чтобы удаленные элементы сгруппировались в конце - он перемещает остающиеся элементы в начало. Хотя в Стандарте такое требование отсутствует, элементы за новым логическим концом интервала обычно сохраняют свои старые значения. Во всех известных мне реализациях после вызова remove вектор v выглядит так:

vbeginO vend() I t

ХУКУ

Как объясняется в совете 33, факт перезаписи некоторых удаляемых значений имеет важные последствия в том случае, если эти значения являются указателями. Но в контексте данного совета достаточно понимать, что remove не удаляет элементы из контейнера, поскольку в принципе не может этого сделать. Элементы могут удаляться лишь функциями контейнера, отсюда следует и главное правило настоящего совета: чтобы удалить элементы из контейнера, вызовите erase после remove.

Элементы, подлежащие фактическому удалению, определить нетрудно - это все элементы исходного интервала, начиная с нового логического конца интервала и завершая его физическим концом. Чтобы уничтожить все эти элементы, достаточно вызвать интервальную форму erase (см. совет 5) и передать ей эти два итератора. Поскольку сам алгоритм remove возвращает итератор для нового логического конца массива, задача решается прямолинейно:

vector<int> v: См. ранее

v.erase(renrave(v.begin().V.endO,99).V.endO); Фактическое удаление

элементов со значением 99 cout V.sizeO; Теперь выводится 7

Передача в первом аргументе интервальной формы erase возвращаемого значения remove используется так часто, что рассматривается как стандартная конструкция. Remove и erase настолько тесно связаны, что они были объединены в функцию remove контейнера 1 i st. Это единственная функция STL с именем remove, которая производит фактическое удаление элементов из контейнера:

list<int> li; Создать список

Заполнить данными li.remove(99); Удалить все элементы со значением 99.

Команда производит фактическое удаление

элементов из контейнера, поэтому размер li

может измениться

Честно говоря, выбор имени remove в данном случае выглядит непоследовательно. В ассоциативных контейнерах аналогичная функция называется erase, поэтому в контейнере list функцию remove тоже следовало назвать erase. Впрочем, этого не произошло, поэтому остается лишь смириться. Мир, в котором

6. Аналогичным образом анализируются элементы v[7], v[8] и v[9]. Значение v[7] присваивается элементу v[5], а значение v[8] присваивается элементу v[6]. Элемент v[9] игнорируется, поскольку находящееся в нем значение подлежит удалению.

7. Алгоритм возвращает итератор для элемента, следующего за последним оставшимся . В данном примере это элемент v[7].

Перемещения элементов в векторе v выглядят следующим образом:

8 I 9 99