가 다음과 같은 질문을 바탕으로

Question

C++ 표준 순환 반복자가 있습니까 : Check if one string is a rotation of other string

내가 범위를 취 순환 반복자 타입을 생각하고 있었는데, 그래서 같이 위의 문제를 해결할 수있을 것입니다 :

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

내 질문에 이미 사용 가능한 제품이 있습니까? Boost와 STL을 확인한 결과 정확한 구현이 이루어지지 않았습니다.

손으로 작성한 (std::iterator의 std::forward_iterator_tag 특수 버전에서 파생 된) 간단한 손수 작성기가 있지만 이미 작성되었거나 테스트 된 구현을 사용합니다.

Answer 1

표준에는 이와 비슷한 것이 없습니다. Cycles는 C++ 반복자에서 잘 작동하지 않습니다. 전체주기를 나타내는 시퀀스가 ​​first == last이므로 빈 시퀀스가되기 때문입니다.

아마도 "아직 완료되지 않음"을 나타내는 부울 플래그 인 iterator에 어떤 상태를 도입 할 수 있습니다. 플래그는 비교에 참여합니다. iterating 전에 true으로 설정하고 증가/감소시 false으로 설정하십시오.

하지만 필요한 알고리즘을 수동으로 작성하는 것이 좋습니다. 전체 사이클을 표현할 수있게되면 빈 시퀀스를 나타내는 것이 불가능해질 수 있습니다.

편집 : 이제 사이클 수를 지정했음을 확인했습니다. 그것은 큰 차이를 만듭니다.

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

아마도 부스트의 Circular Buffer을 찾고있을 것입니다. Boost를 이미 확인했다면 원하는 것이 아닐 수도 있습니다.

Answer 3

다음은 몇 가지 아이디어/솔루션을 제공해야합니다. 2 개의 렌 디션, 두 번째는 약간 가벼운 무게입니다. 벡터와리스트의 부분 범위를 사용하여 테스트 모두 ... 한편

#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

는 순환 반복자의 아주 아이디어는 STL 컨테이너 이데올로기에 호환되지 않습니다. 이 반복자의 사용자가 비정상적인 동작에 의해 과장 될 수 있으므로 순환 반복기를 원하지 않아야합니다. 일반적으로 STL에서는 컨테이너의 처음부터 끝까지 반복합니다. 이 경우 무한 루프. 끝이 도달 할 수 없기 때문입니다.

결국 분명히 작업을 해결하기 위해 2주기 이상을 수행하지 않을 것입니다. 혼란스러운 행동을하는 특별한 반복자를 가질 이유는 없습니다. 보통의 선형 컨테이너를 두 번 반복하는 것이 더 좋으며 두 번 더 적을 수도 있습니다.

Answer 5

CGAL 라이브러리는 Circulators을 정의합니다. 그들은 이런 식으로 사용됩니다. 그들은 첫눈에 반복자처럼 보이지만 로직 (루프의 구조)) 반복자과 다릅니다 것을

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

참고. '(비어 있지 않다면) {..} while() instead of while() {...}`.