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

Мейерс Скотт
Шрифт:

• Нестандартные ассоциативные контейнеры:

hash_set, hash_multiset
,
hash_ map
и
hash_multimap
. Эти популярные разновидности стандартных ассоциативных контейнеров, построенные на базе хэш-таблиц, рассматриваются в совете 25.

• 

vector<char>
как замена для
string
. Условия, при которых возможна подобная замена, описаны в совете 13.

• 

vector
как замена для стандартных ассоциативных контейнеров. Как будет показано в совете 23, в некоторых ситуациях
vector
превосходит стандартные ассоциативные контейнеры как по быстродействию, так и по экономии памяти.

• Некоторые стандартные контейнеры, не входящие в STL: массивы,

bitset
,
valarray
,
stack
,
queue
и
piority_queue
. Поскольку эти контейнеры не относятся к STL, в этой книге они практически не упоминаются, хотя в совете 16 описан случай, когда массив оказывается предпочтительнее контейнеров SQL, а в совете 18 объясняется, почему
bitset
может быть лучше
vector<bool>
. Также стоит помнить о возможности использования массивов с алгоритмами STL, поскольку указатели могут работать как итераторы массивов.

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

vector, deque
и
list
на основании следующих критериев: «…
vector, list
и
deque
обладают различными характеристиками в зависимости от класса выполняемых операций, в соответствии с которыми должен осуществляться выбор. Вектор (
vector
) представляет собой тип последовательного контейнера, который используется в большинстве случаев. Список (
list
) используется при частых операциях вставки и удаления в произвольной позиции. Дек (
deque
) выбирается в случае, если большинство вставок и удалений производится в начале или в конце последовательности элементов».

Если ограничиться алгоритмической сложностью, эта рекомендация звучит вполне разумно, но на практике приходится учитывать множество других факторов.

Вскоре мы рассмотрим некоторые факторы, учитываемые в дополнение к алгоритмической сложности, но сначала я должен представить критерий классификации контейнеров STL, которому, к сожалению, обычно не уделяется должного внимания. Речь идет о различиях между контейнерами с блоковым и узловым выделением памяти.

В блоковых контейнерах (также называемых контейнерами со смежной памятью) элементы хранятся в одном или нескольких динамически выделяемых блоках памяти, по несколько элементов в каждом блоке. При вставке нового или удалении существующего элемента другие элементы того же блока сдвигаются вверх или вниз, освобождая место для нового элемента или заполняя место, ранее занимаемое удаленным элементом. Подобные перемещения влияют как на скорость работы (советы 5 и 14), так и на безопасность (об этом — ниже). К числу стандартных блоковых контейнеров относятся

vector
,
string
и
deque
. Нестандартный контейнер
rope
также является блоковым.

В узловых контейнерах каждый динамически выделенный фрагмент содержит ровно один элемент. Операции удаления и вставки выполняются только с указателями на узлы, не затрагивая содержимого самих узлов, и потому обходятся без перемещений данных в памяти. К этой категории относятся контейнеры связанных списков (такие как

list
и
slist
), а также все стандартные ассоциативные контейнеры, обычно реализуемые в форме сбалансированных деревьев. Как будет показано в совете 25, реализация нестандартных хэшированных контейнеров тоже построена на узловом принципе.

Разобравшись с терминологией, можно переходить к анализу факторов, учитываемых при выборе контейнера. В дальнейшем описании не учитываются контейнеры, не входящие в STL (массивы, битовые множества и т. д.), поскольку книга все-таки посвящена STL.

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

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

• Должен ли контейнер входить в число стандартных контейнеров C++? Если выбор ограничивается стандартными контейнерами, то хэшированные контейнеры,

slist
и
rope
, исключаются.

• К какой категории должны относиться итераторы? С технической точки зрения итераторы произвольного доступа ограничивают ваш выбор контейнерами

vector, deque
и
string
, хотя, в принципе, можно рассмотреть и возможность применения
rope
(этот контейнер рассматривается в совете 50). Если нужны двусторонние итераторы, исключается класс slist (совет 50) и одна распространенная реализация хэшированных контейнеров (совет 25).

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

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

vector
(совет 16).

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