[ Главная ] [ Гостевая ]

[ Назад ] [ Содержание ] [ Вперед ]

Алгоритмы

В начале главы 1 я упоминал о том, что львиная доля репутации STL связана с контейнерами, и это вполне объяснимо. Контейнеры обладают массой достоинств и упрощают повседневную работу бесчисленных программистов C++. Но и алгоритмы STL тоже по-своему замечательны и в той же степени облегчают бремя разработчика. Существует более 100 алгоритмов, и встречается мнение, что они предо-ставляют программисту более гибкий инструментарий по сравнению с контейнерами (которых всего-то восемь!). Возможно, недостаточное применение алгоритмов отчасти и объясняется их количеством. Разобраться в восьми типах контейнеров проще, чем запомнить имена и предназначение многочисленных алгоритмов.

В этой главе я постараюсь решить две основные задачи. Во-первых, я представлю некоторые малоизвестные алгоритмы и покажу, как с их помощью упростить себе жизнь. Не беспокойтесь, вам не придется запоминать длинные списки имен. Алгоритмы, представленные в этой главе, предназначены для решения повседневных задач — сравнение строк без учета регистра символов, эффективный поиск n объектов, в наибольшей степени соответствующих заданному критерию, обобщение характеристик всех объектов в заданном интервале и имитация copy_if (алгоритм из исходной реализации HP STL, исключенный в процессе стандартизации).

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

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

Совет 30. Следите за тем, чтобы приемный интервал имел достаточный размер

Контейнеры STL автоматически увеличиваются с добавлением новых объектов (функциями insert, push_front, push_back и т. д.). Автоматическое изменение размеров чрезвычайно удобно, и у многих программистов создается ложное впечатление, что контейнер сам обо всем позаботится и им никогда не придется следить за наличием свободного места. Если бы так!

Проблемы возникают в ситуации, когда программист думает о вставке объектов в контейнер, но не сообщает о своих мыслях STL. Типичный пример:

int transmogrify(int х); // Функция вычисляет некое новое значение

                         // по переданному параметру х

vector<int> values;

… // Заполнение вектора values данными

vector<int> results;     // Применить transmogrify к каждому объекту

transform(values.begin(), // вектора values и присоединить возвращаемые

 values.end(),            // значения к results.

 results.end(),           // Фрагмент содержит ошибку!

 transmogrify);

В приведенном примере алгоритм transform получает информацию о том, что приемный интервал начинается с results.end. С этой позиции он и начинает вывод значений, полученных в результате вызова transmogrify для каждого элемента values. Как и все алгоритмы, использующие приемный интервал, transform записывает свои результаты, присваивая значения элементам заданного интервала. Таким образом, transform вызовет transmogrify для values[0] и присвоит результат *results.end(). Затем функция transmogrify вызывается для values[1] с присваиванием результата *(results.end()+1). Происходит катастрофа, поскольку в позиции *results.end() (и тем более в *(results.end()+1)) не существует объекта! Вызов transform некорректен из-за попытки присвоить значение несуществующему объекту (в совете 50 объясняется, как отладочная реализация STL позволит обнаружить эту проблему на стадии выполнения).

Допуская подобную ошибку, программист почти всегда рассчитывает на то, что результаты вызова алгоритма будут вставлены в приемный контейнер вызовом insert. Если вы хотите, чтобы это произошло, так и скажите. В конце концов, STL — всего лишь библиотека, и читать мысли ей не положено. В нашем примере задача решается построением итератора, определяющего начало приемного интервала, вызовом back_inserter:

vector<int> values;

transform(values.begin(), // Применить transmogrify к каждому

 values.end(),            // объекту вектора values

 back_inserter(results),  // и дописать значения в конец results

 transmogrify);

При использовании итератора, возвращаемого при вызове back_inserter, вызывается push_back, поэтому back_inserter может использоваться со всеми контейнерами, поддерживающими push_back (то есть со всеми стандартными последовательными контейнерами: vector, string, deque и list). Если вы предпочитаете, чтобы алгоритм вставлял элементы в начало контейнера, Воспользуйтесь front_inserter. Во внутренней реализации front_inserter используется push_front, поэтому front_inserter работает только с контейнерами, поддерживающими эту функцию (то есть deque и list).

… //См. ранее

list<int> results; // Теперь используется

                   // контейнер list

transform(values.begin(), values.end(), // Результаты вызова transform

 front_inserter(results),               // вставляются в начало results

 transmogrify); //в обратном порядке

Поскольку при использовании front_inserter новые элементы заносятся в начало results функцией push_front, порядок следования объектов в results будет обратным по отношению к порядку соответствующих объектов в values. Это ишь одна из причин, по которым front_inserter используется реже back_inserter. Другая причина заключается в том, что vector не поддерживает push_front, поэтому front_inserter не может использоваться с vector.

Чтобы результаты transform выводились в начале results, но с сохранением порядка следования элементов, достаточно перебрать содержимое values в обратном порядке:

list<int> results; // См. ранее

transform(values.rbegin(), values.rend(), // Результаты вызова transform

 front_inserter(results),                 // вставляются в начало results

 transmogrify);                           // с сохранением исходного порядка

Итак, front_inserter заставляет алгоритмы вставлять результаты своей работы в начало контейнера, a back_inserter обеспечивает вставку в конец контейнера. Вполне логично предположить, что inserter заставляет алгоритм выводить свои результаты с произвольной позиции:

vector<int> values; // См. ранее

vector<int> results; // См. ранее - за исключением того, что

…                    // results на этот раз содержит данные

                     // перед вызовом transform.

transform(values.begin(), // Результаты вызова transmogrify

 values.end(),            // выводятся в середине results

 inserter(results, results, begin()+results.size()/2),

 transmogrify);

Независимо от выбранной формы — back_inserter, front_inserter или inserter — объекты вставляются в приемный интервал по одному. Как объясняется в совете 5, это может привести к значительным затратам для блоковых контейнеров (vector, string и deque), однако средство, предложенное в совете 5 (интервальные функции), неприменимо в том случае, если вставка выполняется алгоритмом. В нашем примере transform записывает результаты в приемный интервал по одному элементу, и с этим ничего не поделаешь.

При вставке в контейнеры vector и string для сокращения затрат можно последовать совету 14 и заранее вызвать reserve. Затраты на сдвиг элементов при каждой вставке от этого не исчезнут, но по крайней мере вы избавитесь от необходимости перераспределения памяти контейнера:

vector<int> values; // См. Ранее

vector<int> results;

results.reserve(results.size()+values.size()); // Обеспечить наличие

                                               // в векторе results

                                               // емкости для value.size()

                                               // элементов

transform(values.begin(), values.end(),               // То же, что и ранее,

 inserter(results, results.begin()+results.size()/2), // но без лишних

 transmogrify);                                       // перераспределений памяти

При использовании функции reserve для повышения эффективности серии вставок всегда помните, что reserve увеличивает только емкость контейнера, а размер остается неизменным. Даже после вызова reserve при работе с алгоритмом, который должен включать новые элементы в vector или string, необходимо использовать итератор вставки (то есть итератор, возвращаемый при вызове back_inserter, front_inserter или inserter).

Чтобы это стало абсолютно ясно, рассмотрим ошибочный путь повышения эффективности для примера, приведенного в начале совета (с присоединением результатов обработки элементов values к results):

vector<int> values; // См. ранее

vector<int> results;

results.reserve(results.size()+values.size()); // См. ранее

transform(values.begin(), values.end(), // Результаты вызова

 results.end(),                         // transmogrify записываются

 transmogrify);                         // в неинициализированную

                                        // память; последствия

                                        // непредсказуемы!

В этом фрагменте transform в блаженном неведении пытается выполнить присваивание в неинициализированной памяти за последним элементом results. Обычно подобные попытки приводят к ошибкам времени выполнения, поскольку операция присваивания имеет смысл лишь для двух объектов, но не между объектом и двоичным блоком с неизвестным содержимым. Но даже если этот код каким-то образом справится с задачей, вектор results не будет знать о новых «объектах», якобы созданных в его неиспользуемой памяти. С точки зрения results вектор после вызова transform сохраняет прежний размер, а его конечный итератор будет указывать на ту же позицию, на которую он указывал до вызова transform. Мораль? Использование reserve без итератора вставки приводит к непредсказуемым последствиям внутри алгоритмов и нарушению целостности данных в контейнере.

