L'ordre lexicographique est un ordonnancement bien connu et plutôt intuitif, au sens où il rejoint, quand on se limite aux mots d'un langage comme le français ou l'anglais, ce qu'on nomme l'ordre alphabétique. En mots :
Sur le plan algorithmique, supposant deux séquences de valeurs et que nous représenterons par des vector<int> ci-dessous pour simplifier le propos, on peut illustrer l'algorithme comme suit (implémentation naïve) :
#include <vector>
#include <algorithnm>
using namespace std;
bool precede_lexicographiquement(const vector<int> &v0, const vector<int> &v1) {
const auto m = v0.size(),
n = v1.size()
ppetit = min(m,n);
for(vector<int>::size_type i = 0; i < ppetit; ++i) {
if (v0[i] < v1[i])
return true;
if (v1[i] < v0[i])
return false;
}
// ici, v0 précède v1 seulement si m < n, voyez-vous pourquoi?
return m < n;
}Selon cet algorithme, nous aurons les résultats suivants :
| v0 | v1 | precede_lexicographiquement(v0,v1) |
|---|---|---|
true |
||
false |
||
false |
||
false |
||
true |
||
true |
||
false |
||
false |
Dans la bibliothèque standard de C++, on trouve des fonctions comme std::lexicographical_compare() qui font, de manière bien moins naïve, le même travail que precede_lexicographiquement() ci-dessus mais en travaillant à l'aide de séquences standards, ce qui les rend plus généraux en plus d'être plus efficaces. Comme toujours, préférez la version standard à une version maison.
Le concept d'ordonnancement lexicographique ne se limite pas aux séquences. On peut par exemple l'étendre aux objets :
#include <string>
class Personne {
public:
using str_type = std::string;
private:
str_type nom_,
prenom_;
public:
Personne(const str_type &nom, const str_type &prenom)
: nom_{ nom }, prenom_{ prenom }
{
}
const str_type& nom() const noexcept {
return nom_;
}
const str_type& prenom() const noexcept {
return prenom_;
}
//
// Implémentation lexicographique et l'opérateur <
//
bool operator<(const Personne &autre) const noexcept {
if (nom() < autre.nom()) return true;
return nom() == autre.nom() && prenom() < autre.prenom();
}
// ...
};Certaines propositions sont sur la table pour standardiser ce comportement, et l'offrir par défaut pour les classes écrites en C++. Évidemment, cela présume que le compilateur pourra déduire dans quel ordre comparer les attributs, ce qui influencerait l'ordre de leur déclaration notez que cet impact ne serait pas innocent, car la disposition des attributs dans un objet impacte directement la vitesse d'exécution des programmes et l'espace occupé par les objets en mémoire.
Certains types implémentent implicitement la comparaison lexicographique, par exemple std::pair et sa généralisation std::tuple. Ainsi, on pourrait réécrire Personne ci-dessus sous la forme suivante :
#include <string>
#include <tuple>
class Personne {
public:
using str_type = std::string;
private:
std::tuple<str_type, str_type> identite;
public:
Personne(const str_type &nom, const str_type &prenom) : identite{ nom, prenom } {
}
const str_type& nom() const noexcept {
return std::get<0>(identite);
}
const str_type& prenom() const noexcept {
return std::get<1>(identite);
}
//
// Implémentation lexicographique et l'opérateur <
//
bool operator<(const Personne &autre) const noexcept {
return identite < autre.identite;
}
// ...
};Ceci peut simplifier la programmation à certains égards, surtout si le nombre d'attributs à comparer est grand. Une alternative amusante est de conserver la représentation attribut-par-attribut d'une Personne et de recourir à des std::tuple temporaires au moment de faire la comparaison lexicographique seulement. Nous aurions alors :
#include <string>
#include <tuple>
class Personne {
public:
using str_type = std::string;
private:
str_type nom_,
prenom_;
public:
Personne(const str_type &nom, const str_type &prenom) : nom_{ nom }, prenom_{ prenom } {
}
const str_type& nom() const noexcept {
return nom_;
}
const str_type& prenom() const noexcept
return prenom_;
}
//
// Implémentation lexicographique et l'opérateur <
//
bool operator<(const Personne &autre) const noexcept {
return std::tie(nom_, prenom_) < std::tie(autre.nom_, autre.prenom_);
}
// ...
};Remarquez le recours à std::tie(), qui crée un tuple respectant l'ordonnancement des tests souhaités pour notre classe. Ceci découple l'ordre des tests de celui de la déclaration des attributs. Étonnamment, le recours à std::tie() donne du code essentiellement optimal, du fait que cette fonction crée un tuple de références sur des lvalue, donc un objet extrêmement léger.
Quelques liens pour enrichir le propos.
