Come faccio a ordinare uno std :: vector in base ai valori di un diverso std :: vector?

Question

Ho diversi std :: vector , tutti della stessa lunghezza. Voglio ordinare uno di questi vettori e applicare la stessa trasformazione a tutti gli altri vettori. C'è un modo pulito per farlo? (preferibilmente usando STL o Boost)? Alcuni vettori contengono int e alcuni std :: string s.

Codice 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

L'approccio di friol è buono se abbinato al tuo. Innanzitutto, crea un vettore composto dai numeri 1 ... n , insieme agli elementi del vettore che dettano l'ordinamento:

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

Ora puoi ordinare questo array usando un selezionatore personalizzato:

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

Ora hai catturato l'ordine di riorganizzazione all'interno di order (più precisamente, nel primo componente degli articoli). È ora possibile utilizzare questo ordinamento per ordinare gli altri vettori. Probabilmente esiste una variante sul posto molto intelligente in esecuzione nello stesso tempo, ma fino a quando qualcun altro non ne esce, ecco una variante che non è sul posto. Utilizza order come tabella di ricerca per il nuovo indice di ciascun 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

Inserisci i tuoi valori in un Potenzia il contenitore Multi-Index quindi scorrere per leggere i valori nell'ordine desiderato. Puoi anche copiarli su un altro vettore, se lo desideri.

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}

Ora puoi utilizzare gli " indici " vettore da indicizzare in " Valori " vettoriale.

Answer 4

Mi viene in mente solo una soluzione approssimativa: creare un vettore che è la somma di tutti gli altri vettori (un vettore di strutture, come {3, Third, ...}, {1, First, ...}) quindi ordinare questo vettore per il primo campo e quindi dividere nuovamente le strutture.

Probabilmente esiste una soluzione migliore all'interno di Boost o utilizzando la libreria standard.

Answer 5

Probabilmente puoi definire una facciata " personalizzata " iteratore che fa quello che ti serve qui. Memorizzerebbe gli iteratori su tutti i tuoi vettori o in alternativa trarrebbe gli iteratori per tutti tranne il primo vettore dall'offset del primo. La parte difficile è ciò a cui l'iteratore fa riferimento: pensa a qualcosa come boost :: tuple e fai un uso intelligente di boost :: tie. (Se vuoi estendere questa idea, puoi costruire questi tipi di iteratori in modo ricorsivo usando i modelli ma probabilmente non vorrai mai scriverne il tipo - quindi hai bisogno di c ++ 0x auto o una funzione wrapper per l'ordinamento che accetta intervalli)

Answer 6

Penso che ciò di cui veramente hai bisogno (ma correggimi se sbaglio) è un modo per accedere agli elementi di un contenitore in un certo ordine.

Invece di riorganizzare la mia collezione originale, prenderei in prestito un concetto dal design del database: mantenere un indice, ordinato secondo un determinato criterio. Questo indice è un ulteriore riferimento indiretto che offre una grande flessibilità.

In questo modo è possibile generare più indici in base ai diversi membri di una 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

La risposta di ltjax è un ottimo approccio, che in realtà è implementato in zip_iterator di boost http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Raggruppa in una tupla qualunque iteratore tu gli fornisca.

Puoi quindi creare la tua funzione di confronto per un ordinamento basato su qualsiasi combinazione di valori iteratori nella tua tupla. Per questa domanda, sarebbe solo il primo iteratore nella tua tupla.

Una bella caratteristica di questo approccio è che ti permette di mantenere contigua la memoria di ogni singolo vettore (se stai usando i vettori ed è quello che vuoi). Inoltre, non è necessario memorizzare un indice separato di ints.

Answer 8

Una variante leggermente più compatta della risposta di xtofl se stai solo cercando di scorrere tutti i tuoi vettori in base al singolo vettore keys . Crea un vettore di permutazione e usalo per indicizzare i tuoi altri vettori.

#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

Questo sarebbe stato un addendum alla risposta di Konrad in quanto approccio per una variante sul posto di applicare l'ordinamento a un vettore. Comunque dal momento che la modifica non verrà eseguita, la inserirò qui

Ecco una variante sul posto con una complessità temporale leggermente superiore dovuta a un'operazione primitiva di controllo di un valore booleano. La complessità dello spazio aggiuntiva è di un vettore che può essere un'implementazione dipendente dal compilatore efficiente nello spazio. La complessità di un vettore può essere eliminata se l'ordine dato stesso può essere modificato.

Ecco una variante sul posto con una complessità temporale leggermente superiore dovuta a un'operazione primitiva di controllo di un valore booleano. La complessità dello spazio aggiuntiva è di un vettore che può essere un'implementazione dipendente dal compilatore efficiente nello spazio. La complessità di un vettore può essere eliminata se l'ordine dato stesso può essere modificato. Questo è un esempio di ciò che sta facendo l'algoritmo. Se l'ordine è 3 0 4 1 2, il movimento degli elementi come indicato dagli indici di posizione sarebbe 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

Ecco un'implementazione relativamente semplice che utilizza mappatura dell'indice tra i nomi ordinati e non ordinati che verrà utilizzata per abbinare età a quella ordinata nomi :

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

Per completezza, ecco le funzioni 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 infine, main () diventa:

#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 e algoritmi STL basati sulle risposte di 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

Così tanti hanno posto questa domanda e nessuno ha trovato una risposta soddisfacente. Ecco un aiuto std :: sort che consente di ordinare due vettori contemporaneamente, tenendo conto dei valori di un solo vettore. Questa soluzione si basa su un RadomIt (iteratore casuale) personalizzato e opera direttamente sui dati vettoriali originali, senza copie temporanee, riorganizzazione della struttura o indici aggiuntivi:

C ++, ordina un vettore in base a un altro