Эффективное использование STL

• Нужно ли предотвратить перемещение существующих элементов при вставке или удалении? Если нужно, воздержитесь от использования блоковых контейнеров (совет 5).

• Должна ли структура памяти контейнера соответствовать правилам языка C? Если должна, остается лишь использовать vector (совет 16).

• Насколько критична скорость поиска? Если скорость поиска критична, рассмотрите хэшированные контейнеры (совет 25), сортированные векторы (совет 23) и стандартные ассоциативные контейнеры — вероятно, именно в таком порядке.

• Может ли в контейнере использоваться подсчет ссылок? Если подсчет ссылок вас не устраивает, держитесь подальше от string, поскольку многие реализации string построены на этом механизме (совет 13). Также следует избегать контейнера rope (совет 50). Конечно, средства для представления строк вам все же понадобятся — попробуйте использовать vector<char>.

• Потребуется ли транзакционная семантика для операций вставки и удаления? Иначе говоря, хотите ли вы обеспечить надежную отмену вставок и удалений? Если хотите, вам понадобится узловой контейнер. При использовании транзакционной семантики для многоэлементных (например, интервальных — см. совет 5) вставок следует выбрать list — единственный стандартный контейнер, обладающий этим свойством. Транзакционная семантика особенно важна при написании кода, безопасного по отношению к исключениям. Вообще говоря, транзакционная семантика реализуется и для блоковых контейнеров, но за это приходится расплачиваться быстродействием и усложнением кода. За дополнительной информацией обращайтесь к книге Саттера «Exceptional C++» [8].

• Нужно ли свести к минимуму количество недействительных итераторов, указателей и ссылок? Если нужно — выбирайте узловые контейнеры, поскольку в них операции вставки и удаления никогда не приводят к появлению недействительных итераторов, указателей и ссылок (если они не относятся к удаляемым элементам). В общем случае операции вставки и удаления в блоковых контейнерах могут привести к тому, что все итераторы, указатели и ссылки станут недействительными.

• Не подойдет ли вам последовательный контейнер с итераторами произвольного доступа, в котором указатели и ссылки на данные всегда остаются действительными, если из контейнера ничего не удаляется, а вставка производится только в конце? Ситуация весьма специфическая, но если вы с ней столкнетесь — выбирайте deque. Следует заметить, что итераторы deque могут стать недействительными, даже если вставка производится только в конце контейнера. Это единственный стандартный контейнер STL, у которого итераторы могут стать недействительными при действительных указателях и ссылках.

Вряд ли эти вопросы полностью исчерпывают тему. Например, в них не учитывается тот факт, что разные типы контейнеров используют разные стратегии выделения памяти (некоторые аспекты этих стратегий описаны в советах 10 и 14). Но и этот список наглядно показывает, что алгоритмическая сложность выполняемых операций — далеко не единственный критерий выбора. Бесспорно, она играет важную роль, но приходится учитывать и другие факторы.

При выборе контейнеров STL предоставляет довольно большое количество вариантов, а за пределами STL их оказывается еще больше. Прежде чем принимать окончательное решение, обязательно изучите все возможные варианты. «…Контейнер, используемый в большинстве случаев»? Я так не думаю.

Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода

Основным принципом STL является обобщение. Массивы обобщаются в контейнеры, параметризованные по типам хранящихся объектов. Функции обобщаются в алгоритмы, параметризованные по типам используемых итераторов. Указатели обобщаются в итераторы, параметризованные по типам объектов, на которые они указывают.

Но это лишь начало. Конкретные разновидности контейнеров обобщаются в категории (последовательные и ассоциативные), а похожие контейнеры наделяются сходными функциями. Стандартные блоковые контейнеры (совет 1) обладают итераторами произвольного доступа, тогда как стандартные узловые контейнеры (также описанные в совете 1) поддерживают двусторонние итераторы. Последовательные контейнеры поддерживают операции push_front и/или push_back, у ассоциативных контейнеров такие операции отсутствуют. В ассоциативных контейнерах реализованы функции lower_bound, upper_bound и equal_range, обладающие логарифмической сложностью, а в последовательных контейнерах их нет.

