Скотт Мейерс - Эффективное использование STL
[12] Herb Sutter, «When Is a Container Not A Container?», С++ Report, май 1999 г. Статья доступна по адресу http://www.gotw.ca/publications/mUl09.htm. Материал пересмотрен и дополнен в совете 6 книги «More Exceptional С++» [9].
[13] Herb Sutter, «Standard Library News: sets and maps», С++ Report, октябрь
1999г. Статья доступна по адресу http://www.gotw.ca/publications/millll.htm. Материал пересмотрен и дополнен в совете 8 книги «More Exceptional С++» [9].
[ 14] Nicolai М. Josuttis, «Predicates vs. Function Objects», С++ Report, июнь 2000 г.
[15] Matt Austern, «Why You Shouldn't Use set - and What to Use Instead*, С++ Report, апрель 2000 г.
[16] P.J. Plauger, «HashTables», C/C++ Users Journal, ноябрь 1999 г. В статье описан подход реализации Dinkumware к хэшированным контейнерам (см. совет 25) и его отличия от альтернативных решений.
[17] Jack Reeves, «STL Gotcha's», С++ Report, январь 1997 г. Статья доступна по адресу http://www.bleading-edge.com/Publications/C++Report/v9701/abstract.htm.
[18] Jack Reeves, «Using Standard string in the Real World, Part 2», С++ Report, январь 1999 г. Статья доступна по адресу http://www.bleading-edge.com/Publications/ C++Report/v9901/abstract.htm.
[19] Andrei Alexandrescu, «Traits: The if-then-else of Types», С++ Report, апрель
2000г. Статья доступна по адресу http://www.creport.com/html/from_pages/ view_recent_articles_c.cfm?ArticleID=402.
[20] Herb Sutter, «Optimizations That Aren't (In a Multithreaded World)», C/C++ Users Journal, июнь 1999 г. Статья доступна по адресу http://www.gotw.ca/ publications/optimizations.htm. Материал пересмотрен и дополнен в совете 16 книги «More Exceptional С++» [9]. ,
[21] Web-сайт SGI STL, http://www.sgi.com/tech/stl. В совете 50 кратко описано содержимое этого сайта. Страница, посвященная потоковой безопасности контейнеров STL (взятая за основу при написании совета 12), накодится по адресу http://www.sgi.com/tech/stl/thread_safety.html.
[22] Web-сайт Boost, http://www.boost.org/. Содержимое сайта кратко описано в совете 50.
[23] Nicolai М. Josuttis, «User-Defined Allocator», http://www.josuttis.com/cppcode/ allocator.html. Страница является частью сайта, посвященного превосходной книге Джосаттиса о стандартной библиотеке С++ [3].
[24] Matt Austern, «The Standard Librarim: What Are Allocators Good For?», форум экспертов C/C++ Users Journal (сетевое дополнение к журналу), ноябрь 2000 г., http://www.cuj.com/experts/1812/austern.htm. Найти толковую информацию о распределителях памяти нелегко. Статья дополняет материал советов 10 и 11. Кроме того, в ней приведен пример реализации распределителя памяти.
[25] Klaus Kreft, Angelika Langer, «A Sophisticated Implementation of User-Defined Inserters and Extractors», С++ Report, февраль 2000 г.
[26] Leor^Zolman, «An STL Error Message Decryptor for Visual С++», C/C++ Users Journal, июль 2001 г. Статья и описанная в ней программа доступны по адресу http://www.bdsoft.com/tools/stlfilt.html.
[27] Bjarne Stroustrup, «Sixteens Ways to Stack a Cat», С++ Report, октябрь 1990 г. Статья доступна по адресу http://www.csdn.net/dev/C&C++/Document/Stackcat.pdf.
•Herb Sutter, «Guru of the Week #74: Uses and Abuses of vector», сентябрь 2000 г. Задача с прилагаемым решением помогает разобраться в некоторых аспектак использования vector, в том числе в различиях между размером и емкостью (см. совет 14). Кроме того, в статье обсуждаются преимущества алгоритмов перед циклическими вызовами (см. совет 43).
•Matt Austern, «The Standard Librarian: Bitsets and Bit Vectors?», форум экспертов C/C++ Users Journal (сетевое дополнение к журналу), май 2001 г., http://www.cuj.com/expeits/1905/austern.htm. В статье описаны контейнеры bitset, которые сравниваются с vector<bool>, — эти темы кратко рассматриваются в совете 18.
Ошибки и опечатки
•Список ошибок и опечаток в книге «Effective С++»: http://www.aristeia.com/ BookErrata/ec++2e-errata.html.
[28] Список ошибок и опечаток в книге «More Effective С++»: http://www.aristeia. com/BookErrata/mec-H-errata.html.
•Список ошибок и опечаток на компакт-диске «Effective С++»: http://www. aristeia.com/BookErrata/cdle-errata.html.
[29] Обновления «More Effective С++»* относящиеся к auto_ptr: http://www.awl. com/cseng/titles/0-201-63371-X/auto_ptr.html.
Локальные контексты
В совете 35 приведена реализация сравнения строк без учета регистра символов с применением алгоритмов mismatch и lexicographical_compare, но в нем также указано, что полноценное решение должно учитывать локальный контекст. Книга посвящена STL, а не вопросам интернационализации, поэтому локальным контекстам в ней не нашлось места. Тем не менее, Мэтт Остерн, автор книги «Generic Programming and the STL» [4], посвятил этой теме статью в майском номере журнала «С++ Report» [И]. Текст этой статьи приведен в настоящем приложении. Я благодарен Мэтту и фирме lOlcommunications за то, что они разрешили мне это сделать.
Сравнение строк без учета регистра символов
Мэтт Остерн
Если вам когда-либо доводилось писать программы, в которых используются строки (а кому, спрашивается, не доводилось?), скорее всего, вы встречались с типичной ситуацией — две строки, различающиеся только регистром символов, должны были интерпретироваться как равные. В этих случаях требовалось, чтобы операции сравнения — проверка равенства, больше-меньше, выделение подстрок, сортировка — игнорировали регистр символов. Программисты очень часто спрашивают, как организовать подобные операции средствами стандартной библиотеки С++. На этот вопрос существует огромное количество ответов, многие из которых неверны.
Прежде всего необходимо избавиться от мысли о написании класса, сравнивающего строки без учета регистра. Да, с технической точки зрения это более или менее возможно. Тип std:: string стандартной библиотеки в действительности является синонимом для типа std::basic_string<char,std::char_trais<char>,sd:: allocator<char> >. Операции сравнения определяются вторым параметром; передавая второй параметр с переопределенными операциями «равно» и «меньше», можно специализировать basic_string таким образом, что операции < и = будут игнорировать регистр символов. Такое решение возможно, но игра не стоит свеч.
Вы не сможете выполнять операции ввода-вывода или это потребует больших дополнительных хлопот. Классы ввода-вывода стандартной библиотеки (такие как std:: basic_istream и std::basic_ostream) специализируются по двум начальным параметрам std::basic_string (а std::ostream всего лишь является синонимом для std::basic_ostreanKchar,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. Кроме того, такое решение перестает работать, если по соображениям эффективности перейти от контейнера объектов basicstring к таблице строк.
Более правильное решение, которое лучше соответствует архитектуре стандартной библиотеки, заключается в том, чтобы игнорировать регистр символов только в тех случаях, когда это действительно необходимо. Не стоит возиться с такими функциями контейнера string, как string::find_first или string::rfind; они лишь дублируют функциональные возможности, уже поддерживаемые внешними обобщенными алгоритмами. С другой стороны, алгоритмы обладают достаточной гибкостью, что позволяет реализовать в них поддержку сравнений строк без учета регистра. Например, чтобы отсортировать коллекцию строк без учета регистра, достаточно передать алгоритму працильный объект функции сравнения:
std::sort(С.begin(), С.end().compare_wi thout_case);
Написанию таких объектов и посвящена эта статья.
Первая попытка
Существует несколько способов упорядочения слов по алфавиту. Зайдите в книжный магазин и посмотрите, как расставлены книги на полках. Предшествует ли имя
1 См. статью Александреску A. (Andrei Alexandrescu) в майском номере «С++ Report» за 2000 г. [19].
Mary McCarthy имени Bernard Malamud или следует после него? (В действительности это лишь вопрос привычки, я встречал оба варианта.) Впрочем, простейший способ сравнения строк хорошо знаком нам по школе: речь идет о лексикографическом, или «словарном», сравнении, основанном на последовательном сравнений отдельных символов двух строк.
Лексикографический критерий сравнения может оказаться неподходящим для некоторых специфических ситуаций. Более того, единого критерия вообще не существует — например, имена людей и географические названия иногда сортируются по разным критериям. С другой стороны, в большинстве случаев лексикографический критерий подходит, поэтому он был заложен в основу механизма строковых сравнений в С++. Строка представляет собой последовательность символов. Если объекты х и у относятся к типу std:: string, то выражение х<у эквивалентно выражению
std:: lexicographical_compare(x.begin(),x.end(), y.begin(), y.end())
