Re: Adding 'indirect_sort' to boost::algorithm

From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2023-06-15 08:58:00

On Thu, Jun 15, 2023 at 3:42 AM Marshall Clow via Boost <
boost_at_[hidden]> wrote:

> At Boostcon last month, there was a discussion of indirect sorting
> algorithms to boost::algorithm.
> An “Indirect sort” [...] returns a sequence of indices into the collection
> describing how the collection can be rearranged in order to become sorted.
> [...] Comments welcomed.
>

Hi Marshall. I've long wondered why something like that wasn't in Boost.

In our code base, we've had a "cosort" for several decades, which takes
several arrays/vectors,
sorts the first one, and applies the same "reordering" to the others.

This comes up in "data-oriented" designs where you have N arrays-of-values
instead of 1 array-of-struct-of-N-members.

So you are adding a building block to have such a "cosort".
You're just missing a way to apply that reordering to several
(random-access) collections.

My $0.02.

PS: Note that I'm not sure what the correct term / name is for that algo.
  I always remember it as "cosort" myself, but there has to be a better
name.

PPS: https://hackmd.io/@Q66MPiW4T7yNTKOCaEb-Lw/ryfenBCO5
 is a nice article on Data-Oriented Designs, which mentions the talk from
Andrey Kelly (of Zig fame) I was searching for.