все возможные варианты. «...Контейнер, используемый в большинстве случаев»? Я так не думаю.
Совет 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
, patial_sort
и nth_element
(совет 31).С другой стороны, исходное намерение поддерживать
vector
исключает функции pushfront
и popfont
; vector
и deque
исключают применение splice
и реализацию sort
внутри контейнера. Учитывая те ограничения, о которых говорилось выше, последний запрет означает, что для вашего «обобщенного последовательного контейнера» не удастся вызвать никакую форму sort
.Пока речь идет о вещах простых и очевидных. При нарушении любого из этих ограничений ваша программа не будет компилироваться по крайней мере для одного из контейнеров, которые вы намеревались поддерживать. Гораздо больше проблем возникнет с программами, которые будут компилироваться.
В разных последовательных контейнерах действуют разные правила недействительности итераторов, указателей и ссылок. Чтобы ваш код правильно работал с
vector
, deque
и list
, необходимо предположить, что любая операция, приводящая к появлению недействительных итераторов, указателей и ссылок в любом из этих контейнеров, приведет к тем же последствиям и в используемом контейнере. Отсюда следует, что после каждого вызова insert
недействительным становится абсолютно все, поскольку deque:: insert
делает недействительными все итераторы, а из-за невозможности использования capacity
приходится предполагать, что после операции vector:: insert
становятся недействительными все указатели и ссылки (как упоминается в совете 1, контейнер deque
обладает уникальным свойством — в некоторых случаях его итераторы могут становиться недействительными с сохранением действительных указателей и ссылок). Аналогичные рассуждения приводят к выводу, что после каждого вызова erase
все итераторы, указатели и ссылки также должны считаться недействительными.Недостаточно? Данные контейнера не передаются через интерфейс С, поскольку данная возможность поддерживается только для
vector
(совет 16). Вы не сможете создать экземпляр контейнера с типом bool
— как будет показано в совете 18, vector
не всегда ведет себя как vector
и никогда не хранит настоящие логические величины. Вы даже не можете рассчитывать на постоянное время вставки-удаления, характерное для list
, поскольку в vector
и deque
эти операции выполняются с линейной сложностью.Что же остается после всего сказанного? «Обобщенный последовательный контейнер», в котором нельзя использовать
reserve
, capacity
, operator[], push_front, pop_front, splice
и вообще любой алгоритм, работающий с итераторами произвольного доступа; контейнер, у которого любой вызов insert
и erase
выполняется с линейной сложностью и приводит к недействительности всех итераторов, указателей и ссылок; контейнер, несовместимый с языком С и не позволяющий хранить логические величины. Захочется ли вам использовать подобный контейнер в своем приложении? Вряд ли.Если умерить амбиции и отказаться от поддержки
list
, вы все равно теряете reserve
, capacity
, push_front
и pop_front
; вам также придется полагать, что вызовы insert
и erase
выполняются с линейной сложностью, а все итераторы, указатели и ссылки становятся недействительными; вы все равно теряете совместимость с С и не можете хранить в контейнере логические величины.Даже если отказаться от последовательных контейнеров и взяться за ассоциативные контейнеры, дело обстоит не лучше. Написать код, который бы одновременно работал с
set
и map
, практически невозможно, поскольку в set
хранятся одиночные объекты, а в map
хранятся пары объектов. Даже совместимость с set
и multiset
(или map
и multimap
) обеспечивается с большим трудом. Функция insert
, которой при вызове передается только значение вставляемого элемента, возвращает разные типы для set/map
и их multi-аналогов, при этом вы должны избегать любых допущений относительно того, сколько экземпляров данной величины хранится в контейнере. При работе с map
и multimap
приходится обходиться без оператора [ ], поскольку эта функция существует только в map
.Согласитесь, игра не стоит свеч. Контейнеры действительно отличаются друг от друга, обладают разными достоинствами и недостатками. Они не были рассчитаны на взаимозаменяемость, и с этим фактом остается только смириться. Любые попытки лишь искушают судьбу, а она этого не любит.
Но рано или поздно наступит день, когда окажется, что первоначальный выбор контейнера был, мягко говоря, не оптимальным, и вы захотите переключиться на другой тип. При изменении типа контейнера нужно не только исправить ошибки, обнаруженные компилятором, но и проанализировать весь код, где он используется, и разобраться, что следует изменить в свете характеристик нового контейнера и правил перехода итераторов, указателей и ссылок в недействительное состояние. Переходя с