Эффективное использование STL

Мейерс Скотт

} // оказаться предпочтительным

// объект функции

bool ciStringCompare(const string& s1, const string& s2) {

 return lexicographical_compare(s1.begin, s1.end, // Описание

s2.begin, s2.end, // алгоритма

ciCharLess); // приведено далее

}

Нет, я не буду долго хранить секрет. Самое длинное имя у алгоритма

set_symmetric_difference

.

Если вы знаете, как работает

lexicographical_compare

, приведенный выше фрагмент понятен без объяснений, а если не знаете — это легко поправимо.

Алгоритм

lexicographical_compare

является обобщенной версией

strcmp

. Функция

strcmp

работает только с символьными массивами, а

lexicographical_compare

работает с интервалами значений любого типа. Кроме того, если

strcmp

всегда сравнивает два символа и определяет отношение между ними (равенство, меньше, больше), то

lexicographical_compare

может получать произвольный предикат, который определяет, удовлетворяют ли два значения пользовательскому критерию.

В предыдущем примере алгоритм

lexicographical_compare

должен найти первую позицию, в которой

s1

и

s2

различаются по критерию

ciCharLess

. Если для символов в этой позиции

ciCharLess

возвращает

true

, то же самое делает и

lexicographical_compare

: если в первой позиции, где символы различаются, символ первой строки предшествует соответствующему символу второй строки, то первая строка предшествует второй. Алгоритм

lexicographical_compare

, как и

strcmp

, считает два интервала равных величин равными, поэтому для таких интервалов возвращается значение

false

: первый интервал не предшествует второму. Кроме того, по аналогии с

strcmp

, если первый интервал завершается до обнаружения различия,

lexicographical_compare

возвращает

true

— префикс предшествует любому интервалу, в который он входит.

Довольно о

mismatch

и

lexicographical_compare

. Хотя в этой книге большое значение уделяется переносимости программ, я просто обязан упомянуть о том, что функции сравнения строк без учета регистра символов присутствуют во многих нестандартных расширениях стандартной библиотеки C. Обычно эти функции называются

stricmp

или

strcmpi

и по аналогии с функциями, приведенными в данном совете, игнорируют проблемы интернационализации. Если вы готовы частично пожертвовать переносимостью программы, если строки заведомо не содержат внутренних нуль-символов, а проблемы интернационализации вас не волнуют, то простейший способ сравнения строк без учета регистра символов вообще не связан с STL. Обе строки преобразуются в указатели

const char*

(см. совет 16), передаваемые при вызове

stricmp

или

strcmpi

:

int ciStringCompare(const string& si1, const string& s2) {

 return stricmp(sl.c_str, s2.c_str); // В вашей системе вместо stricmp

} // может использоваться другое имя

Функции

strcmp/strcmp

, оптимизированные для выполнения единственной задачи, обычно обрабатывают длинные строки значительно быстрее, чем обобщенные алгоритмы

mismatch

и

lexicographical_compare

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

Совет 36. Правильно реализуйте copy_if

В STL имеется 11 алгоритмов, в именах которых присутствует слово

copy

:

copy copy_backward

replace_copy reverse_copy

replace_copy_if unique_copy

remove_copy rotate_copy

remove_copy_if partial_sort_copy

uninitialized_copy

Но

как ни странно, алгоритма

copy_if

среди них нет. Таким образом, вы можете вызывать

replace_copy_if

и

remove_copy_if

, к вашим услугам

copy_backward

и

reverse_copy

, но если вдруг потребуется просто скопировать элементы интервала, удовлетворяющие определенному предикату, вам придется действовать самостоятельно.

Предположим, имеется функция для отбора «дефектных» объектов

Widget

:

bool isDefective(const Widget& w);

Требуется скопировать все дефектные объекты

Widget

из вектора в

cerr

. Если бы алгоритм

copy_if

существовал, это можно было бы сделать так:

vector<Widget> widgets;

…

copy_if(widgets.begin, widgets.end, // He компилируется -

 ostream_iterator<Widget>(cerr, "\n"), // в STL не существует

 isDefective); // алгоритма copy_if

По иронии судьбы алгоритм

copy_if

входил в исходную версию STL от Hewlett Packard, которая была заложена в основу библиотеки STL, ставшей частью стандартной библиотеки C++. В процессе сокращения HP STL до размеров, подходящих для стандартизации, алгоритм

copy_if

остался за бортом.

В книге «The C++ Programming Language» [7] Страуструп замечает, что реализация

copy_if

выглядит элементарно — и он прав, но это вовсе не означает, что каждый программист сразу придет к нужному решению. Например, ниже приведена вполне разумная версия

copy_if

, которую предлагали многие программисты (в том числе и я):

template<typename InputIterator, // Не совсем правильная

 typename OutputIterator, // реализация copy_if

 typename Predicate>

OutputIterator copy_if(InputIterator begin, InputIterator end,

 OutputIterator destBegin, Predicate p) {

 return remove_copy_if(begin, end, destBegin, not1(p));

}

Решение основано на простом факте: хотя STL не позволяет сказать «скопировать все элементы, для которых предикат равен

true

», но зато можно потребовать «скопировать все элементы, кроме тех, для которых предикат неравен

true

». Создается впечатление, что для реализации

copy_if

достаточно поставить

not1

перед предикатом, который должен передаваться

copy_if

, после чего передать полученный предикат

remove_copy_if

. Результатом является приведенный выше код.

Если бы эти рассуждения были верны, копирование дефектных объектов Widget можно было бы произвести следующим образом:

copy_if(widgets.begin, widgets.end, // Хорошо задумано,

 ostream_iterator<Widget>(cerr, "\n"), // но не компилируется

 isDefective);

Компилятор недоволен попыткой применения

not1

к

isDefective

(это происходит внутри

copy_if

). Как объясняется в совете 41,

not1

не может напрямую применяться к указателю на функцию — сначала указатель должен пройти через

ptr_fun

. Чтобы вызвать эту реализацию

copy_if

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

copy_if

. Приведенная выше реализация хороша, но недостаточно хороша.