std::list是否有类似于vector::reserve()的等效函数？

Question

我有一个类，长这样：

typedef std::list<char*> PtrList;
class Foo
{
public:
   void DoStuff();
private:
   PtrList m_list;
   PtrList::iterator m_it;
};

函数DoStuff()的基本作用是在m_list中添加元素或删除元素，找到它里面特定元素的迭代器并将其存储在m_it中。需要注意的是每次调用DoStuff()时，都会使用m_it的值。

那么问题出在哪里呢？虽然一切正常，但是性能分析显示由于DoStuff()中的list::push_back()操作，导致new操作符被过度调用。

为了提高性能，我想在初始化Foo时为m_list预分配内存，就像对std::vector这样的容器所做的那样。但这样做会引入新的问题，例如：

1. 元素的insert和erase操作更加低效。 2. 由于从一个DoStuff()调用到下一个调用期间，向量可能已经被修改，因此m_it变得无效。 （Alan Stokes建议使用索引而不是迭代器来解决此问题。）

我的解决方案是：实现一个对象池，可以拥有链表的功能。这样，我就可以获得一个链表，并且可以预先分配内存。这是我能想到的最简单的解决方案。

如果有标准的解决方案存在，我宁愿不要“重新造轮子”，而是使用标准解决方案。

欢迎提出任何想法、解决办法或启发性的评论！

- Eitan T

---

你到底是用那些char*做什么的？ - ScarletAmaranth

@ScarletAmaranth 这些是指向存储数据包的内存位置的指针（我在问题中将其简化为char*）。 - Eitan T

你是否检查过如果只使用vector是否能够更好地执行？它很可能会；快速分配和良好的缓存行为通常可以弥补插入/删除成本。 - Alan Stokes

你可以指定一个自定义的 Allocator（作为 list 模板的第二个参数），并使用它从你的池中分配内存。你可能会发现 boost::pool 很有用。 - Alan Stokes

@ Eitan，你能否存储一个索引而不是迭代器到vector中，以避免无效？ （在插入和删除时要小心。） - Alan Stokes

Answer 1

我认为你在错误地使用容器。

如果你想要快速的推回操作，不要自动地假设你需要一个链表，链表是一种慢速容器，它基本上适用于重新排序。

更好的容器是 std::deque。std::deque 基本上是一个数组的数组。当你 push back 时，它会分配一块内存并占用它，当它用完时，它将分配另一个块。这意味着它只会很少地分配内存，而且你不需要提前知道容器的大小以获得效率，就像 std::vector 和 reserver 一样。

- 111111

---

我需要一个快速的“erase”操作，除此之外还需要一个快速的“push_back”操作。 - Eitan T

你是否真正进行过std::deque的erase基准测试，并与std::list进行比较？相对于连续存储容器，std::list确实非常慢。你的集合有多大？ - 111111

没有对其进行基准测试。我的集合大约包含约10,000个元素。 - Eitan T

如果你的 std::deque 实现能够从一个单独的块中擦除（或者它只需要将该块中的元素向下移动），我会强烈建议对其进行基准测试，如果它比这种实现更慢，那么我会感到惊讶。 - 111111

我怀疑对于std::list来说，insert和erase会比std::deque快得多，但这可能会被deque更有效的分配所抵消。我也会尝试一下。 - Eitan T

Answer 2

你可以使用 std::list 中的 splice 函数来实现一个对象池。添加一个新的成员变量 PtrList m_Pool。当你想要添加一个新的对象且对象池不为空时，将值赋给池中的第一个元素，然后将其拼接到列表中。要删除一个元素，将其从列表中拼接到对象池中即可。

但如果你不关心元素的顺序，那么使用 deque 可能更快。如果你想要删除中间的一个元素，可以将最后一个元素复制到要删除的元素上，然后再删除最后一个元素。

- Derek Ledbetter

---

但是如果您不关心元素的顺序，那么deque可能会更快。请注意，std::deque也是有序的。 - Gill Bates

Answer 3

列表和向量在管理对象方面完全不同。

向量将元素构造到给定容量的分配缓冲区中。当容量用尽时，会进行新的分配。 列表逐个分配元素，每个元素分配到一个单独分配的空间中。

向量元素在插入/删除时会移动，因此向量索引和元素地址不稳定。 列表元素在插入/删除时重新链接，因此列表迭代器和元素地址是稳定的。

一种使列表类似于向量的方法是用另一个分配器替换默认分配器（每次调用都从系统中分配），该分配器将对象分配到大块中，并在调用列表时发送子块。 这不是标准库提供的默认功能。

- Emilio Garavaglia

---

@EitanT：你没有理解“标准库默认没有提供这个功能”这句话的哪一部分？ - Nicol Bolas

@NicolBolas 我不是在谈论标准库本身，也许有其他用于此类目的“标准”实现。我肯定不是第一个想要为 std::list 预分配内存的人... - Eitan T

@NicolBolas 几年前我写了这篇文章：[http://www.codeproject.com/Articles/13265/On-heap-fixed-allocation-outside-MFC]，也许需要一些调整以适应C++11的风格，但它应该能够工作！ - Emilio Garavaglia

@EitanT: "你的意思是..." ... 噢，刚刚修复了！抱歉。 - Emilio Garavaglia

Answer 4

我的建议和111111的建议一样，在你编写任何重要的代码之前，请尝试切换到deque。

然而，直接回答你的问题：你可以使用带有自定义分配器的std::list。这有点棘手，我不会在这里详细讨论所有细节，但其要点是，你需要编写一个类来表示列表节点的内存分配策略。由list分配的节点将比char*大了一些实现定义的数量，但它们都是相同的大小，这意味着你可以为该大小编写一个优化的分配器（一个内存块池而不是一个对象池），并且你可以向其中添加函数，以便在你想要的时间保留所需的空间。然后列表可以快速地进行分配/释放，这样就可以省去重新实现任何实际的list功能的麻烦了。

如果你（出于某种原因）要实现一个具有列表功能的对象池，那么你可以从boost::intrusive开始。在编写自己的分配器时，它可能也很有用，用于跟踪可用块的列表。

- Steve Jessop

---

+1：感谢您的建议。我想节省时间，所以在决定编写任何复杂的代码之前，我想听听其他建议。我遵循了111111的建议并切换到deque。到目前为止，它对我有用（主要是因为我的大多数插入都是push_back而不是在中间）。 - Eitan T

Answer 5

可能可以使用list::get_allocator().allocate()。据我所知，由于list的非连续性质， 默认行为是在需要时获取内存 - 因此缺少reserve() - 但是我立刻没有发现使用allocator方法的主要缺点。只要您在程序中有一个非关键部分，在开头或其他地方，您至少可以选择在那一点上承担损伤。

- Elliott