Écrire une fonction « split() »

É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?

Version avec expression régulière

Les expressions régulières constituent un médium merveilleux (même si quelque peu difficile d'approche dû à la syntaxe) pour réaliser des traitements sur des chaînes de caractères. Sans surprises, il est possible d'implémenter un split() tout simple à l'aide ce cet outil :

// inclure string, regex, vector, algorithm, iterator
auto split(const string &s, const regex &re) {
   vector<string> res;
   copy(sregex_token_iterator{ begin(s), end(s), re, -1 }, sregex_token_iterator{},
        back_inserter(res));
   return res;
}

Un exemple d'utilisation pour séparer une chaîne en sous-chaîne à partir de blancs serait :

#include <vector>
#include <string>
#include <regex>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
auto split(const string &s, const regex &re) {
   vector<string> res;
   copy(sregex_token_iterator{ begin(s), end(s), re, -1 }, sregex_token_iterator{},
        back_inserter(res));
   return res;
}
int main() {
   regex re{ "\\s+" };
   if (string str; getline(cin, str))
      for (const auto & s : split(s.string(), re))
         cout << s << endl;
}

Un autre exemple, qui séparerait un chemin d'un système de fichiers à la Microsoft Windows sur la base du séparateur '\\' (notez le dédoublement, du fait que \ sert de caractère d'échappement en C++) :

#include <vector>
#include <string>
#include <filesystem>
#include <regex>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
namespace fs = std::filesystem;
auto split(const string &s, const regex &re) {
   vector<string> res;
   copy(sregex_token_iterator{ begin(s), end(s), re, -1 }, sregex_token_iterator{},
        back_inserter(res));
   return res;
}
int main() {
   auto here = fs::current_path();
   regex re{ "\\\\" }; // ou regex re{ R"(\\)" }; car il faut deux \ pour l'expression régulière
   for (const auto & s : split(here.string(), re))
      cout << s << endl;
}

C'est quand même pas mal, n'est-ce pas?

Et pour la vitesse?

Étant donné la simplicité de la version reposant sur des expressions régulières et comparaison avec celle, plus manuelle, reposant sur un prédicat, la question de la vitesse relative d'exécution de ces deux versions se pose. J'ai donc écrit un très petit comparatif des deux versions sur la base d'un critère de séparation très simple : la présence d'au moins un blanc. Ceci nous mène d'une part à un prédicat qui se limite à déléguer à std::isspace(c,loc) pour un caractère c et un locale nommé loc donnés, et d'autre part à une expression régulière très simple se limitant à \s+ (au moins un blanc).

Évidemment, la qualité des mesures dans un test comme celui-ci sera fortement influencée par le critère de séparation, et j'ai choisi quelque chose de simple de manière délibérée. Notez aussi que les tests ont été écrits de manière à ne construire les objets qui sont coûteux à construire (le locale d'une part, le regex d'autre part) qu'une seule fois, pour ne pas fausser les résultats dans un sens ou dans l'autre.

#include <vector>
#include <string>
#include <regex>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <chrono>
#include <locale>
using namespace std;
using namespace std::chrono;
namespace manuel {
   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; });
   }
}
namespace re {
   auto split(const string &s, const regex &re) {
      vector<string> res;
      copy(sregex_token_iterator{ begin(s), end(s), re, -1 },
         sregex_token_iterator{},
         back_inserter(res));
      return res;
   }
}
template <class F, class ... Args>
auto test(F f, Args &&... args) {
   auto pre = high_resolution_clock::now();
   auto res = f(std::forward<Args>(args)...);
   auto post = high_resolution_clock::now();
   return make_pair(res, post - pre);
}

int main() {
   enum { N = 100'000 };
   const string texte = "J'aime mon prof";
   auto [n0, dt0] = test([texte, loc = locale{ "" }]{
      int n = 0;
      for (int i = 0; i != N; ++i)
         n += manuel::split(texte, [&](char c) { return isspace(c, loc); }).size();
      return n;
   });
   auto [n1, dt1] = test([texte, reg = regex{ "\\s+" }]{
      int n = 0;
      for (int i = 0; i != N; ++i)
         n += re::split(texte, reg).size();
      return n;
   });
   cout << N << " tests :"
        << "\n\t" << n0 << " mots en " << duration_cast<milliseconds>(dt0).count() << " ms manuel"
        << "\n\t" << n1 << " mots en " << duration_cast<milliseconds>(dt1).count() << " ms regex"
        << endl;
}

J'ai exécuté ce programme de test sur mon ordinateur portatif, utilisant MSVC (Visual Studio 2017.7) et l'implémentation de std::regex qui s'y trouve, et https://wandbox.org/ utilisant g++ HEAD 9.0.0 20180611 (expérimental). Les résultats furent les suivants :

MSVCg++
100000 tests :
        300000 mots en 136 ms manuel
        300000 mots en 1030 ms regex
100000 tests :
	300000 mots en 88 ms manuel
	300000 mots en 283 ms regex

Manifestement, la simplicité des expressions régulières est un plus à plusieurs égards, mais si la vitesse est souhaitée, il y a parfois lieu d'écrire le code requis soi-même, du moins pour le moment.

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !