When is std::list more effective than the other containers?

[Niklas Norrthon]

Should not be a factor in considering using std::list instead of
std::vector

Except that once vector has reserved some memory it's not returned
to the memory manager until the entire vector is destroyed, while
memory used by a list node is returned as soon as that node is
erased.

If data needs to be frequently sorted, then consider using std::set or
std::map instead.

Except when data needs to be sorted in different ways each time.

Most experts, (like Herb Sutters and Scott Meyers) recommend using
std::vector as the default container.
The Official C++ standard also recommends using std::vector as the
default container.
In most container requirements, std::vector will out perform std::list.

I agree, use vector as the default container, but don't forget about
the alternatives, and their usage.

/Niklas Norrthon

 

[Niklas Norrthon]

not if you use pointers........

But then I have other problems, like ownership and lifetime
to worry about...

/Niklas Norrthon

 

[Alf P. Steinbach]

* Niklas Norrthon:

... once vector has reserved some memory it's not returned
to the memory manager until the entire vector is destroyed, while
memory used by a list node is returned as soon as that node is
erased.

You can (in practice) "compact" a vector by copying and swapping,
something like

template< typename T >
void compact( std::vector<T>& v )
{
std::vector<T> copy( v.size() );
copy.assign( v.begin(), v.end() );
v.swap( copy );
}

Disclaimer: untested code.

 

[Axter]

Wrong:

#include <vector>
using std::vector;

typedef vector<int> Vec;
typedef Vec::const_iterator Const_Iter;

int main()
{
/* first we set up things */
Vec foo;
foo.push_back(1);
foo.push_back(2);

/* get an iterator to after the last item of the vector: */
Const_iter last = foo.end();

/* now it's time to delete from the end of the vector */
foo.pop_back();

/* if pepp's statement had been correct the following
* would be ok, but last is invalidated by the pop_back
* and this is UB */

for (Const_Iter i = foo.begin(); i != last; ++i) {
/* do something here */
}
return 0;

Niklas Norrthon,
Exactly what was wrong?
Your code doesn't seem to prove anything related to my comment.
Are you sure you replied to the right post?

I stand my initial post, in the it's incorrect to say that "When you
delete anything from vector, all the iterators after that item must be
reassigned".
Because if you delete from the end, there are no more iterators after
that item.
Moreover, if you're using a std::deque, and you delete from the end or
beginning, you also don't have the reassignment issue.

 

[Axter]

But then I have other problems, like ownership and lifetime
to worry about...

You can fix ownership and lifetime problem by using smart pointers like
boost::shared_ptr, clone smart pointers, or COW smart pointers:
http://www.boost.org/libs/smart_ptr/shared_ptr.htm (boost::shared_ptr)
http://code.axter.com/copy_ptr.h (A clone smart pointer)
http://code.axter.com/cow_ptr.h (COW Copy On Write)

Don't try using auto_ptr on STL containers, because it's usage in
containers is not portable, and when fully implemented, not compilable.

 

[Diego Martins]

this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>(v).swap(v); }

chapter 17 - Effective STL - Scott Meyers

 

[roberts.noah]

a) A vector is not just "almost" guaranteed to be contiguous. It is
contiguous. The standard implies that.

Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. Frankly I don't agree; if a vector
could be better made non-contiguous then it doesn't bother me one bit
so long as it appears to be to me (assuming I don't try direct access
to the memory *p = &vect[0]).

 

[roberts.noah]

(e-mail address removed) wrote:

As a contractor, I've worked in many locations, and it's been my
experience when finding std::list used in code, that 9 out of 10 times,
std::list is being used inappropriately, and std::vector or std::deque
would have done the same job faster.

I'm sorry but I just don't buy your "credentials". Anyone that would
call that dynamic_array class of yours an example of how TO do
something doesn't meet my requirements of an expert. Judging by the
single code example I have seen from you I am not at all impressed.

 

[Alf P. Steinbach]

* Diego Martins:

this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>(v).swap(v); }

chapter 17 - Effective STL - Scott Meyers

A too smart implementation is free, I believe, to simply not copy
anything here, and with no actual copying, no memory usage reduction.

 

[Kai-Uwe Bux]

Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

From the standard:

[23.2.4/1]

[...] The elements of a vector are stored contiguously, meaning that if v is
a vector<T, Allocator> where T is some type other than bool, then it obeys
the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. [snip]

That book seems to be outdated.


Best regards

Kai-Uwe Bux

 

[Axter]

