Sorting a structure of arrays

Question

I have some data laid out as follows:

size_t num_elements = //...
some_type_t *data = //...
int *scores = //...

Each element data[i] has a corresponding score in scores[i]. I would like to sort both data and scores, using the array of scores to order the data.

For example, for the data:

data = {'d', 'g', 'i', 'a', 'p'}
scores = {3, 5, 1, 2, 4}

the sorted version would be

data = {'i', 'a', 'd', 'p', 'g'}
scores = {1, 2, 3, 4, 5}

Is there a way to do this with the C++ standard library? I would prefer not to need to include Boost or libraries that have not yet been standardised.

I would also like to avoid unnecessarily copying the the data. This includes converting it to an array of structures.

`std::sort` appears to work for an array of structures, but I don't see how it would work for this particular case. Could you elaborate? — konsolas, Jan 29 '19 at 16:50
[Here's a very good C++ reference](https://en.cppreference.com/w/cpp). I suggest you bookmark it and go there whenever you want to find some feature or function in the standard library. If you, for example, read about [`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) you can see that you can either provide your own `operator<` for comparison, or provide a function-like argument that is used for comparison. — Some programmer dude, Jan 29 '19 at 16:51
I am aware of `std::sort`, thank you. `std::sort` requires an iterator over some container, and a function to compare elements of that container. I can provide an iterator over `data`, but I cannot provide a function to compare elements in `data` because *the scores are in a separate array*. — konsolas, Jan 29 '19 at 16:55
@Someprogrammerdude providing your own operator< is not sufficient in this case, neither functor — Slava, Jan 29 '19 at 16:55
@eerorika no it is not, OP needs sort to move elements in 2 containers simultaneously, comparator cannot help with that. Please read the question more carefully. — Slava, Jan 29 '19 at 16:58
@Slava There is no requirement to move them simultaneously. It's trivial to do the sort separately for each array as long as you don't mind making a copy. But as I said, this is not optimal. Besides, moving elements in 2 containers simultaneously is possible with `std::sort` by using a custom iterator. — eerorika, Jan 29 '19 at 17:03
My question isn't about sorting two arrays separately. It is about sorting two arrays simultaneously in relation to another. Could you elaborate on the use of custom iterators? — konsolas, Jan 29 '19 at 17:18
There are like dozens of versions of this question asked, if the linked duplicate doesn't suit you. — Phil M, Jan 29 '19 at 17:22
@konsolas why is the simultaneity important? The result will be the same regardless. RE iterators: You can define a class that meets the requirements of the iterator concept. Such iterator can be used as argument to `std::sort`. You can make the class behave such that swapping two values swaps elements in multiple containers. — eerorika, Jan 29 '19 at 17:23
How can the first array be sorted in relation to the second if they are not sorted simultaneously? If I just sorted `data` by itself, I would get `{a, d, g, i , p}` instead of the required `{i, a, d, p, g}` — konsolas, Jan 29 '19 at 17:27
@konsolas you can use the comparison functor to use ordering based on the order of the other array. — eerorika, Jan 29 '19 at 17:28
After the sort makes a single swap, the ordering of the other array no longer corresponds to the order of the original array - the score associated with each data item would change, because the index in `data` would be different from the index in `scores`. — konsolas, Jan 29 '19 at 17:29
@konsolas thus the need to make a copy in this approach. Custom iterator approach doesn't need to do a copy. — eerorika, Jan 29 '19 at 17:31
I assume there's a reason you can't redesign the code to just use an array of structs to begin with? That would eliminate the requirement for copying and allow you to do one, single sort using STL. — Phil M, Jan 29 '19 at 17:35
@eerorika "It's trivial to do the sort separately for each array as long as you don't mind making a copy." trivial or not - special comparator function only is not sufficient to do this task. — Slava, Jan 29 '19 at 18:00

score 1 · Answer 1 · answered Jan 29 '19 at 17:08

1

Assuming there isn't a reason to NOT combine the two data arrays, the simplest answer would be to merge them into a struct or a class (likely the former) with an overloaded operator. Then you can define an array of these structures/classes that will bind the data together so the data and score are moved together.

struct ScoredData
{
   some_type_t data;
   int score;

  bool operator<(const ScoredData& right)
  {
      return this->score < right.score;
  }
}

(This example could be extended by making some_type_t a template parameter)

If combining these in this way is not acceptable, you may find success defining an iterator that mimicks this behavior.

answered Jan 29 '19 at 17:08

PipSqueak

54
1
3

2

The iterator that mimics the behavior is indeed the ticket! But it's a tricky bit of code. – Jan 29 '19 at 17:19
This would work, but it unnecessarily copies all the data and I would like to avoid that. Could you elaborate on the iterator suggestion? – konsolas Jan 29 '19 at 17:20
It would involve writing two classes: one to represent the iterator, one to represent the value it returns on the dereference. The value class needs to be [Swappable](https://en.cppreference.com/w/cpp/named_req/Swappable). – Jan 29 '19 at 17:29
I got this far, but I have an error somewhere because it keeps timing out: http://coliru.stacked-crooked.com/a/6d5be2fbd6f37f24 – Mooing Duck Jan 29 '19 at 17:51
I do not see `less<>` for the actual value class - you seem to define comparisons only for the iterator itself. – Jan 29 '19 at 18:06

bruno · Answer 2 · 2019-01-29T17:31:20.470

0

can you group the elements in a new array of these couples, then sort it using sort and comparing at the right couple element, then update the initial arrays from the sorted array of couple ?

better :

you create a vector of couples made by the score values and the index 0 for the first couple, then 1 for the second, 2 for the third etc So you do not copy the datas

you qsort that array of couples considering the score part, after you just have to look at the new order of the indexes in the couples to sort scores and data easily updating them

edited Jan 29 '19 at 17:31

answered Jan 29 '19 at 17:05

bruno

32,421
7
25
37

1

Yes, but it would be incredibly inefficient: all the data would need to be copied twice. – konsolas Jan 29 '19 at 17:07
1

@konsolas you know the sort will do some copies too – bruno Jan 29 '19 at 17:09
1

But only those necessary to sort the array, and it doesn't have to temporarily double the memory space used to store the data. – konsolas Jan 29 '19 at 17:12
All as a limit, if you want to avoid that define your own qsort :) – bruno Jan 29 '19 at 17:13
The question asks if there is a way to do this with the standard library. The standard library is perfectly capable of sorting an array of structures without unnecessary copying. – konsolas Jan 29 '19 at 17:16
@konsolas I edited my answer with a new proposal ;) – bruno Jan 29 '19 at 17:30

score 0 · Answer 3 · answered Jan 29 '19 at 17:24

One other way to do this is to create an array of indexes (initialize it with 0,1,2,3...) and sort it using the score[a] < score[b] comparison.

Then you need to rearrange the scores and the data arrays according to the indexes. For example, if indexes[0] = 3 after sorting, you need to move elements score[0] = score[3]; data[0] = data[3].

I do not see a way to avoid copying when you rearrange, unfortunately.

Sorting a structure of arrays

3 Answers3