将容器划分为大块，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())), ""); 

该解决方案是相当确定的，但它有几个问题：

1. for循环 - 是否需要？
2. 如果您编写i+K而不是min(i+K, v.size())算法压碎，则需要额外注意边界情况。这看起来很丑陋和分散注意力。

你能提出更优雅的解决方案吗？ 优雅的解决方案我的意思是使用一般算法，内置或由常用库（如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; 
} 

输出：

ab 
cd 
e 

Answer 1

这是排序通用的 - 一个解决方案具有良好的性能：

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 2

我不知道这是否是很优雅，但你可以使用具有标准功能提前量和距离的迭代器：

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 3

WRT“For循环是否需要？”

如果您想避免使用std::distance()，需要循环构造，因为需要跟踪剩余多少元素。 （对于随机接入容器，std::distance()是便宜的 - 但对于所有其他实在是太昂贵了该算法。）

WRT I + K /分钟（）问题

不要写I + K或任何可能导致打包/溢出/下溢问题的事情。而是跟踪剩余和减去多少。这将需要使用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; 
} 

编辑：倒不如写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 

希望有人会发现它有用。