Wie sortiere ich eine std :: vector durch die Werte eines anderen std :: vector?

Question

Ich habe mehrere std::vector, die alle die gleiche Länge haben. Ich möchte einen dieser Vektoren sortieren, und wenden Sie die gleiche Transformation auf alle anderen Vektoren. Gibt es eine nette Art und Weise, dies zu tun? (Vorzugsweise unter Verwendung des STL oder Boost)? Einige der Vektoren halten ints und einige von ihnen std::strings.

Pseudo-Code:

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

friol Ansatz ist gut, wenn sie mit Ihnen verbunden. Erstens baut ein Vektor bestehend aus den Zahlen 1 ... n , zusammen mit den Elementen aus dem Vektor die Sortierreihenfolge diktieren:

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

Jetzt können Sie dieses Array sortieren einen benutzerdefinierten Sortierer mit:

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

Jetzt haben Sie die Reihenfolge der Umlagerung innerhalb order (genauer: in der ersten Komponente der Elemente) erfasst. Sie können nun diese Bestellung nutzen Sie Ihre anderen Vektoren zu sortieren. Es ist wahrscheinlich eine sehr kluge in-Place-Variante in der gleichen Zeit ausgeführt wird, aber bis jemand anderes mit ihm kommt, hier ist eine Variante, die nicht an Ort und Stelle ist. Es nutzt order als Look-Up-Tabelle für den neuen Index jedes Elements.

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

Setzen Sie Ihre Werte in einem Multi-Index Container Erhöhung dann iterieren die Werte in der Reihenfolge lesen Sie wollen. Sie können sie sogar zu einem anderen Vektor kopieren, wenn Sie wollen.

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}

Nun können Sie die „Indizes“ Vektor zu Index in „Werte“ Vektor verwendet werden.

Answer 4

Nur eine grobe Lösung kommt mir in den Sinn: einen Vektor erstellen, die die Summe aller anderen Vektoren ist (ein Vektor von Strukturen, wie {3, Dritter, ...}, {1, Erste, ...}) sortiert diesen Vektors dann durch das erste Feld, und dann die Strukturen aufgespalten wieder.
Wahrscheinlich gibt es eine bessere Lösung innerhalb Erhöhung oder die Standard-Bibliothek.

Answer 5

Sie können sich wahrscheinlich eine eigene „Fassade“ Iterator definieren das tut, was Sie hier benötigen. Es wäre speichern Iteratoren auf alle Ihre Vektoren oder ableiten alternativ die Iteratoren für alle, aber den ersten Vektor aus dem Offset der ersten. Der schwierige Teil ist, was das Iterator Dereferenzierungen zu: Man denke an so etwas wie boost :: tuple und machen geschickten Einsatz von boost :: Krawatte. (Wenn Sie auf diese Idee wollen erweitern, können Sie diese Iteratortypen aufbauen können rekursiv Vorlagen verwenden, aber Sie wollen wahrscheinlich nie die Art der, dass aufzuschreiben - so müssen Sie entweder c ++ 0x Auto oder eine Wrapper-Funktion für die Bereiche Art nimmt)

Answer 6

Ich denke, was Sie wirklich müssen (aber korrigiert mich wenn ich falsch liege) ist eine Art und Weise Elemente eines Behälters in einer bestimmten Reihenfolge zugreifen zu können.

Statt meine ursprüngliche Sammlung neu anordnen, würde ich ein Konzept von Datenbank-Design ausleihen: halte einen Index, um ein bestimmtes Kriterium bestellt. Dieser Index ist eine zusätzliche Indirektion, die eine große Flexibilität bietet.

Auf diese Weise ist es möglich, mehrere Indizes zu erzeugen, nach verschiedenen Mitglieder einer Klasse.

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

ltjax Antwort ist ein großer Ansatz - die tatsächlich in boost der zip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Es Pakete zusammen in ein Tupel, was Iteratoren Sie es schaffen.

Sie können dann Ihre eigene Vergleichsfunktion für eine Art erstellen, die auf einer beliebigen Kombination von Iterator Werte in Ihrem Tupel basiert. Bei dieser Frage wäre es nur der erste Iterator in Ihrem Tupel sein.

Ein schönes Merkmal dieses Ansatzes ist, dass es Ihnen die Erinnerung an jeden einzelnen Vektor zusammenhängenden halten können (wenn Sie Vektoren verwenden und das ist, was Sie wollen). Sie brauchen auch keine separaten Indexvektor von ints zu speichern.

Answer 8

Eine etwas kompaktere Variante der Antwort des xtofl für, wenn Sie gerade auf der Suche durch alle Vektoren auf dem einem einzelnen keys Vektor-basierten iterieren. Erstellen Sie eine Permutation Vektor und verwenden diese zum Index in die andere Vektoren.

#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

Dies wäre eine Ergänzung zu Konrad Antwort, wie es einen Ansatz für eine in-Place-Variante der Anwendung der Sortierreihenfolge auf einen Vektor hat. Wie dem auch sei, da die Bearbeitung nicht durch ich es hier setzen wird

Hier ist eine In-Place-Variante mit einer etwas höheren Zeitkomplexität, die die Überprüfung einen boolean aufgrund eines primitiven Betriebes ist. Die zusätzliche Raum Komplexität ist ein Vektors, der eine platzsparende Compiler abhängig Implementierung sein. Die Komplexität eines Vektors kann beseitigt werden, wenn die gegebene Ordnung selbst geändert werden kann.

Hier ist eine In-Place-Variante mit einer etwas höheren Zeitkomplexität, die die Überprüfung einen boolean aufgrund eines primitiven Betriebes ist. Die zusätzliche Raum Komplexität ist ein Vektors, der eine platzsparende Compiler abhängig Implementierung sein. Die Komplexität eines Vektors kann beseitigt werden, wenn die gegebene Ordnung selbst modifiziert werden kann. Dies ist ein Beispiel dafür, was der Algorithmus tut. Wenn der Auftrag 3 0 4 1 2, wobei die Bewegung der Elemente, wie sie durch die Positionsindizes angegeben würde 3 sein ---> 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

Hier ist eine relativ einfache Implementierung mit Indexabbildung zwischen die geordnete und ungeordnete names, die die ages der bestellten names wird verwendet zur Seite:

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

Der Vollständigkeit halber sind hier die Funktionen populate() und 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";
        }
    }
}

und

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

Und schließlich main() wird:

#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

mit C ++ 11 Lambdas und die STL-Algorithmen basieren auf Antworten von Konrad Rudolph und 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

So viele diese Frage gestellt und niemand kam mit einer zufriedenstellenden Antwort auf. Hier ist ein std :: sort Helfer, die gleichzeitig zwei Vektoren sortieren ermöglicht, unter Berücksichtigung der Werte von nur einem Vektor. Diese Lösung basiert auf einem benutzerdefinierten RadomIt (random Iterator) und arbeitet direkt auf den ursprünglichen Vektordaten, ohne temporäre Kopien, Struktur Umlagerung oder zusätzliche Indizes:

C ++, Sort Vector One On Another One Basierend