• Главная
• Контакты
• Нашёл ошибку
• Прислать материал
• Добавить в избранное

В совете 35 приведена реализация сравнения строк без учета регистра символов с применением алгоритмов mismatch и lexicographical_compare, но в нем также указано, что полноценное решение должно учитывать локальный контекст. Книга посвящена STL, а не вопросам интернационализации, поэтому локальным контекстам в ней не нашлось места. Тем не менее, Мэтт Остерн, автор книги «Generic Programming and the STL» [4], посвятил этой теме статью в майском номере журнала «C++ Report» [11]. Текст этой статьи приведен в настоящем приложении. Я благодарен Мэтту и фирме 101communications за то, что они разрешили мне это сделать.

Мэтт Остерн

Если вам когда-либо доводилось писать программы, в которых используются строки (а кому, спрашивается, не доводилось?), скорее всего, вы встречались с типичной ситуацией — две строки, различающиеся только регистром символов, должны были интерпретироваться как равные. В этих случаях требовалось, чтобы операции сравнения — проверка равенства, больше-меньше, выделение подстрок, сортировка — игнорировали регистр символов. Программисты очень часто спрашивают, как организовать подобные операции средствами стандартной библиотеки C++. На этот вопрос существует огромное количество ответов, многие из которых неверны.

Прежде всего необходимо избавиться от мысли о написании класса, сравнивающего строки без учета регистра. Да, с технической точки зрения это более или менее возможно. Тип

std::string

std::basic_string<char, std::char_trais<char>, std::allocator<char> >

basic_string

<

=

• Вы не сможете выполнять операции ввода-вывода или это потребует больших дополнительных хлопот. Классы ввода-вывода стандартной библиотеки (такие как

std::basic_istream

std::basic_ostream

std::basic_string

std::ostream

std::basic_ostream<char, char_traits<char> >

traits

std::basic_string<char, my_traits_class>

std::basic_ostream<char, my_traits_class>

cin

cout

• Игнорирование регистра символов является не свойством объекта, а лишь контекстом его использования. Вполне возможно, что в одном контексте строки должны интерпретироваться с учетом регистра, а в другом контексте регистр должен игнорироваться (например, при установке соответствующего режима пользователем).

• Решение не соответствует канонам. Класс

char_traits

• Этого вообще не достаточно. Даже если все функции

basic_string

std::search

std::find_end

basic_string

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

string

string::find_first

string::rfind

std::sort(C.begin(), C.end().compare_without_case);

Написанию таких объектов и посвящена эта статья.

Существует несколько способов упорядочения слов по алфавиту. Зайдите в книжный магазин и посмотрите, как расставлены книги на полках. Предшествует ли имя

1. См. статью Александреску А. (Andrei Alexandrescu) в майском номере «C++ Report» за 2000 г. [19].

Mary McCarthy имени Bernard Malamud или следует после него? (В действительности это лишь вопрос привычки, я встречал оба варианта.) Впрочем, простейший способ сравнения строк хорошо знаком нам по школе: речь идет о лексикографическом, или «словарном», сравнении, основанном на последовательном сравнений отдельных символов двух строк.

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

x

y

std::string

x<y

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

В приведенном выражении алгоритм

lexicographical_compare

<

lexicographical_compare

lexicographical_compare

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

struct lt_nocase:

 public std::binary_function<char, char, bool> {

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

  return std::toupper(static_cast<unsigned char>(x))<

   std::toupper(static_cast<unsigned char>(y));

 }

};

«У каждой сложной задачи есть решение простое, элегантное и… неправильное». Авторы книг C++ обожают этот класс за простоту и наглядность. Я тоже неоднократно использовал его в своих книгах. Он почти правилен, и все-таки не совсем, хотя недостаток весьма нетривиален. Следующий пример выявляет этот недостаток:

int main() {

 const char* s1 = "GEW\334RZTRAMINER";

 const char* s2 = "gew\374rztraminer";

 printf("s1=%s, s2=%s\n", s1, s2);

 printf("s1<s2:%s\n",

  std::lexicographical_compare(s1, s1+14, s2, s2+14, lt_nocase())

  ?"true":"false");

}

Попробуйте запустить эту программу в своей системе. На моем компьютере (Silicon Graphics О2 с системой IRIX 6.5) результат выглядел так:

s1=GEWURZTRAMINER,s2=gewurztraminer

s1<s2:true

Странно… Разве при сравнении без учета регистра «GEWURZTRAMINER» и «gewurztraminer» не должны быть равными? И еще возможен вариант с небольшой модификацией: если перед командой printf вставить строку

setlocale(LC_ALL, "de");

результат неожиданно изменяется:

s1=GEWURZTRAMINER,s2=gewurztraminer

s1<s2:false

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

Символьный тип

char

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

isalpha

toupper

По умолчанию функции обработки символов работают с кодировкой, подходящей для простого английского текста. Символ '\374' не изменяется функцией

toupper

setlocale(LC_ALL, "de");

сообщает библиотеке C о переходе на немецкие правила (по крайней мере в системе IRIX — имена локальных контекстов не стандартизованы). В немецком языке есть символ u, поэтому функция

toupper

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

toupper

toupper

При использовании

toupper

binary_search

setlocalе

setlocalе

В языке C приемлемого решения этой проблемы не существует. Библиотека C использует единственный локальный контекст, и с этим ничего не поделаешь. Решение существует в языке C++.

В стандартной библиотеке C++ локальный контекст не является глобальной структурой данных, запрятанной где-то в недрах реализации библиотеки. Это объект типа

std::locale

std::locale L = std::locale::classic();

Локальный контекст немецкого языка создается командой

std::locale L("de");

Имена локальных контекстов, как и в библиотеке C, не стандартизованы. Список имен локальных контекстов, доступных в вашей реализации, следует искать в документации.

Локальные контексты C++ делятся на фасеты (

facets

std::use_facet

ctype

c1

c2

char

L

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

bool result = ct.toupper(c1) < ct.toupper(c2);

Предусмотрена особая сокращенная запись:

std::toupper(c, L)

std::use_facet<std::ctype<char> >(L).toupper(c)

Использование

use_facet

По аналогии с тем, как лексикографическое сравнение оказывается неподходящим в некоторых ситуациях, преобразования символов «один-в-один» тоже годятся не всегда (например, в немецком языке символ (? нижнего регистра соответствует последовательности «SS» в верхнем регистре). К сожалению, средства преобразования регистра в стандартных библиотеках С и C++ работают только с отдельными символами. Если это ограничение вас не устраивает, решение со стандартными библиотеками отпадает.

Если вы знакомы с локальными контекстами C++, возможно, вам уже пришел в голову другой способ сравнения строк. У фасета

collate

strcmp

L

x

y

L(x, y)

use_facet

collate

«Классический» локальный контекст содержит фасет

collate

operator<

string

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

Фасет

ctype

lexicographical_compare

toupper

toupper

tolower

struct lt_str_1:

 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

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

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_1

lt_str_2

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

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

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

vector<char>

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

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

Примечания:

5

См. статью Александреску A. (Andrei Alexandrescu) в майском номере «C++ Report» за 2000 г. [19].

6

Внимание: в шаблоне функции

use_facet

use_facet