Онлайн библиотека PLAM.RU

Загрузка...



  • Сравнение строк без учета регистра символов
  • Первая попытка
  • Локальный контекст
  • Локальные контексты в C++
  • Фасет collate
  • Сравнение строк без учета регистра
  • Локальные контексты

    В совете 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
    , как и все классы характеристик[5], прост, компактен и не содержит информации состояния. Как будет показано ниже, правильная реализация сравнений без учета регистра не отвечает ни одному из этих критериев.

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

    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
    , поскольку он не считается буквой; в некоторых системах при выводе он имеет вид u, но для библиотечной функции C, работающей с английским текстом, это несущественно. В кодировке ASCII нет символа u. Команда

    setlocale(LC_ALL, "de");

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

    toupper
    преобразует u в U.

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

    toupper
    , вызываемая с одним аргументом, зависит еще и от глобальной переменной — хуже того, от скрытой глобальной переменной. Это приводит к стандартной проблеме: на работу функции, использующей
    toupper
    , теоретически может повлиять любая другая функция во всей программе.

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

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

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

    Локальные контексты в C++

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

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

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

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

    std::locale L("de");

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

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

    facets
    ), связанные с разными аспектами интернационализации. Для извлечения заданного фасета из объекта локального контекста используется функция
    std::use_facet
    [6]. Фасет
    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++ работают только с отдельными символами. Если это ограничение вас не устраивает, решение со стандартными библиотеками отпадает.

    Фасет collate

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

    collate
    , предназначенного для инкапсуляции технических аспектов сортировки, имеется функция, по интерфейсу весьма близкая к библиотечной функции C
    strcmp
    . Существует даже специальное средство, упрощающее сравнение двух строк: для объекта локального контекста
    L
    строки 
    x
    и 
    y
    могут сравниваться простой записью
    L(x, y)
    , что позволяет обойтись без хлопот, связанных с вызовом
    use_facet
    и функции
    collate
    .

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

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

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

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

    Фасет

    ctype
    позволяет относительно легко организовать сравнение строк без учета регистра на основе сравнения отдельных символов. Приведенная ниже версия не оптимальна, но по крайней мере она верна. В ней используется практически тот же принцип, что и прежде: строки сравниваются алгоритмом
    lexicographical_compare
    , а отдельные символы сравниваются после приведения к верхнему регистру. Впрочем, на этот раз вместо глобальной переменной используется объект локального контекста. Кстати говоря, сравнение после приведения обоих символов к верхнему регистру не всегда дает тот же результат, что и после приведения к нижнему регистру. Например, во французском языке в символах верхнего регистра принято опускать диакритические знаки, вследствие чего вызов
    toupper
    во французском локальном контексте может приводить к потере информации: символы 'ё' и 'е' преобразуются в один символ верхнего регистра 'Е'. В этом случае при сравнении на базе функции
    toupper
    символы 'e' и 'е' будут считаться одинаковыми, а при сравнении на базе
    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
    вызывается в цикле, а Стандарт C++ требует, чтобы эта функция была виртуальной. Некоторые оптимизаторы выводят вызов виртуальной функции из цикла, но чаще этого не происходит. Циклические вызовы виртуальных функций нежелательны.

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

    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+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
    сортировка списка из 23 791 слова заняла 0,86 секунды, а при использовании
    lt_str_2
    понадобилось только 0,4 секунды.

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

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

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

    vector<char>
    , строковые таблицы или обычные строки C.

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

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


    Примечания:



    5

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



    6

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

    use_facet
    параметр шаблона присутствует только в типе возвращаемого значения, но не в аргументах. При обращении к нему используется языковое средство, называ-емоеявяьш заданием аргументов шаблона, которое не поддерживается некоторыми компиляторами C++. Если ваш компилятор принадлежит к их числу, возможно, авторы реализации библиотеки предусмотрели обходное решение, которое позволяет использовать
    use_facet
    другим способом.









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

    Все материалы представлены для ознакомления и принадлежат их авторам.