By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,413 Members | 999 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,413 IT Pros & Developers. It's quick & easy.

Effective STL Item 4 (size() vs. empty())

P: n/a
Hi,

I am just reading that book by Scott Meyers. In Item 4 Meyers suggests
to always use empty() instead of size() when probing for emptyness of
STL containers. His reasoning is that size() might take linear time on
some list implementations. That makes sense at first.
However, he also says this at the very beginning:

"That being the case [he is referring to size()==0 being equivalent
to empty()==true], you might wonder why one construct should be
preferred to the other, especially in view of the fact that empty is
typically implemented as an inline function that simply returns whether
size returns 0. [...]
.... the reason is simple: empty is a constant-time operations for all
standard containers, but for some list implementations, size may take
linear time."

So where is the logic? If empty() only calls size(), and size() is
implemented to take linear time, empty() obviously needs linear time,
too, because it does nothing more than calling size(). So if size()
happens to take linear time, where is the benefit of using empty() instead?

*confused*

--
Regards,
Matthias
Jul 23 '05 #1
Share this Question
Share on Google+
25 Replies


P: n/a
Matthias wrote:
Hi,

I am just reading that book by Scott Meyers. In Item 4 Meyers suggests
to always use empty() instead of size() when probing for emptyness of
STL containers. His reasoning is that size() might take linear time on
some list implementations. That makes sense at first.
However, he also says this at the very beginning:

"That being the case [he is referring to size()==0 being equivalent
to empty()==true], you might wonder why one construct should be
preferred to the other, especially in view of the fact that empty is
typically implemented as an inline function that simply returns whether
size returns 0. [...]
... the reason is simple: empty is a constant-time operations for all
standard containers, but for some list implementations, size may take
linear time."

So where is the logic? If empty() only calls size(), and size() is
implemented to take linear time, empty() obviously needs linear time,
too, because it does nothing more than calling size(). So if size()
happens to take linear time, where is the benefit of using empty() instead?


I think he explains it clearly.

std::list::empty has a special way to determine emptiness (are there any
objects in the list is easy to determine). However, while
std::list::size==0 can give you the same answer, calling it will have
O(N) time since it needs to count every element. This would not be very
desirable if you have a few million elements in the list.
Jul 23 '05 #2

P: n/a

"Matthias" <no****@digitalraid.com> wrote in message news:ct*************@news.t-online.com...
So where is the logic? If empty() only calls size(), and size() is
implemented to take linear time, empty() obviously needs linear time,
too, because it does nothing more than calling size(). So if size()
happens to take linear time, where is the benefit of using empty() instead?


I think one implementation of empty() may be something like
return size() == 0. But another may be that internally, a class holds
a member bool that gets set to true when size is decremented to
0 and false otherwise. Then empty() could be implemented by
returning this bool.
I think his basic point is that empty() may
call size() but may not - in any case, depending on the implementation,
empty() has possibly less overhead and probably at worst it's the
same.
Jul 23 '05 #3

P: n/a
Matthias wrote:
Hi,

[snip]
[Repeating original with emphasis added:]
you might wonder why one construct should be
preferred to the other, especially in view of the fact that empty is
[!]TYPICALLY[!] implemented as an inline function that simply returns
whether size returns 0. [...]
So where is the logic? If empty() only calls size(), and size() is
implemented to take linear time, empty() obviously needs linear time,
too, because it does nothing more than calling size(). So if size()
happens to take linear time, where is the benefit of using empty()
instead?

*confused*


The Key here is typically! Not always! In the cases were it matters empty()
is obviously NOT implemented in terms of size().

Hope that helps

Fabio
Jul 23 '05 #4

P: n/a
Thanks everybody. I think I got the point.

--
Regards,
Matthias
Jul 23 '05 #5

P: n/a

"Matthias" <no****@digitalraid.com> wrote in message
news:ct*************@news.t-online.com...

