español - libreria vector c++

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

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo ordeno un std :: vector por los valores de un std :: vector diferente? 12 respuestas

Esto es probablemente mejor como un ejemplo. Tengo dos vectores / listas:

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

Quiero ordenar a la Gente según su edad usando algo como sort(People.begin(), People.end(), CustomComparator) , pero no sé cómo escribir el CustomComparator para ver las Edades en lugar de las Personas.

Answer 1

Como otros han señalado, debe considerar agrupar personas y edades.

Si no puede / no quiere, puede 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 enésima persona es people[pos[n]] y su edad es ages[pos[n]]

Answer 2

En general, no se colocan los datos que desea mantener juntos en diferentes contenedores. Hacer una estructura / clase para la persona y el operator< sobrecarga operator< .

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

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

O si esto es algo desechable:

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

std::pair ya implementa operadores de comparación.

Answer 3

En lugar de crear dos vectores / listas separados, la forma habitual de manejar esto es crear un solo vector / lista de objetos que incluyan nombres y edades:

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

Para obtener una clasificación basada en la edad, pase un comparador que analice las edades:

std::sort(people.begin(), people.end(), 
          [](auto const &a, auto const &b) { return a.age < b.age; });

En C ++ anterior (antes de C ++ 11, por lo que no hay expresiones lambda), puede definir la comparación como una sobrecarga de miembros del operator< o bien como un objeto de función (un objeto que sobrecarga al operator() ) para hacer la comparación:

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

Entonces tu ordenación se vería como:

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

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

En cuanto a elegir entre definir el operator< para la clase, o usar un objeto comparador por separado como se muestra arriba, es principalmente una cuestión de si hay un solo pedido que sea "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 sería obvio que la clasificación de personas se haría por edad a menos que especifique explícitamente lo contrario, entonces tendría sentido implementar la comparación como person::operator< lugar de en una clase de comparación separada la forma en que lo he hecho arriba.

Answer 4

No tiene sentido mantenerlos en dos estructuras de datos separadas: si reordena a People , ya no tiene un mapeo sensible a las 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

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

Answer 6

La respuesta de Jerry Coffin fue totalmente clara y correcta.

Solo tengo un problema relacionado que puede otorgar una buena discusión al tema ... :)

Tuve que reordenar las columnas de un objeto de matriz (digamos TMatrix <T> ) según la clasificación de un vector (digamos secuencia ) ... La clase TMatrix <T> no proporciona acceso de referencia a sus filas (por lo tanto, no se puede crear una estructura para reordenarla ...) pero proporciona un método TMatrix <T> :: swap (row1, row2) ...

Así que ese 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;
    }
}

Creo que todavía es O (n log n) ya que cada fila que no esté en su lugar se intercambiará solo una vez ...

¡Que te diviertas! :)