std::deque - произвольный доступ
Оказывается есть произвольный, а есть последовательный доступ через итераторы.
К примеру итераторы на std::vector и std::deque - поддерживают итераторы с произвольным доступом. Итераторы std::list - только с произвольным.
С std::vector - понятно - все элементы - располагаются непрерывно в памяти.
Тепер понятно и с std::list - это список с произвольным расположением в памяти, который содержит указатель на предыдущий и последующий элементы - отсюда и последовательный доступ.
Но, если std::deque - точно так же, как и std::vector - поддерживает произвольный доступ - то чем он отличается от std::vector ?
Ответы (1 шт):
Главное отличие deque от vector - возможность О(1) вставки-удаления не только в конец, но и в начало (в отличие от О(n) для вектора - из-за необходисости полностью перемещать все данные).
Цена этого - то, что дек работает немного медленнее, и все свои данные НЕ хранит последовательно одним блоком в памяти.
P.S. Понравилась диаграмма он Harry, я ее тут добавлю.
