Deque

Deque представляет двухстороннюю очередь. Для использования данного контейнера нужно подключить заголовочный файл deque.

Способы создания двухсторонней очереди:

1
2
3
4
5
6
7
8
std::deque<int> deque1; // пустая очередь
std::deque<int> deque2(5); // deque2 состоит из 5 чисел, каждый элемент имеет значение по умолчанию
std::deque<int> deque(5, 2); // deque3 состоит из 5 чисел, каждое число равно 2
std::deque<int> deque4{ 1, 2, 4, 5 }; // deque4 состоит из чисел 1, 2, 4, 5
std::deque<int> deque5 = { 1, 2, 3, 5 }; // deque5 состоит из чисел 1, 2, 3, 5
std::deque<int> deque6({ 1, 2, 3, 4, 5 }); // deque6 состоит из чисел 1, 2, 3, 4, 5
std::deque<int> deque7(deque4); // deque7 - копия очереди deque4
std::deque<int> deque8 = deque7; // deque8 - копия очереди deque7
Получение элементов очереди
Для получения элементов очереди можно использовать операцию [] и ряд функций:

[index]: получение элемента по индексу

at(index): возращает элемент по индексу

front(): возвращает первый элемент

back(): возвращает последний элемент

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <deque>

int main()
{
std::deque<int> numbers = { 1, 2, 3, 4, 5 };

int first = numbers.front(); // 1
int last = numbers.back(); // 5
int second = numbers[1]; // 2
int third = numbers.at(2); // 3
std::cout << first << second << third << last << std::endl; // 1235

return 0;
}
Стоит отметить, что если мы будем обращаться с помощью операции индексирования по некорректному индексу, который выходит за границы контейнера, то результат будет неопредленным:

1
2
std::deque<int> numbers = { 1, 2, 3, 4, 5 };
int eighth = numbers[7];
В этом случае использование функции at() является более предпочтительным, так как при обращении по некорректному индексу она генерирует исключение out_of_range:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <deque>
#include <stdexcept>

int main()
{
std::deque<int> numbers = { 1, 2, 3, 4, 5};
try
{
int n = numbers.at(7);
}
catch (std::out_of_range e)
{
std::cout << "Incorrect index" << std::endl;
}

return 0;
}
Также в цикле или с помощью итераторов можно перебрать элементы контейнера:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <deque>

int main()
{
std::deque<int> numbers = { 1, 2, 3, 4, 5 };

for (int n : numbers)
std::cout << n << "\t";
std::cout << std::endl;

for (int i=0; i < numbers.size(); i++)
std::cout << numbers[i] << "\t";
std::cout << std::endl;

for (auto iter = numbers.begin(); iter != numbers.end(); iter++)
std::cout << *iter << "\t";
std::cout << std::endl;

return 0;
}
Размер очереди
Чтобы узнать размер очереди, можно использовать функцию size(). А функция empty() позволяет узнать, содержит ли очередь элементы. Она возвращает значение true, если в очереди есть элементы:

1
2
3
4
5
6
7
8
9
10
std::deque<int> numbers = { 1, 2, 3, 4, 5 };
if (numbers.empty())
{
std::cout << "Deque is empty" << std::endl;
}
else
{
int n = numbers.size();
std::cout << "Deque has " << n << " elements" << std::endl;
}
Функция resize() позволяет изменить размер очереди. Эта функция имеет две формы:

resize(n): оставляет в очереди n первых элементов. Если deque содержит больше элементов, то размер контейнера усекается до первых n элементов. Если размер очереди меньше n, то добавляются недостающие элементы и инициализируются значением по умолчанию

resize(n, value): также оставляет в очереди n первых элементов. Если размер очереди меньше n, то добавляются недостающие элементы со значением value

Применение функции:

1
2
3
4
std::deque<int> numbers = { 1, 2, 3, 4, 5, 6 };
numbers.resize(4); // оставляем первые четыре элемента - numbers = {1, 2, 3, 4}

numbers.resize(6, 8); // numbers = {1, 2, 3, 4, 8, 8}
Важно учитывать, что применение функции resize может сделать некорректными все итераторы, указатели и ссылки на элементы.

Изменение элементов очереди
Функция assign() позволяет заменить все элементы очереди определенным набором. Она имеет следующие формы:

assign(il): заменяет содержимое контейнера элементами из списка инициализации il

assign(n, value): заменяет содержимое контейнера n элементами, которые имеют значение value

assign(begin, end): заменяет содержимое контейнера элементами из диапазона, на начало и конец которого указывают итераторы begin и end

Применение функции:

1
2
3
4
5
6
7
8
9
10
std::deque<int> numbers = { 1, 2, 3, 4, 5 };

numbers.assign({ 21, 22, 23, 24, 25 }); // numbers = { 21, 22, 23, 24, 25 }

numbers.assign(4, 3); // numbers = {3, 3, 3, 3}

std::deque<int> values = { 6, 7, 8, 9, 10, 11 };
auto start = values.begin() + 2; // итератор указывает на третий элемент
auto end = values.end(); // итератор указывает на последний элемент
numbers.assign(start, end); // numbers = { 8, 9, 10, 11 }
Функция swap() обменивает значениями две очереди:

1
2
3
std::deque<int> deque1 = { 1, 2, 3, 4, 5 };
std::deque<int> deque2 = { 6, 7, 8, 9};
deque1.swap(deque2); // deque1 = { 6, 7, 8, 9};
Добавление элементов
Чтобы добавить элементы в очередь deque, можно применять ряд функций:

push_back(val): добавляет значение val в конец очереди

push_front(val): добавляет значение val в начало очереди

emplace_back(val): добавляет значение val в конец очереди

emplace_front(val): добавляет значение val в начало очереди

emplace(pos, val): вставляет элемент val на позицию, на которую указывает итератор pos. Возвращает итератор на добавленный элемент

insert(pos, val): вставляет элемент val на позицию, на которую указывает итератор pos, аналогично функции emplace. Возвращает итератор на добавленный элемент

insert(pos, n, val): вставляет n элементов val начиная с позиции, на которую указывает итератор pos. Возвращает итератор на первый добавленный элемент. Если n = 0, то возвращается итератор pos.

insert(pos, begin, end): вставляет начиная с позиции, на которую указывает итератор pos, элементы из другого контейнера из диапазона между итераторами begin и end. Возвращает итератор на первый добавленный элемент. Если между итераторами begin и end нет элементов, то возвращается итератор pos.

insert(pos, values): вставляет список значений values начиная с позиции, на которую указывает итератор pos. Возвращает итератор на первый добавленный элемент. Если values не содержит элементов, то возвращается итератор pos.

Функции push_back(), push_front(), emplace_back() и emplace_front():

1
2
3
4
5
std::deque<int> numbers = { 1, 2, 3, 4, 5 };
numbers.push_back(6); // { 1, 2, 3, 4, 5, 6 }
numbers.push_front(0); // { 0, 1, 2, 3, 4, 5, 6 }
numbers.emplace_back(7); // { 0, 1, 2, 3, 4, 5, 6, 7 }
numbers.emplace_front(-1); // { -1, 0, 1, 2, 3, 4, 5, 6, 7 }
Добавление в середину списка с помощью функции emplace():

1
2
3
std::deque<int> numbers = { 1, 2, 3, 4, 5 };
auto iter = ++numbers.cbegin(); // итератор указывает на второй элемент
numbers.emplace(iter, 8); // добавляем после первого элемента numbers = { 1, 8, 2, 3, 4, 5};
Добавление в середину списка с помощью функции insert():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::deque<int> numbers1 = { 1, 2, 3, 4, 5 };
auto iter1 = numbers1.cbegin(); // итератор указывает на второй элемент
numbers1.insert(iter1 + 2, 8); // добавляем после второго элемента
//numbers1 = { 1, 2, 8, 3, 4, 5};

std::deque<int> numbers2 = { 1, 2, 3, 4, 5 };
auto iter2 = numbers2.cbegin(); // итератор указывает на первый элемент
numbers2.insert(iter2, 3, 4); // добавляем вначало три четверки
//numbers2 = { 4, 4, 4, 1, 2, 3, 4, 5};

std::list<int> values = { 10, 20, 30, 40, 50 };
std::deque<int> numbers3 = { 1, 2, 3, 4, 5 };
auto iter3 = numbers3.cbegin(); // итератор указывает на первый элемент
// добавляем в начало все элементы из values
numbers3.insert(iter3, values.begin(), values.end());
//numbers3 = { 10, 20, 30, 40, 50, 1, 2, 3, 4, 5};

std::deque<int> numbers4 = { 1, 2, 3, 4, 5 };
auto iter4 = numbers4.cend(); // итератор указывает на позицию за последним элементом
// добавляем после последнего элемента список { 21, 22, 23 }
numbers4.insert(iter4, { 21, 22, 23 });
//numbers4 = { 1, 2, 3, 4, 5, 21, 22, 23};
При добавлении в контейнер deque следует учитывать, что добавление может сделать недействительными все итераторы, указатели и ссылки на элементы контейнера.

Удаление элементов
Для удаления элементов из контейнера deque используются следующие функции:

clear(p): удаляет все элементы

pop_back(): удаляет последний элемент

pop_front(): удаляет первый элемент

erase(p): удаляет элемент, на который указывает итератор p. Возвращает итератор на элемент, следующий после удаленного, или на конец контейнера, если удален последний элемент

erase(begin, end): удаляет элементы из диапазона, на начало и конец которого указывают итераторы begin и end. Возвращает итератор на элемент, следующий после последнего удаленного, или на конец контейнера, если удален последний элемент

Применение функций:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::deque<int> numbers = { 1, 2, 3, 4, 5 };
numbers.pop_front(); // numbers = { 2, 3, 4, 5 }
numbers.pop_back(); // numbers = { 2, 3, 4 }
numbers.clear(); // numbers ={}

numbers = { 1, 2, 3, 4, 5 };
auto iter = numbers.cbegin(); // указатель на первый элемент
numbers.erase(iter); // удаляем первый элемент
// numbers = { 2, 4, 5, 6 }

numbers = { 1, 2, 3, 4, 5 };
auto begin = numbers.begin(); // указатель на первый элемент
auto end = numbers.end(); // указатель на последний элемент
numbers.erase(++begin, --end); // удаляем со второго элемента до последнего
//numbers = {1, 5}
При удалении стоит учитывать, что удаление элементов из любой позиции (за исключением удаления первого и последнего элементов) делает все итераторы, указатели и ссылки на элементы deque недействительными.