C++如何将已排序的向量合并到一个已排序的向量/弹出所有这些向量中的最小元素？

Question

我有一个大约一百个排序的集合vector<int>虽然大多数向量中都有少量整数,但是一些向量包含大量(> 10K)它们(因此向量不一定具有相同的大小) ).

我想要做的基本上是遍历从最小到最大的整数,它们包含在所有这些排序的向量中.

一种方法是将所有这些排序的向量合并到一个有序向量中并简单地迭代.从而,

问题1:将排序后的向量合并为有序向量的最快方法是什么？

另一方面,我确信有更快/更聪明的方法来实现这一点,而无需合并和重新排序整个事物 - 也许从这个排序向量集合中迭代地弹出最小的整数; 没有合并它们..所以:

问题2:从一堆排序中弹出最少元素的禁区/最佳方法vector<int>是什么？

---

基于下面的回复,以及对问题的评论,我已经实现了一种方法,我为排序的向量建立了迭代器的优先级队列.我不确定这是否具有性能效率,但它似乎非常节省内存.我认为问题仍然存在,因为我不确定我们是否已经建立了最快的方式.

// compare vector pointers by integers pointed
struct cmp_seeds {
    bool operator () (const pair< vector<int>::iterator, vector<int>::iterator> p1, const pair< vector<int>::iterator, vector<int>::iterator> p2) const {
        return *(p1.first) >  *(p2.first);      
    }
};

int pq_heapsort_trial() {

    /* Set up the Sorted Vectors */ 
    int a1[] = { 2, 10, 100};
    int a2[] = { 5, 15, 90, 200};
    int a3[] = { 12 };

    vector<int> v1 (a1, a1 + sizeof(a1) / sizeof(int));
    vector<int> v2 (a2, a2 + sizeof(a2) / sizeof(int));
    vector<int> v3 (a3, a3 + sizeof(a3) / sizeof(int));

    vector< vector <int> * > sorted_vectors;
    sorted_vectors.push_back(&v1);
    sorted_vectors.push_back(&v2);
    sorted_vectors.push_back(&v3);
    /* the above simulates the "for" i have in my own code that gives me sorted vectors */

    pair< vector<int>::iterator, vector<int>::iterator> c_lead;
    cmp_seeds mycompare;

    priority_queue< pair< vector<int>::iterator, vector<int>::iterator>, vector<pair< vector<int>::iterator, vector<int>::iterator> >, cmp_seeds> cluster_feeder(mycompare);


    for (vector<vector <int> *>::iterator k = sorted_vectors.begin(); k != sorted_vectors.end(); ++k) {
        cluster_feeder.push( make_pair( (*k)->begin(), (*k)->end() ));
    }


    while ( cluster_feeder.empty() != true) {
        c_lead = cluster_feeder.top();
        cluster_feeder.pop();
        // sorted output
        cout << *(c_lead.first) << endl;

        c_lead.first++;
        if (c_lead.first != c_lead.second) {
            cluster_feeder.push(c_lead);
        }
    }

    return 0;
}

Answer 1

一种选择是使用 astd :: priority queue来维护迭代器堆，其中迭代器根据它们指向的值在堆中冒泡。

您还可以考虑使用重复应用程序std :: inplace_merge。这将涉及将所有数据一起附加到一个大向量中，并记住每个不同排序块开始和结束的偏移量，然后将它们传递到 inplace_merge 中。这可能会比堆解决方案更快，尽管我认为从根本上来说复杂性是相同的。

更新：我已经实现了我刚才描述的第二个算法。反复进行适当的合并排序。该代码位于ideone上。

这是通过首先将所有排序列表连接在一起形成一个长列表来实现的。如果存在三个源列表，则意味着存在四个“偏移量”，即完整列表中的四个点，元素在这四个点之间进行排序。然后，该算法将一次完成其中的三个，将两个相应的相邻排序列表合并为一个排序列表，然后记住这三个偏移量中的两个以在 new_offsets 中使用。

这在循环中重复，将相邻的排序范围对合并在一起，直到只剩下一个排序范围。

最终，我认为最好的算法首先将相邻范围的最短对合并在一起。

// http://stackoverflow.com/questions/9013485/c-how-to-merge-sorted-vectors-into-a-sorted-vector-pop-the-least-element-fro/9048857#9048857
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

template<typename T, size_t N>
vector<T> array_to_vector( T(*array)[N] ) { // Yes, this works. By passing in the *address* of
                                            // the array, all the type information, including the
                                            // length of the array, is known at compiler. 
        vector<T> v( *array, &((*array)[N]));
        return v;
}   

void merge_sort_many_vectors() {

    /* Set up the Sorted Vectors */ 
    int a1[] = { 2, 10, 100};
    int a2[] = { 5, 15, 90, 200};
    int a3[] = { 12 };

    vector<int> v1  = array_to_vector(&a1);
    vector<int> v2  = array_to_vector(&a2);
    vector<int> v3  = array_to_vector(&a3);


    vector<int> full_vector;
    vector<size_t> offsets;
    offsets.push_back(0);

    full_vector.insert(full_vector.end(), v1.begin(), v1.end());
    offsets.push_back(full_vector.size());
    full_vector.insert(full_vector.end(), v2.begin(), v2.end());
    offsets.push_back(full_vector.size());
    full_vector.insert(full_vector.end(), v3.begin(), v3.end());
    offsets.push_back(full_vector.size());

    assert(full_vector.size() == v1.size() + v2.size() + v3.size());

    cout << "before:\t";
    for(vector<int>::const_iterator v = full_vector.begin(); v != full_vector.end(); ++v) {
            cout << ", " << *v;
    }       
    cout << endl;
    while(offsets.size()>2) {
            assert(offsets.back() == full_vector.size());
            assert(offsets.front() == 0);
            vector<size_t> new_offsets;
            size_t x = 0;
            while(x+2 < offsets.size()) {
                    // mergesort (offsets[x],offsets[x+1]) and (offsets[x+1],offsets[x+2])
                    inplace_merge(&full_vector.at(offsets.at(x))
                                 ,&full_vector.at(offsets.at(x+1))
                                 ,&(full_vector[offsets.at(x+2)]) // this *might* be at the end
                                 );
                    // now they are sorted, we just put offsets[x] and offsets[x+2] into the new offsets.
                    // offsets[x+1] is not relevant any more
                    new_offsets.push_back(offsets.at(x));
                    new_offsets.push_back(offsets.at(x+2));
                    x += 2;
            }
            // if the number of offsets was odd, there might be a dangling offset
            // which we must remember to include in the new_offsets
            if(x+2==offsets.size()) {
                    new_offsets.push_back(offsets.at(x+1));
            }
            // assert(new_offsets.front() == 0);
            assert(new_offsets.back() == full_vector.size());
            offsets.swap(new_offsets);

    }
    cout << "after: \t";
    for(vector<int>::const_iterator v = full_vector.begin(); v != full_vector.end(); ++v) {
            cout << ", " << *v;
    }
    cout << endl;
}

int main() {
        merge_sort_many_vectors();
}