Sorting lists by struct member variables

[ryan1_00]

Hi,

Bascically I want to sort a list by a member variable of a struct
stored in the list.

// ------------------------------
// Struct Header
// ------------------------------


#include <string>

struct Connection {
int order;
std::string url;
int port;
inline bool empty() {
if ( (url.empty()) && (port == 0) ) {
return true;
} else {
return false;
}
}
};
// ------------------------------

// ------------------------------
// main
// ------------------------------

std::list<Connection> lstconn;
Connection conn;


conn.order = 2
conn.url = www.eg2.com
conn.port = 80

lstconn.push_back(conn);

conn.order = 1
conn.url = www.eg.com
conn.port = 80

lstconn.push_back(conn);

// ------------------------------

How do i sort on the order var?

lstconn.sort() is what i think i want to use but cant see how to point
it at the member var order.

Thanks in advance for all the help.

 

[Jerry Coffin]

[ ... ]

struct Connection {
int order;
std::string url;
int port;
inline bool empty() {
if ( (url.empty()) && (port == 0) ) {
return true;
} else {
return false;
}
}
};

[ ... ]

How do i sort on the order var?

One way is to overload operator< for the struct:

struct connection {
[ ...]
bool operator<(connection const &other) {
return order < other.order;
}
};

Another way is using a free function:

bool f_compare(Connection const &a, Connection const &b) {
return a.order < b.order;
}

Yet another way is to use a functor:

struct c_compare {
bool operator()(Connection const &a, Connection const &b) {
return a.order < b.order;
}
};

The overloaded operator< will be used unless you specify otherwise. To
use the free function, you have to specify its name when you call sort:

lstconn.sort(compare);
or:
lstconn.sort(c_compare());

I'd also note that nothing you've said indicates that a linked list is a
particularly appropriate data structure for the job at hand (and my
experience is that it only rarely IS a good choice). Absent a reason to
do otherwise, I'd consider using a vector instead.

 

[Victor Bazarov]

Bascically I want to sort a list by a member variable of a struct
stored in the list.

// ------------------------------
// Struct Header
// ------------------------------


#include <string>

struct Connection {
int order;
std::string url;
int port;
inline bool empty() {
if ( (url.empty()) && (port == 0) ) {
return true;
} else {
return false;
}
}
};
// ------------------------------

// ------------------------------
// main
// ------------------------------

std::list<Connection> lstconn;
Connection conn;


conn.order = 2
conn.url = www.eg2.com
conn.port = 80

lstconn.push_back(conn);

conn.order = 1
conn.url = www.eg.com
conn.port = 80

lstconn.push_back(conn);

// ------------------------------

How do i sort on the order var?

You need to define a comparison functor which will compare two values
of 'Connection' type and return true if the first's 'order' is smaller
than then the other's. Then you sort the list while providing your
comparator. RTFM about the 'sort' member of std::list class.

lstconn.sort() is what i think i want to use but cant see how to point
it at the member var order.

RTFM

And, BTW, what book are you reading that explains how to use different
facilities of the Standard library? Doesn't that book explain how to
provide custom sorters to 'std::sort' or 'std::list::sort'?

V

 

[Martijn van Buul]

* Jerry Coffin:

I'd also note that nothing you've said indicates that a linked list is a
particularly appropriate data structure for the job at hand (and my
experience is that it only rarely IS a good choice). Absent a reason to
do otherwise, I'd consider using a vector instead.

There are dozens of reasons why using a list can be more appropriate than
a vector. In fact, unless you have a damn good reason why you *NEED* a
vector, you probably don't.

 

[Pvt Ryan]

Hi thanks for the replies..

I can't say I fully understand the first reply due to my limited C/C++
knowledge but atleast I now have a starting point to work with. (if
anyone wants to give me an idiots guide about the options mentioned I
would be gratefull.)

I'd also note that nothing you've said indicates that a linked list is a
particularly appropriate data structure for the job at hand (and my
experience is that it only rarely IS a good choice). Absent a reason to
do otherwise, I'd consider using a vector instead.

Vectors are optimised for random access which i dont need, the list
will be accessed sequentially only, so a vector is not needed.

And, BTW, what book are you reading that explains how to use different
facilities of the Standard library? Doesn't that book explain how to
provide custom sorters to 'std::sort' or 'std::list::sort'?

I am not really using a book (most of the ones i have are on advanced
topics as i just need references points), google is my friend.
This is my first major C/C++ project I usually just hack other peoples
code so my knowledge is quite limited. I had looked at std::sort but I
didnt know that i could provide custom sorters to it, and am not sure
how to access a member var of a struct stored in list in order to use
it to sort on, the only way i can think of is creating an iter to use
to access it but I was hoping that there was a to do it in 2 or 3
lines (i had considered writing a whole method to do it but thought
that it was overkill and there must be an easier way.)

Basically I am writing an updater program to allow me to update exe's
by comparing versions etc..
http://svn.ninet.org/viewvc/updater/

 

[Pvt Ryan]

Hi thanks for the replies..

I can't say I fully understand the first reply due to my limited C/C++
knowledge but I used the overloaded operator which works a treat.

I will have to do some more reading up on that..

I'd also note that nothing you've said indicates that a linked list is a
particularly appropriate data structure for the job at hand (and my
experience is that it only rarely IS a good choice). Absent a reason to
do otherwise, I'd consider using a vector instead.

Vectors are optimised for random access which i dont need, the list
will be accessed sequentially only, so a vector is not needed.

And, BTW, what book are you reading that explains how to use different
facilities of the Standard library? Doesn't that book explain how to
provide custom sorters to 'std::sort' or 'std::list::sort'?

I am not really using a book (most of the ones i have are on advanced
topics as i just need references points), google is my friend.
This is my first major C/C++ project I usually just hack other peoples
code so my knowledge is quite limited. I had looked at std::sort but I
didnt know that i could provide custom sorters to it, and am not sure
how to access a member var of a struct stored in list in order to use
it to sort on, the only way i can think of is creating an iter to use
to access it but I was hoping that there was a to do it in 2 or 3
lines (i had considered writing a whole method to do it but thought
that it was overkill and there must be an easier way.)

Basically I am writing an updater program to allow me to update exe's
by comparing versions etc..
http://svn.ninet.org/viewvc/updater/

 

[Jerry Coffin]

* Jerry Coffin:


There are dozens of reasons why using a list can be more appropriate than
a vector.

In theory there can be -- but in the last 20 years, I've actually
encountered about time that it was even open to argument that it was
_probably_ more appropriate.

In fact, unless you have a damn good reason why you *NEED* a
vector, you probably don't.

You're right -- you almost never "*NEED*" a vector -- but you _want_ it
far more often than you do a linked list.

 

[Jerry Coffin]

[ ... ]

Vectors are optimised for random access which i dont need, the list
will be accessed sequentially only, so a vector is not needed.

A vector works just fine for linear access as well. A list is
appropriate primarily when you need fast insertions and/or deletions in
the middle of the list AND you (nearly) always know ahead of time where
all the insertions or deletions will take place. In nearly every every
case, a linked list is a net loss. At least what you've shown makes it
look like you're adding things to the end of the list, then sorting it,
and finally iterating through it in order. If that's the case, a vector
is almost certainly the preferred choice.

[Warning: what follows is a rather long and probably excessively
technical explanation -- and quite a bit of it is only marginally
topical at that. Feel free to skip over it or just do some profiling to
see whether a linked list is really more suitable for your purposes. ]

Each of the nodes in a linked list is separately allocated, often at
parts of memory rather widely separated from each ohter. The linked list
also requires that each node include two pointers along with the data
being stored, taking up extra space. Both of these tend to make the
processor's cache much less effective.

By contrast, a vector uses contiguous storage and each item stores only
what you've asked for. This (nearly) optimizes cache usage.

There's also a question of the amount of storage used, though this is
generally only an issue when/if you're storing quite a bit of data.

In a linked list, as mentioned above, you have two pointers along with
the data itself. On (for example) a 64-bit system, these will occupy 64
bits apiece, or 16 bytes for the two pointers. That means if (for
example) the data in each node is 16 bytes, you're _doubling_ the total
amount of storage being used.

A vector can also use extra memory, but it does so quite differently. A
typical implementation of vector will have allocated approximately 25%
more storage than it is using at a given time. This storage, however, is
all at the end of the allocated memory and, crucially, is rarely (if
ever) read or written until the vector expands to the point that it is
needed to store actual data. On a typical system with virtual memory
that no real memory will be allocated until or unless the memory is
actually written. The memory gets allocated on a page-by-page basis, so
a full page is allocated if any of the memory in that page has been read
or written. On a typical current system, the page size will be 4 or 8
kilobytes, and the maximum wasted space is just less than that
regardless of how large the vector gets (though of course, for a small
vector, far less space will be wasted).

 

[LR]

There are dozens of reasons why using a list can be more appropriate than
a vector. In fact, unless you have a damn good reason why you *NEED* a
vector, you probably don't.

I'm a little surprised by that, could you expand on that?

I think I often run into very good reasons why I need a vector although
sometimes on consideration I think I really need a map.

TIA

LR

 

[Martijn van Buul]

* LR:

I'm a little surprised by that, could you expand on that?

First of all, std::list and std::vector are part of the STL (Suspicious
and Troublesome Library). As such, they're part of the problem set, because
while they're easy to use and undenyably powerful, they have a hidden
agenda in terms of efficiency. std::vector moreso than std::list. std::vector
can - and will - decide that it needs to be copied at random times. This
means that if you add items to a vector, expect them to be copied at some point
in time, especially when you're least expecting it. Every time a std::vector
claims to do something "in constant time", it really means "I'm going to hit
you over the head with a copy constructor or an assignment operator", where
if std::list cliams constant time, it usually just means updating a pointer
or two. This alone opens up a can of worms. It may be tolerable for POD, but
it's devastating if you're dealing with large objects.

Other than being a pain in the std::end just because of STL-ness, there's
always the observation that:

1) Inserting elements in a list is constant time, whereas it is linear time[1]
in a vector unless in the specific case of adding to the end where there
is enough reserved room.
2) Splicing a list isn't even possible with a vector without making a copy
3) Removing elements from a list is constant time, linear time[1] in a vector.
4) Nearly every operation on a vector will invalidate any iterator, not so
with a list.
5) The lifetime of objects in a list is clearly defined, in a vector it's not.
6) Swapping two elements in a list is cheap, it can be expensive in a vector
7) vectors always suffer from overallocation, in an attempt to keep things
acceptable.

The benefit std::vector has to offer is, of course, that it provides random
access. But in a lot of cases, you don't need random acccess - so why choose
a container that is only optimal for random access, if you don't need it?

Of course, you can plug all these problems with yet another publicly available
patch from STL or boost, but they're just that: A patch.

Martijn

PS: To all those people who will doubtlessly respond with
"premature optimization": You're wrong. Choosing the right
data type isn't about optimization, and it can never be premature.

[1] _AT BEST_, since it assumes that the copy constructor of objects in the
vector can be performed in constant time, which is certainly not always
the case!

 

[James Kanze]

* LR:

First of all, std::list and std::vector are part of the STL
(Suspicious and Troublesome Library). As such, they're part of
the problem set, because while they're easy to use and
undenyably powerful, they have a hidden agenda in terms of
efficiency.

Not really that hidden. The complexity requirements of both are
part of the specification.

std::vector moreso than std::list. std::vector can
- and will - decide that it needs to be copied at random
times. This means that if you add items to a vector, expect
them to be copied at some point in time, especially when
you're least expecting it. Every time a std::vector claims to
do something "in constant time", it really means "I'm going to
hit you over the head with a copy constructor or an assignment
operator", where if std::list cliams constant time, it usually
just means updating a pointer or two.

It also means a separate allocation for each element. If you're
using std::vector, and appending at the end, you'll reallocate
and copy once in a while---very rarely, in fact. If you're
using std::list, you'll never copy, but you will reallocate for
every insertion, and for many objects, allocation is more
expensive than copying. And as Jerry Coffin pointed out,
std::vector has the best locality. In general, the accepted
rule seems to be to use std::vector by default, and other
containers as the need arrises.

Also, we shouldn't forget, std::deque, will never copy either,
as long as insertions are at one of the ends, and will still
have better locality than std::list.

This alone opens up a can of worms. It may be tolerable for
POD, but it's devastating if you're dealing with large
objects.

Other than being a pain in the std::end just because of
STL-ness, there's always the observation that:

1) Inserting elements in a list is constant time, whereas it
is linear time[1] in a vector unless in the specific case
of adding to the end where there is enough reserved room.

The original poster showed no indication that he was inserting
anywhere but at the end. Which is amortised constant time for
std::vector. Unless copying is extremely costly (in which case,
the type probably shouldn't have value semantics, and shouldn't
be put into a container to begin with), std::vector will be
faster than std::list if all insertions are at the end.

2) Splicing a list isn't even possible with a vector without making a copy

Which is only relevant is you need to splice.

3) Removing elements from a list is constant time, linear time[1] in a vector.

It's constant time if you remove them from the end (and a very
small constant at that). It's constant time anywhere from a
list, but the constant is significantly larger. Since there was
no indication here that objects would ever be removed, the
argument is irrelevant here.

4) Nearly every operation on a vector will invalidate any iterator, not so
with a list.

Very few operations on vector actually invalidate iterators, but
it's true that this can sometimes be an argument in favor of
list. In practice, the way the STL is designed to be used, you
shouldn't have any iterators alive when doing any manipulations
on the container; iterators are designed to be short lived
objects, passed to an algorithm, and then best forgotten.

5) The lifetime of objects in a list is clearly defined, in a vector it's not.

??? The lifetime of an object is very exactly defined in both
cases.

6) Swapping two elements in a list is cheap, it can be expensive in a vector

You'll have to defend that; from what I can see, swapping the
value of two elements is always the same, regardless of the
container in which the elements live. Swapping the position of
two elements may be cheaper in a list, but again, that's only
relevant if you want to swap the position of elements.

7) vectors always suffer from overallocation, in an attempt to keep things
acceptable.

Not necessarily. It depends on how you manage your vector.
std::list always allocates more than the data requires, because
it needs extra pointers.

The benefit std::vector has to offer is, of course, that it
provides random access. But in a lot of cases, you don't need
random acccess - so why choose a container that is only
optimal for random access, if you don't need it?

It's optimal in general for simple things. As soon as you
become more complicated, you have to analyse more.

 

[Juha Nieminen]

inline bool empty() {
if ( (url.empty()) && (port == 0) ) {
return true;
} else {
return false;
}

Not related, but why not simply:

inline bool empty() const { return url.empty() && port == 0; }

 

[Jerry Coffin]

First of all, std::list and std::vector are part of the STL (Suspicious
and Troublesome Library). As such, they're part of the problem set, because
while they're easy to use and undenyably powerful, they have a hidden
agenda in terms of efficiency. std::vector moreso than std::list. std::vector
can - and will - decide that it needs to be copied at random times.

Nonsense. The times are not random at all -- the standard specifies
exacctly what iterators can be invalidated by what operations.

This
means that if you add items to a vector, expect them to be copied at some point
in time, especially when you're least expecting it. Every time a std::vector
claims to do something "in constant time", it really means "I'm going to hit
you over the head with a copy constructor or an assignment operator", where
if std::list cliams constant time, it usually just means updating a pointer
or two. This alone opens up a can of worms. It may be tolerable for POD, but
it's devastating if you're dealing with large objects.

The standard specifically says that adding to a vector happens in
"amortized constant time", and textbooks that explain exactly what this
means and how it relates to std::vector are easily and widely available.

Yes, some operations on std::list are constant time instead of amortized
constant time. Then again, just for one obvious example, finding an item
in a list is always linear time, where in a (sorted) vector it can be
logarithmic (which, it should be pointed out, is practically constant
for most reasonable sizes of collections).

[ ... ]

1) Inserting elements in a list is constant time, whereas it is linear time[1]
in a vector unless in the specific case of adding to the end where there
is enough reserved room.

But find the right place to insert the item in the list is linear time
except in the specific case of adding to the beginning, end, or a
previously "memorized" position.

2) Splicing a list isn't even possible with a vector without making a copy

Quite true -- but he didn't mention anything that indicated that he
cared at all about splicing anything.

3) Removing elements from a list is constant time, linear time[1] in a vector.

Removing elements from a list has the same properties as inserting them,
so see the reply to 1) above.

4) Nearly every operation on a vector will invalidate any iterator, not so
with a list.

Pure nonsense. The iterators that can be invalidated by specific
operations are clearly documented.

5) The lifetime of objects in a list is clearly defined, in a vector it's not.

This is pure FUD. In any case, one of the basic ideas of _all_ the
standard containers is that they should be used to hold _values_ that
are relatively cheap to copy; if the lifetime of specific objects is a
major concern, NO standard container is likely to work well for you.

6) Swapping two elements in a list is cheap, it can be expensive in a vector

More FUD. Swapping elements in a vector is a constant-time operation
just like with list.

7) vectors always suffer from overallocation, in an attempt to keep things
acceptable.

And so do lists. The difference is that a list inter-mixes the
overallocation (in the form or at least two pointers per node) with the
real data, hurting locality of reference. As previously mentioned, on a
typical system that uses virtual memory, the overallocation in a vector
is purely of address space, not really memory at all. Since the extra
space in a list is intermixed with the stord data, the overallocation in
a list does need to be backed by real memory.

The benefit std::vector has to offer is, of course, that it provides random
access. But in a lot of cases, you don't need random acccess - so why choose
a container that is only optimal for random access, if you don't need it?

You've mis-characterized the situation in both directions. You've
ignored many of the strengths of vectors and many of the weaknesses of
lists.

Of course, you can plug all these problems with yet another publicly available
patch from STL or boost, but they're just that: A patch.

Complete nonsense. First of all, patches are generally just to fix
coding errors, and have no effect on the fundamental trade-offs between
different types of containers. Second of all, most of what you can get
from Boost is not patches of anything -- it's things like completely new
and different containers such as array, dynamic_bitset and multiindex
that provide capabilities that simply aren't present in the standard
library -- though TR1 added some of these, and all of those in TR1 are
also included in (at least the current draft of) C++ 0x.

PS: To all those people who will doubtlessly respond with
"premature optimization": You're wrong. Choosing the right
data type isn't about optimization, and it can never be premature.

To an extent it is about optimization, and it can CERTAINLY be
premature. Nonetheless, it's true that once you've chosen a data
structure it can be more difficult than most of us would like to change
that decision.

 

[Kai-Uwe Bux]

Nonsense. The times are not random at all -- the standard specifies
exacctly what iterators can be invalidated by what operations.

The point was not about invalidating iterators but about invoking copy
constructors or assignment operators. The standard only points out when
that _might_ happen, but very often it does not happen even when it might
(otherwise, one would not get amortized constant time for push_back()). In
effect, you cannot predict when copy construction happens, you can only
know that it might.

