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

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 s y algunos de ellos std::string s.

Pseudo código:

 std::vector Index = { 3, 1, 2 }; std::vector 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" }; 

El enfoque de friol es bueno cuando se combina con el tuyo. Primero, construye un vector que consta de los números 1 … n , junto con los elementos del vector que dicta el orden de clasificación:

 typedef vector::const_iterator myiter; vector > 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 con un clasificador personalizado:

 struct ordering { bool operator ()(pair const& a, pair const& b) { return *(a.second) < *(b.second); } }; sort(order.begin(), order.end(), ordering()); 

Ahora ha capturado el orden de reordenamiento dentro del order (más precisamente, en el primer componente de los ítems). 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 el order como una tabla de búsqueda para el nuevo índice de cada elemento.

 template  vector sort_from_ref( vector const& in, vector > const& reference ) { vector 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; } 

Coloque sus valores en un contenedor Boost Multi-Index y repítalo para leer los valores en el orden que desee. Incluso puede copiarlos a otro vector si lo desea.

 typedef std::vector int_vec_t; typedef std::vector str_vec_t; typedef std::vector 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".

Solo me viene a la mente una solución aproximada: crea un vector que sea la sum de todos los demás vectores (un vector de estructuras, como {3, Third, …}, {1, First, …}) luego ordena esto vector por el primer campo, y luego divide las estructuras nuevamente.

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

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 comstackr 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)

Creo que lo que realmente necesitas (pero corrígeme si estoy equivocado) 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 según un determinado criterio. Este índice es una indirección adicional que ofrece una gran flexibilidad.

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

 using namespace std; template< typename Iterator, typename Comparator > struct Index { vector 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 index ( Iterator from, Iterator end, Comparator& c ){ return Index(from,end,c); } struct mytype { string name; double number; }; template< typename Iter > struct NameLess : public binary_function { bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; } }; template< typename Iter > struct NumLess : public binary_function { 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 > byname( v, vend, NameLess() ); Index > bynum ( v, vend, NumLess () ); 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 ); } 

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

Se empaqueta en una tupla cualquiera que sea el iterador que le proporcione.

A continuación, 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 te permite mantener la memoria de cada vector individual contigua (si estás usando vectores y eso es lo que quieres). Tampoco necesita almacenar un vector de índice separado de ints.

Una variante un poco más compacta de la respuesta de xtofl para si solo buscas iterar a través de todos tus vectores en base al vector de una sola keys . Crea un vector de permutación y úsalo para indexar en tus otros vectores.

 #include  #include  #include  std::vector keys = ... std::vector values = ... std::vector indices(boost::counting_iterator(0u), boost::counting_iterator(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; } 

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, dado que la edición no se realizará, 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 comprobación de un booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del comstackdor 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 booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del comstackdor 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 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 struct applyOrderinPlace { void operator()(const vector& order, vector& vectoOrder) { vector 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; } } }; 

Aquí hay una implementación relativamente simple que utiliza la asignación de índice entre los names ordenados y desordenados que se utilizarán para hacer coincidir las ages con los names ordenados:

 void ordered_pairs() { std::vector names; std::vector ages; // read input and populate the vectors populate(names, ages); // print input print(names, ages); // sort pairs std::vector sortedNames(names); std::sort(sortedNames.begin(), sortedNames.end()); std::vector 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 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() e print() :

 void populate(std::vector& n, std::vector& 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& n, const std::vector& 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() convierte en:

 #include  #include  #include  #include  #include  void ordered_pairs(); void populate(std::vector&, std::vector&); void print(const std::vector&, const std::vector&); //======================================================================= int main() { std::cout << "\t\tSimple name - age sorting.\n"; ordered_pairs(); } //======================================================================= // Function Definitions... 
 **// C++ program to demonstrate sorting in vector // of pair according to 2nd element of pair #include  #include #include #include  using namespace std; // Driver function to sort the vector elements // by second element of pairs bool sortbysec(const pair &a, const pair &b) { return (a.second < b.second); } int main() { // declaring vector of pairs vector< pair  > 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 

Muchos hicieron esta pregunta y a 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 un RadomIt personalizado (iterador aleatorio) y opera directamente en los datos vectoriales originales, sin copias temporales, reestructuración de la estructura o índices adicionales:

C ++, ordena un vector basado en otro