Best way to append std::list to itself

[equation .]

Hi,

what is the best way to insert the contents of std::list to the end of
the
same list? I haven't used C++ much recently (actually, in quite some
time)
and I can't tell if there's a much simpler way to achieve the
following
(the appending functionality - this is just an example) - assuming
it's
correct and portable and not just happening to work on my system.

#include <list>

struct A {
std::list<type> list;

void append(const std::list<type>& other)
{
if (&list != &other) {
list.insert(list.end(), other.begin(), other.end());
} else if (!list.empty()) {
std::list<type>::iterator end = list.end();
--end;
list.insert(list.end(), list.begin(), end);
list.push_back(*end);
}
}
};

 

[Maxim Yegorushkin]

Hi,

what is the best way to insert the contents of std::list to the end of
the
same list? I haven't used C++ much recently (actually, in quite some
time)
and I can't tell if there's a much simpler way to achieve the
following
(the appending functionality - this is just an example) - assuming
it's
correct and portable and not just happening to work on my system.

#include<list>

struct A {
std::list<type> list;

void append(const std::list<type>& other)
{
if (&list !=&other) {
list.insert(list.end(), other.begin(), other.end());
} else if (!list.empty()) {
std::list<type>::iterator end = list.end();
--end;
list.insert(list.end(), list.begin(), end);
list.push_back(*end);
}
}
};

The one line you posted:

list.insert(list.end(), other.begin(), other.end());

Should do the trick regardless whether list and other are the same object.

 

[Marcel Müller]

The one line you posted:

list.insert(list.end(), other.begin(), other.end());

Should do the trick regardless whether list and other are the same object.

