コンテナをチャンクに分割するC++

Question

N要素のベクトルが与えられた場合v = (1, 2, 3, 4, ... , N)サイズK<Nのすべてのチャンクにわたるリターン・レンジ・イテレータ。 N%K!=0の場合、最後の範囲はKより小さくなる可能性があります。例えば

：

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

表示文字列

"ab", "cd", "e" 

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

一つの可能​​な解決策は、次のとおりです。

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

このソリューションはかなりOKですが、それはいくつかの問題があります。

1. forループ - それは必要ですか？
2. min(i+K, v.size())アルゴリズムクラッシュの代わりにi+Kを書き込む場合、境界の場合にはさらに注意を払う必要があります。これは醜く見え、気をそらす。

より洗練されたソリューションを提案できますか？ エレガントなソリューションとは、一般的なアルゴリズムを使用することです。一般的なライブラリ（boostなど）を使ってビルドするか、提供します。

-------------------------- [編集] ----------------- ---------

あなたの中には実例がありましたが、ここはそうです。

#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; 
} 

出力：

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); 
    } 
} 

Answer 1

標準関数を持つイテレータは、前進距離：

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); 
} 

Answer 2

、それは非常にエレガントだ場合、私は知りませんが、あなたが使用することができます。これは、優れた性能を持つソート・オブ・汎用的なソリューションです

ab 
cd 
e 

Answer 3

WRT "Forループは必要ですか？"

どれくらい残っているかを追跡する必要があるため、std::distance()を使用しないようにするには、ループ構造が必要です。 （ランダム・アクセス・コンテナの場合、std::distance()は安いです - しかし、すべての他人のために、それは、このアルゴリズムはあまりにもコストがかかります。）私はK /分（）問題

は私がKを+書き込まないでください+

WRTラッピング/オーバー/アンダーフローの問題を引き起こす可能性があります。代わりに残っている量を追跡し、差し引く。これにはmin()を使用する必要があります。

WRTエレガントなソリューション

このアルゴリズムは、その中より、 "エレガント" である：

1. 上記の最初の二つの "WRT" の項目の問題ではありません。
2. 外部ライブラリは使用しません。 - std::copy_n()とstd::advance()のみを使用します。
3. 引数が必要な場合は、引数に依存する参照を利用します。
4. コンテナのsize_typeを使用します。
5. これはどんな容器でも効率的に動作します。
6. K < = 0の場合、std::domain_errorがスローされます。

解決策はC++ 11ですが、copy_n()も書き込むと簡単にC++ 98に変換できます。

#include <vector> 
#include <string> 
#include <sstream> 
#include <iterator> 
#include <iostream> 
#include <stdexcept> 
#include <algorithm> 

template < 
    typename Container, 
    typename OutIter, 
    typename ChunkSepFunctor 
> 
OutIter chunker(
    Container const& c, 
    typename Container::size_type const& k, 
    OutIter o, 
    ChunkSepFunctor sep 
) 
{ 
    using namespace std; 

    if (k <= 0) 
    throw domain_error("chunker() requires k > 0"); 

    auto chunkBeg = begin(c); 
    for (auto left=c.size(); left != 0;) 
    { 
    auto const skip = min(left,k); 

    o = copy_n(chunkBeg, skip, o); 

    left -= skip; 
    advance(chunkBeg, skip); 

    if (left != 0) 
     sep(); 
    } 
    return o; 
} 

int main() 
{ 
    using namespace std; 

    using VECTOR = vector<string>; 
    VECTOR v{"a","b","c","d","e"}; 

    for (VECTOR::size_type k = 1; k < 7; ++k) 
    { 
    cout << "k = " << k << "..." << endl; 
    chunker(
     v, k, 
     ostream_iterator<VECTOR::value_type>(cout), 
     []() { cout << endl; } 
    ); 
    } 
    cout << endl; 
} 

EDIT：sepファンクタは出力イテレータを受信し、出力イテレータを返されるようにchunker()を書く方が良いでしょう。この方法では、出力イテレータに関する出力チャンク間の更新はすべて正しく処理され、ジェネリックルーチンははるかに柔軟性があります。 （例えば、これは、ファンクタが各チャンクの終了位置を記憶することを可能にする;チャンクをコピーし、コンテナを空にし、出力イテレータをリセットするためのファンクタ;など）これが望ましくない場合、標準ライブラリのように異なるsep要件を持つ複数のオーバーロードがあるか、または引数をすべて削除する必要があります。この更新chunker()次のようになります。

template < 
    typename Container, 
    typename OutIter, 
    typename ChunkSepFunctor 
> 
OutIter chunker(
    Container const& c, 
    typename Container::size_type const& k, 
    OutIter o, 
    ChunkSepFunctor sep 
) 
{ 
    using namespace std; 

    if (k <= 0) 
    throw domain_error("chunker() requires k > 0"); 

    auto chunkBeg = begin(c); 
    for (auto left=c.size(); left != 0;) 
    { 
    auto const skip = min(left,k); 

    o = copy_n(chunkBeg, skip, o); 

    advance(chunkBeg, skip); 
    left -= skip; 

    if (left != 0) 
     o = sep(o); 
    } 
    return o; 
} 

とチャンクへの呼び出しは（ないこのケースではあるが）それほどかなり一般的に、より有用であろう：

chunker(
    v, k, 
    ostream_iterator<VECTOR::value_type>(cout), 
    [](ostream_iterator<VECTOR::value_type> o) { cout << endl; return o; } 
); 

はこれがあることが判明しました驚くほどエレガントな小さなルーチン。

Answer 4

私は少し@BenjaminBでanwserを修正して、この機能を使用する例を追加しました：

#include <iostream> 
#include <vector> 

using namespace std; 

template<typename Iterator, typename Func> 
void chunks(Iterator begin, 
      Iterator end, 
      iterator_traits<string::iterator>::difference_type 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); 
} 

int main() { 
    string in_str{"123123123"}; 

    vector<string> output_chunks; 

    auto f = [&](string::iterator &b, string::iterator &e) 
    { 
     output_chunks.emplace_back(b, e); 
    }; 

    chunks(in_str.begin(), in_str.end(), 3, f); 

    for (string a_chunk: output_chunks) 
    { 
     cout << a_chunk << endl; 
    } 

    return 0; 
} 

結果は次のとおりです。

123 
123 
123 

は、誰かが役に立つことを見つけることを願っています。