что такое ассоциативный контейнер

Снова про STL: контейнеры

В предыдущей заметке речь шла о массивах как прототипе и прародителе контейнеров. Теперь дошла очередь до собственно контейнерных классов и поддерживающих их библиотек.

Под термином библиотека стандартных шаблонов (STL, Standard Template Library) понимают набор интерфейсов и компонентов, первоначально разработанных Александром Степановым, Менг Ли и другими сотрудниками AT&T Bell Laboratories и Hewlett-Packard Research Laboratories в начале 90-х годов (хотя и позже ещё весьма многие приложили руку к тому, что стало на сегодня стандартным компонентом C++). Далее библиотека STL перешла в собственность компании SGI, а также была включена как компонент в набор библиотек Boost. И наконец библиотека STL вошла в стандарты C++ 1998 и 2003 годов (ISO/IEC 14882:1998 и ISO/IEC 14882:2003) и с тех пор считается одной из составных частей стандартной библиотек C++.

Стандарт не называет эту часть библиотеки STL, но эту хронологию хорошо бы учитывать, разбираясь с какой версией компилятора, языка и литературы вы имеете дело — в процессе сокращения HP STL до размеров, подходящих для стандартизации, часть алгоритмов и функторов выпали из состава библиотеки, а кое-что, со временем, и добавляется (например, расширение набора переопределенных прототипов некоторых методов контейнеров). По тексту будет использоваться традиционное название STL только чтобы было ясно какую часть стандартной библиотеки C++ мы имеем в виду.

Первоначальной целью STL (это хорошо видно из хронологии комментариев в заголовочных файлах) было создание боле гибкой модели регулярных контейнеров по сравнению с массивами и обобщение на них некоторых широко используемых алгоритмов (таких как поиск, сортировка и некоторых других). Но затея оказалась плодотворнее первоначальных намерений, и была существенно расширена. STL вводит ряд понятий и структур данных, которые почти во всех случаях позволяют сильно упростить программный код. Вводятся следующие категории понятий:

Центральным понятием STL, вокруг которого крутится всё остальное, это контейнер (ещё используют термин коллекция). Контейнер — это набор некоторого количества обязательно однотипных элементов, упакованных в контейнер определённым образом. Простейшим прототипом контейнера в классическом языке C++ является массив. Тот способ, которым элементы упаковываются в контейнер и определяет тип контейнера и особенности работы с элементами в таком контейнере. STL вводит целый ряд разнообразных типов контейнеров, основные из них:

элементов типа float. Далее мы видим такие методы класса vector как max_size() — максимально возможная длина векторов вообще (константа реализации), size() — текущий размер (число элементов) вектора, capacity() — текущая ёмкость вектора, максимальное число элементов, которое может быть помещено в вектор в текущем его размещении. Выполнение этого фрагмента даст что-то примерно следующее (детали могут различаться в зависимости от реализации):

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

Примечание: Показанное выше удвоение ёмкости вектора при переразмещении — это характерное поведение для реализации библиотек компилятора GCC. Но точный алгоритм резервирования ёмкости под будущие элементы стандарт оставляет на волю реализатора, поэтому на него нельзя рассчитывать, и описан он здесь только для качественного понимания картины (реализации Visual Studio ведут себя по-другому, резервируя только небольшой избыток… это вы изучите сами).

Отметим на дальнейшее, пока без комментариев, то важное обстоятельство, что операции помещения элементов в контейнер выполняет копирование элемента, что влечёт за собой а).требование наличия копирующего конструктора для типа элементов и б).для структурных элементов это может привести к заметным затратам производительности.

Таким образом мы получили эквивалент массива C++, размер которого (size()) динамически меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается ни в коем случае не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора (симметрично, метод pop_back() выталкивает последний элемент из массива и уменьшает его size()). Другой способ изменить размер вектора — это сразу вызвать методы resize() под нужный размер. Именно потому, что размер вектора, в отличие от массива, может динамически меняться, для вектора предусмотрено 2 разных способа индексации: как операция [ i ] и как метод-функция at( i ). Они различаются: метод at() проверяет текущий размер вектора size(), и при индексации за его границу возбуждает исключение. Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее. Метод at() позволяет нам контролировать выход за границы вектора и либо квалифицировать это как логическую ошибку, либо корректировать текущий размер контейнера под потребность, как в вот таком фрагменте (здесь попыток доступа вдвое больше, чем реально выполненных операций):

