FIFO类型的容器 - 哪种STL容器最适合使用，以及为什么？

Question

我最近被委托实现一个缓冲区，该缓冲区将作为日志类的临时存储。日志类本身是一个单例，并使用观察者监听器模式。您可以预期使用此类记录数千条消息。

现在问题在于：

我们有一个跟踪日志选项，用于调试目的。当启用此选项时，每秒钟记录的消息数量呈指数增长。在发布代码中，跟踪日志已禁用，但是如果发生错误，则会将一个可以存储固定数量消息（例如10000）的缓冲区转储到日志中，以便开发人员可以确定问题的根源。

如果缓冲区已满，则删除最旧的消息以释放空间以存储最新的消息。

void Log::storeToBuffer(const LogType_E & type_in, const LogDomain_E & domain_in,const int & id_in, const char * msg_in)
{
    if(this->myEnableTraceBuffer)
    {
        if(static_cast<std::list<Message> * >(this->myRingBuffer)->size() < this->myRingBufferMaxSize)
        {
            static_cast<std::list<Message> * >(this->myRingBuffer)->push_back(Message(type_in, domain_in, id_in, msg_in));
        }
        else
        {
            //buffer full so remove oldest element and add new
            if(static_cast<std::list<Message> * >(this->myRingBuffer)->size() > 0) static_cast<std::list<Message> * >(this->myRingBuffer)->pop_front();
            static_cast<std::list<Message> * >(this->myRingBuffer)->push_back(Message(type_in, domain_in, id_in, msg_in));
        }
    }
}

我使用 std::list 来实现这个功能，简单地利用 push_back/pop_front，以利用常数时间的删除/插入执行时间。（不要问为什么需要 void 转换，这不是我的决定）。

但由于缓冲区大小是固定的，并且在对象的生命周期内不太可能发生更改，也许使用 vector 和显式索引操作更合适？例如，可以有两个索引，start/current，二者都从位置 0 开始。当向量已满并添加了某些内容时，start 移动到位置 1，current 移动到位置 0，因此在打印结果时我们会得到正确的顺序。

也许另一个 STL 容器更适合这种情况？

感谢您耐心阅读这段长文字。我将在此回答任何问题。

- FailedDev

---

这实际上是先进先出（FIFO），而不是后进先出（LIFO）/先进后出（FILO）。 - Christian Rau

只是好奇，为什么你要把日志保存在内存中？如果出现崩溃，你最需要的时候日志就会消失。 - AndersK

@AndersK. 我们只是将跟踪消息保存在内存中，而不是保存日志本身。当你有数百万条消息时，它会严重影响性能，因此跟踪消息仅用于调试目的。 - FailedDev

没错，谢谢你提供的信息，祝你一切顺利。 - AndersK

小小的疑问 - 为什么 myRingBuffer 是一个指针？如果它真的是 你的 环形缓冲区，不与任何其他人共享，那么为什么不使用集合对象呢？好吧，在你没有启用它的情况下，一个空的集合比一个指针大，但并不是很大。还有一个相关的问题，你从哪种类型转换了这个指针？ - Steve Jessop

Answer 1

< p > std::deque 可以高效地在开头或结尾插入或删除，使其成为缓冲区的优秀结构。它可以用作 std::queue 的模板类型，非常适合您的应用程序 - 每次执行 push 时，请检查队列的大小，如果超过最大值，则执行 pop。

- Mark Ransom

Answer 2

您听说过 std::deque 吗？它可以在常摊时间内实现随机访问和两端的常时间压入/弹出操作。因此，它可以轻松地用作先进先出队列。

话虽如此，由于它可以轻松地被用作先进先出队列，因此有一个容器适配器std::queue，尽管它不提供随机访问和迭代器接口。

- Xeo

---

是的，我考虑过这个选项。这与当前的std::list实现有什么不同吗？我会看到任何性能提升吗？ - FailedDev

@FailedDev，std::list为每个元素保留了一对链接指针。如果这些指针在与存储的项相比较大时，可能会产生影响。std::deque也允许高效的随机访问，但似乎这不是您的使用需求。 - Mark Ransom

哦，是的，非常正确。std::deque 实际上就是一个展开的 std::list。 - Mooing Duck

@MarkRansom 是的，我根本不需要随机访问。 - FailedDev

它（std::queue）不仅没有提供随机访问，而且也没有迭代功能，我认为这可能需要用于输出逻辑。当然，您可以连续弹出，但这会破坏容器。 - Christian Rau

@Chris：对，我总是忘记容器适配器在可用性方面实际上有多糟糕...已编辑。 - Xeo

Answer 3

虽然std :: list的push_back / pop_front是常数时间，但它们将使用堆分配，这可能是您在这里遇到瓶颈的原因。

您描述的使用std :: vector的方法将消除堆分配，并可能因此更快。 如您所述使用std :: vector作为循环缓冲区，如果您可以使用boost，则可在此处获得符合stl标准的一个：http://www.boost.org/doc/libs/1_47_0/libs/circular_buffer/doc/circular_buffer.html

- je4d

---

感谢您的时间。不幸的是，我不能在这个项目中使用boost。 - FailedDev

真遗憾 - 我认为std::deque最终仍然会大量分配新块并释放旧块，尽管您将获得更好的内存局部性，因为它将被分配在块中，并且不会一直维护前向/后向指针。如果性能确实非常重要，那么按照您描述的使用vector实现循环缓冲区可能是正确的选择。但是，取决于您的malloc()实现和应用程序中正在进行的其他分配，收益可能非常微小。 - je4d

Answer 4

您需要的是双端队列，可以在前/后添加或删除元素。C++标准库中的版本是std::deque。它与std::vector在功能上相似（例如通过索引访问，但请注意，没有保证连续存储），但支持快速在前后插入和删除。我认为在内部实际上是使用类似环形缓冲区的纯数组实现的。

这里唯一的问题是它好像没有提供reserve方法。所以你不能从一开始就告诉它要为你的潜在10000个元素腾出空间，并且必须考虑一些重新分配。但这些应该摊销，就像对于向量一样。仍然比std::list的10000个或更多的小分配好。一旦它有了10000个元素的大小，就不应再有任何分配，而std::list将不断释放和分配新对象。

实际上，您还可以使用std::queue，默认情况下使用std::deque作为其底层容器类型，并仅提供FIFO队列所需的少量函数。但在这种情况下，您将无法访问单个元素或迭代所有元素，这可能需要用于输出逻辑。

- Christian Rau