Circular Lists

A number of minor nits, like the container being not assignable because it has a reference member. Otherwise solid. No reason not to make it bidirectional, though.

However, I object to making the end iterator a part of the cycle. It's error-prone and defeats most use cases of a circular list.

I wouldn't have thought to ONLY implement the iterator, my feeble minded-attempt would have written the iterator into a class circular_list but looking over your example I guess there's really no need.

Actually, I suggested that "feeble minded-attempt" to you
I was just lazy to do forwarding so I decided to extend the std::list interface instead

By the way, there's a bug even with my incomplete implementation: operator* should return a T& not a T.

Also, since std::list is a doubly linked list, circular_list_iterator probably should be a bidirectional iterator instead of a forward iterator, so change the iterator tag and implement the various operators

Originally Posted by CornedBee

However, I object to making the end iterator a part of the cycle. It's error-prone and defeats most use cases of a circular list.

So you just drop the function circular_list_end(), because there's simply no explicit need to know what's the end of the list for the user?

Did I get that right?

Originally Posted by CornedBee

However, I object to making the end iterator a part of the cycle. It's error-prone and defeats most use cases of a circular list.

I can imagine a few cases where it could help. In a single thread, the sentinel is not necessary, because you can always tell when you've done a full cycle by checking to see if you come back to the same spot.

But in multithreaded code, you might have one thread cycling through the list while another thread is manipulating it. If the manipulating thread happens to delete the element the cycling thread began at, the cycling thread will get stuck in an infinite loop, thinking it has never come full circle. In that case, you can check for the sentinel to know that you've come to the end.

Actually, I suggested that "feeble minded-attempt" to you

ha ha. Yes, you're right and I'm sorry. I certainly didn't even consider iterators until I was told.

Originally Posted by dudeomanodude

I'd like to figure out the best way to implement a circular list ( assume I'm developing a "generic" circluar list ). I have a few questions:

1. Is it possible to implement the STL <list> to make it function as a circular list?

Why woudlyou want to, just make a regular double linked list. Don't rely on teh STL to do everythign for you, especially nto somethign this simple.

2. If I create my own template circular list should I:

a. Use a "sentinel" node that head->prev and tail->next point to or,

This is called the head node or master link.

b. Have head->prev and tail->next point to each other?

This can be done, but somewhere you need to have a pointer to at least one link in the list. This is usually done with a head node (master link) being a static object. Since you may want the list to contain zero items, the use of a master link eliminates the problem with having an extra variable to coutn the number of memebrs in the link so you dont use a NULL pointer when there are zero.

For my second question, my intuition tells me to implement a sentinel node.

I'd really like to be able to use the STL <list> though, as that should involve significantly less coding.

Thoughts?

using the STL for such a simple thing may not actually involve less coding.

Originally Posted by abachler

Why woudlyou want to, just make a regular double linked list. Don't rely on teh STL to do everythign for you, especially nto somethign this simple.

Sure, why write 10 lines of code when you can write 100 lines? And all the effort by the STL designers to ensure the correctness of the data structure is completely valueless. Better to reimplement it yourself, poorly, with dozens of bugs. Programming is all about pointless struggle right?

</sarcasm>

Why woudlyou want to, just make a regular double linked list. Don't rely on teh STL to do everythign for you, especially nto somethign this simple.

Well, look at how many lines of code it took laserlight to do this. Also, the STL is there for us to rely on as C++ programmers. I won't even start to list the number of reasons why you should use the STL...

Originally Posted by brewbuck

I can imagine a few cases where it could help. In a single thread, the sentinel is not necessary, because you can always tell when you've done a full cycle by checking to see if you come back to the same spot.

But in multithreaded code, you might have one thread cycling through the list while another thread is manipulating it. If the manipulating thread happens to delete the element the cycling thread began at, the cycling thread will get stuck in an infinite loop, thinking it has never come full circle. In that case, you can check for the sentinel to know that you've come to the end.

I would make circular_list_begin function - so you always know when you get to the begining of the list, and avoid returning iterator of the end as CornedBee suggested...

When it comes time to decide whether or not to write your own linked-list I now use this as my guide:

Stroustrups's opinion when to hand-code your own list

Well, look at how many lines of code it took laserlight to do this.

Eh, my example is incomplete.

Incidentally, CornedBee has a point. If you want the iterator to be assignable, you probably should store a pointer to the container (but you will not need to manage memory, thankfully). The interface need not be changed, but the implementation will need to be changed.

EDIT:

I would make circular_list_begin function - so you always know when you get to the begining of the list, and avoid returning iterator of the end as CornedBee suggested...

Why would the circular_list_iterator constructors not suffice?

Eh, my example is incomplete.

Even so, it's going to be significantly less code than implementing my own doubly-linked circular list template.

Originally Posted by dudeomanodude

So you just drop the function circular_list_end(), because there's simply no explicit need to know what's the end of the list for the user?

In a circular list, start == end. To fully traverse the list, you do

Code:

typedef circular_iterator<std::list<int>::iterator> cilit;
for(cilit start = circular_begin(lst), it = start; it != start; ++it) {
}

where lst is a std::list<int> and circular_begin is

Code:

template <typename Container>
circular_iterator<typename Container::iterator>
circular_begin(Container &cnt)
{
  return circular_iterator<typename Container::iterator>(
    cnt.begin(), cnt.begin(), cnt.end());
}

template <typename Container>
circular_iterator<typename Container::const_iterator>
circular_begin(const Container &cnt)
{
  return circular_iterator<typename Container::const_iterator>(
    cnt.begin(), cnt.begin(), cnt.end());
}

and circular_iterator is

Code:

template <class Iterator>
class circular_iterator :
  public boost::iterator_adaptor<
    circular_iterator<Iterator>,
    Iterator
  >
{
  typedef circular_iterator::iterator_adaptor_ base_type;
  struct enabler {};
public:
  circular_iterator(Iterator pos, Iterator start, Iterator stop)
    : base_type(pos), m_begin(start), m_end(stop)
  {}

  template <typename OtherIter>
  circular_iterator(const circular_iterator<OtherIter> &o,
      typename boost::enable_if<
        boost::is_convertible<OtherIter, Iterator>, enabler
      >::type = enabler()
  )
    : base_type(o.base()), m_begin(o.m_begin), m_end(o.m_end)
  {
  }

private:
  friend class boost::iterator_core_access;

  Iterator &mine() { return this->base_reference(); }
  const Iterator &mine() const { return this->base_reference(); }

  Iterator m_begin, m_end;

  void increment() {
    ++mine();
    if(mine() == m_end) {
      mine() = m_begin;
    }
  }

  void decrement() {
    if(mine() == m_begin) {
      mine() = m_end;
    }
    --mine();
  }

  void advance(typename base_type::difference_type n)
  {
    // Tricky.
    typedef base_type::difference_type diff_t;
    diff_t size = m_end - m_begin;
    n &#37;= size;
    if(n < 0) {
      diff_t rem = m_end - mine();
      if(rem <= n) {
        n -= rem;
        mine() = m_begin;
      }
      mine() += n;
    } else {
      diff_t rem = mine() - m_begin;
      if(rem < -n) {
        n += rem;
        mine() = m_end;
      }
      mine() += n;
    }
  }

  template <
    class OtherDerived, class OtherIterator, class V, class C, class R, class D
  >
  typename base_type::difference_type distance_to(
    const boost::iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D>& y) const
  {
    typedef base_type::difference_type diff_t;
    diff_t size = m_end - m_begin;
    diff_t firstoff = m_end - mine();
    diff_t secondoff = m_end - y;
    if(firstoff < secondoff) {
      return secondoff - firstoff;
    } else {
      return firstoff + (size - secondoff);
    }
  }
};

Ah, that was fun.

OK, this code is totally untested, but with the stupid errors fixed, it should work for every container that provides at least forward iterators, automatically adopting greater capabilities as they are available. In other words, you can use this as a circular iteration adapter for slist, list, deque, vector, whatever you want.

Originally Posted by brewbuck

But in multithreaded code, you might have one thread cycling through the list while another thread is manipulating it. If the manipulating thread happens to delete the element the cycling thread began at, the cycling thread will get stuck in an infinite loop, thinking it has never come full circle. In that case, you can check for the sentinel to know that you've come to the end.

If you want to make a full circle and another thread modifies the list, you've got bigger fish to fry.

The primary use case for circular structures is a producer/consumer scheme with a typically fixed buffer size, where the consumer basically chases the producer round and round the circle.
The important thing here is that the code using the circular structure doesn't care for the "start". It's circular, it doesn't need one. The start is where the producer starts when the structure is newly created, nothing more. It could be an arbitrary position.
No, what the client code cares about is that, if it knows there's 4 free places ahead, it can perform an operation these places, without worrying about the "hole" the sentinel creates.

It's like a ring walkway with a built-in trap. "Don't step on this floorti-ARRGH!"


Hey, abachler! 86 lines and I've got a circular structure for every imaginable backing store. How's that for code efficiency?

Originally Posted by CornedBee

If you want to make a full circle and another thread modifies the list, you've got bigger fish to fry.

So if one thread is round-robin scheduling the tasks in the ring buffer while some other thread (or possibly many threads) are constantly adding and removing tasks from the buffer... You don't think that is a realistic situation?

If done cleverly, it can even be done without locking, except in certain boundary cases. This sort of thing is very common in system code.

Originally Posted by CornedBee

Hey, abachler! 86 lines and I've got a circular structure for every imaginable backing store. How's that for code efficiency?

86 lines and i learn jeegabytes of stuffs from it. i hardly use templates and STL and this codes are drowning me.