C++ STL: Clasificación personalizada de un vector según el contenido de otro

Question

Probablemente este sea el mejor ejemplo. Tengo dos vectores/listas:

People = {Anne, Bob, Charlie, Douglas} 
Ages = {23, 28, 25, 21} 

que desea ordenar las personas en función de sus edades utilizando algo así como sort(People.begin(), People.end(), CustomComparator), pero no sé cómo escribir el CustomComparator mirar Edad en lugar de personas.

Answer 1

Sugeriría fusionar estas dos listas en una sola lista de estructuras. De esta forma, simplemente puede definir operator < como se dijo dirkgently.

Answer 2

En lugar de crear dos vectores/listas separadas, la forma habitual de manejar esto es la creación de un vector individual/lista de objetos que incluyen tanto los nombres y las edades:

struct person { 
    std::string name; 
    int age; 
}; 

para obtener una especie basada en la edad , definen un comparador que se ve en las edades:

struct by_age { 
    bool operator()(person const &a, person const &b) { 
     return a.age < b.age; 
    } 
}; 

Luego, su tipo sería algo como:

std::vector<person> people; 
// code to put data into people goes here. 

std::sort(people.begin(), people.end(), by_age()); 

Editar: En cuanto a elegir entre la definición de operator< para la clase, o el uso de un objeto de comparación separado como he mencionado anteriormente, es sobre todo una cuestión de si hay un solo pedido que es "obvio" para esta clase.

En mi opinión, no es necesariamente obvio que la clasificación de personas siempre suceda por edad. Sin embargo, si en el contexto de su programa fuera obvio que clasificando personas se haría por edad, a menos que especifique lo contrario explícitamente, entonces tendría sentido implementar la comparación como person::operator< en lugar de en una clase de comparación separada de la forma en que lo he hecho arriba.

Answer 3

Generalmente, no pondría los datos que desea mantener juntos en contenedores diferentes. Realice una estructura/clase para Persona y sobrecarga operator<.

struct Person 
{ 
    std::string name; 
    int age; 
} 

bool operator< (const Person& a, const Person& b); 

O si esto es algo de usar y tirar:

typedef std::pair<int, std::string> Person; 
std::vector<Person> persons; 
std::sort(persons.begin(), persons.end()); 

std::pair ya poner en práctica los operadores de comparación.

Answer 4

No tiene sentido mantenerlos en dos estructuras de datos separadas: si reordena People, ya no tiene una asignación sensata a Ages.

template<class A, class B, class CA = std::less<A>, class CB = std::less<B> > 
struct lessByPairSecond 
    : std::binary_function<std::pair<A, B>, std::pair<A, B>, bool> 
{ 
    bool operator()(const std::pair<A, B> &left, const std::pair<A, B> &right) { 
     if (CB()(left.second, right.second)) return true; 
     if (CB()(right.second, left.second)) return false; 
     return CA()(left.first, right.first); 
    } 
}; 

std::vector<std::pair<std::string, int> > peopleAndAges; 
peopleAndAges.push_back(std::pair<std::string, int>("Anne", 23)); 
peopleAndAges.push_back(std::pair<std::string, int>("Bob", 23)); 
peopleAndAges.push_back(std::pair<std::string, int>("Charlie", 23)); 
peopleAndAges.push_back(std::pair<std::string, int>("Douglas", 23)); 
std::sort(peopleAndAges.begin(), peopleAndAges.end(), 
     lessByPairSecond<std::string, int>()); 

Answer 5

Como han señalado otros, debería considerar agrupar personas y edades.

Si no puede/no quiere, podría crear un "índice" para ellos, y ordenar ese índice en su lugar. Por ejemplo:

// Warning: Not tested 
struct CompareAge : std::binary_function<size_t, size_t, bool> 
{ 
    CompareAge(const std::vector<unsigned int>& Ages) 
    : m_Ages(Ages) 
    {} 

    bool operator()(size_t Lhs, size_t Rhs)const 
    { 
     return m_Ages[Lhs] < m_Ages[Rhs]; 
    } 

    const std::vector<unsigned int>& m_Ages; 
}; 

std::vector<std::string> people = ...; 
std::vector<unsigned int> ages = ...; 

// Initialize a vector of indices 
assert(people.size() == ages.size()); 
std::vector<size_t> pos(people.size()); 
for (size_t i = 0; i != pos.size(); ++i){ 
    pos[i] = i; 
} 


// Sort the indices 
std::sort(pos.begin(), pos.end(), CompareAge(ages)); 

Ahora, el nombre de la persona que n es people[pos[n]] y su edad es ages[pos[n]]

Answer 6

Jerry Ataúd respuesta era totalmente clara y correcta.

Un simplemente una cuestión relacionada que pueda conceder una buena discusión con el tema ... :)

que tenía que cambiar el orden de las columnas de un objeto matriz (digamos TMatrix < T>) sobre la base de la clasificación de un vector (digamos secuencia) ... TMatrix < T> clase no proporciona acceso de referencia a sus filas (por lo tanto, no puedo crear una estructura para reordenarlo ...) pero proporciona convenientemente un método TMatrix < T> :: swap (row1, row2) ...

Así que eso es el código:

TMatrix<double> matrix; 
vector<double> sequence; 
// 
// 1st step: gets indexes of the matrix rows changes in order to sort by time 
// 
// note: sorter vector will have 'sorted vector elements' on 'first' and 
// 'original indexes of vector elements' on 'second'... 
// 
const int n = int(sequence.size()); 
std::vector<std::pair<T, int>> sorter(n); 
for(int i = 0; i < n; i++) { 
    std::pair<T, int> ae; 
    ae.first = sequence[i]; 
    ae.second = i;    
    sorter[i] = ae; 
}   
std::sort(sorter.begin(), sorter.end()); 

// 
// 2nd step: swap matrix rows based on sorter information 
// 
for(int i = 0; i < n; i++) { 
    // updates the the time vector 
    sequence[i] = sorter[i].first; 
    // check if the any row should swap 
    const int pivot = sorter[i].second; 
    if (i != pivot) { 
     // 
     // store the required swaps on stack 
     // 
     stack<std::pair<int, int>> swaps; 
     int source = pivot; 
     int destination = i; 
     while(destination != pivot) { 
      // store required swaps until final destination 
      // is equals to first source (pivot) 
      std::pair<int, int> ae; 
      ae.first = source; 
      ae.second = destination; 
      swaps.push(ae); 
      // retrieves the next requiret swap 
      source = destination; 
      for(int j = 0; j < n; j++) { 
       if (sorter[j].second == source) 
        destination = j; 
        break; 
       } 
      } 
     }     
     // 
     // final step: execute required swaps 
     // 
     while(!swaps.empty()) { 
      // pop the swap entry from the stack 
      std::pair<int, int> swap = swaps.top(); 
      destination = swap.second;      
      swaps.pop(); 
      // swap matrix coluns 
      matrix.swap(swap.first, destination); 
      // updates the sorter 
      sorter[destination].second = destination; 
     } 
     // updates sorter on pivot 
     sorter[pivot].second = pivot; 
    } 
} 

Me creer que todavía es O (n log n), ya que cada fila que no está en su lugar va a cambiar sólo una vez ...

Que se diviertan! :)