[БЕЗ_ЗВУКА] Обсудим еще один контейнер языка C++.

Возможно, некоторые из вас знакомы с таким абстрактным понятием, как очередь.

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

Соответственно новые люди приходят в конец очереди, а люди,

которых только что обслужили, уходят из начала очереди.

Или может быть очередь запросов к какому-то сервису.

Например, опять же, новые запросы приходят в конец,

ждут своей очереди, и как только их обработали, уходят из начала.

Как нам эту структуру данных реализовать?

Например, можно попробовать взять вектор.

Но если вы хотите реализовать очередь с помощью вектора,

новый запрос вы будете добавлять с помощью push_back, а удалять запрос вам придется

с помощью удаления из начала вектора, то есть вызывать erase(begin).

Я уже говорил неоднократно, что элементы в векторе хранятся подряд,

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

Давайте увидим, почему.

Вот у нас есть вектор, опять же, из наших языков программирования.

Я вызываю erase(begin).

begin — это Python, указывает на Python,

соответственно я должен удалить этот элемент.

Я его удаляю, и на его месте образуется пустота.

Вектор устроен так, что он не допускает пустот внутри себя, он гарантирует,

что элементы хранятся подряд, за счет этого он очень эффективен.

Поэтому эту пустоту надо заполнить,

а именно подвинуть первый элемент на место нулевого.

Я подвинул C++.

Затем я должен подвинуть, у меня опять образовалась пустота,

я должен ее заполнить следующим элементом.

Так я подвинул C, Java и C#.

И наконец я должен подтянуть конец вектора, уменьшить его размер.

Мы увидели, что удаление из вектора

потребовало прохода по всему вектору, и поэтому оно работает долго.

Как нам оптимизировать эту операцию?

Что нам использовать, чтобы удалять из начала быстрее?

Надо использовать специальный контейнер, контейнер называется deque.

deque от слова double-ended queue, двусторонняя очередь.

Это не просто очередь, действительно.

Он умеет быстро удалять из начала, добавлять в начало,

удалять из конца и добавлять в конец с помощью методов push_back, pop_back,

нам известных, и push_front, pop_front, которые мы сейчас только что узнали.

При этом он устроен хитро, там элементы хранятся подряд, но не всегда.

За счет этого он умеет быстро добавлять в начало,

и при этом мы можем быстро обращаться к конкретному элементу deque по его индексу.

Но раз уж я говорю, что из deque удалять из начала быстро,

а из вектора долго, давайте я это продемонстрирую.

Создам какой-нибудь вектор из чисел,

вектор чисел, назову его просто v,

какого-то размера n, а размер я считаю.

Значит, я ввожу размер вектора n, а теперь я попробую

его очистить полностью, удаляя элементы из начала, а не из конца.

Как я это напишу?

Я напишу цикл while, пока у меня вектор не пуст,

while (!v.empty()),

я буду удалять с помощью метода erase элемент из начала,

полученный с помощью функции begin.

И как только у меня всё удалится, я выведу строчку empty,

которая будет символизировать, что все готово.

Давайте я этот код скомпилирую, запущу,

и теперь надо ввести размер вектора.

Давайте, скажем, у меня будет вектор размера 25 000.

25 000 элементов изначально будут векторы.

Затем, когда я удаляю...

Вот у меня вектор быстренько очистился.

Давайте, например, 70 000.

Вот вектор очищается, вот мы даже какое-то время ждали, пока он очищался.

Соответственно, мы сначала удалили первый элемент, всё подвинули,

удалили второй элемент, всё подвинули и так далее.

Может быть, убедительнее будет, если размер будет 80 000.

Ждем, ждем, дождались.

А теперь я попробую вместо вектора использовать deque,

подключив библиотеку deque.

[ЗВУК] Снова компилирую.

Запускаю.

И ввожу 80 000.

Мгновенно очистилось, как и обещали.

Более того, у deque даже erase(begin) работает быстро,

не говоря уже о pop_front.

pop_front.

Перепишем pop_front.

Снова скомпилируем.

Запустим.

Введем 80 000.

Увидим, что мгновенно все удалилось из deque.

Итак, мы получили контейнер, у которого можно быстро удалять из начала,

быстро добавлять в начало и то же самое делать с концом.

Получается, что deque умеет больше, и вследствие этого он чуть менее эффективен.

Если вам достаточно вектора, достаточно push_back и pop_back, используйте вектор.

Если вам не нужны push_front, pop_front, deque использовать не нужно.

Но зато есть, наоборот, дополнительный специальный контейнер — очередь.

Если вам не нужен deque, вам нужно только добавлять в конец и удалять из начала,

то вы можете просто использовать queue, и у нее будет ограниченная функциональность.

У нее будут лишь методы push и pop,

чтобы добавить в один конец и удалить из другого конца, методы front и back,

чтобы обращаться к элементам на концах, и методы size и empty.

По очереди нельзя даже поитерироваться.

Но вообще говоря, исходная абстрактная концепция очереди такова,

что нужно уметь делать лишь такие операции.

Вот такие операции вам предоставляет queue,

становятся доступными после подключения модуля queue.

Кроме того, возможно, некоторые из вас знакомы со stack — это такая структура

данных, у которой можно лишь добавлять в конец и удалять из конца.

Если вам не нужно обращение к конкретному элементу, тогда, наверное,

вам не нужен вектор, вы прямо используйте stack, подключайте модуль stack.

И у stack есть лишь push, pop, top, empty и size.

Итак, мы узнали что есть контейнер deque,

который позволяет быстро удалять из начала и быстро добавлять в начало.

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

вы можете использовать очередь, у которой есть push и pop, и соответственно stack,

у которого добавление и удаление только из одного конца.

Стек, очередь и дек

Основы разработки на C++: жёлтый пояс

Rencontrer les enseignants