Реализована ли STL deque как круговой связанный список?

Question

Я не могу найти внутреннюю информацию о том, как deque реализован в C ++ STL.

Я читал где-то ранее, что в C # это реализовано в виде циклического списка. верно ли это и для C ++ STL? Кроме того, не могли бы вы объяснить, почему это так?

РЕДАКТИРОВАТЬ: под C ++ STL я имею в виду библиотеку STL, которая поставляется с Visual studio C ++ 2010, а также библиотеку, которая поставляется вместе с gcc

Answer 1

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

В большинстве реализаций (включая VC ++ и, вероятно, также gcc) это в основном массивуказатели на блоки данных.Когда вы добавляете данные, обычно они просто добавляются в существующий блок данных.Когда существующие блоки заполняются, он выделяет новый, добавляет его в конец массива, куда вы вставляете, и затем добавляет в него ваши данные.Когда / если базовому массиву не хватает места, он выделяет новый и копирует туда указатели.

Answer 2

Стандарт C ++ требует, чтобы у deque было постоянное время случайного поиска. Круговой связанный список не соответствует требованию.

Answer 3

Реализация deque должна обеспечивать

1. произвольный доступ к его элементам в постоянном времени
2. постоянное время вставки и удаления в конце
3. постоянное время вставки и удаления в начале

(1) исключает любые виды связанных списков, включая циклические списки

(2) & (3) исключают простой кусок памяти, в котором хранятся элементы.

ПРИМЕЧАНИЕ: действующий стандарт ('03) действительно гласит постоянное время , а не амортизированное постоянное время для (2) и (3) (см. 23.2.1/1), однако я думаю, что это упущение. Я не знаю, как сделать все три в постоянное время . Если это только постоянное время для (1) и постоянное время амортизации для (2) и (3), то это довольно просто.

AFAIK MSVC deque использует кольцевой буфер указателей на страницы элементов. Думайте о кольцевом буфере как о массиве (vector) со смещением + циклический переход. А страница содержит небольшое количество элементов (IIRC не более 8), в зависимости от sizeof(element). Кольцевой буфер увеличивается как std::vector, если требуется больше места (и именно здесь вам нужно амортизированное постоянное время вместо постоянное время ).

Я думаю, что другие реализации (GCC, ...) будут очень похожи.

Кстати: в стандарте также есть пункт, который делает невозможным использование только одного большого кольцевого буфера элементов без «указателя указателя». 23.2.1.3/1 говорит, что вставка в начале или конце не делает недействительными ссылки на элементы в deque. Понятно, что это невозможно, если структура, содержащая сами элементы, должна быть перераспределена, когда она выходит за пределы зарезервированного пространства. Это потребует простой кольцевой буфер, поэтому его нельзя использовать.

Answer 4

STL - это спецификация, а не реализация. Спецификация не устанавливает никаких требований к как поведение должно быть реализовано (при условии, что оно подчиняется определенному интерфейсу).