В правильном решении функция reserve используется в сочетании с итератором вставки:

vector<int> values; // См. ранее

vector<int> results;

results.reserve(results.size()+values.size()); // См. ранее

transform(values.begin(), values.end(), // Результаты вызова

 back_inserter(results),                // transmogrify записываются

 transmogrify);                         // в конец вектора results

                                        // без лишних перераспределений

                                        // памяти

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

Допустим, вызов transform должен записывать результаты в results поверх существующих элементов. Если количество элементов в results не меньше их количества в values, задача решается просто. В противном случае придется либо воспользоваться функцией resize для приведения results к нужному размеру:

vector<int> results;

if (results.size() < values.size()) { // Убедиться в том, что размер

 results.resize(values.size());       // results по крайней мере

}                                     // не меньше размера values


transform(values,begin(), values.end(), // Перезаписать первые

 back_inserter(results), // values.size() элементов results

 transmogrify);

либо очистить results и затем использовать итератор вставки стандартным способом:

results.clear();                // Удалить из results все элементы

results.reserve(values.size()); // Зарезервировать память

transform(values.begin(), values.end(), // Занести выходные данные

 back_inserter(results),                // transform в results

 transmogrify);

В данном совете было продемонстрировано немало вариаций на заданную тему, но я надеюсь, что в памяти у вас останется основная мелодия. Каждый раз, когда вы используете алгоритм, требующий определения приемного интервала, позаботьтесь о том, чтобы приемный интервал имел достаточные размеры или автоматически увеличивался во время работы алгоритма. Второй вариант реализуется при помощи итераторов вставки — таких, как ostream_iterator, или возвращаемых в результате вызова back_inserter, front_inserter и inserter. Вот и все, о чем необходимо помнить.

Совет 31. Помните о существовании разных средств сортировки

Когда речь заходит об упорядочении объектов, многим программистам приходит в голову всего один алгоритм: sort (некоторые вспоминают о qsort, но после прочтения совета 46 они раскаиваются и возвращаются к мыслям о sort).

Действительно, sort — превосходный алгоритм, однако полноценная сортировка требуется далеко не всегда. Например, если у вас имеется вектор объектов Widget и вы хотите отобрать 20 «лучших» объектов с максимальным рангом, можно ограничиться сортировкой, позволяющей выявить 20 нужных объектов и оставить остальные объекты несортированными. Задача называется частичной сортировкой, и для ее решения существует специальный алгоритм partial_sort:

bool qualityCompare(const Widgets lhs, const Widgets rhs) {

 // Вернуть признак сравнения атрибутов quality

 // объектов lhs и rhs

}

partial_sort(widgets.begin(), // Разместить 20 элементов

 widgets.begin()+20,          // с максимальным рангом

 widgets.end(),               // в начале вектора widgets

 qualityCompare);

… // Использование widgets

После вызова partial_sort первые 20 элементов widgets находятся в начале контейнера и располагаются по порядку, то есть widgets[0] содержит Widget с наибольшим рангом, затем следует widgets[1] и т. д.

Если вы хотите выделить 20 объектов Widget и передать их 20 клиентам, но при этом вас не интересует, какой объект будет передан тому или иному клиенту, даже алгоритм partial_sort превышает реальные потребности. В описанной ситуации требуется выделить 20 «лучших» объектов Widget в произвольном порядке. В STL имеется алгоритм, который решает именно эту задачу, однако его имя выглядит несколько неожиданно — он называется nth_element.

Алгоритм nth_element сортирует интервал таким образом, что в заданной вами позиции n оказывается именно тот элемент, который оказался бы в ней при полной сортировке контейнера. Кроме того, при выходе из nth_element ни один из элементов в позициях до n не находится в порядке сортировки после элемента, находящегося в позиции n, а ни один из элементов в позициях после n не предшествует элементу, находящемуся в позиции n. Если такая формулировка кажется слишком сложной, это объясняется лишь тем, что мне приходилось тщательно подбирать слова. Вскоре я объясню причины, но сначала мы рассмотрим пример использования nth_element для перемещения 20 «лучших» объектов Widget в начало контейнера widgets:

