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

int ciStringCompareImpl(const string& si, // Реализация приведена далее

 const string& s2);

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

 if (s1.size()<=s2.size() return cStringCompareImpl(s1, s2);

 else return -ciStringComparelmpl(s2, s1);

}

Внутри ciStringCompareImpl всю тяжелую работу выполняет алгоритм mismatch. Он возвращает пару итераторов, обозначающих позиции первых отличающихся символов в интервалах:

int ciStringCompareImpl(const string& si, const string& s2) {

 typedef pair<string::const_iterator, // PSCI = "pair of

 string::const_iterator> PSCI;        // string::const_iterator"

 PSCI p = mismatch(      // Использование ptr_fun

  s1.begin(), s1, end(), // рассматривается

  s2.begin(),            // в совете 41

  not2(ptr_fun(сiCharCompare)));

 if (p.first==s1.end()) {           // Если условие истинно,

  if (p.second==s2.end()) return 0; // либо s1 и s2 равны.

  else return -1; // либо s1 короче s2

 }

 return ciCharCompare(*p.first, *p.second); // Отношение между строками

}                                           // соответствует отношению

                                            // между отличающимися

                                            // символами

Надеюсь, комментарии достаточно четко объясняют происходящее. Зная первую позицию, в которой строки различаются, можно легко определить, какая из строк предшествует другой (или же определить, что эти строки равны), В предикате, переданном mismatch, может показаться странной лишь конструкция not2(ptr_fun(ciCharCompare)). Предикат возвращает true для совпадающих символов, поскольку алгоритм mismatch прекращает работу, когда предикат возвращает false. Для этой цели нельзя использовать ciCharCompare, поскольку возвращается -1, 0 или 1, причем по аналогии с strcmp нулевое значение возвращается для совпадающих символов. Если передать ciCharCompare в качестве предиката для mismatch, C++ преобразует возвращаемое значение ciCharCompare к типу bool, а в этом типе нулю соответствует значение false — результат прямо противоположен тому, что требовалось! Аналогично, когда ciCharCompare возвращает 1 или -1, результат будет интерпретирован как true, поскольку в языке C все целые числа, отличные от нуля, считаются истинными логическими величинами. Чтобы исправить эту семантическую «смену знака», мы ставим not2 и ptr_fun перед ciCharCompare и добиваемся желаемого результата.

Второй вариант реализации ciStringCompare основан на традиционном предикате STL; такая функция может использоваться в качестве функции сравнения в ассоциативных контейнерах. Реализация проста и предельно наглядна, поскольку достаточно модифицировать ciCharCompare для получения функции сравнения символов с предикатным интерфейсом, а затем поручить всю работу по сравнению строк алгоритму lexicographical_compare, занимающему второе место в STL по длине имени:

bool ciCharLess(char c1, char c2)          // Вернуть признак того,

{                                          // предшествует ли c1

                                           // символу с2 без учета

 return                                    // регистра. В совете 46

  tolower(static_cast<unsigned char>(c1))< // объясняется, почему

  tolower(static_cast<unsigned char>(c2)); // вместо функции может

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

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

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