考虑以下代码:
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;
)行必要的标准? - 可能在c++ 17中出现的概念简化能解决这个问题吗?
既然std::vector不满足std::queue的条件,为什么std::vector可以作为std::queue的底层容器?
。
在检查std::queue的底层容器是否满足队列定义行(例如,std::queue<int, std::vector<int>> Q;
)的必要条件时,是不是缺少一些元编程的魔力?
这个句子没有意义,但是如果你问是否有可能在实例化时诊断这个问题,答案是肯定的。不过,这在很大程度上是浪费时间。为了进行比较,请注意越界std::vector::operator[]
也是您的责任,并且不会导致诊断。
可能在c++ 17中出现的概念简化能解决这个问题吗?
只要这是一个"问题",是的。
理论:在实践中,基于向量的队列实现(使用push_back/erase)几乎总是优于基于列表的队列实现。
你自己试试。
这种情况的原因通常是由于连续内存访问的可预测性,因为它与今天的CPU缓存管理有关:顺序数组访问远比列表节点更可预测(对于缓存预加载)。
甚至Bjarne Stroustrup也建议尝试基于向量的列表解决方案,因为在今天的硬件上,它们往往做得更好。