是否有替代插入然后排序

Question

如果我有,vector<int> foo并且vector<int> bar两者都已排序,并且我想将它们合并为foo最终结果已排序,那么标准是否为我提供了这样做的方法？

显然我可以这样做:

foo.insert(foo.end(), bar.begin(), bar.end());
sort(foo.begin(), foo.end());

但我希望有一个步骤算法来实现这一目标.

Answer 1

要详细说明Mat的注释,您的代码可能看起来像这样使用std::merge:

std::vector<int> result;
std::merge(
    foo.begin(), foo.end(),
    bar.begin(), bar.end(),
    std::back_inserter(result));

foo = result; // if desired

Answer 2

使用它可能更快std::inplace_merge而不是std::sort.如果有额外的可用内存,则它具有线性复杂性,否则会回退到NlogN.

auto middle = foo.insert(foo.end(), bar.begin(), bar.end());
std::inplace_merge(foo.begin(), middle, foo.end());