Comment écrire un algorithme « standard »

Un de mes dadas à propos de la plupart des cours, tutoriels et livres sur le C++ est de dire qu'ils semblent ostensiblement ignorer les algorithmes. Je ne parle pas d'algorithmes d'un point de vue théorique, mais des algorithmes de la bibliothèque standard. Je suis étonné du nombre de professeurs de C++ demandant à leurs élèves de ne pas utiliser d'algorithmes dans leurs travaux. Et, à part les algorithmes standards actuels, la majorité des livres, tutoriels et cours ne font aucun effort pour discuter des algorithmes qui suivent le même schéma général. À mon avis, écrire un algorithme standard devrait être un des points clés d'un cours moderne sur C++ pour débutant.

Et, bien sûr, j'ai joint mon code à ma parole : dans chaque cours de C++ que j'ai donné, un des modules décrivait un algorithme standard. C'était la fonction copy_n() avant C++11, mais depuis c'est copy_until(), qui copie une suite jusqu'à ce qu'une valeur donnée soit trouvée(1). Ce papier sera un guide à travers les étapes de création d'un algorithme standard. Il ne s'agit pas de se focaliser sur l'algorithme lui-même, mais sur son processus de création.

Le problème que nous voulons traiter est de copier une suite d'éléments jusqu'à - mais sans l'inclure - un élément de terminaison donné, ou bien la totalité de la suite si l'élément recherché n'existe pas dans la suite. J'ai trouvé plusieurs situations où cela était généralement intéressant. Par exemple, pour l'analyse : lorsque vous analysez des données, il y a de nombreux cas où vous souhaitez récupérer des données jusqu'à un certain caractère - comme lire une ligne entière (le caractère de terminaison est '\n') ou bien une chaîne entre guillemets (le guillemet fermant étant le caractère de terminaison). Il est aussi fréquent de lire une liste de nombres terminés par zéro (pas '\0' mais bien le chiffre 0).

La fonction doit donc, bien évidemment, récupérer la chaîne de caractères en entrée, soit sous forme d'une paire d'itérateurs ou bien d'un ensemble… Nous allons coder les deux options parce que c'est simple. Il nous faudra également un itérateur Output pour écrire les données copiées. Et, bien entendu, nous définirons le caractère d'arrêt. Soit quelque chose comme cela :

// version avec itérateurs
copy_until (first, last, out, stop_value) ;
// version avec un ensemble
copy_until (in, out, stop_value) ;

Nous nous intéresserons aux ordres des arguments et à leurs noms plus tard. Conceptuellement, ce que nous souhaitons faire est simplement :

copy (first, find (first, last, stop_value), out) ;

Le meilleur algorithme que vous puissiez écrire est : pas d'algorithme ; si vous pouvez effectuer le travail à l'aide d'algorithmes standards, il serait stupide d'écrire le vôtre.

Donc, dans cette étape, le but est de voir si ce que nous voulons faire est déjà faisable à l'aide d'algorithmes standards. Si ça l'est, nous avons fini - le problème est résolu. Au pire, la seule chose à faire est d'emballer la solution standard dans notre fonction.

Comme évoqué ci-dessus, le problème que nous essayons de résoudre est juste :

copy (first, find (first, last, stop_value), out) ;

Cela semble vouloir dire que nous avons fini - il n'y a aucun besoin d'écrire un algorithme quand une simple ligne fait le travail.

Mais, il y a un problème. Ce code ne fonctionne pas lorsque les itérateurs de la source sont des itérateurs Input. Pour comprendre pourquoi, mettons ce code sur deux lignes :

auto p = find (first, last, stop_value) ;
copy (first, p, out) ;

Avec des itérateurs Forward, vous pouvez effectuer plusieurs passes sur une suite de données, mais avec des itérateurs Input, vous ne pouvez effectuer qu'une seule passe. La recherche s'effectue en une passe, et comme vous ne pouvez en effectuer qu'une, la copie ne fonctionne pas. Avec des itérateurs Input, la recherche et la copie ne peuvent être effectuées séparément - elles doivent être effectuées en une passe.

