Sorting an array of structs in C++

Question

I'm using a particle physics library written in c++ for a game.

In order to draw the particles I must get an array of all their positions like so..

b2Vec2* particlePositionBuffer = world->GetParticlePositionBuffer();

This returns an array of b2Vec2 objects (which represent 2 dimensional vectors in the physics engine).
Also I can get and set their colour using

  b2ParticleColor* particleColourBuffer = world->GetParticleColorBuffer();

I would like to get the 10% of the particles with the highest Y values (and then change their colour)

My idea is..
1. Make an array of structs the same size as the particlePositionBuffer array, the struct just contains an int (the particles index in the particlePositionBuffer array) and a float (the particles y position)
2.Then I sort the array by the y position.
3.Then I use the int in the struct from the top 10% of structs in my struct array to do stuff to their colour in the particleColourBuffer array.

Could someone show me how to sort and array of structs like that in c++ ?
Also do you think this is a decent way of going about this? I only need to do it once (not every frame)

What's wrong with std::sort? Write a comparator function or overload operator< in your struct. Also just a small nitpick, I presume 2d vector objects is referring to something like 2dvector and not std::vector. Can you edit your question because I initially was confused. — user1508519
yeah I saw this question with a very good answer. stackoverflow.com/questions/873715/c-sort-with-structs The only thing is he says this is for a STL container and not an array (I dunno what an STL container is) — Guye Incognito
@remyabel: BTW, std::nth_element (or std::partial_sort) is enough. — Jarod42
An STL container, is a container found within the Standard Template Library. When you say "make an array...", instead you would "make (and fill) a vector...". In fact, since you want an "array" that the size isn't known until runtime, you really want to use std::vector<> instead. — Chad
@GuyeIncognito: You may use a std::vector<std::pair<float, int>>, and std::greater<std::pair<float, int>> as comparator functor. — Jarod42

Jarod42 Jarod42 · Accepted Answer · 2014-02-13T18:48:09

Following may help:

// Functor to compare indices according to Y value.
struct comp
{
    explicit comp(b2Vec2* particlePositionBuffer) :
        particlePositionBuffer(particlePositionBuffer)
    {}
    operator (int lhs, int rhs) const
    {
        // How do you get Y coord ?
        // note that I do rhs < lhs to have higher value first.
        return particlePositionBuffer[rhs].getY() < particlePositionBuffer[lhs].getY();
    }
    b2Vec2* particlePositionBuffer;
};

void foo()
{
    const std::size_t size = world->GetParticleCount(); // How do you get Count ?
    const std::size_t subsize = size / 10; // check for not zero ?

    std::vector<std::size_t> indices(size);

    for (std::size_t i = 0; i != size; ++i) {
        indices[i] = i;
    }
    std::nth_element(indices.begin(), indices.begin() + subsize, indices.end(),
        comp(world->GetParticlePositionBuffer()));

    b2ParticleColor* particleColourBuffer = world->GetParticleColorBuffer();
    for (std::size_t i = 0; i != subsize; ++i) {
        changeColor(particleColourBuffer[i])
    }
}

Sorting an array of structs in C++

2 Answers