Can I use STL algorithms with circular lists?

Question

Creating an STL-compatible iterator for your custom list is pretty trivial.

However, if the presented list is round, this seems completely pointless, since all STL algorithms work in the range [first, last) and in the circular list first = last .

Is there a standard / consistent way to overcome this obstacle and do STL algorithms work on home circular lists?

I assume that identifying STL-compatible iterators is the first step towards this goal, but it may also be possible to have a solution that works on bands.

---

I need to implement this for many "home" structures. My current solution is to deduce from boost::iterator_facade , and then create my own range class (like Rudolph's ) and use any performance-based algorithm. Nevertheless, this has some logical obstacles and I would like to see the alternatives and / or solutions that have developed.

Answer 1

You will need custom iterators, but the solution can still be range-based. One possibility is that begin() can return a specially allocated iterator (flag initial=true ) so that it knows that it has not yet made a round. end() returns an iterator with the false flag set. Then operator++ set the flag to false, so begin() will not equal end() . You can also use a different labeling scheme.

Answer 2

My understanding of STL and its iterators is incompatible with your proposal. Iterators in the C ++ standard library (as is now known) have pointer semantics. They do not wrap, and end() not equal to begin() .

As analog pointers, iterators indicate a location in the buffer. You cannot expect a linear copy operation by a naive caller to be completed at the end. This will be applied through the algorithm and other libraries. As far as I know, they simply will not work as expected.

I don’t see any reason why you should not use STL collections and iterators, but I don’t think you should expect (or force) it++ wrap it. I rather believe that you need clearly visible member functions that implement the required additional functions.

For example, you might have an incr() function that increments an iterator, but if it points to end() , it wraps itself in the beginning. You may have a copy() function that understands how to retrieve or insert a block of data into a buffer that wraps.

But then I don’t understand your other limitations, so this may not work for you. I think this will work for me.

Answer 3

It is said that in many algorithms (I'm not talking about STL, but in general) a null sheet or null element is inserted into the internal data structure to improve performance.I feel that saving an empty / null element in your circular list can do the trick.

• The zero element is not fixed in position, obviously, and it will move in accordance with the data stream.
• At the same time, you will save the last sample N in your data structure (size N + 1 of the empty element).
• This makes the range [first,last) valid where first != last .
• The null element is the last one indicated, and it will contain the next insert.
• At each insertion, when N elements are in the container, the element indicated by first is “nullified” and first incremented.

Hope this helps.