deque тоже раскидан по памяти как list, или как vector?
Это лист векторов
Точно не вектор указателей на array?
а не подскажете, почему не сделали циклический буфер?
потому что это вектор или array c двумя индексами чтения и записи, пишите, увеличиваете индекс записи, корректируя по размеру вектора, читаете, увеличиваете индекс записи с точно такой же корректировкой
вот, это фактически push_front и pop_back, добавьте запись в r и чтение из w и получится push_back и pop_front - вот и deque, кмк
А причем кольцевой буфер что-то не уловил?
мне всегда казалось, что std::deque устроена примерно как кольцевой буфер
по моему все таки ето
Дека набор чанков фиксированной длины. Расширяется как слева так и справа. Какой же это кольцевой буфер?
я хочу сказать, это можно реализовать как кольцевой буфер, вы ведь можете писать в буфер и слева и справа, только в кольцевом буфере вы начинаете перетираеть старые значения, когда w "догоняет" r, а здесь можно сделать реаллокацию, как в векторе.
Реализация потребует большого оверхеда, там не амортизированная 1 в требованиях к добавлению в конец
Натянул сову на глобус
понятно, спасибо за объяснение!
https://www.quora.com/What-is-a-possible-implementation-for-std-deque кстати, тут указывают причину, что кольцевой буфер не подходит, потому что при вставке могут инвалидироваться ссылки
Обсуждают сегодня