Re: Adding 'indirect_sort' to boost::algorithm

From: David Bien (davidbien_at_[hidden])
Date: 2023-06-15 18:15:15

Wrt (1) I guess you’d have to use something other than iota() since it takes a cue from the initialized size of the array – necessitating initial throwaway initialization of the elements.

bien

Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows

From: David Bien via Boost<mailto:boost_at_[hidden]>
Sent: Thursday, June 15, 2023 12:00 PM
To: boost_at_[hidden]<mailto:boost_at_[hidden]>
Cc: David Bien<mailto:davidbien_at_[hidden]>
Subject: Re: [boost] Adding 'indirect_sort' to boost::algorithm

A couple of things.

  1.  It seems you are initializing the indices of the Permutation <ret> return twice – first to 0 and then to the position in iota(). An optimization would be to first declare an empty Permutation and then reserve() the count of elements you want and then call iota().
  2.  In my former codebase I had a similar indirect_sort() that accepted an input array of indices instead of generating them inside the method. This allows a “select and then indirect_sort this set of indices” which is what I generally used.
  3.  (this less important but just an aside) I also implemented two other types of indirect sort in my old code base due to necessity. A “pointer to element” sort – this allows sorting on post-iterator-access elements – allowing sorting of elements stored in non-indexable iterators. Also an “offset sort” which is more or less like the pointer-to-element sort but allowed sorting of sub-fields of elements (though thinking about it now I don’t remember how I did this and I no longer have access to the code). I used the “pointer to element” sort the most of the time – the size of an 64bit index and a pointer are usually the same so no loss in terms of storage – the return is a set of sorted pointer-to-elements.
bien

Sent from Mail<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgo.microsoft.com%2Ffwlink%2F%3FLinkId%3D550986&data=05%7C01%7C%7Cb05ca86255704e0564e508db6dca57fe%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638224488055949615%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=O4stdx5U6GfpW0jfVok2GFmQI7FLQXM2NS6%2B%2B%2FLJ9tc%3D&reserved=0<https://go.microsoft.com/fwlink/?LinkId=550986>> for Windows

From: Alexander Grund via Boost<mailto:boost_at_[hidden]>
Sent: Thursday, June 15, 2023 3:04 AM
To: boost_at_[hidden]<mailto:boost_at_[hidden]>
Cc: Alexander Grund<mailto:alexander.grund_at_[hidden]>
Subject: Re: [boost] Adding 'indirect_sort' to boost::algorithm

> 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.

There already is: Basically you first do an indirect sort and then use
`boost::algorithm::apply_permutation` on each collection with the result
permutation.
See the test case and documentation of indirect_sort.

Alex

_______________________________________________
Unsubscribe & other changes: https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.boost.org%2Fmailman%2Flistinfo.cgi%2Fboost&data=05%7C01%7C%7Cb05ca86255704e0564e508db6dca57fe%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638224488055949615%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=8xi35vQdmkaAeZZswWGxKX0Uyxa19s8IPf3%2Bg7nnNhc%3D&reserved=0<http://lists.boost.org/mailman/listinfo.cgi/boost>