Деки в языке С++

Что же такое Дек? Дек (deque) — это сокращенная фраза «double-ended-queue», что, в переводе с английского, означает — двусторонняя очередь. Контейнер Дек очень похож на контейнер — Вектор, также как и Вектора, Деки являются динамическими массивами. Разница между Вектором и Деком состоит лишь в том, что в деках динамический массив открыт с двух сторон. Это и позволяет очень быстро добавлять новые элементы как в конец так и в начало контейнера. В векторах элементы можно добавлять лишь в конец массива.
Итак, чтобы использовать дек, необходимо подключить заголовочный файл — <deque>:

#include <deque>

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

#include <iostream>
#include <deque>        // подключаем заголовочный файл деков
#include <iterator>     // заголовок итераторов
using namespace std;

int main()
{
    int dequeSize = 0;
    cout << "Введите размер дека: ";
    cin >> dequeSize;

    deque<char> myDeque(dequeSize);     // создаем дек и резервируем для него память

    cout << "Введите элементы дека: ";
    // заполняем дек с клавиатуры
    for(int i = 0; i < myDeque.size(); i++) {
        cin >> myDeque[i];
    }

    cout << "\nВведенный дек: ";
    if (!myDeque.empty()) { // если дек не пуст
        // вывод на экран элементов дека
        copy( myDeque.begin(), myDeque.end(), ostream_iterator<char>(cout," ") ); // вывод на экран элементов дека
    }
    return 0;
}

Как я и говорил, чтобы использовать деки, нужно подключить специальный заголовочный файл, это сделано в строке 2. Кроме того, у нас подключен заголовок итераторов — <iterator> в строке 3. В статье о векторах, я говорил, что он нужен, для вывода элементов контейнера на экран, в строке 23. В 12-й строке мы объявили дек, размер которого указывает пользователь. Строки 16-18 должны быть нам понятны, тут мы просто инициализируем элементы дека.

В строке 21, у нас есть проверка, которая выполняется с использованием функции empty(), то есть тут проверяется пустой ли контейнер или нет. Если — нет, то элементы дека выводятся на экран, в противном случае не выводятся на экран. Эта проверка по большому счету тут и не нужна, так как при такой организации логики программы, дек не будет пустым. Просто показал вам, что есть такой метод, если есть необходимость — обязательно пользуйтесь им.

В строке 23 выполняется вывод элементов контейнера на экран, первый и второй параметры — это итераторы нашего дека, которые указывают на начало и конец контейнера. То есть нам же нужно вывести все элементы, поэтому итераторы захватывают все элементы. Третий параметр — это итератор потока вывода, нужен для того, чтобы направить элементы контейнера в поток вывода. Так как элементы дека имеют тип данных char, то и в итераторе потока вывода, строка 23, также надо указывать char. Смотрим результат работы программы:

Введите размер дека: 20 
Введите элементы дека: Metallica - I disappear 

Введенный дек: M e t a l l i c a - I d i s a p p e a r

Обратите внимание на то, что в выводе все элементы дека разделены символом пробела, так как именно пробел был указан в качестве разделителя при выводе элементов дека в строке 23. В остальном, думаю, тут все предельно ясно!

Фактически мы еще толком не рассмотрели никакого функционала двусторонних очередей, давайте это исправим. А по сему, вот вам еще один пример программы, в которой будут показаны еще несколько возможностей двусторонних очередей:

#include <iostream>
#include <deque>        // подключаем заголовочный файл деков
#include <iterator>     // заголовок итераторов
#include <string>       // заголовочный файл для работы со строками типа string
using namespace std;

int main()
{
    deque<string> myDeque;     // создаем пустой дек типа string
    myDeque.push_back(string("Winter is")); // добавили в дек один элемент типа string
    cout << "Количество элементов в деке: " << myDeque.size() << endl;

    myDeque.push_front("Game of Thrones:"); // добавили в начало дека еще один элемент
    myDeque.push_back("coming!");           // добавили в конец дека элемент "coming!"
    cout << "Количество элементов в деке изменилось, теперь оно = " << myDeque.size() << endl;

    cout << "\nВведенный дек: ";
    if (!myDeque.empty()) { // если дек не пуст
        // вывод на экран элементов дека
        copy( myDeque.begin(), myDeque.end(), ostream_iterator<string>(cout," ") ); // вывод на экран элементов дека
    }

    myDeque.pop_front(); // удалили первый элемент
    myDeque.pop_back(); // удалили второй элемент
    myDeque.resize(6,"empty"); // увеличиваем размер дека до 6 элементов, новые элементы заполняются словом "empty"

    cout << "\nБыли удалены первый и последний элементы дека, вот что осталось: ";
    for(int i = 0; i < myDeque.size(); i++) {
        cout << myDeque[i] << " ";
    }
    return 0;
}

Итак, начнем со строки 9, мы объявили пустой дек, он пустой потому, что мы даже не выделяли для него памяти, мы не задавали его размер. В строке 10 мы воспользовались методом push_back() чтобы в конец дека добавить новый элемент типа string. В строке 11 мы воспользовались функцией size() и узнали сколько элементов содержится внутри дека. Чем интересны строки 13-14? Вот как раз в этих строках реализована отличительная характеристика деков от векторов. Давайте по порядку, в строке 13 мы воспользовались методом push_front(), чтобы добавить в начало дека новый элемент, в векторах такое делать нельзя. Ну и в строке 14 мы вызвали известный уже нам метод push_back().

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

Еще одна интересная функция — resize(), которая может изменять размер дека. Запомните, что resize() может только увеличивать размер, но не уменьшать. В программе, в строке 25, видно, что мы увеличили размер дека до шести элементов, и все новые элементы заполнили словом — empty. Причем стоит обратить внимание на то, что те элементы дека, которые находились в нем до изменения размера абсолютно не были затронуты, это можно увидеть в результате работы программы.

Хотел еще просто вам напомнить, что не обязательно использовать вывод элементов контейнера как в строке 20, если вам этот способ не удобен, можете использовать способ свойственный для обычных массивов, строки 28-30. Смотрим результат работы программы:

Количество элементов в деке: 1 
Количество элементов в деке изменилось, теперь оно = 3 

Введенный дек: Game of Thrones: Winter is coming! 
Были удалены первый и последний элементы дека, вот что осталось: Winter is empty empty empty empty empty

На этом этапе завершим вводную статью по декам, надеюсь, статья была для вас полезной.