Tengo una colección de cerca de un centenar de ordenados vector<int> 's Aunque la mayoría de los vectores tienen un pequeño número de enteros en ellos, algunos de los vectores contienen una gran (> 10K) de ellos (por lo tanto los vectores no necesariamente tienen el mismo tamaño).C++ Cómo combinar vectores ordenados en un vector ordenado/pop el elemento mínimo de todos ellos?
Lo que me gustaría hacer esencialmente iterar a través de menor a mayor número entero, que están contenidos en todos estos vectores ordenados.
Una forma de hacerlo sería fusionar todos estos vectores ordenados en un vector ordenado & simplemente iterar. Por lo tanto,
Pregunta 1: ¿Cuál es la forma más rápida de combinar vectores ordenados en un vector ordenado?
Estoy seguro de que, por otro lado, hay formas más rápidas/inteligentes de lograr esto sin combinar & reordenar todo el asunto, quizás haciendo estallar el entero más pequeño iterativamente desde esta colección de vectores ordenados; sin fusionarlos primera .. así:
Pregunta 2: ¿Cuál es la mejor manera de ayuno/a estallar el elemento mínimo de un montón de ordenados vector<int> 's?
Sobre la base de las respuestas abajo, y los comentarios a la pregunta que me he aplicado un enfoque donde hago una cola de prioridad de iteradores para los vectores ordenados. No estoy seguro de si se trata de rendimiento con eficiencia, pero parece ser muy eficiente en la memoria. Considero que la pregunta aún está abierta, ya que no estoy seguro de haber establecido la manera más rápida hasta el momento.
// 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;
}
1) Si el espacio no es un problema, realice la fusión estándar de rangos ordenados de su CS101 a un nuevo vector (o simplemente piénselo un minuto y haga lo obvio) 2) Antes de ir por todas partes, asegúrese de comprender las garantías de complejidad de los contenedores estándar; modificar un 'std :: vector' es en general bastante caro. 3) ¡Deja de abjurar de los apo'strophes! –
@ Kerrek-SB Gracias, corrigió el formato un poco. Estoy bastante contento simplemente fusionando los vectores en un vector más grande y ordenando; pero me pregunto si hay formas más rápidas de hacerlo. – Deniz
No, no, realiza una fusión ordenada. Piénselo, hay una manera obvia de explotar el orden de los rangos de entrada para crear un rango de salida ya ordenado. –