Я смотрел на контейнеры STL и пытался понять, что они на самом деле представляют (т.е. используемую структуру данных), и двухстороннюю очередь остановил меня: сначала я подумал, что это двусвязный список, который позволит вставлять и удалять с обоих концов за постоянное время, но меня беспокоит обещание, сделанное оператором [], которое должно быть выполнено в постоянное время. В связанном списке произвольный доступ должен быть O (n), верно?
А если это динамический массив, как он может добавлять элементы за постоянное время? Следует отметить, что может произойти перераспределение, и что O (1) - это амортизированная стоимость , как для вектора .
Так что мне интересно, что это за структура, которая позволяет произвольный доступ в постоянное время, и в то же время никогда не нужно переезжать в новое место побольше.