The standard specifically says that adding to a vector happens in
"amortized constant time", and textbooks that explain exactly what this
means and how it relates to std::vector are easily and widely available.

However, amortized constant time at this point in the standard treats copy
construction and assignment of the value_type as a primitive operation
(regardless of its complexity). If copy-construction involves creating a
new TCP connection, the complexity guarantee for std::vector<> of the
standard is more or less pointless.

Yes, some operations on std::list are constant time instead of amortized
constant time. Then again, just for one obvious example, finding an item
in a list is always linear time, where in a (sorted) vector it can be
logarithmic (which, it should be pointed out, is practically constant
for most reasonable sizes of collections).

[ ... ]

1) Inserting elements in a list is constant time, whereas it is linear
time[1]
in a vector unless in the specific case of adding to the end where
there is enough reserved room.

But find the right place to insert the item in the list is linear time
except in the specific case of adding to the beginning, end, or a
previously "memorized" position.

2) Splicing a list isn't even possible with a vector without making a
copy

Quite true -- but he didn't mention anything that indicated that he
cared at all about splicing anything.

3) Removing elements from a list is constant time, linear time[1] in a
vector.

Removing elements from a list has the same properties as inserting them,
so see the reply to 1) above.

4) Nearly every operation on a vector will invalidate any iterator, not
so
with a list.

Pure nonsense. The iterators that can be invalidated by specific
operations are clearly documented.

All you are saying here is that it is clearly documented. That does not
contradict the (awfully vague) statement that "nearly every" operation
invalidates iterators.

In any case, this seems to be a matter of counting. However, I would contend
that (to make things more complicated) one should use a weighted count:
operations that are used more often are given a higher weight. Since
push_back() can invalidate iterators, that accounts for a lot.

This is pure FUD. In any case, one of the basic ideas of _all_ the
standard containers is that they should be used to hold _values_ that
are relatively cheap to copy; if the lifetime of specific objects is a
major concern, NO standard container is likely to work well for you.

Agreed. Lifetime issues are the same in all containers.

More FUD. Swapping elements in a vector is a constant-time operation
just like with list.

Again the remark above about what constant-time means applies.


[stuff on which I have nothing to add snipped]


Best

Kai-Uwe Bux

 

[Jerry Coffin]

The point was not about invalidating iterators but about invoking copy
constructors or assignment operators. The standard only points out when
that _might_ happen, but very often it does not happen even when it might
(otherwise, one would not get amortized constant time for push_back()). In
effect, you cannot predict when copy construction happens, you can only
know that it might.

The fact remains that copying does not happen at "random times." It
absolutely will NOT happen except under known, specified circumstances.

However, amortized constant time at this point in the standard treats copy
construction and assignment of the value_type as a primitive operation
(regardless of its complexity). If copy-construction involves creating a
new TCP connection, the complexity guarantee for std::vector<> of the
standard is more or less pointless.

Yes, in that case the time is long -- but it's still amortized constant.
OTOH, if it's really someething that creates a TCP connection, it starts
to sound a lot more like an "identity" sort of object instead of a value
object. In that case, it probably shouldn't be getting placed into any
of the standard containers.

Even with std::list, when you initially place the object into the list,
you still get one call to the copy constructor for the object -- so
something that involves creating a new TCP connection when it's copied
probably shouldn't be put there either. Granted, there may be a _few_
situations in which exactly one copy construction is permissible, but
any more than that isn't. This still doesn't (necessarily) rule out
std::vector though -- in particular, if you know the number of items
ahead of time and can preallocate the vector, that's what you get as
well. That may not always be the case, but I think it's at least as
common as items that can really only be copy constructed once.

All you are saying here is that it is clearly documented. That does not
contradict the (awfully vague) statement that "nearly every" operation
invalidates iterators.

