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

Axter wrote:

Josh Mcfarlane wrote:
Just out of curiosity:

When would using std::list be more efficient / effective than using
other containers such as vector, deque, etc?

As far as I'm aware, list doesn't appear to be specialized for
anything.

Thanks,
Josh McFarlane
You should use vector as your default container.

Normally, std::list is rarely the best choice. In most requirements,
std::list will perform worse, or the same as std::vector.

You should consider using std::list if you have a requirement that
performs many inserts and/or deletes from the center of the container.

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
*almost* guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

However, because of the lack of a random access iterator it can still
be more efficient to use a vector if you need random access. If you
are just running the whole list every time you access it then a list is
a very efficient implementation unless you know ahead of time exactly
how big to make your vector (or at least a good usual upper bound).
If you only perform a few insertions and/or deletions from the center,
then you should still prefer to use std::vector or std::deque.

Sorting requirements should not be a motivating factor for using
std::list, because you're more then likely using the wrong set of
containers if you have a (repeat) sorting requirement.
Not only that, but because std::list doesn't have a random access
iterator sorting a list will be considerably slower than a
vector...most of the time. There are rare cases when it might not be,
but usually you will find sort to work faster with a random access than
without.
If you have a requirement that needs to do a lot of sorting, then you
should consider using std::map or std::set instead.

In general, std::list should be your least used container.

I don't agree. Every container serves a particular purpose. It could
be that in YOUR case most development domains seem to be least served
by the list container there are certainly a lot of cases when a list is
a very appropriate choice. The best thing is to understand the
implementations of the different containers and where those kind of
algorithms are best used. Take a class or read a book on data
structures and implement your own list, vector, map, etc...and then you
will be able to understand their value and when to use what.

Dec 12 '05 #10

Axter

roberts.n...@gmail.com wrote:

Axter wrote:
Josh Mcfarlane wrote:
Just out of curiosity:

When would using std::list be more efficient / effective than using
other containers such as vector, deque, etc?

As far as I'm aware, list doesn't appear to be specialized for
anything.

Thanks,
Josh McFarlane

You should use vector as your default container.

Normally, std::list is rarely the best choice. In most requirements,
std::list will perform worse, or the same as std::vector.

You should consider using std::list if you have a requirement that
performs many inserts and/or deletes from the center of the container.

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
*almost* guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

However, because of the lack of a random access iterator it can still
be more efficient to use a vector if you need random access. If you
are just running the whole list every time you access it then a list is
a very efficient implementation unless you know ahead of time exactly
how big to make your vector (or at least a good usual upper bound).

If you only perform a few insertions and/or deletions from the center,
then you should still prefer to use std::vector or std::deque.

Sorting requirements should not be a motivating factor for using
std::list, because you're more then likely using the wrong set of
containers if you have a (repeat) sorting requirement.

Not only that, but because std::list doesn't have a random access
iterator sorting a list will be considerably slower than a
vector...most of the time. There are rare cases when it might not be,
but usually you will find sort to work faster with a random access than
without.
If you have a requirement that needs to do a lot of sorting, then you
should consider using std::map or std::set instead.

In general, std::list should be your least used container.

I don't agree. Every container serves a particular purpose. It could
be that in YOUR case most development domains seem to be least served
by the list container there are certainly a lot of cases when a list is
a very appropriate choice. The best thing is to understand the
implementations of the different containers and where those kind of
algorithms are best used. Take a class or read a book on data
structures and implement your own list, vector, map, etc...and then you
will be able to understand their value and when to use what.

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.

IMHO, std::list is one of the most misused STL containers. You often
find programmers that transfer from programming in C to programming in
C++ to use std::list as there default container, because they're use to
using link list in their old C language code.

I'm not saying you should never use std::list. I'm just saying (in
general), that it's rarely the best choice.

Dec 12 '05 #11

ro**********@gmail.com wrote:

Axter wrote:
Josh Mcfarlane wrote:
> Just out of curiosity:
>
> When would using std::list be more efficient / effective than using
> other containers such as vector, deque, etc?
>
> As far as I'm aware, list doesn't appear to be specialized for
> anything.
>
> Thanks,
> Josh McFarlane

