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 %= 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?