¿Cómo clasifico un std :: vector por los valores de un std :: vector diferente?

Question

Tengo varios std :: vector , todos de la misma longitud. Quiero ordenar uno de estos vectores y aplicar la misma transformación a todos los demás vectores. ¿Hay una manera limpia de hacer esto? (preferiblemente utilizando el STL o Boost)? Algunos de los vectores contienen int sy algunos de ellos std :: string s.

Pseudocódigo:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };

Transformation = sort(Index);
Index is now { 1, 2, 3};

... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };

Answer 1

El enfoque de

friol es bueno cuando se combina con el tuyo. Primero, construya un vector que consista en los números 1 & # 8230; n , junto con los elementos del vector que dictan el orden de clasificación:

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

Ahora puede ordenar esta matriz utilizando un clasificador personalizado:

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

Ahora ha capturado el orden de reorganización dentro de order (más precisamente, en el primer componente de los elementos). Ahora puede usar este orden para ordenar sus otros vectores. Probablemente hay una variante in situ muy inteligente que se ejecuta al mismo tiempo, pero hasta que alguien más se le ocurra, aquí hay una variante que no está en su lugar. Utiliza order como una tabla de búsqueda para el nuevo índice de cada elemento.

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}

Answer 2

Ponga sus valores en un contenedor Boost Multi-Index luego repita para leer los valores en el orden que desee. Incluso puede copiarlos a otro vector si lo desea.

Answer 3

typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;

class SequenceGen {
  public:
    SequenceGen (int start = 0) : current(start) { }
    int operator() () { return current++; }
  private:
    int current;
};

class Comp{
    int_vec_t& _v;
  public:
    Comp(int_vec_t& v) : _v(v) {}
    bool operator()(size_t i, size_t j){
         return _v[i] < _v[j];
   }
};

index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}

int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };

std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}

Ahora puede usar los " índices " vector para indexar en " Valores " vector.

Answer 4

Solo se me ocurre una solución aproximada: crear un vector que sea la suma de todos los demás vectores (un vector de estructuras, como {3, Third, ...}, {1, First, ...}) luego ordene este vector por el primer campo, y luego divida las estructuras nuevamente.

Probablemente haya una solución mejor dentro de Boost o usando la biblioteca estándar.

Answer 5

Probablemente puedas definir una " fachada " personalizada iterador que hace lo que necesitas aquí. Almacenaría iteradores para todos sus vectores o, alternativamente, derivaría los iteradores para todos menos el primer vector a partir del desplazamiento del primero. La parte difícil es a qué hace referencia ese iterador: piense en algo como boost :: tuple y haga un uso inteligente de boost :: tie. (Si desea ampliar esta idea, puede crear estos tipos de iteradores de forma recursiva utilizando plantillas, pero probablemente nunca desee escribir el tipo de eso, por lo que necesita c ++ 0x auto o una función de envoltura para clasificar que lleva rangos)

Answer 6

Creo que lo que realmente necesitas (pero corrígeme si me equivoco) es una forma de acceder a los elementos de un contenedor en algún orden.

En lugar de reorganizar mi colección original, tomaría prestado un concepto del diseño de la base de datos: mantener un índice, ordenado por un cierto criterio. Este índice es una indirección adicional que ofrece una gran flexibilidad.

De esta manera es posible generar múltiples índices de acuerdo con los diferentes miembros de una clase.

using namespace std;

template< typename Iterator, typename Comparator >
struct Index {
    vector<Iterator> v;

    Index( Iterator from, Iterator end, Comparator& c ){
        v.reserve( std::distance(from,end) );
        for( ; from != end; ++from ){
            v.push_back(from); // no deref!
        }
        sort( v.begin(), v.end(), c );
    }

};

template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
    return Index<Iterator,Comparator>(from,end,c);
}

struct mytype {
    string name;
    double number;
};

template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};

template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
};