You should use vector as your default container.

Normally, std::list is rarely the best choice. In most requirements,
std::list will perform worse, or the same as std::vector.

You should consider using std::list if you have a requirement that
performs many inserts and/or deletes from the center of the container.

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
*almost* guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

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

b) Even accounting for reallocations, appending an item to a vector is
guaranteed to be amortized constant time. Whether vector (accounting for
reallocations) or list is more efficient has to be decided by measurement.
In my experience, for small typesize, vector always beats list:

#include <ctime>
#include <vector>
#include <list>
#include <iostream>

class timer {
private:

std::clock_t ticks;

public:

timer ( void )
: ticks ( std::clock() )
{}

std::clock_t passed ( void ) const {
return( std::clock() - ticks );
}

double seconds ( void ) const {
return( double( this->passed() ) / CLOCKS_PER_SEC );
}

}; // timer

class print_timer {
private:

std::ostream & o_str;
std::string banner;
timer watch;

public:

print_timer ( std::ostream & str, std::string msg = std::string() )
: o_str ( str )
, banner ( msg )
, watch ()
{}

~print_timer ( void ) {
o_str << banner << " " << watch.seconds() << "sec" << '\n';
}

}; // print_timer
template < template <class> class cont >
void allocate ( cont<unsigned long> & i_cont,
unsigned long length ) {
print_timer dummy ( std::cout );
for ( unsigned long i = 0; i < length; ++i ) {
i_cont.push_back( i );
}
}

int main ( void ) {
std::list< unsigned long > l_list;
//std::vector< unsigned long > l_list;
allocate( l_list, 10000000 );
std::cout << l_list.back() << '\n';
}

On my machine, vector<unsigned long> beats list<unsigned long> by a factor
of 6; and you bet that the vector was reallocated several times.

So, for a sequence of, say, pointers the concern about reallocation is not
justified. For bigger objects, however, you may have a point. As I said,
this should be left to measurements.
Best

Kai-Uwe Bux

Dec 12 '05 #12

>It's optimized for insertions and sorting. Since the

order of elements is based on links, elements don't
have to be moved to sort or insert, which drastically
speeds those processes. Try doing that with a vector! Oh, lordy...
You'd need to move thousands of bytes of data around,
possibly repeatedly re-allocating huge memory blocks.
Very inefficient.

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

Dec 12 '05 #13

Greg

Kai-Uwe Bux wrote:

ro**********@gmail.com wrote:
On my machine, vector<unsigned long> beats list<unsigned long> by a factor
of 6; and you bet that the vector was reallocated several times.

So, for a sequence of, say, pointers the concern about reallocation is not
justified. For bigger objects, however, you may have a point. As I said,
this should be left to measurements.

All the items would have to be appended to the very end of the
container for a vector to stand any chance of being faster than a list
at insertion. And as soon as any insertions have to be performed any
where else within the container, the performance characteristics of a
vector start to fall fall off a cliff.

Consider revising your benchmark to compare a std::list vs. a
std::vector when insertions are made at the the head of the container.
Here's the change:

for ( unsigned long i = 0; i < length; ++i ) {
i_cont.insert(cont.begin(), i );
}

How much faster will the std::list be than the std::vector when
inserting items at the beginning according to this benchmark? 6 times?
60? 600?

Probably more like 5,000,000. The time it takes to fill the list will
be approximately the same in either benchmark, while the time it takes
the vector would increase quite a bit more. If it takes 5 seconds to
fill the vector when appending 10 million items to its end, it would
take about 9 months(!) of dedicated computer time to do the same when
when all items are inserted at the beginning (though I lost patience
when I tried to time the benchmark just now).

So whatever edge a vector may have over a list when inserting items in
the ideal case, is by no means comparable to the edge that the list has
over a vector in the worst case. So unless all the insertions will be
at the end, I would choose a list over a vector, just to be on the safe
side.

Greg

Dec 13 '05 #14

Jerry Coffin

Josh Mcfarlane wrote:

Just out of curiosity:

When would using std::list be more efficient / effective than using
other containers such as vector, deque, etc?

As far as I'm aware, list doesn't appear to be specialized for
anything.

There are a few situations in which std::list is quite useful, but they
are pretty rare.

