blocks|key|1065656|text|您可能正在寻找Boost的Circular+Buffer。但是如果你已经检查了Boost，它可能不是你想要的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1065657|entityMap|0|LINK|mutability|MUTABLE|url|http://www.boost.org/doc/libs/1_42_0/libs/circular_buffer/doc/circular_buffer.html^0|D|F|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You’re maybe looking for Boost’s <a href="http://www.boost.org/doc/libs/1_42_0/libs/circular_buffer/doc/circular_buffer.html" rel="nofollow noreferrer">Circular Buffer</a>. But if you’ve already checked Boost, it might not be the one you want.

blocks|key|1065721|text|这应该会提供一些想法/解决方案:2个格式，第二个稍微轻一点。两者都使用向量和列表的子范围进行了测试...|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1065722|#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()+%2B+i+%25+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%2B%2B()+
++++{
++++++%2B%2Bcursor;
++++++if+(cursor+==+end)
++++++++cursor+=+begin;
++++++return+*this;
++++}

++++RingIterator+operator%2B%2B(int)+
++++{
++++++RingIterator+ring+=+*this;
++++++%2B%2B*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%2B%2B()+
++++{
++++++%2B%2Bcursor;
++++++if+(cursor+==+end)
++++++++cursor+=+begin;
++++++return+*this;
++++}

++++CyclicIterator+operator%2B%2B(int)+
++++{
++++++CyclicIterator+ring+=+*this;
++++++%2B%2B*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--;+%2B%2Biterator)
++++++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()+%2B+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();+%2B%2Blbegin;

++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);
}|code-block|syntax|javascript|1065723|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This should provide some ideas/solutions: 2 renditions, the second is a little lighter in weight. Both tested using a subrange of a vector and a list ...

<pre><code>#include &lt;vector&gt;

template &lt;typename T, typename Container = std::vector&lt;T&gt;, typename Iterator = Container::iterator&gt;
class RingIterator : public std::iterator &lt;std::bidirectional_iterator_tag, T, ptrdiff_t&gt;
{
 Container&amp; data;

 Iterator cursor;
 Iterator begin;
 Iterator end;

 public:

 RingIterator (Container&amp; v) : data(v), cursor(v.begin()), begin(v.begin()), end(v.end()) {}

 RingIterator (Container&amp; v, const Iterator&amp; i) : data(v), cursor(i), begin(v.begin()), end(v.end()) {}

 RingIterator (Container&amp; v, const Iterator&amp; i, const Iterator&amp; j) : data(v), cursor(i), begin(i), end(j) {}

 RingIterator (Container&amp; v, size_t i) : data(v), cursor(v.begin() + i % v.size()), begin(v.begin()), end(v.end()) {}

 bool operator == (const RingIterator&amp; x) const 
 { 
 return cursor == x.cursor; 
 }

 bool operator != (const RingIterator&amp; x) const 
 {
 return ! (*this == x); 
 }

 reference operator*() const 
 {
 return *cursor; 
 }

 RingIterator&amp; operator++() 
 {
 ++cursor;
 if (cursor == end)
 cursor = begin;
 return *this;
 }

 RingIterator operator++(int) 
 {
 RingIterator ring = *this;
 ++*this;
 return ring;
 }

 RingIterator&amp; operator--() 
 {
 if (cursor == begin)
 cursor = end;
 --cursor;
 return *this;
 }

 RingIterator operator--(int) 
 {
 RingIterator ring = *this;
 --*this; 
 return ring;
 }

 RingIterator insert (const T&amp; x)
 {
 return RingIterator (data, data.insert (cursor, x));
 }

 RingIterator erase() 
 {
 return RingIterator (data, data.erase (cursor));
 }
};

template &lt;typename T, typename Iterator&gt;
class CyclicIterator : public std::iterator &lt;std::bidirectional_iterator_tag, T, ptrdiff_t&gt;
{
 Iterator cursor;
 Iterator begin;
 Iterator end;

 public:

 CyclicIterator (const Iterator&amp; i, const Iterator&amp; j) : cursor(i), begin(i), end(j) {}

 bool operator == (const CyclicIterator&amp; x) const 
 { 
 return cursor == x.cursor; 
 }

 bool operator != (const CyclicIterator&amp; x) const 
 {
 return ! (*this == x); 
 }

 reference operator*() const 
 {
 return *cursor; 
 }

 CyclicIterator&amp; operator++() 
 {
 ++cursor;
 if (cursor == end)
 cursor = begin;
 return *this;
 }

 CyclicIterator operator++(int) 
 {
 CyclicIterator ring = *this;
 ++*this;
 return ring;
 }

 CyclicIterator&amp; operator--() 
 {
 if (cursor == begin)
 cursor = end;
 --cursor;
 return *this;
 }

 CyclicIterator operator--(int) 
 {
 CyclicIterator ring = *this;
 --*this; 
 return ring;
 }
};

#include &lt;iostream&gt;
#include &lt;iomanip&gt;

#include &lt;list&gt;

enum { CycleSize = 9, ContainerSize };

template &lt;typename cyclicIterator&gt;
void test (cyclicIterator&amp; iterator, size_t mn)
{
 int m = mn;
 while (m--)
 for (int n = mn; n--; ++iterator)
 std::cout &lt;&lt; std::setw(3) &lt;&lt; *iterator &lt;&lt; ' ';
 --iterator;
 m = mn;
 while (m--)
 for (int n = mn; n--; --iterator)
 std::cout &lt;&lt; std::setw(3) &lt;&lt; *iterator &lt;&lt; ' ';
}

template &lt;typename containers&gt;
void load (containers&amp; container)
{
 while (container.size() &lt; ContainerSize)
 container.push_back (container.size());
}

void main (void)
{
 typedef std::vector&lt;int&gt; vContainer;
 typedef vContainer::iterator vIterator;
 typedef std::list&lt;int&gt; lContainer;
 typedef lContainer::iterator lIterator;

 vContainer v; load (v);
 vIterator vbegin = v.begin() + 1;

 RingIterator &lt;int, vContainer, vIterator&gt; vring (v, vbegin, v.end());
 CyclicIterator &lt;int, vIterator&gt; vcycle (vbegin, v.end());

 lContainer l; load (l);
 lIterator lbegin = l.begin(); ++lbegin;

 RingIterator &lt;int, lContainer, lIterator&gt; lring (l, lbegin, l.end());
 CyclicIterator &lt;int, lIterator&gt; lcycle (lbegin, l.end());

 test (vring, CycleSize);
 test (vcycle, CycleSize);
 test (lring, CycleSize);
 test (lcycle, CycleSize);
}
</code></pre>

blocks|key|1065780|text|另一方面，循环迭代器的思想与STL容器思想不兼容。您不应该使用循环迭代器，因为此迭代器的用户可能会对其不寻常的行为感到惊讶。通常在STL中，你是从容器的开始到结束进行迭代。在这种情况下是无限循环。因为末端是无法到达的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1065781|毕竟，很明显，你不会做超过2个周期来解决你的任务。没有理由使用行为混乱的特殊迭代器。这比通常的线性容器迭代两次更好，甚至可能比两次更少。|1065782|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

On the other hand, the very idea of cyclic iterator is not compatible to STL container ideology. You should not want cyclic iterator, as the user of this iterator may be surprized by its unusual behavior. Usually in STL you are iterating from the beginning to the end of container. Infinite loop in that case. Because the end is not reachable.

After all, obviously, you are not going to do more than 2 cycles to solve your task. No reason to have special iterator with confusing behavior. That is better to iterate usual linear container twice or may be even less then twice.

blocks|key|1280593|text|CGAL库定义了Circulators。它们是这样使用的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1280594|template<class+Circulator,+class+T>+
bool+contains(Circulator+c,+Circulator+d,+const+T&+value)+{+
++if+(c+!=+0)+{+
++++do+{+
++++++if+(*c+==+value)+
++++++++return+true;+
++++}+while+(%2B%2Bc+!=+d);+
++}+
++return+false;+
}+|code-block|syntax|javascript|1280595|注意，乍一看，它们看起来像迭代器，但注意逻辑(和循环结构)与迭代器不同。if(not+empty)+do{..}while()而不是while(){...}。|style|CODE|1280596|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cgal.org/|1|http://doc.cgal.org/latest/Circulator/classCirculator.html^0|0|4|0|8|B|1|0|0|10|R|1U|C|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]|$A|10|B|11|1|12]]|C|$]]|$1|D|3|E|5|F|7|13|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|14|8|@$A|15|B|16|K|L]|$A|17|B|18|K|L]]|9|@]|C|$]]|$1|M|3|-4|5|6|7|19|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]|U|$5|P|Q|R|C|$S|V]]]]

The <a href="http://www.cgal.org/" rel="nofollow noreferrer">CGAL</a> library defines <a href="http://doc.cgal.org/latest/Circulator/classCirculator.html" rel="nofollow noreferrer">Circulators</a>. They are used like this. 

<pre><code>template&lt;class Circulator, class T&gt; 
bool contains(Circulator c, Circulator d, const T&amp; value) { 
 if (c != 0) { 
 do { 
 if (*c == value) 
 return true; 
 } while (++c != d); 
 } 
 return false; 
} 
</code></pre>

Note that they look like iterators at first glance but note that the logic (and the structure of the loop) is different than for iterators). <code>if(not empty) do{..}while()</code> instead of <code>while(){...}</code>.

blocks|key|1065840|text|Eric+Niebler的ranges+v3库(即将发布的C%2B%2B20+ranges基于该库)具有ranges::view::cycle。这使其源范围适应于无休止重复的无限范围。但是，我们需要一次重复，这可以使用ranges::view::concat轻松实现。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1065841|#include+<ranges/v3/all.hpp>

int+main()+{
++++std::string+s1+=+"abc";
++++std::string+s2+=+"bca";

++++auto+s2s2+=+ranges::view::concat(s2,+s2);
++++auto+i+=+std::search(s2s2.begin(),+s2s2.end(),+s1.begin(),+s1.end());
++++if+(i+!=+s2s2.end()+&&+s1.size()+==+s2.size())+{
++++++++std::cout+<<+"s1+is+a+rotation+of+s2\n";
++++}
}|code-block|syntax|javascript|1065842|entityMap|0|LINK|mutability|MUTABLE|url|https://en.cppreference.com/w/cpp/ranges|1|https://ericniebler.github.io/range-v3/structranges_1_1v3_1_1view_1_1cycle__fn.html|2|https://ericniebler.github.io/range-v3/structranges_1_1v3_1_1view_1_1concat__fn.html^0|1C|J|2X|K|T|C|0|1C|J|1|2X|K|2|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]|$9|Z|A|10|B|C]]|D|@$9|11|A|12|1|13]|$9|14|A|15|1|16]|$9|17|A|18|1|19]]|E|$]]|$1|F|3|G|5|H|7|1A|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]]|L|$M|$5|N|O|P|E|$Q|R]]|S|$5|N|O|P|E|$Q|T]]|U|$5|N|O|P|E|$Q|V]]]]

Eric Niebler's ranges-v3 library (on which the upcoming <a href="https://en.cppreference.com/w/cpp/ranges" rel="nofollow noreferrer">C++20 ranges</a> is based) has <a href="https://ericniebler.github.io/range-v3/structranges_1_1v3_1_1view_1_1cycle__fn.html" rel="nofollow noreferrer"><code>ranges::view::cycle</code></a>. This adapts its source range into an endlessly repeating infinite range. However we require a single repeat which may be easily achieved using <a href="https://ericniebler.github.io/range-v3/structranges_1_1v3_1_1view_1_1concat__fn.html" rel="nofollow noreferrer"><code>ranges::view::concat</code></a>.

<pre><code>#include &lt;ranges/v3/all.hpp&gt;

int main() {
 std::string s1 = "abc";
 std::string s2 = "bca";

 auto s2s2 = ranges::view::concat(s2, s2);
 auto i = std::search(s2s2.begin(), s2s2.end(), s1.begin(), s1.end());
 if (i != s2s2.end() &amp;&amp; s1.size() == s2.size()) {
 std::cout &lt;&lt; "s1 is a rotation of s2\n";
 }
}
</code></pre>

Based on the following question: <a href="https://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string">Check if one string is a rotation of other string</a>

I was thinking of making a cyclic iterator type that takes a range, and would be able to solve the above problem like so:

<pre><code>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 &lt;&lt; "s1 is a rotation of s2" &lt;&lt; std::endl;
}
</code></pre>

My question, Is there already something like this available? I've checked Boost and STL and neither have an exact implementation. 

I've got a simple hand-written (derived from a <code>std::forward_iterator_tag</code> specialised version of <code>std::iterator</code>) one but would rather use an already made/tested implementation.

Is there a standard cyclic iterator in C++

容器

基于以下问题：我在考虑做一个带范围的循环迭代器类型，可以像这样解决上面的问题：std::string s1 = "abc" ;std::string s2 = "bca" ;std::size_t n = 2; // number of cyclescyclic_iterator it(s2.begin(),s2.en...

问C++中有没有标准的循环迭代器？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++中有没有标准的循环迭代器？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++中有没有标准的循环迭代器？
EN