Re: Sorting two arrays with one call to sort()?
On 2007-09-22 13:24, John wrote:
I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...copying/merging the arrays is out of
question...
No, it can not be done with any of the standard C++ algorithms, you
would have to implement your own sort function for this.
It seems to me that you greatest problem is an error in the design,
keeping related data in two separate containers, if element A[i] is
somehow related to B[i] then you need to make that relation explicit in
the code. Without knowing about your circumstances I would say that a
second design error is to use an array instead of std::vector.
You ought to store the data in an std::vector<std::pair<A,B> >, where A
and B is the types of the elements in A and B respectively. Another
alternative is to use std::map<A,B> which is sorted from the beginning.
A third possibility, depending on how you need to access the elements in
B is to make each element in A an std::pair<A, B*> and let the pointer
point to the correct element in B, using this scheme will not sort B but
you will keep the relationship between the elements.
Yes, I know that you said that copying or merging the arrays were out of
question, but on the other hand you said that speed was paramount, and
any one of the schemes above will most probably be faster than whatever
you come up with while trying to re-implement a sorting function.
I would probably do something like this if I was required to keep the
two structures separate:
// Create a vector to store the elements
std::vector<std::pair<A, B> > vec;
vec.reserve(SIZE); // SIZE is the number of elements in the arrays
// Add the elements
for (size_t i = 0; i < SIZE; ++i)
{
vec.push_back(std::make_pair(A[i], B[i]));
}
// Sort
std::sort(vec.begin(), vec.end(), Comp); // Comp is a comparator that
// sorts after the first element in the pair
// Write values back sorted into the arrays
for (size_t i = 0; i < SIZE; ++i)
{
A[i] = vec[i].first;
B[i] = vec[i].second;
}
--
Erik Wikstr??m