Стандарт C++11 привносит дополнительные выразительные средства, такие, например, как списки инициализации и выводимость типов, которые намного упрощают работу с контейнерами (и даже делают ненужными старые привычные приёмы записи). Вот как может описываться матрица, когда одновременно описываются её а). конфигурация (квадратная, хотя может быть прямоугольная и даже треугольная), b). размерность (3х3) и c). инициализирующие значения:

А заодно, здесь же показана работа с векторами (транспонирование квадратной матрицы и вывод в выходной поток) как с псевдо-массивами (пользуясь только индексированием), чем вектора, по существу, и являются (в частности, показано как тип элемента вектор определяется на основании выводимого типа по стандарту C++11):

Примечание: В рамках того, что мы уже знаем о векторах, возникает иногда вопрос: а как строго должен определяться тип возвращаемого size() результата (чтобы избежать зависимости от платформы) и, соответственно, любых переменных циклов, оперирующих с размером вектора? Временами от блюстителей чистоты синтаксиса следует ответ, что это должен быть size_t, и этот ответ — неверный (тем более, что для многих платформ size_t и определяется как unsigned int). Если вы захотите записать абсолютно строгого определение типа size() вектора, то строку в примере выше следует записать вот так:

Или, полагаясь на выводимость типов C++11, вот так:

Отметив здесь этот тонкий нюанс (приняв к сведению), мы не станем его применять далее, во избежания лишней громоздкости примеров, а будем использовать для размерностей просто unsigned.

Источник

СОДЕРЖАНИЕ

Дизайн

Характеристики

И map, и set позволяют вставить в контейнер только один экземпляр ключа или элемента. Если требуется несколько экземпляров элементов, используйте multimap или multiset.

И карты, и наборы поддерживают двунаправленные итераторы. Дополнительные сведения об итераторах см. В разделе Итераторы.

Хотя официально hash_map и hash_set не являются частью стандарта STL, они обычно используются для улучшения времени поиска. Эти контейнеры хранят свои элементы в виде хэш-таблицы, где каждая запись таблицы содержит двунаправленный связанный список элементов. Чтобы обеспечить максимально быстрое время поиска, убедитесь, что алгоритм хеширования для ваших элементов возвращает равномерно распределенные хеш-значения.

Представление

Обзор функций

использование

В следующем коде показано, как использовать map для подсчета вхождений слов. Он использует слово как ключ, а счетчик как значение.

При выполнении пользователь сначала набирает серию слов, разделенных пробелами, и слово «конец», чтобы обозначить конец ввода; затем пользователь может вводить слова, чтобы узнать, сколько раз каждое слово встречалось в предыдущей серии.

Приведенный выше пример также демонстрирует, что operator [] вставляет новые объекты (используя конструктор по умолчанию) на карту, если ни один из них не связан с ключом. Таким образом, интегральные типы инициализируются нулем, строки инициализируются пустыми строками и т. Д.

Следующий пример иллюстрирует вставку элементов в карту с помощью функции вставки и поиск ключа с помощью итератора карты и функции поиска:

В приведенном выше примере с помощью функции вставки вводятся шесть элементов, а затем первый элемент удаляется. Затем выводится размер карты. Затем пользователю предлагается ввести ключ для поиска. Используя итератор, функция find ищет элемент с заданным ключом. Если он находит ключ, программа печатает значение элемента. Если он не находит его, возвращается итератор до конца карты, и он выводит, что ключ не может быть найден. Наконец, все элементы в дереве стираются.

Итераторы

Карты могут использовать итераторы, чтобы указывать на определенные элементы в контейнере. Итератор может обращаться как к ключу, так и к отображенному значению элемента:

Ниже приведен пример цикла по карте для отображения всех ключей и значений с использованием итераторов:

Для компиляции приведенного выше примера на компиляторе GCC необходимо использовать специальный стандартный флаг выбора.

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

Источник

Многопоточные ассоциативные контейнеры в C++. Доклад Яндекса

