Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Effective STL Item 4 (size() vs. empty())

Reply
Thread Tools

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

 
 
Matthias
Guest
Posts: n/a
 
      01-30-2005
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
 
Reply With Quote
 
 
 
 
Gianni Mariani
Guest
Posts: n/a
 
      01-30-2005
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.
 
Reply With Quote
 
 
 
 
Duane Hebert
Guest
Posts: n/a
 
      01-30-2005

"Matthias" <(E-Mail Removed)> wrote in message news:ctikpk$dv0$05$(E-Mail Removed)-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.


 
Reply With Quote
 
Fabio Fracassi
Guest
Posts: n/a
 
      01-30-2005
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


 
Reply With Quote
 
Matthias
Guest
Posts: n/a
 
      01-30-2005
Thanks everybody. I think I got the point.

--
Regards,
Matthias
 
Reply With Quote
 
Thorsten Ottosen
Guest
Posts: n/a
 
      01-30-2005

"Matthias" <(E-Mail Removed)> wrote in message
news:ctikpk$dv0$05$(E-Mail Removed)-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


 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      01-30-2005
Thorsten Ottosen wrote:
> "Matthias" <(E-Mail Removed)> wrote in message
> news:ctikpk$dv0$05$(E-Mail Removed)-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 ?
 
Reply With Quote
 
Thorsten Ottosen
Guest
Posts: n/a
 
      01-30-2005

"Gianni Mariani" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
| Thorsten Ottosen wrote:
| > "Matthias" <(E-Mail Removed)> wrote in message
| > news:ctikpk$dv0$05$(E-Mail Removed)-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


 
Reply With Quote
 
Peter Koch Larsen
Guest
Posts: n/a
 
      01-30-2005

"Thorsten Ottosen" <(E-Mail Removed)> skrev i en meddelelse
news:41fd3299$0$48327$(E-Mail Removed)...
>
> "Matthias" <(E-Mail Removed)> wrote in message
> news:ctikpk$dv0$05$(E-Mail Removed)-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


 
Reply With Quote
 
Howard Hinnant
Guest
Posts: n/a
 
      01-30-2005
In article <41fd51d3$0$48322$(E-Mail Removed)>,
"Thorsten Ottosen" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question about Effective STL item 7 Piotr C++ 2 01-16-2006 11:03 PM
more effective c++ item 31 cfchou@gmail.com C++ 4 09-27-2005 09:15 AM
Effective C++ - item 7 (memory mgt). FBergemann@web.de C++ 1 08-07-2005 12:06 PM
meyers: Item 12: Effective C++ John C++ 4 04-27-2005 04:18 PM
Item 13 in Meyer's Effective C++ Don Kim C++ 9 05-23-2004 07:02 PM



Advertisments