4

I currently have an array of pair<double, int> which I sort using a simple custom comparator function e.g.

// compare by first
int sort_index_lcomparator(const pair<double, int>& a, const pair<double, int>& b) {
    return a.first < b.first;
}
// then sort simply like
pair<double, int> arr[size];
std::sort(arr, arr + size, sort_index_lcomparator);

I'm actually interested in the index order and not in the sorted doubles. My problem is that I would like to change away from this structure and have instead a struct of two arrays rather than an array of a struct i.e. I would like to optimize for locality and auto-vectorization but in this case I need an overloaded swap which is attached to a type specifically. I guess I would need something along the lines of redefining swap for the double type and keep both arrays in sync in such custom swap. Is there a way to "override" swap in such a manner within a limited scope?

SkyWalker
  • 13,729
  • 18
  • 91
  • 187

2 Answers2

4

I have one proposal for you: make the index array the one you sort and keep the values as global array. From then on: sort based on comparator that accepts indices, but actually compares based on the values.

Boris Strandjev
  • 46,145
  • 15
  • 108
  • 135
  • but hold a sec ... the swap will swap the indices and neglect the doubles, so the two will decorrelate no? :( – SkyWalker Aug 19 '12 at 20:48
  • You don't need to swap them right away. First sort the indices as if you were swapping both the doubles and the indices and after that you can reconstruct the sorted double array. After all the ith double will always be paired with index `i`. Why do you need to move them together all along? – Boris Strandjev Aug 19 '12 at 20:59
  • I need to move them together all along because as soon as the first swap call occurs (swap is called internally by std not me) the consistency of the sorting is broken, i.e. you get incorrect sort results. – SkyWalker Aug 19 '12 at 21:01
  • It is not like that. imagine that you have index array `idx` and doubles `d`. Then you swap `idx[i]` and `idx[j]` iff `d[idx[i]] < d[idx[j]]`. This means that in the end there will be no `d[idx[i]]` > `d[idx[j]]` for `i < j`. So the indexes will be sorted according to the values of `d`. – Boris Strandjev Aug 19 '12 at 21:11
  • ahhh OK got it ... I see it now, using the comparator like this `d[idx[i]] < d[idx[j]]`, makes sense, thank you again! – SkyWalker Aug 19 '12 at 21:28
-4

You should specialize std::sort using your custom "comparator".

template <class RandomAccessIterator, class Compare>
void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

By default sort uses a standard comparator which just compares the elements referenced by the given iterators.

Using the custom Compare you may override this. Note that it's not a function (in C++ generally you may not pass a function as a template parameter). It's a class. You pass an object of this class to sort, whereas this object should implement the following operator:

bool operator () (const Type1 &a, const Type2 &b);

So, you may invoke sort for array of your double's. Your comparator should have pointers to the beginning of both your arrays: double and int.

In case with arrays the iterator resolves into a pointer to an array element. Using the array starting address you may convert it into an index, and use it to access the second array.

valdo
  • 12,632
  • 2
  • 37
  • 67
  • but the key here is not the custom comparator, even if I have both pointers available like Boris suggests. The problem is `swap`. It doesn't matter I have access to both pointers if as soon as a `swap` is invoked by std::sort, the two arrays will decorrelate. – SkyWalker Aug 19 '12 at 20:57
  • Also, you may use a functions as template parameters as long as they can be resolved at compile time. – Michael Nett Apr 11 '13 at 05:40