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. — , Feb 13 '14 at 18:18
yeah I saw this question with a very good answer. http://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, Feb 13 '14 at 18:22
@remyabel: BTW, `std::nth_element` (or `std::partial_sort`) is enough. — Jarod42, Feb 13 '14 at 18:23
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, Feb 13 '14 at 18:25
@GuyeIncognito: You may use a `std::vector>`, and `std::greater>` as comparator functor. — Jarod42, Feb 13 '14 at 18:29
@Jarod42 Could you post the code of how to do that as an answer and I will accept it? Sorry but I'm a bit lost in C++ I normally use C# and this library is my 1st exposure to C++ — Guye Incognito, Feb 13 '14 at 18:33

Steven Hansen · Answer 1 · 2014-02-13T18:51:29.913

If your particle count is low, it won't matter much either way, and sorting them all first with a simple stl sort routine would be fine.

If the number were large though, I'd create a binary search tree whose maximum size was 10% of the number of your particles. Then I'd maintain the minY actually stored in the tree for quick rejection purposes. Then this algorithm should do it:

Walk through your original array and add items to the tree until it is full (10%)
Update your minY
For remaining items in original array
- If item.y is less than minY, go to next item (quick rejection)
- Otherwise
  - Remove the currently smallest Y value from the tree
  - Add the larger Y item to the tree
  - Update MinY

A binary search tree has a nice advantage of quick insert, quick search, and maintained ordering. If you want to be FAST, this is better than a complete sort on the entire array.

score 1 · Accepted Answer · answered Feb 13 '14 at 18:48

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 Answers2