CODEWITHSUNDEEP
c++qsort
Ofer strichman
Ofer strichman

Reputation: 171

c++ transfer a parameter to qsort comparer

I am sorting custom objects, and as a comparer I have a function with random tie-breaking (this is important because I am calling it many times, and want a different order each time). This implies that I cannot use std::sort, because this comparer does not satisfy the requirement of strict weak ordering (because it does not maintain transitivity).

This can be done with qsort, but there I have another problem: I need to pass to the comparator function the random engine (e.g. m19937). I cannot use a global random engine, because of other reasons (it is called by multiple threads, and having a global variable makes the program non-deterministic). Transferring a parameter to the comparer function can solve my problem (I will transfer the random engine) - but I do not know how to transfer a parameter to the comparator. Is this possible ?
As far as I saw qsort cannot take a functor as a comparer.

Upvotes: 2

Views: 87

Answers (2)

eerorika
eerorika

Reputation: 238311

I am sorting custom objects, and as a comparer I have a function with random tie-breaking

Then you cannot use std::qsort. C11 draft n1570 says:

7.22.5 Searching and sorting utilities

When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, ...

I cannot use a global random engine, because of other reasons (it is called by multiple threads, and having a global variable makes the program non-deterministic).

If this was the only problem, you might solve it by using thread local random engine.

A simple alternative to achieve the same thing: Shuffle the range first, then sort.

Upvotes: 6

zkoza
zkoza

Reputation: 2860

As far as qsort is considered, I guess qsort_s will do the trick, see https://en.cppreference.com/w/c/algorithm/qsort

Upvotes: 0

Related Questions