Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Do tuples have an implicit lexicographical comparison?

Tags:

c++

c++11

tuples

When sorting eg a vector of pairs :

vector<pair<int, double>> v;
sort(v.begin(), v.end());

You don't need to specify a sorting criterion to have a sorting based on the lexicographical order of the pairs since, when not elseway specified, a lexicographical comparison applies.

Is a similar behaviour standard for tuples as well ?

In VS2012 this compiles

vector<tuple<int, double, char>> tv;
sort(tv.begin(), tv.end());

but is it standard mandated to do so ?

like image 841
Nikos Athanasiou Avatar asked May 23 '14 10:05

Nikos Athanasiou


3 Answers

They do, see operator==,!=,<,<=,>,>=(std::tuple):

operator==
operator!=
operator<
operator<=
operator>
operator>=

lexicographically compares the values in the tuple

like image 170
Maxim Egorushkin Avatar answered Oct 16 '22 17:10

Maxim Egorushkin


According to standard [20.4.2.7 Relational operators]: Yes

Overloaded operator for tuple:

 template<class... TTypes, class... UTypes>
 constexpr bool operator<(const tuple<TTypes...>& t, 
 const tuple<UTypes...>& u);

Returns: The result of a lexicographical comparison between t and u.

The result is defined as:

(bool)(get<0>(t) < get<0>(u)) ||(!(bool)(get<0>(u) < get<0>(t)) && ttail < utail)

where rtail for some tuple r is a tuple containing all but the first element of r. For any two zero-length tuples e and f, e < f returns false.

like image 6
101010 Avatar answered Oct 16 '22 19:10

101010


In 20.4.2.7 Relational operators [tuple.rel]

template<class... TTypes, class... UTypes>
bool operator<(const tuple<TTypes...>& t, const tuple<UTypes...>& u);

Returns: The result of a lexicographical comparison between t and u. The result is defined as:

(bool)(get<0>(t) < get<0>(u)) || (!(bool)(get<0>(u) < get<0>(t)) && ttail < utail) 

where rtail for some tuple r is a tuple containing all but the first element of r. For any two zero-length tuples e and f, e < f returns false.

So no, they don't have an implicit one, they have an explicit

like image 4
Nikos Athanasiou Avatar answered Oct 16 '22 17:10

Nikos Athanasiou