Array alive/dead entity "refresh" algorithm

I have an Entity class that can be either dead or alive.

I store entities contiguously in a resizable array. During an update(), some alive entities can become dead, and some new entities can be added at the end of the array.

The range [0 .. size) contains all non-newly-created entities.

The range [size .. sizeNext) contains all newly-created entities (guaranteed to be alive).

After update(), I call refresh(). This function does:

-
Swap around entities making sure that all alive entities are stored contiguously at the beginning of the array (and that all dead entities are stored contiguously at the end of the array).

-
Deinitialize all dead entities.

-
Update size and sizeNext.

Basically, the algorithm uses two iterators:

-
iD moves from left to right, looking for dead entities.

-
iA moves from right to left, looking for alive entities.

When iD and iA find an entity, the entities are swapped and the iterators advance.

Here's a quick drawing of the algorithm:

And here's the current code:

void refresh()
{
    // `sizeNext` is unsigned - copy it as a signed value
    // to store its initial value and compare it to integers.
    const int intSizeNext(sizeNext);

    // `iD` walks from left to right, looking for dead entities.
    // `iA` walks from right to left, looking for alive entities.
    int iD{0}, iA{intSizeNext - 1};

    do
    {
        // Find dead item from left
        for(; true; ++iD)
        {
            // No more dead items
            if(iD > iA) goto finishRefresh;

            if(isDeadAt(iD)) break;
        }

        // Find alive item from right
        for(; true; --iA)
        {
            // No more alive items
            if(iA = 0; --iA) 
    {
        assert(isAliveAt(iA));
    }

    msize = sizeNext = iD;

    for(; iD < intSizeNext; ++iD)
    {
        assert(isDeadAt(iD));
        deinitAt(iD);
    }
}

• Can the code be improved/optimized?

• Can the goto instructions be avoided?

You could probably use std::remove_if instead of your algorithm. Take this example code:

std::vector vec = { "0", "1", "5", "0", "3", "6", "0", "1" };
std::remove_if(std::begin(vec), std::end(vec), [](const std::string& val)
{
    return val == "0";
});

for (auto&& a: vec)
{
    std::cout << a << ' ';
}

I get the following output:

1 5 3 6 1 0 0 0

std::remove_if swaps the elements of a range so that the elements that are to be kept are at the beginning of the range and maintains their order. The elements that are still at the end have unspecified values, but if Entity is an RAII class, the deinitialization will happen at destruction. Since I don't know what Entity looks like, I can't be sure that this method will work, but there is probaby a way to ensure that it will do what you need it to do.

This method has two advantages: it allows to think in term of iterators instead of sizes and it uses an already existing algorithm. In your case, refresh could probably look like this:

void refresh()
{
    std::remove_if(std::begin(entities), std::end(entities),
                   [](const Entity& ent)
                   {
                       return ent.isDead();
                   });
}

Once again, I am assuming some implementation details that are not shown though. Anyway, try check whether std::remove_if coud be used to do what you want it to do. Standard algorithms can often do much more things than thought.

StackExchange Code Review Q#67524, answer score: 10