nth_element(widgets.begin(), // Переместить 20 «лучших» элементов

 widgets.begin()+20,         // в начало widgets

 widgets.end(),              // в произвольном порядке

 qualityCompare);

Как видите, вызов nth_element практически не отличается от вызова partial_sort. Единственное различие заключается в том, что partial_sort сортирует элементы в позициях 1-20, a nth_element этого не делает. Впрочем, оба алгоритма перемещают 20 объектов Widget с максимальными значениями ранга в начало вектора.

Возникает важный вопрос — что делают эти алгоритмы для элементов с одинаковыми значениями атрибута? Предположим, вектор содержит 12 элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20 «лучших» объектов Widget будет состоять из 12 объектов с рангом 1 и 8 из 15 объектов с рангом 2. Но как алгоритмы partial_sort и nth_element определяют, какие из 15 объектов следует отобрать в «верхнюю двадцатку»? И как алгоритм sort выбирает относительный порядок размещения элементов при совпадении рангов?

Алгоритмы partial_sort и nth_element упорядочивают эквивалентные элементы по своему усмотрению, и сделать с этим ничего нельзя (понятие эквивалентности рассматривается в совете 19). Когда в приведенном примере возникает задача заполнения объектами Widget с рангом 2 восьми последних позиций в «верхней двадцатке», алгоритм выберет такие объекты, какие сочтет нужным. Впрочем, такое поведение вполне разумно. Если вы запрашиваете 20 «лучших» объектов Widget, а некоторых объекты равны, то в результате возвращенные объекты будут по крайней мере «не хуже» тех, которые возвращены не были.

Полноценная сортировка обладает несколько большими возможностями. Некоторые алгоритмы сортировки стабильны. При стабильной сортировке два эквивалентных элемента в интервале сохраняют свои относительные позиции после сортировки. Таким образом, если Widget A предшествует Widget B в несортированном векторе widgets и при этом ранги двух объектов совпадают, стабильный алгоритм сортировки гарантирует, что после сортировки Widget A по-прежнему будет предшествовать Widget B. Нестабильный алгоритм такой гарантии не дает.

Алгоритм partial_sort, как и алгоритм nth_element, стабильным не является. Алгоритм sort также не обладает свойством стабильности, но существует специальный алгоритм stable_sort, который, как следует из его названия, является стабильным. При необходимости выполнить стабильную сортировку, вероятно, следует воспользоваться stable_sort. В STL не входят стабильные версии partial_sort и nth_element.

Следует заметить, что алгоритм nth_element чрезвычайно универсален. Помимо выделения n верхних элементов в интервале, он также может использоваться для вычисления медианы по интервалу и поиска значения конкретного процентиля[3]:

vector<Widget>::iterator begin(widgets.begin()); // Вспомогательные переменные

vector<Widget>::iterator end(widgets.end()); // для начального и конечного

                                             // итераторов widgets

vector<Widget>::iterator goalPosition; // Итератор, указывающий на

                                       // интересующий нас объект Widget

// Следующий фрагмент находит Widget с рангом median

goalPosition = begin + widgets.size()/2; // Нужный объект находится

                                         // в середине отсортированного вектора

nth_element(begin, goalPosition, end, // Найти ранг median в widgets

 qualityCompare);

… // goalPositon теперь указывает

  // на Widget с рангом median


// Следующий фрагмент находит Widget с уровнем 75 процентилей

vector<Widget>::size_type goalOffset = // Вычислить удаление нужного

 0.25*widgets.size();                  // объекта Widget от начала

nth_element(begin, egin+goalOffset, nd, // Найти ранг в

 ualityCompare);                        // begin+goalOffset теперь

…                                       // указывает на Widget

                                        // с уровнем 75 процентилей

Алгоритмы sort, stable_sort и partial_sort хорошо подходят для упорядочивания результатов сортировки, а алгоритм nth_element решает задачу идентификации верхних n элементов или элемента, находящегося в заданной позиции. Иногда возникает задача, близкая к алгоритму nth_element, но несколько отличающаяся от него. Предположим, вместо 20 объектов Widget с максимальным рангом потребовалось выделить все объекты Widget с рангом 1 или 2. Конечно, можно отсортировать вектор по рангу и затем найти первый элемент с рангом, большим 2. Найденный элемент определяет начало интервала с объектами Widget, ранг которых превышает 2.

