•>vector как замена для >string. Условия, при которых возможна подобная замена, описаны в совете 13.
•>vector как замена для стандартных ассоциативных контейнеров. Как будет показано в совете 23, в некоторых ситуациях >vector превосходит стандартные ассоциативные контейнеры как по быстродействию, так и по экономии памяти.
•Некоторые стандартные контейнеры, не входящие в STL: массивы, >bitset, >valarray, >stack, >queue и >piority_queue. Поскольку эти контейнеры не относятся к STL, в этой книге они практически не упоминаются, хотя в совете 16 описан случай, когда массив оказывается предпочтительнее контейнеров SQL, а в совете 18 объясняется, почему >bitset может быть лучше >vector. Также стоит помнить о возможности использования массивов с алгоритмами STL, поскольку указатели могут работать как итераторы массивов.
При столь широком ассортименте контейнеров возрастает и количество факторов, которыми следует руководствоваться при их выборе. К сожалению, многие описания STL ограничиваются поверхностным взглядом на мир контейнеров и полностью игнорируют многие факторы, относящиеся к выбору оптимального контейнера. Этот недостаток присущ даже Стандарту, который предлагает выбирать между >vector, deque и >list на основании следующих критериев: «...>vector, list и >deque обладают различными характеристиками в зависимости от класса выполняемых операций, в соответствии с которыми должен осуществляться выбор. Вектор (>vector) представляет собой тип последовательного контейнера, который используется в большинстве случаев. Список (>list) используется при частых операциях вставки и удаления в произвольной позиции. Дек (>deque) выбирается в случае, если большинство вставок и удалений производится в начале или в конце последовательности элементов».
Если ограничиться алгоритмической сложностью, эта рекомендация звучит вполне разумно, но на практике приходится учитывать множество других факторов.
Вскоре мы рассмотрим некоторые факторы, учитываемые в дополнение к алгоритмической сложности, но сначала я должен представить критерий классификации контейнеров STL, которому, к сожалению, обычно не уделяется должного внимания. Речь идет о различиях между контейнерами с блоковым и узловым выделением памяти.
В блоковых контейнерах (также называемых контейнерами со смежной памятью) элементы хранятся в одном или нескольких динамически выделяемых блоках памяти, по несколько элементов в каждом блоке. При вставке нового или удалении существующего элемента другие элементы того же блока сдвигаются вверх или вниз, освобождая место для нового элемента или заполняя место, ранее занимаемое удаленным элементом. Подобные перемещения влияют как на скорость работы (советы 5 и 14), так и на безопасность (об этом — ниже). К числу стандартных блоковых контейнеров относятся