void indices() {

    mytype v[] =    { { "me"    ,  0.0 }
                    , { "you"   ,  1.0 }
                    , { "them"  , -1.0 }
                    };
    mytype* vend = v + _countof(v);

    Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
    Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );

    assert( byname.v[0] == v+0 );
    assert( byname.v[1] == v+2 );
    assert( byname.v[2] == v+1 );

    assert( bynum.v[0] == v+2 );
    assert( bynum.v[1] == v+0 );
    assert( bynum.v[2] == v+1 );

}

Answer 7

La respuesta de ltjax es un gran enfoque, que en realidad se implementa en zip_iterator de boost http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Se agrupa en una tupla, independientemente de los iteradores que le proporcione.

Luego puede crear su propia función de comparación para una clasificación basada en cualquier combinación de valores de iterador en su tupla. Para esta pregunta, sería el primer iterador en tu tupla.

Una buena característica de este enfoque es que te permite mantener la memoria de cada vector individual contiguo (si estás usando vectores y eso es lo que quieres). Tampoco necesita almacenar un vector de índice separado de ints.

Answer 8

Una variante ligeramente más compacta de la respuesta de xtofl si solo está buscando iterar a través de todos sus vectores basándose en el de un solo vector de keys . Cree un vector de permutación y úselo para indexar sus otros vectores.

#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>

std::vector<double> keys = ...
std::vector<double> values = ...

std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(keys.size()));
std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) {
    return keys[lhs] < keys[rhs];
});

// Now to iterate through the values array.
for (size_t i: indices)
{
    std::cout << values[i] << std::endl;
}

Answer 9

Esto habría sido una adición a la respuesta de Konrad, ya que es un enfoque para una variante in situ de aplicar el orden de clasificación a un vector. De todos modos, ya que la edición no se realizará, la pondré aquí

Aquí hay una variante in situ con una complejidad temporal ligeramente mayor que se debe a una operación primitiva de verificación de un valor booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del compilador eficiente en espacio. La complejidad de un vector puede eliminarse si se puede modificar el orden dado.

Aquí hay una variante in situ con una complejidad temporal ligeramente mayor que se debe a una operación primitiva de verificación de un valor booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del compilador eficiente en espacio. La complejidad de un vector puede eliminarse si el orden dado en sí mismo puede ser modificado. Este es un ejemplo de lo que está haciendo el algoritmo. Si el orden es 3 0 4 1 2, el movimiento de los elementos según lo indicado por los índices de posición sería 3 --- > 0; 0 --- > 1; 1 --- > 3; 2 --- > 4; 4 --- > 2.

template<typename T>
struct applyOrderinPlace
{
void operator()(const vector<size_t>& order, vector<T>& vectoOrder)
{
vector<bool> indicator(order.size(),0);
size_t start = 0, cur = 0, next = order[cur];
size_t indx = 0;
T tmp; 

while(indx < order.size())
{
//find unprocessed index
if(indicator[indx])
{   
++indx;
continue;
}

start = indx;
cur = start;
next = order[cur];
tmp = vectoOrder[start];

while(next != start)
{
vectoOrder[cur] = vectoOrder[next];
indicator[cur] = true; 
cur = next;
next = order[next];
}
vectoOrder[cur] = tmp;
indicator[cur] = true;
}
}
};

Answer 10

Aquí hay una implementación relativamente simple que usa mapeo de índice entre los nombres ordenados y no ordenados que se usarán para hacer coincidir las edades de con los ordenados nombres :

void ordered_pairs()
{
    std::vector<std::string> names;
    std::vector<int> ages;

    // read input and populate the vectors
    populate(names, ages);

    // print input
    print(names, ages);

    // sort pairs
    std::vector<std::string> sortedNames(names);
    std::sort(sortedNames.begin(), sortedNames.end());

    std::vector<int> indexMap;
    for(unsigned int i = 0; i < sortedNames.size(); ++i)
    {
        for (unsigned int j = 0; j < names.size(); ++j)
        {
            if (sortedNames[i] == names[j]) 
            {
                indexMap.push_back(j);
                break;
            }
        }
    }
    // use the index mapping to match the ages to the names
    std::vector<int> sortedAges;
    for(size_t i = 0; i < indexMap.size(); ++i)
    {
        sortedAges.push_back(ages[indexMap[i]]);
    }

    std::cout << "Ordered pairs:\n";
    print(sortedNames, sortedAges); 
}

