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

[Howard Hinnant]

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

[/QUOTE]

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/wg21/docs/papers/2004/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/wg21/docs/lwg-defects.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

 

[Thorsten Ottosen]

From: "Chris Jefferson" <[email protected]>

| 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

 

[Howard Hinnant]

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

 

[Thorsten Ottosen]

| In article <[email protected]>,

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

 

[Phil Staite]

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.

 

[Thorsten Ottosen]

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