Jak mogę posortować dwa wektory w ten sam sposób, stosując kryteria, które używają tylko jednego z wektorów?

Na przykład załóżmy, że mam dwa wektory o tym samym rozmiarze:

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

Następnie sortuję, vectorAużywając funkcji porównania. To sortowanie zostało zmienione vectorA. Jak mogę zastosować tę samą zmianę kolejności vectorB?

Jedną z opcji jest utworzenie struktury:

struct ExampleStruct {
    MyObject mo;
    int i;
};

a następnie posortuj wektor zawierający zawartość vectorAi vectorBspakowany w jeden wektor:

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

Nie wydaje się to idealnym rozwiązaniem. Czy są inne opcje, szczególnie w C ++ 11?

Znajdowanie permutacji sortowania

Biorąc pod uwagę a std::vector<T>i porównanie dla T's, chcemy być w stanie znaleźć permutację, której użyłbyś, gdybyś posortował wektor za pomocą tego porównania.

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

Stosowanie permutacji sortowania

Biorąc pod uwagę a std::vector<T>i permutację, chcemy móc zbudować nową, std::vector<T>która jest uporządkowana zgodnie z permutacją.

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

Możesz oczywiście zmodyfikować, apply_permutationaby zmodyfikować otrzymany wektor, zamiast zwracać nową posortowaną kopię. To podejście jest nadal liniową złożonością czasową i wykorzystuje jeden bit na element w wektorze. Teoretycznie jest to wciąż liniowa złożoność przestrzeni; ale w praktyce, gdy sizeof(T)jest duży, zmniejszenie zużycia pamięci może być dramatyczne. ( Zobacz szczegóły )

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

Przykład

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

Zasoby

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

Z range-v3 , jest to proste, posortuj widok zip:

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

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

lub wyraźnie użyj odwzorowania:

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

Próbny

Chciałbym wnieść swój wkład w rozszerzenie, które wymyśliłem. Celem jest umożliwienie sortowania wielu wektorów w tym samym czasie przy użyciu prostej składni.

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

Algorytm jest taki sam, jak ten, który zaproponował Timothy, ale wykorzystuje różne szablony , więc możemy sortować wiele wektorów dowolnego typu w tym samym czasie.

Oto fragment kodu:

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

Przetestuj w Ideone .

Wyjaśnię to trochę lepiej w tym wpisie na blogu .

Sortowanie w miejscu przy użyciu permutacji

Użyłbym permutacji, takiej jak Timothy, chociaż jeśli twoje dane są zbyt duże i nie chcesz przydzielać więcej pamięci dla posortowanego wektora, powinieneś to zrobić na miejscu . Oto przykład sortowania lokalnego O (n) (złożoność liniowa) przy użyciu permutacji :

Sztuczka polega na uzyskaniu permutacji i permutacji odwrotnej, aby wiedzieć, gdzie umieścić dane nadpisane w ostatnim kroku sortowania.

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. Z poszczególnych wektorów utwórz wektor par.
   zainicjalizuj wektor par
   Dodawanie do wektora pary

2. Utwórz niestandardowy komparator sortowania:
   sortowania Sortowanie wektora obiektów niestandardowych
   http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B

3. Sortuj swój wektor par.

4. Rozdziel wektor par na pojedyncze wektory.

5. Umieść to wszystko w funkcji.

Kod:

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

Zakładam, że wektory A i B mają równe długości. Możesz stworzyć inny wektor, nazwijmy go pos, gdzie:

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

a następnie możesz posortować vectorB za pomocą pos, tj. utworzyć vectorBsorted gdzie:

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

a następnie wektorBsorted jest sortowany według tej samej permutacji indeksów, co wektor A.

Nie jestem pewien, czy to zadziała, ale użyłbym czegoś takiego. Na przykład, aby posortować dwa wektory, użyłbym malejącej metody sortowania bąbelkowego i par wektorów.

W przypadku malejącego sortowania bąbelkowego utworzyłbym funkcję wymagającą pary wektorów.

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

Następnie umieściłbym twoje 2 wartości wektorowe w jednej parze wektorów. Jeśli możesz dodawać wartości w tym samym czasie, użyj tego, a następnie wywołaj funkcję sortowania bąbelkowego.

vector< pair<MyObject,int> > my_vector;

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

bubbleSort(my_vector);

Jeśli chcesz użyć wartości po dodaniu do 2 wektorów, możesz użyć tego, a następnie wywołać funkcję sortowania bąbelkowego.

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

Mam nadzieję, że to pomoże. Pozdrawiam, Caner

Niedawno napisałem odpowiedni iterator zip, który działa z algorytmami STL. Pozwala na tworzenie takiego kodu:

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;

Jest zawarty w jednym nagłówku, a jedynym wymaganiem jest C ++ 17. Sprawdź to na GitHub .

Jest też post na codereview, który zawiera cały kod źródłowy.

Na podstawie odpowiedzi Timothy Shields.
Dzięki niewielkiej poprawce apply_permutaionmożesz zastosować permutację do wielu wektorów różnych typów jednocześnie, używając wyrażenia zwinięcia.

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