| too, because it does nothing more than calling size(). So if size()
| happens to take linear time, where is the benefit of using empty() instead?

Though I have great respect for SM and his books, this Item is *not* correct
as long as we talk about the C++ standard. size() is guaranteed to be O(1)
also for list. Incidently, this false item sneaked its way into Sutter and
Alexandrescus new book too.

br

Thorsten
Jul 23 '05 #6

P: n/a
Thorsten Ottosen wrote:
"Matthias" <no****@digitalraid.com> wrote in message
news:ct*************@news.t-online.com...

| too, because it does nothing more than calling size(). So if size()
| happens to take linear time, where is the benefit of using empty() instead?

Though I have great respect for SM and his books, this Item is *not* correct
as long as we talk about the C++ standard. size() is guaranteed to be O(1)
also for list. Incidently, this false item sneaked its way into Sutter and
Alexandrescus new book too.


GCC seems to have a bug then.

Can you cite where in the standard that is required ?
Jul 23 '05 #7

P: n/a

"Gianni Mariani" <gi*******@mariani.ws> wrote in message
news:15********************@speakeasy.net...
| Thorsten Ottosen wrote:
| > "Matthias" <no****@digitalraid.com> wrote in message
| > news:ct*************@news.t-online.com...
| >
| > | too, because it does nothing more than calling size(). So if size()
| > | happens to take linear time, where is the benefit of using empty()
instead?
| >
| > Though I have great respect for SM and his books, this Item is *not*
correct
| > as long as we talk about the C++ standard. size() is guaranteed to be O(1)
| > also for list. Incidently, this false item sneaked its way into Sutter and
| > Alexandrescus new book too.
|
| GCC seems to have a bug then.

it probably has many.

| Can you cite where in the standard that is required ?

Section 23.2.2 says that list fulfills the container requirements.
Section 23.1, Table 65 says

"Those entries marked ''(Note A)'' should have constant complexity."

Note A applies to container::size()

-Thorsten
Jul 23 '05 #8

P: n/a

"Thorsten Ottosen" <ne*****@cs.auc.dk> skrev i en meddelelse
news:41***********************@news.sunsite.dk...

"Matthias" <no****@digitalraid.com> wrote in message
news:ct*************@news.t-online.com...

| too, because it does nothing more than calling size(). So if size()
| happens to take linear time, where is the benefit of using empty()
instead?

Though I have great respect for SM and his books, this Item is *not*
correct
as long as we talk about the C++ standard. size() is guaranteed to be O(1)
also for list. Incidently, this false item sneaked its way into Sutter and
Alexandrescus new book too.

br

Thorsten

Hi Thorsten

I do not have a copy of the holy standard, but are you absolutely sure? I
believe that size() behaves like e.g. push_back on a vector - that is has an
average complexity of O(1).
Some list algorithms (splicing) might invalidate the internal size holder,
requiring a recalculation when it is required.
Apart from that, I believe you will agree with me that list.empty() is
clearer than list.size() == 0.

Kind regards
Peter
Jul 23 '05 #9

P: n/a
In article <41***********************@news.sunsite.dk>,
"Thorsten Ottosen" <ne*****@cs.auc.dk> wrote:
| Can you cite where in the standard that is required ?

Section 23.2.2 says that list fulfills the container requirements.
Section 23.1, Table 65 says

"Those entries marked ''(Note A)'' should have constant complexity."

Note A applies to container::size()


This is a (dirty) trick in the standard. empty() is said to have
constant complexity. (period)

size() (as Thorsten correctly states) "should have constant complexity".

"should" has a specific meaning in a standards document. See:

http://www.iso.org/iso/en/iso9000-14.../2000rev8.html

To paraphrase, "should" means we would like it to, but we're not going
to require it to. Therefore a linear (or even quadratic or exponential)
complexity on size() is standards conforming. And if you really want to
be horrified, note that Note A applies also to swap and max_size.

In practice, only list::size appears to be vulnerable to this note.

