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

Question

Tenho vários std::vector, todos do mesmo comprimento. Quero classificar um desses vetores, e aplicar a mesma transformação a todos os outros vetores. Existe uma maneira elegante de fazer isso? (De preferência usando o STL ou impulso)? Alguns dos vetores segurar ints e alguns deles std::strings.

código Pseudo:

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

A abordagem de friol é bom quando juntamente com o seu. Em primeiro lugar, construir um vetor consiste nos números 1 ... n , juntamente com os elementos do vetor ditando a ordem de classificação:

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

Agora você pode classificar essa matriz usando um classificador 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());

Agora que você capturou a ordem de order dentro rearranjo (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 surge com ele, aqui está uma variante que não está no local. Ele usa order como uma tabela look-up para o novo í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

Coloque os valores em uma impulso Multi-Índice recipiente seguida, iterar para ler os valores na ordem que você quiser. Você mesmo pode copiá-los para outro vector se você quiser.

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}

Agora você pode usar o vetor "índices" para o índice em "valores" vetor.

Answer 4

Apenas uma solução aproximada vem à minha mente: criar um vector que é a soma de todos os outros vetores (um vetor de estruturas, como {3, terceiro lugar, ...}, {1, First, ...}) em seguida, classificar este vector pelo primeiro campo, e depois dividir as estruturas novamente.
Provavelmente há uma melhor solução dentro impulso ou usando a biblioteca padrão.

Answer 5

Você provavelmente pode definir um costume "fachada" iterador que faz o que você precisa aqui. Seria armazenar iterators a todas suas vetores ou alternativamente obter os iteradores para todos, mas o primeiro vector do deslocamento do primeiro. A parte complicada é que isso iterador dereferences para: pensar em algo como boost :: tuple e fazer uso inteligente de boost :: empate. (Se você quer estender sobre essa idéia, você pode construir esses tipos de iterador recursiva usando modelos, mas você provavelmente nunca querer anotar o tipo de que - assim que você quer necessidade c ++ 0x auto ou uma função wrapper para tipo que leva faixas)

Answer 6

Eu acho que você realmente necessidade (mas me corrija se eu estiver errado) é uma forma de elementos de acesso de um recipiente em alguma ordem.

Ao invés de reorganizar minha coleção original, gostaria de pedir emprestado um conceito de design de banco de dados: manter um índice, ordenada por um determinado critério. Este índice é um engano extra que oferece uma grande flexibilidade.

Desta forma é possível gerar vários índices de acordo com diferentes membros de uma classe.

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

A resposta de ltjax é uma excelente abordagem - que na verdade é implementado em zip_iterator do impulso http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Ele empacota juntos em uma tupla que quer iteradores você fornecê-lo.

Você pode criar sua própria função de comparação para uma espécie baseada em qualquer combinação de iteradoras valores em sua tupla. Para esta questão, que seria apenas a primeira iteração em sua tupla.

Um recurso interessante desta abordagem é que ele permite que você mantenha a memória de cada contígua vector indivíduo (se você estiver usando vetores e é isso que você quiser). Você também não precisa armazenar um vetor índice separado de inteiros.

Answer 8

Uma variante ligeiramente mais compacto da resposta de xtofl para se você está olhando apenas para percorrer todos os seus vetores baseados no de um único vector keys. Criar um vetor de permutação e usar isso para o índice em seus outros vetores.

#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

Esta teria sido uma adenda ao resposta de Konrad como uma abordagem para uma variante no local de aplicação da ordem de classificação para um vetor. De qualquer forma, desde a edição não vai passar eu vou colocá-lo aqui

Aqui está uma variante no local com uma complexidade de tempo um pouco maior que é devido a uma operação primitiva de verificar um booleano. A complexidade de espaço adicional é de um vector que pode ser um espaço eficiente dependente da implementação compilador. A complexidade de um vector pode ser eliminado se a própria ordem dada pode ser modificado.

Aqui está uma variante no local com uma complexidade de tempo um pouco maior que é devido a uma operação primitiva de verificar um booleano. A complexidade de espaço adicional é de um vector que pode ser um espaço eficiente dependente da implementação compilador. A complexidade de um vector pode ser eliminado se a própria ordem dada pode ser modificado. Este é um exemplo do que o algoritmo está fazendo. Se a ordem for 0 3 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<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

Aqui está uma implementação relativamente simples usando mapeamento índice entre o names ordenada e não ordenada que será usado para coincidir com o ages ao names ordenou:

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

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

e

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

E, finalmente, main() torna-se:

#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

com C ++ 11 lambdas e os algoritmos STL com base nas respostas de Konrad Rudolph e 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

Assim, muitos esta pergunta e ninguém veio acima com uma resposta satisfatória. Aqui está um ajudante std :: sort que permite classificar dois vetores simultaneamente, tendo em conta os valores de apenas um vector. Esta solução baseia-se num RadomIt (iteração aleatório) personalizado, e opera directamente sobre os dados originais do vetor, sem cópias temporárias, estrutura rearranjo ou índices adicionais:

C ++, Sort Um vetor com base em outro Um