que - ¿Hay un iterador cíclico estándar en C++?

que es un iterador c++

Question

Basado en la siguiente pregunta: Compruebe si una cadena es una rotación de otra cadena

Estaba pensando en hacer un tipo de iterador cíclico que tome un rango, y podría resolver el problema anterior de esta manera

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? He comprobado Boost y STL y ninguno tiene una implementación exacta.

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

Answer 1

Esto debería proporcionar algunas ideas / soluciones: 2 versiones, la segunda es un poco más liviana. Ambos probados 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 2

La biblioteca CGAL define los 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 parecen iteradores a primera vista, pero tenga en cuenta que la lógica (y la estructura del bucle) es diferente a la de los iteradores). if(not empty) do{..}while() lugar de while(){...} .

Answer 3

No hay nada como esto en la norma. Los ciclos no juegan 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, una bandera booleana que represente "aún no se ha hecho". La bandera participa en comparación. Establézcalo en 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.

EDITAR: Ahora me doy cuenta de 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 4

Por otro lado, la idea misma de iterador cíclico no es compatible con la ideología de contenedor STL. No debe querer el iterador cíclico, ya que el usuario de este iterador puede sorprenderse por su comportamiento inusual. Por lo general, en STL usted 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 iterador especial con comportamiento confuso. Eso es mejor iterar el contenedor lineal habitual dos veces o puede ser incluso menos que dos veces.

Answer 5

Tal vez estés buscando el Buffer Circular de Boost. Pero si ya has marcado Boost, puede que no sea el que quieres.