私は約100個ほどのソートされたコレクションを持ってvector<int>いますほとんどのベクトルには少数の整数が含まれていますが、一部のベクトルにはそれらの大きな（> 10K）が含まれています（したがって、ベクトルは必ずしも同じサイズである必要はありません） ）。
私がやりたいことは、基本的に、これらすべてのソートされたベクトルに含まれている最小の整数から最大の整数まで反復します。
これを行う1つの方法は、これらすべてのソートされたベクトルをソートされたベクトルにマージし、単純に反復することです。したがって、
質問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;
}