Скотт Мейерс - Эффективное использование STL
Альтернативное решение заключается в однократном преобразовании каждого символа с кэшированием результата. Такое решение недостаточно универсально — в частности, при использовании 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 года». И все же у вас больше шансов обойти стороной эту проблему, если ваш локально-зависимый код будет с самого начала правильно работать.
Замечания по поводу платформ STL от Microsoft
В начале книги я ввел термин «платформа STL», означающий комбинацию конкретного компилятора и конкретной реализации STL. Различие между компилятором и библиотекой особенно важно при использовании компилятора Microsoft Visual C++ версий 6 и ниже (то есть компилятора, входившего в комплект поставки Microsoft Visual Studio версий 6 и ниже), поскольку компилятор иногда способен на большее, чем прилагаемая реализация STL. В настоящем приложении описаны важные недостатки старых платформ STL от Microsoft и предложены обходные решения, делающие работу на этих платформах значительно более удобной.
Дальнейший материал предназначен для разработчиков, использующих Microsoft Visual C++ (MSVC) версий 4-6. В Visual C++ .NET перечисленные проблемы отсутствуют.
Шаблоны функций классов в STL
Допустим, у вас есть два вектора объектов Widget, требуется скопировать объекты Widget из одного вектора в конец другого. Задача решается легко — достаточно воспользоваться интервальной функцией insert контейнера vector:
vector<Widget> vw1, vw2;
…
vw1.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(), lw.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> scw;
vw.insert(vw.begin(), scw.begin(), scw.end()); // Присоединить к vw копию
// объектов Widget из scw
Подобная универсальность объясняется тем, что интервальная функция insert контейнера range вообще не является функцией в общепринятом смысле. Это шаблон функции контейнера, специализация которого с произвольным типом итератора порождает конкретную интервальную функцию insert. Для контейнера vector шаблон insert объявлен в Стандарте следующим образом:
template <class T, class Allocator = allocator<T> >
class vector {
public:
…
template<class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
};
Каждый стандартный контейнер должен поддерживать шаблонную версию интервальной функции insert. Аналогичные шаблоны также обязательны для интервальных конструкторов и для интервальной формы assign (см. совет 5).
MSVC версий 4-6
К сожалению, в реализации STL, входящей в комплект поставки версий 4-6, шаблоны функций не объявляются. Библиотека изначально разрабатывалась для MSVC версии 4, а этот компилятор, как и большинство компиляторов того времени, не обладал поддержкой шаблонов функций классов. При переходе от MSCV4 к MSVC6 поддержка этих шаблонов была включена в компилятор, но вследствие судебных дел, косвенно затрагивавших фирму Microsoft, библиотека оставалась практически в неизменном состоянии.
Поскольку реализация STL, поставляемая с MSVC4-6, предназначалась для компилятора без поддержки шаблонов функций классов, авторы библиотеки имитировали эти шаблоны и заменили их конкретными функциями, которым при вызове передавались итераторы контейнера соответствующего типа. Например, шаблон insert был заменен следующей функцией:
void insert(iterator position, // "iterator" - тип итератора
iterator first, iterator last); // для конкретного контейнера
Эта ограниченная форма интервальных функций позволяла выполнить интервальную вставку из vector<Widget> в vector<Widget> или из list<int> в list<int>, но смешанные операции (например, вставка из vector<Widget> в list<Widget> или из set<int> в deque<int>) не поддерживались. Более того, не поддерживалась даже интервальная вставка (а также конструирование или assign) из vector<long> в vector<int>, поскольку итераторы vector<long>::iterator и vector<int>::iterator относятся к разным типам. В результате следующий фрагмент, принимаемый другими компиляторами, не компилируется в MSVC4-6:
istream_iterator<Widget> begin(cin), end; // Создать итераторы begin и end
// для чтения объектов Widget
// из cin (см. совет 6).
vector<Widget> vw(begin, end); // Прочитать объекты Widget
// из cin в vw (см. совет 6)
// не компилируется в MSVC4-6!
list<Widget> lw;
lw.assign(vw.rbegin(), vw.rend()); // Присвоить lw содержимое vw
