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

[Gawain Bolton]

This patch introduces new classes for constant iterators for std::list 
and the _Rb_tree class which is used to implement the 
std::{multi}*{map|set} containers.

The reasons for doing this are:

    * code clarity/simplicity
    * eliminate need for const_casts
    * a single template argument is required for the iterator classes.
          o this results in less debug info and clearer error messages
    * eliminates need for global comparison functions to compare iterators
          o less pollution in std namespace and the code is more readable

The only drawbacks are that there is slightly more code in the header 
files and the new const_iterator classes are basically clones of the 
iterator class.  However, I do not think this is a problem since the 
functions are simple one-liners and the code in question is within the 
same header file, thus this will not be a maintenance problem.

Here's an example of an error message when erasing using a constant 
iterator as provided by the patch:
test.cc: In member function `void test_erase()':
test.cc:375: error: no matching function for call to `std::map<Fred,
   unsigned int, std::less<Fred>, std::allocator<std::pair<const Fred, 
unsigned
   int> > >::erase(std::_Rb_tree_const_iterator<std::pair<const Fred, 
unsigned
   int> >&)'

Here's the equivalent error message currently given without an explicit 
const iterator class:
test.cc: In member function `void test_erase()':
test.cc:375: error: no matching function for call to `std::map<Fred,
   unsigned int, std::less<Fred>, std::allocator<std::pair<const Fred, 
unsigned
   int> > >::erase(std::_Rb_tree_iterator<std::pair<const Fred, unsigned 
int>,
   const std::pair<const Fred, unsigned int>&, const std::pair<const Fred,
   unsigned int>*>&)'

Other changes made by this patch include:

    * std:list
          o Only erase contents in destructor.
          o Eliminated static_casts where possible.
    *  _Rb_tree class:
          o Only erase contents in destructor.
          o Eliminate unnecessary initialization in assignment operator.
          o Optimize for the nominal case by not checking whether
            container is empty in clear().
          o Re-order test in _M_insert() to improve performance.
          o Move initialization of new node's left & right pointers to
            src/stl_tree.cc to where new node's colour is initialized
            and to reduce the amount of inline code.
          o Use  _M_leftmost() and _M_end() to improve readability where
            appropriate.

This patch has been tested on i686-pc-linux-gnu.  Performance tests were 
done using Bjarne Stroustrup's Standard Container Benchmark as found here:
 http://groups.google.fr/groups?q=standard+container+benchmark+group:comp.lang.c%2B%2B.moderated&hl=en&lr=lang_en|lang_fr&ie=UTF-8&group=comp.lang.c%2B%2B.moderated&selm=HFnqCB.6Js%40research.att.com&rnum=1

No changes were made to the benchmark code.  It was compiled with -O2 
and executed several times with and without the patch as the numbers do 
vary a bit from one run to the next.  The data sets reported are neither 
the best nor worst obtained in either case.

Only the performance of list, set and multiset is changed by this patch 
so only the last three columns of information are of interest concerning 
this patch.

Here are the numbers using mainline CVS:
size    array   vector(1)  vector(2)  deque   list    set     multiset
10      3.06    3.19       3.25       5.85    13.63   5.69    10.04
100     1.89    1.89       1.94       3.54    7.26    3.97    6.14
1000    1.82    1.78       1.94       3.14    6.38    3.55    5.62
10000   1.86    1.90       2.06       3.17    7.43    4.20    6.75
100000  2.12    2.21       2.26       3.23    9.19    6.44    8.88
(1) with pointers
(2) with iterators

Here are the numbers using 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

-- 
Gawain Bolton
Coignieres, France
PGP Info: Key server: http://wwwkeys.pgp.net
          Key id: 6EBEDEA6
          Fingerprint: 65C0 0030 21D1 7A01 546A  E7DB D60F 47E0 6EBE DEA6

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