我应该为 FIFO 使用哪个 STL 容器?

哪个 STL 容器最适合我的需求?我基本上有一个 10 个元素宽的容器，在其中我不断 push_back 新元素，同时 pop_front ing 最旧的元素(大约一百万次).

我目前正在使用 std::deque 来完成任务，但想知道 std::list 是否会更有效，因为我不需要重新分配本身(或者我可能将 std::deque 误认为 std::vector?).或者是否有更高效的容器来满足我的需要?

附言我不需要随机访问

解决方案

既然有无数的答案，你可能会感到困惑，但总结一下:

使用 std::queue.原因很简单:它是一种先进先出的结构.你想要先进先出，你使用 std::queue.

它让其他人甚至你自己都清楚你的意图.std::list 或 std::deque 没有.列表可以在任何地方插入和删除，这不是FIFO结构应该做的，而deque可以从任何一端添加和删除，这也是FIFO结构不能做的.>

这就是你应该使用队列的原因.

现在，您询问了性能.首先，永远记住这条重要的经验法则:好的代码在先，性能在后.

这样做的原因很简单:在清洁和优雅之前追求性能的人几乎总是最后完成.他们的代码变得一团糟，因为他们已经放弃了所有好的东西，以便真正从中得到任何东西.

通过首先编写好的、可读的代码，你们中的大多数性能问题都会自行解决.如果以后您发现自己的性能不足，现在可以轻松地将分析器添加到您漂亮、干净的代码中，并找出问题所在.

话虽如此，std::queue 只是一个适配器.它提供了安全的接口，但在内部使用了不同的容器.您可以选择这个底层容器，这提供了很大的灵活性.

那么，您应该使用哪个底层容器?我们知道 std::list 和 std::deque 都提供了必要的函数(push_back(), pop_front() 和 front())，那么我们如何决定?

首先，要明白分配(和释放)内存不是一件快速的事情，通常，因为它涉及到操作系统并要求它做某事.list 必须在每次添加时分配内存，并在它消失时释放内存.

deque，另一方面，以块的形式分配.它将比 list 分配的频率更低.把它想象成一个列表，但每个内存块可以容纳多个节点.(当然，我建议您真正了解它的工作原理.)>

因此，单独使用 deque 应该表现更好，因为它不经常处理内存.再加上您正在处理恒定大小的数据，它可能不必在第一次通过数据后分配，而列表将不断分配和取消分配.

要了解的第二件事是缓存性能.进入 RAM 的速度很慢，因此当 CPU 确实需要时，它会通过将一大块内存带回缓存来充分利用这段时间.由于 deque 在内存块中分配，因此访问此容器中的元素很可能会导致 CPU 也带回容器的其余部分.现在对 deque 的任何进一步访问都将很快，因为数据在缓存中.

这与列表不同，列表一次分配一个数据.这意味着数据可能会散布在内存中的所有地方，缓存性能会很差.

因此，考虑到这一点，deque 应该是更好的选择.这就是为什么在使用 queue 时它是默认容器的原因.话虽如此，这仍然只是一个(非常)有根据的猜测:您必须分析此代码，在一个测试中使用 deque 并在另一个测试中使用 list确实知道.

但请记住:让代码与干净的界面一起工作，然后担心性能.

John 担心包装 list 或 deque 会导致性能下降.再说一次，他和我都可以在没有自己分析的情况下肯定地说，但是编译器可能会内联 queue 进行的调用.也就是说，当你说queue.push()时，它实际上只会说queue.container.push_back()，完全跳过函数调用.

再说一次，这只是一个有根据的猜测，但与使用底层容器 raw 相比，使用 queue 不会降低性能.就像我之前说过的，使用 queue，因为它干净、易于使用且安全，而且如果它真的成为一个问题配置文件和测试.

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.