将矢量合并到现有矢量中

Question

在C++中,给予vector<T> src, dst,两者已经排序,有没有更有效的进行合并的内容的方式src进入dst比

size_t n = dst.size();
dst.insert(dst.end(), src.begin(), src.end());
std::inplace_merge(dst.begin(), dst.begin() + n, dst.end());

？在我关心的情况下,T是一个小的(12-16字节,取决于ABI)POD结构,但每个向量包含数百万个元素,因此播放的内存总量是几十到几百兆.

Answer 1

我至少会尝试:

std::vector<T> tmp;
tmp.reserve(src.size() + dst.size()); // commenters are probably right about this
std::merge(src.begin(), src.end(), dst.begin(), dst.end(), std::back_inserter(tmp));
src.swap(tmp);

但我怀疑,很大程度上取决于的性质T,规模src和dst,为什么我们需要优化.

Answer 2

如果T很重要并且您的编译器支持C++ 0x,则可以更有效地完成它.

#include <iterator> // for make_move_iterator

size_t n = dst.size();

dst.insert(dst.end(),
    std::make_move_iterator(src.begin()),
    std::make_move_iterator(src.end()));

std::inplace_merge(dst.begin(), dst.begin() + n, dst.end());

使用make_move_iterator()会导致insert()到的内容移动src到dst而不是复制它们.

更新:

你正在处理POD类型,并且你已经在溢出保留dst的可能情况下调整/复制向量中的所有内容insert(),因此可以更快地使用std::merge()新的vector.这将避免该初始副本并具有更好的最坏情况复杂性:

inplace_merge()具有O(n)复杂度的最佳情况,但根据您的数据降级为最坏情况O(n log n).

merge()具有最坏情况的O(n)因此保证至少同样快,可能更快.它还内置了移动优化功能.