Dividing a range into N sub-ranges

Question

Introduction

The function divides a range given by a begin_iterator and an end_iterator into n sub-ranges of the same format, where the sub-ranges must be as equally sized as possible.

Example

Consider a set of size 10:

\$\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}\$

The output would be is a set of n = 3 sub-ranges:

\$\{ \{ 0, 3 \}, \{ 4, 6 \}, \{ 7, 9 \} \}\$

Where each sub-set is as even as possible, in the previous example the sets have sizes 4, 3, and 3, respectively; that is the most even way to distribute 10 elements into 3 sub-sets.

Review goals

• Efficiency
• Correctness

Implementation

The oringinal code contained an issue which I missed by pure luck. Here is the fixed working code; the changes do not invalidate the present answer.

#include <vector>   // std::vector<T>
#include <iterator> // std::distance(), std::next()

template <typename Iterator>
decltype( auto ) divide_work( Iterator begin, Iterator end, std::size_t n )
{
    using size_type = std::size_t;

    auto sz = std::distance( begin, end );
    auto element_per_group_count = sz / n;
    auto remaining_element_count = sz % n;

    std::vector<std::pair<Iterator, Iterator>> ranges;
    ranges.reserve( n );

    if ( remaining_element_count == 0 )
    {
        --element_per_group_count;

        ranges.emplace_back( std::make_pair( std::next( begin, 0 ),
            std::next( begin, element_per_group_count ) ) );

        for ( auto i = 1U; i < n; ++i )
        {
            auto first = std::next( ranges[ i - 1 ].second, 1 );
            ranges.emplace_back( std::make_pair( first,
                std::next( first, element_per_group_count ) ) );
        }
    }
    else
    {
        ranges.emplace_back( std::make_pair( std::next( begin, 0 ),
            std::next( begin, element_per_group_count ) ) );

        for ( auto i = 1U; i < remaining_element_count; ++i )
        {
            auto first = std::next( ranges[ i - 1 ].second, 1 );
            ranges.emplace_back( std::make_pair( first,
                std::next( first, element_per_group_count ) ) );
        }

        --element_per_group_count;

        for ( auto i = ranges.size(); i < n; ++i )
        {
            auto first = std::next( ranges[ i - 1 ].second, 1 );
            ranges.emplace_back( std::make_pair( first,
                std::next( first, element_per_group_count ) ) );
        }
    }
    return ranges;
}

Output

Answer 1

Misleading Return Type

You have:

template <typename Iterator>
decltype( auto ) divide_work( Iterator begin, Iterator end, std::size_t n )

The difference between auto and decltype(auto) is that the latter can deduce reference types as well. But you're returning a value, always, regardless of Iterator. This choice makes it seem as if you could be returning a reference. If you are going to use a placeholder return type here, use simply auto.

Even better, the return type for this function is not a complicated expression that's difficult to spell. It's simply std::vector<std::pair<Iterator, Iterator>>, so let's just use that:

template <typename Iterator>
std::vector<std::pair<Iterator, Iterator>>
divide_work( Iterator begin, Iterator end, std::size_t n )

emplace_back

The advantage of emplace_back is not having to actually construct the object to pass in. So when you write:

ranges.emplace_back( std::make_pair( std::next( begin, 0 ),
            std::next( begin, element_per_group_count ) ) );

That's inefficient (you're copy constructing a pair instead of in-place constructing it) and just a bunch of extra typing. Also next(iter, 0) is iter, so the above line is logically exactly equivalent to:

ranges.emplace_back(begin, std::next(begin, element_per_group_count));

Overly Complicated Algorithm!

I'm not sure why you have three for loops or why even division is a special case of the algorithm... Also I'm pretty sure that special case is wrong. Consider a range of size 15 dividing into 3 chunks, so it divides evenly. We'd start with element_per_group_count == 5, but then we decrement it to 4, and add the first range of:

[0, 4)

Then the next two ranges will be:

[5, 9)
[10, 14)

We successfully divided into three chunks, but we're actually missing elements! 4, 9, and 14 will not appear in any of the three chunks. The correct division would be [[0, 5), [5, 10), [10, 15)].

---

We're just chunking the range (begin, end) into n pieces. That implies a simple for-loop. We need n things. Each one is approximately of size distance(begin, end)/n. There will be distance(begin, end)%n remainder, which we will allocate one at a time as we go until we run out of remainder. When we already added n-1 things, we just can add the rest as the last chunk (since there's nothing else to do at that point).

This is all you need:

