我应该使用哪个STL容器用于FIFO？ [英] Which STL container should I use for a FIFO?
问题描述
哪个STL容器最适合我的需要？我基本上有一个10元素宽的容器，其中我不断 push_back 新元素，而 pop_front 百万次）。
我目前使用 std :: deque 执行此任务，但想知道是否 std :: list 会更有效率，因为我不需要重新分配自己（或者我错误的 std :: deque 对于 std :: vector ？）。还是有更高效的容器满足我的需要？
我不需要随机访问
由于有无数的答案，你可能会感到困惑， / p>
使用 std :: queue 。原因很简单：它是一个FIFO结构。你想要FIFO，你使用 std :: queue 。
这使你的意图清楚地向任何人，甚至自己。 std :: list 或 std :: deque 。一个列表可以在任何地方插入和删除，这不是一个FIFO结构是可以做的，一个 deque 可以添加和从任何一端删除，这也是一个FIFO结构不能做。
这是为什么你应该使用队列。
现在，你问过性能。首先，请务必记住这个重要的经验法则：优良的代码优先，效果最好。
这样做的原因很简单：性能在清洁和优雅几乎总是完成最后。他们的代码变成了糊状，因为他们已经放弃了所有的好，以便真正得到没有什么。
通过编写好的，可读的代码首先，大多数的性能问题都会自己解决。如果以后你发现你的性能缺乏，现在很容易添加一个分析器到你漂亮，干净的代码，并找出问题在哪里。
， std :: queue 只是一个适配器。它提供了安全的接口，但在里面使用不同的容器。你可以选择这个底层容器，这允许很大的灵活性。
那么，你应该使用哪个底层容器？我们知道 std :: list 和 std :: deque 都提供必要的函数（ push_back（）， pop_front（）和 front（）我们决定？
首先，了解分配（和释放）内存不是一个快速的事情，一般来说，因为它涉及到操作系统，并要求它做一点事。 列表必须在每次添加内容时分配内存，并在其消失时释放。
A deque ，另一方面，以块的形式分配。它将少于列表分配。把它想象成一个列表，但每个内存块可以容纳多个节点。 （当然，我建议您真正了解它的工作原理。）
所以，单独一个 deque 应该表现得更好，因为它不经常处理内存。混合了你处理常量大小的数据的事实，它可能不会在第一次传递数据后分配，而列表将不断分配和释放。
第二件要明白的是缓存性能。走出RAM是缓慢的，所以当CPU真的需要时，它通过把一大块内存回到缓存，使得在这个时间最好。因为 deque 在内存块中分配，所以访问此容器中的元素可能会导致CPU恢复容器的其余部分。现在，对 deque 的任何进一步访问都将很快，因为数据在缓存中。
列表，其中数据被一次分配一个。这意味着数据可以分布在内存中的所有地方，并且缓存性能会很差。
因此，考虑到， deque 应该是一个更好的选择。这就是为什么使用队列时它是默认容器的原因。所有的说，这仍然只是一个（非常）受过教育的猜测：你将不得不剖析这个代码，使用 deque 在一个测试和
但是请记住：获取代码使用一个干净的界面，然后担心性能。
/ p> John引起关注包装列表或 deque 将导致性能下降。再次，他也不能肯定地说没有自我剖析，但是机会是编译器将内联队列所做的调用。也就是说，当你说 queue.push（），它只会说 queue.container.push_back（）
再次，这只是一个有根据的猜测，但使用队列与使用底层容器raw相比，不会降低性能。像我之前说的，使用队列，因为它干净，易于使用，安全，如果它真的成为一个问题的配置文件和测试。
Which STL container would fit my needs best? I basically have a 10 elements wide container in which I continually push_back new elements while pop_front ing the oldest element (about a million time).
I am currently using a std::deque for the task but was wondering if a std::list would be more efficient since I wouldn't need to reallocate itself (or maybe I'm mistaking a std::deque for a std::vector?). Or is there an even more efficient container for my need?
P.S. I don't need random access
Since there are a myriad of answers, you might be confused, but to summarize:
Use a std::queue. The reason for this is simple: it is a FIFO structure. You want FIFO, you use a std::queue.
It makes your intent clear to anybody else, and even yourself. A std::list or std::deque does not. A list can insert and remove anywhere, which is not what a FIFO structure is suppose to do, and a deque can add and remove from either end, which is also something a FIFO structure cannot do.
This is why you should use a queue.
Now, you asked about performance. Firstly, always remember this important rule of thumb: Good code first, performance last.
The reason for this is simple: people who strive for performance before cleanliness and elegance almost always finish last. Their code becomes a slop of mush, because they've abandoned all that is good in order to really get nothing out of it.
By writing good, readable code first, most of you performance problems will solve themselves. And if later you find your performance is lacking, it's now easy to add a profiler to your nice, clean code, and find out where the problem is.
That all said, std::queue is only an adapter. It provides the safe interface, but uses a different container on the inside. You can choose this underlying container, and this allows a good deal of flexibility.
So, which underlying container should you use? We know that std::list and std::deque both provide the necessary functions (push_back(), pop_front(), and front()), so how do we decide?
First, understand that allocating (and deallocating) memory is not a quick thing to do, generally, because it involves going out to the OS and asking it to do something. A list has to allocate memory every single time something is added, and deallocate it when it goes away.
A deque, on the other hand, allocates in chunks. It will allocate less often than a list. Think of it as a list, but each memory chunk can hold multiple nodes. (Of course, I'd suggest that you really learn how it works.)
So, with that alone a deque should perform better, because it doesn't deal with memory as often. Mixed with the fact you're handling data of constant size, it probably won't have to allocate after the first pass through the data, whereas a list will be constantly allocating and deallocating.
A second thing to understand is cache performance. Going out to RAM is slow, so when the CPU really needs to, it makes the best out of this time by taking a chunk of memory back with it, into cache. Because a deque allocates in memory chunks, it's likely that accessing an element in this container will cause the CPU to bring back the rest of the container as well. Now any further accesses to the deque will be speedy, because the data is in cache.
This is unlike a list, where the data is allocated one at a time. This means that data could be spread out all over the place in memory, and cache performance will be bad.
So, considering that, a deque should be a better choice. This is why it is the default container when using a queue. That all said, this is still only a (very) educated guess: you'll have to profile this code, using a deque in one test and list in the other to really know for certain.
But remember: get the code working with a clean interface, then worry about performance.
John raises the concern that wrapping a list or deque will cause a performance decrease. Once again, he nor I can say for certain without profiling it ourselves, but chances are that the compiler will inline the calls that the queue makes. That is, when you say queue.push(), it will really just say queue.container.push_back(), skipping the function call completely.
Once again, this is only an educated guess, but using a queue will not degrade performance, when compared to using the underlying container raw. Like I've said before, use the queue, because it's clean, easy to use, and safe, and if it really becomes a problem profile and test.
这篇关于我应该使用哪个STL容器用于FIFO？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
