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

Альтернативное решение заключается в однократном преобразовании каждого символа с кэшированием результата. Такое решение недостаточно универсально — в частности, при использовании 32-разрядных символов UCS-4 оно абсолютно неработоспособно. С другой стороны, при работе с типом char(8-разрядным в большинстве систем) идея хранения 256 байт дополнительных данных в объекте функции сравнения выглядит вполне реально.

struct lt_str_2:

public std::binary_function {

struct lt_char {

const char* tab;

lt_char(const char* t) : tab(t) {}

bool operator() (char x, char y) const {

return tab[x-CHAR_MIN] < tab[y-CHAR_MIN];

}

};

char tab[CHAR_MAX-CHAR_MIN+1];

lt_str_2(const std::locale& L = std::locale::classic()) {

const std::ctype& ct = std::use_facet >(L);

for (int i = CHAR_MIN; i<=CHAR_MAX; ++i) tab[i-CHAR_MIN]=(char)i;

ct.toupper(tab, tab+(CHAR_MAX-CHAR_MIN+1));

}

bool operator()(const std::string& x, const std::string& y) const {

return std::lexicographical_compare(x.begin(), x.end(),

y.begin(), y.end(), lt_char(tab));

}

}

Как видите, различия между lt_str_1и lt_str_2не так уж велики. В первом случае используется объект функции сравнения символов, использующий фасет ctypeнапрямую, а во втором случае — объект функции сравнения с таблицей заранее вычисленных преобразований символов к верхнему регистру. Второе решение уступает первому, если создать объект функции lt_str_2, воспользоваться им для сравнения нескольких коротких строк и затем уничтожить. С другой стороны, при обработке больших объемов данных lt_str_2работает значительно быстрее lt_str_1. В моих тестах превосходство было более чем двукратным: при использовании lt_str_1сортировка списка из 23 791 слова заняла 0,86 секунды, а при использовании lt_str_2понадобилось только 0,4 секунды.

Итак, что же мы узнали?

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

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

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

Правильное сравнение строк без учета символов требует большого объема рутинной работы, но ее необходимо проделать только один раз. Или вам, как и большинству коллег, не хочется думать о локальных контекстах? Впрочем, лет десять назад никому не хотелось думать об «ошибке 2000 года». И все же у вас больше шансов обойти стороной эту проблему, если ваш локально-зависимый код будет с самого начала правильно работать.

В начале книги я ввел термин «платформа STL», означающий комбинацию конкретного компилятора и конкретной реализации STL. Различие между компилятором и библиотекой особенно важно при использовании компилятора Microsoft Visual C++ версий 6 и ниже (то есть компилятора, входившего в комплект поставки Microsoft Visual Studio версий 6 и ниже), поскольку компилятор иногда способен на большее, чем прилагаемая реализация STL. В настоящем приложении описаны важные недостатки старых платформ STL от Microsoft и предложены обходные решения, делающие работу на этих платформах значительно более удобной.

Дальнейший материал предназначен для разработчиков, использующих Microsoft Visual C++ (MSVC) версий 4-6. В Visual C++ .NET перечисленные проблемы отсутствуют.

Допустим, у вас есть два вектора объектов Widget, требуется скопировать объекты Widgetиз одного вектора в конец другого. Задача решается легко — достаточно воспользоваться интервальной функцией insertконтейнера vector: