CODEWITHSUNDEEP
c++algorithmstl
Nikos Athanasiou
Nikos Athanasiou

Reputation: 31519

Can STL algorithms be used with circular lists?

Creating an STL compliant iterator for your custom list is pretty mundane.

Yet, if the reffered list is a circular one, it seems quite pointless since all STL algorithms are operating on a [first, last) range and in a circular list first = last.

Is there a standard/consice way to overcome this obstacle and have STL algorithms operate on "home made" circular lists ?

I'm supposing defining STL compliant iterators is the first step to this goal, but a solution that would operate on ranges might also be possible.

I need to implement this for a plethora of "home made" structs. My current solution is to derive from boost::iterator_facade and then create a custom range class (like Rudolph's) and use any algorithm wrapped around range-based execution. Still this has some logical obstacles and would like to see alternatives and or solutions that worked out.

Upvotes: 6

Views: 588

Answers (3)

Stefano Buora
Stefano Buora

Reputation: 1062

Said that in many algorithms (I'm not talking about STL, but in general) a null-leaf(s) or null element(s) is(are) inserted in the internal data structure in order to improve performance, I feel like keeping an empty/null element in your circular list can make the trick.

  • The null element is not fixed in position, obviously, and it will move according to your data flow.
  • At the same time you'll keep the last N sample in your data struct (size N + 1 empty element) contiguous.
  • That makes feasible a range [first,last) where first != last.
  • The null element is the one pointed by last, and it's where the next insertion will take place.
  • At every insertion, once N elements are in the container, the element pointed by first is "nullified", and first incremented.

Hope this may help.

Upvotes: 0

david.pfx
david.pfx

Reputation: 10868

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

As pointer analogues, iterators point to a location in a buffer. You cannot expect a linear copy operation by a naive caller to wrap around at the end. This will apply through the algorithm and other libraries. They will simply not work as expected, as far as I can see.

I see no reason at all why you should not use STL collections and iterators, but I don't think you should expect (or force) it++ to wrap. I rather think you need clearly visible member functions that implement the additional functionality you require.

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

But then I don't understand your other constraints, so this might not work for you. I think it would work for me.

Upvotes: 1

isarandi
isarandi

Reputation: 3349

You will need custom iterators, but the solution can still be range-based. One possibility is that begin() could return a specially marked iterator (flag initial=true) so that it knows that it hasn't made the round yet. end() would return an iterator with that flag set to false. Then operator++ would set the flag to false, so that begin() won't be equal to end(). You could use a different marking scheme as well.

Upvotes: 4

Related Questions