Совет 1. Внимательно подходите к выбору контейнера

Совет 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Создание контейнера с Web-формой поиска

Из книги автора

Создание контейнера с Web-формой поиска Откроем Web-страницу index.htm в Блокноте, найдем созданный в главе 20 фрагмент кода, создающий Web-форму поиска, и удалим его. Вместо него мы вставим сразу после открывающего тега <BODY> код, приведенный в листинге 21.4. Листинг 21.4 <DIV


Создание контейнера с Web-формой поиска

Из книги автора

Создание контейнера с Web-формой поиска Откроем Web-страницу index.htm в Блокноте, найдем созданный в главе 20 фрагмент кода, создающий Web-форму поиска, и удалим его. Вместо него мы вставим сразу после открывающего тега <BODY> код, приведенный в листинге 21.4. Листинг 21.4 <DIV


Рекомендации по выбору товаров

Из книги автора

Рекомендации по выбору товаров Если на страницах каталога товаров разместить полезные для покупателей тексты, касающиеся данной товарной группы, это хорошо скажется на конверсии.Такой текст должен легко читаться, быть компактным, интересным и главное – полезным. В него


Рекомендации по выбору архитектуры: Classic или SuperServer?

Из книги автора

Рекомендации по выбору архитектуры: Classic или SuperServer? Прочитав предыдущий раздел, читатель может ощутить необходимость немедленно перейти на сервер InterBase с архитектурой Classic. Однако стоит побороть это иррациональное стремление и хорошенько все взвесить. Ведь нельзя


7.1. Перебор элементов контейнера

Из книги автора

7.1. Перебор элементов контейнера ПроблемаИмеется диапазон итераторов — скорее всего, из стандартного контейнера — и стандартные алгоритмы не удовлетворяют вашим требованиям, так что вам требуется выполнить итерации самостоятельно.РешениеДля доступа к элементам


7.2. Удаление объектов из контейнера

Из книги автора

7.2. Удаление объектов из контейнера ПроблемаТребуется удалить объекты из контейнера.РешениеДля удаления одного или диапазона элементов используйте метод контейнера erase или один из стандартных алгоритмов. Пример 7.2 показывает пару различных способов удаления элементов


11.3. Вычисление суммы и среднего значения элементов контейнера

Из книги автора

11.3. Вычисление суммы и среднего значения элементов контейнера ПроблемаТребуется вычислить сумму и среднее значение чисел, содержащихся в контейнере.РешениеДля расчета суммы можно использовать функцию accumulate из заголовочного файла <numeric> и затем разделить ее на


11.7. Инициализация контейнера случайными числами

Из книги автора

11.7. Инициализация контейнера случайными числами ПроблемаТребуется заполнить произвольный контейнер случайными числами.РешениеМожно использовать функции generate и generate_n из заголовочного файла <algorithm> совместно с функтором, возвращающим случайные числа. Пример 11.13


Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера

Из книги автора

Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера Контейнеры STL отличаются умом и сообразительностью. Они поддерживают итераторы для перебора как в прямом, так и в


Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели

Из книги автора

Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели Предположим, у нас имеется контейнер set, содержащий указатели string*, и мы пытаемся включить в него несколько новых элементов:set<string*> ssp; // ssp = "set of string ptrs"ssp.insert(new string("Anteater"));ssp.insert(new


ПИСЬМОНОСЕЦ: Внимательно и помногу смотреть телевизор

Из книги автора

ПИСЬМОНОСЕЦ: Внимательно и помногу смотреть телевизор Автор: Леонид Левкович-МаслюкКупив по дороге в институт очередной номер (№44 [616]) и начав читать его на одной из пар, я натолкнулся на статью Михаила Ваннаха «Bestiarum genus». У меня есть небольшое замечание по поводу


Рекомендации по выбору и установке мультимедийного проектора

Из книги автора

Рекомендации по выбору и установке мультимедийного проектора Если доска не предполагает встроенный проектор, то для эффектной и безопасной работы с ней рекомендуется использовать проектор с поддерживаемым разрешением не ниже XGA 1024?768 пикселов (точек) и световым потоком


Игорь Осколков Новогодние подарки — советы по выбору гаджетов

Из книги автора

Игорь Осколков Новогодние подарки — советы по выбору гаджетов Классическая поговорка Лучший подарок книга в современном мире обретает вторую жизнь. Книга, конечно, не бумажная, а электронная — так называемая читалка или e-book. За последний год они стали очень популярны,


Игорь Осколков Новогодние подарки — советы по выбору нетбуков и ноутбуков

Из книги автора

Игорь Осколков Новогодние подарки — советы по выбору нетбуков и ноутбуков Начну, как и прошлый раз, с небольшого лирического отступления. Не секрет, что ноутбуки одной модели могут разительно отличаться друг от друга по техническим характеристикам. Для нетбуков,


Игорь Осколков Новогодние подарки — советы по выбору телефонов и смартфонов

Из книги автора

Игорь Осколков Новогодние подарки — советы по выбору телефонов и смартфонов Для начала — небольшое лирическое отступление. В список наиболее предпочтительных для покупки устройств попали не только самые интересные новинки, которые появились в последние несколько


Рекомендации по выбору типа репозитория

Из книги автора

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