template <typename Iterator>
std::vector<std::pair<Iterator, Iterator>>
divide_work( Iterator begin, Iterator end, std::size_t n )
{
    std::vector<std::pair<Iterator, Iterator>> ranges;
    ranges.reserve(n);

    auto dist = std::distance(begin, end);
    auto chunk = dist / n;
    auto remainder = dist % n;

    for (size_t i = 0; i < n-1; ++i) {
        auto next_end = std::next(begin, chunk + (remainder ? 1 : 0));
        ranges.emplace_back(begin, next_end);

        begin = next_end;
        if (remainder) remainder -= 1;
    }

    // last chunk
    ranges.emplace_back(begin, end);
    return ranges;
}

Dividing up the remainder one at a time means that if we have 15 elements into 6 chunks, we end up with sizes of [3, 3, 3, 2, 2, 2] instead of any other weird alternative like the naive [2, 2, 2, 2, 2, 5].

Too many chunks? None?

What do you do in the case where n > distance(begin, end) or n == 0? I guess we should probably add some error checks:

template <typename Iterator>
std::vector<std::pair<Iterator, Iterator>>
divide_work( Iterator begin, Iterator end, std::size_t n )
{
    std::vector<std::pair<Iterator, Iterator>> ranges;
    if (n == 0) return ranges;
    ranges.reserve(n);

    auto dist = std::distance(begin, end);
    n = std::min<size_t>(n, dist);
    auto chunk = dist / n;
    auto remainder = dist % n;

    for (size_t i = 0; i < n-1; ++i) {
        auto next_end = std::next(begin, chunk + (remainder ? 1 : 0));
        ranges.emplace_back(begin, next_end);

        begin = next_end;
        if (remainder) remainder -= 1;
    }

    // last chunk
    ranges.emplace_back(begin, end);
    return ranges;
}

Answer 2

#include <vector>   // std::vector<T>
#include <iterator> // std::distance(), std::next()

Not a big fan of those comments, they tend to go stale pretty fast, e.g. here you're also "importing" std::cbegin and std::cend in main from that indirect include. If you want to (or have to) explicitly list all you're importing, you're missing those two. And it would be better if you included <iterator> in main rather than relying on that indirect include.

template <typename Iterator>
decltype( auto ) divide_work( Iterator begin, Iterator end, std::size_t n ) ...

Why decltype(auto)? You know exactly the nature (value category/"referenceness") of what you're returning and you better not return any sort of reference since you're returning a local variable. auto is enough.

using size_type = std::size_t;

You're not using that alias, you can drop it.

You might want to pull the two loops into a separate function template. The div_sz loop variable is a bit odd since it is always equal to n. Drop it too.

---

I changed your main to take n as a command line parameter and ran it. Works for your test case, but:

$ ./a.out 0
Floating point exception
$ ./a.out 1
Segmentation fault
$ ./a.out 15
Segmentation fault

Going for n greater than the size of the list gives strange results too.

Answer 3

Barry's points on correctness are good ones. It's also possible to implement the algorithm using STL algorithms rather than a loop. Whether that's an improvement in this case is a matter of taste but here's one way to do it. This could be made even simpler and more general with Eric Niebler's range-v3 library which is being proposed for standardization in C++17.

template<typename It>
auto divide_work(It first, const It last, const std::size_t n) {
    std::vector<std::pair<It, It>> ranges;
    ranges.reserve(n);
    std::generate_n(back_inserter(ranges), n, [&, size = std::distance(first, last)]{
        const auto curr = first;
        std::advance(first, size / n + (ranges.size() < size % n));
        return std::make_pair(curr, first);
    });
    return ranges;
}

Answer 4

At least in theory, rather than returning a vector of ranges, I'd rather this functioned like other algorithms, so the signature would be something like this:

template <class InIt, class OutIt>
void divide_work(InIt b, InIt e, OutIt d, std::size_t n)

Then you'd probably want to do a static_assert (or similar) to assure that the output iterator's value_type is a pair of the input iterators.

For better or worse, however, this can complicate client code considerably. Instead of a simple: auto divs = divide_work(...); the client is stuck with figuring out a fairly complex type like std::pair<std::container<T>::iterator, std::container<T>::iterator>, and defining a container (or other recipient) of that kind of objects. As much as I like it philosophically, it's probably not very practical.

Nonetheless, depending on how the result is used, it might be worth reconsidering this decision--especially if it's not a situation where you can depend on using auto for all (or at least most) code that has to deal with that result container.

As far as computing the sizes goes, rather than a single loop that computes the correct sizes each iteration, (e.g., std::next(begin, chunk + (remainder ? 1 : 0));) I'd rather just use two loops:

auto gen = [&](size_t s) {
    auto it = std::next(begin, s);
    *dest = { begin, it };
    ++dest;
    begin = it;
};

size_t i;
for (i = 0; i < remainder; i++)
    gen(size + 1);

for (; i < n; i++)
    gen(size);

I, for one, find the intent considerably easier to understand this way.