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.
Section: 26.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 26.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]