You can find vehement supporters for this flexibility for list::size,
but I'm not one of them. I believe that not only is this flexibility
not needed, it makes list::size useless, and actually dangerous.

-Howard
Jul 23 '05 #10

P: n/a
"Howard Hinnant" <hi*****@metrowerks.com> wrote in message
news:hi***************************@syrcnyrdrs-03-ge0.nyroc.rr.com...
In article <41***********************@news.sunsite.dk>,
"Thorsten Ottosen" <ne*****@cs.auc.dk> wrote:
| Can you cite where in the standard that is required ?

Section 23.2.2 says that list fulfills the container requirements.
Section 23.1, Table 65 says
.... To paraphrase, "should" means we would like it to, but we're not going
to require it to. Therefore a linear (or even quadratic or exponential)
complexity on size() is standards conforming. And if you really want to
be horrified, note that Note A applies also to swap and max_size. Wow. Very instructive.
In practice, only list::size appears to be vulnerable to this note.

You can find vehement supporters for this flexibility for list::size,
but I'm not one of them. I believe that not only is this flexibility
not needed, it makes list::size useless, and actually dangerous.


Could you list the trade-offs for std::list to store its item count?
I know that splice operations between std::list instances then become
more expensive, and I agree I would not care much about that.
Any other practical obstacle you have been encountering?
Kind regards - Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

Jul 23 '05 #11

P: n/a

"Howard Hinnant" <hi*****@metrowerks.com> wrote in message
news:hi***************************@syrcnyrdrs-03-ge0.nyroc.rr.com...
| In article <41***********************@news.sunsite.dk>,
| "Thorsten Ottosen" <ne*****@cs.auc.dk> wrote:
|
| > | Can you cite where in the standard that is required ?
| >
| > Section 23.2.2 says that list fulfills the container requirements.
| > Section 23.1, Table 65 says
| >
| > "Those entries marked ''(Note A)'' should have constant complexity."
| >
| > Note A applies to container::size()
|
| This is a (dirty) trick in the standard. empty() is said to have
| constant complexity. (period)
|
| size() (as Thorsten correctly states) "should have constant complexity".
|
| "should" has a specific meaning in a standards document. See:
|
| http://www.iso.org/iso/en/iso9000-14.../2000rev8.html
|
| To paraphrase, "should" means we would like it to, but we're not going
| to require it to. Therefore a linear (or even quadratic or exponential)
| complexity on size() is standards conforming. And if you really want to
| be horrified, note that Note A applies also to swap and max_size.

ok, yeah, so the standard does not require it.

| In practice, only list::size appears to be vulnerable to this note.

In Scott's book he discusses how the alternative is between
an O(1) size() and a O(n) splice() or conversely. However, the
standard nails down the complexity of splice() to O(n). Hence
it would be weird to make size() O(n) too.

| You can find vehement supporters for this flexibility for list::size,
| but I'm not one of them. I believe that not only is this flexibility
| not needed, it makes list::size useless, and actually dangerous.

well, the question is: are there other operations than splice() which
would benefit from a O(n) size()? Otherwise there should be no
"should" in the standard.

-Thorsten
Jul 23 '05 #12

P: n/a
> In practice, only list::size appears to be vulnerable to this note.

You can find vehement supporters for this flexibility for list::size,
but I'm not one of them. I believe that not only is this flexibility
not needed, it makes list::size useless, and actually dangerous.


I don't see a problem. I would "cache" an internal count that used to
evaluate list::size().
If the internal count is valid it will O(1) to evaluate size(), otherwise
O(N).
If splice() is never called, size() would always be O(1).
And only with some versions of splice() are we in the dark as to the size()
afterwards, not all.

That gives near enough O(1) behaviour for both size() and splice() and only
alternative calls to each is the worse case.

Stephen Howe
Jul 23 '05 #13