a) A vector is not just "almost" guaranteed to be contiguous. It is
contiguous. The standard implies that.

Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. Frankly I don't agree; if a vector
could be better made non-contiguous then it doesn't bother me one bit
so long as it appears to be to me (assuming I don't try direct access
to the memory *p = &vect[0]).

You should use the Official C++ standard to determine required behavior
for STL objects.
The official standard clearly states that vector is garanteed to be
contiguous, and the original standard is over six years old.

I recommend you moved to more up-todate and more accurate books like
that of Sutters and Meyers.
Bruce Eckel's Thinking in C++ book is more of a beginners book, as you
can see it's listed in beginner's c++ link:
http://www.accu.org/bookreviews/public/reviews/0sb/beginner_s_c__.htm

Consider using the following pool of books instead:
http://www.accu.org/bookreviews/public/reviews/0sb/advanced_c__.htm

 

[Kai-Uwe Bux]

a) A vector is not just "almost" guaranteed to be contiguous. It is
contiguous. The standard implies that.

Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. Frankly I don't agree; if a vector
could be better made non-contiguous then it doesn't bother me one bit
so long as it appears to be to me (assuming I don't try direct access
to the memory *p = &vect[0]).

You should use the Official C++ standard to determine required behavior
for STL objects.
The official standard clearly states that vector is garanteed to be
contiguous, and the original standard is over six years old.

I think, this guarantee was added in the second edition of the standard from
2003. As a side note: the slightly outdated FAQ item [34.3] claims that the
guarantee still had the status of a technical corrigendum to the standard.


Best

Kai-Uwe Bux

 

[Axter]

Kai-Uwe Bux wrote:

a) A vector is not just "almost" guaranteed to be contiguous. It is
contiguous. The standard implies that.

Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. Frankly I don't agree; if a vector
could be better made non-contiguous then it doesn't bother me one bit
so long as it appears to be to me (assuming I don't try direct access
to the memory *p = &vect[0]).

You should use the Official C++ standard to determine required behavior
for STL objects.
The official standard clearly states that vector is garanteed to be
contiguous, and the original standard is over six years old.

I think, this guarantee was added in the second edition of the standard from
2003. As a side note: the slightly outdated FAQ item [34.3] claims that the
guarantee still had the status of a technical corrigendum to the standard.