Il existe une surcharge de getline() qui peut lire jusqu'à un caractère spécifique - newline par défaut. Mais cela ne fonctionne que lorsque l'entrée est un flux et la sortie une chaîne (j'ignore ici, volontairement, la version utilisant un tampon de caractères), et elle peut utiliser uniquement un caractère comme valeur d'arrêt. Cela est trop rigide pour être généralement utile. Il n'existe pas d'algorithmes standards capables d'effectuer la recherche et la copie en une seule passe (du moins, pas sans faire quelque chose de particulier, comme trafiquer la fonction find_if()). Ce qui signifie que nous allons devoir écrire la nôtre.

Lorsque vous écrivez votre propre algorithme, il est conseillé de copier le style des algorithmes standards autant que possible. Faire les choses d'une façon différente et étonnante va uniquement embrouiller et ennuyer quiconque essaiera de l'utiliser, et vous demandera plus de travail pour documenter clairement en quoi votre algorithme se différencie du standard.

Définir l'interface est une des étapes les plus importantes du processus… si vous faites les choses à moitié, vous allez pratiquement tout gâcher. Donc, prenez votre temps, et réfléchissez longtemps et profondément. Plus vous y passerez de temps et plus vous en gagnerez, non seulement en écriture, mais aussi lors de futures utilisations.

Étape 3-a : Déterminer le nom de la fonction▲

Étape 3-b : Déterminer les arguments▲

copy_if (
  InputIterator first,
  InputIterator last,
  OutputIterator out,
  UnaryPredicate f) ;

copy_until (
  InputIterator first,
  InputIterator last,
  OutputIterator out,
  ??? stop) ;

copy_until (
  InputIterator first,
  InputIterator last,
  OutputIterator out,
  typename iterator_traits < InputIterator >::value_type stop) ;

copy_until (
  istream_iterator < string > {in},
  istream_iterator < string > {},
  out,
  "end");

copy_until (
  InputIterator first,
  InputIterator last,
  OutputIterator out,
  T const& stop) ;

template <
  typename InputIterator,
  typename OutputIterator,
  typename T >
auto copy_until (
  InputIterator first,
  InputIterator last,
  OutputIterator out,
  T const& stop) ;

copy_until (
  Range in,
  OutputIterator out,
  T const& stop) ;

copy_until (
  Range const& in,
  OutputIterator out,
  T const& stop) ;

template <
  typename Range,
  typename OutputIterator,
  typename T >
auto copy_until (
  Range const& in,
  OutputIterator out,
  T const& stop) ;

template <
  typename InputIterator,
  typename Sentinel,
  typename OutputIterator,
  typename T >
auto copy_until (
  InputIterator first,
  Sentinel last,
  OutputIterator out,
  T const& stop) ;

Étape 3-c : Déterminer le type de la valeur de sortie▲

auto copy_until (/*…*/) - >
  pair <InputIterator, OutputIterator>

auto src = vector < int > {1, 2, 3, 4};
auto out = vector < int > {};

// version avec itérateurs
auto result1 = copy_until (begin (src), end (src),
back_inserter (out), 3) ;
// out contient maintenant {1,2}

// Positionne l'itérateur à l'endroit où la copie s'est arrêtée
// pointe sur 3 dans le src
auto it1 = get < 0 > (result1) ;

// Maintenant essayons de le modifier
*it1 = 0 ; // pas de problème, src devient {1,2,0,4}

auto src = vector < int > {1, 2, 3, 4};
auto out = vector < int > {};

// version avec plage de données
auto result2 = copy_until (src, back_inserter (out), 3) ;
// out contient maintenant {1,2}

// Positionne l'itérateur à l'endroit où la copie s'est arrêtée
// pointe sur 3 dans le src
auto it2 = get < 0 > (result2) ;

// Essayons maintenant de le changer
*it2 = 0 ; // erreur de compilation

Étape 3-d : Déterminer les contrats de l'interface (les exigences sur les valeurs des arguments et le résultat)▲

Étape 3-e : Déterminer les concepts (les exigences sur les types d'arguments et le résultat)▲

template <
    InputIterator InIt,
    OutputIterator OutIt,
    typename T>
  requires
    Assignable <ValueType<OutIt>, ValueType<InIt>> &&
    EqualityComparable <ValueType <InIt>, T >
auto copy_until (
    InIt first,
    InIt last,
    OutIt out,
    T const& t) - >
  pair <InIt, OutIt> ;

template < InputRange Rng, typename T >
  requires
    Assignable <ValueType <OutIt>, ValueType <Rng>> &&
    EqualityComparable <ValueType<Rng>, T>
auto copy_until (
    Rng const & rng,
    OutIt out,
    T const& t) - >
  pair <Iterator <Rng const&>, OutIt> ;

Arrivés ici, la plupart des programmeurs vont s'en aller écrire l'algorithme (en fait, la plupart des programmeurs l'auront fait après les étapes 1 ou 2). Vous pourriez faire ça, mais je vous recommande d'écrire les tests avant plutôt qu'après. Si vous n'agissez pas de cette façon, vous n'écrirez probablement jamais les tests.

Il n'existe pas de bibliothèques de tests standards, je vais donc utiliser Boost.Test. Il existe d'autres bonnes bibliothèques de tests - j'ai eu de bonnes expériences avec celle de Google - mais celle de Boost est très riche, facile d'utilisation et… c'est Boost. Je ne rentrerai pas dans les détails de l'écriture de tests avec Boost.Test dans cet article, je vais juste vous montrer quelques exemples.

En premier lieu, il y a le test évident… La fonction fait-elle ce qu'elle est supposée faire ? Vous devrez la tester avec les deux versions (itérateur et ensemble). Voici le test de la version itérateur :

BOOST_AUTO_TEST_CASE (copy_until_iterator)
{
    using std::begin ;
    using std::end ;

    auto const src = std::vector <int> {1, 2, 3, 4, 5};
    auto const expected = std::vector <int> {1, 2, 0, 0};
    auto dest = std::vector <int> {0, 0, 0, 0};
    auto const stop_value = 3 ;
    auto const stop_value_index =
      std::distance (begin (src),
        std::find (begin (src), end (src), stop_value));
   
    auto const result = indi::copy_until (
      begin (src), end (src), begin (dest), stop_value) ;

    // Vérification que la séquence en sortie est correcte
    BOOST_CHECK_EQUAL_COLLECTIONS (
      begin (expected), end (expected),
      begin (dest), end (dest));
   
    auto const in_it = std::get <0> (result) ;
    auto const out_it = std::get <1> (result) ;

    // Vérification du résultat sur l'itérateur d'entrée
    BOOST_CHECK_EQUAL (stop_value, *in_it) ;
    BOOST_CHECK_EQUAL (stop_value_index,
      std::distance (begin (src), in_it));
   
    // Vérification du résultat sur l'itérateur de sortie
    BOOST_CHECK_EQUAL (0, *out_it) ;
    BOOST_CHECK_EQUAL (stop_value_index,
      std::distance (begin (dest), out_it));
}

Ceci n'est pas destiné à être un tutoriel sur la façon d'écrire des tests, c'est seulement le code que je montre. Cependant, il y a d'autres choses que vous pourriez vouloir tester :

• une séquence d'entrée vide (rien ne doit être copié),
• une séquence d'entrée ne contenant pas la valeur d'arrêt (toute la suite doit être copiée),
• une séquence d'entrée dont le premier terme est la valeur d'arrêt (rien ne doit être copié),
• une séquence source d'itérateurs de type Input,
• une séquence de sortie d'itérateurs de type Output.

Cette liste n'est pas exhaustive, bien sûr - tout ce qui peut aller de travers doit être testé.

Naturellement, tous les tests vont rater… Ils ne vont même pas compiler. Ce n'est pas surprenant, l'algorithme n'existe pas encore. C'est l'étape suivante.

Il est enfin temps d'écrire la fonction.

Beaucoup de travail a déjà été fait. L'interface a déjà été définie, nous avons donc le squelette de la fonction, l'espace de nom, et le fichier qui va recevoir l'algorithme. Tout rassemblé, nous obtenons ceci :

// indi/copy_until.hpp

#ifndef INDI_INC_copy_until_
#define INDI_INC_copy_until_

#include <iterator>
#include <utility>
 
namespace indi {

namespace copy_until_detail {

using std::begin ;

template <typename Range>
auto adl_begin (Range & r) - > decltype (begin (r));
template <typename Range>
auto adl_begin (Range const & r) - > decltype (begin (r));
 
} // namespace copy_until_detail

template <
  typename InputIterator,
  typename OutputIterator,
  typename T >
auto copy_until (
    InputIterator first,
    InputIterator last,
    OutputIterator out,
    T const& stop) - >
  std::pair <InputIterator, OutputIterator>
{
  // à définir
}

template <
  typename Range,
  typename T>
auto copy_until (
    Range const& r,
    OutputIterator out,
    T const& stop) - >
  std::pair <
    decltype (copy_until_detail::adl_begin (r)),
    OutputIterator >
{
  // à définir
}

} // namespace indi

#endif // include guard

Il n'y a aucune raison de dupliquer le code, nous pouvons simplement écrire la version « ensemble » à l'aide de la version « itérateur » (ou vice versa).

template <
  typename Range,
  typename T>
inline auto copy_until (
    Range const& r,
    OutputIterator out,
    T const& stop)
{
    using std::begin ;
    using std::end ;

    return copy_until (begin (r), end (r), out, stop) ;
}

Et voilà la moitié du travail de fait !

Le corps de la fonction avec itérateurs n'est pas trop difficile à écrire à partir des exigences. Tant que l'itérateur Input courant n'est pas égal à l'itérateur de fin et qu'il ne pointe pas sur la valeur d'arrêt, la valeur qu'il pointe est copiée-assignée à l'itérateur Output, puis les itérateurs Input et Output avancent. L'itérateur Input et l'itérateur Output sont tous les deux renvoyés à la fin de la fonction :

template <
  typename InputIterator,
  typename OutputIterator,
  typename T>
auto copy_until (
    InputIterator first,
    InputIterator last,
    OutputIterator out,
    T const& stop)
{
    while (bool (first ! = last) && !bool (*first == stop))
        *out ++ = *first ++;
   
    return std::make_pair (first, out) ;
}

Et voilà ! Vous pouvez maintenant passer les tests que vous avez écrits précédemment sur ces fonctions. Si tous les tests passent, vous avez fini.

Ainsi écrit, l'algorithme est aussi simple qu'il peut l'être, et il ne peut réellement pas être plus simple s'il doit fonctionner avec des itérateurs Input. Pour utiliser des itérateurs Forward ou mieux, vous avez l'option d'utiliser find/copy :

auto const p = std::find (first, last, stop) ;
return std::make_pair (p, std::copy (first, p, out));

Il ne semble pas y avoir beaucoup à gagner, même si c'est possible. Cela demanderait de parcourir la suite de données d'entrée deux fois - une fois pour trouver la valeur d'arrêt, la deuxième fois pour copier - tandis que la solution écrite ci-dessus parcourt une seule fois la séquence, effectuant la comparaison et la copie en même temps.

Il existe, cependant, un cas où il peut être profitable d'effectuer la recherche et la copie séparément. Lorsque vous avez des éléments dans une séquence d'entrée contiguë - comme un vecteur ou un tableau - et que la séquence de sortie est également contiguë et que le passage du type d'entrée au type de sortie est trivial, vous pouvez copier les éléments avec un memcopy() ultra rapide de la séquence totale d'un seul coup. En premier lieu, vous effectuez la recherche pour obtenir la taille du bloc à copier - qui est situé dans une zone mémoire contiguë, et d'une opération en lecture seule uniquement, puis vous effectuez la copie rapide de bloc. Il y a de fortes chances que ce soit plus rapide qu'une comparaison élément par élément suivie d'une copie (vous devez tester bien entendu, cette optimisation peut n'être valable que sur certaines plateformes seulement).

En supposant que vous vouliez faire cette optimisation, vous devez trouver une façon de déterminer si vous pouvez utiliser la version optimisée ou bien si vous devez retomber sur la version générale. Vous pouvez faire cela au moment de la compilation.

namespace copy_until_detail {

struct general_version {};
struct optimized_version {};

template <
  typename InputIterator,
  typename OutputIterator,
  typename T >
auto copy_until (
    InputIterator first,
    InputIterator last,
    OutputIterator out,
    T const& stop,
    general_version) - >
  std::pair < InputIterator, OutputIterator >
{
    while (bool (first ! = last) && bool (*first ! = stop))
        *out ++ = *first ++;
   
    return std::make_pair (first, out) ;
}

template <
  typename InputIterator,
  typename OutputIterator,
  typename T>
auto copy_until (
    InputIterator first,
    InputIterator last,
    OutputIterator out,
    T const& stop,
    optimized_version) - >
  std::pair < InputIterator, OutputIterator >
{
    auto const p = std::find (first, last, stop) ;
    return std ::make_pair (p, std ::copy (first, p, out));
}
 
} // namespace copy_until_detail

template <
  typename InputIterator,
  typename OutputIterator,
  typename T>
inline auto copy_until (
    InputIterator first,
    InputIterator last,
    OutputIterator out,
    T const& stop) - >
  std::pair < InputIterator, OutputIterator >
{
    return copy_until_detail ::copy_until (
      first, last, out, stop,
      std::conditional_t <
      ???,
      optimized_version,
      general_version>{});
}

Qu'est-ce qui vient dans le « ??? » pour sélectionner la version optimisée ? Les prérequis sont listés ci-dessous :

• la séquence d'entrée doit être contiguë ;
• la séquence de sortie doit être contiguë ;
• le passage du type de valeur de la séquence d'entrée au type de valeur de sortie doit être trivial.

Vous pouvez ajouter d'autres choses à cette liste, en fonction des spécifications d'interface de copy_until(). Par exemple, je n'ai encore rien dit au sujet des exceptions, mais qu'est-ce qui nous garantit que, si une exception est levée lors de la lecture, la comparaison ou le cast d'un élément, les éléments précédents auront été correctement copiés dans la séquence de sortie ? Ce sera le cas dans la version générale écrite dans l'étape 5, mais non pour la version optimisée - en effet si la lecture ou la comparaison plantent pendant la recherche, rien du tout ne sera mis dans la séquence de sortie, car la copie n'aura pas débuté. Vous pourriez ajouter un test : si la lecture, la comparaison ou le cast lèvent une exception… Mais je recommanderais de ne pas avoir du tout cette exigence dans la spécification d'interface. Ajouter cette exigence dans la spécification d'interface rend la fonction plus prédictive dans le cas d'une exception, mais rend ses implémentation et optimisation plus difficiles. Je dois équilibrer entre spécifier suffisamment pour rendre l'algorithme aussi pratique que possible et ne pas surspécifier. Mon opinion est que : spécifier le comportement dans le cas d'exception(4)­ relève de la surspécification.

Tester que l'affectation est triviale est facile :

using src_type = typename
  std::iterator_traits <InputIterator>::value_type ;
using dest_type = typename
  std::iterator_traits <OutputIterator>::value_type ;

std::is_trivially_assignable <dest_type, src_type>::value

Malheureusement, le C++ ne comporte aucun test permettant de savoir si un itérateur se réfère à une suite de données contiguës(5). Le mieux que nous pouvons faire est de tester si l'itérateur est à accès aléatoire. Il est possible pour un itérateur d'être à accès aléatoire et non séquentiel - par exemple std::deque - mais cela est très rare - par exemple parmi les six itérateurs à accès aléatoire définis explicitement dans le standard, seul std::deque n'est pas séquentiel. Ce n'est pas un gros problème si un itérateur à accès aléatoire mais non séquentiel est utilisé avec la version optimisée - il peut y avoir un problème de performances, mais le comportement restera correct. Et de toute façon, de tels itérateurs sont assez rares. Tant qu'il n'existera pas de façon de tester si un itérateur est séquentiel, tester seulement si l'itérateur est à accès aléatoire fonctionnera (mais là encore, vous devez effectuer le test sur votre plateforme pour voir cette optimisation est digne d'intérêt).

Ainsi, si nous voulons tester si l'itérateur est à accès aléatoire, nous ferons :

using src_it_cat = typename
  std::iterator_traits <InputIterator>::iterator_category ;

std::is_base_of <std::random_access_iterator_tag, src_it_cat>::value

Et, la même chose pour l'itérateur de sortie.

En rassemblant tout cela, la fonction d'aiguillage devient :

template <
  typename InputIterator,
  typename OutputIterator,
  typename T>
inline auto copy_until (
    InputIterator first,
    InputIterator last,
    OutputIterator out,
    T const& stop) - >
  std::pair < InputIterator, OutputIterator >
{
    using src_type = typename
      std::iterator_traits < InputIterator >::value_type ;
    using dest_type = typename
      std::iterator_traits < OutputIterator >::value_type ;
    using src_it_cat = typename
      std::iterator_traits < InputIterator >::iterator_category ;
    using dest_it_cat = typename
      std::iterator_traits < OutputIterator >::iterator_category ;

    return copy_until_detail::copy_until (
      first, last, out, stop,
      std::conditional_t <
        std::is_trivially_assignable < dest_type,
            src_type >::value &&
          std::is_base_of <
            std::random_access_iterator_tag,
            src_it_cat >::value &&
          std::is_base_of <
            std::random_access_iterator_tag,
            dest_it_cat >::value,
        optimized_version,
        general_version > {}) ;

Le but de cet article n'était pas vraiment d'écrire la fonction spécifique copy_until(), mais plutôt d'étudier le processus de création d'un nouvel algorithme conforme au standard. Cela m'étonne de voir combien de programmeurs n'ont aucune idée à propos de la bibliothèque standard d'algorithmes ou seulement de vagues notions sur une poignée d'algorithmes les plus utilisés.

Je pense qu'écrire un algorithme conforme au standard devrait être une étape nécessaire dans tous les tutoriels basiques sur le C++ - c'est si simple et ça apprend tellement. Vous pouvez choisir d'effectuer cet exercice de façon superficielle ou bien creuser profondément - cet exercice est valable aussi bien pour les débutants que pour les programmeurs expérimentés en C ++.

Je ne plaide pas l'écriture de vos propres algorithmes au lieu d'utiliser ceux de la bibliothèque standard (ou ceux de Boost). Il n'y a pas de mal à essayer d'en réimplémenter un ou deux pour s'entraîner, mais la réalité est qu'il a tellement d'algorithmes potentiellement utiles n'existant pas dans la bibliothèque standard (ou chez Boost) que cela n'est pas nécessaire. Lorsque vous programmez normalement, il y a des chances que vous rencontriez une situation dans laquelle vous avez besoin de quelque chose potentiellement réutilisable et qui n'existe pas dans la bibliothèque standard - une parfaite opportunité de mettre la théorie en pratique.

Gardez aussi à l'esprit que j'ai simplement esquissé comment vous pouviez creuser le sujet avec une simple fonction copy_until(). J'ai abordé les deux versions « itérateur » et « ensemble », mais vous pouvez avoir également des versions qui prennent un autre argument - une fonction objet qui effectue la comparaison autrement qu'avec '==' (et vous pouvez avoir les versions basiques s'y reportant en utilisant std::equal_to).

Vous avez ici les étapes basiques, que j'ai soulignées, à appliquer lorsque vous écrirez votre propre algorithme « standard » :

1. Spécifiez clairement le problème : une compréhension vague du problème vous garantit pratiquement une solution merdique. Prenez le temps de comprendre clairement ce qui est nécessaire.
2. Essayez d'en faire le moins possible. Recherchez les solutions préexistantes plutôt que d'essayer de réinventer la roue.

3. Définissez l'interface :

   1. Déterminez le nom de la fonction : ainsi que l'espace de nom et le nom du fichier d'en-têtes, etc.,
   2. Déterminez les arguments : considérez ce qui est nécessaire pour que la fonction fasse ce qu'elle doit faire, ainsi que l'ordre et le type des arguments,
   3. Déterminez le type de retour : souvent le type de retour est prédéterminé, mais quand ça ne l'est pas, prenez le temps de considérer de quelles informations utiles les appelants ont besoin de connaître sur ce que la fonction fait,
   4. Déterminez les contrats d'interface (les exigences sur les valeurs des arguments et du résultat) : spécifiez les conditions initiales et les conditions finales au minimum dans la documentation,
   5. Déterminez les concepts (les exigences sur les types d'arguments et de résultat) : les concepts ne sont pas complètement standardisés, mais essayez de spécifier les concepts utilisés par votre algorithme en des termes qui vous permettront de profiter des concepts lorsqu'ils arriveront (ou encore, pensez à Boost. ConceptCheck).
4. Écrivez les tests : testez les opérations normales puis tous les cas aux limites en essayant de penser à tout ce qui peut aller de travers.
5. Écrivez l'algorithme.
6. (Optionnel) Optimisez. Ne pas oublier de profiler !

Si vous êtes tenté de vous essayer à l'écriture d'un ou deux algorithmes pour

augmenter votre aisance en C++ et que vous ne savez pas quoi faire, voici quelques suggestions que vous pouvez considérer, et souvenez-vous, vous pouvez creuser les sujets aussi loin qu'il vous plaira :

• Pour les débutants, essayez un algorithme qui renvoie vrai si une suite de données avec itérateurs bidirectionnels est un palindrome. Ceci peut être délicat ; je l'ai utilisé dans un concours il y a plusieurs années de cela, et pratiquement personne n'y est arrivé - y compris certains qui pensaient être très bons en C++ (bien que, honnêtement, ça en dise probablement plus sur le triste état de l'expertise en C++ que sur la difficulté du défi). Essayez d'effectuer le minimum absolu d'itérations et de comparaison.

• Maintenant, un exercice légèrement plus délicat, mais toujours bon pour les débutants. La bibliothèque standard comprend min_element(), max_element() et minmax_element() - qui renvoient des itérateurs pointant vers le plus petit ou le plus grand (ou les deux) des éléments d'une suite. Essayez d'écrire un algorithme renvoyant une paire contenant la plus petite (ou plus grande, ou les deux) valeur (pas un itérateur, mais bien une valeur) d'une suite et le nombre de fois où elle apparaît, en effectuant une seule passe à travers la suite de façon à pouvoir utiliser un itérateur Input.
• Celui-ci est spécifique aux suites de caractères, mais je le trouve assez utile. Le but est de prendre n'importe quelle suite de caractères - y compris les caractères Unicode et pas seulement les char - et de les convertir en limace. Ce qui implique deux choses : convertir toutes les majuscules en minuscules et remplacer tout ce qui n'est pas alphanumérique par un tiret. La limace ne peut pas commencer par un tiret, se terminer par un tiret, ni comprendre deux tirets consécutifs. Vous devrez prendre une paire d'itérateurs Input sur la séquence en entrée, un itérateur sur la séquence de sortie, et un std::locale (que vous pourrez utiliser avec des choses comme std::tolower() et std::isalnum(). Avec l'itérateur Output, vous devrez renvoyer également un booléen à faux si la sortie débute par un chiffre ou si la sortie est vide. Ce sujet n'est pas facile, mais pas non plus du niveau expert.

• En voici un véritablement difficile. À partir d'une suite définie par des itérateurs Forward, créez une suite faite de paires, où chaque paire contient une des valeurs de la suite et le nombre de fois où elle apparaît, triée dans l'ordre des valeurs. En d'autres termes, vous générez un histogramme des données de la séquence d'entrée. Par exemple, la séquence {7, 7, 7, 9, 3, 1, 1} doit produire la séquence {(1, 2), (3, 1), (7, 3), (9, 1)} en sortie. Cela demande plusieurs passes à travers la suite entrée pour éviter tout besoin d'allocation dynamique, mais essayez de le faire de la façon la plus efficace possible.

Si vous vous essayez à l'un d'entre eux, n'hésitez pas à me le faire savoir en commentaire (ne vous embêtez pas à essayer de coller le code dans le commentaire - utilisez un espace de stockage et collez le lien dans le commentaire).

Bon codage !

Cet article est une traduction autorisée de l'article de paru sur Explicit C++.

Merci aussi à Ced pour sa relecture orthographique.