Gibt es einen Standard zyklischer Iterator in C++

Question

über folgende Frage Basierend: Check if one string is a rotation of other string

Ich dachte, ein zyklisches Iteratortyp machen, die eine Reihe nimmt, und wäre in der Lage, das obige Problem wie so zu lösen:

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

Meine Frage, Gibt es schon so etwas? Ich habe Boost und STL überprüft und keine genaue Implementierung.

Ich habe eine einfache handschriftliche (abgeleitet von einer std::forward_iterator_tag spezialisierte Version von std::iterator), aber würde lieber eine bereits hergestellte/getestete Implementierung verwenden.

Answer 1

Es gibt nichts wie das in der Norm. Zyklen spielen nicht gut mit C++ Iteratoren, weil eine Sequenz, die den gesamten Zyklus darstellt, first == last hätte und daher die leere Sequenz wäre.

Möglicherweise könnten Sie einen Zustand in den Iterator einführen, ein boolesches Flag, um "noch nicht fertig" darzustellen. Die Flagge nimmt am Vergleich teil. Stellen Sie es vor dem Iterieren auf true und auf Inkrement/Dekrement auf false.

Aber es könnte einfach besser sein, die benötigten Algorithmen manuell zu schreiben. Sobald es Ihnen gelungen ist, den gesamten Zyklus darzustellen, ist es möglicherweise unmöglich geworden, eine leere Sequenz darzustellen.

EDIT: Jetzt merke ich, dass Sie die Anzahl der Zyklen angegeben. Das macht einen großen Unterschied.

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

Sie suchen vielleicht nach Boost Circular Buffer. Aber wenn Sie Boost bereits überprüft haben, ist es möglicherweise nicht das, was Sie wollen.

Answer 3

Dies sollte einige Ideen/Lösungen bieten: 2 Darstellungen, die zweite ist ein bisschen leichter. Beide getestet mit einem Teilbereich eines Vektors und einer Liste ...

#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

Auf der anderen Seite, die Idee des zyklischen Iterator ist zu STL-Container Ideologie nicht kompatibel. Sie sollten keinen zyklischen Iterator wünschen, da der Benutzer dieses Iterators durch sein ungewöhnliches Verhalten überrascht sein könnte. Normalerweise durchlaufen Sie in STL vom Anfang bis zum Ende des Containers. Unendliche Schleife in diesem Fall. Weil das Ende nicht erreichbar ist.

Schließlich werden Sie natürlich nicht mehr als 2 Zyklen tun, um Ihre Aufgabe zu lösen. Kein Grund, speziellen Iterator mit verwirrendem Verhalten zu haben. Das ist besser, um den üblichen linearen Container zweimal zu wiederholen oder sogar weniger als zweimal.

Answer 5

Die CGAL Bibliothek definiert Circulators. Sie werden so benutzt.

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

anzumerken, dass sie auf den ersten Blick wie Iteratoren aussehen, aber beachten Sie, dass die Logik (und die Struktur der Schleife) als für Iteratoren unterscheidet). 'Wenn (nicht leer) mache {..} while() instead of while() {...} `.