Splitting range into sub-ranges

Question

I have a container std::vector and I would like to efficiently split it into sub-ranges with x items in each. The original container is not needed so the items should be moved and not copied into the sub-ranges.

I've managed to do the splitting using copying, however I'm unsure how to do it with move assignments?

    range.insert(range.end(), new_items.begin(), new_items.end());
    while(range.size() >= x)
    {
        sub_ranges.push_back(std::vector<int>(range.begin(), range.begin() + x));
        range = std::vector<int>(range.begin() + x, range.end());
    }

EDIT:

Some progress... still not quite there, and a bit ugly

    while(range.size() >= x)
    {
        std::vector<short> sub_range(x); // Unnecessary allocation?
        std::move(range.begin(), range.begin() + x, sub_range.begin());
        sub_ranges_.push_back(std::move(sub_range));

        std::move(range.begin() + x, range.end(), range.begin());
        range.resize(range.size() - x);
    }

score 3 · Answer 1 · answered Nov 10 '10 at 08:09

One question: have you ever heard of the View concept.

The idea is that instead of actually moving the data, you just create a "view" (Proxy pattern) that will restrict / change your perception of it.

For example, for a range, a very simple implementation would be:

template <typename Iterator>
struct Range
{
  Iterator mBegin, mEnd;
};

Boost.Range offers a fat version, with a lot of things.

The advantages are numerous in this case. among which:

A single vector, thus better memory locality
The split is easy, and doesn't involve any move / copy of the data

Here is the split with this method:

typedef Range<std::vector<int>::iterator> range_type;

std::vector<range_type> split(std::vector<int> const& range, size_t x)
{
  std::vector<range_type> subRanges;
  for (std::vector<int>::iterator it = range.begin(), end = range.end();
       it != end; it += std::min(x, (size_t)std::distance(it,end)))
  {
    subRanges.push_back(range_type(it,end));
  }
  return subRanges;
}

Of course, this only works if you can keep the range object around.

Regarding your original algorithm: the use of a while loop is spurious here, and forces you to use much more moves than necessary. The for loop I crafted should be much better in this regard.

Is `subRanges.push_back(range_type(it,end));` correct? There does not seem to be a ctor for `range_type` that takes two iterators. — bgoodr, Mar 01 '22 at 21:31

score 1 · Accepted Answer · answered Nov 09 '10 at 23:19

You can use std::make_move_iterator in <iterator> to wrap your iterator into a move_iterator. This iterator will std::move the result of dereferencing its base iterator, allowing that to be moved elsewhere.

// assuming I understand your code, which I don't
range.insert(range.end(), new_items.begin(), new_items.end());
while(range.size() >= x)
{
    auto first = std::make_move_iterator(range.begin());
    auto last = std::make_move_iterator(range.begin() + x);

    sub_ranges.push_back(std::vector<int>(first, last));
    range = std::vector<int>(range.begin() + x, range.end());
}

EDIT: And like you found, there's a mapping between std::move() and make_move_iterator:

std::move(first, last, out); // is the same as
std::copy(std::make_move_iterator(first), std::make_move_iterator(last), out);

So which you find cleaner is up to you. (The first one, to me.)

Splitting range into sub-ranges

2 Answers2

Linked