哪个STL容器最适合我的需求？我基本上有一个10个元素的宽容器,在这个容器中我不断使用push_back新元素pop_front(大约一百万次).
我目前正在使用a std::deque来执行任务,但是想知道是否std::list会更高效,因为我不需要重新分配自己(或者我可能会误认为std::deque是std::vector？).或者是否有更高效的容器满足我的需求？
PS我不需要随机访问
GMa*_*ckG 181
由于有无数的答案,你可能会感到困惑,但总结一下:
用一个std::queue.原因很简单:它是一个FIFO结构.你想要FIFO,你用一个std::queue.
它使你的意图对任何人,甚至你自己都清楚.A std::list或std::deque不.列表可以在任何地方插入和删除,这不是FIFO结构所要做的,并且deque可以从任一端添加和删除,这也是FIFO结构无法做到的.
这就是你应该使用的原因queue.
现在,您询问了性能.首先,永远记住这个重要的经验法则:良好的代码优先,性能最后.
原因很简单:在清洁和优雅之前追求性能的人几乎总是最后完成.他们的代码变成了一大堆,因为他们已经放弃了所有好的东西,以便真正从中获取任何东西.
通过首先编写好的,可读的代码,大多数性能问题都将自行解决.如果以后你发现你的性能不足,现在可以很容易地为你漂亮,干净的代码添加一个分析器,并找出问题所在.
所有人都说,std::queue只是一个适配器.它提供了安全的界面,但内部使用了不同的容器.您可以选择此底层容器,这样可以提供很大的灵活性.
那么,你应该使用哪个底层容器？我们知道,std::list并且std::deque都提供必要的功能(push_back(),pop_front(),和front()),所以我们如何决定？
首先,要了解分配(和解除分配)内存并不是一件容易的事,通常,因为它涉及到操作系统并要求它做某事.A list必须在每次添加内容时分配内存,并在内存消失时释放内存.
deque另一方面,A 以块的形式分配.它的分配频率低于a list.可以将其视为列表,但每个内存块可以容纳多个节点.(当然,我建议你真正了解它是如何工作的.)
因此,单独使用它deque应该表现得更好,因为它不经常处理内存.与处理常量大小数据的事实相混合,它可能不必在第一次通过数据后分配,而列表将不断分配和解除分配.
要理解的第二件事是缓存性能.走向RAM很慢,所以当CPU确实需要时,通过将一大块内存带回缓存,它可以最大限度地利用它.因为deque在内存块中分配,所以访问此容器中的元素可能会导致CPU带回容器的其余部分.现在任何进一步的访问deque都会很快,因为数据在缓存中.
这与列表不同,列表中一次分配一个数据.这意味着数据可以遍布内存中的所有位置,并且缓存性能会很差.
因此,考虑到这一点,deque应该是一个更好的选择.这就是使用a时它是默认容器的原因queue.总而言之,这仍然只是一个(非常)有根据的猜测:你必须使用deque一个测试来分析这个代码,而另一个测试则list需要确定.
但请记住:让代码使用干净的界面,然后担心性能.
约翰提出了包装list或deque将导致性能下降的担忧.再一次,他和我可以肯定地说,而不是自己描述它,但很可能编译器将内联调用queue.也就是说,当你说queue.push(),它真的只会说queue.container.push_back(),完全跳过函数调用.
再一次,这只是一个有根据的猜测,但queue与使用底层容器raw相比,使用不会降低性能.就像我之前说过的那样,使用它queue,因为它干净,易于使用,而且安全,如果它真的成为问题轮廓和测试.
Mar*_*som 27
退房std::queue.它包装了一个底层容器类型,默认容器是std::deque.
小智 7
在使用最古老的元素(大约一百万次)时,我不断地使用
push_back新元素pop_front.
百万在计算中确实不是一个大数字.正如其他人所建议的,使用a std::queue作为您的第一个解决方案 万一它太慢,请使用分析器识别瓶颈(不要猜测!)并使用具有相同接口的不同容器重新实现.