Контейнеры STL. Возможности деков

   
На этом шаге мы перечислим особенности деков.

   
По своим возможностям деки во многом отличаются от векторов.

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

   
Подведем итог. Выбирайте дек, если выполняются следующие условия:

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

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

   
На следующем шаге мы рассмотрим операции над деками.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий