Title
lexicographical_compare complexity wrong
Status
tc1
Section
[alg.lex.comparison]
Submitter
Howard Hinnant

Created on 1999-06-20.00:00:00 last changed 163 months ago

Messages

Date: 2010-10-21.18:28:33

Proposed resolution:

Change [alg.lex.comparison] complexity to:

At most 2*min((last1 - first1), (last2 - first2)) applications of the corresponding comparison.

Change the example at the end of paragraph 3 to read:

[Example:

    for ( ; first1 != last1 && first2 != last2 ; ++first1, ++first2) {
      if (*first1 < *first2) return true;
      if (*first2 < *first1) return false;
    }
    return first1 == last1 && first2 != last2;
   
--end example]

Date: 1999-06-20.00:00:00

The lexicographical_compare complexity is specified as:

     "At most min((last1 - first1), (last2 - first2)) applications of the corresponding comparison."

The best I can do is twice that expensive.

Nicolai Josuttis comments in lib-6862: You mean, to check for equality you have to check both < and >? Yes, IMO you are right! (and Matt states this complexity in his book)

History
Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg1668
1999-06-20 00:00:00admincreate