Почему std :: queue использует std :: dequeue в качестве основного контейнера по умолчанию?
Как читаешь cplusplus.com, std::queue реализован следующим образом:
очереди реализованы в виде контейнеров-адаптеров, которые являются классами, которые
использовать инкапсулированный объект определенного класса контейнера в качестве его
базовый контейнер, предоставляя определенный набор функций-членов
получить доступ к его элементам. Элементы выталкиваются в «зад»
конкретный контейнер и выскочил из его «фронта».Базовый контейнер может быть одним из стандартных контейнерных классов
шаблон или какой-то другой специально разработанный класс контейнера. это
Базовый контейнер должен поддерживать как минимум следующие операции:……
Стандартные контейнерные классы Deque а также список выполнить эти
требования. По умолчанию, если класс контейнера не указан для
конкретный экземпляр класса очереди, стандартный контейнер Deque является
используемый.
Я не понимаю, почему Deque (двусторонняя очередь на стероидах) используется здесь по умолчанию вместо список (который является двусвязным списком).
Мне кажется, что std::deque это слишком много: это двусторонняя очередь, но она также имеет постоянный доступ к элементам и многие другие функции; будучи в основном полнофункциональным std :: vector bar, гарантия «элементы хранятся непрерывно в памяти».
Как нормальный std::queue только очень мало возможных операций, мне кажется, что двусвязный список должен быть намного более эффективным, так как требуется гораздо меньше сантехники, которая должна происходить внутри.
Почему тогда std::queue реализовано с использованием std::deque по умолчанию вместо std::list?
Решение
Хватит думать о list как «Это неудобно в использовании и не имеет кучу полезных функций, поэтому он должен быть лучшим выбором, когда мне не нужны эти функции».
list реализован в виде двусвязного списка с кэшированным счетчиком. Есть узкий набор ситуаций, где это оптимально; когда вам нужна действительно сильная стабильность ссылок / указателей / итераторов. Когда вы стираете и вставляете в середину контейнера на порядки чаще, чем вы повторяете в середина контейнера.
И это об этом.
std Типы данных были в основном реализованы, затем проанализированы их производительность и другие характеристики, затем был написан стандарт, в котором говорилось: «Вы должны гарантировать эти требования». Немного места для маневра осталось.
Поэтому, когда они написали queueкто-то, вероятно, рассказал, как list а также deque выполнил и обнаружил, насколько быстрее deque был, так использовал deque по умолчанию.
На практике кто-то может отправить deque с ужасной производительностью (например, MSVC имеет крошечный размер блока), но делает его хуже, чем требуется для std::list было бы сложно. list в основном требуется один узел на элемент, и это заставляет кэши памяти плакать.
Другие решения
Причина в том, что deque на несколько порядков быстрее, чем list. Список распределяет каждый элемент отдельно, а deque выделяет большие порции элементов.
Преимущество списка состоит в том, что можно удалить элементы посередине, но очередь не требует этой функции.