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.
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. |
|
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). |
|
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. |
|
|
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. |
|
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.
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 :
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. |
|
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?
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?
É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 :
| MSVC | g++ |
|---|---|
|
|
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.
Dans un courriel de mars 2019, Cleiton Santoia (un brillant programmeur brésilien, et un très chouette monsieur avec qui j'ai bavardé à quelques reprises en 2015) a suggéré cette solution au problème de la fonction split(). L'interface qu'il propose utilise deux paires d'itérateurs : une pour la séquence à parcourir, et une autre pour la séquence délimitante (sa solution accepte donc des délimiteurs de plusieurs caractères plutôt qu'une séquence parmi laquelle un symbole parmi plusieurs délimitera une sous-séquence) :
template <class ForwardIt1, class ForwardIt2, class OutIt>
void split( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, OutIt o ) {
auto sz = std::distance(s_first, s_last);
auto next = first;
while ( next != last ) {
next = std::search(first, last, s_first, s_last);
*o++ = { first, next } ;
first = next;
std::advance(first, sz);
}
}Ainsi, avec le programme suivant :
#include <iterator>
#include <string>
#include <string_view>
#include <vector>
#include <iostream>
int main() {
using namespace std;
auto s = R"(J'aime mon prof
... de "prog")"sv;
auto delims = " "sv;
vector<string> v;
split(begin(s), end(s), begin(delims), end(delims), back_inserter(v));
for(auto str : v)
cout << '\"' << str << '\"' << endl;
}... sa solution affichera ce qui suit (notez que le saut de ligne a été préservé dans la troisième sous-séquence) :
"J'aime"
"mon"
"prof
..."
"de"
""prog""Quelques liens pour enrichir le propos.
