RE: [Dev-C++] STL Map question

[Hossein H. <ult...@em...>]

Dear Ioannis,

I have just posted a response of this message to Shane, but
unfortunately I haven't set the header to have a Cc for the Dev-Cpp
Users. There, I have mentioned that your following assertion is most
likely to be wrong. Anyway, I will repeat it one time more to make it
clear to the group.

> Eh? Why? Both have the same speed, actually empty is usually 
> 
> // inside the class definition
> bool empty() const {  return size()==0; }

This can be the case, but that isn't always true.

I know that holds for many of STL platforms, but they do not have to
follow that way.

> since map has to keep track of its size. 

Has it? No, I don't think so! But I will be pleased if you can prove
me your assertion by mentioning its address in Standard. I don't think
that beeing the case, as I have found the followings in the STL Bible,
i.e., Generic Programming and the STL:

"size() is linear in container's size. (For many containers, such as
vector, and deque, size() is O(1). This satisfies the requirement that
it be O(n).)

maz_size() and empty() are amortised constant time."

(If you want me to address the citation precisely, it is in Section
9.1.1, i.e., Container. And the complete bibliography is:

Matthew H. Austern, Generic Programming and the STL: Using and
Extending the C++ Standard Template Library, Addisson Wesley, 1999,
ISBN: 0-201-30956-4.)

These lines make me to become more sure that there isn't any guarantee
in the Standard for size() and empty() to be equal in the sense of
runtime.

> In any case consider them as equal
> (an equality comparison doesn't take time!).

I don't know anything about the STL platform beeing used. But even if
the Standard has mentioned that O(empty()) == O(size()), that platform
may not be Standard-compliant. Therefore, size() may be a calculating
member function, meaning that it may compute the size and hence not be
constant time. But empty() is more likely to be just returning the
state of an internal flag. And that's why I mentioned to choose
empty() instead of size(). Because, the platform may well have
considered to compute the size of map every time size() is invoked.
And that beeing the case, there may be some (offencing) optimisations
the platform have chosen, and those are causing some unexpected
exception or memory invalidation that the platform itself, doesn't
know.

You may still think that there empty() and size() have the same
runtime. But that doesn't mean there are equal in any case. If you
have any doubt on this issue, consider Item 4 of Effective STL.

(Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of
the Standard Template Library, Addison-Wesley, 2001, 
ISBN: 0-201-74962-9.)

Regards,
--Hossein
-- 
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup

CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
http://corp.mail.com/careers