Как организована память в std::deque?

189

08 февраля 2018, 17:15

Для лучшего понимания устройства контейнеров решил их все реализовать. И вот столкнулся с проблемой на std::deque.Принцип двусвязной очереди понимаю, но не понимаю как устроена стдшная дека, а именно: как она может выполнять добавление элементов с обеих сторон за O(1) и при этом же иметь скорость произвольного доступа так же O(1). Все знакомые программисты говорят что стдшная дека реализована как двусвязный список, элементы в котором - блоки фиксированного размера, но тогда каким образом произвольный доступ O(1)?(как минимум, что-бы дойти до нужного блока я потрачу энное время). Вот такой вот вопрос.

Answer 1

Реализация std::deque не является секретом - ее можно посмотреть в сорцах. Но там немного мрак для неподготовленного человека. Но есть в картинках http://cpp-tip-of-the-day.blogspot.com/2013/11/how-is-stddeque-implemented.html

Если кратко - есть две реализации - вектора объединяются в связанный список и вектор векторов.

Вот на SO как раз и подтверждают, что реализации используют вектор векторов, причем внутренние вектора фиксированного размера.

А вот в переписке gcc обсуждают возможность использования циклического буфера.

и ещё немного картинок и текста - https://www.quora.com/What-is-a-possible-implementation-for-std-deque