473,701 Members | 2,731 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

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
25 7582
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::empt y 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

"Matthias" <no****@digital raid.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
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
Thanks everybody. I think I got the point.

--
Regards,
Matthias
Jul 23 '05 #5

"Matthias" <no****@digital raid.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
Thorsten Ottosen wrote:
"Matthias" <no****@digital raid.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

"Gianni Mariani" <gi*******@mari ani.ws> wrote in message
news:15******** ************@sp eakeasy.net...
| Thorsten Ottosen wrote:
| > "Matthias" <no****@digital raid.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

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

"Matthias" <no****@digital raid.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
In article <41************ ***********@new s.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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
3413
by: lionel pacoud | last post by:
Hi, ok, so I have pictures that I store in Postgres (7.2.4) via JDBC. if the size of my picture is small (less than 1ko) it's ok, there is no pb. but I never succed to put a bigger picture. the response is : java.sql.SQLException: ERROR: index_formtuple: data takes 211980 bytes, max is 8191... or java.sql.SQLException: ERROR: btree: index item size 2768 exceeds
5
2681
by: Gernot Frisch | last post by:
Hi, can I tell e.g. a queue that it should re-allocate 512 elements each time it comes to it's boundaries? -- -Gernot int main(int argc, char** argv) {printf ("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}
9
3730
by: R.Z. | last post by:
i was wondering whether it pays off in terms of memory use to maintain lots of empty deques (it would be convenient for my algorithms but memory use is more important). and does the size of a deque depends on the size of its members even if the deque is empty? is there at all a way to check out how much memory my deque occupies? i've read that the sizeof operator cannot be used with dynamically allocated arrays so i figured it wouldn't give...
17
3385
by: TheMadHatter | last post by:
yello, Quick Q: With regards to ram use, there really isnt any memory savings if I use type bool, vs int....... is there? If I remmeber correctly from a microcontroller course, the smallest addressable unit is an int. All rules still apply for todays machines, right? Thanks in advance.
26
6261
by: Ed L. | last post by:
Here's some of my current notions on pgsql performance tuning strictly as it relates to pgsql tuning parameters in the context of a dedicated linux or hpux server. I'm particularly focusing on the shared_buffers setting. I invite any corrective or confirming feedback. I realize there are many other hugely important performance factors outside this scope. One key aspect of pgsql performance tuning is to adjust the memory ...
3
5877
by: Sally Sally | last post by:
I have a very basic question on the two parameters shared buffers and effective cache size. I have read articles on what each is about etc. But I still think I don't quite grasp what these settings mean (especially in relation to each other). Since these two settings seem crucial for performance can somebody explain to me the relationship/difference between these two settings and how they deal with shared memory. Thanks much Sally ...
0
988
by: Gabriele | last post by:
For didactical purposes I'm trying to create a C Template Item (an empty *.c file) (the header template file is already included) and a C empty project with all the settings to allow only C programming. Following the instructions of some articles I read, i should be able to export my template item by selecting a c file I previously created (and included in a C project) and by clicking on Export Template... that is disabled!! How can I...
1
1932
by: mahesh.kanakaraj | last post by:
Hi All, I have a confusion in finding the 'effective content' of a complex type definition in a XML Schema. I shall give you an example situation to clearly explain my problem. Let's have an element declaration as follows:
15
2004
by: Igal | last post by:
hay, i have this werid problem with my book adding function, this how it looks book* AddBook(book *bp, unsigned *size) { .... //then i use realloc to allocate space for the new item in the bp pointer bp = (book*)realloc(bp, sizeof(book)); .... }
0
8736
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8649
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9229
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8934
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7824
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6571
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5904
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
1
3102
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2398
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.