"Locking" two vectors and sorting them

Question

I have this two vector<double> 's mass and velocity both of the same size N. They contain the information about the mass and velocity of N particles. mass[i] and velocity[i] are thus properties of the i'th particle

Is it possible in C++ to "lock" these two vectors together and sort them in increasing order of mass? Thus after the sorting the vector mass should be in increasing order, and the velocity vector should contain the corresponding velocities of the sorted masses

e.g. Before sorting mass = (4,2,1,3) and velocity = (13, 14,15,16 ) After sorting mass=(1,2,3,4) and velocity =(15, 14, 16, 13)

The one (non-efficient) way I know for this is to transfer the data into an vector of struct's

struct particle
{

double mass;
double velocity;


bool operator < (const particle& str) const

 {
    return (mass < str.mass);
  }



};

and create vector<particle> particlelist(N) and then sort this vector by using the std::sort by overloading the < operator as I have done in the definition above.

I do not want to put my data into Array of Structures fashion since I have heard it is inefficient compared to the Structure of Arrays approach(at least in CUDA).

define "lock" better do you mean like if one changes a property the other changes i the same manner? — John Riselvato, Nov 16 '11 at 07:07
Related: http://stackoverflow.com/questions/3398819/sort-by-proxy-or-sort-one-container-by-the-contents-of-another-in-c — John Bartholomew, Nov 16 '11 at 07:12
`sort(zip(mass.all(), velocity.all()))` if we had Alexandrescu's ranges :) — R. Martinho Fernandes, Nov 16 '11 at 07:17
Regarding efficiency -- it depends on your data access patterns. If processing a particle involves looking at both mass and velocity, then both values will have to be read from memory at once, in which case it is advantageous to load them both into the cache simultaneously (i.e., use array-of-structs). If you have two separate processing passes, one which only looks at mass and one which only looks at velocity, then struct-of-arrays is likely to be better so that each process can make most effective use of cache memory and not have half of it wasted by an irrelevant value. — John Bartholomew, Nov 16 '11 at 07:17
(of course the above is just a rule-of-thumb guideline -- there are other factors involved too; as always, to know true performance you have to measure it) — John Bartholomew, Nov 16 '11 at 07:18

score 10 · Answer 1 · answered Nov 16 '11 at 07:18

Create vector indexes; fill it by values 0..n-1 than

    struct CmpMass {
    {
       CmpMass(vector<double>& vec) : values(vec){}
       bool operator() (const int& a, const int& b) const
       {
           return values[a] < values[b];
       }
       vector<double>& values;
    }

sort(indexes.begin(), indexes.end(), CmpMass(mass));

than you have in vector indexes order of items in both arrays. Than you can create mass/velocity vectors in correct order or convert index during access: mass[indexes[i]], velocity[indexes[i]]

score 5 · Accepted Answer · edited Nov 16 '11 at 08:03

5

At least as far as I know, none of the sorting algorithms built into the standard library will do this for you directly. The most obvious possibility would probably be to use a Boost Zip Iterator to make the two arrays act like a single collection.

edited Nov 16 '11 at 08:03

Mankarse

39,818
11
97
141

answered Nov 16 '11 at 07:19

Jerry Coffin

476,176
80
629
1,111

score 5 · Answer 3 · answered Nov 16 '11 at 10:14

Why don't you use std::pair as you have two values which are linked, you than can then implement your own comparison method/function to pass on to the std::sort function via pointer(there exist an overloaded version of std::sort which supports that).

But be sure that you have a strict weak ordering implemented, because else std::sort might lead to a SEGFAULT

"Locking" two vectors and sorting them

3 Answers3

Linked