我应该使用哪个STL容器来实现先进先出（FIFO）功能？

Question

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

我目前正在使用std::deque来完成这项任务，但是我想知道是否使用std::list会更有效率，因为我不需要重新分配空间（或者也许我将std::deque错认为是std::vector了？）。还是说有更适合我的需求的容器吗？

P.S.我不需要随机访问。

- Gab Royer

---

为什么不尝试两种方法并计时，看哪一种更适合您的需求呢？ - KTC

我本想这么做，但我也在寻找一个理论上的答案。 - Gab Royer

std::deque 不会重新分配内存。它是 std::list 和 std::vector 的混合体，它分配比 std::list 更大的块，但不像 std::vector 那样重新分配内存。 - Matt Price

不，这里是标准中相关的保证：“在deque的开头或结尾插入单个元素始终需要恒定的时间，并且会导致对T的复制构造函数进行一次调用。” - Matt Price

阅读这里的评论就像看火车撞车一样。 - greyfade

Answer 1

由于有许多答案，您可能会感到困惑，但总结如下：

使用std::queue。原因很简单：它是一个FIFO结构。你想要FIFO，就用std::queue。

这使得你的意图对任何人都清晰明了，甚至对你自己也是如此。std::list或std::deque不行。列表可以在任何地方插入和删除，这不是FIFO结构应该做的事情，而deque可以从任一端添加和删除，这也是FIFO结构不能做的事情。

这就是为什么你应该使用queue的原因。

现在，你问到性能问题。首先，永远记住这个重要的经验法则：好的代码第一，性能最后。

原因很简单：那些在干净和优雅之前追求性能的人几乎总是最后完成的。他们的代码变成了一堆糊糊的东西，因为他们放弃了所有好的东西，却真正得不到任何东西。

通过首先编写良好、可读的代码，大多数性能问题都会自行解决。如果以后发现性能不足，现在很容易向你的漂亮、干净的代码添加分析器，并找出问题所在。

尽管如此，std::queue只是个适配器。它提供了安全的接口，但内部使用了不同的容器。您可以选择底层容器，这样可以提供很大程度的灵活性。

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

首先，需要明白分配(和释放)内存通常不是一个快速的过程，因为它涉及到向操作系统请求执行某些任务。每当添加内容时，list都必须分配内存，并在对象不再使用时进行释放。

而另一方面，deque是以块为单位进行分配的。它的分配次数比list少。可以将其想象成一个列表，但每个内存块可以容纳多个节点。(当然，我建议您真正了解它的工作原理。)

因此，仅凭这一点，deque的性能应该更好，因为它不需要像list那样频繁地进行内存操作。再加上您正在处理的数据大小是常量，因此它可能不需要在第一次通过数据时分配内存，而list则需要不断分配和释放内存。

第二个需要理解的是缓存性能。访问RAM速度较慢，所以当CPU真正需要时，它会将一块内存带回缓存中，以最大化利用这段时间。因为deque在内存中分配块，所以访问此容器中的元素可能会导致CPU也将其余部分带回。现在，任何进一步访问deque的操作都将非常快，因为数据已经在缓存中了。

这与列表不同，列表中的数据是逐个分配的。这意味着数据可能分散在内存中的各个位置，缓存性能会很差。

因此，考虑到这一点，deque应该是更好的选择。这就是为什么在使用queue时，它是默认容器的原因。但是请记住：先让代码具备清晰的接口，然后再考虑性能。

约翰提出了一个问题，即包装列表或deque会导致性能下降。他和我都不能确定，除非自己进行分析，但很有可能编译器将内联队列调用。也就是说，当您说queue.push()时，它实际上只会说queue.container.push_back()，完全跳过函数调用。

再次强调，这只是一个有根据的猜测，但与使用底层容器相比，使用队列不会降低性能。像我之前说过的那样，使用队列，因为它干净、易于使用和安全，如果真的成为问题，则进行分析和测试。

- GManNickG

---

如果发现 boost::circular_buffer<> 有最佳性能，那么就将其作为底层容器使用（它还提供了所需的 push_back()、pop_front()、front() 和 back()）。+1 - Michael Burr

接受详细解释（这正是我所需要的，感谢您花时间）。至于好代码优先性能最后，我必须承认这是我最大的缺点之一，我总是试图在第一次运行时完美地完成事情......虽然我一开始使用了deque编写代码，但由于它的表现不如我想象中的好（应该是准实时），我猜我应该稍微改进一下。正如Neil所说，我真的应该使用分析器...尽管现在犯这些错误并不重要，但我很高兴。非常感谢你们所有人。 - Gab Royer

未解决问题、冗长无用的回答得到了负面评价。正确的答案是 boost::circular_buffer<>，简洁明了。 - Dmitry Chichkov

“好的代码先行，性能后求”，这是一句很棒的名言。如果每个人都能理解这一点就好了 :) - thegreendroid

我很赞赏对性能分析的重视。提供经验法则一件事，然后通过性能分析进行证明是更好的事情。 - talekeDskobeDa

Answer 2

请查看 std::queue。它包装了一个底层容器类型，而默认容器是 std::deque。

- Mark Ransom

---