Полная сортировка потребует большого объема работы, совершенно ненужной для поставленной цели. Более разумное решение основано на использовании алгоритма partition, упорядочивающего элементы интервала так, что все элементы, удовлетворяющие заданному критерию, оказываются в начале интервала.

Например, для перемещения всех объектов Widget с рангом 2 и более в начало вектора widgets определяется функция идентификации:

bool hasAcceptableQualty(const Widgets w) {

 // Вернуть результат проверки того, имеет ли объект w ранг больше 2

}

Затем эта функция передается при вызове partition:

vector<Widget>::iterator goodEnd = // Переместить все объекты Widget,

 partition(widgets.begin(),        // удовлетворяющие условию

 widgets.end(),                    // hasAcceptableQuality, в начало

 hasAcceptableQuality);            // widgets и вернуть итератор

                                   // для первого объекта,

                                   // не удовлетворяющего условию

После вызова интервал от widgets.begin() до goodEnd содержит все объекты Widget с рангом 1 и 2, а интервал от goodEnd до widgets.end() содержит все объекты Widget с большими значениями ранга. Если бы в процессе деления потребовалось сохранить относительные позиции объектов Widget с эквивалентными рангами, вместо алгоритма partition следовало бы использовать stable_partition.

Алгоритмы sort, stable_sort, partial_sort и nth_element работают с итераторами произвольного доступа, поэтому они применимы только к контейнерам vector, string, deque и array. Сортировка элементов в стандартных ассоциативных контейнерах бессмысленна, поскольку эти контейнеры автоматически хранятся в отсортированном состоянии благодаря собственным функциям сравнения. Единственным контейнером, к которому хотелось бы применить алгоритмы sort, stable_sort, partial_sort и nth_element, является контейнер list — к сожалению, это невозможно, но контейнер list отчасти компенсирует этот недостаток функцией sort (интересная подробность: list::sort выполняет стабильную сортировку). Таким образом, полноценная сортировка list возможна, но алгоритмы partial_sort и nth_element приходится имитировать. В одном из таких обходных решений элементы копируются в контейнер с итераторами произвольного доступа, после чего нужный алгоритм применяется к этому контейнеру. Другое обходное решение заключается в создании контейнера, содержащего list::iterator, применении алгоритма к этому контейнеру и последующему обращению к элементам списка через итераторы. Третье решение основано на использовании информации упорядоченного контейнера итераторов для итеративной врезки (splice) элементов list в нужной позиции. Как видите, выбор достаточно широк.

Алгоритмы partition и stable_partition отличаются от sort, stable_sort, partial_sort и nth_element тем, что они работают только с двусторонними итераторами. Таким образом, алгоритмы partition и stable_partition могут использоваться с любыми стандартными последовательными контейнерами.

Подведем краткий итог возможностей и средств сортировки.

• Полная сортировка в контейнерах vector, string, deque и array: алгоритмы sort и stable_sort.

• Выделение n начальных элементов в контейнерах vector, string, deque и array: алгоритм partial_sort.

• Идентификация n начальных элементов или элемента, находящегося в позиции n, в контейнерах vector, string, deque и array: алгоритм nth_element.

• Разделение элементов стандартного последовательного контейнера на удовлетворяющие и не удовлетворяющие некоторому критерию: алгоритмы partition и stable_partition.

• Контейнер list: алгоритмы partition и stable_partition; вместо sort и stable_sort может использоваться list::sort. Алгоритмы partial_sort или nth_element приходится имитировать. Существует несколько вариантов их реализации, некоторые из которых были представлены выше.

Чтобы данные постоянно находились в отсортированном состоянии, сохраните их в стандартном ассоциативном контейнере. Стоит также рассмотреть возможность использования стандартного контейнера priority_queue, данные которого тоже хранятся в отсортированном виде (контейнер priority_queue традиционно считается частью STL, но, как упоминалось в предисловии, в моем определении «контейнер STL» должен поддерживать итераторы, тогда как контейнер priority_queue их не поддерживает).

