Update: [Patch]: Separate classes for constant iterators and miscellaneous optimizations

[Gawain Bolton]

This is an update for the patch posted previously here:
   http://gcc.gnu.org/ml/libstdc++/2003-08/msg00018.html

It fixes a bug that was present in the previous patch in the 
_Rb_tree::_M_insert() function.

This patch also moves even move code out of the stl_tree.h header file 
into the stl_tree.cc implementation file than the previous patch.

This results in a reduction in code size for applications inserting 
elements in the std::{set|map|multiset|multimap} containers.

With respect to DRs about const_iterators and iterators as hinted at here:
   http://gcc.gnu.org/ml/libstdc++/2003-08/msg00019.html

I found the following two items:
   http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#179
   http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#322

Concerning Item 179 "Comparison of const_iterators to iterators doesn't 
work", I have added the required global comparison operators so that 
comparisons between constant and non-constant iterators are possible. 
This is what I understand from the proposed resolution of this DR - 
although the notes are confusing.

As for Item 322 " iterator and const_iterator should have the same value 
type", the constant and non-constant iterators in this patch have the 
same value_type so I don't see any issue here.

Otherwise, the patch is as previously posted and explained.

The new performance numbers using Bjarne Stroustrup's Standard Container 
Benchmark are very similar to the previous patch - perhaps slightly 
better even.

For completeness, here is the new set of numbers obtained with the patch:

size    array   vector(1)  vector(2)   deque   list    set     multiset
10      3.15    3.16       3.31        5.64    10.42   5.73    9.84
100     1.85    1.87       1.95        3.48    5.13    3.90    6.07
1000    1.79    1.78       1.97        3.21    4.68    3.41    5.41
10000   1.86    1.85       2.04        3.20    5.44    3.96    6.24
100000  2.05    2.04       2.17        3.23    7.53    5.83    8.40
(1) with pointers
(2) with iterators

Cheers,


Gawain

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: libstdc++_patch_20030807.txt
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030807/23731842/attachment.txt>