Скотт Мейерс - Эффективное использование STL
Контейнеры
В STL входит немало полезных компонентов (в том числе итераторы, алгоритмы и объекты функций), однако большинство программистов C++ ставит на первое место именно контейнеры. По сравнению с массивами контейнеры обладают большей гибкостью и функциональностью. Они динамически увеличивают (а иногда и уменьшают) свои размеры, самостоятельно управляют памятью, следят за количеством хранящихся объектов, ограничивают алгоритмическую сложность поддерживаемых операций и обладают массой других достоинств. Популярность контейнеров STL легко объяснима — просто они превосходят своих конкурентов, будь то контейнеры из других библиотек или самостоятельные реализации. Контейнеры STL не просто хороши. Они действительно хороши.
В этой главе приведены общие сведения, относящиеся ко всем типам контейнеров STL (конкретные типы контейнеров будут рассмотрены в других главах). В частности, мы рассмотрим такие вопросы, как выбор подходящего контейнера при заданных ограничениях; возможность работы кода, написанного для одного типа контейнера, с другими типами контейнеров; особая роль операций копирования объектов в контейнерах; проблемы, возникающие при создании контейнеров с указателями auto_ptr; нюансы, связанные с удалением элементов; оптимизация работы с контейнерами и замечания относительно работы контейнеров в многопоточной среде.
Список получился внушительным, но пусть вас это не пугает. Материал излагается небольшими порциями, а попутно вы встретите немало полезных идей, которые сможете немедленно применить в своих программах.
Итак, STL предоставляет в ваше распоряжение множество разных контейнеров, но знаете ли вы, насколько широко это разнообразие? Следующая краткая сводка поможет вам убедиться в том, что вы ни о чем не забыли.
Совет 1. Внимательно подходите к выбору контейнера
• Стандартные последовательные контейнеры STL: vector, string, deque и list.
• Стандартные ассоциативные контейнеры STL: set, multiset, map и multimap.
• Нестандартные последовательные контейнеры: slist и rope. Контейнер slist представляет односвязный список, а rope — строку с дополнительными возможностями. Краткий обзор этих нестандартных (но достаточно широко распространенных) контейнеров приведен в совете 50.
• Нестандартные ассоциативные контейнеры: 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) и стандартные ассоциативные контейнеры — вероятно, именно в таком порядке.
• Может ли в контейнере использоваться подсчет ссылок? Если подсчет ссылок вас не устраивает, держитесь подальше от string, поскольку многие реализации string построены на этом механизме (совет 13). Также следует избегать контейнера rope (совет 50). Конечно, средства для представления строк вам все же понадобятся — попробуйте использовать vector<char>.
• Потребуется ли транзакционная семантика для операций вставки и удаления? Иначе говоря, хотите ли вы обеспечить надежную отмену вставок и удалений? Если хотите, вам понадобится узловой контейнер. При использовании транзакционной семантики для многоэлементных (например, интервальных — см. совет 5) вставок следует выбрать list — единственный стандартный контейнер, обладающий этим свойством. Транзакционная семантика особенно важна при написании кода, безопасного по отношению к исключениям. Вообще говоря, транзакционная семантика реализуется и для блоковых контейнеров, но за это приходится расплачиваться быстродействием и усложнением кода. За дополнительной информацией обращайтесь к книге Саттера «Exceptional C++» [8].
