Determine the lexicographical ordering of two sequences

Source code

Declaration

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             Compare comp);

Description Each function compares two ranges [ first1, last1) \ and [ first2, last2) lexicographically. In the first function, element comparisons are done using operator<, while in the second they are done using the function object comp .

Type requirements

• InputIterator1 and InputIterator2 must be at least input iterators .
• Compare must be a function object type that provides int operator()(S, S), where S is the dereference type of both InputIterator1 and InputIterator2.

Group Sorting and related operations.

Time complexity Linear.

The number of compare operations is at most i, the smallest index at which a disagreement occurs.

Space complexity Constant.

Mutative? No.

Details For the sequence in the range [ first1, last1) and the sequence

in the range [ first2, last2) , let i be the smallest index such that one of or i = n or i = m holds. Then the value returned by lexicographical_compare is:

1. true (ie. non-zero) if i < n and i < m and , or i = n < m

2. false (ie. zero) if i < n and i < m and , or .

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.