Como faço para classificar um std :: vector pelos valores de um std :: vector diferente?

Eu tenho vários std::vector , todos do mesmo tamanho. Eu quero classificar um desses vetores e aplicar a mesma transformação a todos os outros vetores. Existe uma maneira legal de fazer isso? (preferencialmente usando o STL ou Boost)? Alguns dos vetores mantêm int s e alguns deles 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" }; 

A abordagem de friol é boa quando combinada com a sua. Primeiro, construa um vetor que consiste nos números 1… n , juntamente com os elementos do vetor que ditam a ordem de sorting:

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

Agora você pode classificar essa matriz usando um classificador personalizado:

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

Agora você capturou a ordem de rearranjo dentro da order (mais precisamente, no primeiro componente dos itens). Agora você pode usar essa ordenação para classificar seus outros vetores. Há provavelmente uma variante no local muito inteligente em execução no mesmo tempo, mas até que alguém a invente, aqui está uma variante que não está no lugar. Usa order como uma tabela de consulta para o novo í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 seus valores em um contêiner Multi-Índices Boost e, em seguida, repita para ler os valores na ordem desejada. Você pode até copiá-los para outro vetor se quiser.

 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} 

Agora você pode usar o vetor "índices" para indexar no vetor "Valores".

Apenas uma solução aproximada vem à minha mente: criar um vetor que seja a sum de todos os outros vetores (um vetor de estruturas, como {3, terceiro, …}, {1, primeiro, …}), em seguida, classifique isso vetor pelo primeiro campo e, em seguida, divida as estruturas novamente.

Provavelmente existe uma solução melhor dentro do Boost ou usando a biblioteca padrão.

Você provavelmente pode definir um iterador “fachada” personalizado que faz o que você precisa aqui. Ele armazenaria os iteradores em todos os seus vetores ou, alternativamente, derivaria os iteradores para todos, menos o primeiro vetor, do deslocamento do primeiro. A parte complicada é o que o iterador desreferencia: pensar em algo como boost :: tuple e fazer uso inteligente de boost :: tie. (Se você quiser estender essa idéia, você pode construir esses tipos de iteradores recursivamente usando modelos, mas provavelmente você nunca vai querer escrever o tipo disso – então você precisa do auto de c ++ 0x ou de uma function de empacotamento para ordenar os intervalos)

Eu acho que o que você realmente precisa (mas me corrija se eu estiver errado) é uma maneira de acessar elementos de um contêiner em alguma ordem.

Em vez de reorganizar minha coleção original, eu tomaria emprestado um conceito do design do database: manter um índice, ordenado por um determinado critério. Esse índice é uma indireta extra que oferece grande flexibilidade.

Desta forma, é possível gerar múltiplos índices de acordo com diferentes membros de uma class.

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

A resposta do ltjax é uma ótima abordagem – que é realmente implementada no zip_iterator do boost http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Ele agrupa em uma tupla qualquer iterador que você fornecer.

Você pode então criar sua própria function de comparação para uma sorting baseada em qualquer combinação de valores de iterador na sua tupla. Para esta questão, seria apenas o primeiro iterador na sua tupla.

Um bom recurso dessa abordagem é que ela permite que você mantenha a memory de cada vetor contíguo (se você estiver usando vetores e é isso que você quer). Você também não precisa armazenar um vetor índice separado de ints.

Uma variante um pouco mais compacta da resposta do xtofl para se você está apenas procurando iterar através de todos os seus vetores com base no vetor de uma única tecla. Crie um vetor de permutação e use isso para indexar em seus outros vetores.

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

Isso teria sido um adendo à resposta de Konrad como uma abordagem para uma variante no local de aplicação da ordem de sorting a um vetor. De qualquer forma, já que a edição não vai passar eu vou colocar aqui

Aqui está uma variante no local com uma complexidade de tempo ligeiramente maior devido a uma operação primitiva de verificação de um booleano. A complexidade do espaço adicional é de um vetor que pode ser uma implementação dependente do compilador eficiente no espaço. A complexidade de um vetor pode ser eliminada se a própria ordem dada puder ser modificada.

Aqui está uma variante no local com uma complexidade de tempo ligeiramente maior devido a uma operação primitiva de verificação de um booleano. A complexidade do espaço adicional é de um vetor que pode ser uma implementação dependente do compilador eficiente no espaço. A complexidade de um vetor pode ser eliminada se a própria ordem dada puder ser modificada. Este é um exemplo do que o algoritmo está fazendo. Se a ordem for 3 0 4 1 2, o movimento dos elementos como indicado pelos índices de posição seria 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; } } }; 

Aqui está uma implementação relativamente simples usando o mapeamento de índice entre os names ordenados e não ordenados que serão usados ​​para corresponder as ages aos 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); } 

Por uma questão de perfeição, aqui estão as funções 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"; } } } 

e:

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

E finalmente, main() se torna:

 #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 

Muitos fizeram esta pergunta e ninguém chegou a uma resposta satisfatória. Aqui está um auxiliar std :: sort que permite classificar dois vetores simultaneamente, levando em conta os valores de apenas um vetor. Essa solução é baseada em um RadomIt personalizado (iterador random) e opera diretamente nos dados vetoriais originais, sem cópias temporárias, rearranjo de estrutura ou índices adicionais:

C ++, classificar um vetor com base em outro