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

该算法internal_vectors使用push_back()在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_backs吗？

---

更新:
1)根据DeadMG MSVC9进行这种类型的优化(Swaptimization- TR1 Fixes in VC9 SP1).gcc 4.3可能不会做这种类型的优化.

2)我已经分析了使用的算法版本,std::deque< std::vector<unsigned char> >我发现它的性能更好.

3)我也使用swap了Mark Ransom建议的使用方法.使用这改善了性能:

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

Answer 1

MSVC9 为其标准容器实现了所谓的“交换优化”。它是移动语义的较弱版本。当外部向量调整大小时，它不会内部向量。

但是，您最好将编译器升级到 MSVC10 或 GCC（我认为是 4.5），这将为您提供移动语义，从而使此类操作更加高效。当然，astd::deque可能仍然是更智能的容器，但移动语义在很多很多地方都有利于性能。