3

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

Daniel Langr
  • 22,196
  • 3
  • 50
  • 93
  • 2
    You can specialize `std::swap` for your type. – chris Mar 18 '14 at 15:09
  • Why is it missing you ask? Well, how often do you run in the situation where you have to sort two arrays simultaneously.. ;) – Saraph Mar 18 '14 at 15:16
  • 1
    @chirs: Not sure it will work, see http://stackoverflow.com/questions/14212701/stdsort-does-not-always-call-stdswap – Daniel Langr Mar 18 '14 at 15:17
  • 3
    Could you create a mapping vector or array that would map your sorted indices to the actual indices of the parallel arrays? I believe you could use `std:sort` on the mapping array with a custom comparator. – Fred Larson Mar 18 '14 at 15:23
  • @FredLarson: Cannot, it would need 2/3 of additional memory in my case (imagine the arrays represent a sparse matrix which typically occupies 80-90% of available memory in my program). – Daniel Langr Mar 18 '14 at 15:26
  • Understood. I'm contemplating some sort of proxy container/iterator that would wrap your parallel arrays with little or no overhead and allow you to use `std::sort`, but I don't have it all figured out yet. – Fred Larson Mar 18 '14 at 15:37
  • Such kind of solution has been discussed many times, especially in the context of this problem, but to no result (at least what I have seen). E.g., the boost zip_iterator is mentioned frequently, as in http://stackoverflow.com/questions/9343846/boost-zip-iterator-and-stdsort. – Daniel Langr Mar 18 '14 at 15:50
  • @DanielLangr: Maybe your initial design decision coupled with your memory limitations just won't make this feasible. What exactly are these memory limitations? – PaulMcKenzie Mar 18 '14 at 16:00
  • As I wrote above, the arrays occupy 80-90% of physical memory and there is no space for additional (proxy) arrays. However, I do not expect to find here a solution using std::sort. I asked a different question - looking for some other sorting C++ (or C) implementation. – Daniel Langr Mar 18 '14 at 16:13

1 Answers1

0

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.

minorlogic
  • 1,872
  • 1
  • 17
  • 24