Écrire une fonction split()

Il est fréquent qu'un programme traitant des chaînes de caractères doive séparer ce texte selon certains délimiteurs (des blancs, des points-virgules, des symboles d'affectation, etc.).

Écrire une fonction accomplissant cette tâche est quelque chose de relativement simple. Le langage C offre une fonction (strtok()) très rapide pour cette fin, mais cette fonction est dangereuse en situation de multiprogrammation (elle repose sur une variable statique locale à la fonction). Plusieurs langages comme Java et les langages .NET offrent une méthode (habituellement nommée split() ou Split()) pour faire ce travail à même les classes String ou string de leurs infrastructures respectives. Ces méthodes sont simples à utiliser mais varient en qualité.

Pour en savoir plus sur les divers types de caractères, voir cet article et cet article.

Pour une proposition de std::split() en vue de C++ 17, voir ../../Liens/Evolution-Cplusplus--Liens.html#bibliotheques_algorithmes

Il est possible en C++ d'écrire une telle fonction avec élégance à l'aide d'outils standards. Le présent article vous offrira quelques versions plutôt simples que vous pourrez raffiner à loisir :

Je vous invite d'ailleurs fortement à raffiner ces exemples.

Chaque version sera aussi facile à utiliser que les autres, mais comprendre la deuxième demandera une certaine affinité avec les templates et la programmation générique, alors que la troisième bénéficiera de l'apport d'expressions λ. Comme il se doit, la complexité sera du côté du code serveur (de la fonction elle-même), pas du côté du code client.

Version pour caractères traditionnels seulement

Nous présumerons que notre but est de déposer les divers jetons (bouts de texte séparés par des délimiteurs) dans un vecteur standard puis de les afficher, un jeton par ligne. Ceci nous donnera une base de travail simple à comprendre.

Notre petite fonction split() prendra en paramètre le texte original et un caractère servant de délimiteur.

Tant qu'il y restera au moins une occurrence du délimiteur dans le texte original, elle fera une copie de qui se trouve entre l'occurrence précédente et l'occurrence courante du délimiteur et insérera cette copie dans un vecteur standard.

#include <vector>
#include <algorithm>
#include <string>
std::vector<std::string>
   split(const std::string & src, char delim) {
   using namespace std;
   vector<string> v;
   auto p = begin(src);
   for(auto q = find(p, end(src), delim); q != end(src); q = find(++p, end(src), delim)) {
      v.emplace_back(p, q);
      p = q;
   }
   if (p != end(src))
      v.emplace_back(p, end(src));
   return v;
}

S'il reste du texte après la dernière occurrence du délimiteur, ce texte sera inséré à la fin du vecteur. Enfin, le vecteur contenant tous les jetons sera retourné au code client.

Le code client proposé à droite montre un appel valide à split(), utilisant l'espace comme délimiteur.

On y présente ensuite deux manières d'afficher les jetons à la console : une conventionnelle, lente et lourde, avec une répétitive for, et une plus compacte et plus rapide avec un itérateur sur un flux en sortie).

// ...
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
   auto v = split(string("allo man chose genre t'sais"), ' ');
   //
   // affichage conventionnel
   //
   for(const auto &s : v)
      cout << s << endl;
   //
   // projection à l'aide d'un itérateur
   //
   copy(begin(v), end(v) ostream_iterator<string>(cout, "\n"));
}

Version pour tous types de caractères

Nous raffinerons maintenant notre code pour qu'il puisse traiter des chaînes de quelque sorte de caractère que ce soit. Pour ce faire, nous profiterons du fait que std::string est un alias pour std::basic_string<char> et que nous pouvons rédiger split() pour que cette fonction soit générique sur la base du type de caractère auquel s'applique une chaîne donnée.

Dans le code ci-dessous, le type de caractère utilisé sera le paramètre générique nommé CType. Il servira à la fois de type pour le délimiteur, pour la sorte de chaîne de caractères et pour le texte dans le vecteur retourné.

Le code à droite montre clairement que, au type C près, l'algorithme de split() est le même que celui proposé dans la version précédente.

