std::vector< std::vector<unsigned char> >还是std::deque< std::vector<unsigned char> >？
我有一个现有的算法，我需要优化它，如果可能的话。在这个算法中改变很多并不是目前的选择。algoritm与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该算法使用internal_vectors ()在internal_vector_t的internal_vector_t实例中插入了很多次。大多数internal_vector_t实例的大小为1MB。由于internal_vectors的大小未知，因此事先不进行任何保留()操作。
我不明白的第一件事是，当internal_vectors达到其当前容量时，需要分配一个新块并将其当前内容复制到更大的内存块中时，会发生什么。由于大多数块的大小为1Mb，所以复制是一项长期操作。我是否应该期望编译器(gcc 4.3，MS VC++ 2008)会设法优化它，以避免复制？
如果复制不可避免的话，std::deque 会帮助吗？我考虑std::deque，因为我仍然需要像internal_vectors10这样的索引访问。如下所示：
typedef std::vector<unsigned char> internal_vector_t;
std::deque< internal_vector_t > internal_vectors;
// the same while据我所知，std::deque不需要重新部署曾经分配过的位置。我说对了吗，在这种情况下，std::deque在push_backs上请求的分配和复制会减少吗？
更新：
1)根据DeadMG，MSVC9进行了这种类型的优化(Swaptimization-TR1在VC9 SP1中的修复)。gcc 4.3可能不会做这种优化。
2)描述了使用std::deque< std::vector<unsigned char> >算法的版本，发现它的性能更好。
( 3)我还使用了马克·兰瑟姆建议的马克·兰瑟姆。使用这一方法可以提高性能：
internal_vector_t tmp;
internal_vectors.push_back(empty);
tmp.swap(internal_vectors.back());回答 5
Stack Overflow用户
发布于 2012-02-16 03:58:57
MSVC9为它的标准容器实现了所谓的“交换化”。这是移动语义的一个较弱的版本。当外部向量被调整大小时，它将不会复制内部向量。
但是，您最好将编译器升级到MSVC10或GCC (我认为是4.5)，这将给您提供移动语义，这将大大提高这些操作的效率。当然，std::deque可能仍然是一个更聪明的容器，但是移动语义在许多地方都是有益的。
Stack Overflow用户
发布于 2012-02-15 19:33:34
每次将internal_vector_t插入到internal_vectors中时，它都会复制internal_vector_t。无论您使用vector还是deque，这都是正确的。标准容器总是要复制要插入的对象。
您可以通过插入一个空的internal_vector_t，然后用您真正想要插入的对象来swap插入对象的内容来消除复制。
有时，当向量在插入过程中耗尽空间时，需要调整其自身的大小，这将导致对象再次被复制。只要你总是在开头或结尾插入，德克就会消除这一点。
编辑：--我上面给出的建议--可以用这些代码更改来总结。此代码应避免对大向量的所有复制。
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
}Stack Overflow用户
发布于 2012-02-15 19:43:48
std::deque不连续地存储它的元素--它将它的存储分解为一系列固定大小的“块”。这意味着当一个std::deque耗尽容量时，它只需要分配一个新的常量块--它不需要重新分配它的整个内部缓冲区并移动它所有的现有元素。
另一方面，std::vector确实维护着连续的存储，所以当它耗尽容量并重新分配时，它确实需要移动它所有的现有元素--这可能会很昂贵。
std::vector对其重新分配方案是“聪明的”，按照一个几何级数(通常是将容量加倍或增加1.5等等)进行块分配。这意味着重新分配不会经常发生。
在这种情况下，std::deque可能更有效，因为当重新分配发生时，它的工作量就会减少。和往常一样，你必须通过基准测试才能得到任何真实的数字。
您的代码可能会在其他领域得到进一步改进。在while循环的每一次迭代中，您似乎都要创建一个新的internal_vector_t tmp。在循环之外声明这一点可能更有效，只需在每次迭代时将其存储起来就更有效了。每次调用internal_vectors.push_back(tmp)时，您也要复制整个internal_vectors.push_back(tmp)向量--您可能通过通过internal_vectors.push_back(std::move(tmp))移动tmp向量来改进这一点--这将只复制几个指针。
希望这能有所帮助。
https://stackoverflow.com/questions/9299835
复制相似问题
腾讯云开发者
