Re: The design and evolution of STL containers, the case of std::map.size()
AlfC wrote:
1) keeping the counter current takes an extra operation each time we
add a subtract an element (or a key/value pair), so there is a hidden
cost there of keeping .size() to be O(1) operation.
Considering the amount of operations required to insert or remove
elements from a binary tree, incrementing/decrementing an integral
variable is certainly not a bottleneck. Removing this would probably
have no significant effect on the overall speed of the container.
2) not every application of std::map needs to know the size of the
container, so why pay for what you don't need?(TM)
You pay probably something like 0.1% slower insertion and deletion.
Not a big deal IMO.
The same question applies to other containers, like std::list or
std::set.
I wish std::list had an element counter like std::map has.
Unfortunately in most implementations it doesn't, and std::list::size()
is an O(n) operation.
[An exception is std::vector where .size() is O(1)
absolutely for free (just calculated as .end()-.begin()).]
Actually calculating end()-begin() (which most implementations of
std::vector::size() do) is slower than returning a variable. Not by
much, of course, but still.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]