Deque представляет двухстороннюю очередь. Для использования данного контейнера нужно подключить заголовочный файл deque.
Способы создания двухсторонней очереди:
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(): возвращает последний элемент
#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
}
Стоит отметить, что если мы будем обращаться с помощью операции индексирования по некорректному индексу, который выходит за границы контейнера, то результат будет неопредленным:
std::deque<int> numbers { 1, 2, 3, 4, 5 };
int eighth = numbers[7];
В этом случае использование функции at() является более предпочтительным, так как при обращении по некорректному индексу она генерирует исключение out_of_range:
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers { 1, 2, 3, 4, 5};
try
{
int n { numbers.at(7) };
std::cout << n << std::endl;
}
catch (const std::out_of_range&)
{
std::cout << "Incorrect index" << std::endl;
}
}
Также в цикле или с помощью итераторов можно перебрать элементы контейнера:
#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 (unsigned i {}; 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, если в очереди есть элементы:
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
Применение функции:
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
Применение функции:
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() обменивает значениями две очереди:
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():
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():
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():
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::deque<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. Возвращает итератор на элемент, следующий после последнего удаленного, или на конец контейнера, если удален последний элемент
Применение функций:
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 недействительными.
Таким образом, deque, как и vector и array, поддерживает произвольный доступ к элементам контейнера, но в отличие от вектора также поддерживает добавление в начало контейнера. Кроме того, во внутренней реализации deque при изменении размера не выделяет новый массив в памяти для вмещения нового набора элементов, а манипулирует указателями.