Sorting two arrays, one of which keeps original location.

[RadMabbit]

Hey guys, have two arrays,

string a[4] = {"3","2","1","1"}
int b[4] = {0,1,2,3}

I want to sort a into order, but at the same time, sort a into the same order so that after I have done some stuff to a, I can use b to re order a into the original order.

I want this
string a[4] = {"1","1","2","3"}
int b[4] = {2,3,1,1}

Any help would be great!

[RadMabbit]

Is there a way that can be done whilst also keeping an nlog(n) complexity?

[Cubbi]

Assuming there was a typo in your example and the intention was to end up with b == {2,3,1,0}, typically you would use a map for this:

#include <iostream>
#include <string>
#include <map>

int main()
{
    std::string a[4] = {"3","2","1","1"};
    int b[4] = {0,1,2,3};

    // copy into a map
    // could use a map of proxy objects if you don't want space overhead
    std::multimap<std::string, int> m;
    for(size_t i = 0; i < 4; ++i) // or use zip_iterator for the fancy
        m.insert(make_pair(a[i], b[i]));

    // copy back
    size_t i = 0;
    for(auto& p : m) {
       a[i] = p.first;
       b[i++] = p.second;
    }

    std::cout << "The first array is now: ";
    for(auto& s : a)
        std::cout << '"' << s << "\" ";
    std::cout << "\nThe second array is now: ";
    for(auto& n : b)
        std::cout << n << ' ';
    std::cout << '\n';
}

I get:

The first array is now: "1" "1" "2" "3" 
The second array is now: 2 3 1 0 

(you could do it in-place too, but it's a bit involving: http://stackoverflow.com/a/3406274/273767 -- but then why not have a map to start with?)

[RadMabbit]

Awesome, thats freaking great!

How would I then reverse this, I just tried switching line 12 and 14, but it didnt quite work.
NEVER MIND, got it!