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

• Название: Эффективное использование STL
• Автор: Скотт Мейерс
• Издательство: Питер
• Жанр: Программирование
• Год: 2002
• ISBN: ISBN 5-94723-382-7

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.

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

---

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

В приведенном выражении алгоритм lexicographical_compare сравнивает отдельные символы оператором <, однако существует другая версия lexicographical_ compare, позволяющая задать пользовательский критерий сравнения символов. Она вызывается с пятью аргументами вместо четырех; в последнем аргументе передается объект функции, двоичный предикат, определяющий, какой из двух символов предшествует другому. Таким образом, для сравнения строк без учета регистра на базе lexicographical_compare достаточно объединить этот алгоритм с объектом функции, игнорирующим различия в регистре символов.

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

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

}

};

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

int main() {

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

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

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

printf("sl<s2:2s\n",

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

?"true":"false"):

}

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

sl=GEWURZTRAMINER,s2=gewQrztraminer

sl<s2:true

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

setlocale(LC_ALL,"de");

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

sl=GEW0RZTRAMINER,s2=gewurztraminer

sl<s2:false

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

Локальный контекст

Символьный тип char в действительности представляется самым обычным целым числом. Это число можно интерпретировать как символ, но такая интерпретация ни в коем случае не является универсальной. Что должно соответствовать конкретному числу — буква, знак препинания, непечатаемый управляющий символ?

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

По умолчанию функции обработки символов работают с кодировкой, подходящей для простого английского текста. Символ '\374' не изменяется функцией toupper, поскольку он не считается буквой; в некоторых системах при выводе он имеет вид ü, но для библиотечной функции С, работающей с английским текстом, это несущественно. В кодировке ASCII нет символа ü. Команда

setlocale(LC_ALL,"de"):

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

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

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

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

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

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

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

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

std::locale L("de");

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

Локальные контексты С++ делятся на фасеты (facets), связанные с разными аспектами интернационализации. Для извлечения заданного фасета из объекта локального контекста используется функция std:: use_facet[6]. Фасет ctype отвечает за классификацию символов, в том числе и преобразования типа. Если c1 и с2 относятся к типу char, следующий фрагмент сравнивает их без учета регистра по правилам локального контекста L.

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

bool result = ct-toupper(cl)<ct.toupper(c2);

Предусмотрена особая сокращенная запись: std:: toupper (с, L), эквивалентная

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

Использование use_facet стоит свести к минимуму, поскольку оно связано с заметными затратами.

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

Фасет collate

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

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

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