Разделить контейнер на куски, C ++

Question

С учетом вектора из N элементов v = ( 1, 2, 3, 4, ... , N ) возвращать итератор диапазона для всех кусков размером K<N.Последний диапазон может быть меньше K, если 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).

-------------------------- [править] --------------------------

Некоторые из вас хотели бы получить рабочий пример,вот оно.

#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, тогда выбрасывается <code>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;
}

EDIT: Было бы лучше написать 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; 
}

и вызов chunk будет менее красивым, но в целом более полезным (хотя и не в этом случае):

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

Answer 4

Извините за задержку с ответом, но похоже, что никто не предложил это решение:

template <typename Cont, typename Func, typename Sep>
void do_chunks(const Cont& cont, size_t K, Func f, Sep sep, char c='\n') {
    size_t size = cont.size();
    for (int i = 0; i < K; ++i) {
        for (int j = i*size / K, n = (i + 1)*size / K; j < n; ++j) {
            f(cont[j]);
        }
        sep(c);
    }
}

std::vector<int> m = {
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
};
do_chunks(
    m, 
    3, 
    [](const auto& x) { std::cout << x << " "; }, 
    [](char c)        { std::cout << c; }
);

вывод:

1 2 3
4 5 6 7
8 9 10 11

Так что когда i == K - 1(i + 1)*size / K == size точно, таким образом, мы корректно перебираем все элементы контейнера без каких-либо выходов за границы.

Answer 5

Я немного изменил anwser @BenjaminB и добавил пример использования этой функции:

#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

Надеюсь, кто-то найдет его полезным.