我正在研究一种外部排序算法,它使用std::queue并且必须小心地限制其内存使用量.我注意到在合并阶段(使用几个std::queue固定长度),我的内存使用量增加到我预期的2.5倍左右.由于std::queue默认情况下使用std::deque它作为其底层容器,因此我运行了一些测试std::deque以确定其内存开销.以下是在发布模式下在VC++ 9上运行的结果,具有64位进程:
当向chara 添加100,000,000 s时std::deque,内存使用量增长到252,216K.请注意,100M chars(1字节)应占用97,656K,因此这是154,560K的开销.
我用doubles(8字节)重复测试,看到内存增长到1,976,676K,而100M doubles应该占用781,250K,开销为1,195,426K!
现在我明白这std::deque通常是作为"块"的链表实现的.如果这是真的,那么为什么开销与元素大小成比例(因为指针大小当然应该固定在8个字节)？为什么这么大呢？
任何人都可以解释为什么要std::deque使用如此多的危险记忆？我想我应该切换我的std::queue底层容器,std::vector因为没有开销(考虑到适当的大小reserve).我认为它的好处std::deque在很大程度上取决于它有如此巨大的开销(导致缓存未命中,页面错误等),并且std::vector鉴于整体内存使用情况,复制元素的成本可能会更低太低了.这只是std::deque微软的糟糕实现吗？