C++中有标准循环迭代器吗?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (72)

我正在考虑制作一个循环迭代器类型,它需要一个范围,并能够解决上述问题,如下所示:

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::forward_iterator_tag专门的版本std::iterator),但宁可使用已经制定/测试的实现。

提问于
用户回答回答于

标准中没有这样的东西。循环在C ++迭代器中表现不佳,因为代表整个循环的序列会first == last有空序列。

可能你可以在迭代器中引入一些状态,一个布尔标志来表示“尚未完成”。true在迭代之前设置它,并false在增加/减少时进行设置。

但是手动编写所需的算法可能会更好。一旦你设法表示整个循环,代表一个空序列可能变得不可能。

用户回答回答于

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

扫码关注云+社区