Remove code duplication inside of a loop preserving performance

Question

I'm coding a 2D collision engine, and I need to merge adjacent axis-aligned bounding boxes depending on a direction (left, right, top, bottom).

The four cases are very similar, except for the if condition, and the push_back argument. Is there any way I can refactor this code without compromising performance?

vector<AABB> getMergedAABBSLeft(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getRight() == b.getRight())
            {
                result.push_back(getMergedAABBVertically(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

vector<AABB> getMergedAABBSRight(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getLeft() == b.getLeft())
            {
                result.push_back(getMergedAABBVertically(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

vector<AABB> getMergedAABBSTop(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getBottom() == b.getBottom())
            {
                result.push_back(getMergedAABBHorizontally(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

vector<AABB> getMergedAABBSBottom(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getTop() == b.getTop())
            {
                result.push_back(getMergedAABBHorizontally(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

Answer 1

I find this line hard to read:

bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

Please split variables up 1 per line.
Yes the new syntax allows {} for list initialization. But these are not lists so it seems confusing to me (this one is more personal bias so feel free to ignore).

bool   merged(false);
AABB   a(mSource.back());
mSource.pop_back();

Pass large parameters by const reference if you can.
It saves a copy and you don't seem to need the copy (since you are not modifying the value (Note the eraseRemove() call has no effect externally and does not effect the rest of the code)).

vector<AABB> getMergedAABBSLeft(vector<AABB> const&   mSource)
                                     //     ^^^^^^^^

Since your four functions are identical apart from one method call you could write a generic version and pass that method as a parameter:

vector<AABB> getMergedAABBSLeft(vector<AABB> mSource)
{    return getMergedAABBSGeneric(mSource, &AABB::getRight);
}

Answer 2

Without knowing much about the AABB type, I'm assuming it has the operations getBottom(), and it's top-left-right couterparts.

What you could do is set up functions which returns the appropiate result and pass it as an argument to the general function. I only show the process for the top/left/right/bottom. The horizontally/vertically part goes the same way. Something like:

    typedef elem_type (*selector)(AABB*);
    elem_type getRightSelector(AABB* obj)
    {
        return obj->getRight(); // Return value is of elem_type
    }
    // Same for the others (left, top...)

vector<AABB> getMergedAABBS(vector<AABB> mSource, selector sel )
{
     (...)
        for(auto& b : mSource)
            if(sel(a) == sel(b))
            {
                // We'd need another pointer here
                result.push_back(getMergedAABBHorizontally(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

     (...)
    return result;
}

    // Any particular one:
    vector<AABB> getMergedAABBSRight(vector<AABB> mSource )
{
         return getMergedAABBS(mSource, getRightSelector);
}

Then you'd call the general function from each suffixed function (ie. getMergedAABBTop, etc.) passing the appropriate selector function.

Note this may be achieved in a cleaner way with C++11 features, what I'm not so certain about is the performance impact. Here you are adding one function call with respect to your code inside the loop, plus one function call from the specialized functions to the general one. Consider inlining, too.

Answer 3

This looks like a perfect opportunity for templates, maybe something like this:

template<typename C, typename T, T(C::*Selector)() const, C(*MergeFn)(C, C)> struct static_merger {

    std::vector<C> run(std::vector<C> mSource) {
        std::vector<C> result;
        while(!mSource.empty())
        {
            bool merged = false;
            AABB a = mSource.back();
            mSource.pop_back();

            for(auto & b : mSource) {
                if((a.*Selector)() == (b.*Selector)())
                {
                    result.push_back((*MergeFn)(a, b));
                    eraseRemove(mSource, b);
                    merged = true;
                    break;
                }
            }
            if(!merged) {
                result.push_back(a);
            }
        }
        return result;
    }
};

Usage is simple:

std::vector<AABB> orig / * = ... */;
static_merger<AABB, int, &AABB::getLeft, &mergeVertically> mergl;
static_merger<AABB, int, &AABB::getRight, &mergeVertically> mergr;
static_merger<AABB, int, &AABB::getTop, &mergeHorizontally> mergt;
static_merger<AABB, int, &AABB::getBottom, &mergeHorizontally> mergb;
std::vector<AABB> mergedl = mergl.run(orig);
std::vector<AABB> mergedr = mergr.run(orig);
std::vector<AABB> mergedt = mergt.run(orig);
std::vector<AABB> mergedb = mergb.run(orig);

Notice that with this approach, you need to create 4 different instances of our static_merger since the callbacks are being passed as template arguments.

If you want to be able to decide at runtime which callbacks to use, you can use this one:

template<typename C, typename T> struct dynamic_merger {

    std::vector<C> run(std::vector<C> const & mSource, T(C::*selector)() const, C(*merge_fn)(C, C)) {
        std::vector<C> result;
        while(!mSource.empty())
        {
            bool merged = false;
            AABB a = mSource.back();
            mSource.pop_back();

            for(auto & b : mSource) {
                if((a.*selector)() == (b.*selector)())
                {
                    result.push_back((*merge_fn)(a, b));
                    eraseRemove(mSource, b);
                    merged = true;
                    break;
                }
            }
            if(!merged) {
                result.push_back(a);
            }
        }
        return result;
    }
};

Usage is also simple:

std::vector<AABB> orig / * = ... */;
dynamic_merger<AABB, int> merg;
std::vector<AABB> mergedl = merg.run(orig, &AABB::getLeft, &mergeVertically);
std::vector<AABB> mergedr = merg.run(orig, &AABB::getRight, &mergeVertically);
std::vector<AABB> mergedt = merg.run(orig, &AABB::getTop, &mergeHorizontally);
std::vector<AABB> mergedb = merg.run(orig, &AABB::getBottom, &mergeHorizontally);

One last thing, as Loki Astari suggested you should pass your original data by (const) reference instead of by value, this avoids expensive copying, resulting in (possibly) faster execution times.