Класс deque
Упорядочивает элементы заданного типа в линейном порядке и, подобно векторам, обеспечивает быстрый произвольный доступ к любому элементу и эффективную вставку и удаление в конце контейнера. Однако в отличие от объекта vector класс deque также поддерживает эффективную вставку и удаление в передней части контейнера.
Синтаксис
Параметры
Тип
Тип данных элементов, сохраняемых в объекте deque.
Выделен
Тип, представляющий сохраненный объект распределителя, содержащий сведения о распределении и отмене распределения памяти для deque. Этот аргумент является необязательным, и значение по умолчанию — > Тип распределителя.
Комментарии
Выбор типа контейнера должен в общем случае производиться на основе типа поиска и вставки, который требуется приложению. Векторы должны быть предпочтительными контейнерами для управления последовательностью, когда произвольный доступ к любому элементу имеет уровень Premium, а вставки или удаления элементов требуются только в конце последовательности. Производительность контейнера list выше, если эффективные вставки и удаления (в константном времени) в любом расположении в последовательности имеют больший приоритет. Таким операциям в середине последовательности требуются копии элементов и присвоения, пропорциональные количеству элементов в последовательности (линейное время).
Перераспределение объекта deque происходит, когда функция-член должна вставить или удалить элементы последовательности:
Если элемент вставляется в пустую последовательность или элемент удаляется, чтобы оставить после себя пустую последовательность, то итераторы, ранее возвращенные begin и end, становятся недействительными.
Если элемент вставляется в первую позицию deque, то все итераторы, но не ссылки, которые определяют существующие элементы, становятся недействительными.
Если элемент вставляется в последнюю позицию очереди, то end и все итераторы, но не ссылки, которые определяют существующие элементы, становятся недействительными.
Если элемент удаляется в передней части объекта deque, только этот итератор и ссылки на удаленный элемент становятся недействительными.
Если последний элемент удаляется из конца объекта deque, только этот итератор последнего элемента и ссылки на удаленный элемент становятся недействительными.
В противном случае вставка или удаление элемента делает недействительными все итераторы и ссылки.
Члены
Конструкторы
Определения типов
Функции
Операторы
allocator_type
Тип, представляющий класс allocator для объекта deque.
Комментарии
Пример
assign
Удаляет элементы из очереди и копирует новый набор элементов в целевую очередь.
Параметры
Первая
Положение первого элемента в диапазоне элементов, копируемых из очереди аргументов.
Последняя
Положение первого элемента за пределами диапазона элементов, копируемых из очереди аргументов.
Количество
Количество копий элемента, вставляемых в очередь.
Val
Значение элемента, вставляемого в очередь.
IList
Объект initializer_list, вставляемый в очередь.
Комментарии
После удаления любых существующих элементов в целевой очереди assign либо вставляет указанный диапазон элементов из исходной очереди или какой-либо другой очереди в целевую очередь, либо вставляет копии нового элемента указанного значения в целевую очередь.
Пример
Возвращает ссылку на элемент в заданном положении в очереди.
Параметры
pos
Нижний индекс (или номер позиции) элемента, на который включается ссылка в очереди.
Возвращаемое значение
Если значение POS превышает размер deque, вызывается исключение.
Комментарии
Пример
Назад
Возвращает ссылку на последний элемент очереди.
Возвращаемое значение
Последний элемент очереди. Если очередь пуста, возвращаемое значение не определено.
Комментарии
При компиляции с помощью _ITERATOR_DEBUG_LEVEL, для которого задано значение 1 или 2, возникнет ошибка времени выполнения при попытке доступа к элементу в пустой очереди. Дополнительные сведения см. в разделе Проверяемые итераторы.
Пример
begin
Возвращает итератор, адресующий первый элемент в очереди.
Возвращаемое значение
Итератор произвольного доступа, адресующий первый элемент в очереди или расположение после пустой очереди.
Комментарии
Пример
cbegin
Возвращаемое значение
Комментарии
Возвращаемое значение
Итератор произвольного доступа, который указывает на место сразу после конца диапазона.
Комментарии
cend используется для проверки того, прошел ли итератор конец диапазона.
clear
Стирает все элементы в очереди.
Пример
const_iterator
Тип, предоставляющий итератор произвольного доступа, который может получать доступ к const элементу в deque и считывать его.
Комментарии
Тип const_iterator нельзя использовать для изменения значения элемента.
Пример
const_pointer
Предоставляет указатель на элемент const в очереди.
Комментарии
Тип const_pointer нельзя использовать для изменения значения элемента. Для доступа к элементу очереди чаще используется iterator.
const_reference
Тип, предоставляющий ссылку на const элемент, хранящийся в deque для чтения и выполнения const операций.
Комментарии
Тип const_reference нельзя использовать для изменения значения элемента.
Пример
const_reverse_iterator
Тип, предоставляющий итератор произвольного доступа, который может читать любой const элемент в deque.
Комментарии
Тип const_reverse_iterator не может изменять значение элемента и используется для последовательного прохождения через очередь в обратную сторону.
Пример
См. пример объявления и использования итератора в разделе rbegin.
crbegin
Возвращает константный итератор первому элементу в очереди в обратную сторону.
Возвращаемое значение
Константный обратный итератор произвольного доступа, указывающий на первый элемент в обращенном объекте deque или на элемент, который был последним в до обращения.
Комментарии
Пример
crend
Возвращает константный итератор, который указывает на расположение после последнего элемента в очереди в обратную сторону.
Возвращаемое значение
Константный обратный итератор произвольного доступа, адресующий расположение после последнего элемента в обращенном объекте deque (расположение перед первым элементом в необращенной очереди).
Комментарии
Если возвращается значение crend (уменьшенное соответствующим образом), объект deque изменить нельзя.
crend можно использовать, чтобы проверить, достиг ли обратный итератор конца очереди.
Пример
deque
Создает очередь определенного размера или с элементами определенного значения, или с определенным распределителем, или в качестве копии какой-либо другой очереди или ее части.
Параметры
Al
Класс распределителя для использования с данным объектом.
Количество
Количество элементов в создаваемой очереди.
Val
Значение элементов в создаваемой очереди.
Right
Очередь, для которой создаваемая очередь станет копией.
Первая
Положение первого элемента в диапазоне копируемых элементов.
Последняя
Положение первого элемента за пределами диапазона копируемых элементов.
IList
Копируемый initializer_list.
Комментарии
Все конструкторы хранят объект распределителя (Al) и инициализируют deque.
Первые два конструктора указывают пустую начальную deque; второй также указывает тип распределителя ( _Al ) для использования.
Шестой конструктор задает копию правогоdeque.
Седьмой и восьмой конструкторы копируют диапазон [First, Last) очереди.
Седьмой конструктор перемещает правоdeque.
Восьмой конструктор копирует содержимое initializer_list.
Ни один из конструкторов не выполняет промежуточные перераспределения.
Пример
difference_type
Тип, предоставляющий разницу между двумя итераторами, ссылающимися на элементы в одной и той же очереди.
Комментарии
difference_type также можно описать как число элементов между двумя указателями.
Пример
emplace
Вставляет элемент, созданный на месте, в указанное положение в очереди.
Параметры
_Where
Позиция в объекте deque, куда вставляется первый элемент.
Возвращаемое значение
Функция возвращает итератор, указывающий на положение вставки нового элемента в очередь.
Комментарии
Пример
emplace_back
Добавляет элемент, созданный на месте, в конец очереди.
Параметры
Val
Элемент, добавляемый в конец объекта deque.
Пример
emplace_front
Добавляет элемент, созданный на месте, в конец очереди.
Параметры
Val
Элемент, добавляемый в начало deque.
Пример
empty
Проверяет, пуста ли очередь.
Возвращаемое значение
true значение, если deque пусто; false Если deque не является пустым.
Пример
Возвращает итератор, адресующий расположение за последним элементом в очереди.
Возвращаемое значение
Возвращает итератор произвольного доступа, адресующий расположение за последним элементом в очереди. Если очередь пуста, то deque::end == deque::begin.
Комментарии
end используется для проверки того, достиг ли итератор конца его deque.
Пример
erase
Удаляет элемент или диапазон элементов с указанных позиций в очереди.
Параметры
_Where
Положение элемента, удаляемого из очереди.
first
Положение первого элемента, удаленного из очереди.
last
Положение после последнего элемента, удаленного из очереди.
Возвращаемое значение
Итератор произвольного доступа, указывающий на первый элемент, оставшийся после удаленных элементов, или на указатель конца очереди, если такого элемента не существует.
Комментарии
erase никогда не создает исключений.
Пример
лицевая камера
Возвращает ссылку на первый элемент в очереди.
Возвращаемое значение
Если очередь пуста, возвращаемое значение не определено.
Комментарии
При компиляции с помощью _ITERATOR_DEBUG_LEVEL, для которого задано значение 1 или 2, возникнет ошибка времени выполнения при попытке доступа к элементу в пустой очереди. Дополнительные сведения см. в разделе Проверяемые итераторы.
Пример
get_allocator
Возвращает копию объекта распределителя, использованного для создания очереди.
Возвращаемое значение
Распределитель, используемый очередью.
Комментарии
Распределители для класса очереди определяют, как этот класс управляет хранилищем. Распределителей по умолчанию в классах контейнеров стандартной библиотеки C++ достаточно для большинства задач программирования. Написание и использование собственного класса распределителя требует расширенных навыков работы с C++.
Пример
insert
Вставляет один элемент, несколько элементов или диапазон элементов в указанное положение в очереди.
Параметры
Where
Положение в целевой очереди, куда вставляется первый элемент.
Val
Значение элемента, вставляемого в очередь.
Количество
Количество элементов, вставляемых в очередь.
Первая
Положение первого элемента в диапазоне элементов в копируемой очереди аргументов.
Последняя
Положение первого элемента за пределами диапазона элементов в копируемой очереди аргументов.
IList
Объект initializer_list, содержащий вставляемые элементы.
Возвращаемое значение
Две первые функции вставки возвращают итератор, указывающий на положение вставки нового элемента в очередь.
Комментарии
Любая операция вставки может быть ресурсоемкой.
iterator
Тип, предоставляющий итератор произвольного доступа, который может читать или изменять любой элемент в очереди.
Комментарии
Тип iterator можно использовать для изменения значения элемента.
Пример
max_size
Возвращает максимальную длину очереди.
Возвращаемое значение
Максимально возможная длина очереди.
Пример
operator[]
Возвращает ссылку на элемент очереди в указанной позиции.
Параметры
pos
Положение элемента очереди, на который должна быть ссылка.
Возвращаемое значение
Ссылка на элемент, позиция которого указана в аргументе. Если заданная позиция больше размера очереди, результат не определен.
Комментарии
При компиляции с помощью _ITERATOR_DEBUG_LEVEL, для которого задано значение 1 или 2, возникнет ошибка времени выполнения при попытке доступа к элементу за пределами очереди. Дополнительные сведения см. в разделе Проверяемые итераторы.
Пример
operator=
Заменяет элементы этой очереди с помощью элементов из другой очереди.
Параметры
Правильно
Очередь, предоставляющая новое содержимое.
Комментарии
Первое переопределение копирует элементы в этот deque с правогокрая, источника назначения. Второе переопределение перемещает элементы в deque из right.
Элементы, содержащиеся в этой очереди перед выполнением оператора, удаляются.
Пример
указатель
Предоставляет указатель на элемент в объекте deque.
Комментарии
Тип pointer можно использовать для изменения значения элемента. Для доступа к элементу очереди чаще используется iterator.
pop_back
Удаляет элемент в конце очереди.
Комментарии
Последний элемент не должен быть пустым. pop_back никогда не создает исключений.
Пример
pop_front
Удаляет элемент в начале очереди.
Комментарии
Первый элемент не должен быть пустым. pop_front никогда не создает исключений.
Пример
push_back
Добавляет элемент в конец очереди.
Параметры
Val
Элемент, добавляемый в конец очереди.
Комментарии
При создании исключения очередь не изменяется, а исключение создается снова.
push_front
Добавляет элемент в начало очереди.
Параметры
Val
Элемент, добавляемый в начало очереди.
Комментарии
При создании исключения очередь не изменяется, а исключение создается снова.
Пример
rbegin
Возвращает итератор, указывающий на первый элемент в обращенной очереди.
Возвращаемое значение
Обратный итератор произвольного доступа, указывающий на первый элемент в обращенной очереди или на последний элемент в необращенной очереди.
Комментарии
rbegin используется с обращенной очередью точно так же, как rbegin используется с очередью.
rbegin можно использовать для последовательного прохождения по очереди в обратную сторону.
Пример
reference
Тип, предоставляющий ссылку на элемент, хранящийся в очереди.
Пример
Возвращает итератор, адресующий расположение после последнего элемента в обращенной очереди.
Возвращаемое значение
Обратный итератор произвольного доступа, адресующий расположение после последнего элемента в обращенной очереди (расположение перед первым элементом в необращенной очереди).
Комментарии
rend используется с обращенной очередью точно так же, как rend используется с очередью.
rend можно использовать, чтобы проверить, достиг ли обратный итератор конца очереди.
Пример
изменить размер
Указывает новый размер очереди.
Параметры
_Newsize
Новый размер очереди.
Val
Значение новых элементов, добавляемых в очередь, если новый размер больше исходного. Если значение не задано, новым элементам назначается значение по умолчанию для класса.
Комментарии
Если размер deque меньше запрошенного размера, _Newsizeэлементы добавляются в deque до тех пор, пока не достигнет запрошенного размера.
Если размер deque больше запрошенного размера, элементы, ближайшие к концу deque, удаляются до тех пор, пока deque не достигнет размера _Newsize.
Если текущий размер очереди совпадает с запрошенным, никакие действия не выполняются.
size — это текущий размер очереди.
Пример
reverse_iterator
Тип, предоставляющий итератор произвольного доступа, который может читать или изменять любой элемент в обращенной очереди.
Комментарии
Тип reverse_iterator используется для итерации по очереди.
Пример
См. пример для rbegin.
shrink_to_fit
Удаляет лишнюю емкость.
Комментарии
Пример
Возвращает число элементов в очереди.
Возвращаемое значение
Текущая длина очереди.
Пример
size_type
Тип, который подсчитывает количество элементов в очереди.
Пример
Меняет местами элементы двух объектов deque.
Параметры
слева
Объект deque, элементы которого должны быть заменены элементами deque right.
Пример
value_type
Тип, представляющий тип данных, хранящихся в очереди.
Комментарии
Дек (двусторонняя очередь).
Дек (deque — double ended queue, «двусторонняя очередь») – структура данных типа «список», функционирующая одновременно по двум принцам организации данных: FIFO и LIFO. Определить дек можно как очередь с двумя сторонами, так и стек, имеющий два конца. То есть данный подвид списка характерен двухсторонним доступом: выполнение поэлементной операции, определенной над деком, предполагает возможность выбора одной из его сторон в качестве активной.
Число основных операций, выполняемых над стеком и очередью, как помнит читатель, равнялось трем: добавление элемента, удаление элемента, чтение элемента. При этом не указывалось место структуры данных, активное в момент их выполнения, поскольку ранее оно однозначно определялось свойствами (определением) самой структуры. Теперь, ввиду дека как обобщенного случая, для приведенных операций следует указать эту область. Разделив каждую из операций на две: одну применительно к «голове» дека, другую – его «хвосту», получим набор из шести операций:
На практике этот список может быть дополнен проверкой дека на пустоту, получением его размера и некоторыми другими операциями.
В плане реализации двусторонняя очередь очень близка к стеку и обычной очереди: в качестве ее базиса приемлемо использовать как массив, так и список. Далее мы напишем интерфейс обработки дека, представленного обычным индексным массивом. Программа будет состоять из основной части и девяти функций:
Помимо самого массива потребуется указатель на последний элемент, назовем его last. Указатель на первый элемент не потребуется, поскольку дек будет представлять собой смещающуюся структуру, т. е. при добавлении нового элемента в начало, каждый из старых элементов сместиться на одну позицию вправо, уступив тем самым первому элементу ячейку с индексом 0 (в C++), следовательно, адрес первого элемента – константа.
Контейнеры STL C++: в чем разница между deque и list?
в чем разница между ними? Я имею в виду, что все методы одинаковы. Для пользователя они работают одинаково.
6 ответов
от (датированный, но все еще очень полезный)SGI STL итог deque :
deque очень похож на вектор: как и вектор, это последовательность, поддерживающая произвольный доступ к элементам, постоянную временную вставку и удаление элементов в конце последовательности и линейную временную вставку и удаление элементов в середине.
основной способ, которым deque отличается от вектора, заключается в том, что deque также поддерживает постоянное время вставка и удаление элементов в начале последовательности. Кроме того, deque не имеет функций-членов, аналогичных capacity() и reserve () вектора, и не предоставляет каких-либо гарантий достоверности итератора, связанных с этими функциями-членами.
вот резюме на list С того же сайта:
список-это дважды связанный список. То есть, это последовательность, которая поддерживает как вперед, так и обратный обход, и (амортизированный) ввод постоянного времени и удаление элементов в начале или конце, или в середине. Списки имеют важное свойство, что вставка и сращивание не делают недействительными итераторы для элементов списка, и что даже удаление делает недействительными только итераторы, указывающие на удаляемые элементы. Порядок итераторов может быть изменен (то есть list::iterator может иметь другой предшественник или преемник после операции списка, чем раньше), но сами итераторы не будут признаны недействительными или сделаны для указания на разные элементы, если это недействительность или мутация не явны.
в итоге контейнеры могут иметь общие процедуры, но гарантии времени для этих процедур отличаются от контейнера к контейнеру. Это очень важно при рассмотрении того, какой из этих контейнеров использовать для задачи: с учетом как контейнер будет наиболее часто использоваться (например, больше для поиск, чем для вставки / удаления) проходит долгий путь, направляя вас к правильному контейнеру.
позвольте мне перечислить различия:
сложности
нет. Deque поддерживает только O (1) вставку и удаление спереди и сзади. Например, он может быть реализован в векторе с обтеканием. Поскольку он также гарантирует O (1) случайный доступ, вы можете быть уверены, что он не использует (просто) дважды связанный список.
другой важной гарантией является то, как каждый контейнер хранит свои данные в памяти:
обратите внимание, что deque был разработан для попытаться баланс преимуществ как векторные, так и без их недостатков. Это особенно интересный контейнер в памяти ограниченных платформ, например, микроконтроллеров.
стратегия хранения памяти часто упускается из виду, однако часто Это одна из самых важных причин для выбора наиболее подходящего контейнера для определенного приложения.
Deque c что это
Так как мы знакомимся с деком, то нам тяжело понять чем же он хорош, чем лучше других контейнеров. Начнем с общего описания дека. Что этот дек вообще такое в STL? Далеко ходить не будем, возьмем урок физкультуры. Многие из нас знают, что такое «построиться по росту». Так вот, такое построение, что ни на есть самый настоящий дек. Ведь образуется ряд, в этот ряд могут внедряться и с его конца и с его начала и даже занимать позицию внутри этого ряда. А по скорости куда быстрее вставать? Разумеется или в начало или в конец ряда, а в середине ряда нужно искать приблизительно свой рост и потом сравниваться и менять позиции. При этом при вставке в середину ряда, весь ряд будет сдвинут. Вот такая вот аналогия дека из жизни.
Поэтому дек имеет смысл применять тогда когда в приоритете будут вставки или в начало или в конец коллекции, но при этом не исключается, что какие-то элементы придется вставлять и в середину. (соответственно и выбирать из дека аналогично). Хотя деки поддерживают вставку и удаление в средине последовательности, эти операции выполняются за линейное время. Если в приложении должно выполняться много таких операций, лучшим выбором могут оказаться списки.
Список отличий дека(очереди deque) от вектора:
Особенности векторов, которые относятся к декам
Предпочтение декам отдается тогда когда выполняются следующие условия
Следует учитывать, что
Интерфейс вектора и дека почти идентичен, различие только в том, что могут отсутствовать некоторые функции, если они отсутствуют, то это значит они не нужны. Так, например класс дека не имеет функций членов capacity, reserve. Просто потому что дек не испытывает необходимости в таком повышении производительности, как в случае векторов.
Используя деки мы должны быть осторожны и не писать кода, который зависит от итераторов или ссылок, остающихся корректными при вставках.
В общем, по сути своей деки те же векторы, следовательно и работать с ними можно как с векторами, просто надо научиться выбирать когда и что выбирать лучше.
Деки оптимизированы для вставки одного элемента либо в начало, либо в конец структуры данных. Такие вставки выполняются за константное время и вызывают копирующий конструктор один раз.
Если элемент вставляется в середину дека, то в наихудшем случае для выполнения этой операции требуется время, линейно зависящее от меньшего значения среди расстояний от точки вставки до начала и до конца дека.
Функции-члены insert, push_front и push_back делают недействительными все итераторы, указывающие в дек. Ссылки также делаются недействительными при вставке в середину дека.
Ну и чтобы был какой-то пример, возьмем простой алгоритм перегруппировки данных в очереди. Перегруппируем все элементы внутри очереди так, чтобы элементы, удовлетворяющие некоторому нашему условию находились перед элементами не удовлетворяющим этому же условию
