C++ 我应该为 FIFO 使用哪个 STL 容器？

Which STL container should I use for a FIFO?

提问by Gab Royer

Which STL container would fit my needs best? I basically have a 10 elements wide container in which I continually push_backnew elements while pop_fronting the oldest element (about a million time).

哪个 STL 容器最适合我的需求？我基本上有一个 10 个元素宽的容器，我在其中不断添加push_back新元素，同时pop_front使用最旧的元素（大约一百万次）。

I am currently using a std::dequefor the task but was wondering if a std::listwould be more efficient since I wouldn't need to reallocate itself (or maybe I'm mistaking a std::dequefor a std::vector?). Or is there an even more efficient container for my need?

我目前正在使用 astd::deque来完成任务，但想知道 astd::list是否会更有效，因为我不需要重新分配自己（或者我可能将 a 误认为std::dequea std::vector？）。或者是否有更有效的容器来满足我的需要？

P.S. I don't need random access

PS我不需要随机访问

回答by GManNickG

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.

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

It makes your intent clear to anybody else, and even yourself. A std::listor std::dequedoes not. A list can insert and remove anywhere, which is not what a FIFO structure is suppose to do, and a dequecan add and remove from either end, which is also something a FIFO structure cannot do.

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

This is why you should use a queue.

这就是为什么你应该使用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::queueis 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.

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

So, which underlying container should you use? We know that std::listand std::dequeboth provide the necessary functions (push_back(), pop_front(), and front()), so how do we decide?

那么，您应该使用哪个底层容器？我们知道，std::list并且std::deque都提供必要的功能（push_back()，pop_front()，和front()），所以我们如何决定？

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 listhas to allocate memory every single time something is added, and deallocate it when it goes away.

首先，要了解分配（和释放）内存通常不是一件快速的事情，因为它涉及到操作系统并要求它做某事。list每次添加东西时，A必须分配内存，并在它消失时释放它。

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.)

deque另一方面，A 分块分配。它的分配频率低于 a list。把它想象成一个列表，但每个内存块可以容纳多个节点。（当然，我建议你真正了解它是如何工作的。）

So, with that alone a dequeshould 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.

因此，仅凭这一点 adeque应该表现得更好，因为它不会经常处理内存。与您正在处理恒定大小数据的事实相结合，它可能不必在第一次通过数据后分配，而列表将不断分配和解除分配。

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 dequeallocates 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 dequewill be speedy, because the data is in cache.

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

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 dequeshould 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 dequein one test and listin the other to really know for certain.

因此，考虑到这一点，adeque应该是更好的选择。这就是为什么它是使用queue. 话虽如此，这仍然只是一个（非常）有根据的猜测：您必须分析此代码，deque在一个测试中使用 a 并在另一个测试list中真正确定。

But remember: get the code working with a clean interface, then worry about performance.

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

John raises the concern that wrapping a listor dequewill 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 queuemakes. That is, when you say queue.push(), it will really just say queue.container.push_back(), skipping the function call completely.

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

Once again, this is only an educated guess, but using a queuewill 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.

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

回答by Mark Ransom

Check out std::queue. It wraps an underlying container type, and the default container is std::deque.

退房std::queue。它包装了一个底层容器类型，默认容器是std::deque.

回答by Emile Cormier

Where performance really matters, check out the Boost circular buffer library.

如果性能真的很重要，请查看Boost 循环缓冲区库。

回答by Emile Cormier

I continually push_backnew elements while pop_fronting the oldest element (about a million time).

我在使用最旧的push_back元素时不断添加新元素pop_front（大约一百万次）。

A million is really not a big number in computing. As others have suggested, use a std::queueas your first solution. In the unlikely event of it being too slow, identify the bottleneck using a profiler (do not guess!) and re-implement using a different container with the same interface.

一百万在计算中真的不是一个大数字。正如其他人所建议的那样，使用 astd::queue作为您的第一个解决方案。万一它太慢，请使用分析器确定瓶颈（不要猜测！）并使用具有相同接口的不同容器重新实现。

回答by eduffy

Why not std::queue? All it has is push_backand pop_front.

为什么不std::queue呢？它所拥有的只是push_back和pop_front。

回答by lavinio

A queueis probably a simpler interface than a dequebut for such a small list, the difference in performance is probably negligible.

一个队列可能是一个比一个更简单的接口，双端队列，但对于这样的小单子，在性能上的差异可能是微不足道的。

Same goes for list. It's just down to a choice of what API you want.

同去的名单。这只是取决于您想要的 API 的选择。

回答by Allan Bazinet

Use a std::queue, but be cognizant of the performance tradeoffs of the two standard Containerclasses.

使用 a std::queue，但要注意两个标准Container类的性能权衡。

By default, std::queueis an adapter on top of std::deque. Typically, that'll give good performance where you have a small number of queues containing a large number of entries, which is arguably the common case.

默认情况下，std::queue是在std::deque. 通常，当您拥有包含大量条目的少量队列时，这将提供良好的性能，这可以说是常见情况。

However, don't be blind to the implementation of std::deque. Specifically:

但是，不要对std::deque的实现视而不见。具体来说：

"...deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++)."

“...双端队列通常具有较大的最小内存成本；仅包含一个元素的双端队列必须分配其完整的内部数组（例如，64 位 libstdc++ 上对象大小的 8 倍；对象大小的 16 倍或 4096 字节，以较大者为准，在 64 位 libc++ 上）。”

To net that out, presuming that a queue entry is something that you'd want to queue, i.e., reasonably small in size, then if you have 4 queues, each containing 30,000 entries, the std::dequeimplementation will be the option of choice. Conversely, if you have 30,000 queues, each containing 4 entries, then more than likely the std::listimplementation will be optimal, as you'll never amortize the std::dequeoverhead in that scenario.

为了解决这个问题，假设队列条目是您想要排队的内容，即，大小相当小，那么如果您有 4 个队列，每个队列包含 30,000 个条目，那么std::deque实现将是选择的选项。相反，如果您有 30,000 个队列，每个队列包含 4 个条目，那么std::list实现很可能是最佳的，因为std::deque在这种情况下您永远不会分摊开销。

You'll read a lot of opinions about how cache is king, how Stroustrup hates linked lists, etc., and all of that is true, under certain conditions. Just don't accept it on blind faith, because in our second scenario there, it's quite unlikely that the default std::dequeimplementation will perform. Evaluate your usage and measure.

你会读到很多关于缓存如何为王、Stroustrup 如何讨厌链表等的观点，在某些情况下，所有这些都是正确的。只是不要盲目接受它，因为在我们的第二种情况下，默认std::deque实现不太可能执行。评估您的使用情况并进行测量。