Movatterモバイル変換

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

142. lexicographical_compare complexity wrong

Section: 26.8.11[alg.lex.comparison]Status:TC1Submitter: Howard HinnantOpened: 1999-06-20Last modified: 2016-01-28

Priority:Not Prioritized

View all issues withTC1 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 forequality you have to check both < and >? Yes, IMO you areright! (and Matt states this complexity in his book)

Proposed resolution:

Change 26.8.11[alg.lex.comparison] complexity to:

At most2*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]