Блог

Главная - Вопросы по программированию - Почему очередь принимает vector в качестве своего базового контейнера?

Почему очередь принимает vector в качестве своего базового контейнера?

#c #c 11 #stl #c 14

#c #c 11 #stl #c 14

Вопрос:

Рассмотрим следующий фрагмент кода:

 std::queue<int, std::vector<int>> Q;
Q.push(1);
Q.push(2);

Live Demo

Помимо того факта, что использование контейнера с непрерывной памятью в качестве базового контейнера std::queue значительно ухудшило бы производительность операций массового обслуживания, приведенный выше фрагмент кода вполне приемлем и компилируется. Однако, если мы вызываем std::queue::pop функцию-член (например, Q.pop(); ), программа не может скомпилироваться, и компилятор справедливо жалуется, что у std::vector нее нет функции-члена pop_front .

Live Demo

Вопросы:

  1. Почему это std::vector приемлемо в качестве базового контейнера для, std::queue поскольку оно не удовлетворяет std::queue критериям?
  2. Разве не хватает магии метапрограммирования, чтобы проверить, соответствует ли базовый контейнер std::queue необходимым критериям в строке определения очереди (например, std::queue<int, std::vector<int>> Q; )?
  3. Может ли появление concepts-lite, возможно, в C 17, решить эту проблему?

Комментарии:

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

2. @chris: Он, очевидно, знает об этом. На самом деле он спрашивает, почему код компилируется и как предотвратить это.

3. @ChristianHackl, Это отвечает на вопрос 1; это неприемлемо, но проверять это не queue входит в обязанности. Это также касается 2 и 3, говоря, что да, можно проверить функции. Учитывая, что Boost выполняет проверку концепции с помощью синтаксиса, подобного концепции, требование SequenceContainer также должно быть возможно проверить.

4. @chris: Я видел только первое предложение вашего комментария, прежде чем вы его отредактировали 🙂

5. @ChristianHackl, я не помню, чтобы редактировал это O_o, но я признаю, что я это сделал.

Ответ №1:

Почему std::vector приемлем в качестве базового контейнера для std::queue, поскольку он не удовлетворяет критериям std::queue?

Это не так.

Разве не хватает магии метапрограммирования, чтобы проверить, соответствует ли базовый контейнер std::queue необходимым критериям в строке определения очереди (например, std::queue<int, std::vector<int>> Q; )?

Это предложение не имеет смысла, но если вы спрашиваете, возможно ли диагностировать это при создании экземпляра, ответ — да. Однако это в значительной степени было бы пустой тратой времени. Для сравнения обратите внимание, что выход за границы std::vector::operator[] также является вашей ответственностью и не приведет к диагностике.

Может ли появление concepts-lite, возможно, в C 17, решить эту проблему?

Насколько это вообще «проблема», да.

Ответ №2:

Теория в сторону: на практике реализации очереди на основе векторов (с использованием push_back / erase) почти всегда превосходят реализации очереди на основе списков.

Попробуйте сами.

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

Даже Бьярне Страуструп советует попробовать векторные решения для списков, потому что на современном оборудовании они, как правило, работают лучше.