Из доклада старшего разработчика Сергея Мурылёва можно узнать о многопоточном ассоциативном контейнере для стандартной библиотеки, который разрабатывают в рамках WG21. Сергей рассказал о плюсах и минусах популярных решений этой задачи и о пути, выбранном разработчиками.

— Вы, наверное, уже догадались из названия, что сегодняшний доклад будет о том, как мы в рамках Рабочей группы 21 делали свой контейнер, похожий на std::unordered_map, но для многопоточной среды.

Во многих языках программирования — Java, C#, Python — такое уже есть и довольно широко используется. А в нашем горячо любимом, самом быстром и производительном C++ такого не оказалось. Но мы посовещались и решили такую штуку сделать.

Прежде чем добавить что-то в стандарт, надо подумать, как этим станут пользоваться люди. Потом сделать более правильный интерфейс, который будет с большой вероятностью принят комитетом — желательно, без каких-то поправок. И чтобы в итоге там не было такого, что делали одно, а получилось другое.

Самый известный и широко используемый вариант — кеширование больших тяжелых вычислений. Есть достаточно известный сервис Memcached, который просто кеширует ответы веб-серверов в памяти. Понятно, что сделать примерно то же самое можно на стороне своего приложения, если у тебя есть конкурентный ассоциативный контейнер. У того и другого подхода есть свои плюсы и минусы. Но если такого контейнера у тебя нет, придется либо делать свой велосипед, либо использовать какой-нибудь Memcached.

Следующим популярным случаем использования является дедупликация событий. Я думаю, многие в этой комнате пишут всякие распределенные системы и знают, что часто для связи между компонентами используются распределенные очереди, типа Apache Kafka и Amazon Kinesis. Они отличаются такой особенностью, что у них одно сообщение одному консьюмеру может приходить по несколько раз. Это называется у них at least once delivery, что означает гарантию доставки как минимум один раз: больше можно, меньше нельзя.

Рассмотрим это с точки зрения реальной жизни. Представим, что у нас есть какой-нибудь бэкенд какого-нибудь чатика или соцсети, где происходит обмен сообщениями. Это может привести к тому, что кто-то написал сообщение и кому-то потом пришло на мобильник несколько раз пуш-уведомление. Понятно, что если такое увидят пользователи, они этому не обрадуются. Утверждается, что эту проблему можно решить при помощи такого замечательного многопоточного контейнера.

Следующий, уже не так часто используемый случай — когда нам надо просто на стороне сервера что-то где-то сохранить, какие-то метаданные для пользователя. Например, мы можем сохранить время, когда пользователь последний раз проходил аутентификацию, чтобы понимать, когда следующий раз у него спрашивать логин и пароль.

Последний вариант на этом слайде — подсчет статистики. Из реальных применений в жизни можно привести пример использования в виртуальной машине от Facebook. Они сделали целую виртуальную машину, чтобы оптимизировать PHP и у себя в этой виртуальной машине они для всех встроенных функций стараются записывать в многопоточную хэш-таблицу аргументы, с которыми они назывались. И если у них в кэше есть результат, то они его пытаются просто сразу отдать и ничего не считать.

_{Ссылка со слайда}

Добавить что-то большое и сложное в стандарт — не простая и не быстрая работа. Как правило, если происходит добавление чего-то большого, оно проходит через техническую спецификацию. В данный момент в стандарте идет большое движение по расширению поддержки многопоточности в стандартной библиотеке. И конкретно сейчас туда едет proposal P0260R3 про многопоточные очереди. Этот proposal — про очень похожую на нас структуру данных, и решения в дизайне у нас во многом похожи.

Собственно говоря, одним из основных концепций их дизайна является то, что у них интерфейс отличается от стандартного std::queue. В чем суть? Если посмотреть на стандартную очередь, то, чтобы из нее извлечь элемент, надо сделать две операции. Надо сделать операцию front, чтобы считать, и операцию pop, чтобы удалить. Если мы работаем в условиях многопоточности, то у нас может произойти какая-то операция над очередью между этими двумя вызовами, и может получиться так, что мы считаем один элемент, а удалим уже другой, что кажется концептуально неверным. Поэтому эти два вызова там заменили на один, и добавили еще немного вызовов из разряда try push и try pop. Но общая идея такова, что многопоточный контейнер не будет таким же, как обычный по интерфейсу.

