std::vector< std::vector<unsigned char> > 或者 std::deque< std::vector<unsigned char> >？ 请注意，这是一个提问标题，不需要回答。

Question

我有一个现有的算法，如果可能的话，我需要稍微优化它。目前不考虑在该算法中进行大量更改。该算法使用 std::vector< std::vector<unsigned char> > 实例。它看起来像这样：

typedef std::vector<unsigned char> internal_vector_t;
std::vector< internal_vector_t > internal_vectors; 

while (fetching lots of records) {
   internal_vector_t tmp;
   // reads 1Mb of chars in tmp...
   internal_vectors.push_back(tmp);
   // some more work
}

// use this internal_vectors

算法使用push_back()在internal_vectors中插入很多次internal_vector_t实例。大部分的internal_vector_t实例大小为1 Mb。由于internal_vectors的大小未知，因此没有提前进行reserve()。

我不明白的第一件事是当internal_vectors达到其当前容量时会发生什么，需要分配一个新块并将其当前内容复制到更大的内存块中。由于大多数块的大小为1Mb，复制是一个漫长的操作。我是否应该期望编译器（gcc 4.3、MS VC++ 2008）能够优化它以避免复制？

如果无法避免复制，改用std::deque是否有帮助？我考虑std::deque，因为我仍然需要通过索引访问，比如internal_vectors[10]。

typedef std::vector<unsigned char> internal_vector_t;
std::deque< internal_vector_t > internal_vectors; 
// the same while

据我所了解，std::deque 不需要重新分配已经分配的内存。在这种情况下，std::deque 在 push_back 操作时需要较少的分配和复制。

更新： 1）根据 DeadMG MSVC9 进行了这种类型的优化（Swaptimization - TR1 Fixes In VC9 SP1）。gcc 4.3 可能不会进行这种类型的优化。

2）我已经对使用 std::deque< std::vector<unsigned char> > 的算法版本进行了性能分析，发现其性能更好。

3）我还使用了 Mark Ransom 建议的使用 swap。使用后，性能得到了改善。

   internal_vector_t tmp;
   internal_vectors.push_back(empty);
   tmp.swap(internal_vectors.back());

- user184968

---

你是使用 insert 还是 push_back？代码中写的是 insert，但是实际上应该是 push_back，因为对于 vector 来说，它们的成本是非常不同的。 - David Rodríguez - dribeas

当内存不足时，显然需要分配更多的RAM。它会根据增量值来进行分配。增量和初始容量都应该是可设置的。增量值越高，每次分配的内存就越多。 - crush

我使用了 push_back，并在我的问题中修正了它。 - user184968

@ Lightness Races in Orbit，我修好了。为什么不呢？ - user184968

似乎是标准库中的2倍。我们使用自定义实现，允许您在像这样具有线性增长的情况下设置增量。 - crush

Answer 1

MSVC9实现了一种称为“交换优化”的标准容器技术，它是移动语义的一个较弱版本。当外部向量被调整大小时，它不会复制内部向量。

然而，最好的方法是升级到MSVC10或GCC（我认为是4.5），这将提供移动语义，使此类操作更加高效。当然，std::deque可能仍然是更明智的容器选择，但移动语义在许多地方都具有性能优势。

- Puppy

---

有没有类似于gcc中的swaptimization？您提到了gcc 4.5。 - user184968

@skwllsp：正确的版本是移动语义，它是C++11的一个特性。你可以在MSVC10和一些较新的GCC版本中找到它，如4.4或4.5。 - Puppy

Answer 2

每次将一个 `internal_vector_t` 插入到 `internal_vectors` 中时，它都会复制一份 `internal_vector_t`。无论您使用 `vector` 还是 `deque`，这都是正确的。标准容器总是会复制您要插入的对象。

您可以通过插入一个空的 `internal_vector_t`，然后使用您真正想要插入的对象与其交换内容来消除复制。

偶尔，向矢量插入对象时，矢量需要调整大小，因为在插入过程中已经没有足够的空间，这将导致对象再次被复制。只要始终在开头或结尾插入，deque 就可以消除这种情况。

编辑：我上面给出的建议可以用以下代码更简洁地总结。这段代码应该避免所有大型矢量的复制。

typedef std::vector<unsigned char> internal_vector_t;
std::deque< internal_vector_t > internal_vectors; 
internal_vector_t empty;

while (fetching lots of records) {
   internal_vector_t tmp;
   // reads 1Mb of chars in tmp...
   internal_vectors.push_back(empty);
   tmp.swap(internal_vectors.back());
   // some more work
}

- Mark Ransom

---

实际上，我主要感兴趣的是优化这个函数：Occasionally the vector will need to resize itself as it runs out of room during an insertion，因为这是我在对代码进行性能分析时第二频繁调用的函数。 - user184968

