将容器划分为块,C++

Question

给定一个N元素向量v = ( 1, 2, 3, 4, ... , N )返回范围迭代器覆盖所有大小的块K<N.最后一个范围可以小于Kif N%K!=0.

例如:

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)构建或提供.

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

你们当中有些人在这方面取得了成功.

#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

我不知道它是否非常优雅,但你可以使用标准函数advance和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);
}

Answer 2

WRT"需要循环吗？"

如果想要避免使用循环结构,则需要std::distance()跟踪剩余多少.(对于随机访问容器,std::distance()价格便宜 - 但对于所有其他容器来说,这种算法成本太高.)

WRT i + K/min()问题

不要编写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,尽管如果一个人也写,它可以很容易地转换为C++ 98 copy_n().

#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仿函数接收输出迭代器并返回输出迭代器.这样,可以正确处理输出关于输出迭代器的块之间的任何更新,并且通用例程更加灵活.(例如,这将允许仿函数记住每个块的结束位置;仿冒块复制块,清空容器,重置输出迭代器;等等)如果这是不希望的,那么就像标准库一样可以有多个具有不同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 3

这是一种具有良好性能的通用解决方案:

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