Еще у многопоточных очередей есть много разных имплементаций, которые решают несколько разных задач. Самая частая задача, это задача производителей и потребителей, когда у нас есть сколько-то потоков, которые производят какие-то задачи и есть сколько-то потоков, которые берут задачи из очереди и их обрабатывают.

Второй случай, это когда нам надо иметь просто какую-то синхронизованную очередь. В случае с производителями и потребителями у нас получается очередь, которая ограничена сверху и снизу. Если мы пытаемся, условно говоря, извлечь из пустой очереди, то мы переходим в состояние ожидание. И то же самое примерно происходит, если мы пытаемся добавить что-то, что не влезает по размеру в очередь.

Также в этом proposal’e описано, что у нас есть отдельно сделанный интерфейс, который позволяет различить, какая у нас имплементация внутри блокирующая, или lock free. То, что тут везде в proposal пишется lock free, на самом деле в книжках это пишется, как wait free. Это означает, что у нас алгоритм отрабатывает за фиксированное количество операций. Lock free там означает немного другое, но это не суть.

Посмотрим на типичную схему того, как может выглядеть имплементация нашей хэш-таблицы, если она блокируется. Она у нас разбита на какое-то количество сегментов. Каждый сегмент, как правило, содержит какую-то блокировку, типа Mutex, Spinlock, или чего-нибудь еще более хитрого. И помимо Mutex или Spinlock она еще содержит внутри себя обычную хэш-таблицу, которая как раз таки этим делом защищена.

На данной картинке у нас нарисована хэш-таблица, которая сделана на списках. На самом деле, в нашей референсной имплементации мы написали хэш-таблицу с открытой адресацией из соображений производительности. Соображения производительности, в принципе, такие же, почему std::vector быстрее, чем std::list, потому что vector, условно говоря, хранится последовательно в памяти. Когда мы по нему идем, у нас происходит последовательный доступ, который хорошо кешируется. Если мы используем какие-то листы, то у нас будет много всяких прыжков между разными участками памяти. И все это дело, как правило, заканчивается тем, что мы теряем производительность.

В самом начале, когда мы хотим найти что-то в этой хэш-таблице, мы берем хэш-код от ключа. Можно его взять по модулю и сделать что-то еще с ним такое, чтобы у нас получился номер сегмента, а уже в сегменте мы ищем, как в обычной хэш-таблице, но мы при этом, естественно, берем блокировку.

_{Ссылка со слайда}

Основные идеи нашего дизайна. Конечно же, мы тоже сделали интерфейс, который не совпадает с std::unordered_map. Причина такая. У нас, например, в обычном std::unordered_map есть такая замечательная штука, как итераторы. Во-первых, не все имплементации могут их нормально поддержать. А те, которые могут поддержать, как правило, это какие-то lock free имплементации, которые требуют наличия либо garbage collection, либо каких-нибудь умных указателей, которые подчищают за ней память.

Помимо этого там есть еще несколько других типов операций, которые мы выкинули. На самом деле, итераторы, они во многих местах есть. Например, они есть на Java. Но, как правило, как это ни странно, они там никак не синхронизуются. И если вы попытаетесь что-то с ними сделать из разных потоков, то они могут легко перейти в невалидное состояние, и можно в Java получить exception, а если написать такое на плюсах, то это, скорее всего, будет undefined behavior, что еще хуже. И кстати, на тему undefined behavior: по-моему, товарищи из Facebook в своей библиотеке folly, которая выложена в опенсорс на GitHub, именно так и сделали. Просто скопировали интерфейс с Java и получили такие замечательные итераторы.

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

Следующий концептуальный момент, это мы никогда ни при каких условиях никому наружу не отдаем ссылки и указатели на внутренние объекты. Это как раз таки было сделано с целью того, чтобы предотвратить необходимость наличия garbage collection, и чтобы не энфорсить умные указатели. Понятно, что если мы храним какие-то достаточно большие объекты, хранить их по значению внутри будет невыгодно. Но, в этом случае, мы их всегда можем обернуть их в какие-то умные указатели по своему выбору. И, если мы хотим, например, делать какую-то синхронизацию на значениях, мы можем их обернуть в какой-нибудь boost::synchronised_value.

