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

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());

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

现场样本：link.

Answer 4

所以在查看所有标准算法后我可以确认，除了 insert 和 sort. 别无选择，因为我正在搜索标准算法我确实注意到 all 复制算法使用输入迭代器和输出迭代器，唯一使用输入输出迭代器的时间是在对单个范围进行操作时。（例如 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算法需要注意两点：

它不尊重 last1 假定在 last1 之外分配了足够的 space 以包含输入范围
func 的输入输出范围不能像标准算法中的任何其他仅输出范围那样用 back_inserter 调用

因此即使 func 也不能是 "one step algorithm"。必须这样称呼：

 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());

唯一实际的 "one step algorithm" 是将此 Blastfurnace 的答案滚动到一个函数中，您可以通过传入要合并的容器来调用该函数。

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

Is There an Alternative to insert and then sort

c++

sorting

merge

insert

stl-algorithm