Czy istnieje norma iterator cykliczny w C++

Question

oparciu o następujące pytanie: Check if one string is a rotation of other string

Myślałam popełnienia cykliczny typu iterator że trwa szereg, i byłby w stanie rozwiązać powyższy problem tak:

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

Moje pytanie, czy jest już dostępne coś takiego? Sprawdziłem Boost i STL i nie mam dokładnej implementacji.

Mam prosty odręczny (wywodzący się z wyspecjalizowaną wersję std::iterator) jeden, ale wolałbym użyć już wykonane/przetestowane realizacji.

Answer 1

Nie ma nic takiego w standardzie. Cykle nie grają dobrze z iteratorami C++, ponieważ sekwencja reprezentująca cały cykl miałaby first == last, a zatem byłaaby pustą sekwencją.

Prawdopodobnie mógłbyś wprowadzić jakiś stan do iteratora, boolowską flagę reprezentującą "jeszcze nie zrobione". Flaga bierze udział w porównaniu. Przed wykonaniem iteracji ustaw go na true i na false po inkrementacji/dekrementacji.

Ale może lepiej byłoby ręcznie napisać algorytmy, których potrzebujesz. Gdy uda ci się reprezentować cały cykl, reprezentowanie pustej sekwencji może stać się niemożliwe.

EDYCJA: Teraz zauważam, że podałeś liczbę cykli. To robi dużą różnicę.

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

Być może szukasz Boost's Circular Buffer. Ale jeśli już zaznaczyłeś opcję Zwiększ, może to nie być ta, której chcesz.

Answer 3

Powinno to dostarczyć pewnych pomysłów/rozwiązań: 2 wersje, druga jest nieco lżejsza. Oba testowane za pomocą podzakresu z wektorem oraz listę ...

#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

Z drugiej strony, sama idea cyklicznego iterator nie jest zgodny z ideologią kontenera STL. Nie powinieneś chcieć cyklicznego iteratora, ponieważ użytkownik tego iteratora może być zaskoczony jego niecodziennym zachowaniem. Zwykle w STL wykonuje się iteracje od początku do końca kontenera. Nieskończona pętla w tym przypadku. Ponieważ koniec nie jest osiągalny.

Przecież, oczywiście, nie będziesz robić więcej niż 2 cykle, aby rozwiązać swoje zadanie. Nie ma powodu, aby mieć specjalny iterator z mylącym zachowaniem. Lepiej jest powtarzać zwykły liniowy pojemnik dwa razy lub może być nawet mniej niż dwa razy.

Answer 5

Biblioteka CGAL definiuje Circulators. Są używane w ten sposób.

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

Zauważ, że wyglądają jak iteratorów na pierwszy rzut oka, ale zauważ, że logika (a struktura pętli) jest inna niż dla iteratory). 'if (nie puste) wykonaj {..} while() instead of while() {...} `.