Мы посмотрели на то, что какое-то время назад у класса shared_ptr убрали метод, который возвращал количество активных ссылок на этот объект. И пришли к выводу, что нам тоже надо выкинуть несколько функций, а именно, size, count, empty, buckets_count, потому что, как только мы возвращаем это значение из функции, оно сразу перестает быть валидным, потому что его кто-то может в этот же момент поменять.

Еще у нас на одном из прошлых заседаний просили, чтобы мы добавили своего рода режим, чтобы можно было обращаться в однопоточном режиме к нашему контейнеру, как к обычному std::unordered_map. Такая семантика позволяет явно отличить, где у нас происходит работа в многопоточном режиме, а где нет. И избежать каких-то неприятных ситуаций, когда люди берут многопоточный контейнер, ожидают, что у них все будет хорошо, берут итераторы, а потом неожиданно оказывается, что все плохо.

_{Ссылка со слайда}

На этом заседании на Гавайях против нас написали целый proposal. 🙂 Нам сказали, что таким вещам не место в стандарте, потому что способов сделать свой многопоточный ассоциативный контейнер существует очень много.

У каждого есть свои плюсы и минусы — и непонятно, как использовать то, что у нас в итоге у нас получится. Как правило, оно используется, когда тебе нужен какой-то экстремальный перформанс. И вроде как наше коробочное решение не подходит, надо оптимизироваться под каждый конкретный случай.

Второй поинт этого proposal был в том, что наш интерфейс не совместим с тем, что запостил Facebook на GitHub из своей стандартной библиотеки.

На самом деле там каких-то особых проблем не было. Там просто был вопрос из разряда «Я не читал, но осуждаю». Просто они посмотрели — интерфейс разный, значит, не совместимый.

Идея proposal была еще и в том, что подобные задачи надо решать при помощи так называемого policy based design, когда необходимо сделать дополнительный шаблонный параметр, в котором можно передавать битовую маску с тем, какие фичи мы хотим включить, а какие выключить. Действительно, это звучит немного диковато и приводит к тому, что у нас получается порядка 2^n имплементаций, где n — количество различных фич.

В коде это выглядит примерно так. У нас есть какой-то параметр и какое-то количество предопределенных констант, которые туда можно передавать. Как ни странно, этот proposal отклонили.

Потому что, на самом деле, комитет уже занял позицию, что таким вещам быть, когда многопоточная очередь прошла через SG1. По этому вопросу даже не было голосования. Но на голосование были выставлены два вопроса.

Первый. Много людей захотели, чтобы мы на стороне нашей референсной имплементации поддержали чтение без взятия любых блокировок. Чтобы у нас было полностью не блокирующее чтение. Это, действительно, имеет смысл: как правило, самый популярный юзкейс — кеширование. И нам очень выгодно иметь быстрое чтение.

Второй момент. Все наслушались предыдущего товарища, который говорил про policy based design. У всех возникла идея — а что, давай я свою идею тоже потолкаю! И все проголосовали за то, чтобы policy based design был. Хотя надо сказать, вся эта история длится достаточно давно, и перед нами этим занимались коллеги из Intel, Арч Робинсон и Антон Малахов. И у них уже было несколько proposals на эту тему. Они как раз таки предлагали добавить lock free-имплементацию на основе алгоритма SeepOrderedList. И у них тоже был policy based design как раз таки с рекламацией памяти.

И этот proposal не понравился Library Evolution Working Group. Его завернули с тем основанием, что у нас просто будет неограниченно расти количество слов в стандарте. Это будет просто невозможно адекватно проревьюить и просто реализовать в коде.

У нас замечаний к самим идеям нет. У нас есть замечания, по большей части, к референсной имплементации. И конечно, у нас есть пара идей, которые можно внести, чтобы было понятнее. Но по сути, мы в следующий раз пойдем примерно с тем же самым proposal. Мы искренне надеемся, что у нас не будет, как с модулями, пять заходов с одним и тем же proposal. Мы искренне верим в себя, и что в следующий заход нас пропустят дальше, и что Library Evolution Working Group все-таки настоит на своем мнении, не даст пропихивать policy based design. Потому что наш оппонент не останавливается. Он решил доказывать всем, что это надо. Но, как говорится, время покажет. У меня все, спасибо за внимание.

