是否有插入然后排序的替代方法

Question

如果我有vector<int> foo和vector<int> bar两者都被排序，并且我想将它们合并到foo以便对最终结果进行排序，标准是否为我提供了一种执行此操作的方法？

显然我可以做到：

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

但我希望有一个一步算法来完成这个。

Answer 1

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

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

Answer 2

为了详细说明 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 3

如果您需要这种合并，为什么不自己做一个呢？

template <class Vector>
void insert_sorted(Vector& where, Vector& what)
{
typename Container::iterator src = what.begin();
typename Container::iterator src_end = what.end();
size_t index = 0;
while(src != src_end)
{
if(*src < where[index])
{
where.insert(where.begin() + index, *src);
++src;
}
++index;
}
}

示例用法：

vector<int> foo{ 0, 5, 7, 9, 11, 14 };
vector<int> bar{ 1, 2, 4, 8, 10, 12 };
insert_sorted(foo, bar);
for(vector<int>::iterator i = foo.begin(); i != foo.end(); ++i)
cout << *i << " ";

输出：

0 1 2 4 5 7 8 9 10 11 12 14

实时样本：链接。

Answer 4

因此，在查看了所有标准算法之后，我可以确认，除了insert和sort之外别无选择。当我搜索标准算法时，我确实注意到所有复制算法都使用输入迭代器和输出迭代器，只有在操作单个范围时才会使用输入输出迭代器。(例如，sort使用输入输出迭代器，但任何copy都使用输入迭代器和输出迭代器。

我想举例说明我的观点。因此，让我们举一个示例，说明带有输入输出迭代器的插入合并算法是什么样的：

template <class BidirectionalIterator, class InputIterator>
void func(BidirectionalIterator first1, BidirectionalIterator last1, InputIterator first2, InputIterator last2){
bool is1Empty = first1 == last1;
bool is2Empty = first2 == last2;
BidirectionalIterator end = next(last1, distance(first2, last2));
if (!is1Empty){
--last1;
}
if (!is2Empty){
--last2;
}
while (!is1Empty || !is2Empty){
--end;
if (!is1Empty){
if (!is2Empty && *last2 > *last1){
*end = *last2;
if (last2 == first2){
is2Empty = true;
}else{
--last2;
}
}else{
*end = *last1;
if (last1 == first1){
is1Empty = true;
}
else{
--last1;
}
}
}else{
*end = *last2;
if (last2 == first2){
is2Empty = true;
}
else{
--last2;
}
}
}
}

关于此func算法，应注意两点：

1. 它不尊重last1假设分配了超出last1足够的空间以包含输入范围内的所有元素
2. func的输入输出范围不能像标准算法中的任何其他仅输出范围那样用back_inserter调用

正因为如此，即使func也不能是"一步算法"。它必须这样称呼：

foo.resize(foo.size() + bar.size());
func(foo.begin(), next(foo.begin(), foo.size() - bar.size()), bar.begin(), bar.end());

请注意，高炉的答案利用了它正在合并两个排序范围的知识，因此速度与func相当：

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

唯一实际的"一步算法"是将这个高炉的答案滚动到一个函数中，你可以通过传入要合并的容器来调用该函数。