При таких тенденциях к обобщению возникает естественная мысль — последовать положительному примеру. Желание похвальное. Несомненно, им стоит руководствоваться при написании собственных контейнеров, итераторов и алгоритмов, но многие программисты пытаются добиться этой цели несколько иным способом. Вместо того чтобы ориентироваться на конкретный тип контейнера, они пытаются обобщить синтаксис так, чтобы в программе, например, использовался vector, но позднее его можно было бы заменить на deque или list без изменения кода, в котором этот контейнер используется. Иначе говоря, они пытаются писать контейнерно-независимый код. Подобные обобщения, какими бы благими намерениями они не были вызваны, почти всегда нежелательны.

Даже самый убежденный сторонник контейнерно-независимого кода вскоре осознает, что универсальный код, работающий как с последовательными, так и с ассоциативными контейнерами, особого смысла не имеет. Многие функции существуют только в контейнерах определенной категории; например, функции push_front и push_back поддерживаются только последовательными контейнерами; функции count и lower_bound — только ассоциативными контейнерами и т. д. Даже сигнатуры таких базовых операций, как insert и erase, зависят от категории. Например, в последовательном контейнере вставленный объект остается в исходной позиции, тогда как в ассоциативном контейнере он перемещается в позицию, соответствующую порядку сортировки данного контейнера. Или другой пример: форма erase, которой при вызове передается итератор, для последовательного контейнера возвращает новый итератор, но для ассоциативного контейнера не возвращается ничего (в совете 9 показано, как это обстоятельство влияет на программный код).

Допустим, вас посетила творческая мысль — написать код, который работал бы со всеми распространенными последовательными контейнерами: vector, deque и list. Разумеется, вам придется программировать в контексте общих возможностей этих контейнеров, а значит, функции reserve и capacity (совет 14) использовать нельзя, поскольку они не поддерживаются контейнерами deque и list. Присутствие list также означает, что вам придется отказаться от оператора [] и ограничиться двусторонними итераторами, что исключает алгоритмы, работающие с итераторами произвольного доступа — sort, stable_sort, partial_sort и nth_element (совет 31).

С другой стороны, исходное намерение поддерживать vector исключает функции push_front и pop_front; vector и deque исключают применение splice и реализацию sort внутри контейнера. Учитывая те ограничения, о которых говорилось выше, последний запрет означает, что для вашего «обобщенного последовательного контейнера» не удастся вызвать никакую форму sort.

Пока речь идет о вещах простых и очевидных. При нарушении любого из этих ограничений ваша программа не будет компилироваться по крайней мере для одного из контейнеров, которые вы намеревались поддерживать. Гораздо больше проблем возникнет с программами, которые будут компилироваться.

В разных последовательных контейнерах действуют разные правила недействительности итераторов, указателей и ссылок. Чтобы ваш код правильно работал с vector, deque и list, необходимо предположить, что любая операция, приводящая к появлению недействительных итераторов, указателей и ссылок в любом из этих контейнеров, приведет к тем же последствиям и в используемом контейнере. Отсюда следует, что после каждого вызова insert недействительным становится абсолютно все, поскольку deque::insert делает недействительными все итераторы, а из-за невозможности использования capacity приходится предполагать, что после операции vector::insert становятся недействительными все указатели и ссылки (как упоминается в совете 1, контейнер deque обладает уникальным свойством — в некоторых случаях его итераторы могут становиться недействительными с сохранением действительных указателей и ссылок). Аналогичные рассуждения приводят к выводу, что после каждого вызова erase все итераторы, указатели и ссылки также должны считаться недействительными.

Недостаточно? Данные контейнера не передаются через интерфейс C, поскольку данная возможность поддерживается только для vector (совет 16). Вы не сможете создать экземпляр контейнера с типом bool — как будет показано в совете 18, vector<bool> не всегда ведет себя как vector и никогда не хранит настоящие логические величины. Вы даже не можете рассчитывать на постоянное время вставки-удаления, характерное для list, поскольку в vector и deque эти операции выполняются с линейной сложностью.