Реализация C++ std::deque: почему бы не использовать циклический буфер?

Я провел поиск по реализации deque. Согласно этот пост, deque использует вектор векторов. Я знаю, что нажатие в начале и в конце должно быть как в постоянное время, так и в произвольном доступе. Я думаю, что кольцевой буфер отвечает всем этим требованиям и намного проще. Так почему бы не использовать циклический буфер?

Я также нашел циклический буфер ускорения. Как это сравнивается с деком?

Изменить: хорошо, значит, это как-то связано с правилами аннулирования итераторов. В нем говорится:

все итераторы и ссылки становятся недействительными, если только вставленный элемент не находится в конце (впереди или сзади) двухсторонней очереди (в этом случае все итераторы становятся недействительными, но ссылки на элементы не затрагиваются)

Я понимаю, что для перегрузки оператора, такого как iter++, итераторы должны владеть указателем на карту узлов и указателем на фрагмент, поэтому, если карта узлов перераспределена, итератор становится недействительным. Но поскольку данные никогда не перемещаются, ссылки по-прежнему действительны.


c++ stl circular-buffer deque
person sunnior    schedule 27.10.2016    source источник
comment
Циклический буфер накладывает некоторый верхний предел на размер двухсторонней очереди. Как указано, у deque нет верхнего предела размера.   -  person Sam Varshavchik    schedule 27.10.2016
comment
Что вы ожидаете от краткого и окончательного ответа здесь? Stack Overflow — это не дискуссионный форум.   -  person πάντα ῥεῖ    schedule 27.10.2016
comment
Что происходит, когда ваш кольцевой буфер заполнен, и вы добавляете другой элемент?   -  person TartanLlama    schedule 27.10.2016
comment
@TartanLlama, как насчет перераспределения, как это делает вектор?   -  person sunnior    schedule 27.10.2016
comment
@sunnior, тогда вы аннулируете все итераторы и должны скопировать/переместить все существующие элементы.   -  person TartanLlama    schedule 27.10.2016
comment
Одним из ключевых свойств std::deque является то, что вы никогда не сделаете недействительными итераторы и ссылки при добавлении или удалении элементов с любого конца. С круговым буфером такого не будет.   -  person Galik    schedule 27.10.2016
comment
О, я вижу. это требование, которое я пропускаю ~ спасибо, ребята.   -  person sunnior    schedule 27.10.2016
comment
Хотя я думаю, что @sunnior имеет в этом какой-то смысл; Я не понимаю, почему deque не может использовать вектор колец. Это было бы не намного сложнее реализовать, чем вектор векторов, и это позволило бы контейнеру никогда не выделять память, если общее количество элементов никогда не превышает размер кольца.   -  person Andrey Turkin    schedule 27.10.2016
comment
@AndreyTurkin, я думаю, что когда дека заполнена, голова и хвост, вероятно, находятся в одном кольце. вы не можете переместить их, чтобы вставить новый фрагмент. и, кстати, чанк маленький, поэтому я думаю, что они не будут волноваться, если чанк не заполнен.   -  person sunnior    schedule 27.10.2016
comment
Отсюда вектор колец. Как только кольцо заполнится, выделите другое и начните его использовать; так же, как это делается сейчас с вектором. Кольца должны давать некоторый выигрыш, если количество элементов, хранящихся в deque, невелико, но скорость вставки/удаления высока (например, FIFO), потому что не нужно будет выделять новые векторы каждые N вставок.   -  person Andrey Turkin    schedule 27.10.2016
comment
@AndreyTurkin, о, я вижу. но я думаю, что одним недостатком является необходимость дополнительного хранилища и процедуры для обработки всех этих орлов (хвостов)~, и я думаю, что это также увеличивает вероятность промаха кеша, потому что данные начальных и хвостовых данных хранятся в одном кольце, данные довольно фрагментирован.   -  person sunnior    schedule 27.10.2016
comment
Договорились о некоторых накладных расходах. Не вижу, как это может увеличить промахи кеша; он почти такой же непрерывный и последовательный, как вектор. Во всяком случае, в некоторых случаях это может улучшить локальность кеша (опять же, FIFO с небольшим количеством элементов). В любом случае, давайте закроем эту дискуссию, поскольку она бессмысленна :). Некоторым (я надеюсь) гораздо более умным людям, чем я, пришлось приложить много усилий для разработки реализации deque, и они должны были прийти к похожей идее, протестировать ее (надеюсь) и отвергнуть.   -  person Andrey Turkin    schedule 27.10.2016

Ответы (1)


arrow_upward
3
arrow_downward

Циклический буфер не может расширяться бесконечно. В конце концов, вам нужно выделить новый и скопировать все элементы.

Дек может просто выделить новый вектор перед предыдущими и добавить туда «средний» элемент. Я думаю об этом скорее как о списке векторов.

person Macke    schedule 26.03.2019