STL Знакомство с deque

Опубликовано 30.09.2014 | Автор: admin

Дек является динамическим массивом, который реализован таким образом, что он может расширяться с двух сторон одинаково быстро. Кроме этого, в дек разрешено вставлять элементы вовнутрь себя на произвольную позицию, однако вставка элементов в произвольную позицию происходит не так быстро как вставка в начало или в конец и даже может уступать аналогичной операции в векторе.

Так как мы знакомимся с деком, то нам тяжело понять чем же он хорош, чем лучше других контейнеров. Начнем с общего описания дека. Что этот дек вообще такое в STL? Далеко ходить не будем, возьмем урок физкультуры. Многие из нас знают, что такое «построиться по росту». Так вот, такое построение, что ни на есть самый настоящий дек. Ведь образуется ряд, в этот ряд могут внедряться и с его конца и с его начала и даже занимать позицию внутри этого ряда. А по скорости куда быстрее вставать? Разумеется или в начало или в конец ряда, а в середине ряда нужно искать приблизительно свой рост и потом сравниваться и менять позиции. При этом при вставке в середину ряда, весь ряд будет сдвинут. Вот такая вот аналогия дека из жизни.

Поэтому дек имеет смысл применять тогда когда в приоритете будут вставки или в начало или в конец коллекции, но при этом не исключается, что какие-то элементы придется вставлять и в середину. (соответственно и выбирать из дека аналогично). Хотя деки поддерживают вставку и удаление в средине последовательности, эти операции выполняются за линейное время. Если в приложении должно выполняться много таких операций, лучшим выбором могут оказаться списки.

По сути своей дек — это вектор с более быстрой вставкой элементов в свое начало или в самый свой хвост. Но в то же время прочие операции у дека имеют то же время работы (или медленнее на константный множитель), что и соответствующие операции векторов.

Список отличий дека(очереди deque) от вектора:

Вставка элементов и в начало и в конец очереди являются быстрыми операциями, у векторов быстрой операцией является только вставка в конец. Занимает такая вставка константное время.
Перемещение по деку и доступ к элементам дека как правило немного медленнее чем аналогичные операции у вектора
Итераторы дека должны быть умными указателями особого типа, а не обычными указателями, поскольку они должны переключаться между разными блоками
В системах, которые имеют ограничения на размер блоков памяти (например, некоторые системы ПК), двусторонняя очередь может содержать больше элементов, чем может содержать вектор, потому что она использует более одного блока памяти. Таким образом, max_size () способен быть большим для двусторонних очередей нежели для векторов
Двусторонние очереди не обеспечивают управление емкостью и не определяют момент повторного выделения памяти. В частности, любая вставка или удаление, кроме вставки элементов в начало или в конец делают невалидными все указатели, ссылки и итераторы, которые относятся к элементам двусторонней очереди. Тем не менее, перераспределение памяти может работать лучше, чем для векторов, так как в соответствии с их типичной внутренней структурой, двусторонние очереди не нуждаются в копировании всех элементов при перераспределении памяти.
Блоки памяти могут высвобождаться, когда они больше не используются, поэтому размер памяти дека может сократиться (однако, когда и как это происходит, зависит от конкретной реализации).

Особенности векторов, которые относятся к декам

Вставка и удаление элементов в середину относительно медленная операция, потому что все элементы до любого конца должны быть перемещены, чтобы освободить место или, чтобы заполнить пространство.
И у векторов и у деков итераторы произвольного доступа
Класс deque предоставляет в точности такой же набор конструкторов, как и класс vector.

Предпочтение декам отдается тогда когда выполняются следующие условия

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

Следует учитывать, что

Ни одна функция, кроме .at(), из всех функций, обеспечивающих доступ к элементам дека не проверяет является ли индекс или итератор корректным.
Вставка или удаление может вызывать повторное выделение памяти. Таким образом, любая вставка или удаление делает некорректными все указатели, ссылки и итераторы, установленные на другие элементы дека. Исключением являются вставка в начало или в конец дека. При вставке в начало или в конец дека ссылки и указатели остаются корректными, но итераторы нет.

Интерфейс вектора и дека почти идентичен, различие только в том, что могут отсутствовать некоторые функции, если они отсутствуют, то это значит они не нужны. Так, например класс дека не имеет функций членов capacity, reserve. Просто потому что дек не испытывает необходимости в таком повышении производительности, как в случае векторов.

Используя деки мы должны быть осторожны и не писать кода, который зависит от итераторов или ссылок, остающихся корректными при вставках.

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

Деки оптимизированы для вставки одного элемента либо в начало, либо в конец структуры данных. Такие вставки выполняются за константное время и вызывают копирующий конструктор один раз.
Если элемент вставляется в середину дека, то в наихудшем случае для выполнения этой операции требуется время, линейно зависящее от меньшего значения среди расстояний от точки вставки до начала и до конца дека.
Функции-члены insert, push_front и push_back делают недействительными все итераторы, указывающие в дек. Ссылки также делаются недействительными при вставке в середину дека.

Ну и чтобы был какой-то пример, возьмем простой алгоритм перегруппировки данных в очереди. Перегруппируем все элементы внутри очереди так, чтобы элементы, удовлетворяющие некоторому нашему условию находились перед элементами не удовлетворяющим этому же условию

#include <iostream>
#include <deque>  //обязательно если используем deque
#include <algorithm>
using namespace std;

  bool mypred(const int x){
     return x<51;   //наше условие, что элемент в деке меньше чем 51
  }

int main(){
    setlocale(LC_ALL,"");
    int Arr[]={1,78,89,23,51,49,100};
    deque<int> d(&Arr[0],&Arr[7]);

    cout<<"Исходная\n";
    for (deque<int>::iterator it=d.begin();it!=d.end();it++) std::cout<<*it<<" | ";
    cout<<"\n";

    stable_partition(d.begin(),d.end(),mypred);

    cout<<"\nПолучили\n";
    for (deque<int>::iterator it=d.begin();it!=d.end();it++) std::cout<<*it<<" | ";
    cout<<"\n";


}
//Теперь слева все числа меньшие 51, а справа большие или равные

#include <iostream>

#include <deque> //обязательно если используем deque

#include <algorithm>

using namespace std;

bool mypred(const int x){

return x<51; //наше условие, что элемент в деке меньше чем 51

}

int main(){

setlocale(LC_ALL,"");

int Arr[]={1,78,89,23,51,49,100};

deque<int> d(&Arr[0],&Arr[7]);

cout<<"Исходная\n";

for (deque<int>::iterator it=d.begin();it!=d.end();it++) std::cout<<*it<<" | ";

cout<<"\n";

stable_partition(d.begin(),d.end(),mypred);

cout<<"\nПолучили\n";

for (deque<int>::iterator it=d.begin();it!=d.end();it++) std::cout<<*it<<" | ";

cout<<"\n";

}

//Теперь слева все числа меньшие 51, а справа большие или равные

Может кому непонятно

bool mypred(const int x){
     return x<51; //Всегда когда x<51 вернет true, иначе false
  }

bool mypred(const int x){

return x<51; //Всегда когда x<51 вернет true, иначе false

}

Это тоже самое, что

bool mypred(const int x){
     if (x<51) return true;
     return false;
  }

bool mypred(const int x){

if (x<51) return true;

return false;

}

Вот, собственно, что еще сказать и не знаю. Выбрать дек или вектор во многом зависит от задачи, но, надеюсь этот материал поможет определить имеет ли смысл отдать предпочтение первому или второму.

Рубрика: Без рубрики