# 11 Algorithms library [algorithms]

## 11.5 Sorting and related operations [alg.sorting]

### 11.5.8 Lexicographical comparison [alg.lex.comparison]

``` template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, class Proj1 = identity, class Proj2 = identity, IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>> bool lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, class Proj1 = identity, class Proj2 = identity, IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>> Comp = less<>> bool lexicographical_compare(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); ```

Returns: true if the sequence of elements defined by the range [first1,last1) is lexicographically less than the sequence of elements defined by the range [first2,last2) and false otherwise.

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

Remarks: If two sequences have the same number of elements and their corresponding elements are equivalent, then neither sequence is lexicographically less than the other. If one sequence is a prefix of the other, then the shorter sequence is lexicographically less than the longer sequence. Otherwise, the lexicographical comparison of the sequences yields the same result as the comparison of the first corresponding pair of elements that are not equivalent.

```for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
if (invoke(comp, invoke(proj1, *first1), invoke(proj2, *first2))) return true;
if (invoke(comp, invoke(proj2, *first2), invoke(proj1, *first1))) return false;
}
return first1 == last1 && first2 != last2;
```

Remarks: An empty sequence is lexicographically less than any non-empty sequence, but not less than any empty sequence.