Deque против вектора в C ++ STL
Deque в стандартной библиотеке шаблонов C ++ (STL)
Двусторонние очереди - это контейнеры последовательности с функцией расширения и сжатия на обоих концах.
Они похожи на векторы, но более эффективны при вставке и удалении элементов. В отличие от векторов, непрерывное выделение памяти не может быть гарантировано.
Двусторонние очереди - это в основном реализация двусторонней очереди структуры данных. Структура данных очереди допускает вставку только в конце и удаление спереди. Это похоже на очередь в реальной жизни, в которой людей убирают спереди и добавляют сзади. Двусторонние очереди - это особый случай очередей, в которых операции вставки и удаления возможны на обоих концах.
Функции для deque такие же, как для вектора, с добавлением операций push и pop как для передней, так и для обратной стороны.
Вектор в C ++ STL
Векторы такие же, как динамические массивы, с возможностью автоматического изменения размера при вставке или удалении элемента, а их хранение автоматически обрабатывается контейнером. Элементы вектора помещаются в непрерывное хранилище, чтобы к ним можно было получить доступ и пройти с помощью итераторов. В векторах данные вставляются в конце. Вставка в конце занимает разное время, так как иногда может возникнуть необходимость в расширении массива. Удаление последнего элемента занимает только постоянное время, потому что изменение размера не происходит. Вставка и стирание в начале или в середине линейны во времени.
Разница между Deque и Vector:
| Вектор | Deque |
|---|---|
| Предоставляет методы вставки и удаления в середине и конце | Предоставляет методы вставки и удаления в середине, конце, начале |
| Плохая производительность при вставке и удалении спереди | Хорошая производительность для вставки и удаления спереди |
| Хранит элементы непрерывно | Он содержит списки блоков памяти, в которых элементы хранятся непрерывно. |
| Хорошая производительность для добавления и удаления элементов в конце | Низкая производительность при добавлении и удалении элементов в конце |
Когда мы должны выбрать Deque вместо Vector?
Мы должны выбрать Deque, когда наши операции добавляют и удаляют элементы в начале и в конце (двусторонняя очередь ADT).