Wie kann ich zwei Vektoren auf dieselbe Weise sortieren, wobei Kriterien nur einen der Vektoren verwenden?

Angenommen, ich habe zwei Vektoren gleicher Größe:

vector<MyObject> vectorA;
vector<int> vectorB;

Ich sortiere dann vectorAmit einer Vergleichsfunktion. Diese Sortierung wurde neu angeordnet vectorA. Wie kann ich die gleiche Nachbestellung anwenden lassen vectorB?

Eine Möglichkeit besteht darin, eine Struktur zu erstellen:

struct ExampleStruct {
    MyObject mo;
    int i;
};

und sortieren Sie dann einen Vektor, der den Inhalt von enthält vectorAund vectorBin einen einzelnen Vektor komprimiert ist:

// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;

Dies scheint keine ideale Lösung zu sein. Gibt es andere Optionen, insbesondere in C ++ 11?

Eine Sortierpermutation finden

Mit einem std::vector<T>und einem Vergleich für T's möchten wir in der Lage sein, die Permutation zu finden, die Sie verwenden würden, wenn Sie den Vektor mithilfe dieses Vergleichs sortieren würden.

template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
    const std::vector<T>& vec,
    Compare& compare)
{
    std::vector<std::size_t> p(vec.size());
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
    return p;
}

Anwenden einer Sortierpermutation

Bei einer std::vector<T>und einer Permutation möchten wir in der Lage sein, eine neue zu erstellen std::vector<T>, die entsprechend der Permutation neu angeordnet wird.

template <typename T>
std::vector<T> apply_permutation(
    const std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<T> sorted_vec(vec.size());
    std::transform(p.begin(), p.end(), sorted_vec.begin(),
        [&](std::size_t i){ return vec[i]; });
    return sorted_vec;
}

Sie können natürlich ändern apply_permutation den Vektor , den Sie ihm geben, anstatt eine neue sortierte Kopie zurückzugeben. Dieser Ansatz ist immer noch linear zeitlich komplex und verwendet ein Bit pro Element in Ihrem Vektor. Theoretisch ist es immer noch lineare Raumkomplexität; In der Praxis kann sizeof(T)die Reduzierung der Speichernutzung jedoch dramatisch sein , wenn sie groß ist. ( Siehe Details )

template <typename T>
void apply_permutation_in_place(
    std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<bool> done(vec.size());
    for (std::size_t i = 0; i < vec.size(); ++i)
    {
        if (done[i])
        {
            continue;
        }
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = p[i];
        while (i != j)
        {
            std::swap(vec[prev_j], vec[j]);
            done[j] = true;
            prev_j = j;
            j = p[j];
        }
    }
}

Beispiel

vector<MyObject> vectorA;
vector<int> vectorB;

auto p = sort_permutation(vectorA,
    [](T const& a, T const& b){ /*some comparison*/ });

vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);

Ressourcen

• std::vector
• std::iota
• std::sort
• std::swap
• std::transform

Mit range-v3 ist es einfach, eine Zip-Ansicht zu sortieren:

std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;

ranges::v3::sort(ranges::view::zip(vectorA, vectorB));

oder explizit Projektion verwenden:

ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
                 std::less<>{},
                 [](const auto& t) -> decltype(auto) { return std::get<0>(t); });

Demo

Ich möchte mit einer Erweiterung beitragen, die ich mir ausgedacht habe. Ziel ist es, mit einer einfachen Syntax mehrere Vektoren gleichzeitig sortieren zu können.

sortVectorsAscending(criteriaVec, vec1, vec2, ...)

Der Algorithmus ist der gleiche wie der von Timothy vorgeschlagene, verwendet jedoch verschiedene Vorlagen , sodass wir mehrere Vektoren beliebigen Typs gleichzeitig sortieren können.

Hier ist das Code-Snippet:

template <typename T, typename Compare>
void getSortPermutation(
    std::vector<unsigned>& out,
    const std::vector<T>& v,
    Compare compare = std::less<T>())
{
    out.resize(v.size());
    std::iota(out.begin(), out.end(), 0);

    std::sort(out.begin(), out.end(),
        [&](unsigned i, unsigned j){ return compare(v[i], v[j]); });
}