About the only time it works out well is when the task involves a (or
more than one) semi-permanent "cursor" that maintains a current
position in the list, and you do a lot of inserting/deleting at that
point (which hopefully doesn't change very often, except maybe by one
item at a time).

Otherwise, the list will normally lose -- in particular, even though
inserting/deleting in the middle of the list is constant complexity,
getting TO that spot in the list is linear. For a constrasting example,
consider storing items in a tree, in which case you can find a spot
with roughly log2(N) complexity, and insert or delete in about the
same. These operations will typically have somewhat higher constants,
but the complexity reduction is so great that it'll still win over
anything but quite a short/small list.

If you really expect your list to remain quite small, you're probably
better off with a deque or vector. These reverse the shortcomings of a
list: searching has low complexity, but insertion/deletion in the
middle are linear. The difference is in the constants: vectors (for
example) use contiguous memory, so they're much more cache friendly,
and give much lower per-operation constants as a general.rule.

It might seem right off that there should be some middle ground: that a
vector/deque would be best for a really small number of items, and a
tree for a really large number of items, but a list would be best
somewhere in the middle. My experience is the opposite: lists always
lose -- there is a cross-over point when a tree becomes faster than a
vector, but even right at the cross-over point, they're BOTH faster
than a list.

--
The universe is a figment of its own imagination.

Dec 13 '05 #15

Greg wrote:

Kai-Uwe Bux wrote:
ro**********@gmail.com wrote:
On my machine, vector<unsigned long> beats list<unsigned long> by a
factor of 6; and you bet that the vector was reallocated several times.

So, for a sequence of, say, pointers the concern about reallocation is
not justified. For bigger objects, however, you may have a point. As I
said, this should be left to measurements.
All the items would have to be appended to the very end of the
container for a vector to stand any chance of being faster than a list

[snip]

Do not snip the relevant context! I replied to:
Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
almost guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

Thus, I was addressing the overhead of reallocation only. It is *consensus*
that list is better if insertions/deletions occur in other places than the
end.
Best

Kai-Uwe Bux

Dec 13 '05 #16

* Kai-Uwe Bux:

I ended up implementing a
rope like data structure that also supports efficient line numbering and
that helps with the undo feature, too.

Well, I'm getting senile, I think, can't remember how well I remembered or
not, so I had to look it up, found

<url:
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf>,

no such in Boost, unfortunately!

But there is in the SGI STL.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Dec 13 '05 #17

"Axter" <go****@axter.com> writes:

pepp wrote:
The runtime of list for
deletion and insertion operation is better than vectors.

When you delete anything from vector, all the iterators after that item
must be reassigned. no such thing wtih list.

That's not entirely correct.
This only happens when deleting from the center or beginning of the
vector.

deleting from the end of the vector does not cause this.

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;
}

Dec 13 '05 #18

"Axter" <go****@axter.com> writes:

Robbie Hatley wrote:
"Josh Mcfarlane" <da*****@gmail.com> wrote:
When would using std::list be more efficient / effective than using
other containers such as vector, deque, etc?
std::list is best any time you have one or more of the
following situations:

1. Wildly variable amount of data.

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.

3. Data needs to be sorted frequently.

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

Dec 13 '05 #19

"g" <ge*******@yahoo.com> writes:

It's optimized for insertions and sorting. Since the
order of elements is based on links, elements don't
have to be moved to sort or insert, which drastically
speeds those processes.

Try doing that with a vector! Oh, lordy...
You'd need to move thousands of bytes of data around,
possibly repeatedly re-allocating huge memory blocks.
Very inefficient.

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

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

/Niklas Norrthon

Dec 13 '05 #20

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

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Dec 13 '05 #21

Axter

Niklas Norrthon wrote:

"Axter" <go****@axter.com> writes:
pepp wrote:
The runtime of list for
deletion and insertion operation is better than vectors.

When you delete anything from vector, all the iterators after that item
must be reassigned. no such thing wtih list.

That's not entirely correct.
This only happens when deleting from the center or beginning of the
vector.

deleting from the end of the vector does not cause this.

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.

Dec 13 '05 #22

Axter

Niklas Norrthon wrote:

