Manipuler les std::string

Version imprimable

11/12/2008, 14h57
camboui

Manipuler les std::string

J'aimerais faire des manipulations de toutes sortes de chaines de caractères.
En utilisant les std::string (suivant votre conseil) et en évitant les fonctions C (vous me l'avez déconsillé).

Par exemple, tronquer une sous-chaine d'une chaine, remplacer une sous-chaine par une autre, faire des comparaisons contextuelles (par exemple o O ò Ò ö Ö Ô etc étant tous équivalents à la simple lettre o), remplacer les espaces consécutifs par un seul espace (tab, cr, lf, #160), etc.

J'en suis à "retomber" à utiliser strcmp(,) pour la plus basique des comparaison (ou strnicmp ou strncmp ou stricmp ou une fonction semblable perso), n'y a-t-il pas mieux avec la S(T)L ?
Merci.
11/12/2008, 15h32
koala01

Salut,

Si, bien sur, il y a mieux :D

Je te conseillerais volontiers de t'intéresser au fonction (r)find (r)replace, substr et autres de la classe std::string ainsi qu'à la valeur (constante et globale) std::string::npos ;)
11/12/2008, 15h37
Arzar
Ben là, il me semble qu'il n'y ait pas d'autres solutionsque d'éplucher la doc. Les fonctions de base de std::string permettent déjà de faire pas mal de chose :

std::string
operator+=
append
push_back
assign
insert
erase
replace
copy
swap

find
rfind
find_first_of
find_last_of
find_first_not_of
find_last_not_of
substr
compare

Si tu te sens à l'étroit, boost.string ouvrent des possiblités quasi infini :

http://www.boost.org/doc/libs/1_37_0...ring_algo.html

Case Conversion
to_upper()
to_lower()

Trimming
trim_left
trim_left_if()
trim_left_copy()
trim_left()
trim_right
trim_right_if()
trim_right_copy()
trim_right()
trim
trim_if()
trim_copy()
trim()

Predicates
starts_with()
istarts_with()
ends_with
iends_with()
contains
icontains()
equals
iequals()
lexicographical_compare
ilexicographical_compare()
all

Find algorithms
find_first
ifind_first()
find_last
ifind_last()
find_nth
ifind_nth()
find_head
find_tail
find_token
find_regex
find

Erase/Replace

replace/erase_first
replace_first_copy()
ireplace_first()
ireplace_first_copy()
erase_first()
erase_first_copy()
ierase_first()
ierase_first_copy()
replace/erase_last
replace_last_copy()
ireplace_last()
ireplace_last_copy()
erase_last()
erase_last_copy()
ierase_last()
ierase_last_copy()
replace/erase_nth
replace_nth()
replace_nth_copy()
ireplace_nth()
ireplace_nth_copy()
erase_nth()
erase_nth_copy()
ierase_nth()
ierase_nth_copy()
replace/erase_all
replace_all()
replace_all_copy()
ireplace_all()
ireplace_all_copy()
erase_all()
erase_all_copy()
ierase_all()
ierase_all_copy()
replace/erase_head
replace_head()
replace_head_copy()
erase_head()
erase_head_copy()
replace/erase_tail
replace_tail()
replace_tail_copy()
erase_tail()
erase_tail_copy()
replace/erase_regex
replace_regex()
replace_regex_copy()
erase_regex()
erase_regex_copy()
replace/erase_regex_all
replace_all_regex()
replace_all_regex_copy()
erase_all_regex()
erase_all_regex_copy()

Split

find_all()
ifind_all()
find_all_regex()
split()
split_regex()

Join
join
join_if

Predicates
is_classified
is_space
is_alnum
is_alpha
is_cntrl
is_digit
is_graph
is_lower
is_print
is_punct
is_upper
is_xdigit

Si tu es vraiment insatiable, il y a encore boost.tokeniser :

http://www.boost.org/doc/libs/1_37_0.../tokenizer.htm

Et tout au sommet de l'Olympe boost.regex :

http://www.boost.org/doc/libs/1_37_0...tml/index.html

Bon ceci dit, pour ne pas te mentir, les fonctions offertes par std::string ne sont pas toujours d'une simplicité biblique. Il faut lire attentivement la doc car parfois leurs comportements ne sont pas entièrement intuitifs.

