我应该将哪个 STL 容器用于 FIFO？

Question

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

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

PS我不需要随机访问

Answer 1

由于有无数的答案，您可能会感到困惑，但总结一下：

使用 std::queue。 原因很简单：它是一个 FIFO 结构。 如果您想要 FIFO，则可以使用 std::queue。

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

这就是为什么您应该使用队列。

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

原因很简单：在干净和优雅之前追求性能的人几乎总是最后完成。 他们的代码变得一团糟，因为他们为了真正从中一无所获而放弃了所有好的东西。

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

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

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

首先，要了解分配（和释放）内存通常不是一件很快的事情，因为它涉及到操作系统并要求它执行某些操作。 列表每次添加内容时都必须分配内存，并在内容消失时释放内存。

另一方面，双端队列以块的形式进行分配。 它的分配频率低于列表。 将其视为一个列表，但每个内存块可以容纳多个节点。 （当然，我建议您真正了解它是如何工作的。）

所以，仅凭这一点，deque 应该表现得更好，因为它不那么频繁地处理内存。 再加上您正在处理恒定大小的数据，它可能不必在第一次传递数据后进行分配，而列表将不断分配和取消分配。

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

这与列表不同，列表一次分配一个数据。 这意味着数据可能会分散在内存中的各处，并且缓存性能会很差。

因此，考虑到这一点，双端队列应该是更好的选择。 这就是为什么它是使用队列时的默认容器。 总而言之，这仍然只是一个（非常）有根据的猜测：您必须分析此代码，在一个测试中使用 deque ，在另一个测试中使用 list确实知道。

但请记住：让代码以干净的界面运行，然后再担心性能。

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

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

Answer 2

我不断push_back新元素
while pop_front ing 最旧的元素
（大约一百万次）。

一百万对于计算来说确实不是一个大数字。 正如其他人所建议的，使用 std::queue 作为您的第一个解决方案。 万一速度太慢，请使用分析器识别瓶颈（不要猜测！）并使用具有相同接口的不同容器重新实现。

Answer 3

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

Answer 4

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

Answer 5

使用 std::queue，但要认识到两个标准 Container 类的性能权衡。

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

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

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

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

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

Answer 6

这个案例很简单，您可以自己编写。 对于 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);}
};

Answer 7

queue 可能是比 deque 但对于这么小的列表，性能差异可能可以忽略不计。

list 也是如此。 只需选择您想要的 API 即可。

Answer 8

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