c++ - 合并按 vector 排序的 N C++

Question

我有一个包含比较运算符的已排序 C++ 类的 vector 。我需要一个排序对象的 vector 。是否有任何开源算法可以采用 vector 列表或 vector vector 并生成一个排序 vector ？

对于 n=2，这工作正常:

std::vector<Data> dst;
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));

Answer 1

标准库包含 merge function ，允许合并两个排序的 vector (特别是)。

假设您有 k 个序列，总长度为 n。当然，您可以每次合并 2 个序列，直到只剩下一个序列，但这是 known to be worst-case Θ(k²n) .

有两种选择:

• 按贪心大小合并 在这个变体中，每次合并两个最短的序列。这 [将最坏情况的时间减少到 Θ(k log(k) n) .

• 与优先队列合并 this scheme , 优先级队列包含迭代器和序列索引对，当弹出一个最小元素时，将推送序列中具有该索引的下一个项目。这有时间 Θ(log(k) n)，因为优先级队列每次最多有 k 个项目。

以下包含后者的实现(完整代码在 ideone 上)。 (我怀疑，虽然它比前者渐近更好，但它的常量比前者高得多。不过，贪心算法的通用实现(至少对我而言)有点棘手。)

include <vector>
#include <queue>
#include <iostream>


template<
    class InIts, 
    typename OutIt,
    class Cmp=std::less<typename std::iterator_traits<typename InIts::value_type::first_type>::value_type>>
OutIt merge(const InIts &in_its, OutIt out_it, Cmp cmp=Cmp())
{
    using it_t = typename InIts::value_type::first_type;
    using pair_t = std::pair<it_t, std::size_t>;
    auto pair_cmp = [cmp](const pair_t &lhs, const pair_t &rhs) { return !cmp(*lhs.first, *rhs.first); };
    using q_t = std::priority_queue<pair_t, std::vector<pair_t>, decltype(pair_cmp)>;

    std::vector<std::pair<it_t, it_t>> origs{in_its};
    q_t q{pair_cmp};

    for(std::size_t i = 0; i < origs.size(); ++i)
    {   
        auto &p = origs[i];
        if(p.first != p.second)
            q.push(std::make_pair(p.first++, i));
    }

    while(!q.empty()) 
    {
        auto t = q.top();
        *(out_it++) = *t.first;
        const auto i = t.second;
        q.pop();

        auto &p = origs[i];
        if(p.first != p.second)
            q.push(std::make_pair(p.first++, i));
    }

    return out_it;
}

您可以按如下方式使用它:

int main()
{
    using vec_t = std::vector<int>;

    vec_t v0{1, 2, 3}; 
    vec_t v1{2, 3, 4}; 
    vec_t v2{4, 5, 6}; 

    using vec_it_t = vec_t::iterator;

    std::vector<std::pair<vec_it_t, vec_it_t>> its{
        std::make_pair(std::begin(v0), std::end(v0)),
        std::make_pair(std::begin(v1), std::end(v1)),
        std::make_pair(std::begin(v2), std::end(v2))};

    vec_t res;
    merge(its, std::back_inserter(res));
    for(auto &e: res)
        std::cout << e << std::endl;
}