Et pour la comparaison au fait ?
Ben, moi je fais comme ça :
Code:

1 2 3 4 5 6 std::string str = "toto"; if(str == "toto") { std::cout << "Plus besoin de strcmp !" << std::endl ; }
11/12/2008, 15h55
camboui

Ok, merci merci merci merci !!!

Pour boost on verra un peu plus tard.

Commençons donc avec std::string.
Alors comparer "toto" avec "toto", ça ira merci ;)

Mais pour comparer "toto" avec "TötÔ", ou "strasse" avec "Straße", je fais comment ? (sachant bien sûr qu'il y a "égalité" dans ces deux exemples)
11/12/2008, 16h38
Arzar

Citation:

Envoyé par camboui

Mais pour comparer "toto" avec "TötÔ", ou "strasse" avec "Straße", je fais comment ? (sachant bien sûr qu'il y a "égalité" dans ces deux exemples)

Ben là, typiquement, t'es mal :aie:

Bon plus sérieusement, ça dépasse mes compétences. En C comme en C++ les problèmes d'internationalisation sont toujours une horreur.
Désolé. Il va falloir attendre des avis plus qualifiés. :oops:
11/12/2008, 16h44
JolyLoic

Pour tout ce qui est lié à une gestion fine de l'internationalisation, il y a icu : http://www.icu-project.org/userguide/Collate_Intro.html

Citation:

Envoyé par camboui

Ok, merci merci merci merci !!!

Pour boost on verra un peu plus tard.

Commençons donc avec std::string.
Alors comparer "toto" avec "toto", ça ira merci ;)

Mais pour comparer "toto" avec "TötÔ", ou "strasse" avec "Straße", je fais comment ? (sachant bien sûr qu'il y a "égalité" dans ces deux exemples)

Je suis loin d'etre sur qu'il y a egalite dans ces cas. La maniere de comparer en tenant compte des locales, c'est:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <locale> #include <string> int main() { // utilisons la locale definie par le contexte (on demarre en locale "C") std::locale::global(std::locale("")); ... // construisons deux chaines std::string l, r; // et comparons les if (std::locale()(l, r)) { // l < r } else { // l >= r } }
Voir aussi les facets "collate" et "ctype" pour plus de fonctionalites.

J'ai fait un exercice simple.

Dans la faq il y a un exemple, retirer un caractère d'une string:
Code:

1 2 char c='0'; s.erase(std::remove_copy(s.begin(),s.end(),s.begin(),c),s.end());
J'ai voulu l'étendre pour retirer un ensemble de caractères et j'obtiens ceci (du vrai code C++ pur et dur ;)):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 struct IsCharList { const char *s_cp; size_t s_cplen; IsCharList(const char *cp,size_t cplen) :s_cp(cp),s_cplen(cplen) {} bool operator()(char c) { return (std::char_traits<char>::find(s_cp,s_cplen,c)!=0); } }; s.erase( std::remove_copy_if(s.begin(),s.end(),s.begin(),IsCharList("1234",4)) ,s.end());
En utilisant mes (mauvaises ?) habitudes, j'obtiens ceci:
Code:

1 2 3 4 5 6 7 8 std::string::iterator f,l,t; for (f=t=s.begin(),l=s.end();f!=l;++f) { char c=*f; if (memchr("1234",c,4)!=0) *t++=c; } s.erase(t,l);
Je me demande ce qui est le mieux... ou le moins pire...

08/01/2009, 14h48
3DArchi

Bah, tu pourrais encore abstraire IsCharList en 'templatisant' par rapport à char.

[EDIT]: pour ce qui est le moins pire. Je préfère encore ta première solution. Même si certains reprochent aux foncteurs à tous crins de complexifier la lecture du code.

Juste deux remarques :

1. Je ne comprend pas pourquoi tu utilises remove_copy et remove_copy_if. On peut écrire plus simplement :
Code:

1 2 3 s.erase(std::remove(s.begin(), s.end(), c), s.end()); s.erase(std::remove_copy_if(s.begin(),s.end(),IsCharList("1234",4)),s.end());
2.
Code:

1 2 return (std::char_traits<char>::find(s_cp,s_cplen,c)!=0);
Alors la, chapeau. Je ne savais même pas que des trucs de ce genre existaient dans la STL. :aie:
On peut aussi utiliser la forme générique de find
(find(begin, end, &val) renvoie end si val pas trouvé)
Code:

1 2 return (std::find (s_cp, s_cp + s_cplen, c) != s_cp + s_cplen );
Pour ce qui est le moins pire, je préfère aussi ta première solution, même si je l'aurais écrit instinctivement avec des string :D
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 struct IsCharList { public: IsCharList(const std::string& charList) : charList_(charList) {} bool operator()(char c) { return (charList_.find(c) != std::string::npos); } private: const std::string& charList_; }; s.erase(std::remove_if(s.begin(),s.end(),IsCharList("1234")) ,s.end());
Mais, c'est vrai que la libraire standard du C++ est un peu atrophié concernant les string. Il manque parfois des algorithmes essentiels (comme trim), il faut parfois coder des foncteurs pour des opérations qui semblent simples, comme ici...

A l'heure actuelle la seule solution élégante c'est boost...
Code:

1 2 3 4 s.erase( std::remove_if(s.begin(), s.end(), boost::is_any_of("1234")), s.end()); // ou boost::erase_all_regex(s, boost::regex("[1234]"));
J'espère qu'avec le c++0x, on aura droit à une nouvelle gamme d'algo pour les strings qui nous ferons oublier tous ces tracas. Il y a déjà un proposal qui va dans ce sens pour le TR2 et qui copie boost.

08/01/2009, 16h54
Jean-Marc.Bourguet

Citation:

Envoyé par Arzar

J'espère qu'avec le c++0x, on aura droit à une nouvelle gamme d'algo pour les strings qui nous ferons oublier tous ces tracas. Il y a déjà un proposal qui va dans ce sens pour le TR2 et qui copie boost.

TR2 est pour après C++-0X.

Quelle dommage...
A ce propos est-ce que le c++0x sera rigoureusement identique au TR1, ou peut-il y avoir des features n'appartenant ni au TR1, ni au TR2 ?

Bon, sinon j'ai fait un petit bench pour tester les différentes solutions proposées plus haut, car j'étais assez curieux de mesurer la "pénalité d'abstraction" imposés par les string ou par boost.

Il faudrait aussi les mesurer contre une solution purement en C, mais je suis pas assez bon en C pour faire quelque chose de vraiment performant. :aie:

Sans plus attendre le code du bench:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
#include <iostream>
#include <algorithm>
#include <string>
#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/regex.hpp>
#include <windows.h>
#include <time.h>
 
 
struct IsCharListCamboui
{
	const char *s_cp;
	size_t s_cplen;
	IsCharListCamboui(const char *cp , size_t cplen)
		:s_cp(cp),s_cplen(cplen) {}
	bool operator()(char c)
	{
		return (std::char_traits<char>::find(s_cp,s_cplen,c)!=0);
	}
};
 
struct IsCharListMe
{
public:
	IsCharListMe(const std::string& charList) : charList_(charList) {}
	bool operator()(char c)
	{
		return (charList_.find(c) != std::string::npos);
	}
private:
	const std::string& charList_;
};
 
void removeCharListCamboui1(std::string& s)
{
	std::string::iterator f, t, end;
	for (f = t = s.begin(), end = s.end() ; f != end ; ++f)
	{
		char c = *f;
		if (memchr("1234", c, 4) == 0)
			*t++ = c;
	}
	s.erase(t, end);
}
 
inline void removeCharListCamboui2(std::string& s)
{
	s.erase( std::remove_if(s.begin(),s.end(), IsCharListCamboui("1234", 4)) ,s.end());
}
 
inline void removeCharListMe(std::string& s)
{
	s.erase( std::remove_if(s.begin(),s.end(), IsCharListMe("1234")) ,s.end());
}
 
inline void removeCharListBoost1(std::string& s)
{
	s.erase( std::remove_if(s.begin(), s.end(), boost::is_any_of("1234")), s.end());
}
 
inline void removeCharListBoost2(std::string& s)
{
	boost::erase_all_regex(s, boost::regex("[1234]"));
}
 
std::string ul2string(unsigned long value)
{
	char buf[12];
	char *bufp=buf;
	for(;;)
	{
		*bufp++=(char)(value % 10u);
		if ((value/=10u)==0ul)
			break;
	}
	std::string s;
	s.resize(bufp-buf);
	std::string::iterator it_s=s.begin();
	while (bufp!=buf)
	{
		char c=*--bufp;
		*it_s=(char)(c+'0');
		++it_s;
	}
	return s;
}
 
int main()
{
  srand(time(NULL));
  LARGE_INTEGER ticksPerSecond;
  LARGE_INTEGER start;   // A point in time
  LARGE_INTEGER end;   // For converting tick into real time
  double diff;
 
  // get the high resolution counter's accuracy
  QueryPerformanceFrequency(&ticksPerSecond);
 
  std::string s;
 
  // test 1
  QueryPerformanceCounter(&start);
  for(int i = 0 ; i < 10000000 ; i++)
  {
	  s = ul2string(rand());
  }
  QueryPerformanceCounter(&end);
  diff = ((end.QuadPart - start.QuadPart) * 1000.0) / ticksPerSecond.QuadPart;
  std::cout << "Test Temoin (pas de traitement) : " << diff << std::endl;
 
  // test 1
  QueryPerformanceCounter(&start);
  for(int i = 0 ; i < 10000000 ; i++)
  {
	  s = ul2string(rand());
	  removeCharListCamboui1(s);
  }
  QueryPerformanceCounter(&end);
  diff = ((end.QuadPart - start.QuadPart) * 1000.0) / ticksPerSecond.QuadPart;
  std::cout << "Test Camboui 1 (acces direct par iterateur) : " << diff << std::endl;
 
  // test 2
  QueryPerformanceCounter(&start);
  for(int i = 0 ; i < 10000000 ; i++)
  {
	  s = ul2string(rand());
	  removeCharListCamboui2(s);
  }
  QueryPerformanceCounter(&end);
  diff = ((end.QuadPart - start.QuadPart) * 1000.0) / ticksPerSecond.QuadPart;
  std::cout << "Test camboui 2 (avec foncteur + char*) : " << diff << std::endl;
 
  //test 3 
   QueryPerformanceCounter(&start);
  for(int i = 0 ; i < 10000000 ; i++)
  {
	  s = ul2string(rand());
	  removeCharListMe(s);
  }
  QueryPerformanceCounter(&end);
  diff = ((end.QuadPart - start.QuadPart) * 1000.0) / ticksPerSecond.QuadPart;
  std::cout << "Test me (avec foncteur + string) : " << diff << std::endl;
 
  //test 4 
  QueryPerformanceCounter(&start);
  for(int i = 0 ; i < 10000000 ; i++)
  {
	  s = ul2string(rand());
	  removeCharListBoost1(s);
  }
  QueryPerformanceCounter(&end);
  diff = ((end.QuadPart - start.QuadPart) * 1000.0) / ticksPerSecond.QuadPart;
  std::cout << "Test boost (boost::is_any_of) : " << diff << std::endl;
 
 
  //test 5
  QueryPerformanceCounter(&start);
  for(int i = 0 ; i < 1000000 ; i++)
  {
	  s = ul2string(rand());
	  removeCharListBoost2(s);
  }
  QueryPerformanceCounter(&end);
  diff = ((end.QuadPart - start.QuadPart) * 1000.0) / ticksPerSecond.QuadPart;
  std::cout << "Test boost regex : " << diff << std::endl;
 
return 0;
}

Et les résultats !!

Petite précision : A chaque tour de boucle ce bench rafraichit une string globale avec un entier aléatoire (pour éviter que le compilo n'optimise la boucle) puis il élimine les chiffres 1, 2, 3 et 4 de ce nombre en une seule passe avec le code fournit par Camboui et le mien. Le bench est en mode release, avec visual studio 2005.

Test Temoin (pas de traitement) : 6277.61 ms
Uniquement la gestion des nombres aléatoires

Test Camboui 1 (accès direct par itérateur) : 11939.4 ms

Test camboui 2 (avec foncteur + char*) :11500.2 ms

Test me (avec foncteur + string) : 16637.4 ms
Un peu plus lent. Il y a bien une petite pénalité d'abstraction imposée par string.

Test boost (boost::is_any_of) : 14143.9 ms
8O Choc ! La version de boost, mille fois plus générique (boost::is_any_of) est plus rapide que mon foncteur. J'y crois pas ! :evilred:

Test boost regex : 10334.8 ms
8O Choc ! Les regex, élégantes, puissantes, versatiles, tellement plus simple à utiliser... mais lentes. Très lentes.

Au final, en ratio :
boucle à la main = x1
foncteur + char*= x1
foncteur + string = x1.44
boost::is_any_of = x1.22
Regex = x10.8

08/01/2009, 20h26
Jean-Marc.Bourguet

Citation:

Envoyé par Arzar

Quelle dommage...
A ce propos est-ce que le c++0x sera rigoureusement identique au TR1, ou peut-il y avoir des features n'appartenant ni au TR1, ni au TR2 ?

Il y a pas mal de choses dans C++0X qui n'étaient pas dans TR1. Pour commencer tout ce qui n'est pas bibliothèque.

Il y a des choses qui étaient dans TR1 qui n'ont pas été reprises dans C++0X. De mémoire, je ne vois qu'un certain nombre de fonctions mathématiques importées de C99 et d'usage plutôt spécialisé. Peut-être aussi des choses rendues inutiles par les changements dans le langage lui-même, mais il me semble que ce n'est pas le cas.

Il y a aussi des modifications dans les choses de TR1, principalement pour corriger des erreurs, oublis, tenir compte de l'expérience et profiter des changements dans le langage.
08/01/2009, 21h36
camboui

Citation:

Envoyé par Arzar

Et les résultats !!

Petite précision : A chaque tour de boucle ce bench rafraichit une string globale avec un entier aléatoire (pour éviter que le compilo n'optimise la boucle) puis il élimine les chiffres 1, 2, 3 et 4 de ce nombre en une seule passe avec le code fournit par Camboui et le mien. Le bench est en mode release, avec visual studio 2005.

Test Temoin (pas de traitement) : 6277.61 ms
Uniquement la gestion des nombres aléatoires

Test Camboui 1 (accès direct par itérateur) : 11939.4 ms

Test camboui 2 (avec foncteur + char*) :11500.2 ms

Test me (avec foncteur + string) : 16637.4 ms
Un peu plus lent. Il y a bien une petite pénalité d'abstraction imposée par string.

Test boost (boost::is_any_of) : 14143.9 ms
8O Choc ! La version de boost, mille fois plus générique (boost::is_any_of) est plus rapide que mon foncteur. J'y crois pas ! :evilred:

Test boost regex : 10334.8 ms (missing digit ?)
8O Choc ! Les regex, élégantes, puissantes, versatiles, tellement plus simple à utiliser... mais lentes. Très lentes.

Au final, en ratio :
boucle à la main = x1
foncteur + char*= x1
foncteur + string = x1.44
boost::is_any_of = x1.22
Regex = x10.8

Wow ! 8O
Et t'as même repris ma fonction ul2string() de l'autre discussion 8-)

Le test est très intéressant, et les résultats sont sans doute logiques (sans connaître boost). Derrière le regex j'imagine qu'il y a une sorte d'interpréteur assez pénalisant (t'as oublié un chiffre je pense dans les résultats).
Malgré tout je suis assez surpris que le code en accès direct (Camboui 1) soit un chouia plus lent que celui par foncteur (Camboui 2). Je me demande bien ce qu'il y a derrière std::char_traits<char>::find() exactement pour que ça puisse être plus rapide qu'un memchr().

EDIT, je me répond à moi-même (memchr() n'y est probablement pour rien): je pense que remove_if() du code Camboui 2 teste d'abord si le conteneur va être modifé avant de le faire si nécessaire, alors que le code Camboui 1 recopie d'office le buffer sur lui-même. Il y a sans doute beaucoup de string qui restent inchangées vu leur génération aléatoire et leur petite taille, les copies systématiques sur soi-même sont peut-être pénalisantes dans le code Camboui 1.
J'avais utilisé à l'origine remove_copy_if() au lieu de remove_if() pour forcer la copie car je pense que dans le cas général le conteneur sera modifié le plus souvent (donc optimisé pour ce cas).
A vérifier cependant avec ton code de test afin de voir la différence entre remove_if() et remove_copy_if().

Merci beaucoup pour cet éclairsissement !