C++ ordenar en vector utilizando el objeto de función

Question

Estoy tratando de ordenar un vector v1 usando otro vector v2. No puedo hacerme a este error:

terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check
Abort trap

mientras se ejecuta este código:

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

class Comp 
{ 
    public: 
     Comp(vector<double>& inVec): _V(inVec) {} 
     bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));} 
    private: 
     vector<double> _V; 
}; 

int main(int argc, char** argv) 
{ 
    double x1[] = {90.0, 100.0, 80.0}; 
    double x2[] = {9.0, 3.0, 1.0}; 
    vector<double> v1(x1,x1+3); 
    vector<double> v2(x2,x2+3); 

    sort(v1.begin(), v1.end(), Comp(v2)); // sort v1 according to v2 

    for(unsigned int i=0; i<v1.size(); i++) 
    { 
     cout << v1.at(i) << " " << v2.at(i) << endl; 
    } 

    return 0; 
} 

v1 y v2 son del mismo tamaño. ¿Por qué el error out_of_range?

Gracias de antemano por cualquier apuntador.

Answer 1

creo que el problema es en esta línea:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));} 

El problema es que cuando el algoritmo std::sort utiliza una devolución de llamada personalizados, que pasa por los valores reales almacenados en el vector en lugares particulares, no el índices de las ubicaciones dentro del vector. Como resultado, cuando se llama

sort(v1.begin(), v1.end(), Comp(v2)); // sort v1 according to v2 

El Comp comparador de haber escrito va a obtener pasados ​​como parámetros los valores almacenados en el vector v1 y entonces tratar de indexación en esas posiciones en el vector v2. Dado que los valores en v1 son mayores que el tamaño de v2, la llamada a _V.at(i) provocará una excepción out_of_range.

Si desea ordenar los dos rangos entre sí, tendrá que adoptar un enfoque diferente. No conozco una forma directa de hacerlo, pero te lo haré saber si pienso en uno.

Answer 2

Tamaño de v1 es sólo 3, pero usted está usando cada valor de v2 como el índice de v1. Y como v2 tiene un valor 9 que es mayor que el tamaño de v1, que es lo que da std::out_of_range error en aquí:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));} 

std::vector::at función da std::out_of_range excepción del índice que se le pasa como argumento es mayor que el tamaño de vector. Es decir, el índice debe ser menor que vector::size().

Answer 3

Como se dijo en otras respuestas, el problema es que el algoritmo de clasificación pasa los valores reales para comparar en lugar de índices.

Aquí es cómo se puede resolver:

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

typedef pair<double, double> Zipped; // Represent an element of two lists 
            // "zipped" together 

// Compare the second values of two pairs 
bool compareSeconds (Zipped i, Zipped j) 
{ 
    return i.second < j.second; 
} 

int main (int argc, char **argv) 
{ 
    double x1[] = { 90, 100, 80 }; 
    double x2[] = { 9, 3, 1 }; 

    vector<double> v1(x1, x1 + 3); 
    vector<double> v2(x2, x2 + 3); 

    vector<Zipped> zipped(v1.size()); // This will be the zipped form of v1 
             // and v2 

    for (int i = 0; i < zipped.size(); ++i) 
    { 
     zipped[i] = Zipped(v1[i], v2[i]); 
    } 

    sort(zipped.begin(), zipped.end(), &compareSeconds); 

    for (int i = 0; i < zipped.size(); ++i) 
    { 
     cout << zipped[i].first << " " << zipped[i].second << endl; 
    } 

    for (int i = 0; i < v1.size(); ++i) 
    { 
     v1[i] = zipped[i].first; 
    } 

    // At this point, v1 is sorted according to v2 

    return 0; 
} 

Answer 4

Ok, ahora usted está probablemente consciente del hecho de que ij y son valores reales celebradas en vector en lugar de índices. Hay una buena razón para eso: la clasificación se trata de valores, no de índices. Tenga en cuenta que está pasando iteradores al método sort, por lo que no hay forma de que pueda extraer el índice por usted. Por supuesto, podría obtener un índice relativo al primer iterador, pero no hay ninguna razón para hacerlo.

Sin embargo, vamos a estar locos por un tiempo e imaginamos que obtendríamos índices en lugar de valores en su comparador.Suponga que su código hace lo que quiere y vamos a pensar en siguiente escenario:

v1 = {20,10}; v2 = {2,1}

secretamente supuesto de que desea el siguiente resultado:

v1 = {10, 20}

¿verdad? Ahora imagina que estoy una función de clasificación que está llamando y lo hago siguientes pasos:

• v2[0] < v2[1] es falso, por lo swap(&v1[0], &v1[1])

Se ordenadas, ¿verdad? Pero espera, soy una función de clasificación loco, así que quiero para asegurarse de que está ordenada, por lo que hago lo siguiente:

• v2[0] < v2[1] es falso, swap(&v1[0], &v1[1])

Y de nuevo:

• v2[0] < v2[1] es falso, swap(&v1[0], &v1[1])

y otra vez, otra vez, otra vez ...

¿Ves problema? La función de clasificación tiene algunos requisitos y seguramente está rompiendo uno fundamental.

sospecho que necesita contenedor completamente diferente (tal vez std::map con claves desde vec1 y valores de vec2) o al menos algo parecido a vector< pair<double, double> >, por lo que fácilmente puede ordenar por el primero o el segundo valor. De lo contrario, considere crear vector con valores en el rango [0, v2.size()), ordenándolo con su comparador (los valores son iguales a índices, por lo tanto estará bien) y luego imprima los valores correctos desde v1. Este código funciona bien:

vector<size_t> indices; 
for(size_t i =0; i < v1.size(); ++i) 
{ 
    indices.push_back(i); 
} 

// yes, it works using your original comparator 
sort(indices.begin(), indices.end(), Comp(v2)); 

for(size_t i =0; i < indices.size(); ++i) 
{ 
    cout << v1.at(indices[i]) << " " << v2.at(indices[i]) << endl; 
}