Скотт Мейерс - Эффективное использование STL
Допустим, перед вызовом remove_if вектор v имеет следующий вид:
После вызова remove_if вектор выглядит примерно так (с итератором, возвращаемым при вызове remove_if):
Если подобное превращение кажется непонятным, обратитесь к совету 32, где подробно описано, что происходит при вызове remove (в данном случае — remove_if).
Причина утечки ресурсов очевидна. «Удаленные» указатели на объекты B и C были перезаписаны «оставшимися» указателями. На два объекта Widget не существует ни одного указателя, они никогда не будут удалены, а занимаемая ими память расходуется впустую.
После выполнения remove_if и erase ситуация выглядит следующим образом:
Здесь утечка ресурсов становится особенно очевидной, и к настоящему моменту вам должно быть ясно, почему алгоритмы remove и его аналоги (remove_if и unique) не рекомендуется вызывать для контейнеров, содержащих указатели на динамически выделенную память. Во многих случаях разумной альтернативой является алгоритм partition (см. совет 31).
Если без remove никак не обойтись, одно из решений проблемы заключается в освобождении указателей на несертифицированные объекты и присваивании им null перед применением идиомы erase-remove с последующим удалением из контейнера всех null-указателей:
void delAndNullifyUncertified(Widget*& pWidget) // Если объект *pWidget
{ // не сертифицирован,
if (!pWidget()->isCertified()) { //удалить указатель
delete pWidget; //и присвоить ему null
pWidget = 0;
}
for_each(v.begin(), v.end(), // Удалить и обнулить все указатели на
delAndNullifyUncertified); // все указатели на объекты, не прошедшие
// сертификацию
v.erase(remove(v.begin(), v.end(), // Удалить из v указатели null;
static_cast<Widget*>(0)), // 0 преобразуется в указатель, чтобы C++
v.end()); // правильно определял тип третьего параметра
Приведенное решение предполагает, что вектор не содержит null-указателей, которые бы требовалось сохранить. В противном случае вам, вероятно, придется написать собственный цикл, который будет удалять указатели в процессе перебора. Удаление элементов из контейнера в процессе перебора связано с некоторыми тонкостями, поэтому перед реализацией этого решения желательно прочитать совет 9.
Если контейнер указателей заменяется контейнером умных указателей с подсчетом ссылок, то все трудности, связанные с remove, исчезают, а идиома erase-remove может использоваться непосредственно:
template<typename T>
class RCSP{…}; // RCSP = "Reference Counting Smart Pointer"
typedef RCSP<Widget> RCSPW; // RCSPW = "RCSP to Widget"
vector<RCSPW> v; // Создать вектор и заполнить его
… // умными указателями на динамически
v.push_back(RCSPW(new Widget)); // созданные объекты Widget
v.erase(remove_if(v.begin(), v.end(), // Удалить указатели на объекты
not1(mem_fun(&Widget::isCertified))), // Widget, не прошедшие
v.end()); // сертификацию.
// Утечка ресурсов отсутствует!
Чтобы этот фрагмент работал, тип умного указателя (например, RCSP<Widget>) должен преобразовываться в соответствующий тип встроенного указателя (например Widget*). Дело в том, что контейнер содержит умные указатели, но вызываемая функция (например Widget::isCertifed) работает только со встроенными указателями. Если автоматическое преобразование невозможно, компилятор выдаст сообщение об ошибке.
Если в вашем программном инструментарии отсутствует шаблон умного указателя с подсчетом ссылок, попробуйте шаблон shared_ptr из библиотеки Boost. Начальные сведения о Boost приведены в совете 50.
Независимо от того, какая методика будет выбрана для работы с контейнерами динамически созданных указателей — умные указатели с подсчетом ссылок, ручное удаление и обнуление указателей перед вызовом remove-подобных алгоритмов или другой способ вашего собственного изобретения — главная тема данного совета остается актуальной: будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей. Забывая об этой рекомендации, вы своими руками создаете предпосылки для утечки ресурсов.
Совет 34. Помните о том. какие алгоритмы получают сортированные интервалы
Не все алгоритмы работают с произвольными интервалами. Например, для алгоритма remove (см. советы 32 и 33) необходимы прямые итераторы и возможность присваивания через эти итераторы. Таким образом, алгоритм не применим к интервалам, определяемым итераторами ввода, а также к контейнерам map/multimap и некоторым реализациям set/multiset (см. совет 22). Аналогично, многие алгоритмы сортировки (см. совет 31) требуют итераторов произвольного доступа и потому не могут применяться к элементам списка.
При нарушении этих правил компилятор выдает длинные, невразумительные сообщения об ошибках (см. совет 49). Впрочем, существуют и другие, более сложные условия. Самым распространенным среди них является то, что некоторые алгоритмы работают только с интервалами отсортированных значений. Данное требование должно неукоснительно соблюдаться, поскольку нарушение приводит не только к выдаче диагностических сообщений компилятора, но и к непредсказуемому поведению программы на стадии выполнения.
Некоторые алгоритмы работают как с сортированными, так и с несортированными интервалами, но максимальную пользу приносят лишь в первом случае. Чтобы понять, почему сортированные интервалы подходят лучше, необходимо понимать принципы работы этих алгоритмов.
Я знаю, что среди читателей встречаются приверженцы «силового запоминания». Ниже перечислены алгоритмы, требующие обязательной сортировки данных:
binary_search lower_bound
upper_bound equal_range
set_union set_intersection
set_difference set_symmetric_difference
merge inplace_merge
includes
Кроме того, следующие алгоритмы обычно используются с сортированными интервалами, хотя сортировка и не является обязательным требованием:
unique unique_copy
Вскоре будет показано, что в определении «сортированный интервал» кроется одно важное ограничение, но сначала позвольте мне немного прояснить ситуацию с этими алгоритмами. Вам будет проще запомнить, какие алгоритмы работают с сортированными интервалами, если вы поймете, для чего нужна сортировка.
Алгоритмы поиска binary_search, lower_bound, upper_bound и equal_range (см. совет 45) требуют сортированные интервалы, потому что их работа построена на бинарном поиске. Эти алгоритмы, как и функция bsearch из библиотеки C, обеспечивают логарифмическое время поиска, но взамен вы должны предоставить им заранее отсортированные значения.
Вообще говоря, логарифмическое время поиска обеспечивается не всегда. Оно гарантировано лишь в том случае, если алгоритмам передаются итераторы произвольного доступа. Если алгоритм получает менее мощные итераторы (например, двусторонние), он выполняет логарифмическое число сравнений, но работает с линейной сложностью. Это объясняется тем, что без поддержки «итераторной математики» алгоритму необходимо линейное время для перемещения между позициями интервала, в котором производится поиск.
Четверка алгоритмов set_unon, set_inesection, set_diffeence и set_symmetric_difference предназначена для выполнения со множествами операций с линейным временем. Почему этим алгоритмам нужны сортированные интервалы? Потому что в противном случае они не справятся со своей задачей за линейное время. Начинает прослеживаться некая закономерность — алгоритмы требуют передачи сортированных интервалов для того, чтобы обеспечить лучшее быстродействие, невозможное при работе с несортированными интервалами. В дальнейшем мы лишь найдем подтверждение этой закономерности.
Алгоритмы merge и inplace_merge выполняют однопроходное слияние с сортировкой: они читают два сортированных интервала и строят новый сортированный интервал, содержащий все элементы обоих исходных интервалов. Эти алгоритмы работают с линейным временем, что было бы невозможно без предварительной сортировки исходных интервалов.
Перечень алгоритмов, работающих с сортированными интервалами, завершает алгоритм includes. Он проверяет, входят ли все объекты одного интервала в другой интервал. Поскольку includes рассчитывает на сортировку обоих интервалов, он обеспечивает линейное время. Без этого он в общем случае работает медленнее.