I would not bet so. List iterators stay valid on insertion but this
implies that if other.end() points after the end of the list this should
always be the same regardless of the insertions. So you finally end up
with an infinite loop because the rage [other.begin(),other.end[ is
extended by the insert.

The only simplification I can see is that the OP always might choose the
second implementation. This reduces complexity and improves the code
coverage.

void append(const std::list<type>& other)
{
if (!list.empty()) {
std::list<type>::iterator end = list.end();
--end;
list.insert(list.end(), list.begin(), end);
list.push_back(*end);
}
}


Marcel

 

[Jorgen Grahn]

I.e. list.insert(list.end(), list.begin(), list.end()) should work.

I would not bet so. List iterators stay valid on insertion but this
implies that if other.end() points after the end of the list this should
always be the same regardless of the insertions.

Huh? other.end() doesn't point after the end of the list -- it *is* the
end of the list.

So you finally end up
with an infinite loop because the rage [other.begin(),other.end[ is
extended by the insert.

In the original example, other.end() is evaluated once (just like any
other expression). The range is not extended by anything, and there
is no infinite loop.

/Jorgen

 

[Ulrich Eckhardt]

what is the best way to insert the contents of std::list to the end of
the same list?

Define "best".

std::list<type> list;

void append(const std::list<type>& other)
{
if (&list != &other) {
list.insert(list.end(), other.begin(), other.end());
} else if (!list.empty()) {
std::list<type>::iterator end = list.end();
--end;
list.insert(list.end(), list.begin(), end);
list.push_back(*end);
}
}

There is both a simpler and better way. You first copy the list and then
you use list::slice() to append it. Reasons this is better:
1. less typing (2 lines)
2. exception-safety (I'm not 100% sure you get that with insert).
3. no need to check for self-appending (I'm not sure it's necessary
anyway)


Cheers!

Uli

 

[equation .]

The one line you posted:

     list.insert(list.end(), other.begin(), other.end());

Should do the trick regardless whether list and other are the same object..

I was pretty sure I tried that at first - and try as I might, it leads
to infinite loop (and quite a memory usage) on my compiler (i.e.
list.insert(list.end(), list.begin(), list.end()) does not work).
Perhaps there's a bug in my STL, in which case there's little reason
to discuss about workarounds in this group.

Copy-and-splice seems 'best' for now. I thought about it at first, and
now that I look at things, it's better than the hackish (i.e.
not-'good') version I posted.

 

[Michael Doubez]

Hi,

what is the best way to insert the contents of std::list to the end of
the
same list? I haven't used C++ much recently (actually, in quite some
time)
and I can't tell if there's a much simpler way to achieve the
following
(the appending functionality - this is just an example) - assuming
it's
correct and portable and not just happening to work on my system.

[snip]

I don't know about the best way but a way is to append it to the front
(you get the same result). This can be achieved with a one liner:

std::copy(list.begin(),list.end(),std::front_inserter(list));

 

[Michael Doubez]

what is the best way to insert the contents of std::list to the end of
the
same list? I haven't used C++ much recently (actually, in quite some
time)
and I can't tell if there's a much simpler way to achieve the
following
(the appending functionality - this is just an example) - assuming
it's
correct and portable and not just happening to work on my system.

[snip]

I don't know about the best way but a way is to append it to the front
(you get the same result). This can be achieved with a one liner:

std::copy(list.begin(),list.end(),std::front_inserter(list));

Oups, I mean:

std::copy(list.begin(),list.end(),std::inserter(list,list.begin()));

 

[Marcel Müller]

I.e. list.insert(list.end(), list.begin(), list.end()) should work.


Huh? other.end() doesn't point after the end of the list -- it *is* the
end of the list.

Nope.

"a.end() Returns an iterator pointing one past the last element in the
container."

So you finally end up
with an infinite loop because the rage [other.begin(),other.end[ is
extended by the insert.

In the original example, other.end() is evaluated once (just like any
other expression).

Yes, and according to the guarantees of std::list it will always point
to one past the last element in the container. Regardless of the
insertions at the end.

The range is not extended by anything, and there
is no infinite loop.

Wrong!

Simply test it.


Marcel

 

[Juha Nieminen]

std::list<type>::iterator end = list.end();
--end;
list.insert(list.end(), list.begin(), end);
list.push_back(*end);

std::list<type> copy(list);
list.splice(list.end(), copy);

 

[Jorgen Grahn]

Nope.

"a.end() Returns an iterator pointing one past the last element in the
container."

In other words, the end of the list. Do you perhaps think of "the end
of the list" as "the last valid element of the list"?

So you finally end up
with an infinite loop because the rage [other.begin(),other.end[ is
extended by the insert.

In the original example, other.end() is evaluated once (just like any
other expression).

Yes, and according to the guarantees of std::list it will always point
to one past the last element in the container. Regardless of the
insertions at the end.

The range is not extended by anything, and there
is no infinite loop.

Wrong!

Simply test it.

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.

/Jorgen

 

[Ulrich Eckhardt]

I don't know about the best way but a way is to append it to the front
(you get the same result). This can be achieved with a one liner:

std::copy(list.begin(),list.end(),std::front_inserter(list));

Oups, I mean:

std::copy(list.begin(),list.end(),std::inserter(list,list.begin()));

I'll throw in

list.insert(list.begin(), list.begin(), list.end());
copy(list.rbegin(), list.rend(), front_inserter(list));

The iterator to the currently first element doesn't move like the past-
the-end iterator, so you should be able to insert at the front.



Uli

 

[Jorgen Grahn]

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.

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.)

/Jorgen

 

[Ian Collins]

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.

 

[Paul Brettschneider]

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

Actually, I would have expected that the program loops for ever. But
possibly only because of my preconception that end() is implemented as a
fixed sentinel node or simply by NULL.

What if foo is a std::vector? Undefined behaviour because the first
insertion possibly invalidates all iterators or is it guaranteed to work
with self insert?

 

[Paul Brettschneider]

Actually, I would have expected that the program loops for ever. But
possibly only because of my preconception that end() is implemented as a
fixed sentinel node or simply by NULL.

What if foo is a std::vector? Undefined behaviour because the first
insertion possibly invalidates all iterators or is it guaranteed to work
with self insert?

I just had a look at the g++ implementation of _M_range_insert and it
handles the situation gracefully: the old memory is only freed after
performing the copy. The question remains: QOI or mandated?

 

[Paul Brettschneider]

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.

Actually, g++/libstdc++ std::list<T>::insert() does what others in this
thread have suggested - first copy, then splice (I hope it is OK to post GPL
code excerpts?):
template<typename _InputIterator>
void
insert(iterator __position, _InputIterator __first,
_InputIterator __last)
{
list __tmp(__first, __last, _M_get_Node_allocator());
splice(__position, __tmp);
}

Looks inherently sensible although I cannot say if this is standards
conformant. I guess the Sun/Microsoft implementations use some kind of loop
where end() is reevaluated after inserting every element. The g++ version
seems to make more sense.

 

[Marcel Müller]

In other words, the end of the list. Do you perhaps think of "the end
of the list" as "the last valid element of the list"?

Yes. That is what I would call "the end of the list" from the human
language point of view.

Did *you* test it? How?

Yes. But first I had a look into stl_list.h. At this point I was already
sure that it would fail.

#include <list>
using namespace std;
int main()
{ list<int> l;
l.push_back(7);
l.insert(l.end(), l.begin(), l.end());
return 0;
}

Compiled with gcc on OS/2. It runs a split second and then terminates
abnormally, most likely with std::bad_alloc. (Thanks to swap on SSD!)


The interesting question is, if we are in the land of undefined behavior
or if either implementation is wrong?

"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().
But note 3 tells something contrary:

"A similar property holds for all versions of insert() and erase().
List<T, Alloc>::insert() never invalidates any iterators, ..."

However, /if/ list.end() is still valid after insertion (I guess this is
true) it will always point to the end. So the question is whether the
comparison against the upper limit of the range is /before or after/ the
actual insertions take place. So we have a dependency of the execution
sequence and I see no sequence point that would give them a defined order.

I finally say it is UB.


Marcel

 

[Marcel Müller]

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

No.

The question is when the comparison to the iterator returned by
foo.end() takes place. /Before or after/ an insertion has actually taken
place.

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. The range
[begin(), end()[ /is/ modified by the insert operation for sure.


Marcel

 

[James Kanze]

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.)

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.

In this particular case, I wouldn't expect anything. The
standard states that for a.insert(p, i, j) (regardless of the
container type, see table 67), there is a precondition that
i and j are not iterators into a. You've violated
a precondition, so the results are undefined behavior. In
a good implementation, I would expect the equivalent of an
assertion failure. (None that I have access to do detect this
error, however. Even though they can make the connection
between iterator and the associated container; e.g. they
complain if the first iterator into the assert isn't an iterator
into foo.)

The question still remains concerning my first example. If
I then do:
for (std::list<char>::iterator j = l.begin(); j != i; ++ j)
std::cout << *j;
, how many characters do I output. Both of the compilers
I have access to output "abcd". Even though with the code using
insert, one goes into an infinite loop (until running out of
memory), and the other generates "123123".