This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of TC1 status.

### 142. lexicographical_compare complexity wrong

Section: 25.8.11 [alg.lex.comparison] Status: TC1 Submitter: Howard Hinnant Opened: 1999-06-20 Last modified: 2016-01-28

Priority: Not Prioritized

View all issues with TC1 status.

Discussion:

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)

Proposed resolution:

Change 25.8.11 [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]