C++ Sorting Objects in a vector based on member boolean

Question

In my program, I have classes I use for handling projectiles in a game.

class Projectile
{
bool IsActive;
bool GetActive();
//....
};

class Game
{
std::vector<Projectile*> ProjectilesToUpdate;
//....
};

Of course, there is more to it than that, however I'm trying to stay relevant to my current problem.

I want to use std::sort to make it so that all projectiles where IsActive == true are at the far beginning and that any projectile which isn't active is at the very end.

How would I go about doing this?

The reason why std::partition is being suggested instead of std::sort is that it is more efficient. std::sort could be used but it's O(n*log(n)) compared to O(n) for partition. — Simon, Mar 16 '15 at 10:02

score 9 · Accepted Answer · edited May 23 '17 at 12:16

Basically, you want to create a partition:

std::partition(std::begin(ProjectilesToUpdate),
               std::end(ProjectilesToUpdate), 
               [](Projectile const* p) { return p->GetActive(); }
);

As for the subsidiary questions:

I had to remove the "const" part in the code to make it compile.

That's because your GetActive() method should be const:

bool GetActive() const { return IsActive; }

See Meaning of "const" last in a C++ method declaration?

how can I use this to delete every single object (and pointer to object) that is no longer needed?

You could use smart pointers (such as std::shared_ptr) and no longer care about delete. Thus you could use the Erase–remove idiom as follow:

std::vector<std::shared_ptr<Projectile>> ProjectilesToUpdate;
// :
// :
auto it = std::remove_if(
    std::begin(ProjectilesToUpdate), 
    std::end(ProjectilesToUpdate),
    [](std::shared_ptr<Projectile> const& p) { return !p->GetActive(); } // mind the negation
);
ProjectilesToUpdate.erase(it, std::end(ProjectilesToUpdate));

Related question: What is a smart pointer and when should I use one?

If you don't want to use smart pointers, you could use the returned iterator which point to the first element of the second group (i.e. the non active ones) and iterate until the end of the array:

auto begin = std::begin(ProjectilesToUpdate);
auto end = std::end(ProjectilesToUpdate);
auto start = std::partition(begin, end, 
    [](Projectile const* p) { return p->GetActive(); }
);
for (auto it = start; it != end; ++it) {
    delete *it;
}
ProjectilesToUpdate.erase(start, end);

Note that I'm not calling erase inside the loop since it invalidates iterators.

And of course, this last solution is more complex than using smart pointers.

Thanks so much. I know this might be asking quite a lot, but I have had some unexpected troubles using this to help me. Firstly, I had to remove the "const" part in the code to make it compile. Also, how can I use this to delete every single object (and pointer to object) that is no longer needed? — Cupcake1029, Mar 16 '15 at 12:39
Absolutely; the memory usage stayed at a constant rate compared to before thanks to you. I learnt a lot in the process, so thanks very much :) — Cupcake1029, Mar 19 '15 at 06:21
@Cupcake1029 In that case, would you mind accepting the answer (there's a tick on the left of the answer if I remember correctly)? Thanks. — Hiura, Mar 19 '15 at 08:04

C++ Sorting Objects in a vector based on member boolean

1 Answers1