P: n/a
In article <41***********************@news.sunsite.dk>,
"Thorsten Ottosen" <ne*****@cs.auc.dk> wrote:
| You can find vehement supporters for this flexibility for list::size,
| but I'm not one of them. I believe that not only is this flexibility
| not needed, it makes list::size useless, and actually dangerous.

well, the question is: are there other operations than splice() which
would benefit from a O(n) size()? Otherwise there should be no
"should" in the standard.
In article <ct**********@news.hispeed.ch>,
"Ivan Vecerina" <IN*************************@vecerina.com> wrote:
Could you list the trade-offs for std::list to store its item count?
I know that splice operations between std::list instances then become
more expensive, and I agree I would not care much about that.
Any other practical obstacle you have been encountering?


Sure.

list::splice is the only function where there is an order of complexity
change. However, my last sentence is, I believe, overly alarming, and
indeed, an exaggeration.

There are 5 possible valid splice situations: splicing from self or
splicing from another list, crossed with splicing 1 element, some
elements, or all elements. The O(1) size leads to an O(some) splice in
one of these five situations (best viewed in a mono-spaced font):

* *list::splice complexity with O(1) size
+------+-----------------+-----------------+
| * * *| * * from self * | * * from other *|
+------+-----------------+-----------------+
| one *| * * *O(1) * * * | * * *O(1) * * * |
+------+-----------------+-----------------+
| some | * * *O(1) * * * | * * O(some) * * |
+------+-----------------+-----------------+
| all *| * *not valid * *| * * *O(1) * * * |
+------+-----------------+-----------------+

In the "splice some from other" case, the splice function must compute:

std::distance(first, last);

where [first, last) represents the range "some" which is to be spliced
from other. So the constant on that linear complexity term is really
quite small (but of course not zero).

To combat this, Metrowerks (which has a O(1) list::size) offers yet
another splice overload:

void splice(iterator position, list& x, iterator first,
iterator last, size_type n);

Where a precondition is that the last parameter "n" is equal to
distance(first, last). It turns out that clients that use the "splice
some from other" functionality usually know, or can compute without
changing algorithmic complexity, distance(first, last). Furthermore, in
debug builds this precondition is checked (along with a host of other
checks in debug builds).

The result is that distance(first, last) no longer needs to be computed
within splice (in release mode) and so "splice some from other" is also
now truly O(1).

Now on to the question: What does O(1) list::size benefit?

Answer: Both client code, and the implementation of list.

I have had the opportunity to review much C++ production code using
std::list, which I have not written. Of the code I've reviewed,
list::size is used much, much more often than list::splice. And
list::size is sometimes used in a way that could turn a linear algorithm
into a quadratic one (such as the end condition in a for loop). Yet I
haven't noticed "splice some from other" being used in a context where
it could change the complexity of an algorithm. Note this is not to say
it isn't used in such a context. Just that I haven't actually seen it
in production code that I've reviewed.

Conclusion (anecdotal, not scientific): std::list clients ignorant of
this issue are more likely to be bitten by an O(N) list::size than by an
O(some) list::splice some from other.

In the implementation of std::list, there are some functions that can
take good advantage of an O(1) size (though it does not result in a
complexity reduction).

When list::resize is shrinking, an O(1) size can be used to choose
whether it is better to iterate from begin to the start of the erase
range, or from end to the start of the erase range. Indeed, I've seen
implementations of list::resize that have an O(N) size and the first
thing they do is compute distance(begin(), end()).

For operator== and operator!= for list one can check size() first (if it
is O(1)) before continuing with the element by element check,
potentially making these operations more efficient for common cases.

For list assignment (operator=, and assign overloads), the exception
safety guarantee can be increased from from basic to strong for the case
that T's assignment has a nothrow guarantee (at no extra expense).
Trying to do this with an O(N) size is computationally not practical.

list::sort is simpler to implement, and potentially slightly faster if
one can use an O(1) size to efficiently bisect the list in preparation
for a merge sort.