编译器将消除每个额外的层。按您的逻辑，我们应该都只用汇编语言编程，因为语言只是妨碍。关键是要为工作使用正确的类型，而“队列”就是那种类型。优秀的代码首先要考虑，性能可以后期优化。事实上，大多数性能都来自于一开始就使用良好的代码。 - GManNickG

抱歉有些含糊 - 我的意思是队列正是问题所需要的，而C++设计者认为deque是这种用例的一个很好的基础容器。 - Mark Ransom

这个问题中没有任何迹象表明他发现性能不足。许多初学者经常询问任何给定问题的最有效解决方案，无论他们当前的解决方案是否可接受。 - jalf

你看了我的回答吗？在任何方面，双端队列都是更好的选择。而“显然”是什么意思，你认为在争论中使用这样一个主观的词语会有什么好处？我认为列表和双端队列同样是“显然”的选择，所以我说，“嘿，双端队列具有更好的分配和缓存性能”。我认为这使得双端队列成为“显然”的选择。“显然最好”本身并不可靠。牛顿的万有引力定律曾经是“显然”的，现在看看它。 - GManNickG

std::queue<>的好处是，如果deque<>不符合您要求（出于性能或其他原因），只需一行代码即可将其更改为使用std::list作为后备存储器 - 就像GMan很久以前说的那样。而如果你真的想使用环形缓冲区而不是列表，boost::circular_buffer<>可以直接使用... std::queue<>几乎肯定是应该使用的“接口”。它的后备存储器几乎可以随意更改。 - Michael Burr

Answer 3

如果性能很重要，那么可以查看Boost环形缓冲区库

。

- Emile Cormier

Answer 4

我需要不断地加入新元素，同时弹出最旧的元素（大约一百万次）。

在计算机中，一百万并不是一个很大的数字。正如其他人建议的那样，首先可以使用 std::queue 作为解决方案。如果不幸它过慢，使用分析器（不要猜测！）确定瓶颈并重新实现使用具有相同接口的不同容器。

- anon

---

事实上，问题在于这是一个很大的数字，因为我想要做的事情应该是实时的。虽然你说得对，我应该使用分析器来确定原因... - Gab Royer

事实上，我并不太习惯使用分析器（我们在其中一门课程中使用过gprof，但我们并没有深入研究...）。如果您能指引我一些资源，我将不胜感激！PS. 我使用的是VS2008。 - Gab Royer

@Gab：你用的是哪个版本的VS2008（Express，Pro...）？有些版本自带分析器。 - sbi

@Gab 抱歉，我不再使用 VS 了，所以无法提供建议。 - anon

@Sbi，从我所看到的情况来看，这只在团队系统版本中（我有权限访问）出现。我会进一步调查此事。 - Gab Royer

Answer 5

为什么不使用 std::queue 呢？它只有 push_back 和 pop_front。

- eduffy

Answer 6

一个队列可能比双端队列更简单易用，但对于如此小的列表，性能差异可能可以忽略不计。

列表也是一样的。这只是你想要哪种API的选择。

- lavinio

---

但我在想，如果不断使用 push_back 是否会导致队列或双端队列重新分配内存。 - Gab Royer

std::queue是另一个容器的包装器，因此将队列包装在deque中比原始deque效率低。 - John Millikin

对于10个项目，性能很可能不会是一个大问题，因此"效率"更好地以程序员时间而非代码时间来衡量。并且，由任何良好的编译器优化所执行的队列到双端队列的调用几乎可以忽略不计。 - lavinio

@John：我希望你能给我展示一组基准测试，证明这种性能差异。它的效率不比一个原始的deque低。C++编译器有很强的内联优化能力。 - jalf

我试过了。 :D 在 VC9 的 Release 版本上，使用 100,000,000 个随机 int 数字进行 pop_front() & push_back() 操作，容器中包含 10 个元素。速度测试结果为：list(27), queue(6), deque(6), array(8)。 - KTC

Answer 7

使用std::queue，但要注意两个标准Container类的性能权衡。默认情况下，std::queue是在std::deque上的适配器。通常，在包含大量条目的少量队列的情况下，这将提供良好的性能，这可以说是常见情况。但是，不要对std::deque的实现视而不见。具体来说：“...双端队列通常具有较大的最小内存成本；仅包含一个元素的双端队列必须分配其完整的内部数组（例如，在64位libstdc++上为对象大小的8倍；在64位libc++上为对象大小的16倍或4096字节中的较大值）。”

为了简化，假设一个队列条目是您想要排队的东西，即大小合理，则如果您有4个队列，每个队列包含30,000个条目，则std :: deque实现将是首选选项。相反，如果您有30,000个队列，每个队列包含4个条目，则很可能std :: list实现将是最佳选择，因为在这种情况下您永远不会摊销std :: deque开销。

您会读到很多关于缓存是王者，Stroustrup讨厌链接列表等的观点，所有这些都是真实的，在某些条件下。只是不要盲目接受它，因为在我们的第二种情况下，很难使默认的std :: deque实现发挥作用。评估您的使用情况并进行测量。

- Allan Bazinet

Answer 8

这个案例足够简单，你可以自己编写。以下是一种适用于微控制器情况的方法，其中STL使用会占用太多空间。这是一种很好的方式，可以从中断处理程序传递数据和信号到主循环。

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};

- user10658782

---

但那会在什么情况下发生呢？ - user10658782

哦，我以为它可以做某些事情。没关系！ - Ry-