algorithm specialisations for vector/basic_string iterators

[Philip Martin <pm at corris dot dircon dot co dot uk>]

Hi

The algorithm specialisations that used to be used for
vector/basic_string iterators when they were pointers do not get used
with the __normal_iterator class.  That's not very surprising, however
it can have a significant effect on performance.

The problems occurs both within the class code in cases like:

    // case 1
    std::vector<int> v1( 3 );
    std::vector<int> v2( v1.begin(), v1.end();

and outside the class code:

    // case 2
    std::vector<int> v1( 3 );
    int a[3[ = { 1, 2, 3 };
    std::copy( a, a + 3, v1.begin() );

I think it is reasonable to expect the specialisations to be used in
all cases when replacing __normal_iterators with their underlying
iterator would cause a specialisation to be invoked.  The code in the
vector class could be altered to solve case 1 above, but that can not
be done in case 2.

Taking copy as an example a possible solution is to provide the
following template functions in std:: (possibly in stl_iterator.h)

template<typename _Tp, typename _C, typename _T>
_T copy(__normal_iterator<_Tp, _C> __first,
        __normal_iterator<_Tp, _C> __second, _T __result);

template<typename _T, typename _Tp, typename _C>
__normal_iterator<_Tp, _C> copy(_T __first, _T __second,
                                __normal_iterator<_Tp, _C> __result);

template<typename _Tp1, typename _C1, typename _Tp2, typename _C2>
__normal_iterator<_Tp2, _C2> copy(__normal_iterator<_Tp1, _C1> __first,
                                  __normal_iterator<_Tp1, _C1> __second,
				  __normal_iterator<_Tp2, _C2> __result)

These would extract the underlying iterator and call the standard
copy() function.  Is that a reasonable solution?  An alternative might
be to use some sort of traits mechanism to dispatch __normal_iterators
to the appropriate specialisation.

A related point: I don't see any simple way for the testsuite to check
that the right specialisation gets called.  I suppose one could build
an executable and use nm/c++filt/grep to look for certain names, but
that sounds a bit hairy. Does anybody have any better ideas?

Philip