CODEWITHSUNDEEP
c++sortingswap
Daniel Langr
Daniel Langr

Reputation: 23527

C++ sort implementation with custom swap?

There has been numerous questions asked about how to sort multiple arrays in C++ at once. Answers are always the same, i.e., to use the vector of structs instead of multiple arrays. Unfortunately, I cannot do this for several reasons (I/O, partial MPI transfers, utilization of vectorization units, etc.). Also, I cannot translate the array of structs into independent arrays after sorting due to memory limitations. My question is, if there exists any C++ implementation of some efficient (n log n) sorting algorithm that can work with custom swap (and custom compare) operation?

(I still cannot understand why such an option is missing in the STL. Evidently, a lot of C++ programmers are asking for it.)

Upvotes: 5

Views: 2557

Answers (2)

CygnusX1
CygnusX1

Reputation: 21818

An old question; I was looking for a solution too and I found one on the Internet.

This blog post:

https://artificial-mind.net/blog/2020/11/28/std-sort-multiple-ranges

provides a complete implementation of how it can be done.

In short. The idea is to create a multi-iterator that holds an index and refers to all the arrays you have (could be more than 2). You need to provide a way to read from and assign values to memory referred by the multi-iterator.

The reference type of the iterator will be not a regular reference though, but a proxy value holding references to cells at the same given index from all your arrays. For this type you need to define:

  • a way to swap contents (your custom swap you asked in the question)
  • a way to compare contents

With all the above done, you can then use the std::sort directly on your arrays, without copying them or using any auxiliary arrays. And I see no reason why it shouldn't work with parallel versions of the algorithms too.

Upvotes: 1

minorlogic
minorlogic

Reputation: 1918

You can sort not exactly data, but only indexes to other arrays and custom comparator. After sort, you will have array of sorted indexes and for O(n) you can permute all arrays.

Upvotes: 0

Related Questions