"g" <ge*******@yahoo.com> writes:
It's optimized for insertions and sorting. Since the
order of elements is based on links, elements don't
have to be moved to sort or insert, which drastically
speeds those processes.

Try doing that with a vector! Oh, lordy...
You'd need to move thousands of bytes of data around,
possibly repeatedly re-allocating huge memory blocks.
Very inefficient.

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

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.

Dec 13 '05 #23

Alf P. Steinbach wrote:

* Kai-Uwe Bux:

It is *consensus*
that list is better if insertions/deletions occur in other places than
the end.

I don't want to get into this analysis so won't discuss details (and I
think the most important property of container is how convenient it is for
the problem at hand!), but perhaps you haven't heard of cursor gaps, an
array
based logical list technique technique -- if you, or whoever is reading
this, haven't, look them up, or, just implement a simple text editor...
;-)

Ah, the fun of writing a text editor. At one point, I investigated how
different editors handle text. If I recall correctly, emacs features a
buffer gap. For an editor, this is a reasonable thing, since most of the
time consecutive insertions happen at the same place. Random insertions
and deletions, however, are still inefficient. I ended up implementing a
rope like data structure that also supports efficient line numbering and
that helps with the undo feature, too.
Best

Kai-Uwe Bux

Dec 13 '05 #24

* Kai-Uwe Bux:

It is *consensus*
that list is better if insertions/deletions occur in other places than the
end.

I don't want to get into this analysis so won't discuss details (and I think
the most important property of container is how convenient it is for the
problem at hand!), but perhaps you haven't heard of cursor gaps, an array
based logical list technique technique -- if you, or whoever is reading
this, haven't, look them up, or, just implement a simple text editor... ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Dec 13 '05 #25

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

Dec 13 '05 #26

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

Dec 13 '05 #27

Axter wrote:

roberts.n...@gmail.com wrote:

I don't agree. Every container serves a particular purpose. It could
be that in YOUR case most development domains seem to be least served
by the list container there are certainly a lot of cases when a list is
a very appropriate choice. The best thing is to understand the
implementations of the different containers and where those kind of
algorithms are best used. Take a class or read a book on data
structures and implement your own list, vector, map, etc...and then you
will be able to understand their value and when to use what.

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.

Dec 13 '05 #28

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

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Dec 13 '05 #29

ro**********@gmail.com wrote:

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.

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

Dec 13 '05 #30

Axter

ro**********@gmail.com wrote:

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 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/publ...nner_s_c__.htm

Consider using the following pool of books instead:
http://www.accu.org/bookreviews/publ...vanced_c__.htm

Dec 14 '05 #31

Axter wrote:

ro**********@gmail.com wrote:
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.
Best

Kai-Uwe Bux

Dec 14 '05 #32

Axter

Kai-Uwe Bux wrote:

Axter wrote:
ro**********@gmail.com wrote:
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.

Dec 14 '05 #33

deane_gavin

Axter wrote:

Kai-Uwe Bux wrote:
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?

Gavin Deane

Dec 14 '05 #34

pepp wrote:

> When you delete anything from vector, all the iterators after that item
> must be reassigned. no such thing wtih list.
And "Axter" <go****@axter.com> replied:
That's not entirely correct.
This only happens when deleting from the center or beginning of the
vector.

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::pop_back(), which is what I tried to illustrate with the
code example:
#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;

And "Axter" <go****@axter.com> said:
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::pop_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

Dec 14 '05 #35

"Diego Martins" <jo********@gmail.com> writes:

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

Dec 14 '05 #36

Axter

Niklas Norrthon wrote:

pepp wrote:
> > When you delete anything from vector, all the iterators after that item
> > must be reassigned. no such thing wtih list.
And "Axter" <go****@axter.com> replied:
That's not entirely correct.
> This only happens when deleting from the center or beginning of the
> vector.

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::pop_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()

Dec 14 '05 #37

Axter

de*********@hotmail.com wrote:

Axter wrote:
Kai-Uwe Bux wrote:
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.

Dec 14 '05 #38

Neil Cerutti

On 2005-12-14, Niklas Norrthon <do********@invalid.net> wrote:

"Diego Martins" <jo********@gmail.com> writes:
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);
}