I just took a look at the original 1998 C++ standard, and much to my
surprise it was not in there (or at least I couldn't find it).
I guess you're right. It's been added in the 2003 version.

 

[deane_gavin]

You should use the Official C++ standard to determine required behavior
for STL objects.
The official standard clearly states that vector is garanteed to be
contiguous, and the original standard is over six years old.

I think, this guarantee was added in the second edition of the standard from
2003. As a side note: the slightly outdated FAQ item [34.3] claims that the
guarantee still had the status of a technical corrigendum to the standard.

I just took a look at the original 1998 C++ standard, and much to my
surprise it was not in there (or at least I couldn't find it).
I guess you're right. It's been added in the 2003 version.

Yep, you couldn't find it because it wasn't there in the 1998 standard.
I read an article a while ago somewhere by Herb Sutter saying that in
practice you could assume vectors were contiguous anyway because the
pratice of implementing them that way was so widespread.

By the way, do you know if the 2003 standard is available in handy
cheap electronic format like the last one was?

Gavin Deane

 

[Niklas Norrthon]

My point is that all the iterators after the deleted item are invalidated
even when you delete from the end of a vector. The member functions
vector::end() and vector::rbegin() return iterators to one past the
end of the vector, and all such iterators are invalidated by
vector:op_back(), which is what I tried to illustrate with the
code example:

Your code doesn't seem to prove anything related to my comment.
Are you sure you replied to the right post?

The code stores the result of vector::end(), and then tries to use
that iterator after a call to vector:op_back().

I stand my initial post, in the it's incorrect to say that "When you
delete anything from vector, all the iterators after that item must be
reassigned".
Because if you delete from the end, there are no more iterators after
that item.

So what does vector::end() return then?

Moreover, if you're using a std::deque, and you delete from the end or
beginning, you also don't have the reassignment issue.

Same issues with deque::end() as with vector::end(). And with deque
there is a similar issue with begin():

#include <deque>
using std::deque;

int main()
{
std::deque d;

d.push_back(1);
d.push_back(2);

std::deque::const_iterator iter = d.begin();
*iter = 13; // ok
d.pop_front();

*iter = 42; // error iter is invalidated by pop_front
return 0;
}

/Niklas Norrthon

 

[Niklas Norrthon]

this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>(v).swap(v); }

chapter 17 - Effective STL - Scott Meyers

Ok lets analyze this...

For simplicity, let's get rid of the template stuff, and
assume vector<int>, then we have:

void compact( std::vector<int>& v )
{
std::vector<int>(v).swap(v);
}

The above first creates a temporary, using copy constructor, and
then call swap. The same a bit more explicit:

void compact( std::vector<int>& v )
{
std::vector<int> tmp(v);
tmp.swap(v);
}

A typical implementation of vector's copy constructor
(simplified not using allocators):

vector<int>::vector(const vector<int>& x) :
data(new int[x.reserved]),
reserved(x.reserved),
sz(x.sz)
{
std::copy(x.begin(), x.end(), data)
}

There is nothing in the specification of vector, that
prevents the copy constructor from reserving the same amount
of memory as the source vector.

/Niklas Norrthon

 

[Axter]

My point is that all the iterators after the deleted item are invalidated
even when you delete from the end of a vector. The member functions
vector::end() and vector::rbegin() return iterators to one past the
end of the vector, and all such iterators are invalidated by
vector:op_back(), which is what I tried to illustrate with the
code example:

I don't see the point been relevant, or important for this particular
discussion. How does that help in deciding which container to use?
In general, when it's ever possible for the container to change, you
should not store the value of vector::end() and/or vector::rbegin()

 

[Axter]

Axter wrote:
You should use the Official C++ standard to determine required behavior
for STL objects.
The official standard clearly states that vector is garanteed to be
contiguous, and the original standard is over six years old.

I think, this guarantee was added in the second edition of the standard from
2003. As a side note: the slightly outdated FAQ item [34.3] claims that the
guarantee still had the status of a technical corrigendum to the standard.

I just took a look at the original 1998 C++ standard, and much to my
surprise it was not in there (or at least I couldn't find it).
I guess you're right. It's been added in the 2003 version.

Yep, you couldn't find it because it wasn't there in the 1998 standard.
I read an article a while ago somewhere by Herb Sutter saying that in
practice you could assume vectors were contiguous anyway because the
pratice of implementing them that way was so widespread.

By the way, do you know if the 2003 standard is available in handy
cheap electronic format like the last one was?

When I purchased the electronic version of the 2003 standard, I notice
that there were two separate sources to purchase it, and one source had
a high ridiculous price, and the second source had a more reasonable
price, but even the reasonable price source was much higher then the
price of the original 98 standard.
I forgot the links, because it's been a while now, but I believe one
link was associated with ANSI and the other was associated with ISO.

 

[Neil Cerutti]

this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>(v).swap(v); }

chapter 17 - Effective STL - Scott Meyers

Ok lets analyze this...

For simplicity, let's get rid of the template stuff, and
assume vector<int>, then we have:

void compact( std::vector<int>& v )
{
std::vector<int>(v).swap(v);
}

The above first creates a temporary, using copy constructor, and
then call swap. The same a bit more explicit:

void compact( std::vector<int>& v )
{
std::vector<int> tmp(v);
tmp.swap(v);
}

A typical implementation of vector's copy constructor
(simplified not using allocators):

vector<int>::vector(const vector<int>& x) :
data(new int[x.reserved]),
reserved(x.reserved),
sz(x.sz)
{
std::copy(x.begin(), x.end(), data)
}

There is nothing in the specification of vector, that prevents
the copy constructor from reserving the same amount of memory
as the source vector.

Nothing prevents a standard compliant implementation from always
reserving 100,000,000*size(T) bytes for each vector, either, but
mostly we don't need to worry about that unless the vendor of our
compiler is named Snidely Wiplash. ;-)

On the other hand, the constructor that takes iterators cannot
clone the capacity, even if Snidely Wiplash wanted to, since it's
not accessible.

void compact( std::vector<int>& v )
{
std::vector<int> tmp(v.begin(), v.end());
tmp.swap(v);
}

 

[roberts.noah]

Yep, you couldn't find it because it wasn't there in the 1998 standard.
I read an article a while ago somewhere by Herb Sutter saying that in
practice you could assume vectors were contiguous anyway because the
pratice of implementing them that way was so widespread.

By the way, do you know if the 2003 standard is available in handy
cheap electronic format like the last one was?

I *just* got a dead tree version from bookpool for about $50 (I hope
it's the newer one anyway, don't know because it isn't right here with
me - in a box of stuff I dug out of my wreck of a car after the
accident). I based my former statements on an apparently outdated book
but still very good book. He also stated that you could make the
assumption but based it more on the assumption that the standard
indicated an interface that could really only be implemented with
contiguious memory.