是的，我能够做到。这些调用来自于std::vector< std::vector <uchar> >::M_fill_insert或者std::vector<uchar>::M_fill_insert。std::vector< std::vector <uchar> >::M_fill_insert需要更多的处理时间。这就是为什么我询问可能的优化和使用std::deque的原因。 - user184968

这不是真的。MSVC9为标准容器实现了“交换优化”，因此当外部向量调整大小时，它不会复制内部向量。 - Puppy

@DeadMG，你有关于“swaptimization”方面的阅读链接吗？还有gcc呢？ - user184968

@DeadMG，有趣。我曾考虑过这样的优化可能是可行的，但编译器如何知道类型是可交换的？如果类型没有专门化std::swap，那不会导致劣化吗？ - Mark Ransom

Answer 3

std::deque 不会将其元素连续存储 - 它将其存储分解成一系列恒定大小的“块”。这意味着当一个 std::deque 超出其容量时，它只需要分配一个新的恒定大小的块 - 它不需要重新分配整个内部缓冲区并移动所有现有元素。

另一方面，std::vector 确实维护连续的存储，因此当它耗尽容量并重新分配时，它确实需要移动所有现有元素 - 这可能是昂贵的。

std::vector 对其重新分配方案进行了“智能”设计，根据几何级数（通常翻倍或增加 1.5 等）分配块。这意味着重新分配不经常发生。

在这种情况下，std::deque 可能更有效率，因为在重新分配时它要处理的工作较少。如常规操作一样，您需要进行基准测试以获得任何真实数字。

你的代码可能在其他方面还可以进一步改进。似乎在每次while循环迭代中，你都会创建一个新的internal_vector_t tmp。将其声明在循环外部并在每次迭代时只需清除存储即可更有效率。此外，每次调用internal_vectors.push_back(tmp)时，你都会复制整个tmp向量 - 通过internal_vectors.push_back(std::move(tmp))仅移动tmp向量，这样只会复制几个指针，你可能可以在此基础上进行改进。

希望这能有所帮助。

- Darren Engwirda

---

我基本上只使用std::deque作为FIFO队列，或者当我需要一个通常占用超过一半RAM的增长容器时（非常罕见）。 - Mooing Duck

@MooingDuck：我认为还有其他用例。如果您不知道要::reserve多少空间，而大小可能会很大（本质上是这个问题），我会看一下std::deque。不仅是std::vector的重新分配成本可能成为问题，而且重复重新分配可能导致内存碎片化的潜在问题。通常情况下，我发现std::deque在<<半个RAM的大小时可能更有效率，但当然您必须对您正在使用的特定代码进行基准测试。 - Darren Engwirda

技巧在于，相对于vector而言，deque往往会进行更多的分配，尽管它没有复制操作，这使得比较变得困难。对于推入5000个int，MSFT的vector将进行约19次分配，deque将进行约1250次分配。对于gcc，分别为约12和39。但是deque不会复制。@skwllsp：进行性能分析！ - Mooing Duck

@MooingDuck：众所周知，（目前的）MSVC std::deque存在严重缺陷，因为它们在16字节的疯狂小块中分配内存，导致您提到的行为。出于这个原因，我不使用MSVC容器，并且我认为基于一个特定的std库实现问题做出概括是不公平的。 - Darren Engwirda

deque很有用，但通常使用向量是正确的答案。至于基于一个实现的概括，这就是为什么我列出了“最常见”的两个实现。 - Mooing Duck

请注意，Dinkumware编写了MSVC++使用的标准库，因此任何使用Dinkumware标准库实现的编译器也可能会表现出相同的行为。 - In silico

Answer 4

你是否正在索引外部向量？如果没有，那么考虑使用std::list<std::vector<unsigned char> >？

- Ben Voigt

---

是的，我在我的问题中提到了它。我考虑使用std::deque，因为我仍然需要像internal_vectors[10]这样通过索引进行访问。 - user184968

@skwllsp 你真的需要随机访问吗？你可以通过遍历列表来完成。只需递增计数器并检查您需要的元素是否在该索引处即可。我希望我说得清楚。 - pezcode

@pezcode 你真的需要随机访问吗？ 不确定。但是，遗憾的是，这个算法的重大改变不是一个选择。 - user184968

Answer 5

一个双端队列在实现上可能更加高效。与向量不同，双端队列不能保证连续的存储空间，因此可以分配多个独立的内存块。因此，它可以在不移动已添加元素的情况下分配更多的内存。你应该尝试并测量其影响。

- rasmus

---

+1 用于性能分析，因为我认为在这种情况下差异将在纳秒总数中体现。 - Mooing Duck