Best way to append std::list to itself

[James Kanze]

Interesting. Compiled with gcc, the code terminates with the 'expected'
output. With Sun CC, it loops forever.

The problem is probably how foo.end() is calculated.

Or how it is used inside insert. I can imagine that some
implementations first create the list to be inserted, then
splice it in (which gives "123123"), others insert one element
at a time (which results in an infinite loop if the end iterator
actually points to a "virtual" element guaranteed to be at the
end---a frequent implementation).

An implementation is free to use either, since it can assume
that the second and third iterators are not iterators into foo
(because this is a precondition for insert).

Just curious: but what would you "expect" as the behavior if the
first iterator were foo.begin() + 1 (i.e. into the middle of the
list being inserted)?

 

[James Kanze]

Ian Collins wrote:

[...]

foo.end() will /always/ point past the last element of the
list and not past an element that have been the last one at
some time ago.

Could you point out the text which makes you think so. (The
implementations I have access to behave this way, but I can't
find anything one way or the other in the standard.)

foo.end() returns an iterator which points to one past the last
element. That's all I can find in the standard. Thus, if the
last element were 3, it points to the element after the element
3. Should this change when the list is modified? The standard
really doesn't say, or at least, I can't find where it says one
way or the other.

 

[Spike]

>
foo.end() returns an iterator which points to one past the last
element. That's all I can find in the standard. Thus, if the
last element were 3, it points to the element after the element
3. Should this change when the list is modified? The standard
really doesn't say, or at least, I can't find where it says one
way or the other.

ISO/IEC 14882:2003(E):

23.1 - Container requirements:

[...]

7 [...] end() returns an iterator which is the past-the-end value for
the container. [...]

I think this is very clear and unambiguous.

SM

 

[Spike]

>
That's an interesting assertion. I don't think that the
standard is clear here: does the end iterator point to one past
the last element, always, or does it point to one past the last
element when it was called. I.e.:

std::list<char> l;
l.push_back('a');
l.push_back('b');
l.push_back('c');
std::list<char>::iterator i = l.end();
// i points to one past the element 'c'
l.push_back('d');
// i points to one past the element 'c'?
// or one past the new last element.

I don't think that the standard is really clear here. (I don't
think it's an issue for other containers---in vector, for
example, insertion invalidates any iterators behind the point of
insertion, and thus, any end iterator.)

See my other post.

SM

 

[peter koch]

That's an interesting assertion.  I don't think that the
standard is clear here: does the end iterator point to one past
the last element, always, or does it point to one past the last
element when it was called.  I.e.:

    std::list<char> l;
    l.push_back('a');
    l.push_back('b');
    l.push_back('c');
    std::list<char>::iterator i = l.end();
    //  i points to one past the element 'c'
    l.push_back('d');
    //  i points to one past the element 'c'?
    //  or one past the new last element.

I don't think that the standard is really clear here.  (I don't
think it's an issue for other containers---in vector, for
example, insertion invalidates any iterators behind the point of
insertion, and thus, any end iterator.)

[snip]
Interesting subject. You are not entirely right, as the iterators will
stay valid so long as the vector has sufficient capacity.

/Peter


/Peter

 

[Spike]

Interesting subject. You are not entirely right, as the iterators will
stay valid so long as the vector has sufficient capacity.

23.2.4.3:

1 [...] If no reallocation happens, all the iterators and references
before the insertion point remain valid. [...]

So, James is right.

SM

 

[Maxim Yegorushkin]

Ian Collins wrote:
[...]
foo.end() will /always/ point past the last element of the
list and not past an element that have been the last one at
some time ago.

Could you point out the text which makes you think so. (The
implementations I have access to behave this way, but I can't
find anything one way or the other in the standard.)

foo.end() returns an iterator which points to one past the last
element. That's all I can find in the standard. Thus, if the
last element were 3, it points to the element after the element
3. Should this change when the list is modified? The standard
really doesn't say, or at least, I can't find where it says one
way or the other.

A list iterator becomes invalid only after the element it points to has
been erased. Therefore, list.end() must never change since there is no
way to remove list.end() element.

 

[Joshua Maurice]

"Lists have the important property that insertion and splicing do not
invalidate iterators to *list elements,* and that even removal
invalidates only the iterators that point to the elements that are removed."

This would explicitly exclude list.end().

I remember some discussion recently about this topic. IIRC: Something
to do with swapping lists, and if this should swap their allocator
instances if unequal. Specifically, it came up in conversation that
while all of the iterators to the elements are swapped between the
lists, the end-iterators are not swapped. Thus I think your reasoning
is incorrect, at least from the judgments of that other thread.

The "one past the end" iterator is not an iterator to an element. It's
special.

Having said that, I'm not exactly sure what the standard mandates in
this case. It's quite interesting to think about.