¿Cómo puedo ordenar 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 buena manera de hacer esto? (preferiblemente usando el STL o Boost)? Algunos de los vectores contienen int sy algunos de ellos std::strings.

Pseudo có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. En primer lugar, construir un vector que consiste en los números 1 ... 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 se puede ordenar este array 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 reordenació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 exista una variante en contexto muy inteligente que se ejecute 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

Sólo una solución aproximada viene a la mente: crear un vector que es la suma de todos los otros vectores (un vector de estructuras, como {3, tercera, ...} , {1, Primero, ...}) luego ordena este vector por el primer campo, y luego divide las estructuras nuevamente.

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

Answer 3

Creo que lo que realmente necesidad (pero corrígeme si me equivoco) es una manera de acceder a los elementos de un contenedor en un cierto orden.

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

De esta manera es posible generar múltiples índices según 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 4

Ponga sus valores en un Boost Multi-Index container continuación, iterar sobre para leer los valores en el orden que desee. Incluso puede copiarlos a otro vector si lo desea.

Answer 5

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 el vector "índices" para indexar en el vector "Valores".

Answer 6

Probablemente pueda definir un iterador de "fachada" personalizado que haga lo que necesita aquí. Almacenaría iteradores a todos sus vectores o, alternativamente, derivaría los iteradores para todos menos el primer vector del desplazamiento del primero. La parte difícil es a lo que se refiere el iterador: piense en algo como boost :: tuple y haga un uso inteligente de boost :: tie.(Si desea ampliar esta idea, puede compilar estos tipos de iteradores de forma recursiva mediante plantillas, pero probablemente nunca desee escribir el tipo de eso, por lo que necesita C++ 0x auto o una función de envoltura para ordenamiento que tome rangos) respuesta

Answer 7

de ltjax es un gran acercamiento - que se llevan a la práctica zip_iterator de impulso http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

se empaqueta juntos en una tupla lo iteradores que la proporcione.

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 de tu tupla.

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

Answer 8

Una variante ligeramente más compacta de la respuesta de xtofl para si solo buscas iterar a través de todos tus vectores en función de un solo vector keys. Crea un vector de permutación y úsalo para indexar en tus 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 un enfoque para una variante en lugar de aplicar el criterio de ordenación de un vector. De todos modos, dado que la edición no se procesará, la pondré aquí

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

Aquí hay una variante in situ con una complejidad de tiempo ligeramente mayor que se debe a una operación primitiva de comprobación de un valor booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del compilador de espacio eficiente. La complejidad de un vector puede eliminarse si el orden dado puede ser modificado. Este es un ejemplo de lo que el algoritmo está haciendo. Si la 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í es una implementación relativamente simple usando mapeo índice entre el names ordenadas y desordenadas que será utilizado para que coincida con la ages a la names ordenado:

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); 
} 

En aras de la exhaustividad, 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, se convierte en main():

#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

Tantos hecho esta pregunta y nadie se le ocurrió una respuesta satisfactoria.Aquí hay un auxiliar std :: sort que permite ordenar dos vectores simultáneamente, teniendo en cuenta los valores de un solo vector. Esta solución se basa en una costumbre RadomIt (iterador al azar), y opera directamente sobre los datos de vector, sin copias temporales, estructura de reordenamiento o índices adicionales:

C++, Sort One Vector Based On Another One