c++ - std::deque 或 std::list

Question

我正在使用push_front()并且push_back()只有。因此，我不会因使用insert()or而产生任何其他费用remove()。

我知道这两个容器都O(1)为这些功能中的每一个提供了复杂性，deque与 s 具有恒定时间相比，s 具有摊销list的恒定时间。

但我想知道哪个时间比另一个少，如果有的话。

Answer 1

不知道如何回答你的问题。您似乎希望我们编写一个您自己可以轻松编写的基准程序。因此，我不这样做，而是说明这一点：

• 使用 a list，您推送的每个项目都会导致内存分配。
• 使用 a deque，一次分配大块。

鉴于内存分配通常很慢，我预计会优于deque列表。

如果您一次推送或弹出许多项目，则尤其如此，因为缓存局部性开始发挥作用。

当然，你可以在列表上写一个分配器来使用内存池。那么你可能会得到更好的表现。

因此，考虑到这些假设，离开并测量它，如果你想讨论结果，那就是提出问题的时候了。

Answer 2

每当谈到性能时，“猜测”（或在互联网上询问，这比猜测稍微好一点，但只是有点）是一个坏主意，并且总是最好测量这两个选项 - 在这种情况下，只需执行一个循环, 和 push_back 或 push_front 足够的东西使它变得现实[你可能想让它更现实并运行你的代码所做的大部分事情，并在循环中执行足够的时间以使其持续足够长以测量时间 - 它通常更多比向list/添加大量值deque然后发现“当你必须换出时，它变得非常慢！”更现实。