Pour vous en convaincre, vous n'avez qu'à prendre la version précédente pour y remplacer, de manière systématique, std::string par std::basic_string<char>. La similitude deviendra évidente.

#include <vector>
#include <algorithm>
#include <string>
template <class C>
   std::vector<std::basic_string<C>>
      split(const std::basic_string<C> & src, C delim) {
   using namespace std;
   vector<basic_string<C>> v;
   auto p = begin(src);
   for(auto q = find(p, end(src), delim); q != end(src); q = find(++p, end(src), delim)) {
      v.emplace_back(p, q);
      p = q;
   }
   if (p != end(src))
      v.emplace_back(p, end(src));
   return v;
}

Le code client proposé à droite montre clairement que l'utilisation de notre fonction split() est identique peu importe le type de caractère dans la chaîne suppléée lors de l'invocation de la fonction.

La mécanique de déduction des types des paramètres du langage détermine seule le type générique C. Le code client a pour seule exigence d'être cohérent.

#include <string>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
   {
      auto v = split(string("allo man chose genre t'sais"), ' ');
      //
      // affichage conventionnel
      //
      for(const auto &s : v)
         cout << s << endl;
      //
      // projection à l'aide d'un itérateur
      //
      copy(begin(v), end(v), ostream_iterator<string>(cout, "\n"));
   }
   cout << "\n--------------------\n\n";
   {
      auto v = split(wstring(L"yo man wow genre cool full"), L' ');
      //
      // affichage conventionnel
      //
      for(const auto &s : v)
         wcout << s << endl;
      //
      // projection à l'aide d'un itérateur
      //
      copy(begin(v), end(v), ostream_iterator<wstring>(cout, L"\n"));
   }
}

Vous remarquerez le recours à des blocs anonymes dans le code client ci-dessus; ils ne sont là que pour délimiter la vie des variables se trouvant à l'intérieur (comme le vecteur v). J'ai simplement été paresseux.

Version avec prédicat

Pour élargir la gamme de possibilités de notre fonction split(), voici une version qui couvrira tous les cas vus ci-dessus, en permettant de séparer une chaîne sur la base de critères plus complexes que celle de la présence d'un caractère précis. Avec cette version, nous pourrions par exemple réaliser la segmentation sur la base de plusieurs caractères (un blanc, un symbole de ponctuation, une majuscule, etc.)

Cette version sera donc composée de deux implémentations distinctes, soit :

  • La version générale qui utilise un prédicat comme critère de segmentation, et
  • La version séparant sur la base d'un symbole délimiteur, et qui délègue (dans ce cas) le travail vers la version générale en lui suppléant un critère correspondant à retourner true seulement si le délimiteur est rencontré

Pour l'essentiel, le code proposé ici est le même que dans les versions précédentes, à ceci près que la recherche du point de segmentation dans la version générale utilise std::find_if() plutôt que std::find().

Je me suis permis d'utiliser auto en tant que type de retour, pour alléger l'écriture.

// ... inclusions et using...
template <class C, class Pred>
   auto split(const std::basic_string<C> &src, Pred crit) {
      using namespace std;
      using str_type = basic_string<C>;
      vector<str_type> v;
      auto p = begin(src);
      for (auto q = find_if(p, end(src), crit); q != end(src); q = find_if(++p, end(src), crit)) {
         v.emplace_back(p, q);
         p = q;
      }
      if (p != end(src))
         v.emplace_back(p, end(src));
      return v;
   }

template <class C>
   auto split(const std::basic_string<C> &src, C delim) {
      return split(src, [delim](C c) { return c == delim; });
   }

Un raffinement possible serait de permettre de traiter une séquence de symboles consécutifs respectant le prédicat comme un seul point de coupure, ce qui permettrait par exemple de transformer "a...b" en un vecteur de deux chaînes seulement avec le prédicat suivant :

[](char c){ return std::ispunct(c,std::locale{}); }

À titre comparatif, notre version actuelle donnerait un vecteur de quatre chaînes, soit "a", "", "" et "b". Comment y arriveriez vous?


Valid XHTML 1.0 Transitional

CSS Valide !