Esiste un iteratore ciclico standard C++

Question

In base alla seguente domanda: Check if one string is a rotation of other string

stavo pensando di fare un tipo di iteratore ciclico che prende una serie, e sarebbe in grado di risolvere il problema di cui sopra in questo modo:

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

La mia domanda, c'è già qualcosa di simile a questo disponibile? Ho controllato Boost e STL e nessuna implementazione esatta.

Ho una semplice scrittura a mano (derivata da una versione specializzata di std::iterator) ma preferisco utilizzare un'implementazione già realizzata/testata.

Answer 1

Non c'è nulla di simile nello standard. I cicli non funzionano bene con gli iteratori C++ perché una sequenza che rappresenta l'intero ciclo dovrebbe avere first == last e quindi essere la sequenza vuota.

Forse si potrebbe introdurre qualche stato nell'iteratore, una bandiera booleana che rappresenta "non ancora eseguita". La bandiera partecipa al confronto. Impostalo su true prima di iterare e su false su incremento/decremento.

Ma potrebbe essere semplicemente meglio scrivere manualmente gli algoritmi necessari. Una volta che sei riuscito a rappresentare l'intero ciclo, rappresentare una sequenza vuota potrebbe essere diventato impossibile.

MODIFICA: Ora noto che è stato specificato il numero di cicli. Questo fa una grande differenza.

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

Forse stai cercando Boost's Circular Buffer. Ma se hai già controllato Boost, potrebbe non essere quello che vuoi.

Answer 3

Questo dovrebbe fornire alcune idee/soluzioni: 2 renditions, il secondo è un po 'più leggero di peso. Sia testato utilizzando un sottoinsieme di un vettore e 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

D'altra parte, la stessa idea di iteratore ciclico non è compatibile al contenitore STL ideologia. Non si dovrebbe desiderare un iteratore ciclico, poiché l'utente di questo iteratore potrebbe essere sorpreso dal suo comportamento insolito. Di solito in AWL stai iterando dall'inizio alla fine del contenitore. Loop infinito in quel caso. Perché la fine non è raggiungibile.

Dopo tutto, ovviamente, non si eseguiranno più di 2 cicli per risolvere il proprio compito. Non c'è motivo di avere un iteratore speciale con comportamenti confusi. È meglio iterare il solito contenitore lineare due volte o anche meno due volte.

Answer 5

La libreria CGAL definisce Circulators. Sono usati così.

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

Nota che assomigliano iteratori a prima vista, ma di notare che la logica (e la struttura del ciclo) è diverso da quello per iteratori). 'if (non vuoto) do {..} while() instead of while() {...} `.