This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
splicing / size on lists
- From: Chris Jefferson <caj at cs dot york dot ac dot uk>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Mon, 31 Jan 2005 10:37:35 +0000
- Subject: splicing / size on lists
Those of you who read comp.lang.c++ may have noticed a recent discussion
(Effective STL Item 3 (size() vs. empty())). The main off-shoot of this
is that there must be a trade-off made between splice() being constant
time and size() begin constant time.
The only splice that can cause problems is splicing a range of iterators
from one list to another. According to the standard this is
(23.2.2.4-14) linear time, whereas in 23.1, Table 65, size() "should
have constant complexity", where "should" means (according to ISO):
- used to indicate that among several possibilities one is recommended
as particularly suitable, without mentioning or excluding others,
- a certain course of action is preferred but not necessarily required
While it is true that the current list is standards-compliant, I do
agree that it looks like we may have made the wrong tradeoff. Adding
O(1) size would I believe
Do what 23.2.2.4-14 says, make splice of a range between different lists
have O(n) where n=last-first.
Add some small constants to think like insert, remove, etc, but overall
be a good thing (it would involve adding another member to list of
course, although not to each node, so wouldn't be too expensive. It
would have to be in so_7 of course)
Does anyone have any comments / suggestions?