Класс deque: двусторонняя очередь

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

#include <deque>

Создание объекта

Объявление класса deque:

template<typename _Tp, typename _Alloc = allocator<_Tp> >
   class deque : protected _Deque_base<_Tp, _Alloc>;

Создать экземпляр класса deque можно следующими способами (полный список конструкторов смотрите в документации):

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок задается тип данных. В этом случае очередь не содержит элементов. Пример объявления без инициализации:
std::deque<int> arr;
  • указать внутри круглых скобок количество элементов:
std::deque<int> arr(5);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0 0 0

Все элементы будут иметь значения по умолчанию для типа. Например, для типа int все элементы будут содержать значение 0. Указать другое значение можно во втором параметре. Пример создания очереди из 5 элементов со значением 1:

std::deque<int> arr(5, 1);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 1 1 1 1
  • перечислить значения через запятую внутри фигурных скобок:
std::deque<int> arr1{1, 2, 3};
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::deque<int> arr2 = {4, 5, 6};
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
  • указать объект класса deque внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):
std::deque<int> arr1 = {1, 2, 3};
// Создание копии
std::deque<int> arr2(arr1);
arr2[0] = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3
// Перемещение элементов
std::deque<int> arr3(std::move(arr1));
for (int &el : arr3) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::cout << arr1.size() << std::endl; // 0
  • указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:
std::deque<int> arr1 = {1, 2, 3};
std::deque<int> arr2(arr1.begin(), arr1.end());
arr2[0] = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3

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

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::deque<int> arr2(arr, arr + ARR_SIZE);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Над двумя объектами класса deque определены операции ==, !=, <, <=, > и >=. Пример сравнения двух объектов:

std::deque<int> arr1 = {1, 2, 3};
std::deque<int> arr2(arr1.begin(), arr1.end());
if (arr1 == arr2) {
   std::cout << "arr1 == arr2" << std::endl;
}

Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

std::deque<int> arr1 = {1, 2, 3}, arr2, arr3;
// Создание копии
arr2 = arr1;
arr2[0] = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3
// Перемещение элементов
arr3 = std::move(arr1);
for (int &el : arr3) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::cout << arr1.size() << std::endl; // 0

Доступно также присваивание элементов из списка инициализации:

std::deque<int> arr;
arr = {1, 2, 3};
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо оператора = для присваивания значения можно воспользоваться методом assign(). Прототипы метода:

void assign(size_type count, const value_type &val);
template<typename _InputIterator>
   void assign(_InputIterator first, _InputIterator last);
void assign(initializer_list<value_type> list);

Первый прототип удаляет существующие элементы, а затем вставляет count элементов val. Второй прототип удаляет существующие элементы, а затем вставляет элементы из диапазона, ограниченного итераторами first и last. Третий прототип удаляет существующие элементы, а затем вставляет элементы из списка инициализации. Пример:

std::deque<int> arr1 = {1, 2, 3}, arr2 = {4, 5};
arr1.assign(3, 0);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0
arr1.assign(arr2.begin(), arr2.end());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5
arr1.assign({6, 7, 8});
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 6 7 8

Пример присваивания элементов из обычного массива:

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::deque<int> arr2;
arr2.assign(arr, arr + ARR_SIZE);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вставка элементов

Вставить элементы позволяют следующие методы:

  • push_front() — добавляет элемент в начало очереди (доступно копирование и перемещение значения);
  • push_back() — добавляет элемент в конец очереди (доступно копирование и перемещение значения):
std::deque<int> arr = {2, 3};
arr.push_front(1);      // В начало
arr.push_back(4);       // В конец
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4
  • emplace_front() — создает объект, передавая конструктору указанные через запятую значения, а затем добавляет объект в начало очереди. Начиная со стандарта C++17, метод возвращает ссылку на созданный объект;
  • emplace_back() — создает объект, передавая конструктору указанные через запятую значения, а затем добавляет объект в конец очереди. Начиная со стандарта C++17, метод возвращает ссылку на созданный объект:
class C {
public:
   int x, y;
   C(int a, int b) : x(a), y(b) { }
};
// ... Фрагмент опущен ...
std::deque<C> arr;
arr.push_back(C(20, 20));
arr.emplace_front(10, 40);  // В начало
arr.emplace_back(30, 60);   // В конец
for (C &el : arr) std::cout << el.x << ' ';
std::cout << std::endl; // 10 20 30
  • insert() — вставляет один или несколько элементов в позицию pos, заданную с помощью итератора. Прототипы метода:
iterator insert(const_iterator pos, const value_type &val);
iterator insert(const_iterator pos, value_type &&val);
iterator insert(const_iterator pos, size_type count,
                const value_type &val);
template<typename _InputIterator>
   iterator insert(const_iterator pos, _InputIterator first,
                   _InputIterator last);
iterator insert(const_iterator pos,
                initializer_list<value_type> list);

Первые два прототипа вставляют элемент в позицию pos, на которую указывает итератор и возвращают итератор, ссылающийся на вставленный элемент:

std::deque<int> arr = {10};
arr.insert(arr.begin(), 0);     // В начало
arr.insert(arr.end(), 20);      // В конец
arr.insert(arr.begin() + 1, 5); // В позицию 1
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 5 10 20

Третий прототип вставляет count копий элемента val в позицию pos, на которую указывает итератор:

std::deque<int> arr = {1, 2, 3};
arr.insert(arr.begin(), 3, 0);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0 1 2 3

Четвертый прототип вставляет элементы из диапазона, ограниченного итераторами first и last, в позицию pos, на которую указывает итератор:

std::deque<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.insert(arr1.end(), arr2.begin(), arr2.end());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Пример вставки элементов из обычного массива:

std::deque<int> arr1 = {1, 2, 3};
int arr2[] = {4, 5, 6};
arr1.insert(arr1.end(), arr2, arr2 + 3);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Пятый прототип вставляет элементы из списка инициализации в позицию pos, на которую указывает итератор:

std::deque<int> arr = {1, 2, 3};
arr.insert(arr.end(), {4, 5, 6});
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6
  • emplace() — создает объект, передавая конструктору указанные через запятую значения во втором и последующих параметрах, а затем добавляет объект в позицию, заданную в первом параметре. Метод возвращает итератор, ссылающийся на вставленный элемент. Добавим два объекта в конец очереди и один в начало:
std::deque<C> arr;
arr.emplace(arr.end(), 30, 40);
arr.emplace(arr.end(), 50, 60);
arr.emplace(arr.begin(), 10, 20);
for (C &el : arr) std::cout << el.x << ' ';
std::cout << std::endl; // 10 30 50
  • swap() — меняет элементы двух очередей местами:
std::deque<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.swap(arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо метода swap() можно воспользоваться одноименной функцией:

std::deque<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
std::swap(arr1, arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Определение и изменение количества элементов

Для определения и изменения количества элементов очереди предназначены следующие методы:

  • size() — возвращает количество элементов в очереди. Прототип метода:
size_type size() const noexcept;

Пример:

std::deque<int> arr = {1, 2, 3};
std::cout << arr.size() << std::endl; // 3
  • empty() — возвращает значение true, если очередь не содержит элементов, и false — в противном случае. Прототип метода:
bool empty() const noexcept;

Пример:

std::deque<int> arr;
std::cout << std::boolalpha
          << arr.empty() << std::endl;          // true
arr = {1, 2, 3};
std::cout << arr.empty() << std::endl;          // false
  • shrink_to_fit() — уменьшает объем памяти, чтобы он соответствовал размеру очереди. Прототип метода:
void shrink_to_fit() noexcept;
  • resize() — задает количество элементов, равное числу new_size. Если указанное количество элементов меньше текущего количества, то лишние элементы будут удалены. Если количество элементов необходимо увеличить, то в параметре val можно указать значение, которое заполнит новое пространство. Прототипы метода:
void resize(size_type new_size);
void resize(size_type new_size, const value_type &val);

Пример:

std::deque<int> arr = {1, 2, 3};
arr.resize(2);
std::cout << arr.size() << std::endl;          // 2
arr.resize(5, 0);
std::cout << arr.size() << std::endl;          // 5
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                        // 1 2 0 0 0
  • max_size() — возвращает максимальное количество элементов, которое теоретически может содержаться в контейнере. Прототип метода:
size_type max_size() const noexcept;

Пример:

std::deque<int> arr;
std::cout << arr.max_size() << std::endl;
// 4611686018427387903

Удаление элементов

Для удаления элементов предназначены следующие методы:

  • pop_front() — удаляет первый элемент. Прототип метода:
void pop_front();

Пример:

std::deque<int> arr = {1, 2, 3};
arr.pop_front();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 3
  • pop_back() — удаляет последний элемент. Прототип метода:
void pop_back();

Пример:

std::deque<int> arr = {1, 2, 3};
arr.pop_back();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2
  • erase() — удаляет один элемент или элементы из диапазона. Прототипы метода:
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

Первый прототип удаляет элемент на который указывает итератор. Второй прототип удаляет элементы из диапазона, ограниченного итераторами first и last:

std::deque<int> arr = {1, 2, 3, 4, 5};
arr.erase(arr.begin());
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 3 4 5
arr.erase(arr.begin() + 1, arr.begin() + 3);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 5
  • clear() — удаляет все элементы. Прототип метода:
void clear() noexcept;

Пример:

std::deque<int> arr = {1, 2, 3, 4, 5};
arr.clear();
std::cout << arr.size() << std::endl;     // 0

Доступ к элементам

К любому элементу можно обратиться как к элементу массива. Достаточно указать его индекс в квадратных скобках. Нумерация начинается с нуля. Можно как получить значение, так и изменить его. Если индекс выходит за границы диапазона, то возвращаемое значение не определено. Пример доступа к элементу по индексу:

std::deque<int> arr = {1, 2, 3};
std::cout << arr[0] << std::endl; // 1
arr[0] = 55;
std::cout << arr[0] << std::endl; // 55

Для доступа к элементам предназначены следующие методы:

  • at() — возвращает ссылку на элемент, расположенный по индексу n. Метод позволяет как получить значение, так и изменить его. Если индекс выходит за границы диапазона, то генерируется исключение. Прототипы метода:
reference at(size_type n);
const_reference at(size_type n) const;

Пример:

std::deque<int> arr = {1, 2, 3};
std::cout << arr.at(0) << std::endl; // 1
arr.at(0) = 55;
std::cout << arr.at(0) << std::endl; // 55
  • front() — возвращает ссылку на первый элемент. Метод позволяет как получить значение, так и изменить его. Прототипы метода:
reference front();
const_reference front() const;
  • back() — возвращает ссылку на последний элемент. Метод позволяет как получить значение, так и изменить его. Прототипы метода:
reference back();
const_reference back() const;

Пример:

std::deque<int> arr = {1, 2, 3};
arr.front() = 55;
arr.back() = 88;
std::cout << arr.front() << std::endl; // 55
std::cout << arr.back() << std::endl;  // 88
  • begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin() и crend() — возвращают итераторы (см. разд. 16.1.1). Изменим и выведем значение первого элемента:
std::deque<int> arr = {1, 2, 3};
std::deque<int>::iterator it = arr.begin();
std::cout << *it << std::endl; // 1
*it = 0;
std::cout << *it << std::endl; // 0

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем значение последнего элемента:

std::deque<int> arr = {1, 2, 3};
std::deque<int>::iterator it = std::end(arr);
std::cout << *(--it) << std::endl; // 3

Перебор элементов

Перебрать все элементы можно с помощью цикла for each, итераторов и алгоритма for_each(). Пример использования цикла for each:

std::deque<int> arr(3);
// Заполняем очередь значениями
int n = 1;
for (int &el : arr) {
   el = n++;
}
// Выводим значения
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Если нужен доступ по индексу, то можно воспользоваться циклом for:

std::deque<int> arr = {1, 2, 3};
for (size_t i = 0, j = arr.size(); i < j; ++i)
   std::cout << arr.at(i) << ' ';
std::cout << std::endl; // 1 2 3

Пример перебора элементов с помощью итераторов и цикла for в прямом и обратном порядке:

std::deque<int> arr = {1, 2, 3};
std::deque<int>::iterator it1, it2;
// Перебор в прямом порядке
for (it1 = arr.begin(), it2 = arr.end(); it1 != it2; ++it1) {
   std::cout << *it1 << ' ';
}
std::cout << std::endl; // 1 2 3
// Перебор в обратном порядке
std::deque<int>::reverse_iterator it3, it4;
for (it3 = arr.rbegin(), it4 = arr.rend(); it3 != it4; ++it3) {
   std::cout << *it3 << ' ';
}
std::cout << std::endl; // 3 2 1

Пример перебора элементов с помощью итераторов и цикла while:

std::deque<int> arr = {1, 2, 3};
auto it1 = arr.begin(), it2 = arr.end();
while (it1 != it2) {
   std::cout << *it1++ << ' ';
}
std::cout << std::endl; // 1 2 3

С помощью алгоритма for_each() умножим значение каждого элемента массива на 2, а затем выведем все значения в окно консоли:

// #include <algorithm>
std::deque<int> arr = {1, 2, 3};
// Умножаем все элементы на 2
std::for_each( arr.begin(), arr.end(),
               [](int &a) { a *= 2; } );
// Выводим значения всех элементов
std::for_each( arr.begin(), arr.end(),
               [](int &a){ std::cout << a << ' '; } );
std::cout << std::endl; // 2 4 6

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов