На этом шаге мы перечислим особенности деков.
По своим возможностям деки во многом отличаются от векторов.
- Вставка и удаление выполняются быстро как в начале, так и в конце (для векторов эти операции выполняются быстро только в конце). Операции выполняются с амортизированным постоянным временем.
- Внутренняя структура содержит дополнительный уровень ссылок, поэтому обращение к элементам и перемещение итератора в деках обычно выполняются чуть медленнее.
- Итераторы должны быть умными указателями особого типа. Обычные указатели не подходят из-за необходимости перехода между блоками.
- В системах с ограниченными размерами блоков памяти (например, в некоторых системах PC) дек может содержать больше элементов, поскольку он не ограничивается одним блоком памяти. Следовательно, функция max_size() может возвращать для деков большую величину.
- Деки не позволяют управлять емкостью и моментом перераспределения памяти. В частности, при любых операциях вставки и удаления, выполняемых не в начале или конце вектора, становятся недействительными все указатели, ссылки и итераторы, ссылающиеся на элементы дека. Однако перераспределение памяти в общем случае выполняется более эффективно, чем для векторов, потому что из-за особенностей своей внутренней структуры декам не приходится копировать все элементы.
- Освобождение неиспользуемых блоков может привести к уменьшению объема памяти, занимаемой деком (хотя как это происходит и происходит ли вообще, зависит от реализации). Следующие особенности векторов характерны также и для деков.
- Вставка и удаление элементов в середине контейнера выполняется относительно медленно, потому что для освобождения места или заполнения пропуска приходится перемещать элементы с обоих концов.
- Итераторы являются итераторами произвольного доступа.
Подведем итог. Выбирайте дек, если выполняются следующие условия:
- вставка элементов выполняется с обоих концов (классический пример очереди);
- в программе не используются ссылки на элементы контейнера;
- важно, чтобы контейнер освобождал неиспользуемую память (хотя стандарт таких гарантий не дает).
Интерфейс векторов и деков почти не отличается. Если в программе не используются специфические возможности вектора или дека, вы можете легко опробовать оба контейнера.
На следующем шаге мы рассмотрим операции над деками.
