ENIB LANG-CPP 03_Generic - Programmation générique

{} Les fonctions génériques

Les fonctions génériques sont des fonctions dont la définition exprime un algorithme qui manipule des données dont le type n'est pas encore connu : elles sont qualifiées de template.
(https://en.cppreference.com/w/cpp/language/function_template)
Ce n'est qu'au moment où nous invoquons ces fonctions que le type des données (généralement ceux des paramètres effectifs) est connu.
Le compilateur reformule alors l'algorithme en substituant les types template par les types exacts détectés lors de l'appel : il s'agit de l'instanciation des templates.

Tout se passe alors comme si nous venions tout juste de rédiger cette même fonction en précisant explicitement les types des données que nous souhaitons manipuler.
Des erreurs peuvent être signalées à cette étape car ce n'est qu'ici que le compilateur est en mesure de vérifier si les opérations exprimées dans l'algorithme sont légitimes pour les types utilisés✍.
Puisque leur définition doit être connue du compilateur au moment de leur appel (afin d'en réaliser l'instanciation), les fonctions génériques sont généralement définies inline dans les fichiers d'en-tête✍.

{} Utilisation de fonctions génériques

L'expérimentation passera par la réalisation d'un nouveau programme.
Créez alors sur votre poste de travail un répertoire de votre choix dans lequel vous placerez le fichier GNUmakefile et un fichier prog.cpp définissant la fonction test_min_max() qui se contentera, dans un premier temps, d'afficher son nom et qui sera appelée depuis la fonction principale.
Il ne s'agit pour l'instant que d'utiliser les fonctions std::min() et std::max(), exposées par le fichier d'en-tête standard

<algorithm>

, afin de nous familiariser avec des fonctionnalités génériques simples.
(https://en.cppreference.com/w/cpp/algorithm/min)
(https://en.cppreference.com/w/cpp/algorithm/max)

Dans la fonction test_min_max(), déclarez et initialisez deux variables de type entier, deux autres de type réel et enfin deux qui soient des chaînes de caractères C++ ; faites en sorte que leurs valeurs respectives soient faciles à distinguer.
À l'aide de messages dans la console, vérifiez que les fonctions std::min() et std::max() appliquées à chaque paire de variables donnent bien les résultats attendus.
En l'état, nous constatons qu'elles sont bien applicables à des données de types variés ; nous pourrions soupçonner l'existence d'une multitude de surcharges (comme vu dans cette section), mais il n'en est rien.

La documentation de ces fonctions nous apprend qu'elles sont probablement définies d'une manière similaire à celle-ci :

template<typename T> 
inline
const T &
min(const T &a,
    const T &b)
{
  return b<a ? b : a;
}

template<typename T> 
inline
const T &
max(const T &a,
    const T &b)
{
  return a<b ? b : a;
}

Nous reconnaissons des définitions inline très classiques si ce n'est qu'elles sont chacune précédées de template<typename T>.
La construction template<...> sert à énumérer les arguments template qui permettront de décliner la fonction qui la suit selon les besoins de chacune de ses invocations.
Il s'agit principalement d'indiquer des noms symboliques pour représenter des types✍ : typename T ici✍, où le nom T peut être choisi librement.
Partout où apparaît ce nom de type symbolique, il prend la place du nom du type qui sera effectivement substitué au moment de l'instanciation.
Ainsi, si nous invoquons la fonction std::min<T>() ou std::max<T>() avec des paramètres effectifs qui sont des chaînes, tout se passe comme si nous appelions une fonction qui prend deux références constantes sur ces chaînes, les compare selon l'opérateur

qui est propre aux chaînes et renvoie la référence constante désignant la plus petite ou la plus grande des deux.
Il en serait de même avec des entiers, des réels... tout type pour lequel l'opérateur

est applicable.

Dans ces deux fonctions simplistes, les paramètres sont simplement consultés.
Nous avions vu dans cette section que dans ce cas nous utilisions un passage par valeur pour les types simples, et un passage par référence constante pour les types potentiellement coûteux à recopier.
Seulement ici, lors de la définition de ces fonctions, rien n'est connu quant au coût des recopies des différents types qui seront utilisés lors des différentes instanciations.
Par prudence, les paramètres sont alors passés par référence constante afin de ne pas risquer de coûteuses recopies si le cas se présentait.

Néanmoins, cette section suggère que dans certaines situations les références ne sont rien d'autre que des pointeurs dissimulés.
Dans le cas où, lors de l'instanciation de ces fonctions template, nous aurions affaire à des types aussi simples que des entiers ou des réels, il serait légitime de se questionner à propos d'un éventuel surcoût lié à leur accès indirect à travers de tels hypothétiques pointeurs.
Fort heureusement, puisque la définition des fonctions template est inline, le compilateur a une vision directe sur les données référencées et s'autorise à y accéder directement sans avoir recours à des pointeurs✍.
L'utilisation systématique de passages par référence constante pour les paramètres template qui ne doivent être que consultés permet d'éviter les éventuelles recopies coûteuses sans pour autant engendrer de surcoût d'accès lorsque les types considérés à l'instanciation sont simples.

{} Adaptation par une lambda-closure

Les fonctions std::min<T>() et std::max<T>() utilisées précédemment imposaient leur critère de comparaison : l'opérateur

du type concerné.
Il existe cependant une autre déclinaison de ces fonctions template qui attend un troisième paramètre.
(https://en.cppreference.com/w/cpp/algorithm/min)
(https://en.cppreference.com/w/cpp/algorithm/max)
Ce dernier n'a pas le rôle d'une simple donnée mais matérialise un traitement qui sera utilisé en lieu et place de l'opérateur

.
Il s'utilise donc comme une fonction attendant deux paramètres ayant le type choisi lors de l'invocation de la fonction template et fournissant le résultat booléen de leur comparaison selon un critère qui lui est propre.

Pour expérimenter cette fonctionnalité, nous allons décider, de manière très caricaturale, que la comparaison de deux chaînes de caractères revient à comparer simplement leurs longueurs respectives.
Complétez alors la fonction test_min_max() avec l'affichage du résultat d'un nouvel appel à la fonction std::min<T>() ou std::max<T>() appliquée à vos deux variables qui sont des chaînes, et qui utilisera comme troisième paramètre :

[&](const auto &lhs, const auto &rhs) // left-hand-side, right-hand-side
{
  return size(lhs)<size(rhs);
}

Cette formulation plutôt longue doit bien prendre la place du troisième paramètre effectif lors de l'appel ; c'est-à-dire qu'elle est précédée de la virgule qui la sépare du paramètre précédent, et suivie de la parenthèse qui termine la liste des paramètres.

Il s'agit d'une lambda-closure reconnaissable à sa paire de crochets initiale✍, sa paire de parenthèses qui évoque les paramètres d'une fonction et sa paire d'accolades qui évoque le corps d'une fonction.
(https://en.cppreference.com/w/cpp/language/lambda)
Pour l'instant nous pouvons nous contenter de considérer qu'il s'agit d'une fonction anonyme : elle n'a pas de nom et est directement définie à l'emplacement d'un paramètre effectif de l'algorithme qui a besoin de l'invoquer✍.
La fonction std::min<T>() ou std::max<T>() à trois paramètres que nous invoquons ici appellera cette lambda-closure afin qu'elle réalise une comparaison des deux premiers arguments.

Dans le cas présent, notre lambda-closure attend donc deux paramètres passés par référence constante (pour les mêmes raisons que les paramètres template décrits précédemment) et renvoie un booléen qui renseigne sur la comparaison des résultats de la fonction size() appliquée à chacun d'eux.
Bien entendu, les deux paramètres attendus ici correspondent aux deux chaînes transmises lors de notre invocation de std::min<T>() ou std::max<T>().
Nous aurions pu spécifier leur type exact (

const std::string &

), mais depuis C++14 l'usage de auto est autorisé ce qui facilite la réutilisation du code si nous décidions de choisir un autre type pour l'instanciation de la fonction template.
Remarquez également que le type de retour de cette lambda-closure n'est spécifié nulle part : il est automatiquement déduit du type de l'expression transmise par l'instruction return.
Ajustez l'initialisation de vos deux variables de type chaîne (en jouant sur leur longueur et leurs premiers caractères respectifs) afin qu'elles donnent des résultats contradictoires pour les fonctions std::min<T>() ou std::max<T>() à deux ou trois paramètres ; vous verrez ainsi l'effet de votre nouveau critère de comparaison.

Pour compléter l'exploration de cette fonctionnalité, déclarez maintenant dans la fonction test_min_max() une nouvelle variable de cette façon :

const auto inv_cmp=
  [&](const auto &lhs, const auto &rhs)
  {
    return lhs>rhs;
  };

Cette variable nommée inv_cmp utilise le mot-clef auto pour que son type soit automatiquement déduit par le compilateur à partir de sa valeur d'initialisation : il s'agit en l'occurrence d'une lambda-closure dont il serait très difficile de spécifier précisément le type✍.
Elle se contente d'utiliser l'opérateur

sur ses deux paramètres.
Si nous la transmettons à nouveau comme troisième paramètre aux fonctions std::min<T>() ou std::max<T>(), nous inversons leur comportement car nous venons juste de vérifier qu'elles utilisent ce troisième paramètre en lieu et place de l'opérateur

.

Complétez donc la fonction test_min_max() avec les affichages de nouvelles invocations des fonctions std::min<T>() et std::max<T>() appliquées à vos variables de type entier et de type réel, en utilisant la variable inv_cmp comme troisième paramètre effectif.
Remarquez qu'ici nous utilisons la même lambda-closure pour plusieurs invocations ; nous avons utilisé une variable pour la désigner et ainsi ne pas avoir à la saisir entièrement à chaque invocation.
Une observation attentive des messages produits doit confirmer l'effet de notre lambda-closure sur les fonctions std::min<T>() et std::max<T>().

En présentant les lambda-closures un peu plus haut, nous ne nous étions pas attardés sur la signification du symbole & qui figure dans la paire de crochets initiale.
Ce symbole est une consigne de capture qui indique que notre lambda-closure est autorisée à faire référence✍, depuis la paire d'accolades qui constitue le corps de son algorithme, à des variables qui existent dans son contexte environnant.
Pensez par exemple à une boucle for ou une alternative if : le code qui est inscrit dans les accolades de ce for ou de ce if peut accéder implicitement aux variables environnantes pour les consulter ou les modifier ; il en va de même pour les lambda-closures munies de la capture [&].
Afin d'en constater l'effet, complétez la fonction test_min_max() en réalisant une boucle for très classique qui compte avec un entier pos partant de 0 et s'arrêtant juste avant d'atteindre la longueur minimal de vos deux chaînes.
À l'intérieur de cette boucle, invoquez à nouveau la fonction std::min<T>() sur vos deux chaînes, en lui précisant comme troisième paramètre la lambda-closure suivante :

[&](const auto &lhs, const auto &rhs)
{
  return lhs[pos]<rhs[pos];
}

qui ne fait porter la comparaison que sur un seul caractère à une position choisie au sein des deux chaînes.
Vous constatez que, dans cette nouvelle situation, le code servant à la comparaison dépend d'une variable pos, qui varie à notre convenance dans notre programme et dont la fonction std::min<T>() ignore totalement l'existence.
Cette fonction générique n'a donc aucun moyen de transmettre la variable pos en paramètre à la lambda-closure ; le seul moyen pour cette dernière d'avoir accès à cette variable est de la capturer comme l'y autorise la notation [&].
C'est cette dernière remarque qui distingue fondamentalement une simple fonction d'une lambda-closure : une fonction ne peut avoir accès aux informations qui la concernent qu'à travers ses paramètres✍, alors que la capture d'une lambda-closure autorise un accès très naturel aux variables qui environnent l'appel à la fonction générique qui l'exploite.

Nous venons de vérifier que, bien qu'ayant été définies longtemps à l'avance (dans la bibliothèque standard de C++ ici), des fonctions génériques peuvent être conçues pour prendre en compte des lambda-closures qui permettent d'adapter leur comportement aux besoins très spécifiques de chaque situation applicative particulière.

{} Réalisation de fonctions génériques

Les fonctions génériques std::min<T>() et std::max<T>() nous serviront d'inspiration pour réaliser nos propres fonctions génériques.
Nous utiliserons comme prétexte simpliste le calcul de la moyenne entre deux valeurs.

{} Une fonction générique simple

{} Surcharge d'une fonction générique

Appliquez maintenant votre fonction s4prc::avg<T>() à la paire de variables de type chaîne.
Vous devriez constater qu'une erreur de compilation apparaît : l'opération + est bien utilisable sur deux chaînes mais la division par 2 de la chaîne résultante n'a aucune signification !

Nous proposons alors, dans le fichier average.hpp, une nouvelle surcharge pour la fonction s4prc::avg() dans le cas où ses paramètres sont des chaînes :

inline
std::string
avg(const std::string &a,
    const std::string &b)
{
  const int sza=int(size(a));
  const int szb=int(size(b));
  const int sz=avg(sza, szb);
  std::string result;
  for(int i=0; int(size(result))<sz; ++i)
  {
    if(i<sza)
    {
      result+=a[i];
    }
    if(i<szb)
    {
      result+=b[i];
    }
  }
  return result;
}

Remarquez qu'il ne s'agit pas d'une fonction template mais d'une simple surcharge avec les types explicitement spécifiés✍.
Il existe un autre mécanisme qui consiste à spécialiser les templates, mais la règle T.144 des CppCoreGuideLines nous déconseille d'y recourir✍.
Les conversions explicites des résultats de size() vers le type int ne servent ici qu'à éviter des messages d'avertissement concernant la comparaison avec l'entier i.

Cette surcharge calcule, de manière complètement fantaisiste (ce n'est qu'un prétexte à l'expérimentation), la moyenne de deux chaînes en décidant que la chaîne résultante doit avoir une longueur qui est la moyenne de celle des deux paramètres et un contenu qui est l'alternance de leurs caractères respectifs.
Vérifiez que, maintenant, la fonction s4prc::avg() appliquée à la paire de variables de type chaîne se comporte comme attendu.

{} Types template multiples

Puisque la fonction s4prc::avg<T>() s'applique aussi bien à des entiers qu'à des réels, et que les entiers peuvent être implicitement convertis en réels, il paraît légitime de calculer la moyenne entre un entier et un réel.
Complétez alors la fonction test_average() pour qu'elle tente cette opération ; vous devriez constater que la compilation échoue puisque notre fonction s4prc::avg<T>() attend le même type pour ses deux paramètres.

Nous devons donc la modifier selon cette nouvelle formulation :

template<typename T1,
         typename T2>
inline
auto
avg(const T1 &a,
    const T2 &b)
{
  return (a+b)/2;
}

Nous avons choisi deux noms de type template distincts, T1 et T2, afin d'indiquer que les deux paramètres peuvent avoir des types différents✍.

Dans sa version précédente, notre fonction combinait deux données de même type, ce qui nous permettait de supposer que le résultat devait lui aussi avoir ce type✍.
Désormais, cette supposition ne tient plus :

si a désigne un entier, et b un réel, alors le résultat sera un réel,
si a désigne un réel, et b un entier, alors le résultat sera un réel,
si a et b désignent des réels, alors le résultat sera un réel,
si a et b désignent des entiers, alors le résultat sera un entier.

Comment choisir dans ces conditions le type de la valeur de retour ? (est-ce T1 ? T2 ? autre chose ?)
Le mieux reste encore de laisser le compilateur le déterminer automatiquement puisqu'il connaît sans ambiguïté le type de l'expression (a+b)/2 une fois que les types des paramètres a et b ont été choisis.
Dans le cas d'une fonction définie inline✍, l'expression de son résultat est directement visible après l'instruction return, nous avons alors tout intérêt à faire une nouvelle fois usage du mot-clef auto pour spécifier son type de retour.

Vérifiez qu'avec cette nouvelle version de votre fonction s4prc::avg<T1, T2>() votre programme fonctionne tout aussi bien avec des paramètres hétérogènes qu'avec des paramètres homogènes.
Seulement, si nous essayons maintenant de combiner une chaîne avec un réel ou un entier lors de l'invocation de s4prc::avg(), une (longue) erreur de compilation nous indiquera que la fonction s4prc::avg<T1, T2>() n'est pas utilisable car l'expression (a+b)/2 n'a aucun sens pour les types choisis.

De manière similaire à ce que nous avons fait dans la section précédente, il suffit d'ajouter de nouvelles surcharges :

template<typename T>
inline
auto
avg(const T &a,
    const std::string &b)
{
  using std::to_string;
  return avg(to_string(a), b);
}

template<typename T>
inline
auto
avg(const std::string &a,
    const T &b)
{
  using std::to_string;
  return avg(a, to_string(b));
}

Celles-ci prennent en considération les cas où l'un des deux paramètres effectifs est une chaîne✍.
Elles se contentent alors d'utiliser la fonction std::to_string()✍ exposée dans le fichier d'en-tête standard

<string>

pour produire une chaîne à partir de leur paramètre template qui n'en est pas une.
Cela permet finalement d'invoquer la surcharge qui considère le cas de deux paramètres de type chaîne.
Vérifiez qu'avec ces nouvelles surcharges de votre fonction s4prc::avg() votre programme est en mesure de combiner des chaînes avec des entiers ou des réels.

Au cours de cette étape, nous avons utilisé un prétexte fantaisiste, un simple calcul de moyenne, pour réaliser une fonction générique.
Nous l'avons poussé jusqu'au bout de l'absurde en fournissant artificiellement des surcharges spécifiques pour les cas où les opérations initialement exprimées ne s'appliquent pas aux types choisis : des moyennes qui impliquent des chaînes de caractères !

Cette démarche nous a permis d'aborder la réalisation de fonctions simples utilisant des types template.
Plusieurs types template peuvent intervenir dans la même fonction pour offrir plus de souplesse dans le choix des paramètres effectifs qui peuvent lui être transmis.
L'usage du mot-clef auto est particulièrement recommandé dans ce contexte puisqu'il laisse au compilateur le soin de déterminer le type résultant de la combinaison des types template.
En particulier, puisque les fonctions template sont définies inline, nous avons tout intérêt à utiliser auto pour exprimer leur type de retour.

Nous avons également constaté que les fonctions template cohabitent très bien avec les différentes surcharges qui explicitent certains types (voire tous).
Il faut retenir le fait que le compilateur choisit de préférence les surcharges dont les types correspondent exactement aux paramètres effectifs.
Dans ces conditions, les versions template peuvent être vues comme des solutions génériques par défaut lorsque aucune surcharge plus spécifique n'est applicable.

Nous venons de découvrir, sur quelques exemples simples, le fait que l'usage d'une fonction template revient simplement à retarder l'expression des types exacts utilisés jusqu'au moment de son invocation.
Cela permet d'exprimer une fois pour toutes un algorithme qui sera automatiquement décliné en autant de versions qu'il sera nécessaire pour les types effectivement choisis.
L'usage du mot-clef auto est plus que jamais encouragé✍ dans le sens où il nous permet d'éviter d'exprimer des choix forts qui risqueraient de limiter la réutilisabilité de nos fonctions template : au contraire, nous laissons au compilateur la responsabilité de déduire les types.
Le fait que les fonctions template soient nécessairement définies inline offre de très bonnes opportunités d'optimisation au compilateur et le recours systématique à des références (constantes ou non selon les besoins) n'implique pas forcément le surcoût de multiples indirections à travers d'hypothétiques pointeurs dissimulés.
Bien qu'étant rédigées pour appliquer le même algorithme à une grande variété de types, ces fonctions génériques peuvent néanmoins être adaptées aux spécificités de certains types grâce au mécanisme de surcharge déjà connu, ou aux particularités du contexte applicatif grâce la fourniture de lamda-closures lorsque l'algorithme le prévoit.

{} Les itérateurs

{} Les conteneurs génériques

Nous avons déjà eu l'occasion de constater que de nombreux types fournis par la bibliothèque standard reposent sur l'usage des template.
Si l'apparence est évidente pour std::array<T> ou std::vector<T>, c'est également le cas pour bien d'autres.
Par exemple, le type std::string n'est que l'instanciation du type std::basic_string<T> dans le cas particulier où T correspond au type char✍.

La bibliothèque standard de C++ propose une variété de types, les conteneurs, dont l'aspect template répond directement à un besoin essentiel : mémoriser des données dont le type est choisi librement.
(https://en.cppreference.com/w/cpp/container)
Bien que réalisés chacun selon des principes très différents, ils sont tous exploitables de manière très similaire à travers les itérateurs fournis par les fonctions cbegin(), cend(), begin() et end().
Chacun d'eux a des propriétés qui font que l'un ou l'autre sera plus ou moins bien adapté à un usage applicatif particulier.
Il n'est pas question ici de décrire en détail leurs fonctionnalités (la documentation de référence joue déjà parfaitement ce rôle) mais de présenter les quelques caractéristiques qui permettront de faire un choix parmi les conteneurs les plus courants.

{} Disposition compacte des données

Parmi les conteneurs usuels, certains ont la particularité de maintenir les données qu'ils contiennent de manière contiguë (ou au moins partiellement) en mémoire comme le ferait un tableau.
Cette propriété est très précieuse pour plusieurs raisons :

le temps d'accès aux données voisines dans la mémoire est amorti par les mémoires cache✍
Cet aspect matériel sera étudié au septième semestre de la scolarité à l'ENIB dans les matières S7-SEN et S7-CRS.
ce qui rend les parcours séquentiels très efficaces,
lors d'un parcours séquentiel des éléments, cette disposition rend la progression très prédictible, ce qui autorise le compilateur à reformuler le code exécutable très efficacement,
l'accès à n'importe quel élément du conteneur peut se faire en temps constant sans avoir à parcourir les éléments un-à-un jusqu'à rencontrer celui qui est visé.

{} Les tableaux std::array<T, N>

Le type std::array<T, N>, exposé par le fichier d'en-tête standard

<array>

, a été rencontré très tôt dans cet enseignement.
Nous avons vu à cette occasion qu'il ne s'agissait que de l'équivalent d'un tableau du langage C (T name[N];, N étant connu dès la compilation).
En particulier, un tel tableau ne repose pas sur l'allocation dynamique de mémoire ; sa taille est déterminée une fois pour toutes.
(https://en.cppreference.com/w/cpp/container/array)

Son exposition sous la forme d'un type élaboré de C++ présente l'intérêt d'offrir des fonctions (membres ou non) comparables à celles qui concernent les autres conteneurs ; une telle présentation homogène de différents conteneurs favorise l'écriture de traitements génériques qui puissent les exploiter indifféremment.
En particulier, nous avons vu que la recopie de tels tableaux était rendue tout à fait semblable à la recopie des autres types✍.
Attention toutefois : puisque aucune allocation dynamique de mémoire n'est impliquée dans la réalisation du type std::array<T, N>, l'opération de déplacement sur un tel tableau est strictement équivalente à la recopie complète, et donc potentiellement coûteuse.

{} Les tableaux dynamiques std::vector<T>

Un autre conteneur que nous rencontrons depuis le début de cet enseignement joue le rôle de tableau dynamique et est matérialisé par le type std::vector<T>, exposé par le fichier d'en-tête standard

<vector>

.
Nous pouvons le considérer comme un type structuré qui maintient un invariant à propos :

d'un pointeur désignant une zone de mémoire allouée dynamiquement pour contenir les éléments,
d'une information sur la capacité de cette zone de stockage,
d'une information sur le nombre d'éléments effectivement mémorisés à l'intérieur de cette zone de stockage.

(https://en.cppreference.com/w/cpp/container/vector)
Puisque ce type repose en interne sur de l'allocation dynamique, l'opération de déplacement sur une donnée de type std::vector<T> est très avantageuse par rapport à une recopie complète✍.

Ce type prend complètement à sa charge la gestion de la réallocation de la zone de mémoire dynamique utilisée selon une stratégie spéculative (voir cette section du cours S3-PRC).
Toutefois, si nous connaissons à l'avance, même de manière approximative, le nombre d'éléments que nous souhaitons placer dans un tel conteneur, nous avons intérêt à préciser la capacité minimale souhaitée avec sa fonction membre reserve().
(https://en.cppreference.com/w/cpp/container/vector/reserve)
(https://en.cppreference.com/w/cpp/container/vector/capacity)

const int amount=guess_number_of_elements();
std::vector<Element> v;
v.reserve(amount); // pre-allocation for at least amount elements
for(int i=0; i<amount; ++i)
{
  v.emplace_back(obtain_an_element());
}

Cette précaution évite de multiples réallocations et recopies du contenu qui pourraient survenir avant d'atteindre la taille finalement nécessaire à la mémorisation de l'ensemble des éléments.
La réservation préalable de la capacité représente une opportunité d'optimisation qu'il est très important de saisir car le mécanisme d'allocation de mémoire et les recopies d'un volume conséquent d'information sont connus pour être très pénalisants en temps d'exécution.

Une autre chose qu'il est important de connaître à propos du type std::vector<T>, concerne l'ajout et le retrait d'éléments.
Nous avons jusqu'alors privilégié, à juste titre, les opérations emplace_back() et pop_back().
En effet, elles opèrent au niveau de l'indice le plus élevé à l'intérieur du tableau dynamique, ce qui fait qu'il n'est pas nécessaire de déplacer les autres éléments.

Complément : ajout et retrait à la fin d'un std::vector<T>

Imaginons un tableau dynamique ayant cette représentation symbolique :

capacity: 10 (storage is allocated for 10 elements)
    size: 8  (only 8 elements are stored, 2 slots left in storage)
 content: [ A | B | C | D | E | F | G | H | . | . ]

L'ajout d'un nouvel élément à la fin par v.emplace_back(X) reviendrait :

à initialiser l'élément à l'indice 8 (c'est-à-dire size) avec X,
et à incrémenter size (qui passerait à 9),

pour obtenir

capacity: 10 (storage is allocated for 10 elements)
    size: 9  (only 9 elements are stored, 1 slot left in storage)
 content: [ A | B | C | D | E | F | G | H | X | . ]

De la même façon, retirer le dernier élément avec v.pop_back() reviendrait :

à appeler le destructeur de l'élément H (à l'indice 7, c'est-à-dire size-1),
et à décrémenter size (qui passerait à 7),

pour obtenir

capacity: 10 (storage is allocated for 10 elements)
    size: 7  (only 7 elements are stored, 3 slots left in storage)
 content: [ A | B | C | D | E | F | G | . | . | . ]

Nous constatons que sur chacune de ces deux opérations en fin de séquence, seul l'élément concerné est modifié et l'information size est incrémentée ou décrémentée : ces opérations sont donc très peu coûteuses en temps d'exécution✍.

Complément : ajout et retrait au cœur d'un std::vector<T>

Imaginons un tableau dynamique ayant cette représentation symbolique :

capacity: 10 (storage is allocated for 10 elements)
    size: 8  (only 8 elements are stored, 2 slots left in storage)
 content: [ A | B | C | D | E | F | G | H | . | . ]

L'ajout d'un nouvel élément par v.emplace(cbegin(v)+2, X) reviendrait :

à déplacer tous les éléments ayant un indice supérieur ou égal à 2 vers les emplacements d'indice supérieur,
à initialiser l'élément à l'indice 2 avec X,
et à incrémenter size (qui passerait à 9),

pour obtenir

capacity: 10 (storage is allocated for 10 elements)
    size: 9  (only 9 elements are stored, 1 slot left in storage)
 content: [ A | B | X | C | D | E | F | G | H | . ]

De la même façon, retirer un élément avec v.erase(cbegin(v)+2) reviendrait :

à appeler le destructeur de l'élément C (à l'indice 2),
à déplacer tous les éléments ayant un indice supérieur à 2 vers les emplacements d'indice inférieur,
et à décrémenter size (qui passerait à 7),

pour obtenir

capacity: 10 (storage is allocated for 10 elements)
    size: 7  (only 7 elements are stored, 3 slots left in storage)
 content: [ A | B | D | E | F | G | H | . | . | . ]

Nous constatons que sur chacune de ces deux opérations au cœur de la séquence, tous les éléments dont l'indice est supérieur à celui de l'opération doivent être déplacés.
Ce surcoût peut s'avérer extrêmement pénalisant lorsque la séquence est très longue.

Lorsque l'ordre des éléments mémorisés n'est pas important, il est préférable de systématiquement ajouter ou retirer les éléments d'un std::vector<T> du côté de sa fin (back).
En particulier, nous pouvons avantageusement remplacer l'appel :

v.erase(cbegin(v)+idx);

par l'appel :

v[idx]=std::move(v.back()); // move last to idx
v.pop_back(); // get rid of (moved-from) last

qui écrase l'élément dont nous voulons nous débarrasser en y déplaçant le dernier✍, avant de retirer le dernier élément qui vient d'être dépossédé de son contenu.
(https://en.cppreference.com/w/cpp/container/vector/erase)
(https://en.cppreference.com/w/cpp/container/vector/operator_at)
(https://en.cppreference.com/w/cpp/container/vector/back)

Le type std::vector<T> doit être considéré en premier lieu lorsqu'il est question de choisir un conteneur ; un autre type de conteneur ne doit être envisagé que dans les rares cas où l'application exhibe une particularité qui le justifie impérativement✍.
Il est en effet très simple dans sa réalisation ce qui le rend très efficace pour la plupart des usages.
Il offre néanmoins un grand confort d'utilisation tout en autorisant un contrôle assez fin de son fonctionnement.

{} Les files à double entrées std::deque<T>

Il a été souligné précédemment que les tableaux dynamiques offraient un usage optimal uniquement du côté de leur fin (back).
Les files à double entrées std::deque<T>, exposées par le fichier d'en-tête standard

<deque>

, visent à donner l'illusion de tableaux dynamiques pour lesquels les manipulations seraient optimales à la fois du côté de leur début (front) et de leur fin (back).
Il ne s'agit pas à proprement parler d'une unique zone de stockage dans laquelle tous les éléments sont placés de manière contiguë (comme pour les tableaux, dynamiques ou non), mais en pratique les éléments sont ici regroupés dans plusieurs plus petits tableaux dynamiques qui peuvent apparaître ou disparaître à chaque extrémité selon les besoins✍.
Puisque ce type repose en interne sur de l'allocation dynamique, l'opération de déplacement sur une donnée de type std::deque<T> est très avantageuse par rapport à une recopie complète.
(https://en.cppreference.com/w/cpp/container/deque)
(https://en.wikipedia.org/wiki/Double-ended_queue)

Aux opérations emplace_back() et pop_back() s'ajoutent désormais les opérations emplace_front() et pop_front() auxquelles il faut recourir de préférence.
(https://en.cppreference.com/w/cpp/container/deque/emplace_back)
(https://en.cppreference.com/w/cpp/container/deque/pop_back)
(https://en.cppreference.com/w/cpp/container/deque/emplace_front)
(https://en.cppreference.com/w/cpp/container/deque/pop_front)
Les ajouts et retraits à tout autre emplacement de la séquence sont tout aussi pénalisants que dans le cas d'un tableau dynamique.

Bien que les éléments ne soient stockés en mémoire que de manière partiellement contiguë, le temps d'accès à un élément quelconque reste raisonnable✍.
Cette proximité, même partielle, des éléments reste profitable lors de l'accès à des données voisines, grâce à une bonne exploitation des mémoires cache.
En revanche un parcours simple de la séquence ne devient pas aussi prédictible que dans le cas d'un tableau, et le compilateur ne sera certainement pas capable de reformuler aussi efficacement le code exécutable.

Un cas d'usage typique du type std::deque<T> à la place du type std::vector<T> se présente lorsque les ajouts ont lieu systématiquement à une extrémité et les retraits à l'autre extrémité.
Dans le cas d'un tableau dynamique il y aurait un déplacement de tous les éléments à chaque intervention (ajout ou retrait, selon l'extrémité concernée), alors qu'une file à double entrées ne ferait que des interventions très localisées sur les éléments concernés.
Le type std::queue<T> utilise d'ailleurs par défaut le type std::deque<T> pour réaliser une file d'attente (First-In-First-Out).
(https://en.cppreference.com/w/cpp/container/queue)

De par son efficacité et sa facilité d'utilisation, le type std::vector<T> est à privilégier lorsque l'ordre des éléments mémorisés importe peu ou si nous pouvons nous contenter de modifier ce conteneur uniquement du côté de sa fin.
Si des modifications doivent régulièrement avoir lieu à chacune des deux extrémités, le type std::deque<T> sera probablement plus approprié tout en gardant des performances raisonnables.
Le type std::array<T>, de par ses fonctionnalités limitées (taille fixe déterminée dès la compilation, déplacement inefficace) ne trouve que peu d'usage dans la pratique.

{} Disposition fragmentée des données

À l'opposé des conteneurs précédents, il en existe d'autres qui ont la particularité de maintenir leurs éléments dans de multiples et éparses portions de mémoire indépendantes.
La motivation d'un tel choix repose sur le souhait de limiter le surcoût d'un ajout ou d'un retrait au cœur de la séquence lorsqu'une telle intervention est inhérente au problème traité✍.
Cependant, les avantages en termes de performance qui étaient liés à un stockage compact laissent dorénavant place à des pénalités :

des données proches dans la séquence sont désormais éloignées en mémoire ce qui conduit à une mauvaise utilisation des mémoires cache,
lors d'un parcours séquentiel des éléments, l'accès à chaque élément suivant est très peu prédictible, ce qui empêche le compilateur de reformuler efficacement le code exécutable,
l'accès à n'importe quel élément du conteneur nécessite un passage en revue de plusieurs éléments jusqu'à rencontrer celui qui est visé.

Ces conteneurs ne s'avéreront intéressants sur un cas applicatif particulier que si les bénéfices liés à l'ajout et au retrait au cœur de la séquence compensent largement ces pénalités.

{} Les listes chaînées

Le type std::list<T>, exposé par le fichier d'en-tête standard

<list>

, représente une liste chaînée qui désigne une succession de nœuds.
Chaque nœud est alloué dynamiquement de manière individuelle et contient à la fois la donnée à mémoriser et deux pointeurs vers les nœuds suivant et précédent : la liste est dite doublement chaînée.
Il existe donc autant de portions de mémoire allouées dynamiquement qu'il y a d'éléments à mémoriser dans la liste, ce qui contribue à la fragmentation de leur répartition en mémoire.
(https://en.wikipedia.org/wiki/Linked_list)
(https://en.cppreference.com/w/cpp/container/list)

Le parcours séquentiel d'une telle liste consiste à partir d'une extrémité (connue de la liste elle-même) et à progresser de nœud en nœud, en suivant chaque nouveau pointeur rencontré.
Il existe une variante plus simple, le type std::forward_list<T>, dont les nœuds ne contiennent un pointeur que vers l'élément suivant : la liste est dite simplement chaînée.
(https://en.cppreference.com/w/cpp/container/forward_list)
Dans tous les cas, le seul moyen d'accéder à un élément qui ne soit pas situé à une extrémité consiste à réaliser un parcours séquentiel, ce qui peut s'avérer très long et très pénalisant !

Le bénéfice attendu d'une telle liste chaînée peut provenir du fait que si nous désignons un de ses éléments, sa suppression ne nécessite que l'ajustement des pointeurs des nœuds précédents et suivants, sans avoir à déplacer de nombreux éléments.
Il en est de même pour l'ajout : il suffit d'ajuster les pointeurs du nœud nouvellement introduit, de son précédent et de son suivant.

Il est extrêmement rare de rencontrer des cas applicatifs réalistes dans lesquels les listes chaînées offrent de meilleures performances que les tableaux dynamiques ou les files à double entrées (à moins d'inventer artificiellement de tels contre-exemples à dessein).
Les références indiquées à la fin de cette section étudient précisément ce sujet.
Si les listes chaînées existent toujours pour des raisons historiques✍, nous n'avons en pratique que peu de raisons légitimes de les utiliser.

{} Les ensembles

Jusqu'alors, les conteneurs présentés ne matérialisaient qu'une séquence d'éléments sans plus de contrainte (si ce n'est celles liées à leur stockages en mémoire) : nous pouvions décider que leur ordre était important ou non, qu'il pouvait y avoir des doublons ou non...
Le type std::set<T>, exposé par le fichier d'en-tête standard

<set>

, représente un ensemble d'éléments qui sont uniques du point de vue du critère de comparaison de leur type (leur opérateur <).
L'usage de cette relation d'ordre fait que ces éléments sont parcourus dans l'ordre croissant.
(https://en.cppreference.com/w/cpp/container/set)

Tout comme dans le cas des listes, ces éléments sont mémorisés dans des nœuds alloués dynamiquement de manière individuelle.
Ces nœuds sont organisés sous la forme d'un arbre équilibré, ce qui fait que la recherche d'un élément n'a pas une complexité linéaire mais logarithmique✍.
L'utilisation des conteneurs de type std::set<T> peut donc s'avérer très pertinente lorsqu'il est question de rechercher fréquemment des éléments dans un très grand ensemble.
Si les recherches sont efficaces, les opérations d'ajout et de retrait d'un élément impliquent quant à elles un surcoût nécessaire au maintien du bon équilibre de l'arbre.

Exemple d'utilisation du type std::set<T>

Cette portion de code

std::set<int> s;
for(int i=0; i<10; ++i)
{
  const int value=((i+2)*(i+5))%11;
  if(const auto [iter, inserted]=s.insert(value); inserted)
  {
    std::cout << value << " -->";
    for(const auto &elem: s)
    {
      std::cout << ' ' << elem;
    }
    std::cout << '\n';
  }
  else
  {
    std::cout << *iter << " is already present\n";
  }
}
if(const auto iter=s.find(7); iter!=cend(s))
{
  std::cout << *iter << " found, will be removed\n";
  s.erase(iter);
}
std::cout << "final set -->";
for(const auto &elem: s)
{
  std::cout << ' ' << elem;
}
std::cout << '\n';

produit cet affichage

10 --> 10
7 --> 7 10
6 --> 6 7 10
7 is already present
10 is already present
4 --> 4 6 7 10
0 --> 0 4 6 7 10
9 --> 0 4 6 7 9 10
9 is already present
0 is already present
7 found, will be removed
final set --> 0 4 6 9 10

Nous constatons que la fonction membre d'insertion insert() renvoie deux résultats (std::pair<T1, T2>, c'est-à-dire std::tuple<...> à deux membres) :

un itérateur sur l'élément inséré ou déjà présent,
un booléen indiquant si l'insertion a effectivement eu lieu (aucun élément équivalent n'était déjà présent).

(https://en.cppreference.com/w/cpp/container/set/insert)
Nous avons choisi ici d'extraire ces deux informations dans deux variables qui sont locales à l'alternative qui les exploite.

La recherche avec la fonction membre find() renvoie un itérateur sur l'élément trouvé (ou la fin de séquence en cas d'échec).
(https://en.cppreference.com/w/cpp/container/set/find)
Nous avons à nouveau choisi ici de rendre cette information locale à l'alternative qui l'exploite.

Le retrait d'un élément avec la fonction membre erase() attend un tel itérateur.
(https://en.cppreference.com/w/cpp/container/set/erase)

Il existe des variantes de ce type :

le type std::multiset<T> ajoute la possibilité de mémoriser plusieurs éléments considérés équivalents tout en conservant le parcours dans l'ordre croissant,
(https://en.cppreference.com/w/cpp/container/multiset)
le type std::unordered_set<T> utilise une table d'indexation et des listes (lorsque les comparaisons entre éléments sont coûteuses ou non pertinentes), ce qui ne garantit plus un parcours dans l'ordre croissant,
(https://en.cppreference.com/w/cpp/container/unordered_set)
le type std::unordered_multiset<T> ajoute au précédent la possibilité de mémoriser plusieurs éléments considérés équivalents.
(https://en.cppreference.com/w/cpp/container/unordered_multiset)

{} Les conteneurs associatifs

Le type std::map<K, V>, exposé par le fichier d'en-tête standard

<map>

, peut être vu comme la généralisation du type std::set<T> : il utilise le même procédé pour organiser des clefs qui sont associées à des données✍.
Il s'agit donc également d'un arbre équilibré dont les nœuds, qui sont alloués dynamiquement et de manière individuelle, renferment à la fois une clef et une donnée.
Le critère de comparaison porte uniquement sur les clefs : elles sont uniques et parcourues dans l'ordre croissant.
L'intérêt essentiel d'un tel conteneur est de mémoriser de multiples associations entre une clef et une donnée.
Si le conteneur contient de nombreuses associations, l'organisation sous forme d'arbre équilibré permet de retrouver efficacement une donnée quelconque en recherchant la clef qui lui est associée.
(https://en.cppreference.com/w/cpp/container/map)

Exemple d'utilisation du type std::map<K, V>

Cette portion de code

std::map<std::string, int> m;
m["unan"]=1;     m["daou"]=2;  m["tri"]=3;  m["pevar"]=4; m["pemp"]=5;
m["c'hwec'h"]=6; m["seizh"]=7; m["eizh"]=8; m["nav"]=9;   m["dek"]=10;
for(const auto &[key, value]: m)
{
  std::cout << key << " --> " << value << '\n';
}
std::cout << "pevar means " << m["pevar"] << '\n';

produit cet affichage

c'hwec'h --> 6
daou --> 2
dek --> 10
eizh --> 8
nav --> 9
pemp --> 5
pevar --> 4
seizh --> 7
tri --> 3
unan --> 1
pevar means 4

Nous constatons que l'opérateur [] propose un moyen confortable de réaliser des consultations et des ajouts (il existe toutefois les fonctions membres find(), emplace() et erase() qui offrent un contrôle plus fin).
(https://en.cppreference.com/w/cpp/container/map/operator_at)
(https://en.cppreference.com/w/cpp/container/map/find)
(https://en.cppreference.com/w/cpp/container/map/emplace)
(https://en.cppreference.com/w/cpp/container/map/erase)

Le parcours de ce conteneur fournit à chaque itération deux résultats (std::pair<K, V>, c'est-à-dire std::tuple<...> à deux membres) :

la clef de l'élément visité,
la valeur de l'élément visité.

Il existe des variantes de ce type :

le type std::multimap<K, V> ajoute la possibilité de mémoriser plusieurs données dont les clefs sont considérées équivalentes tout en conservant le parcours dans l'ordre croissant,
(https://en.cppreference.com/w/cpp/container/multimap)
le type std::unordered_map<K, V> utilise une table d'indexation et des listes (lorsque les comparaisons entre clefs sont coûteuses ou non pertinentes), ce qui ne garantit plus un parcours dans l'ordre croissant,
(https://en.cppreference.com/w/cpp/container/unordered_map)
le type std::unordered_multimap<K, V> ajoute au précédent la possibilité de mémoriser plusieurs données dont les clefs sont considérées équivalentes.
(https://en.cppreference.com/w/cpp/container/unordered_multimap)

Parmi les conteneurs reposant sur l'allocation dynamique individuelle de nœuds, les listes chaînées n'apportent que très peu de bénéfices, au regard de leur surcoût en performance, par rapport à des conteneurs plus simples ; elles peuvent désormais être considérées comme des vestiges du passé✍.
Les ensembles, de par la possibilité de recherche efficace d'un élément, paraissent apporter des fonctionnalités plus intéressantes ; seulement, dans la plupart des cas où il y a beaucoup plus d'opérations de recherche que d'ajouts et de retraits, un tableau dynamique trié fait tout aussi bien l'affaire (voir l'exemple choisi dans cette section) tout en garantissant une bonne efficacité en matière de parcours séquentiel et d'accès aléatoire.
Celui qui rend le plus de services dans la pratique est std::map<K, V> (ou une de ses variantes) : il offre en effet la même facilité d'utilisation que les dictionnaires des langages de plus haut niveau comme Javascript ou Python.
Il ne faut pas oublier toutefois qu'au-delà de la recherche d'un élément par sa clef, le parcours séquentiel d'un tel conteneur associatif reste très pénalisant.

Le choix des conteneurs à utiliser dans chaque cas applicatif est un sujet très largement débattu.
Les considérations théoriques sur la complexité algorithmique des divers procédés se confrontent désormais aux réalités pratiques de mise en œuvre du procédé d'accès aux données mémorisées dans les machines informatiques modernes.
Les experts de C++, qui justifient le choix d'utiliser ce langage par un besoin de maîtrise fine de l'exploitation du matériel, recommandent dorénavant de systématiquement se tourner en priorité vers l'utilisation de tableaux dynamiques std::vector<T>.
Seulement dans quelques cas où, mesures de performances à l'appui✍, il s'avère que le problème mérite manifestement l'usage d'un autre type de conteneur, nous nous éloignerons de ce premier choix.

{} Réalisation d'un type générique

Nous envisageons maintenant la réalisation de notre propre type dépendant de types template.
Afin d'illustrer la remarque à propos des recherches efficaces formulée en conclusion de cette section, ce type organisera les éléments d'un conteneur de notre choix en s'assurant qu'ils sont toujours triés.
Dans ces conditions, une recherche dichotomique sera envisagée pour retrouver efficacement un élément.
Notre type générique offrira donc de nouvelles fonctionnalité sur un conteneur existant dont le type exact sera choisi librement✍.

Ce type nommé Sorted, appartenant à l'espace de noms s4prc, ainsi que les fonctions qui le concernent seront définis dans un unique fichier d'en-tête sorted.hpp puisque les fonctionnalités template doivent être définies inline (voir cette section).
Il s'agit d'un type structuré très conventionnel :

template<typename Container>
struct Sorted
{
  Container content;
};

La notation template<typename Container> qui le précède indique que nous considérons le nom symbolique Container comme le type du conteneur qui sera choisi lors de l'instanciation ; il pourrait s'agir d'un std::vector<T>, d'une std::deque<T>, d'une std::list<T>...
Au premier abord, nous pourrions nous interroger sur l'utilité d'une structure n'ayant qu'un seul membre (un conteneur de ce type qui sera spécifié ultérieurement).
L'intérêt essentiel ici✍ est d'introduire un nouveau type (Sorted) qui permettra de choisir précisément les fonctions qui s'y appliquent : seules les fonctions qui attendent en paramètre le type Sorted seront directement invocables et non n'importe quelle fonction qui s'applique habituellement au conteneur sous-jacent.
Cette démarche qui consiste à réutiliser un type existant en contraignant son usage selon un besoin particulier est connue comme l'approche new-type dans le contexte de la programmation fonctionnelle✍.

Le minimum qu'on puisse demander au type Sorted est de nous donner accès à la séquence de données triées qu'il mémorise.
La fonction suivante :

template<typename Container>
inline
auto // typename Container::const_iterator
cbegin(const Sorted<Container> &sorted)
{
  return cbegin(sorted.content);
}

se contente de renvoyer l'itérateur indiquant le début du conteneur sous-jacent afin de consulter ses éléments.
Remarquez que cette fonction s'applique à un Sorted considéré comme non modifiable (référence constante).
En toute rigueur le type de retour devrait être spécifié comme indiqué en commentaire (le nom de type const_iterator fourni par le conteneur sous-jacent), mais le mot-clef auto s'y substitue parfaitement sans introduire la moindre ambiguïté et simplifie grandement la relecture.
Sur le même principe, ajoutez une fonction cend() similaire.

Il serait très pratique que les boucles range-for soient utilisables sur le type Sorted, seulement ces boucles recherchent sur le conteneur parcouru la présence de fonctions begin() et end() (sans la lettre c du début) même lorsque le conteneur est considéré comme constant.
Pour satisfaire cette exigence, il nous suffit de fournir de telles fonctions en invoquant simplement les deux précédentes :

begin() aura le même prototype que cbegin() et l'invoquera,
end() aura le même prototype que cend() et l'invoquera.

En imaginant que des données triées soient déjà mémorisées, nous devons fournir une fonction qui permette de retrouver efficacement la position d'un élément.

template<typename Container>
inline
auto // element position or end (typename Container::const_iterator)
find(const Sorted<Container> &sorted,
     const typename Container::value_type &value)
{
  const auto it=std::lower_bound(cbegin(sorted), cend(sorted), value);
  return (it==cend(sorted))||(value<*it) ? cend(sorted) : it;
}

Cette fonction s'applique à un Sorted considéré comme non modifiable (référence constante) car elle n'a qu'un rôle de consultation (pas de modification) sur la donnée concernée.
Comme dans le cas des fonctions précédentes, son prototype utilise simplement auto pour le type du résultat ; cela aurait aussi pu s'écrire typename Container::const_iterator puisque nous renvoyons un itérateur permettant de consulter un élément du conteneur sous-jacent.
En ce qui concerne la paramètre value, il est nécessaire de préciser que cette fonction ne peut être appelée qu'avec une donnée pouvant être mémorisée dans le conteneur sous-jacent : ce type peut être désigné par typename Container::value_type.
En effet, les conteneurs standards, en plus de renfermer des données membres et des fonctions membres, définissent des types qui leur sont propres (const_iterator, value_type...) afin que nous puissions les désigner explicitement.
Nous exploitons la fonction std::lower_bound(), exposée par le fichier d'en-tête standard

<algorithm>

, pour effectuer une recherche dichotomique (donc efficace) sur une séquence supposée triée.
Son résultat indique la position du premier élément qui est supérieur ou égal à la donnée recherchée.
(https://en.cppreference.com/w/cpp/algorithm/lower_bound)
Dans le cas présent nous souhaitons une égalité stricte ; si ce n'est pas le cas, nous renvoyons la fin de la séquence afin de signifier l'échec de la recherche.

Nous devons également fournir un moyen d'ajouter des éléments dans le conteneur ; bien entendu, cette opération doit prendre soin de garder les éléments triés.
Ce sera assuré par cette fonction :

template<typename Container>
inline
auto // insert position (typename Container::const_iterator)
insert(Sorted<Container> &sorted,
       typename Container::value_type value)
{
  const auto it=std::lower_bound(cbegin(sorted), cend(sorted), value);
  return sorted.content.emplace(it, std::move(value));
}

qui s'applique à un Sorted considéré comme modifiable (référence non-constante).
La position d'insertion est à nouveau obtenue par une recherche dichotomique.
Il suffit de réclamer au conteneur l'ajout d'un nouvel élément à l'emplacement indiqué (qui peut être à la fin de la séquence sans que ce soit problématique).
Puisqu'il s'agit de mémoriser le paramètre, nous retrouvons la démarche qui consiste à le transmettre par valeur puis à le déplacer lors de la mémorisation effective (voir cette section).
Les fonctions membres emplace() des conteneurs standards renvoient la position d'insertion ; nous en profitons pour faire de même.

Le retrait d'un élément du conteneur ne nécessite pas de précaution particulière ; il ne modifie pas l'ordre des éléments qui restent.
Il nous suffit alors de fournir une fonction erase() qui se contente de reporter l'appel sur le conteneur sous-jacent.

template<typename Container>
inline
auto // next element position or end (typename Container::const_iterator)
erase(Sorted<Container> &sorted,
      typename Container::const_iterator it)
{
  return sorted.content.erase(it);
}

Elle s'applique à un Sorted considéré comme modifiable (référence non-constante).
Bien que nous ne connaissions pas à l'avance le type exact de const_iterator, nous savons qu'il a le rôle d'itérateur.
Par principe, il s'agit d'une information très légère (un simple pointeur la plupart du temps) qui n'est absolument pas coûteuse à recopier.
Nous nous permettons alors de le passer par valeur en paramètre (comme un simple entier) afin de désigner l'emplacement dans la séquence auquel le retrait doit avoir lieu.

Pour tester le type s4prc::Sorted ainsi réalisé, nous devons ajouter au fichier prog.cpp une fonction test_sorted() qui commence par afficher son nom et qui sera appelée depuis la fonction principale.
Les tests porteront sur trois conteneurs standards qui représentent des séquences de taille variable mais non ordonnées (voir cette section).

s4prc::Sorted<std::vector<int>> sv;
s4prc::Sorted<std::deque<int>> sd;
s4prc::Sorted<std::list<int>> sl;

Arrangez-vous pour ajouter à chacun d'eux, à l'aide de votre fonction insert(), de nombreux éléments de manière désordonnée et affichez-en le contenu✍ (qui doit apparaître ordonné).
Remarquez que pour l'affichage, la boucle range-for habituelle doit spontanément bénéficier des fonctions begin() et end() que vous avez fournies pour le type s4prc::Sorted sans que vous ayez à les invoquer explicitement.
De la même façon, provoquez la recherche et le retrait de valeurs dans ces trois conteneurs, avec vos fonctions find() et erase(), et contrôlez-en l'effet par des affichages appropriés✍.

Nous vérifions ainsi que la nouvelle contrainte d'usage que nous avons introduite pour un besoin particulier (travailler efficacement avec des données triées, dans cet exemple) grâce à notre type structuré générique s4prc::Sorted est exploitable sur des conteneurs dont le type exact importe peu (seul un sous-ensemble minimal de fonctionnalités communes est attendu)✍.

Nous venons de constater que la définition de types génériques simples n'est finalement pas bien différente de ce que nous savons faire à propos de fonctions ; il s'agit principalement d'énumérer des données membres dont le type ne sera précisément connu qu'à l'instanciation des templates.
Les fonctions qui manipulent ces types génériques sont identiques dans leur principe à toutes les autres fonctions génériques que nous avons manipulées dans ce chapitre.
Elles dépendent simplement d'un ou plusieurs types qui ne sont pas encore connus précisément au moment où elles sont définies.