#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);
Помимо того факта, что использование контейнера с непрерывной памятью в качестве базового контейнера std::queue
значительно ухудшило бы производительность операций массового обслуживания, приведенный выше фрагмент кода вполне приемлем и компилируется. Однако, если мы вызываем std::queue::pop
функцию-член (например, Q.pop();
), программа не может скомпилироваться, и компилятор справедливо жалуется, что у std::vector
нее нет функции-члена pop_front
.
Вопросы:
- Почему это
std::vector
приемлемо в качестве базового контейнера для,std::queue
поскольку оно не удовлетворяетstd::queue
критериям? - Разве не хватает магии метапрограммирования, чтобы проверить, соответствует ли базовый контейнер
std::queue
необходимым критериям в строке определения очереди (например,std::queue<int, std::vector<int>> Q;
)? - Может ли появление 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) почти всегда превосходят реализации очереди на основе списков.
Попробуйте сами.
Причина, по которой это обычно так, связана с предсказуемостью непрерывного доступа к памяти, поскольку это связано с современным управлением кэшем процессора: последовательный доступ к массиву гораздо более предсказуем (для предварительной загрузки кэша), чем к узлам списка.
Даже Бьярне Страуструп советует попробовать векторные решения для списков, потому что на современном оборудовании они, как правило, работают лучше.