¿Existe un iterador cíclica estándar en C++

Question

Sobre la base de la siguiente pregunta: Check if one string is a rotation of other string

Yo estaba pensando en hacer un tipo de iterador cíclico que tiene un rango, y sería capaz de resolver el problema anterior, así:

std::string s1 = "abc" ; 
std::string s2 = "bca" ; 
std::size_t n = 2; // number of cycles 
cyclic_iterator it(s2.begin(),s2.end(),n); 
cyclic_iterator end; 

if (std::search(it, end, s1.begin(),s1.end()) != end) 
{ 
    std::cout << "s1 is a rotation of s2" << std::endl; 
} 

Mi pregunta, ¿Ya hay algo como esto disponible? Revisé Boost y STL y tampoco tengo una implementación exacta.

Tengo una simple versión manuscrita (derivada de una versión especializada std::forward_iterator_tag de std::iterator) pero preferiría usar una implementación ya hecha/probada.

Answer 1

No hay nada como esto en el estándar. Los ciclos no funcionan bien con los iteradores de C++ porque una secuencia que representa el ciclo completo tendría first == last y, por lo tanto, sería la secuencia vacía.

Posiblemente podría introducir algún estado en el iterador, un indicador booleano para representar "aún no se ha completado". La bandera participa en comparación. Configúrelo true antes de iterar y en false al aumentar/disminuir.

Pero podría ser mejor escribir manualmente los algoritmos que necesita. Una vez que haya logrado representar todo el ciclo, representar una secuencia vacía podría haberse vuelto imposible.

EDIT: Ahora he notado que ha especificado el número de ciclos. Eso hace una gran diferencia.

template< class I > 
class cyclic_iterator 
/* : public iterator< bidirectional, yadda yadda > */ { 
    I it, beg, end; 
    int cnt; 
    cyclic_iterator(int c, I f, I l) 
     : it(f), beg(f), end(l), cnt(c) {} 
public: 
    cyclic_iterator() : it(), beg(), end(), cnt() {} 

    cyclic_iterator &operator++() { 
     ++ it; 
     if (it == end) { 
      ++ cnt; 
      it = beg; 
     } 
    } // etc for --, post-operations 

    friend bool operator== 
     (cyclic_iterator const &lhs, cyclic_iterator const &rhs) 
     { return lhs.it == rhs.it && lhs.cnt == rhs.cnt; } // etc for != 

    friend pair< cyclic_iterator, cyclic_iterator > cycle_range 
     (int c, I f, I l) {//factory function, better style outside this scope 
     return make_pair(cyclic_iterator(0, f, l), 
          cyclic_iterator(c, f, l)); 
    } 
}; 

Answer 2

Quizás esté buscando Boost Circular Buffer. Pero si ya ha marcado Boost, puede que no sea el que desea.

Answer 3

Esto debería proporcionar algunas ideas/soluciones: 2 entregas, el segundo es un poco más ligero de peso. Tanto probado usando un subrango de un vector y una lista ...

#include <vector> 

template <typename T, typename Container = std::vector<T>, typename Iterator = Container::iterator> 
class RingIterator : public std::iterator <std::bidirectional_iterator_tag, T, ptrdiff_t> 
{ 
    Container& data; 

    Iterator cursor; 
    Iterator begin; 
    Iterator end; 

    public: 

    RingIterator (Container& v) : data(v), cursor(v.begin()), begin(v.begin()), end(v.end()) {} 

    RingIterator (Container& v, const Iterator& i) : data(v), cursor(i), begin(v.begin()), end(v.end()) {} 

    RingIterator (Container& v, const Iterator& i, const Iterator& j) : data(v), cursor(i), begin(i), end(j) {} 

    RingIterator (Container& v, size_t i) : data(v), cursor(v.begin() + i % v.size()), begin(v.begin()), end(v.end()) {} 

    bool operator == (const RingIterator& x) const 
    { 
     return cursor == x.cursor; 
    } 

    bool operator != (const RingIterator& x) const 
    { 
     return ! (*this == x); 
    } 

    reference operator*() const 
    { 
     return *cursor; 
    } 

    RingIterator& operator++() 
    { 
     ++cursor; 
     if (cursor == end) 
     cursor = begin; 
     return *this; 
    } 

    RingIterator operator++(int) 
    { 
     RingIterator ring = *this; 
     ++*this; 
     return ring; 
    } 

