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

Для вектора 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()) ), "" );

Это решение вполне нормально, но у него есть несколько проблем:

  • for цикл - это необходимо?
  • если вы пишете 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

Ответы

Ответ 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);
}

Ответ 2

WRT "Для этого нужен цикл?"

Конструкция цикла необходима, если вы хотите избежать использования std::distance(), поскольку нужно отслеживать, сколько осталось. (Для контейнеров с произвольным доступом std::distance() дешево - но для всех остальных это слишком дорого для этого алгоритма.)

Проблема WRT я + K/min()

Не пишите я + K или все, что может вызвать проблемы с оберткой/перегрузкой/недогрузкой. Вместо этого отслеживайте, сколько осталось и вычтите. Для этого потребуется использовать min().

WRT элегантное решение

Этот алгоритм более "изящный" в этом:

  • Первые два вышеуказанных пункта "WRT" не являются проблемами.
  • Он не использует внешние библиотеки; - использует только std::copy_n() и std::advance().
  • Он использует зависящий от аргумента поиск, если это необходимо/желательно.
  • Он использует контейнер size_type.
  • Он будет работать эффективно с любым контейнером.
  • Если K <= 0, то std::domain_error выбрано.

Решением является С++ 11, хотя его можно легко преобразовать в С++ 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 получил итератор вывода и вернул выходной итератор. Таким образом, любые обновления между выводами блоков в отношении выходного итератора могут быть правильно обработаны, а общая процедура намного более гибкая. (Например, это позволит функтору запомнить конечную позицию каждого фрагмента, функтор для копирования фрагментов, пустой контейнер и reset выходной итератор и т.д.). Если это нежелательно, то, как и стандартная библиотека можно было бы иметь более одной перегрузки с различными требованиями 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; }
);

Это оказалось удивительно элегантной рутиной.

Ответ 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);
    }
}

Ответ 4

Я немного изменил 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

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

Ответ 5

Я извиняюсь за опоздание с ответом, но похоже, что никто не предложил это решение:

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 точно, таким образом, мы правильно выполняем итерации по всем элементам контейнера без каких-либо выходов за пределы.