Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Divide container into chunks, C++

Tags:

c++

c++11

Given a vector of N elements v = ( 1, 2, 3, 4, ... , N ) return range iterator over all chunks of size K<N. The last range can be smaller than K if N%K!=0.

For example:

v = ("a","b","c","d","e")

display strings

"ab", "cd", "e"

N=v.size();
K=2;

One possible solution is:

for( unsigned int i=0; i<v.size(); i+=K )
    cout << boost::join( v | boost::adaptors::sliced( i, min(i+K, v.size()) ), "" );

This solution is quite ok but it has several problems:

  1. for loop - is it needed?
  2. if you write i+K instead of min(i+K, v.size()) algorithm crushes, one needs to pay additional attention to boundary case. This looks ugly and distracts.

Can you propose more elegant solution? By elegant solution I mean the use of a general algorithm, build in or provided by commonly used library (such as boost).

-------------------------- [edit] --------------------------

Some of you wonted working example, here it is.

#include <iostream>
#include <vector>
#include <string>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/assign.hpp> //just for fun

using namespace std;
using namespace boost::assign;

int main(int , char **)
{
    const int K = 2;
    vector< string > v;
    v += "a","b","c","d","e";

    for( unsigned int i=0; i<v.size(); i+=K )
        cout << boost::algorithm::join( 
                    v | boost::adaptors::sliced( i, min(i+K, v.size()) ), "" ) 
             << endl;
}

Output:

ab 
cd
e
like image 922
bartek Avatar asked Mar 30 '12 12:03

bartek


2 Answers

I don't know if it's very elegant, but you can use iterators with standard functions advance and distance :

template<typename Iterator, typename Func, typename Distance>
void chunks(Iterator begin, Iterator end, Distance k ,Func f){
    Iterator chunk_begin;
    Iterator chunk_end;
    chunk_end = chunk_begin = begin;

    do{
        if(std::distance(chunk_end, end) < k)
            chunk_end = end;
        else
            std::advance(chunk_end, k);
        f(chunk_begin,chunk_end);
        chunk_begin = chunk_end;
    }while(std::distance(chunk_begin,end) > 0);
}
like image 174
BenjaminB Avatar answered Sep 20 '22 05:09

BenjaminB


This is a sort-of-generic solution with good performance:

template <class T, class Func>
void do_chunks(T container, size_t K, Func func) {
    size_t size = container.size();
    size_t i = 0;

    // do we have more than one chunk?
    if (size > K) {
        // handle all but the last chunk
        for (; i < size - K; i += K) {
            func(container, i, i + K);
        }
    }

    // if we still have a part of a chunk left, handle it
    if (i % K) {
        func(container, i, i + i % K);
    }
}
like image 36
orlp Avatar answered Sep 21 '22 05:09

orlp