In any case, this seems to be a matter of counting. However, I would contend
that (to make things more complicated) one should use a weighted count:
operations that are used more often are given a higher weight. Since
push_back() can invalidate iterators, that accounts for a lot.

It's true that push_back can invalidate iterators. At least IME, the
weighted count of times I've needed (or wanted) to preserve an iterator
into a vector across calls to push_back has been precisely zero.
Iterators into a vector tend to be used only to pass to algorithms, in
which case you don't get any chance to call push_back during the
algorithm's execution. Otherwise, if you want to remember a spot in a
vector, you use its index, and push_back has no effect on the value of
any previously-valid index.

[ ... ]

Again the remark above about what constant-time means applies.

And the reply above applies as well.

The bottom line is that to justify recommending list for this kind of
object, you have to find some sort of boject that's entirely reasonable
to copy once, but completely unacceptable to ever copy it more than
that.

I've never seen such a thing, and I'm not convinced that your example
fits the criteria either. IME, objects generally fall into two distinct
categories: most can be copied entirely freely. The rest can't be copied
at all. A smart pointer to a member of the latter group is generally an
instance of the former group. Smart pointers are sufficiently common and
efficient that I suspect there's an overlap, where you could reasonably
copy objects the number of times you'd typically see by putting them
into a vector, but you still decide to most use a smart pointer to them
because it's cheap and easy to do.

 

[Alf P. Steinbach]

* Jerry Coffin:

This is pure FUD. In any case, one of the basic ideas of _all_ the
standard containers is that they should be used to hold _values_ that
are relatively cheap to copy; if the lifetime of specific objects is a
major concern, NO standard container is likely to work well for you.

std::list is likely to work well for that...

And as I recall, C++0x will remove the requirement of "assignable" for
std::list, precisely because it's meaningless for std::list.

Copy construction presumably still required for initial insertion of items.

Cheers,

- Alf

 

[Alf P. Steinbach]

* Kai-Uwe Bux:

Agreed. Lifetime issues are the same in all containers.

No, not at all.

Insertion in a list has no effect on validity of iterators to that list.

While validity of iterators is not the same as guarantees about
lifetime, the continued existence of the data elements (that they're not
will-nilly in-place destroyed and reconstructed for no reason) is in
practice guaranteed.


Cheers,

- Alf

 

[Kai-Uwe Bux]

* Kai-Uwe Bux:

No, not at all.

Insertion in a list has no effect on validity of iterators to that list.

While validity of iterators is not the same as guarantees about
lifetime, the continued existence of the data elements (that they're not
will-nilly in-place destroyed and reconstructed for no reason) is in
practice guaranteed.

Right, I was not precise. The actual objects in a vector might undergo
copy-destroy cycles. However, the _values_ are not vanishing from the
sequence unless you erase them. I have a tendency to consider the
copy-destruction way of moving around objects that happens when a vector
reallocates an artifact that does not affect identity of objects on a
conceptual level. However, since the standard defines an object to be a
region of memory, formally, the identity of the object changes.


Best

Kai-Uwe Bux

 

[Jerry Coffin]

* Jerry Coffin:

std::list is likely to work well for that...

Work, maybe. Work well, almost certainly not.

And as I recall, C++0x will remove the requirement of "assignable" for
std::list, precisely because it's meaningless for std::list.

Copy construction presumably still required for initial insertion of items.

Thanks (largely) to the wonders of rvalue references, C++ 0x won't
require assignment or copy construction even for items in a vector. For
those writing merge sorts (for one example) the ability to have a vector
of streams will be kind of nice...

 

[Jerry Coffin]

* Kai-Uwe Bux:

[ ... ]

No, not at all.

Insertion in a list has no effect on validity of iterators to that list.

True, but irrelevant.

While validity of iterators is not the same as guarantees about
lifetime, the continued existence of the data elements (that they're not
will-nilly in-place destroyed and reconstructed for no reason) is in
practice guaranteed.

Also true -- for all containers!