splicing / size on lists

[Chris Jefferson]

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?