list container question

[kazio]

Hello,

So, I need to have double linked, circular list (last element point to the
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 it,
and when I increase (++) iterator pointing to the last element the program
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 so.
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 connection
between last and first element (LastElem->next == FirstElem and FirstElem->prev ==
LastElem), so I really don't understand:
1) why the iterator cannot go further after the last element
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. And begin() should return
LastElem->next which means the first one, as expected from this circular
list.
Maybe I'm missing something important in my investigation process, please
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 (compatible
with STL) or should I write one for myself from scratch?

Thank you very much

Kazimierz

 

[Victor Bazarov]

So, I need to have double linked, circular list (last element point to the
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 it,
and when I increase (++) iterator pointing to the last element the program
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 so.

Because a linear (not circular) list is more common and therefore
it makes more sense to have it in the library, I suppose. You
can ask for a better explanation in comp.std.c++, where the Standard
is discussed (why things are the way they are, what should be changed
in the language or why it shouldn't be changed, etc.)

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 connection
between last and first element (LastElem->next == FirstElem and FirstElem->prev ==
LastElem), so I really don't understand:
1) why the iterator cannot go further after the last element

Because there is nothing there, I believe. It's like walking off
the roof.

2) and actually what does it mean, that iterator returned from end()
points to "the element after the last one"?

That's just a term to make it analogous to arrays. After you
increment a pointer that pointed to the last element of an array,
the pointer points to the "element after the last one". The
actual element doesn't exist, of course, but the pointer is
considered valid for some operations (although you cannot
dereference it).

After my study of gcc implementation of list
this should just return the last one. And begin() should return
LastElem->next which means the first one, as expected from this circular
list.

"Should"? I think that most of programmer community will NOT
agree with you.

Maybe I'm missing something important in my investigation process, please
help me.

You're missing the fact that only you, only now, need the list
to be circular. Many of us don't.

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 (compatible
with STL) or should I write one for myself from scratch?

Write an adapter that would emulate the circularity of your list
using 'std::list' as its underlying container.

Victor

 

[Victor Bazarov]

or better yet ... write your own container that does it exactly the way
you want it.

How is it better? No, that's not a tease, I am really
interested to learn.

Victor

 

[Gianni Mariani]

How is it better? No, that's not a tease, I am really
interested to learn.

because you get exactly what you want ....

like I said.

 

[Victor Bazarov]

because you get exactly what you want ....

like I said.

You didn't have to repeat yourself. I read what you said.
However, what you said _implied_ that one cannot "get exactly"
what one wants by implementing an adapter. I would like to
know how implementing _everything_ yourself is better than
adapting a standard container. What cannot you "get exactly"
as you want by implementing an adapter?

Thank you.

Victor

 

[Gianni Mariani]

You didn't have to repeat yourself. I read what you said.
However, what you said _implied_ that one cannot "get exactly"
what one wants by implementing an adapter.

The cost of implementing an adaptor *may* outweight the cost of
implementing exactly what the OP wants.

There is nothing sacred about using std::list. (far from it actually).


I would like to

know how implementing _everything_ yourself is better than
adapting a standard container.

These words come from your mouth, not mine. You'd better explain
yourself ...

What cannot you "get exactly"

as you want by implementing an adapter?

And your agrument is ?

Not had your coffee this morning yet ?

If you're trying to make the assertion that everything that resembles a
list should use std::list then you know you're going to loose. The
answer is, "IT DEPENDS" and you know it. If you have a problem with my
suggestion, then I hope you have more scope to go with because given the
scope the OP presented is wide open. My comment was simply implying
that a list template class is a piece of cake and you have an option to
write the list class YOUR way. Perhaps my choice of the words "better
yet" stifles your scope of my argument; it's simply methaphoric for
"other possibly better options".

I'm sure there are jucier topics we can lock horns on. This one is
rather boring.

LOL

G

P.S. Yes, I have implemented a std::list replacement and I will likely
never use std::list again. But that's beside the point.

 

[Victor Bazarov]

[...]

With your permission I will leave your personal attacks
on my coffee drinking habits, and your vague statements
about scopes OP presented, and your boasting about using
your own implementation of a list instead of standard
template without a response. You apparently posted out
of boredom (by your own admission) and there is nothing
I like less than prolonging somebody else's discomfort.

Thanks.

Victor

 

[Gianni Mariani]

[...]

With your permission I will leave your personal attacks
on my coffee drinking habits, and your vague statements
about scopes OP presented, and your boasting about using
your own implementation of a list instead of standard
template without a response. You apparently posted out
of boredom (by your own admission) and there is nothing
I like less than prolonging somebody else's discomfort.

Thanks.

Victor

*PLONK*

 

[Evan]

Hello,

So, I need to have double linked, circular list (last element point to the
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 it,
and when I increase (++) iterator pointing to the last element the program
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 so.
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 connection
between last and first element (LastElem->next == FirstElem and FirstElem->prev ==
LastElem), so I really don't understand:
1) why the iterator cannot go further after the last element

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.

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.

And begin() should return
LastElem->next which means the first one, as expected from this circular
list.

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.

Maybe I'm missing something important in my investigation process, please
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 (compatible
with STL) or should I write one for myself from scratch?

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

 

[Stuart Golodetz]

kazio <[email protected]> wrote in message


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.



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.



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

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.