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

[Ioannis V. <iv...@em...>]

> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Hossein Haeri
> Sent: Saturday, July 12, 2003 11:39 PM
> To: dev...@li...
> Subject: RE: [Dev-C++] STL Map question
>=20
>=20
> Dear Ioannis,
>=20
> 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.
>=20
> > Eh? Why? Both have the same speed, actually empty is usually=20
> >=20
> > // inside the class definition
> > bool empty() const {  return size()=3D=3D0; }
>=20
> This can be the case, but that isn't always true.
>=20
> I know that holds for many of STL platforms, but they do not have to
> follow that way.


Yes. Any implementor can follow his way, the standard defines only the
template interface but the above is a reasonable implementation. And I =
got
it straight  from TC++PL 3. :-)



>=20
> > since map has to keep track of its size.=20
>=20
> 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:
>=20
> "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).)
>=20
> maz_size() and empty() are amortised constant time."



It is not required by the standard but it would be prudent to not =
calculate
size() every time it is called. Also if I would have a choice between
storing information on whether it is empty or the size I would have =
chosen
the size since the empty can be estimated by the size and would require =
less
checks in the instance of the code where I would have placed a lot of =
checks
if the empty value is true or false and change it.

Anyway as I said only the interface is required by the standard but in =
C++
world all strive for maximum performance.



=20
> (If you want me to address the citation precisely, it is in Section
> 9.1.1, i.e., Container. And the complete bibliography is:
>=20
> Matthew H. Austern, Generic Programming and the STL: Using and
> Extending the C++ Standard Template Library, Addisson Wesley, 1999,
> ISBN: 0-201-30956-4.)
>=20
> 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.



Of course there is not. Nor there is any guarantee on which is faster =
nor
whether it takes milliseconds, seconds and weeks. However as I said what =
I
provided is a reasonable implementation.



>=20
> > In any case consider them as equal
> > (an equality comparison doesn't take time!).
>=20
> I don't know anything about the STL platform beeing used. But even if
> the Standard has mentioned that O(empty()) =3D=3D 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.


Yes. It may also calculate the 1000 first digits of pi (3.14..) in the
meantime, but we are discussing reasonable implementations and having to
calculate the size() of every container that provides size() each time =
it is
called (and it may have millions) doesn't sound too reaaonable to me.


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


Yes, it may has decided manyy things. However we mau assume that all =
member
functions are maximally efficient, else throw the platform away!



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


Read TC++PL 3. Straight from the creator of C++.






Ioannis Vranos
=20
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net