Tworzenie wektora indeksów posortowanego wektora

Question

Zmienna x jest wektorem n ints i chcę posortować wektor w porządku rosnącym. Jednak z przyczyn nieobjętych zakresem tego pytania chcę, aby wektor pozostał nienaruszony. W związku z tym, zamiast faktycznie sortować zawartość x, chcę utworzyć kolejny wektor z indeksów n, gdzie każdy indeks odnosi się do odpowiedniej wartości w x, jeśli zostały posortowane x.

Na przykład:

std::vector<int> x = {15, 3, 0, 20}; 
std::vector<int> y; 
// Put the sorted indices of x into the vector y 
for (int i = 0; i < 4; i++) 
{ 
    std::cout << y[i]; 
} 

powinien dać wyjście:

2 
1 
0 
3 

odpowiadające wartościom w X:

0 
3 
15 
20 

mogę myśleć o wiele aktualnych sposobów realizacji tego , ale zastanawiam się, czy STL ma coś wbudowanego, aby wydajnie to dla mnie wykonać?

Answer 1

1) Tworzenie y jako wektor wskaźnika (e zakres liczb całkowitych)

2) Sortowanie ten zakres w komparator, który zwraca elementy indeksy od x Korzystanie Biblioteka standardowa, która daje:

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main() { 

    std::vector<int> x = {15, 3, 0, 20}; 

    std::vector<int> y; 

    std::vector<int> y(x.size()); 
    std::size_t n(0); 
    std::generate(std::begin(y), std::end(y), [&]{ return n++; }); 

    std::sort( std::begin(y), 
       std::end(y), 
       [&](int i1, int i2) { return x[i1] < x[i2]; }); 

    for (auto v : y) 
     std::cout << v << ' '; 

    return 0; 
} 

Live demo.

Answer 2

Fill y ze wszystkimi wskaźnikami x następnie użyć std::sort na y ale zapewniają komparator który porównuje odpowiednie elementy w x:

std::vector<int> y(x.size()); 
    std::iota(y.begin(), y.end(), 0); 
    auto comparator = [&x](int a, int b){ return x[a] < x[b]; }; 
    std::sort(y.begin(), y.end(), comparator); 

Answer 3

można zrobić coś w rodzaju do innej listy następnie porównanie z nieposortowane lista następnie 3rd lista, gdzie można przechowywać indeksy tj nlog(n) + n^2 czy tylko O(n^2)

Uwaga: to kod pseudo

vector<int> x = {15, 3, 0, 20}; 
vector<int> y = sort(x); 
vector<in> z; 
for(int i = 0; y < y.size(); i++){ 
    for(int j = 0; j < y.size(); j++){ 
     if(y[i] == x[j]){ 
     z.push_back(j); 
     } 
    } 
} 

Answer 4

Możesz podać własny komparator, który sprawdza wartości docelowego VECTOR podczas sortowania wektor indeksów raczej tak:

#include <vector> 
#include <iostream> 
#include <algorithm> 

struct IdxCompare 
{ 
    const std::vector<int>& target; 

    IdxCompare(const std::vector<int>& target): target(target) {} 

    bool operator()(int a, int b) const { return target[a] < target[b]; } 
}; 

int main() 
{ 
    std::vector<int> x = {15, 3, 0, 20}; 
    std::vector<int> y; 

    // initialize indexes 
    for(size_t i = 0; i < x.size(); ++i) 
     y.push_back(i); 

    std::sort(y.begin(), y.end(), IdxCompare(x)); 

    std::cout << "\nvector x: " << '\n'; 
    for(size_t i = 0; i < x.size(); ++i) 
     std::cout << x[i] << '\n'; 

    std::cout << "\nvector y: " << '\n'; 
    for(size_t i = 0; i < x.size(); ++i) 
     std::cout << y[i] << '\n'; 

    std::cout << "\nvector x through y: " << '\n'; 
    for(size_t i = 0; i < x.size(); ++i) 
     std::cout << x[y[i]] << '\n'; 
} 

WYJŚCIE:

vector x: 
15 
3 
0 
20 

vector y: 
2 
1 
0 
3 

vector x through y: 
0 
3 
15 
20 

Answer 5

Możemy wziąć " oznacza "podejście bezpośrednio i użyj tablicy wskaźników do wartości w wektorze źródłowym.

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main(int argc, const char * argv[]) { 
    //a source vector, who's order shouldn't be changed 
    std::vector<int> values = {15, 4, 20, 25, 0, 19, -5}; 
    //a vector of pointers to the values in the source vector 
    std::vector<int *> pointersToValues; 
    pointersToValues.reserve(values.size()); 

    for(auto& value : values){ 
     pointersToValues.push_back(&value); 
    } 

    //two comparators in form of lambda functions 
    auto descendingOrderSorter = [](int * i, int * j){ 
     return *i > *j; 
    }; 

    auto ascendingOrderSorter = [](int * i, int * j){ 
     return *i < *j; 
    }; 

    //examples of usage 
    std::cout<<"Sorting in a descending order"<<std::endl; 
    std::sort(pointersToValues.begin(), pointersToValues.end(), descendingOrderSorter); 
    for(int i = 0; i < pointersToValues.size(); ++i) { 
     std::cout << "index: " << i << ", value: " << *pointersToValues[i] << std::endl; 
    } 

    std::cout<<"Sorting in an ascending order"<<std::endl; 
    std::sort(pointersToValues.begin(), pointersToValues.end(), ascendingOrderSorter); 
    for(int i = 0; i < pointersToValues.size(); ++i) { 
     std::cout << "index: " << i << ", value: " << *pointersToValues[i] << std::endl; 
    } 

    return 0; 
} 

pointersToValues ​​[i] co daje wskaźnik do pierwotnej wartości, * pointersToValues ​​[i] co daje wartość.