Divida el contenedor en trozos, C++

Question

Dado un vector de N elementos v = (1, 2, 3, 4, ... , N) iterador de rango de retorno en todos los trozos de tamaño K<N. El último rango puede ser más pequeño que K si N%K!=0.

Por ejemplo:

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

visualización cadenas

"ab", "cd", "e" 

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

Una posible solución es:

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

Esta solución es bastante bueno, pero tiene varios problemas:

1. for lazo - ¿es necesario?
2. si escribe i+K en lugar de min(i+K, v.size()) aplasta el algoritmo, hay que prestar atención adicional al caso límite. Esto se ve feo y distrae.

¿Puede proponer una solución más elegante? Por solución elegante me refiero al uso de un algoritmo general, incorporado o proporcionado por la biblioteca de uso común (como el impulso).

-------------------------- [editar] ----------------- ---------

Algunos de ustedes ganaron ejemplo de trabajo, aquí está.

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

Salida:

ab 
cd 
e 

Answer 1

Ésta es una solución de clase-de-genérico con buen rendimiento:

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

No sé si es muy elegante, pero se puede usar iteradores con funciones estándar de avance y distancia:

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 "¿Se necesita bucle?"

Se necesita una construcción de bucle si se quiere evitar el uso de std::distance() ya que se necesita rastrear cuánto queda. (Para los envases de acceso aleatorio, std::distance() es barato --pero para todos los demás que es demasiado costoso para este algoritmo.)

WRT i + K/min() tema

No escriba i + K o cualquier cosa que pueda causar problemas de envoltura/sobre/bajo flujo. En lugar de eso rastrear cuánto queda y restar. Esto requerirá usar min().

WRT solución elegante

Este algoritmo es más "elegante" en la que:

1. Los primeros dos artículos "WRT" anteriores no son cuestiones.
2. No utiliza ninguna biblioteca externa; --sólo hace uso de std::copy_n() y std::advance().
3. Explota la búsqueda dependiente del argumento si es necesario/deseado.
4. Utiliza el contenedor size_type.
5. Funcionará eficientemente con cualquier contenedor.
6. Si K < = 0, se emite std::domain_error.

La solución es C++ 11 aunque se puede convertir fácilmente a C++ 98 si también se escribe 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: Sería mejor escribir chunker() para que el funtor sep recibió el iterador de salida y devuelve un iterador de salida. De esta forma, cualquier actualización entre los fragmentos de salida con respecto al iterador de salida podría manejarse correctamente y la rutina genérica sería mucho más flexible. (Por ejemplo, esto permitiría al funtor recordar la posición final de cada fragmento, el funtor para copiar fragmentos, vaciar el contenedor y restablecer el iterador de salida; etc.) Si esto no es deseado, entonces al igual que la Biblioteca estándar, uno podría tiene más de una sobrecarga con diferentes requisitos sep o eliminando el argumento por completo. Esta actualización chunker() se parece a esto:

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

y la llamada a trozo sería la menos bonita, pero en general más útil (aunque no en este caso):

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

Esto ha resultado ser una pequeña rutina sorprendentemente elegante.

Answer 4

que poco modificado por anwser @BenjaminB y añadí un ejemplo del uso de esta función:

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

El resultado es:

123 
123 
123 

espero que alguien le resulte útil.