--
Neil Cerutti

Dec 14 '05 #39

de*********@hotmail.com wrote:

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.

Dec 14 '05 #40

Axter

ro**********@gmail.com wrote:

Axter wrote:
roberts.n...@gmail.com wrote:

I don't agree. Every container serves a particular purpose. It could
be that in YOUR case most development domains seem to be least served
by the list container there are certainly a lot of cases when a list is
a very appropriate choice. The best thing is to understand the
implementations of the different containers and where those kind of
algorithms are best used. Take a class or read a book on data
structures and implement your own list, vector, map, etc...and then you
will be able to understand their value and when to use what.

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.

Don't take my credentials. As I've previously recommended to you, you
should read more advance books like that of Sutters and Meyers.
These two authors have very well known established credentials.
It's a mistake to base your opinions just on online information,
because anyone can write an FAQ or a web site, and claim authority on
the subject.
It's also a mistake to base your opinions on out dated beginner's C++
books.
If you're going to advocate a position that contradicts others, you
should at least make the effort to be well informed by more respectable
sources.
Otherwise garbage in, garbage out.
You read garbage, and you're going to end up reiterating the same
garbage, which is what I've mostly seen from your previous posting.

Here are the top 10 programming books that I recommend to all C++
programmers:
Effective C++ by Scott Meyers
More Effective C++ by Scott Meyers
Exceptional C++ by Herb Sutter
More Exceptional C++ by Herb Sutter
Effective STL by Scott Meyers
C++ Coding Standards : 101 Rules, Guidelines, and Best Practices {Herb
Sutter, Andrei Alexandrescu}
Programming languages - C++ STANDARD ISO/IEC 14882:1998(E)
C++ Programming Language Special Edition, The by Bjarne Stroustrup
Efficient C++ by Dov Bulka & David Mayhew
Modern C++ Design by Andrei Alexandrescu

And you don't have to take my word for it. Instead look them up in the
following well known respected site:
advanced c++
http://www.accu.org/bookreviews/publ...vanced_c__.htm

Dec 15 '05 #41

Axter wrote:

It's also a mistake to base your opinions on out dated beginner's C++
books.
You sure make a lot of assumptions little boy.

Thinking in C++ V2 is (c) 2003. The standard was altered in this one
little way just before publication apparently. This is really no big
deal, it happens. This is a very good book in every other way. I
refer to it quite often in fact, along with "The C++ Standard Library",
which is equally "outdated" by your standard. I have quite a few
"beginner" books I use as reference when I need to.
If you're going to advocate a position that contradicts others, you
should at least make the effort to be well informed by more respectable
sources.
By "contradict others" I think you must mean yourself? I don't need my
degrees, my experience, or my references to know that the code sample
you keep touting around is trash.
Otherwise garbage in, garbage out.
Well, if that is true then I would have to assume the books you read
are garbage. Luckily it doesn't work that way.
You read garbage, and you're going to end up reiterating the same
garbage, which is what I've mostly seen from your previous posting.

Thinking in C++ is not garbage. The first volume is a great
introduction to the language. The second volume is very good
instruction on how to USE the language at several levels. The second
volume is one of the best C++ books around.

Dec 15 '05 #42

Neil Cerutti <le*******@email.com> writes:

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

But reserving space for 100,000,000 items by default would be deemed
as unreasonable by most people, while I think it's perfectly
reasonable for a copy constructor to reserve the same amount of
memory as the source vector has reserved. Especially since it's
trivial to call another constructor if one doesn't need that
amount of reserved space in the copy.

/Niklas Norrthon

Dec 16 '05 #43

Neil Cerutti

On 2005-12-16, Niklas Norrthon <do********@invalid.net> wrote:

Neil Cerutti <le*******@email.com> writes:
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. ;-)

But reserving space for 100,000,000 items by default would be
deemed as unreasonable by most people, while I think it's
perfectly reasonable for a copy constructor to reserve the same
amount of memory as the source vector has reserved.

I don't agree. Copying capacity makes unsuppported assumptions.
At extremes, it's making the same assumption that you find
unreasonable in a default constructor.

--
Neil Cerutti

Dec 16 '05 #44