«А что можно сказать о быстродействии?» — спросите вы. Хороший вопрос. В общем случае время работы алгоритма зависит от объема выполняемой работы, а алгоритмам стабильной сортировки приходится выполнять больше работы, чем алгоритмам, игнорирующим фактор стабильности. В следующем списке алгоритмы, описанные в данном совете, упорядочены по возрастанию затрачиваемых ресурсов (времени и памяти):

1. partition;

2. stable_partition;

3. nth_element;

4. partial_sort;

5. sort;

6. stable_sort.

При выборе алгоритма сортировки я рекомендую руководствоваться целью, а не соображениями быстродействия. Если выбранный алгоритм ограничивается строго необходимыми функциями и не выполняет лишней работы (например, partition вместо полной сортировки алгоритмом sort), то программа будет не только четко выражать свое предназначение, но и наиболее эффективно решать поставленную задачу средствами STL.

Совет 32. Сопровождайте вызовы remove-подобных алгоритмов вызовом erase

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

Объявление remove выглядит следующим образом:

template<class ForwardIterator, class T>

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

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

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

vector<int> v;             // Создать vector<int> и заполнить его

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<int>::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] образуется новая «дыра».

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

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

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

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

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

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

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

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

v.erase(remove(v.begin(), v.end(), 99), v.end()); // Фактическое удаление

                                                  // элементов со значением 99

cout << v.size(); // Теперь выводится 7

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

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

…             // Заполнить данными

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

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

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

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

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

Как только вы поймете, что алгоритм remove не может «по-настоящему» удалять объекты из контейнера, применение его в сочетании с erase войдет в привычку. Не забывайте, что remove — не единственный алгоритм, к которому относится это замечание. Существуют два других remove-подобных алгоритма: remove_if и unique.

Сходство между remove и remove_if настолько прямолинейно, что я не буду на нем останавливаться, но алгоритм unique тоже похож на remove. Он предназначен для удаления смежных повторяющихся значений из интервала без доступа к контейнеру, содержащему элементы интервала. Следовательно, если вы хотите действительно удалить элементы из контейнера, вызов unique должен сопровождаться парным вызовом erase. В контейнере list также предусмотрена функция unique, производящая фактическое удаление смежных дубликатов. По эффективности она превосходит связку erase-unique.

Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей

Предположим, мы динамически создаем ряд объектов Widget и сохраняем полученные указатели в векторе:

class Widget {

public:

 …

 bool isCertified() const; // Функция сертификации объектов Widget

}

vector<Widget*> v; // Создать вектор и заполнить его указателями

…                  // на динамически созданные объекты Widget

v.push_back(new Widget);

Поработав с v в течение некоторого времени, вы решаете избавиться от объектов Widget, не сертифицированных функцией Widget, поскольку они вам не нужны. С учетом рекомендаций, приведенных в совете 43 (по возможности использовать алгоритмы вместо циклов), и того, что говорилось в совете 32 о связи remove и erase, возникает естественное желание использовать идиому erase-remove, хотя в данном случае используется алгоритм remove_if:

v.erase(remove_if(v.begin(),  v.end(), // Удалить указатели на объекты

 not1(mem_fun(&Widget::isCertified))), // Widget, непрошедшие

 v.end());                             // сертификацию.

                                       // Информация о mem_fun

                                       // приведена в совете 41.

Внезапно у вас возникает беспокойство по поводу вызова erase, поскольку вам смутно припоминается совет 7 — уничтожение указателя в контейнере не приводит к удалению объекта, на который он ссылается. Беспокойство вполне оправданное, но в этом случае оно запоздало. Вполне возможно, что к моменту вызова erase утечка ресурсов уже произошла. Прежде чем беспокоиться о вызове erase, стоит обратить внимание на remove_if.

Допустим, перед вызовом 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 рассчитывает на сортировку обоих интервалов, он обеспечивает линейное время. Без этого он в общем случае работает медленнее.

В отличие от перечисленных алгоритмов, unique и unique_copy способны работать и с несортированными интервалами. Но давайте взглянем на описание unique в Стандарте (курсив мой): «…Удаляет из каждой смежной группы равных элементов все элементы, кроме первого».

