Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Best way to append std::list to itself

Reply
Thread Tools

Best way to append std::list to itself

 
 
James Kanze
Guest
Posts: n/a
 
      01-07-2011
On Jan 6, 9:52 pm, Ian Collins <(E-Mail Removed)> wrote:
> On 01/ 7/11 10:37 AM, Jorgen Grahn wrote:
> > On Thu, 2011-01-06, Paavo Helde wrote:
> >> Jorgen Grahn<(E-Mail Removed)> wrote in
> >>news:(E-Mail Removed) d:
> >>> Did *you* test it? How?


> >>> #include<list>
> >>> #include<iostream>
> >>> int main()
> >>> {
> >>> std::list<int> foo;
> >>> foo.push_back(1);
> >>> foo.push_back(2);
> >>> foo.push_back(3);
> >>> foo.insert(foo.end(), foo.begin(), foo.end());
> >>> for(std::list<int>::const_iterator i = foo.begin();
> >>> i!=foo.end(); ++i) {
> >>> std::cout<< *i<< '\n';
> >>> }
> >>> return 0;
> >>> }


> >>> In what way am I wrong? I see no infinite loop. On my system this
> >>> prints 1 2 3 1 2 3 and that's also what I'd expect.


> >> On my system this ate up some gigabytes of memory, then the whole system
> >> hung. Seems like nasal demons to me


> > What is your system? Mine is Linux and gcc, AMD64 and ppc.


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


> > I'm not saying you are mistaken or that your system has a bug; I just
> > want to know exactly what rule that code is violating. I found the
> > up-thread arguments unconvincing. (In particular, as you found out,
> > the suggestion "test it" was not helpful.)


> 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
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      01-07-2011
On Jan 7, 11:08 am, Marcel Müller <(E-Mail Removed)>
wrote:
> 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.

--
James Kanze
 
Reply With Quote
 
 
 
 
Spike
Guest
Posts: n/a
 
      01-07-2011
On 07/01/2011 12:58, James Kanze wrote:
>
> 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

--
http://www.econet-project.eu
 
Reply With Quote
 
Spike
Guest
Posts: n/a
 
      01-07-2011
On 07/01/2011 12:47, James Kanze wrote:
>
> 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

--
http://www.econet-project.eu
 
Reply With Quote
 
peter koch
Guest
Posts: n/a
 
      01-07-2011
On 7 Jan., 12:47, James Kanze <(E-Mail Removed)> wrote:
> On Jan 6, 6:28 pm, Jorgen Grahn <(E-Mail Removed)> wrote:
>
> > On Thu, 2011-01-06, Marcel M ller wrote:
> > > Yes, and according to the guarantees of std::list it will
> > > always point to one past the last element in the container.

>
> 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
 
Reply With Quote
 
Spike
Guest
Posts: n/a
 
      01-07-2011
On 07/01/2011 15:19, peter koch wrote:
> On 7 Jan., 12:47, James Kanze<(E-Mail Removed)> wrote:
>> 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.)
>>

> 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

--
http://www.econet-project.eu
 
Reply With Quote
 
Maxim Yegorushkin
Guest
Posts: n/a
 
      01-07-2011
On 07/01/11 11:58, James Kanze wrote:
> On Jan 7, 11:08 am, Marcel Müller<(E-Mail Removed)>
> wrote:
>> 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.

--
Max
 
Reply With Quote
 
Joshua Maurice
Guest
Posts: n/a
 
      01-11-2011
On Jan 7, 3:03*am, Marcel Müller <(E-Mail Removed)> wrote:
> "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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why doesn't python's list append() method return the list itself? dhruvbird Python 16 07-16-2010 05:40 PM
obtain element name, or attribute and value of the document name itself, and some elemnts and attributes from an ancestor or the node itself using xquery Jeff Kish XML 4 10-30-2008 05:47 PM
Best way to force a JComponent to repaint itself zerg Java 125 09-09-2008 01:14 AM
the address of list.append and list.append.__doc__ HYRY Python 10 09-26-2007 09:41 AM
Best way for -h option for script to run perldoc on itself? Ed Hennig Perl Misc 12 02-16-2006 10:27 PM



Advertisments