Para completar, aquí están las funciones populate () y print () :

void populate(std::vector<std::string>& n, std::vector<int>& a)
{
    std::string prompt("Type name and age, separated by white space; 'q' to exit.\n>>");
    std::string sentinel = "q";

    while (true)
    {
        // read input
        std::cout << prompt;
        std::string input;
        getline(std::cin, input);

        // exit input loop
        if (input == sentinel)
        {
            break;
        }

        std::stringstream ss(input);

        // extract input
        std::string name;
        int age;
        if (ss >> name >> age)
        {
            n.push_back(name);
            a.push_back(age);
        }
        else
        {
            std::cout <<"Wrong input format!\n";
        }
    }
}

y:

void print(const std::vector<std::string>& n, const std::vector<int>& a)
{
    if (n.size() != a.size())
    {
        std::cerr <<"Different number of names and ages!\n";
        return;
    }

    for (unsigned int i = 0; i < n.size(); ++i)
    {
         std::cout <<'(' << n[i] << ", " << a[i] << ')' << "\n";
    }
}

Y finalmente, main () se convierte en:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

void ordered_pairs();
void populate(std::vector<std::string>&, std::vector<int>&);
void print(const std::vector<std::string>&, const std::vector<int>&);

//=======================================================================
int main()
{
    std::cout << "\t\tSimple name - age sorting.\n";
    ordered_pairs();
}
//=======================================================================
// Function Definitions...

Answer 11

**// C++ program to demonstrate sorting in vector
// of pair according to 2nd element of pair
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>

using namespace std;

// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<char,char> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

int main()
{
    // declaring vector of pairs
    vector< pair <char, int> > vect;

    // Initialising 1st and 2nd element of pairs
    // with array values
    //int arr[] = {10, 20, 5, 40 };
    //int arr1[] = {30, 60, 20, 50};
    char arr[] = { ' a', 'b', 'c' };
    int arr1[] = { 4, 7, 1 };

    int n = sizeof(arr)/sizeof(arr[0]);

    // Entering values in vector of pairs
    for (int i=0; i<n; i++)
        vect.push_back( make_pair(arr[i],arr1[i]) );

    // Printing the original vector(before sort())
    cout << "The vector before sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;

    }

    // Using sort() function to sort by 2nd element
    // of pair
    sort(vect.begin(), vect.end(), sortbysec);

    // Printing the sorted vector(after using sort())
    cout << "The vector after sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;
    }
    getchar();
    return 0;`enter code here`
}**

Answer 12

con C ++ 11 lambdas y los algoritmos STL basados ??en las respuestas de Konrad Rudolph y Gabriele D'Antona:

template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & b ){

    // zip the two vectors (A,B)
    std::vector<std::pair<T,U>> zipped(a.size());
    for( size_t i = 0; i < a.size(); i++ ) zipped[i] = std::make_pair( a[i], b[i] );

    // sort according to B
    std::sort(zipped.begin(), zipped.end(), []( auto & lop, auto & rop ) { return lop.second < rop.second; }); 

    // extract sorted A
    std::vector<T> sorted;
    std::transform(zipped.begin(), zipped.end(), std::back_inserter(sorted), []( auto & pair ){ return pair.first; }); 

    return sorted;
}

Answer 13

Muchos hicieron esta pregunta y a nadie se le ocurrió una respuesta satisfactoria. Aquí hay un std :: sort helper que permite ordenar dos vectores simultáneamente, teniendo en cuenta los valores de un solo vector. Esta solución se basa en un RadomIt personalizado (iterador aleatorio) y opera directamente en los datos vectoriales originales, sin copias temporales, reorganización de la estructura o índices adicionales:

C ++, Ordenar un vector en función de otro