The cost of updating the size data within list to support an O(1) size
does not significantly effect any function, much less change its
complexity (except of course for the "splice some from other" function
already stated).

For my money, the pros outweigh the cons by a significant margin for an
O(1) list::size. Not the least of which is that (if standardized)
clients could depend upon list::size portably.

-Howard
Jul 23 '05 #14

P: n/a
In article <41*********************@news.dial.pipex.com>,
"Stephen Howe" <sjhoweATdialDOTpipexDOTcom> wrote:
In practice, only list::size appears to be vulnerable to this note.

You can find vehement supporters for this flexibility for list::size,
but I'm not one of them. I believe that not only is this flexibility
not needed, it makes list::size useless, and actually dangerous.


I don't see a problem. I would "cache" an internal count that used to
evaluate list::size().
If the internal count is valid it will O(1) to evaluate size(), otherwise
O(N).
If splice() is never called, size() would always be O(1).
And only with some versions of splice() are we in the dark as to the size()
afterwards, not all.

That gives near enough O(1) behaviour for both size() and splice() and only
alternative calls to each is the worse case.


<nod> This is a popular alternative suggestion to this conundrum.
However it is not without cost. Each internal list function which
depends upon an O(1) list::size, must now take into account that
list::size may not be O(1). list::size itself now must contain a
conditional expression, and may now be too big to be inlined. Instead
of simply returning a data member it has to ask if the cache is valid
and then possibly recompute it. Branches can be expensive in heavily
pipelined architectures.

And then there is the storage for the cache validity flag. You might
sacrifice only a bit, reducing the max_size of the list, and
complicating the extraction of the size. Or you could allocate a word
for this purpose to increase computational efficiency but now the
sizeof(list) has increased by 33%, making container<list<T>>
significantly more expensive.

Imho, either way, the cost isn't worth it. The cost isn't much, but it
buys even less.

-Howard
Jul 23 '05 #15

P: n/a
Howard Hinnant wrote:
<snip>
Now on to the question: What does O(1) list::size benefit?

Answer: Both client code, and the implementation of list.


One quick question. It would seem to me that if you wanted to allow
splice, and O(1) list::size, then each list node would have to contain a
pointer to some kind of central information bank about the list, which
stores the size. if you didn't have this then you would have no way of
accessing the size information to update it after a splice out of the
list. Also you wouldn't even be able to check if a splice had occured.
You could make the first/last node of the list a different type to every
other node and then whenever you splice out of a list cycle around to
it, but that would be expensive.

Basically, I don't see how you can make a list with O(1) size without
adding an extra item to every single node, which could potentially make
a list take 25% more space (for list<int> and sinilar things). That
isn't to be sniffed at?

Chris
Jul 23 '05 #16

P: n/a
"Howard Hinnant" <hi*****@metrowerks.com> wrote in message
news:hi***************************@syrcnyrdrs-02-ge0.nyroc.rr.com...
In article <ct**********@news.hispeed.ch>,
"Ivan Vecerina" <IN*************************@vecerina.com> wrote:
Could you list the trade-offs for std::list to store its item count?
I know that splice operations between std::list instances then become
more expensive, and I agree I would not care much about that.
Any other practical obstacle you have been encountering?
Sure.

Thank you :)
There are 5 possible valid splice situations: splicing from self or
splicing from another list, crossed with splicing 1 element, some
elements, or all elements. The O(1) size leads to an O(some) splice
in one of these five situations (best viewed in a mono-spaced font):

list::splice complexity with O(1) size
+------+-----------------+-----------------+
| | from self | from other |
+------+-----------------+-----------------+
| one | O(1) | O(1) |
+------+-----------------+-----------------+
| some | O(1) | O(some) |
+------+-----------------+-----------------+
| all | not valid | O(1) |
+------+-----------------+-----------------+

In the "splice some from other" case, the splice function must compute:

std::distance(first, last);

