Thread: Circular Lists

  1. #16
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Quote Originally Posted by CornedBee View Post
    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?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  4. #19
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    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.

  5. #20
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  6. #21
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by dudeomanodude View Post
    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.

  7. #22
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by abachler View Post
    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>

  8. #23
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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...
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  9. #24
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by brewbuck View Post
    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...
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #25
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  11. #26
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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?
    Last edited by laserlight; 03-04-2008 at 02:36 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #27
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Eh, my example is incomplete.
    Even so, it's going to be significantly less code than implementing my own doubly-linked circular list template.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  13. #28
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by dudeomanodude View Post
    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.

    Quote Originally Posted by brewbuck View Post
    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?
    Last edited by CornedBee; 03-04-2008 at 03:05 PM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #29
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    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.

  15. #30
    Registered User jian2587's Avatar
    Join Date
    Feb 2008
    Location
    NY
    Posts
    11
    Quote Originally Posted by CornedBee View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. circular linked lists??
    By atif in forum C Programming
    Replies: 3
    Last Post: 04-30-2002, 03:58 AM
  5. circular shift
    By n00bcodezor in forum C Programming
    Replies: 2
    Last Post: 11-20-2001, 03:51 AM