Sorting Three vectors based on the arrangement of

问题:

vector<int> reference = ages;
sort(ages.begin(),ages.end());
for (int i=0; i<20 ;++i){
    for (int j=0; j<20; ++j){
        if (ages[i]==reference[j]){
            cout << setw(LongestString(names))<<names[j] <<setw(agewidth)<<ages[i]<<setw(probwidth)<<prob[j]<<endl;
        }
    }
}

So I have a three vectors and I want to sort them based off of the ages, and then reorder them. However, there are repetitions in the ages, so whenever it gets to those it prints them multiple times. Is there a way to prevent that without the creation of a structure?

回答1:

Generate a vector of indices from 0 to ages.size()-1. Sort the indices according to ages, probably using a lambda compare function. Then reorder all three vectors according to the sorted vector of indices. This will keep all three vectors in "sync", regardless of any duplicates in ages.

The reordering is simple if you just copy a vector according to indices sorted[i] = original[sorted_index[i]]. Reordering in place can also be done, as shown in the example below, but it's a little known algorithm, and if this is homework, I don't know where a student would be expected to be aware of this algorithm or be able to find examples of this algorithm. The algorithm is based on the fact that a permutation can be considered as a sequence of cycles:

http://en.wikipedia.org/wiki/Permutation#Cycle_notation

    std::vector <int> A;                // ages
    std::vector <std::string> N;        // names
    std::vector <int> Z;                // zip codes
    std::vector <size_t> I;             // indices

    // vectors A, N, Z are initialized here ...

    // initialize vector of indices
    for(size_t i = 0; i < A.size(); i++)
        I.push_back(i);
    // sort vector of indices according to A
    std::stable_sort(I.begin(), I.end(),
        [&A](size_t i, size_t j) {return 
        A[i] < A[j];});
    // reorder A, N, Z in place also restore I back to 0 to size-1
    // time complexity is O(n)
    // every move places an element in its sorted position
    for(size_t i = 0; i < A.size(); i++){
        size_t j, k;
        int tA;                         // temp variables
        std::string tN;
        int tZ;
        if(i != I[i]){
            tA = A[i];
            tN = N[i];
            tZ = Z[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                N[k] = N[j];
                Z[k] = Z[j];
                I[k] = k;
                k = j;
            }
            A[k] = tA;
            N[k] = tN;
            Z[k] = tZ;
            I[k] = k;
        }
    }