    RingIterator& operator--() 
    { 
     if (cursor == begin) 
     cursor = end; 
     --cursor; 
     return *this; 
    } 

    RingIterator operator--(int) 
    { 
     RingIterator ring = *this; 
     --*this; 
     return ring; 
    } 

    RingIterator insert (const T& x) 
    { 
     return RingIterator (data, data.insert (cursor, x)); 
    } 

    RingIterator erase() 
    { 
     return RingIterator (data, data.erase (cursor)); 
    } 
}; 

template <typename T, typename Iterator> 
class CyclicIterator : public std::iterator <std::bidirectional_iterator_tag, T, ptrdiff_t> 
{ 
    Iterator cursor; 
    Iterator begin; 
    Iterator end; 

    public: 

    CyclicIterator (const Iterator& i, const Iterator& j) : cursor(i), begin(i), end(j) {} 

    bool operator == (const CyclicIterator& x) const 
    { 
     return cursor == x.cursor; 
    } 

    bool operator != (const CyclicIterator& x) const 
    { 
     return ! (*this == x); 
    } 

    reference operator*() const 
    { 
     return *cursor; 
    } 

    CyclicIterator& operator++() 
    { 
     ++cursor; 
     if (cursor == end) 
     cursor = begin; 
     return *this; 
    } 

    CyclicIterator operator++(int) 
    { 
     CyclicIterator ring = *this; 
     ++*this; 
     return ring; 
    } 

    CyclicIterator& operator--() 
    { 
     if (cursor == begin) 
     cursor = end; 
     --cursor; 
     return *this; 
    } 

    CyclicIterator operator--(int) 
    { 
     CyclicIterator ring = *this; 
     --*this; 
     return ring; 
    } 
}; 

#include <iostream> 
#include <iomanip> 

#include <list> 

enum { CycleSize = 9, ContainerSize }; 

template <typename cyclicIterator> 
void test (cyclicIterator& iterator, size_t mn) 
{ 
    int m = mn; 
    while (m--) 
    for (int n = mn; n--; ++iterator) 
     std::cout << std::setw(3) << *iterator << ' '; 
    --iterator; 
    m = mn; 
    while (m--) 
    for (int n = mn; n--; --iterator) 
     std::cout << std::setw(3) << *iterator << ' '; 
} 

template <typename containers> 
void load (containers& container) 
{ 
    while (container.size() < ContainerSize) 
    container.push_back (container.size()); 
} 

void main (void) 
{ 
    typedef std::vector<int>  vContainer; 
    typedef vContainer::iterator vIterator; 
    typedef std::list<int>  lContainer; 
    typedef lContainer::iterator lIterator; 

    vContainer v; load (v); 
    vIterator vbegin = v.begin() + 1; 

    RingIterator <int, vContainer, vIterator> vring (v, vbegin, v.end()); 
    CyclicIterator <int, vIterator> vcycle (vbegin, v.end()); 

    lContainer l; load (l); 
    lIterator lbegin = l.begin(); ++lbegin; 

    RingIterator <int, lContainer, lIterator> lring (l, lbegin, l.end()); 
    CyclicIterator <int, lIterator> lcycle (lbegin, l.end()); 

    test (vring, CycleSize); 
    test (vcycle, CycleSize); 
    test (lring, CycleSize); 
    test (lcycle, CycleSize); 
} 

Answer 4

Por otro lado, la idea misma de iterador cíclico no es compatible con la ideología de contenedores STL. No debería querer el iterador cíclico, ya que el usuario de este iterador puede sorprenderse por su comportamiento inusual. Por lo general, en STL está iterando desde el principio hasta el final del contenedor. Bucle infinito en ese caso. Porque el final no es alcanzable.

Después de todo, obviamente, no va a hacer más de 2 ciclos para resolver su tarea. No hay razón para tener un iterador especial con un comportamiento confuso. Es mejor repetir el contenedor lineal habitual dos veces o incluso menos que dos veces.

Answer 5

La biblioteca CGAL define Circulators. Se usan así.

template <class Circulator, class T> 
bool contains(Circulator c, Circulator d, const T& value) { 
    if (c != 0) { 
    do { 
     if (*c == value) 
     return true; 
    } while (++c != d); 
    } 
    return false; 
} 

Tenga en cuenta que se parecen a los iteradores a primera vista, pero tenga en cuenta que la lógica (y la estructura del bucle) es diferente que para los iteradores). 'if (no vacío) do {..} while() instead of while() {...} `.