102

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

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

PS我不需要随机访问

4

8 回答 8

225

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

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

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

这就是为什么你应该使用queue.

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

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

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

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

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

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

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

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

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

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

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

但请记住：让代码使用干净的界面，然后担心性能。

listJohn 提出了包装ordeque会导致性能下降的担忧。再一次，他和我可以肯定地说，无需自己分析，但编译器很可能会内联调用queue。也就是说，当您说 时queue.push()，它实际上只会说queue.container.push_back()，完全跳过函数调用。

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

于 2009-08-11T21:44:01.797 回答
29

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

于 2009-08-11T20:49:55.200 回答
11

在性能真正重要的地方，请查看Boost 循环缓冲区库。

于 2010-01-22T04:12:31.913 回答
7

我在寻找最古老的元素的push_back同时不断地添加新元素pop_front（大约一百万次）。

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

于 2009-08-11T21:02:25.377 回答
5

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

于 2009-08-11T20:51:50.530 回答
3

队列可能是比双端队列更简单的接口，但对于这么小的列表，性能差异可能可以忽略不计。

list也是如此。这取决于您想要的 API 的选择。

于 2009-08-11T20:48:45.187 回答
1

使用 a ，但要注意两个标准类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开销。

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

于 2019-12-31T21:39:44.850 回答
0

这个案例很简单，你可以自己写。对于 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);}
};
于 2020-06-11T19:12:41.547 回答