|
||||||||||||||||||||||||||||||||||||||||||
|
|
Программирование в STL STL традиционно характеризуется как совокупность контейнеров, итераторов, алгоритмов и объектов функций, однако программирование в STL заключает в себе нечто большее. Этот термин означает, что программист способен правильно выбирать между циклами, алгоритмами или функциями контейнеров; знает, в каких случаях equal_rangeпредпочтительнее lower_bound, когда lower_boundпредпочтительнее findи когда findпревосходит equal_range. Термин означает, что программист умеет повышать быстродействие алгоритма посредством замены функций эквивалентными функторами и избегает написания непереносимого или плохо читаемого кода. Более того, к этому понятию даже относится умение читать сообщения об ошибках компилятора, состоящие из нескольких тысяч символов, и хорошее знание Интернет-ресурсов, посвященных STL (документация, расширения и даже полные реализации). Да, для программирования в STL необходимо много знать, и большая часть этой информации приведена в данной главе. Совет 43. Используйте алгоритмы вместо циклов Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_elementнаходит минимальное значение в интервале, алгоритм accumulateвычисляет сводную величину, характеризующую интервал в целом (см. совет 37), а алгоритм partitionделит элементы интервала на удовлетворяющие и не удовлетворяющие заданному критерию (см. совет 31). Чтобы алгоритм мог выполнить свою задачу, он должен проанализировать каждый объект в переданном интервале (или интервалах), для чего объекты в цикле перебираются от начала интервала к концу. Некоторые алгоритмы (такие как findи find_if) могут вернуть управление до завершения полного перебора, но и в этих алгоритмах задействован внутренний цикл. Ведь даже алгоритмы findи find_ifдолжны проанализировать все элементы интервала, прежде чем принять решение об отсутствии искомого элемента. Итак, внутренняя реализация алгоритмов построена на использовании циклов. Более того, благодаря разнообразию алгоритмов STL многие задачи, естественно кодируемые в виде циклов, могут решаться при помощи алгоритмов. Рассмотрим класс Widgetс функцией redraw(): class Widget { public: … void redraw() const; … }; Если потребуется вызвать функцию redrawдля всех объектов в контейнере list, это можно сделать в следующем цикле: list<Widget> lw; … for (list<Widget>::iterator = lw.begin(); i != lw.end(); ++i) { i->redraw(); } С другой стороны, с таким же успехом можно воспользоваться алгоритмом for_each: for_each(lw.begin(), lw.end(); // Функция mem_fun_ref mem_fun_ref(&Widget::redraw)); // описана в совете 41 Многие программисты C++ считают, что циклы естественнее алгоритмов, а прочитать цикл проще, чем разбираться в mem_fun_refи получении адреса Widget::redraw. Но в заголовке этого совета рекомендуется отдавать предпочтение алгоритмам. В сущности, заголовок означает, что вызов алгоритма предпочтительнее любого явно запрограммированного цикла. Почему? По трем причинам. • Эффективность: алгоритмы обычно работают эффективнее, чем циклы, организованные программистами. • Правильность: при написании циклов чаще встречаются ошибки, чем при вызове алгоритмов. • Удобство сопровождения: алгоритмы часто порождают более наглядный и прямолинейный код, чем эквивалентные циклы. Вся оставшаяся часть совета будет посвящена подробному анализу этих причин. С точки зрения эффективности превосходство алгоритмов объясняется тремя факторами: двумя основными и одним второстепенным. Второстепенный фактор связан с исключением лишних вычислений. Еще раз взгляните на только что приведенный цикл: for (list<Widget>::iterator=lw.begin(); i != lw.end(); ++i) { i->redraw(); } Я выделил условие завершения цикла, чтобы подчеркнуть, что при каждой итерации цикла будет выполнено сравнение с lw.end(). Следовательно, при каждой итерации будет вызываться функция list::end. Однако вызывать эту функцию больше одного раза не нужно, поскольку цикл не модифицирует список. Но если взглянуть на вызов алгоритма, можно заметить, что endвызывается ровно один раз: for_each(lw.begin(), lw.end(), // lw.end() вычисляется mem_fun_ref(&Widget::redraw)); // только один раз Объективности ради замечу: авторы реализаций STL хорошо понимают, что функции beginи end(и другие функции — например, size) используются очень часто, и стараются оптимизировать их с расчетом на максимальную эффективность. Они почти всегда объявляют такие функции подставляемыми ( inline) и стараются кодировать их так, чтобы большинство компиляторов могло избежать повторяющихся вычислений, выводя результаты из цикла. Впрочем, опыт показывает, что это не всегда им удается, и в таких случаях исключения повторяющихся вычислений вполне достаточно, чтобы алгоритмы имели преимущество по быстродействию перед циклами, закодированными вручную. Но как было сказано выше, вывод лишних вычислений из цикла является второстепенным фактором, существуют два более важных. Первый важный фактор заключается в том, что разработчики библиотек могут воспользоваться знанием внутренней реализации контейнера и оптимизировать перебор так, как не сможет ни один пользователь библиотеки. Например, объекты во внутреннем представлении контейнера deque обычно хранятся в одном или нескольких массивах фиксированного размера. Перебор в этих массивах с использованием указателей производится быстрее, чем перебор на базе итераторов, однако он может использоваться только разработчиками библиотеки, поскольку они знают размер внутренних массивов и способ перехода от одного массива к другому. Некоторые версии STL содержат реализации алгоритмов, использующие внутренние структуры данных deque; эксперименты показали, что они работают примерно на 20% быстрее «обычных» реализаций. Здесь важно не то, что реализации STL оптимизируются для deque(или другого конкретного типа контейнера), а то, что разработчики знают об устройстве контейнеров больше, чем простые пользователи, и могут применить свои знания при реализации алгоритмов. Отказываясь от алгоритмов в пользу циклов, вы не сможете пользоваться преимуществами оптимизации, основанной на знании внутреннего устройства структур данных. Второй принципиальный аргумент заключается в том, что практически все алгоритмы STL (кроме самых элементарных) основаны на теоретических разработках, более сложных — а иногда гораздо более сложных, — нежели те, которые может предложить средний программист C++. Превзойти sortи его сородичей (см. совет 31) по эффективности практически невозможно; столь же эффективны алгоритмы поиска в сортированных интервалах (см. советы 34 и 45). Даже повседневные задачи вроде удаления объектов из блоковых контейнеров более эффективно решаются при помощи идиомы erase-remove, чем при помощи самостоятельно запрограммированных циклов (см. совет 9). Если соображений эффективности недостаточно, существует и другой принципиальный фактор — правильность работы программы. В частности, при самостоятельном программировании циклов приходится следить за тем, чтобы итераторы (1) были действительными и (2) указывали на те элементы, на которые они должны указывать. Предположим, у нас имеется массив (возможно, из-за использования унаследованного интерфейса с языком C — см. совет 16), и вы хотите взять каждый элемент массива, прибавить к нему 41 и вставить в начало контейнера deque. При самостоятельном программировании цикла примерная реализация выглядит приблизительно так (следующий фрагмент представляет собой видоизмененный пример из совета 16): // Функция получает указатель на массив. // содержащий не более arraySize чисел типа double, // и записывает в него данные. // Возвращается количество записанных чисел. size_t fillArray(double *pArray, size_t arraySize); double data[maxNumDoubles]; // Определение локального массива deque<double> d; // Создать контейнер deque … // и заполнить его данными size_t numDoubles = fillArray(data.maxNumDoubles); // Получение данных от функции for (size_t i=0; i < numDoubles; ++i) { // Для каждого индекса i в data d.insert(d.begin(), data[i]+41); // вставить в начало d значение } // data[i]+41. //Программа содержит ошибку! Вообще говоря, этот пример работает — если вас устраивает, что вновь вставленные элементы следуют в порядке, обратном порядку соответствующих элементов data. Вставка производится в позиции d.begin(), поэтому последний вставленный элемент попадает в начало контейнера! Если изменение порядка не было предусмотрено (признайтесь, ведь не было!), проблему можно решить следующим образом: deque<double>::iterator insertLocaton = d.begin(); // Сохранить итератор // для начальной // позиции d for (size_t = 0; i < numDoubles; ++i) { // Вставить значение data[i]+41 d.insert(insertLocation++, data[i]+41); // в позиции insertLocation } // и увеличить insertLocation. // Программа также содержит ошибку! На первый взгляд кажется, что этот фрагмент решает сразу две проблемы — программа не только наращивает итератор, задающий позицию вставки, но и избавляется от необходимости заново вычислять beginпри каждой итерации; тем самым решается второстепенная проблема повторяющихся вычислений, о которой говорилось выше. К сожалению, вместо этих двух проблем возникает третья — программа вообще перестает работать. При каждом вызове deque::insertвсе итераторы deque, включая insertLocation, становятся недействительными, поэтому второй и все последующие вызовы insertприводят к непредсказуемым последствиям. После обнаружения этой проблемы (возможно, при помощи отладочного режима STL — см. совет 50) приходит в голову следующее решение: deque<double>::iterator insertLocation = d.begin(); // См. ранее for (size_t i = 0; i < numDoubles; ++i) { // Программа обновляет insertLocation = // итератор insertLocation d.insert(insertLocaton, data[i]+41); // при каждом вызове insert ++insertLocation; // и увеличивает его. } Программа делает именно то, что требовалось, но подумайте, как много времени понадобилось, чтобы прийти к верному решению! А теперь сравните со следующим вызовом transform: transform(data, data+numDoubles, // Копирование всех элементов inserter(d, d.begin()), // из data в начало d bind2nd(plus<int>(), 41)); // с прибавлением 41 Возможно, вам потребуется пара минут на анализ конструкции bnd2nd(plus<int>(), 41), но после этого все хлопоты с итераторами сводятся к простому заданию начала и конца исходного интервала и вызову inserterпри определении начала приемного интервала (см. совет 30). На практике итераторы исходного и приемного интервала обычно вычисляются относительно просто — во всяком случае, это значительно проще, чем диагностика случайного появления недействительных итераторов в теле цикла. Данный пример убедительно показывает, что программирование циклов часто бывает связано с трудностями. Программисту приходится постоянно следить за тем, чтобы итераторы в процессе цикла не стали недействительными или с ними не были выполнены недопустимые операции. Другой пример скрытого перехода итераторов в недействительное состояние приведен при описании циклических вызовов erase в совете 9. Применение недействительных итераторов приводит к непредсказуемым последствиям, которые редко проявляются на стадии разработки и тестирования. Так зачем идти на риск, если без этого можно обойтись? Поручите работу алгоритмам, пусть они беспокоятся о технических подробностях операций с итераторами. Итак, я объяснил, почему алгоритмы обычно работают эффективнее «ручных» циклов и почему при работе с циклами возникают многочисленные трудности, отсутствующие при использовании алгоритмов. Если мне повезло, вы поверили в силу алгоритмов, но везение — вещь ненадежная, а я хочу окончательно разобраться в этом вопросе перед тем, как следовать дальше. Мы переходим к следующему фактору: наглядности кода. В долгосрочной перспективе принцип наглядности очень важен, поскольку наглядную программу проще понять, она проще усовершенствуется, сопровождается и адаптируется в соответствии с новыми требованиями. Циклические конструкции выглядят привычнее, но алгоритмы обладают значительными преимуществами. Одним из ключевых преимуществ является семантическая сила стандартных имен. В STL существует 70 имен алгоритмов, с учетом перегрузки (overloading) получается более 100 различных шаблонов функций. Каждый алгоритм выполняет четко определенную задачу, и вполне логично ожидать, что профессиональный программист C++ знает эти задачи (или легко найдет нужную информацию). Таким образом, при виде вызова transformпрограммист понимает, что некоторая функция применяется ко всем объектам в интервале, а результат куда-то записывается. При виде вызова replace_ifон знает, что программа модифицирует все объекты интервала, удовлетворяющие некоторому предикату. Вызов partitionнаводит на мысль о том, что объекты интервала перемещаются с группировкой всех объектов, удовлетворяющих предикату (см. совет 31). Имена алгоритмов STL несут большую семантическую нагрузку и более четко выражают смысл происходящего, чем любые циклы. При виде цикла for, whileи doпрограммист знает только одно — программа многократно выполняет некоторые действия. Чтобы получить хотя бы примерное представление о происходящем, необходимо изучить тело цикла. С алгоритмами дело обстоит иначе, сам вызов алгоритма характеризует суть происходящего. Конечно, для полноценного понимания необходимо проанализировать аргументы, передаваемые алгоритму, но обычно это требует меньшей работы, чем анализ обобщенной циклической конструкции. Проще говоря, имена алгоритмов информативны, а ключевые слова for, whileили do— нет. Впрочем, это относится практически ко всем компонентам стандартных библиотек C и C++. Никто не запрещает вам написать собственную реализацию strlen, memsetили bsearch, но вы этого не делаете. Почему? Во-первых, кто-то уже сделал это за вас, и нет смысла повторять уже выполненную работу; во-вторых, имена этих функций стандартны, и все знают, что они делают; в-третьих, можно предположить, что автор библиотеки знает приемы оптимизации, недоступные для вас, и отказываться от возможного повышения эффективности было бы неразумно. А раз вы не пишете собственные версии strlenи т. д., то было бы нелогично программировать циклы, дублирующие функциональность готовых алгоритмов STL. На этом я бы хотел завершить данный совет, поскольку финал выглядит довольно убедительно. К сожалению, тема не поддается столь однозначной трактовке. Действительно, имена алгоритмов информативнее простых циклов, но четкая формулировка действий, выполняемых при каждой итерации, иногда бывает нагляднее вызова алгоритма. Допустим, нам потребовалось найти первый элемент вектора, значение которого лежит в заданном диапазоне <x, y>. В цикле это делается так: vector<int> v; int х, у; vector<int>::iterator i=v.begin(); // Перебирать элементы, начиная for(; i!=v.end(); ++i){ // с v.begin(), до нахождения нужного if(*i > x && *i < y)) break; // элемента или достижения v.end() } … // После завершения цикла // i указывает на искомый элемент // или совпадает с v.end() То же самое можно сделать и при помощи find_if, но для этого придется воспользоваться нестандартным адаптером объекта функции — например, compose2из реализации SGI (см. совет 50): vector<int>::iterator i = find_if(v.begin(), v.end(), // Найти первое значение val, compose2(logical_and<bool>(), // для которого одновременно bind2nd(greater<int>(), x), // истинны условия bind2nd(less<int>(), y))); // val>x, и val<y Но даже если бы нестандартные компоненты не использовались, многие программисты полагают, что вызов алгоритма значительно уступает циклу по наглядности, и я склонен с ними согласиться (см. совет 47). Вызов find_ifможно было бы упростить за счет выделения логики проверки в отдельный класс функтора. template<typename T> class BetweenValues: public unary_function<T, bool> { // См. совет 40 public:
lowVal(lowValue), highVal(highValue) {}
return val > lowVal && val < highVal; } private: T lowVal; T highVal; }; … vector<int> iterator i = find_if(v.begin(), v.end(), BetweenValues<int>(x, y)); Однако у такого решения имеются свои недостатки. Во-первых, создание шаблона BetweenValuesтребует значительно большей работы, чем простое написание тела цикла. Достаточно посчитать строки в программе: тело цикла — одна строка, BetweenValues— четырнадцать строк. Соотношение явно не в пользу алгоритма. Во-вторых, описание критерия поиска физически отделяется от вызова. Чтобы понять смысл вызова find_if, необходимо найти определение BetweenValues, но оно должно располагаться вне функции, содержащей вызов find_if. Попытка объявить BetweenValuesвнутри функции, содержащей вызов find_if: { // Начало функции … template<typename T> class BetweenValues: public unary_function<T, bool> {…}; vector<int>::iterator i = find_if(v.begin(), v.end(), BetweenValues<int>(x, у)); } // Конец функции не компилируется, поскольку шаблоны не могут объявляться внутри функций. Если попробовать обойти это ограничение посредством реализации BetweenValuesв виде класса: { // Начало функции … class BetweenValues: public unary_function<int, bool> {…}; vector<int>::iterator i = find_if(v.begin(), v.end(), BetweenValues(x, y)); } // Конец функции все равно ничего не получается, поскольку классы, определяемые внутри функций, являются локальными, а локальные классы не могут передаваться в качестве аргументов шаблонов (как функтор, передаваемый find_if). Печально, но классы функторов и шаблоны классов функторов не разрешается определять внутри функций, как бы удобно это ни было. В контексте борьбы между вызовами алгоритмов и циклами это означает, что выбор определяется исключительно содержимым цикла. Если алгоритм уже умеет делать то, что требуется, или нечто очень близкое, вызов алгоритма более нагляден. Если задача элементарно решается в цикле, а при использовании алгоритма требует сложных нагромождений адаптеров или определения отдельного класса функтора, вероятно, лучше ограничиться циклом. Наконец, если в цикле приходится выполнять очень длинные и сложные операции, выбор снова склоняется в пользу алгоритмов, потому что длинные и сложные операции лучше оформлять в отдельных функциях. После того как тело цикла будет перенесено в отдельную функцию, почти всегда удается передать эту функцию алгоритму (особенно часто — алгоритму for_each) так, чтобы полученный код был более наглядным и прямолинейным. Если вы согласны с тем, что вызовы алгоритмов обычно предпочтительнее циклов, а также с тем, что интервальные функции обычно предпочтительнее циклического вызова одноэлементных функций (см, совет 5), можно сделать интересный вывод: хорошо спроектированная программа C++, использующая STL, содержит гораздо меньше циклических конструкций, чем аналогичная программа, не использующая STL, и это хорошо. Замена низкоуровневых конструкций for, whileи doвысокоуровневыми терминами insert, findи foreachповышает уровень абстракции и упрощает программирование, документирование, усовершенствование и сопровождение программы. Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов Некоторые контейнеры содержат функции, имена которых совпадают с именами алгоритмов STL. Так, в ассоциативных контейнерах существуют функции count, find, lower_bound, upper_boundи equal_range, а в контейнере listпредусмотрены функции remove, remove_if, unique, sort, mergeи reverse. Как правило, эти функции используются вместо одноименных алгоритмов, что объясняется двумя причинами. Во-первых, функции классов быстрее работают. Во-вторых, они лучше интегрированы с контейнерами (особенно ассоциативными), чем алгоритмы. Дело в том, что алгоритмы и одноименные функции классов обычно работают не совсем одинаково. Начнем с ассоциативных контейнеров. Допустим, имеется множество set<int>, содержащее миллион значений, и вы хотите найти позицию первого вхождения числа 727, если оно присутствует. Ниже приведены два очевидных способа поиска: set<int> s; // Создать множество … // и занести в него // миллион чисел set<int>::iterator i = s.find(727); // Функция find контейнера if (i != s.end()) … set<int>::iterator i = find(s.begin(), s.end(), 727); // Алгоритм find if (i != s.end()) … Функция класса findработает с логарифмической сложностью, поэтому независимо от того, присутствует ли число 727 в множестве или нет, set::findв процессе поиска выполнит не более 40 сравнений, а обычно потребуется не более 20. С другой стороны, алгоритм findработает с линейной сложностью, поэтому при отсутствии числа 727 будет выполнено 1 000 000 сравнений. Впрочем, даже если число 727 присутствует, алгоритм findв процессе поиска выполняет в среднем 500 000 сравнений. Результат явно не в пользу алгоритма find. Кстати, я не совсем точно указал количество сравнений для функции find, поскольку оно зависит от реализации, используемой ассоциативными контейнерами. В большинстве реализаций используются красно-черные деревья — особая разновидность сбалансированных деревьев с разбалансировкой по степеням 2. В таких реализациях максимальное количество сравнений, необходимых для поиска среди миллиона значений, равно 38, но в подавляющем большинстве случаев требуется не более 22 сравнений. Реализация, основанная на идеально сбалансированных деревьях, никогда не требует более 21 сравнения, но на практике по общему быстродействию идеально сбалансированные деревья уступают «красно-черным». По этой причине в большинстве реализаций STL используются «красно-черные» деревья. Различия между функцией класса и алгоритмом find не ограничиваются быстродействием. Как объясняется в совете 19, алгоритмы STL проверяют «одинаковость» двух объектов по критерию равенства, а ассоциативные контейнеры используют критерий эквивалентности. Таким образом, алгоритм findищет 727 по критерию равенства, а функция find— по критерию эквивалентности. Различия в критериях иногда приводят к изменению результата поиска. Например, в совете 19 было показано, как применение алгоритма findдля поиска информации в ассоциативном контейнере завершается неудачей, тогда как аналогичный поиск функцией findпривел бы к успеху! При работе с ассоциативными контейнерами функциональные формы find, countи т. д. предпочтительнее алгоритмических, поскольку их поведение лучше согласуется с другими функциями этих контейнеров. Вследствие различий между равенством и эквивалентностью алгоритмы не столь последовательны. Особенно ярко это различие проявляется при работе с контейнерами mapи multimap, потому что эти контейнеры содержат объекты pair, но их функции учитывают только значение ключа каждой пары. По этой причине функция countсчитает только пары с совпадающими ключами (естественно, «совпадение» определяется по критерию эквивалентности); значение, ассоциированное с ключом, игнорируется. Функции find, lower_boundи т. д. поступают аналогично. Чтобы алгоритмы также ограничивались анализом ключа в каждой паре, вам придется выполнять акробатические трюки, описанные в совете 23 (что позволит заменить проверку равенства проверкой эквивалентности). С другой стороны, если вы стремитесь к максимальной эффективности, то фокусы совета 23 в сочетании с логарифмической сложностью поиска алгоритмов из совета 34 могут показаться не такой уж высокой ценой за повышение быстродействия. А если вы очень сильно стремитесь к максимальной эффективности, подумайте об использовании нестандартных хэшированных контейнеров (см. совет 25), хотя в этом случае вы также столкнетесь с различиями между равенством и эквивалентностью. Таким образом, для стандартных ассоциативных контейнеров применение функций вместо одноименных алгоритмов обладает сразу несколькими преимуществами. Во-первых, вы получаете логарифмическую сложность вместо линейной. Во-вторых, «одинаковость» двух величин проверяется по критерию эквивалентности, более естественному для ассоциативных контейнеров. В-третьих, при работе с контейнерами mapи multimapавтоматически учитываются только значения ключей вместо полных пар (ключ, значение). Эти три фактора достаточно убедительно говорят в пользу функций классов. Перейдем к функциям контейнера list, имена которых совпадают с именами алгоритмов STL. В этом случае эффективность является практически единственным фактором. Алгоритмы, у которых в контейнере listсуществуют специализированные версии ( remove, remove_if, unique, sort, mergeи reverse), копируют объекты, a list-версии ничего не копируют; они просто манипулируют указателями, соединяющими узлы списка. По алгоритмической сложности функции классов и алгоритмы одинаковы, но если предположить, что операции с указателями обходятся значительно дешевле копирования объектов, list-версии обладают лучшим быстродействием. Следует помнить, что list-версии часто ведут себя иначе, чем их аналоги-алгоритмы. Как объясняется в совете 32, для фактического удаления элементов из контейнера вызовы алгоритмов remove, remove_ifи uniqueдолжны сопровождаться вызовами erase, однако одноименные функции контейнера listчестно уничтожают элементы, и последующие вызовы eraseне нужны. Принципиальное различие между алгоритмом sortи функцией sortконтейнера listзаключается в том, что алгоритм неприменим к контейнерам list, поскольку ему не могут передаваться двусторонние итераторы list. Алгоритм mergeтакже отличается от функции mergeконтейнера list— алгоритму не разрешено модифицировать исходные интервалы, тогда как функция list::mergeвсегда модифицирует списки, с которыми она работает. Теперь вы располагаете всей необходимой информацией. Столкнувшись с выбором между алгоритмом STL и одноименной функцией контейнера, предпочтение следует отдавать функции контейнера. Она почти всегда эффективнее работает и лучше интегрируется с обычным поведением контейнеров. Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: count, find, binary_search, lower_bound, upper_boundи equal_range. Как же принять верное решение? Очень просто. Основными критериями должны быть скорость и простота. Временно предположим, что границы интервала поиска обозначены итераторами. Случай с поиском во всем контейнере будет рассмотрен ниже. При выборе стратегии поиска многое зависит от того, определяют ли итераторы сортированный интервал. Если это условие выполнено, воспользуйтесь алгоритмами binary_search, lower_bound, upper_boundи equal_rangeдля проведения быстрого поиска (обычно с логарифмической сложностью — см. совет 34). Если интервал не отсортирован, выбор ограничивается линейными алгоритмами count, count_if, findи find_if. В дальнейшем описании _if-версии алгоритмов countи findигнорируются, как и разновидности binary_search, lower_bound, upper_boundи equal_range, которым при вызове передается предикат. Алгоритм поиска выбирается по одним и тем же соображениям независимо от того, используете ли вы стандартный предикат или задаете свой собственный. Итак, в несортированных интервалах выбор ограничивается алгоритмами countи find. Эти алгоритмы решают несколько отличающиеся задачи, к которым следует присмотреться повнимательнее. Алгоритм countотвечает на вопрос: «Присутствует ли заданное значение, и если присутствует — то в каком количестве экземпляров?». Для алгоритма findвопрос звучит так: «Присутствует ли заданное значение, и если присутствует — то где именно?» Допустим, вы просто хотите проверить, присутствует ли в списке некоторое значение wкласса Widget. При использовании алгоритма count решение выглядит так: list<Widget> lw; // Список объектов Widget Widget w; // Искомое значение класса Widget … if (count(lw.begin(), lw.end(), w)) { … // Значение w присутствует в lw } else { … // Значение не найдено } В приведенном фрагменте продемонстрирована стандартная идиома: применение countдля проверки существования. Алгоритм countвозвращает либо ноль, либо положительное число; в программе ненулевое значение интерпретируется как логическая истина, а ноль — как логическая ложь. Возможно, следующая конструкция более четко выражает суть происходящего: if (count(lw.begin(), lw.end(), w) != 0)… Некоторые программисты предпочитают эту запись, но неявное преобразование, как в приведенном выше примере, встречается достаточно часто. Решение с алгоритмом findвыглядит чуть сложнее, поскольку возвращаемое значение приходится сравнивать с конечным итератором списка: if (find(lw.begin(), lw.end(), w) != lw.end()) { … } else { … } В контексте проверки существования идиоматическое использование countчуть проще кодируется. С другой стороны, оно также менее эффективно при успешном поиске, поскольку findпри обнаружении искомого значения немедленно прекращает поиск, a countпродолжает искать дополнительные экземпляры до конца интервала. Для большинства программистов выигрыш в эффективности компенсирует дополнительные хлопоты, связанные с программированием find. Впрочем, простой проверки существования во многих случаях бывает недостаточно; требуется также найти в интервале первый объект с заданным значением. Например, этот объект можно вывести, вставить перед ним другой объект или удалить его (удаление в процессе перебора рассматривается в совете 9). Если требуется узнать, какой объект (или объекты) имеют заданное значение, воспользуйтесь алгоритмом find: list<Widget>::iterator i = find(lw.begin(), lw.end(), w); if (i!=lw.end()) { … // Успешный поиск, i указывает на первый экземпляр } else { … // Значение не найдено } При работе с сортированными интервалами существуют и другие варианты, и им определенно стоит отдать предпочтение. Алгоритмы countи findработают с линейной сложностью, тогда как алгоритмы поиска в сортированных интервалах ( binary_search, lower_bound, upper_boundи equal_range) обладают логарифмической сложностью. Переход от несортированных интервалов к сортированным влечет за собой изменение критерия сравнения двух величин. Различия между критериями подробно описаны в совете 19, поэтому я не стану повторяться и замечу, что алгоритмы countи findиспользуют критерий равенства, а алгоритмы binary_search, lower_bound, upper_boundи equal_rangeоснованы на критерии эквивалентности. Присутствие величины в сортированном интервале проверяется алгоритмом binary_search. В отличие от функции bsearchиз стандартной библиотеки C (а значит, и стандартной библиотеки C++), алгоритм binary_searchвозвращает только bool. Алгоритм отвечает на вопрос: «Присутствует ли заданное значение в интервале?», и возможны только два ответа: «да» и «нет». Если вам понадобится дополнительная информация, выберите другой алгоритм. Пример применения binary_searchк сортированному вектору (преимущества сортированных векторов описаны в совете 23): vector<Widget> vw; // Создать вектор, заполнить … // данными и отсортировать sort(vw.begin(), vw.end()); Widget w; // Искомое значение … if (binary_search(vw.begin(), vw.end(), w)) { … // Значение w присутствует в vw } else { … // Значение не найдено } Если у вас имеется сортированный интервал и вы ищете ответ на вопрос: «Присутствует ли заданное значение в интервале, и если присутствует — то где именно?», следует использовать алгоритм equal_range, хотя на первый взгляд кажется, что вам нужен алгоритм lower_bound. Вскоре мы вернемся к equal_range, а пока проанализируем поиск в интервалах с применением алгоритма lower_bound. При поиске заданной величины в интервале алгоритм lower_boundвозвращает итератор, указывающий на первый экземпляр этой величины (в случае успешного поиска) или на правильную позицию вставки (в случае неудачи). Таким образом, алгоритм lower_boundотвечает на вопрос: «Присутствует ли заданное значение в интервале? Если присутствует, то где находится первый экземпляр, а если нет — где он должен находиться?». Как и в случае с алгоритмом find, результат lower_boundнеобходимо дополнительно проверить и убедиться в том, что он указывает на искомое значение. Но в отличие от find, его нельзя просто сравнить с конечным итератором. Вместо этого приходится брать объект, идентифицированный алгоритмом lower_bound, и проверять, содержит ли он искомое значение. Многие программисты используют lower_boundпримерно так: vector<Widget>::iterator = lower_bound(vw,begin(), vw.end(), w); if (i != vw.end() && *i == w) { // Убедиться в том, что i указывает // на объект, и этот объект имеет искомое // значение. Ошибка!!!! … // Значение найдено, i указывает на первый // экземпляр объекта с этим значением } else { … // Значение не найдено } В большинстве случаев такая конструкция работает, но в действительности она содержит ошибку. Присмотритесь к проверяемому условию: if (i != vw.end() && *i == w) { В этом условии проверяется равенство, тогда как lower_boundиспользует при поиске критерий эквивалентности. Как правило, результаты проверки по двум критериям совпадают, но, как показано в совете 19, это не всегда так. В таких ситуациях приведенный выше фрагмент не работает. Чтобы исправить ошибку, необходимо убедиться в том, что итератор, полученный от lower_bound, указывает на объект со значением, эквивалентным искомому. Проверку можно выполнить вручную (в совете 19 показано, как это делается, а в совете 24 приведен пример ситуации, когда такое решение оправданно), однако сделать это непросто, поскольку при этом должна использоваться та же функция сравнения, как и при вызове lower_bound. В общем случае мы имеем дело с произвольной функцией (или объектом функции). При передаче lower_boundфункции сравнения эта же функция должна использоваться и в «ручной» проверке эквивалентности; следовательно, при изменении функции сравнения, передаваемой lower_bound, вам придется внести соответствующие изменения в проверку эквивалентности. В принципе, синхронизировать функции сравнения не так уж сложно, но об этом необходимо помнить, а при программировании хлопот и без этого хватает. Существует простое решение: воспользуйтесь алгоритмом equal_range. Алгоритм возвращает пару итераторов; первый совпадает с итератором, возвращаемым lower_bound, а второй совпадает с итератором, возвращаемым upper_bound(то есть указывает в позицию за интервалом значений, эквивалентных искомому). Таким образом, алгоритм equal_rangeвозвращает пару итераторов, обозначающих интервал значений, эквивалентных искомому. Согласитесь, имя алгоритма выбрано довольно удачно. Возможно, правильнее было бы назвать его equvalent_range, но и equal_rangeвоспринимается неплохо. Относительно возвращаемого значения equal_rangeнеобходимо сделать два важных замечания. Если два итератора совпадают, это говорит о том, что интервал пуст, а значение не найдено. По этому факту можно судить о том, было ли найдено совпадение. Пример: vector<Widget> vw; … sort(vw.begin(), v.end()); typedef vector<Widget>::iterator VWIter; // Вспомогательные typedef pair<VWIter, VWIter> VWIterPair; // определения типов VWIterPar p = equal_range(vw.begin(), vw.end(), w); if (p.first != p.second) { // Если equal_range возвращает // непустой интервал… … // Значение найдено, p.first // указывает на первый элемент // интервала, а p.second - // на позицию за последним элементом } else { … // Значение не найдено, p.first // и p.second указывают на точку // вставки искомого значения } В этом фрагменте используется только критерий эквивалентности, поэтому он всегда верен. Другая особенность возвращаемого значения equal_rangeзаключается в том, что расстояние между двумя итераторами равно количеству объектов в интервале, то есть количеству объектов, эквивалентных искомому объекту. В результате equal_rangeне только выполняет функции findдля сортированных интервалов, но и заменяет count. Например, поиск в vwобъектов Widget, эквивалентных w, с последующим выводом их количества может выполняться следующим образом: VWIterPair р = equal_range(vw.begin(), vw.end(), w); cout << "There are " << distance(p.first, p.second) << " elements in vw equivalent to w."; До настоящего момента предполагалось, что в интервале ищетсянекоторое значение, но есть ситуации, в которых возникает задача поиска граничной позиции. Предположим, у нас имеется класс Timestamp и вектор объектов Timestamp, отсортированный от «старых» объектов к «новым»: class Timestamp {…}; bool operator<(const Timestamp& lhs, //Проверяет, предшествует ли const Timestamp& rhs); // объект lhs объекту rhs по времени vector<Timestamp> vt; // Создать вектор, заполнить данными … // и отсортировать так, чтобы sort(vt.begin(), vt.end()); // "старые" объекты предшествовали "новым" Предположим, из vtтребуется удалить все объекты, предшествующие некоторому пороговому объекту ageLimit. В данном случае не нужно искать в vtобъект Timestamp, эквивалентный ageLimit, поскольку объекта с точно совпадающим значением может и не быть. Вместо этого в vtищется граничная позиция, то есть первый элемент, не старший ageLimit. Задача решается элементарно, поскольку алгоритм loweboundпредоставляет всю необходимую информацию: Timestamp ageLimit; … vt.erase(vt.begin(), lower_bound(vt.begin(), // Удалить из vt все объекты, vt.end(), // предшествующие значению ageLimit)); // ageLimit Слегка изменим условия задачи. Допустим, требуется удалить все объекты, предшествующие или равные ageLimit. Для этого необходимо найти первый объект после ageLimit. Для решения задачи идеально подходит алгоритм upper_bound: vt.erase(vt.begin(), upper_bound(vt.begin(), // Удалить из vt все объекты, vt.end(), // предшествующие или ageLimit)); // эквивалентные ageLimit Алгоритм upper_boundтакже часто применяется при вставке в сортированные интервалы, когда объекты с эквивалентными значениями должны следовать в контейнере в порядке вставки. Рассмотрим сортированный список объектов Person, в котором объекты сортируются по имени: class Person { public: … const string& name() const; … } struct PersonNameLess: public binary_function<Person, Person, bool> { // См. совет 40 bool operator()(const Person& lhs, const Person& rhs) const { return lhs.name() < rhs.name(); } }; list<Person> lp; … lp.sort(PersonNameLess()); // Отсортировать lp по критерию // PersonNameLess Чтобы список сортировался требуемым образом (по имени, с хранением эквивалентных имен в порядке вставки), можно воспользоваться алгоритмом upper_boundдля определения позиции вставки: Person newPerson; … lp.insert(upper_bound(lp.begin(), // Вставить newPerson за последним lp.end(), // объектом lр, предшествующим newPerson, // или эквивалентным newPerson PersonNameLess()), newPerson); Приведенное решение работоспособно и достаточно удобно, но не стройте иллюзий насчет того, что оно каким-то волшебным способом обеспечивает поиск точки вставки в контейнер listс логарифмической сложностью. Как объясняется в совете 34, при работе с listпоиск занимает линейное время, но при этом выполняется логарифмическое количество сравнений. До настоящего момента рассматривался только случай, когда поиск осуществляется в интервале, определяемом парой итераторов. Довольно часто работать приходится со всем контейнером вместо интервала. В этом случае необходимо различать последовательные и ассоциативные контейнеры. Для стандартных последовательных контейнеров ( vector, string, dequeи list) достаточно следовать рекомендациям, изложенным ранее, используя начальный и конечный итераторы контейнера для определения интервала. Со стандартными ассоциативными контейнерами ( set, multiset, map, multimap) дело обстоит иначе. В них предусмотрены функции поиска, которые по своим возможностям обычно превосходят алгоритмы STL Превосходство функций контейнеров перед алгоритмами подробно рассматривается в совете 44; если говорить кратко — они быстрее работают и ведут себя более последовательно. К счастью, имена функций обычно совпадают с именами соответствующих алгоритмов, поэтому там, где речь идет об алгоритмах count, find, lower_bound, upper_boundи equal_range, при поиске в ассоциативных контейнерах вместо них достаточно выбрать одноименную функцию. К сожалению, для алгоритма binary_searchпарной функции не существует. Чтобы проверить наличие значения в контейнере setили map, воспользуйтесь идиоматической ролью countкак условия проверки: set<Widget> s; // Создать множество, заполнить данными … Widget w; // Искомое значение … if (s.count(w)) { // Существует значение, эквивалентное w … } else { … // Эквивалентное значение не существует } При проверке присутствия значений в контейнерах multisetили multimapфункция findобычно превосходит count, поскольку она останавливается при обнаружении первого объекта с искомым значением, а функция count в худшем случае просматривает все элементы контейнера. Тем не менее при подсчете объектов в ассоциативных контейнерах countнадежно занимает свою нишу. В частности, вызов countпредпочтительнее вызова equal_rangeс последующим применением distanceк полученным итераторам. Во-первых, само название функции подсказывает ее смысл — слово countозначает «подсчет». Во-вторых, countупрощает работу программиста, поскольку ему не приходится создавать пару и передавать ее компоненты при вызове distance. В-третьих, countработает чуть быстрее. Попробуем подвести итог всему, о чем говорилось в настоящем совете. Информация собрана в следующей таблице.
Несколько странно выгладит частое присутствие equal_rangeв столбце, относящемся к сортированным интервалам. Оно связано с особой ролью проверки эквивалентности при поиске. Использование lower_boundи upper_boundчревато ошибочной проверкой равенства, а при использовании equal_rangeболее естественно выглядит проверка эквивалентности. Во второй строке предпочтение отдается equal_rangeеще по одной причине: equal_rangeработает с логарифмическим временем, а вызов findсвязан с линейными затратами времени. Для контейнеров multisetи multimapв качестве возможных кандидатов для поиска первого объекта с заданным значением указаны два алгоритма, findи lower_bound. Обычно для решения этой задачи выбирается find— возможно, вы обратили внимание, что именно этот алгоритм указан в таблице для контейнеров setи map. Однако multi-контейнеры не гарантируют, что при наличии нескольких элементов с заданным значением findнайдет первый элемент в контейнере; известно лишь то, что будет найден один из этих элементов. Если вы действительно хотите найти первый объект с заданным значением, воспользуйтесь lower_boundи выполните вручную вторую часть проверки эквивалентности, описанной в совете 19 (без этой проверки можно обойтись при помощи equal_range, но вызов equal_rangeобходится дороже, чем вызов lower_bound). Выбрать между count, find, binary_search, lower_bound, upper_boundи equal_rangeнесложно. Предпочтение отдается тому алгоритму или функции, которые обладают нужными возможностями, обеспечивают нужное быстродействие и требуют минимальных усилий при вызове. Следуйте этой рекомендации (или обращайтесь к таблице), и у вас никогда не будет проблем с выбором. Совет 46. Передавайте алгоритмам объекты функций вместо функций Часто говорят, что повышение уровня абстракции языков высокого уровня приводит к снижению эффективности сгенерированного кода. Александр Степанов, изобретатель STL, однажды разработал небольшой комплекс тестов для оценки «платы за абстракцию» при переходе с C на C++. В частности, результаты этих тестов показали, что код, сгенерированный для работы с классом, содержащим double, почти всегда уступает по эффективности соответствующему коду, непосредственно работающему с double. С учетом сказанного вас может удивить тот факт, что передача алгоритмам объектов функций STL — то есть объектов, маскирующихся под функции, — обычно обеспечивает более эффективный код, чем передача «настоящих» функций. Предположим, вы хотите отсортировать вектор чисел типа doubleпо убыванию. Простейшее решение этой задачи средствами STL основано на использовании алгоритма sortс объектом функции типа greater<double>: vector<double> v; … sort(v.begin(), v.end(), greater<double>()); Вспомнив о «плате за абстракцию», программист решает заменить объект функции «настоящей» функцией, которая к тому же оформлена как подставляемая ( inline):
return d1 > d2; } … sort(v.begin(), v.end(), doubleGreater); Как ни странно, хронометраж двух вызовов sort показывает, что вызов с greater<double>почти всегда работает быстрее. В своих тестах я сортировал вектор, содержащий миллион чисел типа double, на четырех разных платформах STL с оптимизацией по скорости, и версия с greater<double>всегда работала быстрее. В худшем случае выигрыш в скорости составил 50%, в лучшем он достигал 160%. Вот тебе и «плата за абстракцию»… Факт объясняется просто. Если функция operator()объекта функции была объявлена подставляемой (явно, с ключевым словом inline, или косвенно, посредством определения внутри определения класса), большинство компиляторов благополучно подставляет эту функцию во время создания экземпляра шаблона при вызове алгоритма. В приведенном выше примере это происходит с функцией greater<double>::operator(). В результате код sortне содержит ни одного вызова функций, а для такого кода компилятор может выполнить оптимизацию, недоступную при наличии вызовов (связь между подстановкой функций и оптимизацией компиляторов рассматривается в совете 33 «Effective C++» и главах 8-10 книги «Efficient C++» [10]). При вызове sortс передачей doubleGreaterситуация выглядит иначе. Чтобы убедиться в этом, необходимо вспомнить, что передача функции в качестве параметра другой функции невозможна. При попытке передачи функции в качестве параметра компилятор автоматически преобразует функцию в указатель на эту функцию, поэтому при вызове передается указатель. Таким образом, при вызове sort(v.begin(), v.end(), doubleGreater); алгоритму sortпередается не doubleGreater, а указатель на doubleGreater. При создании экземпляра шаблона объявление сгенерированной функции выглядит так: void sort(vector<double>::iterator first, // Начало интервала vector<double>:iterator last, // Конец интервала bool (*comp)(double, double)); // Функция сравнения Поскольку compявляется указателем на функцию, при каждом его использовании внутри sort происходит косвенный вызов функции (то есть вызов через указатель). Большинство компиляторов не пытается подставлять вызовы функций, вызываемых через указатели, даже если функция объявлена с ключевым словом inlineи оптимизация выглядит очевидной. Почему? Наверное, потому, что разработчики компиляторов не считают нужным ее реализовать. Пожалейте их — народ постоянно чего-нибудь требует, а успеть все невозможно. Впрочем, это вовсе не означает, что требовать не нужно. Подавление подстановки кода функций объясняет один факт, который кажется невероятным многим опытным программистам C: функция C++ sortпочти всегда превосходит по скорости функцию C qsort. Конечно, в C++ приходится создавать экземпляры шаблонов функций и вызывать operator(), тогда как в C все ограничивается простым вызовом функции, однако все «излишества» C++ теряются во время компиляции. На стадии выполнения sortобращается к подставленной функции сравнения (при условии, что функция была объявлена с ключевым словом inline, а ее тело доступно на стадии компиляции), тогда как qsortвызывает функцию сравнения через указатель. Результат — sortработает гораздо быстрее. В моих тестах с вектором, содержащим миллион чисел double, превосходство по скорости достигало 670%, но я не призываю верить мне на слово. Вы легко убедитесь в том, что при передаче объектов функций в качестве параметров алгоритмов «плата за абстракцию» превращается в «премию за абстракцию». Существует и другая причина для передачи объектов функций в параметрах алгоритмов, не имеющая ничего общего с эффективностью. Речь идет о компилируемости программ. По каким-то загадочным причинам некоторые платформы STL отвергают абсолютно нормальный код — это связано с недоработками то ли компилятора, то ли библиотеки, то ли и того и другого. Например, одна распространенная платформа STL отвергает следующий (вполне допустимый) фрагмент, выводящий в coutдлину всех строк в множестве: set<string> s; … transform(s.begin(), s.end(), ostream_iterator<string::size_type>(cout, "\n"), mem_fun_ref(&string::size) ); Проблема возникает из-за ошибки в работе с константными функциями классов (такими как string::size) в этой конкретной платформе STL. Обходное решение заключается в использовании объекта функции: struct StringSize: public_unary_function<string, string::size_type> { // См. совет 40
return s.size(); } }; transform (s.begin(), s.end(), ostream_iterator<string::size_type>(cout, "\n"), StringSize(); Существуют и другие обходные решения, но приведенный фрагмент хорош не только тем, что он компилируется на всех известных мне платформах STL. Он также делает возможной подстановку вызова string::size, что почти наверняка невозможно в предыдущем фрагменте с передачей mem_fun_ref(&string::size). Иначе говоря, определение класса функтора StringSizeне только обходит недоработки компилятора, но и может улучшить быстродействие программы. Другая причина, по которой объекты функций предпочтительнее обычных функций, заключается в том, что они помогают обойти хитрые синтаксические ловушки. Иногда исходный текст, выглядящий вполне разумно, отвергается компилятором по законным, хотя и неочевидным причинам. Например, в некоторых ситуациях имя экземпляра, созданного на базе шаблона функции, не эквивалентно имени функции. Пример: template<typename FPType> // Вычисление среднего FPType average(FPType val1, FPType val2) // арифметического двух { //вещественных чисел return (val1 + val2)/2; }; template<typename InputIter1, typename InputIter2> void writeAverages(InputIter begin1, // Вычислить попарные InputIter end1, // средние значения InputIter begin2, // двух серий элементов ostream& s) { // в потоке transform(begin1, end1, begin2, ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s, "\n"), average<typename iterator traits<InputIter1>::value_type>()); // Ошибка? } Многие компиляторы принимают этот код, но по Стандарту C++ он считается недопустимым. Дело в том, что теоретически может существовать другой шаблон функции с именем average, вызываемый с одним параметром-типом. В этом случае выражение average<typename iterator_traits<InputIter1>::value_type>становится неоднозначным, поскольку непонятно, какой шаблон в нем упоминается. В конкретном примере неоднозначность отсутствует, но некоторые компиляторы на вполне законном основании все равно отвергают этот код. Решение основано на использовании объекта функции: template<typename FPType> struct Average: public binary_function<FPType, FPType, FPType> { // См. совет 40
return average(val1, val2); } }; template<typename InputIter1, typename InputIter2> void writeAverages(InputIter1 begin1, InputIter1 end1, InputIter2 begin2, ostream& s) { transform(begin1, end1, begin2, ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s, "\n"), Average<typename iterator_traits<InputIter1>::value_type()); } Новая версия должна приниматься любым компилятором. Более того, вызовы Average::operator()внутри transformдопускают подстановку кода, что не относится к экземплярам приведенного выше шаблона average, поскольку averageявляется шаблоном функции, а не объекта функции. Таким образом, преимущество объектов функций в роли параметров алгоритмов не сводится к простому повышению эффективности. Объекты функций также обладают большей надежностью при компиляции кода. Бесспорно, «настоящие» функции очень важны, но в области эффективного программирования в STL объекты функций часто оказываются полезнее. Совет 47. Избегайте «нечитаемого» кода Допустим, имеется вектор vector<int>. Из этого вектора требуется удалить все элементы, значение которых меньше х, но оставить элементы, предшествующие последнему вхождению значения, не меньшего у. В голову мгновенно приходит следующее решение: vector<int> v; int х, у; … v.erase( remove_if(find_if(v.rbegin(), v.rend(), bind2nd(greater_equal<int>(), y)).base(), v.end(), bind2nd(less<int>(),x)), v.end()); Всего одна команда, и задача решена. Все просто и прямолинейно. Никаких проблем. Правда? Не будем торопиться с выводами. Считаете ли вы приведенный код логичным и удобным в сопровождении? «Нет!» — воскликнет большинство программистов C++ с ужасом и отвращением. «Да!» — скажут считанные единицы с явным удовольствием. В этом и заключается проблема. То, что один программист считает выразительной простотой, другому представляется адским наваждением. Насколько я понимаю, приведенный выше фрагмент вызывает беспокойство по двум причинам. Во-первых, он содержит слишком много вызовов функций. Чтобы понять, о чем идет речь, приведу ту же команду, в которой имена функций заменены обозначениями fn: v.f1(f2(f3(v.f4(), v.f5(),f6(f7(), y)).f8(), v.f9(), f6(f10(), x)), v.f9()); Такая запись выглядит неестественно усложненной, поскольку из нее убраны отступы, присутствующие в исходном примере. Можно уверенно сказать, что большинство программистов C++ сочтет, что двенадцать вызовов десяти разных функций в одной команде — это перебор. Но программисты с опытом работы на функциональных языках типа Scheme могут считать иначе. По своему опыту могу сказать, что почти все программисты, которые просматривали этот фрагмент без малейших признаков удивления, имели основательный опыт программирования на функциональных языках. У большинства программистов C++ такой опыт отсутствует, так что если ваши коллеги не привыкли к многоуровневым вложениям вызовов функций, конструкции вроде предыдущего вызова erase будут приводить их в замешательство. Второй недостаток приведенного кода заключается в том, что для его понимания нужно хорошо знать STL. В нем встречаются менее распространенные _if-формы алгоритмов findи remove, обратные итераторы (см. совет 26), преобразования reverse_iteratorв iterator(см. совет 28), bind2ndи анонимные объекты функций, а также идиома erase-remove(см. совет 32). Опытный программист STL разберется в этой комбинации без особого труда, но гораздо больше будет таких, кто надолго задумается над ней. Если ваши коллеги далеко продвинулись в изучении STL, присутствие erase, remove_if, find_if, baseи bind2ndв одной команде вполне допустимо, но если вы хотите, чтобы ваша программа была понятна программисту C++ со средним уровнем подготовки, я рекомендую разделить эту команду на несколько фрагментов. Ниже приведен один из возможных вариантов (комментарии приводятся не только для книги — я бы включил их и в программу). typedef vector<int>::iterator VecIntIter; // Инициализировать angeBegin первым элементом v, большим или равным // последнему вхождению у. Если такой элемент не существует, rangeBegin // инициируется значением v.begin() VecIntIter rangeBegin = find_if(v.rbegin(), v.rend(), bind2nd(greater_equal<int>(), y)).base(); // Удалить от rangeBegin до v.end все элементы со значением, меньшим х v.erase(remove_if(rangeBegin, v.end(), bind2nd(less<int>(), x)), v.end()); Возможно, даже этот вариант кое-кого смутит, поскольку он требует понимания идиомы erase-remove, но при наличии комментариев в программе и хорошего справочника по STL (например, «The C++ Standard Library» [3] или web-сайта SGI [21]) каждый программист C++ без особых усилий разберется, что же происходит в программе. Обратите внимание: в процессе модификации я не отказался от использования алгоритмов и не попытался заменить их циклами. В совете 43 объясняется, почему алгоритмы обычно предпочтительнее циклов, и приведенные аргументы действуют и в этом случае. Основная цель при программировании заключается в создании кода, понятного как для компилятора, так и для читателя-человека, и обладающего приемлемым быстродействием. Алгоритмы почти всегда лучше подходят для достижения этой цели. Тем не менее, совет 43 также объясняет, почему интенсивное использование алгоритмов естественным образом приводит к частому вложению вызовов функций и использованию адаптеров функторов. Вернемся к постановке задачи, с которой начинается настоящий совет. Допустим, имеется вектор vector<int>. Из этого вектора требуется удалить все элементы, значение которых меньше x, но оставить элементы, предшествующие последнему вхождению значения, не меньшего y. Нетрудно придти к общей схеме решения: • поиск последнего вхождения значения в векторе требует применения findили find_ifс обратными итераторами; • удаление элементов требует eraseили идиомы erase-remove. Объединяя эти две идеи, мы получаем следующий псевдокод, где «нечто» обозначает код, который еще не был наполнен смысловым содержанием: v.erase(remove_if(find_if(v.rbegin(), v.rend(), нечто).base(), v.end(), нечто)), v.end()); При наличии такой схемы рассчитать, что же кроется за «нечто», совсем несложно. Вы не успеете опомниться, как придете к решению из исходного примера. Во время написания программы подобные решения выглядят вполне логичными, поскольку в них отражается последовательное применение базовых принципов (например, идиомы erase-removeплюс использование findс обратными итераторами). К сожалению, читателю вашей программы будет очень трудно разобрать готовый продукт на те идеи, из которых он был собран. «Нечитаемый» код легко пишется, но разобраться в нем трудно. Впрочем, «нечитаемость» зависит от того, кто именно читает программу. Как упоминалось выше, некоторые программисты C++ вполне нормально относятся к конструкциям вроде приведенной в начале этого совета. Если такая картина типична для среды, в которой вы работаете, и вы ожидаете, что она останется таковой в будущем, не сдерживайте свои творческие порывы. Но если ваши коллеги недостаточно уверенно владеют функциональным стилем программирования и не столь хорошо разбираются в STL, умерьте свои амбиции и напишите что-нибудь вроде альтернативного решения, приведенного выше. Банальный факт из области программирования: код чаще читается, чем пишется. Хорошо известно также, что на сопровождение программы уходит значительно больше времени, чем на ее разработку. Если программу нельзя прочитать и понять, ее нельзя и успешно сопровождать, а такие программы вообще никому не нужны. Чем больше вы работаете с STL, тем увереннее себя чувствуете и тем сильнее хочется использовать вложенные вызовы функций и создавать объекты функций «на лету». В этом нет ничего плохого, но всегда следует помнить, что написанную сегодня программу завтра придется кому-то читать — может быть, даже вам. Приготовьтесь к этому дню. Да, используйте STL в своей работе. Используйте хорошо и эффективно… но избегайте написания «нечитаемого» кода. В долгосрочной перспективе такой код будет каким угодно, но только не эффективным. Совет 48. Всегда включайте нужные заголовки При программировании в STL нередко встречаются программы, которые успешно компилируются на одной платформе, но требуют дополнительных директив #includeна другой. Этот раздражающий факт связан с тем, что Стандарт C++ (в отличие от Стандарта C) не указывает, какие стандартные заголовки могут или должны включаться в другие стандартные заголовки. Авторы реализаций пользуются предоставленной свободой и выбирают разные пути. Попробую пояснить, что это значит на практике. Однажды я засел за пять платформ STL (назовем их A, B, C, D и E) и попробовал экспериментальным путем определить, какие стандартные заголовки можно убрать, чтобы программа при этом нормально компилировалась. По этим данным становится ясно, какие заголовки включают другие заголовки директивой #include. Вот что я узнал: • на платформах A и C <vector>включает <string>; • на платформе C <algorithm>включает <string>; • на платформах C и D <iostream>включает <iterator>; • на платформе D <iostream>включает <string>и <vector>; • на платформах D и E <string>включает <algorithm>; • во всех пяти реализациях <set>включает <functional>. За исключением последнего случая мне так и не удалось провести программу с убранным заголовком мимо реализации B. По закону Мэрфи вам всегда придется вести разработку на таких платформах, как A, C, D и E, и переносить программы на такие платформы, как B, особенно когда это очень важная работа, которую необходимо сделать как можно скорее. Так бывает всегда. Но не стоит осуждать компиляторы или разработчиков библиотек за трудности с переносом. Пропущенные заголовки на вашей ответственности. При каждой ссылке на элементы пространства имен std вы также отвечаете за включение соответствующих заголовков. Если заголовки опущены, программа теоретически может откомпилироваться, но другие платформы STL имеют полное право отвергнуть ваш код. Чтобы вам было проще запомнить необходимые заголовки, далее приведена краткая сводка содержимого всех стандартных заголовков, относящихся к STL. • Почти все контейнеры объявляются в одноименных заголовках, то есть vectorобъявляется в заголовке <vector>, listобъявляется в заголовке <list>и т. д. Исключениями являются <set>и <map>. В заголовке <set>объявляются контейнеры setи multiset, а в заголовке <map>объявляются контейнеры mapи multimap. • Все алгоритмы, за исключением четырех, объявляются в заголовке <algorithm>. Исключениями являются алгоритмы accumulate(см. совет 37), inner_poduct, adjacent_differenceи partial_sum. Эти алгоритмы объявляются в заголовке <numeric>. • Специализированные разновидности итераторов, включая istream_iteratorи streambuf_iterator(см. совет 29), объявляются в заголовке <iterator>. • Стандартные функторы (например less<T>) и адаптеры функторов (например not1и bind2nd) объявляются в заголовке <functional>. Не забывайте включать соответствующую директиву #includeпри использовании любых из перечисленных компонентов, даже если платформа разработки позволяет обойтись и без нее. Ваше прилежание непременно окупится при переносе программы на другую платформу. Совет 49. Научитесь читать сообщения компилятора При определении вектора в программе вы имеете полное право указать конкретный размер: vector<int> v(10); // Создать вектор из 10 элементов Объекты string имеют много общего с vector, поэтому кажется, что следующая команда тоже допустима: string s(10); // Попытаться определить string из 10 элементов Однако эта команда не компилируется, поскольку у контейнера stringне существует конструктора, вызываемого с аргументом типа int. На одной из платформ STL компилятор реагирует на эту команду следующим образом: example.cpp(20):error С2664:'))thiscall std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >::std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >(const class std::allocator<char>&)': cannot convert parameter 1 from 'const int' to 'const class std::allocator<char>&' Reason: cannot convert from 'const int' to 'const class std::allocator<char>' No constructor could take the source type, or constructor overload resolution was ambiguous Ну как, впечатляет? Первая часть сообщения выглядит как беспорядочное нагромождение символов, вторая часть ссылается на распределитель памяти, ни разу не упоминавшийся в исходном тексте, а в третьей части что-то говорится о вызове конструктора. Конечно, третья часть содержит вполне точную информацию, но для начала разберемся с первой частью, типичной для диагностики, часто встречающейся при работе со string. Вспомните, что string— не самостоятельный класс, а простой синоним для следующего типа: basic_string<char, char_traits<char>, allocator<char> > Это связано с тем, что понятие строки C++ было обобщено до последовательности символов произвольного типа, обладающих произвольными характеристиками («traits») и хранящихся в памяти, выделенной произвольными распределителями. Все string-подобные объекты C++ в действительности являются специализациями шаблона basic_string, поэтому при диагностике ошибок, связанных с неверным использованием string, большинство компиляторов упоминает тип basic_string(некоторые компиляторы любезно включают в диагностику имя string, но большинство из них этого не делает). Нередко в диагностике указывается на принадлежность basic_string(а также вспомогательных шаблонов char_traitsи allocator) к пространству имен std, поэтому в сообщениях об ошибках, связанных с использованием string, нередко упоминается тип std::basic_string<char, std::char_traits<char>, std::allocator<char> > Такая запись весьма близка к той, что встречается в приведенной выше диагностике, но разные компиляторы могут описывать stringпо-разному. На другой платформе STL ссылка на stringвыглядит иначе: basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > Имена string_char_traitsи default_alloc_templateне являются стандартными, но такова жизнь. Некоторые реализации STL отклоняются от Стандарта. Если вам не нравятся отклонения в текущей реализации STL, подумайте, не стоит ли перейти на другую реализацию. В совете 50 перечислены некоторые ресурсы, в которых можно найти альтернативные реализации. Независимо от того, как тип stringупоминается в диагностике компилятора, методика приведения диагностики к осмысленному минимуму остается той же: хитроумная конструкция с basic_stringзаменяется текстом « string». Если вы используете компилятор командной строки, задача обычно легко решается при помощи программы sed или сценарных языков типа Perl, Python или Ruby (пример сценария приведен в статье Золмана (Zolman) «An STL Error Message Decryptor for Visual C++» [26]). В приведенном примере производится глобальная замена фрагмента std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > строкой string, в результате чего будет получено следующее сообщение: example.срр(20):error С2664:'))thiscall string::string(const class std::allocator<char>&)': cannot convert parameter 1 from 'const int' to 'const class std::allocator<char>&' Из этого сообщения можно понять, что проблема связана с типом параметра, переданного конструктору string. Несмотря на загадочное упоминание allocator<char>, вам не составит труда просмотреть различные формы конструкторов stringи убедиться в том, что ни одна из этих форм не вызывается только с аргументом размера. Кстати, упоминание распределителя памяти (allocator) связано с наличием у всех стандартных контейнеров конструктора, которому передается только распределитель памяти. У типа stringсуществуют три одноаргументных конструктора, но компилятор по какой-то причине решает, что вы пытаетесь передать именно распределитель. Его предположение ошибочно, а диагностика лишь сбивает с толку. Что касается конструктора, получающего только распределитель памяти, — пожалуйста, не используйте его; он слишком часто приводит к появлению однотипных контейнеров с неэквивалентными распределителями памяти. Как правило, такая ситуация крайне нежелательна (более подробные объяснения приведены в совете 11). Рассмотрим пример более сложной диагностики. Предположим, вы реализуете программу для работы с электронной почтой, которая позволяет ссылаться на адресатов не только по адресам, но и по синонимам — скажем, адресу президента США (president@whitehouse.gov) ставится в соответствие синоним «The Big Cheese». В такой программе может использоваться ассоциативный контейнер для отображения синонимов на адреса электронной почты и функция showEmailAddress, которая возвращает адрес для заданного синонима: class NiftyEmailProgram { private: typedef map<string, string> NicknameMap; NicknameMap nicknames; public: void showEmailAddress(const string& nickname) const; }; В реализации showEmailAddressпотребуется найти адрес электронной почты, ассоциированный с заданным синонимом. Для этого может быть предложен следующий вариант: void NiftyEmail Program::showEmailAddress(const string& nickname) const { NicknameMap::iterator i = nicknames.find(nickname); if (i !=nicknames.end())… } Компилятору такое решение не понравится. На то есть веская, но не очевидная причина. Чтобы помочь вам разобраться в происходящем, одна из платформ STL услужливо выдает следующее сообщение: example.cpp(17):error С2440:'initializing': cannot convert from 'class std::_Tree<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, struct std::pair<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > const, class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > >, struct std::map<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, struct std::less<class std::basc_string<char, struct std::char_traits<char>, class std::allocator<char> > >, class std::allocator<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > > >::_Kfn, struct std::less<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > >, class std::allocator<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > > >::const_iterator' to 'class std::_Tree<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, struct std::pair<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > const, class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > >, struct std::map<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, class std: std::char_traits<char>, class std::allocator<char> >, struct std std::basic_string<char, struct std::char_traits<char>, class std::basic_string<char, struct std::less<class std::allocator<char> >, struct std::less<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > >, class std::allocator<class std::char traits<char>, class std::allocator<char> : basic_string<char, struct : _Kfn, struct std::less<class std::<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, struct std::char_traits<char>, class std::basic_string<char, struct std::pair<class std::basic_string<char, struct allocator<char> > const, class std::char_traits<char>, class std::allocator<char> >, struct std::map<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >, class std std::allocator<char> >, struct std::char_traits<char>, class std::basic_string<char, struct std::_Kfn, struct std::less<class std::allocator<char> > >, class std::basic_string<char, struct std::char_traits<char>, class less<class std::basic_string<char, struct allocator<char> > >, class std::char_traits<char>, class std::basic_string<char, struct std::allocator<class allocator<char> > > >::char traits<char>, class std::allocator<class std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> > > >::iterator' No constructor could take the source type, or constructor overload resolution was ambiguous Сообщение состоит из 2095 символов и выглядит довольно устрашающе, но я видал и похуже. Например, одна из моих любимых платформ STL однажды выдала сообщение из 4812 символов. Наверное, вы уже догадались, что я люблю ее совсем не за это. Давайте немного сократим эту хаотическую запись и приведем ее к более удобному виду. Начнем с замены конструкции basic_string… на string. Результат выглядит так: example.cpp(17):error С2440:'initializing': cannot convert from 'class std::_Tree<class string, struct std::pair<class string const, class string >, struct std::map<class string, class string, struct std::less<class string>, class std::allocator<class string > >::_Kfn, struct std::less<class string>, class std::allocator<class string> >::const_iterator' to 'class std::_Tree<class string, struct std::pair<class string const, class string>, struct std::map<class string, class string, struct std::less<class string>, class std::allocator<class string> >::_Kfn, struct std::less<class string>, class std::allocator<class string> >: iterator' No constructor could take the source type, or constructor overload resolution was ambiguous Уже лучше. Осталось каких-нибудь 745 символов, можно начинать разбираться в сообщении. В глаза бросается упоминание шаблона std::_Tree. В Стандарте ничего не сказано о шаблоне с именем Tree, но мы помним, что имена, начинающиеся с символа подчеркивания и прописной буквы, зарезервированы для авторов реализаций. Перед нами один из внутренних шаблонов, используемых в реализации некой составляющей STL. Оказывается, практически во всех реализациях STL стандартные ассоциативные контейнеры ( set, multiset, mapи multimap) строятся на основе базовых шаблонов. По аналогии с тем, как при использовании string в диагностике упоминается тип basic_string, при работе со стандартными ассоциативными контейнерами часто выдаются сообщения с упоминанием базовых шаблонов. В данном примере этот шаблон называется _Tree, но в других известных мне реализациях встречались имена treeи _rb_tree, причем в последнем имени отражен факт использования красно-черных (Red-Black) деревьев, самой распространенной разновидности сбалансированных деревьев, встречающейся в реализациях STL. В приведенном выше сообщении упоминается знакомый тип std::map<class string, class string, stuct std::less<class string>, class std::allocator<class string> >. Перед нами тип используемого контейнера map, если не считать типов функции сравнения и распределителя памяти (которые не были заданы при определении контейнера). Сообщение об ошибке станет более понятным, если заменить этот тип нашим вспомогательным определением NicknameMap. Результат: example.срр(17):error С2440:'initalzing': cannot convert from 'class std::_Tree<class string, struct std::pair<class string const, class string >, struct NicknameMap::_Kfn, struct std::less<class string>, class std::allocator<class string > >::const_iterator' to 'class std::_Tree<class string, struct std::pair<class string const, class string>, struct NicknameMap_Kfn, struct std::less<class string>, class std::allocator<class string> >: iterator' No constructor could take the source type, or constructor overload resolution was ambiguous Сообщение стало короче, но его смысл остался туманным; нужно что-то сделать с _Tree. Известно, что шаблон _Treeзависит от реализации, поэтому узнать смысл его параметров можно только одним способом — чтением исходных текстов. Но зачем копаться в исходных текстах реализации STL, если это не нужно? Попробуем просто заменить все данные, передаваемые Tree, условным обозначением «НЕЧТО» и посмотрим, что из этого выйдет. Результат: example.cpp(17):error С2440:'initalizing': cannot convert from 'class std::_Tree<НЕЧТО::const_iterator' to 'class std::_Tree<НЕЧТО:iterator' No constructor could take the source type, or constructor overload resolution was ambiguous А вот с этим уже можно работать. Компилятор жалуется на попытку преобразования const_iteratorв iteratorс явным нарушением правил константности. Вернемся к исходному примеру; строка, вызвавшая гнев компилятора, выделена жирным шрифтом: class NiftyEmailProgram { private: typedef map<string, string> NicknameMap; NicknameMap nicknames; public: void showEmailAddress(const string& nickname) const; }; void NiftyEmailProgram::showEmailAddress(const string& nickname) const { NicknameMap::iterator i = nicknames.find(nickname); if (i != nicknames.end())… } Сообщение об ошибке можно истолковать лишь одним разумным образом — мы пытаемся инициализировать переменную i(типа iterator) значением типа const_iterator, возвращаемым при вызове map::find. Такая интерпретация выглядит несколько странно, поскольку findвызывается для объекта nicknames. Объект nicknamesне является константным, поэтому функция find должна вернуть неконстантный итератор. Взгляните еще раз. Да, объект nicknamesобъявлен как неконстантный тип map, но функция showEmalAddressявляется константной, а внутри константной функции все нестатические переменные класса становятся константными! Таким образом, внутри showEmalAddressобъект nicknamesявляется константным объектом map. Сообщение об ошибке внезапно обретает смысл. Мы пытаемся сгенерировать iteratorдля объекта map, который обещали не изменять. Чтобы исправить ошибку, необходимо либо привести iк типу const_iterator, либо объявить showEmalAddressнеконстантной функцией. Вероятно, оба способа потребуют значительно меньших усилий, чем выяснение смысла сообщения об ошибке. В этом совете были показаны некоторые текстовые подстановки, уменьшающие сложность сообщений об ошибках, но после непродолжительной практики вы сможете выполнять подстановки в голове. Я не музыкант, но мне рассказывали, что хорошие музыканты способны читать партитуру целиком, не присматриваясь к отдельным нотам. Опытные программисты STL приобретают аналогичные навыки. Они могут автоматически преобразовать конструкцию вида std::basic_string<char, std::char_traits<char>, std::allocator<char> >в string, нисколько не задумываясь над происходящим. Подобный навык разовьется и у вас, но до этих пор следует помнить, что диагностику компилятора почти всегда можно привести к вразумительному виду заменой длинных типов на базе шаблонов более короткими мнемоническими обозначениями. Во многих случаях для этого достаточно заменить расширенные определения типов именами, используемыми в программе. Именно это было сделано в приведенном примере, когда мы заменили std::map<class string, class string, struct std::less<class string>, class std::allocator<class string> >на NicknameMap. Далее приведены некоторые рекомендации, которые помогут вам разобраться в сообщениях компилятора, относящихся к STL. • Для контейнеров vectorи stringитераторы обычно представляют собой указатели, поэтому в случае ошибки с итератором в диагностике компилятора обычно указываются типы указателей. Например, если в исходном коде имеется ссылка на vector<double>::iterator, в сообщении почти наверняка будет упоминаться указатель double*. Исключение составляет реализация STLport в отладочном режиме; в этом случае итераторы vectorи stringне являются указателями. За информацией о STLport и отладочном режиме обращайтесь к совету 50. • Сообщения, в которых упоминаются back_insert_iterator, front_insert_iteratorи insert_iterator, почти всегда означают, что ошибка была допущена при вызове back_inserter, front_inserterили inserterсоответственно ( back_inserterвозвращает объект типа back_insert_iterator, front_inserterвозвращает объект типа front_insert_iterator, a inserterвозвращает объект типа insert_iterator; за информацией об этих типах обращайтесь к совету 30). Если эти функции не вызывались в программе, значит, они были вызваны из других функций (косвенно или явно). • Сообщения с упоминаниями binder1stи binder2ndобычно свидетельствуют об ошибке при использовании bind1stи bind2nd( bind1stвозвращает объект типа binder1st, a bind2ndвозвращает объект типа binder2nd). • Итераторы вывода (например, ostream_iteratorи ostream_buf_iterator— см. совет 29, а также итераторы, возвращаемые back_inserter, front_inserterи inserter) выполняют свои операции вывода или вставки внутри операторов присваивания, поэтому ошибки, относящиеся к этим типам итераторов, обычно приводят к появлению сообщений об ошибке внутри операторов присваивания, о которых вы и понятия не имеете. Чтобы понять, о чем идет речь, попробуйте откомпилировать следующий фрагмент: vector<string*> v; // Попытка вывода содержимого copy(v.begin(), v.end(), // контейнера указателей string* ostream_iterator<string>(cout, "\n")); // как объектов string • Если полученное сообщение об ошибке исходит из реализации алгоритма STL (то есть если код, в котором произошла ошибка, находится в <algoritm>), вероятно, проблема связана с типами, которые вы пытаетесь передать этому алгоритму. Пример — передача итераторов неправильной категории. Попробуйте откомпилировать следующий фрагмент: list<int>::iterator i1, i2; // Передача двусторонних итераторов sort(i1, i2); // алгоритму, которому необходимы итераторы // произвольного доступа • Если вы используете стандартный компонент STL (например, контейнер vectorили string, алгоритм for_each), а компилятор утверждает, что он понятия не имеет, что имеется в виду, скорее всего, вы забыли включить необходимый заголовочный файл директивой #include. Как объясняется в совете 48, эта проблема может нарушить работоспособность кода, успешно компилировавшегося в течение некоторого времени, при переносе его на другую платформу. Совет 50. Помните о web-сайтах, посвященных STL Интернет богат информацией об STL. Если ввести в любой поисковой системе запрос «STL», вы получите сотни ссылок, часть из которых даже будет содержать полезную информацию. Впрочем, большинство программистов STL в поисках не нуждается и хорошо знает следующие сайты: • сайт SGI STL, http://www.sgi.com/tech/stl; • сайт STLport, http://stlport.org; • сайт Boost, http://www.boost.org. Ниже я постараюсь объяснить, почему эти сайты заслуживают вашего внимания. Сайт SGI STL Web-сайт SGI STL не случайно находится в начале списка. На нем имеется подробная документация по всем компонентам STL. Многие программисты рассматривают его как основной источник электронной документации незав4исимо от используемой платформы STL. Документацию собрал Мэтт Остерн (Matt Austern), который позднее дополнил ее и представил в книге «Generic Programming and the STL» [4]. Материал не сводится к простому описанию компонентов STL. Например, описание потоковой безопасности контейнеров STL (см. совет 12) основано на материалах сайта SGI STL. На сайте SGI программисту предлагается свободно распространяемая реализация STL. Она была адаптирована лишь для ограниченного круга компиляторов, но поставка STL легла в основу распространенной поставки STLport, описанной ниже. Более того, в реализацию STL от SGI входят некоторые нестандартные компоненты, делающие программирование в STL не только более мощным и гибким, но и более интересным. Некоторые из них стоит выделить. • Хэшированные ассоциативные контейнеры • Односвязный список slistреализован наиболее стандартным образом, а итераторы указывают на те узлы списка, на которые они и должны указывать. К сожалению, этот факт оборачивается дополнительными затратами при реализации функций insert и erase, поскольку обе функции должны модифицировать указатель на следующий узел списка в узле, предшествующем тому, на который указывает итератор. В двусвязном списке (например, в стандартном контейнере list) это не вызывает проблем, но в односвязном списке возврат к предыдущему узлу является операцией с линейной сложностью. В контейнере slistиз реализации SGI функции insertи eraseвыполняются с линейной сложностью вместо постоянной, что является существенным недостатком. В реализации SGI эта проблема решается при помощи нестандартных (но зато работающих с постоянной сложностью) функций insert_afterи erase_after. В сопроводительной документации говорится:
В реализацию Dinkumware также входит односвязный список slist, но в нем используется другая архитектура итераторов, сохраняющая постоянную сложность при вызовах insert и erase. За дополнительной информацией о Dimkumware обращайтесь к приложению Б. • Контейнер ropeописывается так:
Во внутреннем представлении контейнер ropeреализуется в виде дерева подстрок с подсчетом ссылок, при этом каждая строка хранится в виде массива char. Одна из интересных особенностей интерфейса ropeзаключается в том, что функции beginи endвсегда возвращают тип const_iterator. Это сделано для предотвращения операций, изменяющих отдельные символы. Такие операции обходятся слишком дорого. Контейнер ropeоптимизирован для операций с текстом в целом или большими фрагментами (присваивание, конкатенация и выделение подстроки); операции с отдельными символами выполняются неэффективно. • Различные нестандартные объекты функций и адаптеры. Некоторые классы функторов из исходной реализации HP STL не вошли в Стандарт C++. Опытным мастерам старой школы больше всего не хватает функторов select1stи select2nd, чрезвычайно удобных при работе с контейнерами mapи multimap. Функтор select1stвозвращает первый компонент объекта pair, а функтор select2ndвозвращает второй компонент объекта pair. Пример использования этих нестандартных шаблонов классов функторов: map<int, string> m; … // Вывод всех ключей map в cout transform(m.begin(), m.end(), ostream_iterator<int>(cout, "\n"), select1st<map<int, string>::value_type>()); // Создать вектор и скопировать в него // все ассоциированные значения из map vector<string> v; transform(m.begin(), m.end(), back_inserter(v), select2nd<map<int, string>::value_type>()); Как видите, функторы select1stи select2ndупрощают использование алгоритмов в ситуациях, где обычно приходится писать собственные циклы (см. совет 43). С другой стороны, вследствие нестандартности функторов вас могут обвинить в написании непереносимого и вдобавок плохо сопровождаемого кода (см. совет 47). Настоящих фанатов STL это нисколько не волнует. Они считают, что отсутствие select1stи select2ndв Стандарте само по себе является вопиющей несправедливостью. К числу нестандартных объектов функций, входящих в реализацию STL, также принадлежат объекты identity, project1st, project2nd, compose1и compose2. Информацию о них можно найти на сайте, хотя пример использования compose2приводился на с. 172 настоящей книги. Надеюсь, я убедил вас в том, что посещение web-сайта SGI принесет несомненную пользу. Реализация библиотеки от SGI выходит за рамки STL. Первоначально ставилась цель разработки полной реализации стандартной библиотеки C++ за исключением компонентов, унаследованных из C (предполагается, что у вас в распоряжении уже имеется стандартная библиотека C). По этой причине с сайта SGI также стоит получить реализацию библиотеки потоков ввода-вывода C++. Как следует ожидать, эта реализация хорошо интегрируется с реализацией STL от SGI, но при этом по быстродействию она превосходит многие аналогичные реализации, поставляемые с компиляторами C++. Сайт STLport Главная отличительная особенность STLport заключается в том, что эта модифицированная версия реализации STL от SGI (включая потоки ввода-вывода и т. д.) была перенесена более чем на 20 компиляторов. STLport, как и библиотека SGI, распространяется бесплатно. Если ваш код должен работать сразу на нескольких платформах, вы избавите себя от множества хлопот, если возьмете за основу унифицированную реализацию STLport и будете использовать ее со всеми компиляторами. Большинство изменений кода SGI в реализации STLport связано с улучшением переносимости, однако STLport является единственной известной мне реализацией, в которой предусмотрен «отладочный режим» для диагностики случаев неправильного использования STL — компилируемых, но приводящих к непредсказуемым последствиям во время работы программы. Например, в совете 30 распространенная ошибка записи за концом контейнера поясняется следующим примером: int transmogrify(int х); // Функция вычисляет некое новое значение // по переданному параметру х vector<int> values; … // Заполнение вектора values данными vector<int> results; transform(values.begin(), // Попытка записи за концом results! values.end(), results.end, transmogrify); Этот фрагмент компилируется, но во время выполнения работает непредсказуемо. Если вам повезет, проблемы возникнут при вызове transform, и отладка будет относительно элементарной. Гораздо хуже, если вызов transformиспортит данные где-то в другом месте адресного пространства, но это обнаружится лишь позднее. В этом случае определение причины порчи данных становится задачей — как бы выразиться? — весьма нетривиальной. Отладочный режим STLport значительно упрощает эту задачу. При выполнении приведенного выше вызова transformвыдается следующее сообщение (предполагается, что реализация STLport установлена в каталоге C:\STLport): C:\STLport\stlport\stl\debug\_iterator.h:265 STL assertion failure: _Dereferenceable(*this) На этом программа прекращает работу, поскольку в случае ошибки отладочный режим STLport вызывает abort. Если вы предпочитаете, чтобы вместо этого инициировалось исключение, STLport можно настроить и на этот режим. Честно говоря, приведенное сообщение об ошибке менее понятно, чем хотелось бы, а имя файла и номер строки относятся к внутренней проверке условия STL, а не к строке с вызовом transform, но это все же значительно лучше пропущенного вызова transformи последующих попыток разобраться в причинах разрушения структур данных. В отладочном режиме STLport остается лишь запустить программу-отладчик, вернуться по содержимому стека к написанному вами коду и определить, что же произошло. Строка, содержащая ошибку, обычно находится достаточно легко. Отладочный режим STLport распознает широкий спектр стандартных ошибок, в том числе передачу алгоритмам недопустимых интервалов, попытки чтения из пустого контейнера, передачу итератора одного контейнера в качестве аргумента функции другого контейнера и т. д. Волшебство основано на взаимном отслеживании итераторов и контейнеров. При наличии двух итераторов это позволяет проверить, принадлежат ли они одному контейнеру, а при модификации контейнера — определить, какие итераторы становятся недействительными. В отладочном режиме реализация STLport использует специальные реализации итераторов, поэтому итераторы vectorи stringявляются объектами классов, а не низкоуровневыми указателями. Таким образом, использование STLport и компиляция в отладочном режиме помогают убедиться в том, что ваша программа не игнорирует различия между указателями и итераторами для соответствующих типов контейнеров. Одной этой причины может оказаться достаточно для того, чтобы познакомиться с отладочным режимом STLport. Сайт Boost В 1997 году завершился процесс, приведший к появлению Международного стандарта C++. Многие участники были разочарованы тем, что возможности, за которые они выступали, не прошли окончательный отбор. Некоторые из этих участников были членами самого Комитета, поэтому они решили разработать основу для дополнения стандартной библиотеки во время второго круга стандартизации. Результатом их усилий стал сайт Boost, который был призван «предоставить бесплатные библиотеки C++. Основное внимание уделяется переносимым библиотекам, соответствующим Стандарту C++». За этой целью кроется конкретный мотив:
Иначе говоря, Boost предлагается в качестве механизма, помогающего отделить плевелы от зерен в области потенциальных дополнений стандартной библиотеки C++. Вполне достойная миссия, заслуживающая нашей благодарности. Также стоит обратить внимание на подборку библиотек, находящихся на сайте Boost. Я не стану описывать ее здесь хотя бы потому, что к моменту выхода книги на сайте наверняка появятся новые библиотеки. Для пользователей STL особый интерес представляют две библиотеки. Первая содержит шаблон shared_ptr, умный указатель с подсчетом ссылок, который в отличие от указателя auto_ptrиз стандартной библиотеки может храниться в контейнерах STL (см. совет 8). Библиотека умных указателей также содержит шаблон shared_array, умный указатель с подсчетом ссылок для работы динамическими массивами, но в совете 13 вместо динамических массивов рекомендуется использовать контейнеры vectorи string; надеюсь, приведенные аргументы покажутся вам убедительными. Поклонники STL также оценят богатый ассортимент библиотек, содержащих объекты функций и другие вспомогательные средства. В этих библиотеках заново спроектированы и реализованы некоторые концепции, заложенные в основу объектов функций и адаптеров STL, в результате чего были сняты некоторые искусственные ограничения, снижающие практическую полезность стандартных функторов. В частности, при попытках использовать bind2ndс функциями mem_funи mem_fun_ref(см. совет 41) для привязки объекта к параметрам функции класса выясняется, что при передаче параметра по ссылке код, скорее всего, компилироваться не будет. Аналогичный результат достигается использованием not1и not2с ptr_funи функцией, получающей параметр по ссылке. Причина в обоих случаях заключается в том, что в процессе специализации шаблона многие платформы STL генерируют «ссылку на ссылку», но в C++ такая конструкция запрещена (в настоящее время Комитет по стандартизации рассматривает возможность внесения изменений в Стандарт для решения этой проблемы). Пример проблемы «ссылки на ссылку»: class Widget { public: … int readStream(istream& stream); // Функции readStream … // параметр передается }; // по ссылке vector<Widget*> vw; … for_each( // Большинство платформ STL vw.begin(), vw.end(), // при этом вызове bind2nd(mem_fun(&Widget::readStream), cin) // пытается сгенерировать ); // ссылку на ссылку. //Фрагмент не компилируется! Объекты функций Boost решают эту и многие другие проблемы, а также значительно повышают выразительность объектов функций. Если вы интересуетесь потенциальными возможностями объектов функций STL и хотите познакомиться с ними поближе, поскорее посетите сайт Boost. Если объекты функций вас пугают и вы считаете, что они существуют только для умиротворения малочисленных апологетов Lisp, вынужденных программировать на C++, все равно посетите сайт Boost. Библиотеки объектов функций Boost важны, но они составляют лишь малую часть полезной информации, находящейся на сайте. |
|
||||||||||||||||||||||||||||||||||||||||
|
Главная | Контакты | Нашёл ошибку | Прислать материал | Добавить в избранное |
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