Иначе говоря, если вы хотите, чтобы алгоритм unique удалил из интервала все дубликаты (то есть обеспечил «уникальность» значений в интервале), сначала необходимо позаботиться о группировке всех дубликатов. Как нетрудно догадаться, именно эта задача и решается в процессе сортировки. На практике алгоритм unique обычно применяется для исключения всех дубликатов из интервала, поэтому интервал, передаваемый при вызове unique (или unique_copy), должен быть отсортирован. Программисты Unix могут обратить внимание на поразительное сходство между алгоритмом STL unique и командой Unix uniq — подозреваю, что совпадение отнюдь не случайное.

Следует помнить, что unique исключает элементы из интервала по тому же принципу, что и remove, то есть ограничивается «логическим» удалением. Если вы не совсем уверены в том, что означает этот термин, немедленно обратитесь к советам 32 и 33. Трудно выразить, сколь важно доскональное понимание принципов работы remove и remove-подобных алгоритмов. Общих представлений о происходящем недостаточно. Если вы не знаете, как работают эти алгоритмы, у вас будут неприятности.

Давайте посмотрим, что же означает само понятие «сортированный интервал». Поскольку STL позволяет задать функцию сравнения, используемую в процессе сортировки, разные интервалы могут сортироваться по разным критериям. Например, интервал int можно отсортировать как стандартным образом (то есть по возрастанию), так и с использованием greater<int>, то есть по убыванию. Интервал объектов Widget может сортироваться как по цене, так и по дате. При таком изобилии способов сортировки очень важно, чтобы данные сортировки, находящиеся в распоряжении контейнера STL, была логически согласованы. При передаче сортированного интервала алгоритму, который также получает функцию сравнения, проследите за тем, чтобы переданная функция сравнения вела себя так же, как функция, применявшаяся при сортировке интервала.

Рассмотрим пример неправильного подхода:

vector<int> v;                            // Создать вектор, заполнить

…                                         // данными, отсортировать

sort(v.begin(), v.end(), greater<int>()); // по убыванию.

… // Операции с вектором

  // (не изменяющие содержимого).

bool a5Exists =                        // Поиск числа 5 в векторе.

 binary_search(v.begin(), v.end(), 5); // Предполагается, что вектор

                                       // отсортирован по возрастанию!

По умолчанию binary_search предполагает, что интервал, в котором производится поиск, отсортирован оператором < (то есть по возрастанию), но в приведенном примере вектор сортируется по убыванию. Как нетрудно догадаться, вызов binary_search (или lower_bound и т. д.) для интервала, порядок сортировки которого отличен от ожидаемого, приводит к непредсказуемым последствиям.

Чтобы программа работала правильно, алгоритм binary_search должен использовать ту же функцию сравнения, которая использовалась при вызове sort:

bool a5Exists = binаry_search(v.begin(), v.end(), 5, greater<int>());

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

Одиннадцать алгоритмов требуют передачи сортированных интервалов для того, чтобы обеспечить повышенную эффективность, невозможную без соблюдения этого требования. Передавайте им только сортированные интервалы, помните о соответствии двух функций сравнения (передаваемой алгоритму и используемой при сортировке) и вы избавитесь от хлопот при проведении поиска, слияния и операций с множествами, а алгоритмы unique и unique_copy будут удалять все дубликаты — чего вы, вероятно, и добивались.

Совет 35. Реализуйте простые сравнения строк без учета регистра символов с использованием mismatch или lexicographical_compare

Один из вопросов, часто задаваемых новичками в STL — «Как в STL сравниваются строки без учета регистра символов?» Простота этого вопроса обманчива. Сравнения строк без учета регистра символов могут быть очень простыми или очень сложными в зависимости от того, насколько общим должно быть ваше решение. Если игнорировать проблемы интернационализации и ограничиться строками, на которые была рассчитана функция strcmp, задача проста. Если решение должно работать со строками в языках, не поддерживаемых strcmp (то есть практически в любом языке, кроме английского), или программа должна использовать нестандартный локальный контекст, задача чрезвычайно сложна.

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