'Looping' an std::list

E

esuvs

Hi, I would like to change the behavior of the std::list so that if I
set an iterator to the last element and increment it I would like it to
point to the first element, and vice vesa. That is, i would like to use
it as a circular buffer.

Is this possble? Given that the linked list is probably just a set of
nodes and 'next' pointers it doesn't seem unreasonable (just set the
last pointer to point at the start) but I suspect the std::list is to
safe/robust to allow me to abuse it in this way...

Be great if someone could prove me wrong :-D Otherwise is there an
STL/Boost container giving this behaviour? I think i could do it with
boost::graph but seems a bit of a heavyweight solution.

Thanks,

David
 
D

Daniel T.

"esuvs said:
Hi, I would like to change the behavior of the std::list so that if I
set an iterator to the last element and increment it I would like it to
point to the first element, and vice vesa. That is, i would like to use
it as a circular buffer.

Is this possble? Given that the linked list is probably just a set of
nodes and 'next' pointers it doesn't seem unreasonable (just set the
last pointer to point at the start) but I suspect the std::list is to
safe/robust to allow me to abuse it in this way...

Be great if someone could prove me wrong :-D Otherwise is there an
STL/Boost container giving this behaviour? I think i could do it with
boost::graph but seems a bit of a heavyweight solution.

I posted the below back in March... (Pieter Pareit seems to have posted
something very much like it back in Jan of 2002.)

You can use the circular_iterator on any of the standard containers. The
code below does need some fleshing out (for eg: post-increment and
decrement, operator->() and const dereference operators) but the below
is enough for most uses.


   template < typename Container >
class circular_iterator_t : public std::iterator<
               typename Container::iterator::iterator_category,
               typename Container::iterator::value_type >
{
   Container& rep;
   typename Container::iterator loc;
public:
   explicit circular_iterator_t( Container& container ):
               rep( container ), loc( container.begin() ) { }
   circular_iterator_t( Container& container,
               typename Container::iterator it ):
               rep( container ), loc( it ) { }
   typename Container::value_type& operator*() {
      return *loc;
   }
   circular_iterator_t& operator--() {
      if ( loc == rep.begin() )
         loc = --rep.end();
      else
         --loc;
      return *this;
   }
   circular_iterator_t& operator++() {
      ++loc;
      if ( loc == rep.end() )
         loc = rep.begin();
      return *this;
   }
   friend bool operator==( const circular_iterator_t& lhs,
               const circular_iterator_t& rhs ) {
      return lhs.rep == rhs.rep && lhs.loc == rhs.loc;
   }
};

   template < typename Container >
bool operator!=( const circular_iterator_t<Container>& lhs,
               const circular_iterator_t<Container>& rhs ) {
   return !( lhs == rhs );

}

   template < typename Container >
circular_iterator_t<Container> circular_iterator( Container& container )
{
   return circular_iterator_t<Container>( container );
}

   template < typename Container >
circular_iterator_t<Container> circular_iterator( Container& container,
typename Container::iterator it ) {
   return circular_iterator_t<Container>( container, it );
}
 
E

esuvs

That's excellent, thanks. I was wondering if I should implement my own
container but yours is a more elegant solution.

David
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top