list container question

**Victor Bazarov** · Jul 19 '05, 03:18 PM

Re: list container question

"kazio" <pkurys@maja.il > wrote...[color=blue]
> 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.[/color]

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.)
[color=blue]
> 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[/color]
FirstElem->prev ==[color=blue]
> LastElem), so I really don't understand:
> 1) why the iterator cannot go further after the last element[/color]

Because there is nothing there, I believe. It's like walking off
the roof.
[color=blue]
> 2) and actually what does it mean, that iterator returned from end()
> points to "the element after the last one"?[/color]

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).
[color=blue]
> 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.[/color]

"Should"? I think that most of programmer community will NOT
agree with you.
[color=blue]
> Maybe I'm missing something important in my investigation process, please
> help me.[/color]

You're missing the fact that only you, only now, need the list
to be circular. Many of us don't.
[color=blue]
> 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?[/color]

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

Victor

**Victor Bazarov** · Jul 19 '05, 03:18 PM

Re: list container question

"Gianni Mariani" <gi2nospam@mari ani.ws> wrote...[color=blue]
> Victor Bazarov wrote:
>[color=green]
> >
> > Write an adapter that would emulate the circularity of your list
> > using 'std::list' as its underlying container.
> >[/color]
>
> or better yet ... write your own container that does it exactly the way
> you want it.[/color]

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

Victor

**Gianni Mariani** · Jul 19 '05, 03:18 PM

Re: list container question

Victor Bazarov wrote:[color=blue]
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote...
>[color=green]
>>Victor Bazarov wrote:
>>
>>[color=darkred]
>>>Write an adapter that would emulate the circularity of your list
>>>using 'std::list' as its underlying container.
>>>[/color]
>>
>>or better yet ... write your own container that does it exactly the way
>>you want it.[/color]
>
>
> How is it better? No, that's not a tease, I am really
> interested to learn.
>[/color]

because you get exactly what you want ....

like I said.

**Victor Bazarov** · Jul 19 '05, 03:18 PM

Re: list container question

"Gianni Mariani" <gi2nospam@mari ani.ws> wrote...[color=blue]
> Victor Bazarov wrote:[color=green]
> > "Gianni Mariani" <gi2nospam@mari ani.ws> wrote...
> >[color=darkred]
> >>Victor Bazarov wrote:
> >>
> >>
> >>>Write an adapter that would emulate the circularity of your list
> >>>using 'std::list' as its underlying container.
> >>>
> >>
> >>or better yet ... write your own container that does it exactly the way
> >>you want it.[/color]
> >
> >
> > How is it better? No, that's not a tease, I am really
> > interested to learn.
> >[/color]
>
> because you get exactly what you want ....
>
> like I said.[/color]

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** · Jul 19 '05, 03:18 PM

Re: list container question

Victor Bazarov wrote:[color=blue]
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote...
>[color=green]
>>Victor Bazarov wrote:
>>[color=darkred]
>>>"Gianni Mariani" <gi2nospam@mari ani.ws> wrote...
>>>
>>>
>>>>Victor Bazarov wrote:
>>>>
>>>>
>>>>
>>>>>Write an adapter that would emulate the circularity of your list
>>>>>using 'std::list' as its underlying container.
>>>>>
>>>>
>>>>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.
>>>[/color]
>>
>>because you get exactly what you want ....
>>
>>like I said.[/color]
>
>
> 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.[/color]

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[color=blue]
> know how implementing _everything_ yourself is better than
> adapting a standard container.[/color]

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

What cannot you "get exactly"[color=blue]
> as you want by implementing an adapter?
>[/color]

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** · Jul 19 '05, 03:18 PM

Re: list container question

"Gianni Mariani" <gi2nospam@mari ani.ws> wrote...[color=blue]
> [...][/color]

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** · Jul 19 '05, 03:19 PM

Re: list container question

Victor Bazarov wrote:[color=blue]
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote...
>[color=green]
>>[...][/color]
>
>
> 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
>
>[/color]
*PLONK*

**Evan** · Jul 19 '05, 03:19 PM

Re: list container question

kazio <pkurys@maja.il > wrote in message news:<Pine.BSF. 4.31L2.03071021 58220.94781-100000@novum.am .lublin.pl>...[color=blue]
> 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[/color]
[color=blue]
> 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=contai ner.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=blue]
> 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=blue]
> 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?[/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

**Stuart Golodetz** · Jul 19 '05, 03:19 PM

Re: list container question

Evan <eed132@psu.edu > wrote in message
news:3f25c666.0 307111125.685a9 163@posting.goo gle.com...[color=blue]
> kazio <pkurys@maja.il > wrote in message[/color]
news:<Pine.BSF. 4.31L2.03071021 58220.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=contai ner.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 CircularSublist Iterator
{
private:
typedef typename std::list<T>::i terator 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:
CircularSublist Iterator(const LIter& begin, const LIter& end, const
LIter& it)
: m_begin(begin),
m_end(end),
m_it(it)
{}

CircularSublist Iterator& operator++()
{
++m_it;
if(m_it == m_end) m_it = m_begin;
return *this;
}

CircularSublist Iterator operator++(int)
{
CircularSublist Iterator old(*this);
++(*this);
return old;
}

operator LIter&()
{
return m_it;
}
};

Example Usage:

std::list<int> L;
....
for(CircularSub listIterator<in t> CSI(L.begin(), L.end(), L.begin());
<terminating condition here>; ++CSI)
{
...
}

HTH,

Stuart.

list container question

list container question

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment