Читать онлайн «Эффективное использование STL». Страница 60

Сравнение строк без учета регистра

Фасет ctype позволяет относительно легко организовать сравнение строк без учета регистра на основе сравнения отдельных символов. Приведенная ниже версия не оптимальна, но по крайней мере она верна. В ней используется практически тот же принцип, что и прежде: строки сравниваются алгоритмом lexicographical_ compare, а отдельные символы сравниваются после приведения к верхнему регистру. Впрочем, на этот раз вместо глобальной переменной используется объект локального контекста. Кстати говоря, сравнение после приведения обоих символов к верхнему регистру не всегда дает тот же результат, что и после приведения к нижнему регистру. Например, во французском языке в символах верхнего регистра принято опускать диакритические знаки, вследствие чего вызов toupper во французском локальном контексте может приводить к потере информации: символы 'ё' и 'е' преобразуются в один символ верхнего регистра 'Е'. В этом случае при сравнении на базе функции toupper символы 'ё' и 'е' будут считаться одинаковыми, а при сравнении на базе tolower они будут считаться разными. Какой из ответов правилен? Вероятно, второй, но на самом деле все зависит от языка, национальных обычаев и специфики приложения.

struct lt_str_l

:public std::binary_function<std::string.std::string.bool>{

struct lt_char{

const std::ctype<char>& ct:

lt_char(const std::ctype<char>& c):ct(c) {}

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

return ct.toupper(x)<ct.toupper(y);

}

};

std::locale loc;

const std::ctype<char>& ct;

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

:loc(L),ct(std::use_facet<std::ctype<char> >(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 вызывается в цикле, а Стандарт С++ требует, чтобы эта функция была виртуальной. Некоторые оптимизаторы выводят вызов виртуальной функции из цикла, но чаще этого не происходит. Циклические вызовы виртуальных функций нежелательны.

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

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

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

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

struct lt_str_2:

public std::binary_function<std::string.std::string.bool>{

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+l];

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

const std::ctype<char>& ct = std::use_facet<std::ctype<char> >(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_l сортировка списка из 23 791 слова заняла 0,86 секунды, а при использовании lt_str_2 понадобилось только 0,4 секунды.

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

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

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

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

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

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

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

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

vector<Widget> vw1,vw2;

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

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

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

vector<Widget> vw;

deque<Widget> dw:

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

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

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

vector<Widget> vw;

list<Widget> lw;

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

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

set<Widget> sw;

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

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

template<typename T,

typename Allocator - allocator<T> > // Шаблон нестандартного

class SpecialContainer {...}:// STL-совместимого контейнера

SpecialContainer<Widget> sew;

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

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

Подобная универсальность объясняется тем, что интервальная функция insert контейнера range вообще не является функцией в общепринятом смысле. Это шаблон функции контейнера, специализация которого с произвольным типом итератора порождает конкретную интервальную функцию insert. Для контейнера vector шаблон insert объявлен в Стандарте следующим образом:

template <class Т, class Allocator = allocator<T> >

class vector {

public:

template<class InputIterator>

void insert(iterator position, InputIterator first. InputIterator last);

};

Каждый стандартный контейнер должен поддерживать шаблонную версию интервальной функции insert. Аналогичные шаблоны также обязательны для интервальных конструкторов и для интервальной формы assign (см. совет 5).

К сожалению, в реализации STL, входящей в комплект поставки версий 4-6, шаблоны функций не объявляются. Библиотека изначально разрабатывалась для MSVC версии 4, а этот компилятор, как и большинство компиляторов того времени, не обладал поддержкой шаблонов функций классов. При переходе от MSCV4 к MSVC6 поддержка этих шаблонов была включена в компилятор, но вследствие судебных дел, косвенно затрагивавших фирму Microsoft, библиотека оставалась практически в неизменном состоянии.