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
– user1508519, Commented Feb 13, 2014 at 18:18
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
– Guye Incognito, Commented Feb 13, 2014 at 18:22
@remyabel: BTW, std::nth_element (or std::partial_sort) is enough. — Jarod42
– Jarod42, Commented Feb 13, 2014 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
– Chad, Commented Feb 13, 2014 at 18:25
@GuyeIncognito: You may use a std::vector<std::pair<float, int>>, and std::greater<std::pair<float, int>> as comparator functor. — Jarod42
– Jarod42, Commented Feb 13, 2014 at 18:29

Jarod42 · Accepted Answer · 2014-02-13 18:48:09Z

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])
    }
}

Steven Hansen · Accepted Answer · 2014-02-13 18:51:29Z

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.

Collectives™ on Stack Overflow

Sorting an array of structs in C++

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related