О дополнительном обращении deque <T> - PullRequest
Новая
       45

О дополнительном обращении deque <T>

6 голосов
/ 29 ноября 2011

Удивляясь, почему мои обращения к памяти были несколько медленнее, чем я ожидал, я наконец-то понял, что реализация deque в Visual C ++ действительно имеет встроенный слой косвенной адресации extra , разрушающий мою память.

т.е. похоже, он содержит массив T*, а не массив T.

Есть ли другая реализация, которую я могу использовать с VC ++, у которой нет этой "функции", или есть какой-то способ (хотя я считаю это маловероятным), чтобы избежать ее в этой реализации?

Я в основном ищу vector, который также имеет O (1) push / pop спереди.
Думаю, я мог бы реализовать это сам, но иметь дело с allocator s и так сложно, и чтобы разобраться с этим потребовалось бы некоторое время, поэтому я бы предпочел использовать что-то ранее написанное / протестированное, если это возможно.

Ответы [ 3 ]

10 голосов
/ 29 ноября 2011

По любой причине, по крайней мере, начиная с MSVC 2010, реализация std::deque использует невероятно маленький размер блока (максимум 16 байтов или 1 отдельный элемент, если я не ошибаюсь!).

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

Я не знаю, почему это так.Насколько я понимаю, установка deque с таким маленьким размером блока - это именно то, что , а не должно быть сделано.

Проверьте реализацию gcc stdlib.Из памяти они используют гораздо больший размер блока.

РЕДАКТИРОВАТЬ: В попытке решить другие проблемы:

  • std::deque должен иметьдополнительный слой косвенности.Он часто реализуется как «заблокированная» структура данных - то есть хранит массив «узлов», где каждый узел сам является массивом элементов данных.Он никогда не похож на связанный список - массив узлов никогда не «пересекается», как список, он всегда напрямую индексируется (даже в случае 1 элемента на блок).

  • Конечно, вы можете свернуть свою собственную структуру данных, которая оставляет некоторое дополнительное пространство впереди.Он не будет работать в худшем случае O(1) push/pop front/back и как таковой не будет удовлетворять требованиям контейнера std::deque.Но если тебя это не волнует ...

2 голосов
/ 29 ноября 2011

Стандарт C ++ не позволяет std::deque выполнять перераспределения при толчках вперед или назад.Эти операции всегда постоянны.Не амортизируется , всегда .

Стандарт C ++ не имеет такого контейнера.Насколько я знаю, у Boost нет (подумал, что библиотека Boost.Container может; я не смотрел на это).

0 голосов
/ 29 ноября 2011

Направленность, на которую вы жалуетесь, на самом деле обязательна стандартным требованием, что ссылки / указатели никогда не аннулируются push / pop front / back (за исключением тех ссылок / указателей на удалены элементы, очевидно).

Итак, вы видите, что это требование не имеет ничего общего с требованием сложности.

Эта косвенность также позволяет быстрее (но все равно O (размер)) push front / back, когда нет свободного места.

...