template <typename T>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t)
{
    assert(order.size() == t.size());
    std::vector<T> st(t.size());
    for(unsigned i=0; i<t.size(); i++)
    {
        st[i] = t[order[i]];
    }
    t = st;
}

template <typename T, typename... S>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t,
    std::vector<S>&... s)
{
    applyPermutation(order, t);
    applyPermutation(order, s...);
}

template<typename T, typename Compare, typename... SS>
void sortVectors(
    const std::vector<T>& t,
    Compare comp,
    std::vector<SS>&... ss)
{
    std::vector<unsigned> order;
    getSortPermutation(order, t, comp);
    applyPermutation(order, ss...);
}

// make less verbose for the usual ascending order
template<typename T, typename... SS>
void sortVectorsAscending(
    const std::vector<T>& t,
    std::vector<SS>&... ss)
{
    sortVectors(t, std::less<T>(), ss...);
}

Testen Sie es in Ideone .

Ich erkläre das in diesem Blog-Beitrag etwas besser .

In-Place-Sortierung mittels Permutation

Ich würde eine Permutation wie Timothy verwenden, obwohl , wenn Ihre Daten zu groß ist und Sie nicht mehr Speicher für den sortierten Vektor zuordnen wollen Sie es tun sollten , an Ort und Stelle . Hier ist ein Beispiel für eine In-Place-Sortierung mit O (n) (lineare Komplexität) unter Verwendung von Permutation :

Der Trick besteht darin, die Permutation und die umgekehrte Permutation zu ermitteln, wo die durch den letzten Sortierschritt überschriebenen Daten abgelegt werden sollen.

template <class K, class T> 
void sortByKey(K * keys, T * data, size_t size){
    std::vector<size_t> p(size,0);
    std::vector<size_t> rp(size);
    std::vector<bool> sorted(size, false);
    size_t i = 0;

    // Sort
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
                    [&](size_t i, size_t j){ return keys[i] < keys[j]; });

    // ----------- Apply permutation in-place ---------- //

    // Get reverse permutation item>position
    for (i = 0; i < size; ++i){
        rp[p[i]] = i;
    }

    i = 0;
    K savedKey;
    T savedData;
    while ( i < size){
        size_t pos = i;
        // Save This element;
        if ( ! sorted[pos] ){
            savedKey = keys[p[pos]];
            savedData = data[p[pos]];
        }
        while ( ! sorted[pos] ){
            // Hold item to be replaced
            K heldKey  = keys[pos];
            T heldData = data[pos];
            // Save where it should go
            size_t heldPos = rp[pos];

            // Replace 
            keys[pos] = savedKey;
            data[pos] = savedData;

            // Get last item to be the pivot
            savedKey = heldKey;
            savedData = heldData;

            // Mark this item as sorted
            sorted[pos] = true;

            // Go to the held item proper location
            pos = heldPos;
        }
        ++i;
    }
}

1. Machen Sie aus Ihren einzelnen Vektoren einen Paarvektor.
   Vektor von Paaren initialisieren
   Hinzufügen zu einem Vektor von Paaren

2. Erstellen Sie einen benutzerdefinierten Sortierkomparator:
   Sortieren eines Vektors mit benutzerdefinierten Objekten
   http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B

3. Sortieren Sie Ihren Vektor von Paaren.

4. Trennen Sie Ihren Paarvektor in einzelne Vektoren.

5. Setzen Sie all dies in eine Funktion ein.

Code:

std::vector<MyObject> vectorA;
std::vector<int> vectorB;

struct less_than_int
{
    inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
    {
        return (a.second < b.second);
    }
};

sortVecPair(vectorA, vectorB, less_than_int());

// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{

    std::vector<pair<T,R>> vecC;
    vecC.reserve(vecA.size());
    for(int i=0; i<vecA.size(); i++)
     {
        vecC.push_back(std::make_pair(vecA[i],vecB[i]);   
     }

    std::sort(vecC.begin(), vecC.end(), cmp);

    vecA.clear();
    vecB.clear();
    vecA.reserve(vecC.size());
    vecB.reserve(vecC.size());
    for(int i=0; i<vecC.size(); i++)
     {
        vecA.push_back(vecC[i].first);
        vecB.push_back(vecC[i].second);
     }
}

Ich gehe davon aus, dass vectorA und vectorB gleich lang sind. Sie könnten einen anderen Vektor erstellen, nennen wir ihn pos, wobei:

pos[i] = the position of vectorA[i] after sorting phase

und dann können Sie vectorB mit pos sortieren, dh vectorBsorted erstellen, wobei:

vectorBsorted[pos[i]] = vectorB[i]

und dann wird vectorBsorted nach der gleichen Permutation von Indizes sortiert wie vectorA.

Ich bin nicht sicher, ob das funktioniert, aber ich würde so etwas verwenden. Zum Beispiel würde ich zum Sortieren von zwei Vektoren die Methode der absteigenden Blasensortierung und Vektorpaare verwenden.

Für absteigende Blasensortierung würde ich eine Funktion erstellen, die ein Vektorpaar erfordert.

void bubbleSort(vector< pair<MyObject,int> >& a)
{
    bool swapp = true;
    while (swapp) {
        int key;
        MyObject temp_obj;
        swapp = false;
        for (size_t i = 0; i < a.size() - 1; i++) {
            if (a[i].first < a[i + 1].first) {
                temp_obj = a[i].first;
                key = a[i].second;

                a[i].first = a[i + 1].first;
                a[i + 1].first = temp_obj;

                a[i].second = a[i + 1].second;
                a[i + 1].second = key;

                swapp = true;
            }
        }
    }
}

Danach würde ich Ihre 2 Vektorwerte in ein Vektorpaar setzen. Wenn Sie in der Lage sind, gleichzeitig Werte hinzuzufügen, verwenden Sie diesen und rufen Sie dann die Blasensortierfunktion auf.

vector< pair<MyObject,int> > my_vector;

my_vector.push_back( pair<MyObject,int> (object_value,int_value));

bubbleSort(my_vector);

Wenn Sie nach dem Hinzufügen zu Ihren 2 Vektoren Werte verwenden möchten, können Sie diesen verwenden und dann die Blasensortierfunktion aufrufen.

vector< pair<MyObject,int> > temp_vector;

for (size_t i = 0; i < vectorA.size(); i++) {
            temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
        }

bubbleSort(temp_vector);

Ich hoffe das hilft. Grüße, Caner

Ich habe kürzlich einen richtigen Zip-Iterator geschrieben, der mit den STL-Algorithmen funktioniert. Damit können Sie Code wie folgt erstellen:

std::vector<int> a{3,1,4,2};
std::vector<std::string> b{"Alice","Bob","Charles","David"};

auto zip = Zip(a,b);
std::sort(zip.begin(), zip.end());

for (const auto & z: zip) std::cout << z << std::endl;

Es ist in einem einzelnen Header enthalten und die einzige Voraussetzung ist C ++ 17. Schau es dir auf GitHub an .

Es gibt auch einen Beitrag auf codereview, der den gesamten Quellcode enthält.

Basierend auf Timothy Shields Antwort.
Mit einer kleinen Änderung anapply_permutaion Sie die Permutation mithilfe eines Fold-Ausdrucks auf mehrere Vektoren unterschiedlichen Typs gleichzeitig anwenden.

template <typename T, typename... Ts>
void apply_permutation(const std::vector<size_t>& perm, std::vector<T>& v, std::vector<Ts>&... vs) {

    std::vector<bool> done(v.size());
    for(size_t i = 0; i < v.size(); ++i) {
        if(done[i]) continue;
        done[i] = true;
        size_t prev = i;
        size_t curr = perm[i];
        while(i != curr) {
            std::swap(v[prev], v[curr]);
            (std::swap(vs[prev], vs[curr]), ...);
            done[curr] = true;
            prev = curr;
            curr = perm[curr];
        }
    }
}