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

const std::ctype& ct;

lt_str_l(const std::locale& L = std::locale::classic()):

loc(L), ct(std::use_facet >(loc)) {}

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(ct));

}

};

Данное решение не оптимально; оно работает медленнее, чем могло бы работать. Проблема чисто техническая: функция toupperвызывается в цикле, а Стандарт C++ требует, чтобы эта функция была виртуальной. Некоторые оптимизаторы выводят вызов виртуальной функции из цикла, но чаще этого не происходит. Циклические вызовы виртуальных функций нежелательны.

В данном случае тривиального решения не существует. Возникает соблазнительная мысль — воспользоваться одной из функций объекта ctype:

const char* ctype::toupper(char* f, char* i) const

Эта функция изменяет регистр символов в интервале [f, i]. К сожалению, для наших целей этот интерфейс не подходит. Чтобы воспользоваться этой функцией для сравнения двух строк, необходимо скопировать обе строки в буферы и затем преобразовать их содержимое к верхнему регистру. Но откуда возьмутся эти буферы? Они не могут быть массивами фиксированного размера (неизвестно, каким должен быть максимальный размер), а динамические массивы потребуют дорогостоящего выделения памяти.

Альтернативное решение заключается в однократном преобразовании каждого символа с кэшированием результата. Такое решение недостаточно универсально — в частности, при использовании 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:

vector vw1, vw2;

…

vw1.insert(vw1.end(), vw2.begin(), vw2.end()); // Присоединить к vw1 копию

// объектов Widget из vw2

Аналогичную операцию можно выполнить с контейнерами vectorи deque:

vector vw;

deque dw;

…

vw.insert(vw.end(), dw.begin(), dw.end()); // Присоединить к vw копию

// объектов Widget из dw

Оказывается, эту операцию можно выполнить независимо от того, в каких контейнерах хранятся копируемые объекты. Подходят даже нестандартные контейнеры:

vector vw;

…

list lw;

…

vw.insert(vw.begin(), lw.begin(), lw.end()); // Присоединить к vw копию

// объектов Widget из lw

set sw;

…

vw.insert(vw.begin(), sw.begin(), sw.end()); // Присоединить к vw копию