|
Очередь deque библиотеки STL языка C++Курс по структурам данных: https://stepik.org/a/134212 Мы продолжаем знакомство с очередями. На этом занятии разберем работу контейнера (класс) deque из стандартной библиотеки шаблонов STL языка С++. Напомню, что этот контейтер реализует функционал двухсторонней очереди, то есть, возможность добавления и удаления элементов и в конец и в начало. Однако в С++ очередь имеет особую реализацию в виде гибрида двусвязного списка и динамических массивов:
Здесь значения элементов 0, 1, 2, … совпадают с их индексами в этой структуре данных. То есть, в нашем примере, первые три значения 0, 1, 2 хранятся в первом массиве (первого элемента двусвязного списка), следующие три значения – во втором массиве (и втором элементе списка) и так далее. Для чего понадобилось определять такую более сложную структуру для хранения данных в очереди? Дело в том, что в пределах одного массива мы достаточно быстро можем обратиться к произвольному элементу – за время O(1). Значит, если нам нужно получить значение k-го элемента, то вначале определяем элемент списка, в котором он находится: j = k // size_array (здесь оператор // - целочисленное деление; size_array – максимальное число элементов в массивах, массивы полагаем равной длины во всех объектах двусвязного списка). Затем в массиве j-го объекта переходим к нужному элементу массива: i = k % size_array (здесь оператор % - вычисление целого остатка от деления). Все, в итоге, нам нужно перебрать только первые j значений двусвязного списка, вместо k, если бы использовался обычный список. Это заметно ускоряет доступ к отдельным элементам очереди. И в этом главная причина использования такой структуры данных в объекте deque языка С++. Но есть и недостатки в сравнении с обычными двусвязными списками. Операции добавления/удаления граничных элементов работают несколько дольше, т.к. приходится смещать элементы динамических массивов. Также несколько больше операций может занимать и вставка/удаление промежуточных значений. Поэтому выбор, что использовать в качестве хранилища данных двусторонней очереди, делает сам разработчик алгоритма, опираясь на собственные соображения. Я здесь лишь констатирую факт, что в С++ применяется гибридная схема двусвязного списка с динамическими массивами. Использование класса deque в С++Для использования в программе класса deque вначале нужно подключить заголовок с таким же названием: #include <deque>После этого в пространстве имен std появится класс deque: int main() { std::deque<int> dq; return 0; } Чтобы все время не писать std:: подключим пространство имен std в функции main(): using namespace std;Итак, команда deque<int> dq; создает пустую очередь (без элементов) с типом данных в элементах int. Если нужно инициализировать очередь некоторыми начальными значениями, то это можно сделать так: deque<int> dq = { 1, 2, 3 }; или так: deque<int> dq { 1, 2, 3 }; Давайте теперь отобразим элементы списка в консоли. Для этого я воспользуюсь циклом for следующим образом: for (unsigned int i = 0; i < dq.size(); ++i) cout << dq[i] << " "; cout << endl; Здесь метод size() возвращает общее число элементов в списке. А обращение к значению отдельного элемента осуществляется по индексу, используя оператор квадратные скобки. Аналогичный результат можно получить с помощью метода at(): for (unsigned int i = 0; i < dq.size(); ++i) cout << dq.at(i) << " "; Однако, обратите внимание, доступ к отдельным элементам объекта deque требует O(n) операций, где n – число объектов в двусвязном списке. Поэтому, лучше выводить последовательные значения, используя механизм итераторов, следующим образом: for (auto it = dq.cbegin(); it != dq.cend(); ++it) cout << *it << " "; Такая конструкция будет работать быстрее и выигрыш становится тем больше, чем больше элементов в списке. С методами cbegin(), cend(), а также begin() и end() мы с вами уже знакомы, когда рассматривали двусвязные списки. Поэтому повторяться здесь не буду. Далее, для получения значения первого или последнего элементов используются методы front() и back(): cout << dq.front() << endl; cout << dq.back() << endl; Для добавления новых элементов в начало или конец списка – методы push_front() и push_back(): dq.push_front(0); dq.push_back(10); Удаление первого или последнего элемента осуществляется с помощью методов pop_front() и pop_back(): dq.pop_front(); dq.pop_back(); Обратите внимание, эти методы не возвращают значений удаляемых элементов. За это отвечают ранее рассмотренные методы front() и back(). Также объект deque поддерживает операции вставки и удаления промежуточных элементов. Они реализуются методами insert() и erase() и работают по тому же принципу, что и в двусвязных списках: auto pos_it = dq.cbegin(); int n = 1; for (int k = 0; k < n; ++pos_it, ++k); dq.insert(pos_it, 100); И метод erase(): auto pos_it = dq.cbegin(); dq.erase(++pos_it); Я подробно на них не останавливаюсь, т.к. мы уже их рассматривали в двусвязных списках. И последний метод, что мы рассмотрим на этом занятии – это clear() для очистки (удаления) всех элементов очереди: dq.clear(); ЗаключениеВот основные операции при работе с элементами объекта deque языка С++. Конечно, мы рассмотрели не все доступные операции, но с ними можно подробно ознакомиться, например, на ресурсе: https://en.cppreference.com/w/cpp/container/deque А на данный момент вы должны себе представлять, как работают следующие методы класса deque:
Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