Источник

Урок №197. Контейнеры STL

Обновл. 15 Сен 2021 |

Безусловно, наиболее часто используемым функционалом библиотеки STL являются контейнерные классы (или как их еще называют — «контейнеры»). Библиотека STL содержит много разных контейнерных классов, которые можно использовать в разных ситуациях. Если говорить в общем, то контейнеры STL делятся на три основные категории:

Сейчас сделаем их краткий обзор.

Последовательные контейнеры

Последовательные контейнеры (или «контейнеры последовательности») — это контейнерные классы, элементы которых находятся в последовательности. Их определяющей характеристикой является то, что вы можете добавить свой элемент в любое место контейнера. Наиболее распространенным примером последовательного контейнера является массив: при добавлении 4 элементов в массив, эти элементы будут находиться (в массиве) в точно таком же порядке, в котором вы их добавили.

Начиная с C++11, STL содержит 6 контейнеров последовательности:

В следующей программе мы добавляем 5 целых чисел в вектор и с помощью перегруженного оператора индексации [] получаем к ним доступ для их последующего вывода:

Результат выполнения программы:

Класс deque (или просто «дек») — это двусторонняя очередь, реализованная в виде динамического массива, который может расти с обоих концов. Например:

Результат выполнения программы:

List (или просто «список») — это двусвязный список, каждый элемент которого содержит 2 указателя: один указывает на следующий элемент списка, а другой — на предыдущий элемент списка. List предоставляет доступ только к началу и к концу списка — произвольный доступ запрещен. Если вы хотите найти значение где-то в середине, то вы должны начать с одного конца и перебирать каждый элемент списка до тех пор, пока не найдете то, что ищете. Преимуществом двусвязного списка является то, что добавление элементов происходит очень быстро, если вы, конечно, знаете, куда хотите добавлять. Обычно для перебора элементов двусвязного списка используются итераторы.

Хотя о классе string (и wstring) обычно не говорят, как о последовательном контейнере, но он, по сути, таковым является, поскольку его можно рассматривать как вектор с элементами типа char (или wchar).

Ассоциативные контейнеры

set — это контейнер, в котором хранятся только уникальные элементы, и повторения запрещены. Элементы сортируются в соответствии с их значениями.

multiset — это set, но в котором допускаются повторяющиеся элементы.

map (или «ассоциативный массив») — это set, в котором каждый элемент является парой «ключ-значение». «Ключ» используется для сортировки и индексации данных и должен быть уникальным, а «значение» — это фактические данные.

multimap (или «словарь») — это map, который допускает дублирование ключей. Все ключи отсортированы в порядке возрастания, и вы можете посмотреть значение по ключу.

Адаптеры

Адаптеры — это специальные предопределенные контейнерные классы, которые адаптированы для выполнения конкретных заданий. Самое интересное заключается в том, что вы сами можете выбрать, какой последовательный контейнер должен использовать адаптер.

stack (стек) — это контейнерный класс, элементы которого работают по принципу LIFO (англ. «Last In, First Out» = «последним пришел, первым ушел»), т.е. элементы добавляются (вносятся) в конец контейнера и удаляются (выталкиваются) оттуда же (из конца контейнера). Обычно в стеках используется deque в качестве последовательного контейнера по умолчанию (что немного странно, поскольку vector был бы более подходящим вариантом), но вы также можете использовать vector или list.

queue (очередь) — это контейнерный класс, элементы которого работают по принципу FIFO (англ. «First In, First Out» = «первым пришел, первым ушел»), т.е. элементы добавляются (вносятся) в конец контейнера, но удаляются (выталкиваются) из начала контейнера. По умолчанию в очереди используется deque в качестве последовательного контейнера, но также может использоваться и list.

priority_queue (очередь с приоритетом) — это тип очереди, в которой все элементы отсортированы (с помощью оператора сравнения ). При добавлении элемента, он автоматически сортируется. Элемент с наивысшим приоритетом (самый большой элемент) находится в самом начале очереди с приоритетом, также, как и удаление элементов выполняется с самого начала очереди с приоритетом.

На следующем уроке мы рассмотрим итераторы STL.

Источник