[Bug libstdc++/32908] New: Miss lexicographical_compare random access override

[chris at bubblescope dot net]

lexicographical_compare is used to implement operator< and friends on all
containers. The code is not optimised for random_access iterators, where we can
find which list is the longest before starting and save one comparison every
loop.

Replace the following line:

for (; __first1 != __last1 && __first2 != __last2;
           ++__first1, ++__first2)

With:

      _InputIterator1 __newlast1 = __first1 + 
                std::min(__last1 - __first1, __last2 - __first2);

      for (; __first1 != __newlast1;
           ++__first1, ++__first2)

(or something similar.

This produces a 15% speed improve on operator< on vector<int>.

If this bug remains I will write up code myself, but I am unable to compile g++
from source at the moment.


-- 
           Summary: Miss lexicographical_compare random access override
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: chris at bubblescope dot net


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32908