sorting - Sort by proxy (or: sort one container by the contents of another) in C++

Question

I have a set of data which is split into two arrays (let's call them data and keys). That is, for any given item with an index i, I can access the data for that item with data[i] and the key for that item with keys[i]. I cannot change this structure (eg, to interleave keys and data into a single array), because I need to pass the data array to a library function which expects a certain data layout.

How can I sort both arrays (preferably using standard library functions) according to the content of the keys array?

Answer 1

Create a vector of objects that contain indices to the two arrays. Define operator< for that object to do the comparison based on keys[index]. Sort that vector. When you're done, walk through that vector and put your original objects into the order defined by those proxy objects:

// warning: untested code.
struct sort_proxy { 
    size_t i;

    bool operator<(sort_proxy const &other) const { 
        return keys[i] < keys[other.i];
    }
};

// ... key_size = number of keys/data items.
std::vector<sort_proxy> proxies(key_size); 

for (i=0; i<keys_size; i++)
    proxies[i].i = i;

std::sort(proxies.begin(), proxies.end());

// in-place reordering left as an exercise for the reader. :-)
for (int i=0; i<proxies[i].size(); i++) {
    result_keys[i] = keys[proxies[i].i];
    result_data[i] = data[proxies[i].i];
}