where [first, last) represents the range "some" which is to be spliced
from other. So the constant on that linear complexity term is really
quite small (but of course not zero).

I think there is an additional case here: if the source and
destination lists have different allocators, the items actually
have to be copied and the 'splice some/all from other' is O(N) anyway
- so there is no cost in counting them to maintain an O(1) list size.

I appreciate the thorough list you provide ( all points seem very
valid, only for the implementation of list::sort do I not see a
clear benefit ).
Since we are talking about splice, I dare ask another question:
I am currently using splice(1 item from self) to move items within
an std::list. The standard seems to say that iterators to moved
items are always invalidated by splice. But in the case where the
source and destination lists are the same, I see no practical reason
for the iterator to be invalidated (and all the implementations of
std::list I reviewed seem to agree). And I am using std::list just
for that reason: to be able to keep iterators to specific items.
But this does not seem to be guaranteed by the standard (ISO '98).

Is this a reasonable omission?
Is there a safe way to move items in an std::list without
invalidating iterators?
Also, am I right to believe that list::sort preserves iterators?

[NB: I asked similar questions in clc++m, with no enlightening reply
yet: "std::list::splice to move item within the same list[...]" ]
Thank you Howard.
Kudos for your excellent work, I keep fond memories of the early days
of CW on the Mac, which was the first C++ lib I used (and enjoyed!).
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Jul 23 '05 #17

P: n/a
"Chris" <ca*@cs.york.ac.uk> wrote in message
news:41************@cs.york.ac.uk...
Howard Hinnant wrote:
<snip>
Now on to the question: What does O(1) list::size benefit?

Answer: Both client code, and the implementation of list.


One quick question. It would seem to me that if you wanted to allow
splice, and O(1) list::size, then each list node would have to contain a
pointer to some kind of central information bank about the list, which
stores the size. if you didn't have this then you would have no way of
accessing the size information to update it after a splice out of the
list.


The splice member functions receives among its parameters a reference
to the list that owns the items to be transferred. Similarly, all
functions that add or remove items to and std::list already have a
reference (or 'this' pointer) to the owning list root/object.

So there is no need for individual list items (or iterators) to
store a pointer to the owning list instance - your concerns
are unwarranted.
Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Jul 23 '05 #18

P: n/a
Ivan Vecerina wrote:
"Chris" <ca*@cs.york.ac.uk> wrote in message
news:41************@cs.york.ac.uk...
Howard Hinnant wrote:
<snip>
Now on to the question: What does O(1) list::size benefit?

Answer: Both client code, and the implementation of list.


One quick question. It would seem to me that if you wanted to allow
splice, and O(1) list::size, then each list node would have to contain a
pointer to some kind of central information bank about the list, which
stores the size. if you didn't have this then you would have no way of
accessing the size information to update it after a splice out of the
list.

The splice member functions receives among its parameters a reference
to the list that owns the items to be transferred. Similarly, all
functions that add or remove items to and std::list already have a
reference (or 'this' pointer) to the owning list root/object.


Woops, thats what I get for trying to remember the splice function.
Apologises!

Chris
Jul 23 '05 #19

P: n/a
Howard Hinnant wrote:
<snip>
For my money, the pros outweigh the cons by a significant margin for an
O(1) list::size. Not the least of which is that (if standardized)
clients could depend upon list::size portably.
Thank you for the interest discussion about the pros and cons.
Personally I actually splice quite a bit, so I would perfer O(1) splice
and O(n) size, as I would see the O(1) splice as one of the big
advantages of std::list, and the (fixed) overhead of having and
maintaining a counter would not be useful for me personally.

However, one thing I think we can all agree on is that the standard
should either mandate an O(1) splice or an O(1) size, as at the moment
people like myself have to make sure we are using a compiler with O(1)
splice, and other people assume they get O(1) size. I like the idea of
having splice with an extra parameter, while that wouldn't fix my
problems, it would I suspect fix most other people's problems. However I
expect the chances of this ever getting mandated one way or the other is
slim. It I suspect wouldn't get snuck in as a defect report, so we'd
have to wait quite a while for a fix anyway.

Chris -Howard

Jul 23 '05 #20

P: n/a
In article <ct**********@news.hispeed.ch>,
"Ivan Vecerina" <NO**********************************@vecerina.com >
wrote:
In the "splice some from other" case, the splice function must compute:

std::distance(first, last);

where [first, last) represents the range "some" which is to be spliced
from other. So the constant on that linear complexity term is really
quite small (but of course not zero).
I think there is an additional case here: if the source and
destination lists have different allocators, the items actually
have to be copied and the 'splice some/all from other' is O(N) anyway
- so there is no cost in counting them to maintain an O(1) list size.
<nod> I intentionally ignored the unequal allocators case. I do discuss
this in a little more detail here:

http://www.open-std.org/jtc1/sc22/wg...004/n1599.html

This paper is about swap for containers of unequal allocators, but
splice is a closely related issue.

I feel that turning splice (and swap) into an element by element copy is
too dangerous because it silently turns a nothrow operation into a
throwing operation. This could silently invalidate client code which
has been crafted with a nothrow splice/swap in mind. If this situation
occurs, I'd prefer it be as noisy as possible the very first time it
gets executed instead of silently trying to please.

In addition to the changed exception guarantees, iterator validity also
would get silently messed up with an element-by-element copy (see below).
Since we are talking about splice, I dare ask another question:
I am currently using splice(1 item from self) to move items within
an std::list. The standard seems to say that iterators to moved
items are always invalidated by splice. But in the case where the
source and destination lists are the same, I see no practical reason
for the iterator to be invalidated (and all the implementations of
std::list I reviewed seem to agree). And I am using std::list just
for that reason: to be able to keep iterators to specific items.
But this does not seem to be guaranteed by the standard (ISO '98).

Is this a reasonable omission?
Is there a safe way to move items in an std::list without
invalidating iterators?

[NB: I asked similar questions in clc++m, with no enlightening reply
yet: "std::list::splice to move item within the same list[...]" ]
This is a defect in the standard, and has a proposed resolution with WP
status. WP status means that the committee has voted on the proposed
resolution and is happy with it, and has applied it to the working paper
for C++0X.

http://www.open-std.org/jtc1/sc22/wg...fects.html#250

The proposed resolution does what you believe is reasonable, and find in
practice. Although I did not initiate this issue, by coincidence, I did
write the current proposed wording.
Also, am I right to believe that list::sort preserves iterators?
Yes. Reference 23.1p11:
Unless otherwise specified (either explicitly or by defining a function in
terms of other functions), invoking a container member function or passing a
container as an argument to a library function shall not invalidate iterators
to, or change the values of, objects within that container. Thank you Howard.
Kudos for your excellent work, I keep fond memories of the early days
of CW on the Mac, which was the first C++ lib I used (and enjoyed!).


Thanks for your kind words.

-Howard
Jul 23 '05 #21

P: n/a
From: "Chris Jefferson" <ca*@cs.york.ac.uk>

| However, one thing I think we can all agree on is that the standard
| should either mandate an O(1) splice or an O(1) size, as at the moment
| people like myself have to make sure we are using a compiler with O(1)
| splice, and other people assume they get O(1) size.

That was my point: the standard may not be strict about the requirement for
size(), but
it does AFAICT mandate an iterator-range splice() to be of linear complexity
***. Hence, there is no point in having a O(n) size().

-Thorsten

*** I assume that explicit complexity requirements are not allowed to be
faster, though.
I guess I could use some training in reading the standard
Jul 23 '05 #22

P: n/a
In article <41***********************@news.sunsite.dk>,
"Thorsten Ottosen" <ne*****@cs.auc.dk> wrote:
That was my point: the standard may not be strict about the requirement for
size(), but
it does AFAICT mandate an iterator-range splice() to be of linear complexity
***. Hence, there is no point in having a O(n) size().

-Thorsten

*** I assume that explicit complexity requirements are not allowed to be
faster, though.
I guess I could use some training in reading the standard
See 17.3.1.3p5:
Complexity requirements specified in the library clauses are upper bounds,
and implementations that provide better complexity guarantees satisfy the
requirements.


-Howard
Jul 23 '05 #23

P: n/a

"Howard Hinnant" <hi*****@metrowerks.com> wrote in message
news:hi***************************@syrcnyrdrs-01-ge0.nyroc.rr.com...
| In article <41***********************@news.sunsite.dk>,
| "Thorsten Ottosen" <ne*****@cs.auc.dk> wrote:

| > *** I assume that explicit complexity requirements are not allowed to be
| > faster, though.
| > I guess I could use some training in reading the standard
|
| See 17.3.1.3p5:
|
| > Complexity requirements specified in the library clauses are upper bounds,
| > and implementations that provide better complexity guarantees satisfy the
| > requirements.

this is fine as long as it does not involve design tradeoffs---in the case of
list
it means a drastic change in performance across implementations. This is
different from a O(n) std::sort() where there is no tradeoff.

Anyway, it does mean that I was wrong and Scott was right.

-Thorsten
Jul 23 '05 #24

P: n/a

Consider this typical (SGI) implementation of size() and empty() for
std::vector... (paraphrasing from memory, I'm on my linux box now)
size_t size() const { return static_cast<size_t>( end() - begin() ); }

bool empty() const { return begin() == end(); }
Seem about the same?

What do you know about iterators for say std::vector??? They're really
pointers to the contained type. (in every implementation I've looked at)

So what you really have in empty() is a simple pointer comparison, the
result of which will set an architecture dependent flag (eg. the zero
flag in the CPU...) that can be tested. (usually a subtraction and test
of the zero flag)

But end() - begin() is a pointer difference. That means a subtraction
of the two, and a division by sizeof(T) for whatever type is in the
vector... This gives you the offset between the pointers in T sized
units... Which you can then compare to 0 to set the CPU flag... So, it
would appear that the size() idiom requires an additional integral
subtraction and division as compared to simply calling empty(). That,
IMHO is why we should use empty() when we mean empty(), not size() == 0...

This came up at work a couple of weeks ago and I tested it (on SGIs)
doing a zillion calls of each, both with empty and non-empty vectors and
as expected, the size() calls were slower.

Jul 23 '05 #25

P: n/a

"Phil Staite" <ph**@nospam.com> wrote in message
news:41**************@nospam.com...
|
| Consider this typical (SGI) implementation of size() and empty() for
| std::vector... (paraphrasing from memory, I'm on my linux box now)
|
|
| size_t size() const { return static_cast<size_t>( end() - begin() ); }
|
| bool empty() const { return begin() == end(); }
|

| So what you really have in empty() is a simple pointer comparison, the
| result of which will set an architecture dependent flag (eg. the zero
| flag in the CPU...) that can be tested. (usually a subtraction and test
| of the zero flag)
|
| But end() - begin() is a pointer difference. That means a subtraction
| of the two, and a division by sizeof(T) for whatever type is in the
| vector... This gives you the offset between the pointers in T sized
| units... Which you can then compare to 0 to set the CPU flag... So, it
| would appear that the size() idiom requires an additional integral
| subtraction and division as compared to simply calling empty(). That,
| IMHO is why we should use empty() when we mean empty(), not size() == 0...

This is a good point although the biggest problem arises when size() has O(n)
complexity.

Howver, for your reason, Eric Niebler's comming BOOST_FOREACH() library
definitely uses

for( ; !empty( range ); ++range ) { ... }

instead of checking agaist size() == 0. Just imagine the performace impact
when
iterating over a subrange of a list.

-Thorsten
Jul 23 '05 #26

This discussion thread is closed

Replies have been disabled for this discussion.