Evan <eed132@psu.edu> wrote in message
news:3f25c666.0307111125.685a9163@posting.google.c om...[color=blue]
> kazio <pkurys@maja.il> wrote in message[/color]
news:<Pine.BSF.4.31L2.0307102158220.94781-100000@novum.am.lublin.pl>...[color=blue][color=green]
> > Hello,
> >
> > So, I need to have double linked, circular list (last element point to[/color][/color]
the[color=blue][color=green]
> > first one and first one points to the last one). I thought maybe I could
> > use list container from STL, but unfortunately probably not. I checked[/color][/color]
it,[color=blue][color=green]
> > and when I increase (++) iterator pointing to the last element the[/color][/color]
program[color=blue][color=green]
> > crashes.
> > I know the standard says, this is a linear list (with beginning and the
> > end), but I completely don't understand why they designed (limited) it[/color][/color]
so.[color=blue][color=green]
> > I also studied quite carefully the source for my STL list implementation
> > (gcc), and I think it is actually a circular list, and there is[/color][/color]
connection[color=blue][color=green]
> > between last and first element (LastElem->next == FirstElem and[/color][/color]
FirstElem->prev ==[color=blue][color=green]
> > LastElem), so I really don't understand:
> > 1) why the iterator cannot go further after the last element[/color]
>[color=green]
> > 2) and actually what does it mean, that iterator returned from end()
> > points to "the element after the last one"? After my study of gcc
> > implementation of list this should just return the last one.[/color]
>
> Let's say that you have a list with the following contents:
> | 1 | 2 | 3 | ... | 8 | 9 |
>
> Calling myList.end() will return an iterator pointing not at 9, but at
> 9.next. This is to allow loops such as:
>
> for(iter=container.begin() ; iter!=container.end() ; ++iter)
> { /* ... */ }
>
> If end() returned an iterator to element 9, the body of the loop would
> not be executed for it since iter would equal end() before the
> iteration began and so execution would jump past the body.
>
>[color=green]
> > And begin() should return
> > LastElem->next which means the first one, as expected from this circular
> > list.[/color]
>
> While you're correct in thinking that most implementations of the STL
> use a circular list of sorts, it's not exactly what you want. Most of
> the time there is a blank throwaway node between the first and last
> element of the list. Going back to the list of no.s 1-9, the second
> through 8th elements behave as you'd think. However, 9.next does not
> point to 1; it points to the throwaway node, as does 1.prev. The
> throwaway's next and prev are set to 1 and 9 respectively.
>
> (The reason this is done is that it allows there to be no special end
> cases. If you implemented as a liner list directly, you'de have to
> check that prev and next weren't null before adjusting them.)
>
> I don't mean that this is how it's done in all implementations, but
> from what I know this is the typical one. It also doesn't necessarily
> mean that if you do
> iter = list.end(); ++iter;
> it will point to the first element, but that very possibly may happen.
>
>
> Now, why doesn't it make it a straight circular list you ask? As
> Victor said, linear lists are more often needed. Also, doing it as a
> striaght circular list would either break the loop above if you made
> end() point tao the last element, or break it for a different reason
> if you made end() point to the last element.next, because that woulb
> be the first element, so then you'd have iter==end() before the first
> iteration and the loop wouldn't run at all.
>
>[color=green]
> > Maybe I'm missing something important in my investigation process,[/color][/color]
please[color=blue][color=green]
> > help me.
> > A general question is:
> > Can I use the STL list (maybe after some modifications) as a circular
> > list, if not are there somewhere ready circular list libraries[/color][/color]
(compatible[color=blue][color=green]
> > with STL) or should I write one for myself from scratch?[/color]
>
> There are a couple possibilities, ranging from most flexible and
> hardest to least flexible and easiest. First, you can write a circular
> list class from scratch. Or you could write a circular list class with
> a stl::list as a back end. Finally, you could write just a new
> iterator for the list that holds a list::iterator and a pointer or
> reference to the container on increment checks to see if the
> iterator==the container's end and, if so, sets the iterator to the
> beginning.
>
> Evan[/color]
Here's an implementation of the last one, if it's any use (it's slightly
more flexible because you can cycle over a sublist of a std::list as well as
just over the whole thing):
// Untested
template <typename T>
class CircularSublistIterator
{
private:
typedef typename std::list<T>::iterator LIter; // I *think* typename is
needed here, but I don't have my templates book with me to check it :-)
LIter m_begin, m_end, m_it;
public:
CircularSublistIterator(const LIter& begin, const LIter& end, const
LIter& it)
: m_begin(begin),
m_end(end),
m_it(it)
{}
CircularSublistIterator& operator++()
{
++m_it;
if(m_it == m_end) m_it = m_begin;
return *this;
}
CircularSublistIterator operator++(int)
{
CircularSublistIterator old(*this);
++(*this);
return old;
}
operator LIter&()
{
return m_it;
}
};
Example Usage:
std::list<int> L;
....
for(CircularSublistIterator<int> CSI(L.begin(), L.end(), L.begin());
<terminating condition here>; ++CSI)
{
...
}
HTH,
Stuart.
