Comment pourrait-on convertir une chaîne en majuscules. Les exemples que j'ai trouvés sur Google ne concernent que les caractères.
268
Boost algorithmes de chaîne:
#include <boost/algorithm/string.hpp>
#include <string>
std::string str = "Hello World";
boost::to_upper(str);
std::string newstr = boost::to_upper_copy<std::string>("Hello World");
::toupper
on suppose très probablement ASCII.std::string newstr(boost::to_upper_copy<std::string>("Hello World"));
la source
toupper()
peut être implémenté comme une macro. Cela peut provoquer un problème.toupper
. Des idées?Solution courte utilisant C ++ 11 et toupper ().
la source
c
deconst char
type (deauto
)? Si c'est le cas, vous ne pouvez pas l'affecter (en raison d'uneconst
partie) à ce qui est retourné partoupper(c)
.c
doit être casté pourunsigned char
que cela soit corrigé.Remarque: quelques problèmes avec la meilleure solution:
Ce qui signifie que les
cctype
membres peuvent bien être des macros non adaptées à la consommation directe dans les algorithmes standards.Un autre problème avec le même exemple est qu'il ne jette pas l'argument ni ne vérifie que ce n'est pas négatif; ceci est particulièrement dangereux pour les systèmes où plain
char
est signé. (La raison en est: si elle est implémentée en tant que macro, elle utilisera probablement une table de recherche et vos arguments dans cette table. Un index négatif vous donnera UB.)la source
Ce problème est vectorisable avec SIMD pour le jeu de caractères ASCII.
Comparaisons d'accélération:
Tests préliminaires avec x86-64 gcc 5.2
-O3 -march=native
sur un Core2Duo (Merom). La même chaîne de 120 caractères (ASCII mixte en minuscules et non en minuscules), convertie en boucle 40 millions de fois (sans insertion de fichier croisé, de sorte que le compilateur ne peut pas l'optimiser ou le retirer de la boucle). Mêmes tampons source et dest, donc pas de surcharge malloc ou d'effets mémoire / cache: les données sont chaudes dans le cache L1 tout le temps, et nous sommes purement liés au CPU.boost::to_upper_copy<char*, std::string>()
: 198,0 s . Oui, Boost 1.58 sur Ubuntu 15.10 est vraiment aussi lent. J'ai profilé et fait une seule étape dans un débogueur, et c'est vraiment, vraiment mauvais: il y a un dynamic_cast d'une variable locale qui se produit par caractère !!! (dynamic_cast prend plusieurs appels à strcmp). Cela se produit avecLANG=C
et avecLANG=en_CA.UTF-8
.Je n'ai pas testé en utilisant un RangeT autre que std :: string. Peut-être que l'autre forme d'
to_upper_copy
optimise mieux, mais je pense que ce sera toujoursnew
/malloc
espace pour la copie, donc c'est plus difficile à tester. Peut-être que quelque chose que j'ai fait diffère d'un cas d'utilisation normal, et peut-être que g ++ est normalement arrêté peut hisser la configuration locale hors de la boucle par caractère. Ma lecture en boucle d'unstd::string
et l'écriture vers unchar dstbuf[4096]
est logique pour les tests.boucle appelant la glibc
toupper
: 6,67 s (ne vérifie pas leint
résultat pour un potentiel UTF-8 multi-octets, cependant. Cela est important pour le turc.)cmov
, avec la table chaude en L1 de toute façon.Voir aussi cette question sur la
toupper()
lenteur sous Windows lorsqu'un paramètre régional est défini .J'ai été choqué que Boost soit un ordre de grandeur plus lent que les autres options. J'ai revérifié que j'avais
-O3
activé, et j'ai même fait un pas pour voir ce qu'il faisait. C'est presque exactement la même vitesse avec clang ++ 3.8. Il a une énorme surcharge à l'intérieur de la boucle par caractère. Le résultatperf record
/report
(pour l'cycles
événement perf) est:Autovectorisation
Gcc et clang ne vectoriseront automatiquement les boucles que lorsque le nombre d'itérations est connu avant la boucle. (c'est-à-dire que les boucles de recherche comme l'implémentation plain-C de
strlen
ne seront pas autovectorisées.)Ainsi, pour les chaînes suffisamment petites pour tenir dans le cache, nous obtenons une accélération significative pour les chaînes ~ 128 caractères longtemps avant de
strlen
commencer. Cela ne sera pas nécessaire pour les chaînes de longueur explicite (comme C ++std::string
).Toute libc décente aura une efficacité
strlen
beaucoup plus rapide que de boucler un octet à la fois, donc les boucles strlen et toupper vectorisées séparées sont plus rapides.Ligne de base: une boucle qui vérifie un 0 se terminant à la volée.
Temps pour les itérations 40M, sur un Core2 (Merom) 2,4 GHz. gcc 5.2
-O3 -march=native
. (Ubuntu 15.10).dst != src
(nous faisons donc une copie), mais ils ne se chevauchent pas (et ne sont pas à proximité). Les deux sont alignés.Certains résultats sont un peu différents avec clang.
La boucle de microbenchmark qui appelle la fonction se trouve dans un fichier séparé. Sinon, il s'aligne et
strlen()
se hisse hors de la boucle, et il fonctionne considérablement plus vite, esp. pour 16 chaînes de caractères (0,187 s).Cela a le principal avantage que gcc peut le vectoriser automatiquement pour n'importe quelle architecture, mais l'inconvénient majeur qu'il est plus lent pour le cas généralement courant des petites chaînes.
Il y a donc de grandes accélérations, mais la vectorisation automatique du compilateur ne fait pas un excellent code, en particulier. pour le nettoyage des 15 derniers caractères maximum.
Vectorisation manuelle avec intrinsèque SSE:
Basé sur ma fonction de retournement de casse qui inverse la casse de chaque caractère alphabétique. Il tire parti de "l'astuce de comparaison non signée", où vous pouvez faire
low < a && a <= high
une seule comparaison non signée par décalage de plage, de sorte que toute valeur inférieure à selow
termine par une valeur supérieure àhigh
. (Cela fonctionne silow
ethigh
ne sont pas trop éloignés.)SSE a uniquement une comparaison signée supérieure, mais nous pouvons toujours utiliser l'astuce "comparaison non signée" en décalant la plage vers le bas de la plage signée: soustrayez 'a' + 128, de sorte que les caractères alphabétiques varient de -128 à -128 +25 (-128 + 'z' - 'a')
Notez que l'ajout de 128 et la soustraction de 128 sont la même chose pour les entiers 8 bits. Il n'y a nulle part où aller pour le porter, donc c'est juste xor (add sans porter), renversant le bit haut.
Étant donné cette fonction qui fonctionne pour un vecteur, nous pouvons l'appeler en boucle pour traiter une chaîne entière. Puisque nous ciblons déjà SSE2, nous pouvons effectuer une vérification de fin de chaîne vectorisée en même temps.
Nous pouvons également faire beaucoup mieux pour le "nettoyage" des derniers jusqu'à-15 octets restants après avoir fait des vecteurs de 16B: le boîtier supérieur est idempotent, donc le retraitement de certains octets d'entrée est très bien. Nous effectuons un chargement non aligné du dernier 16B de la source et le stockons dans le tampon dest chevauchant le dernier magasin 16B de la boucle.
La seule fois où cela ne fonctionne pas, c'est lorsque la chaîne entière est inférieure à 16B: Même lorsque
dst=src
, la lecture-modification-écriture non atomique n'est pas la même chose que de ne pas toucher du tout certains octets, et peut casser le code multithread.Nous avons une boucle scalaire pour cela, et aussi pour nous
src
aligner. Puisque nous ne savons pas où se terminera le 0, une charge non alignéesrc
pourrait traverser la page suivante et segfault. Si nous avons besoin d'octets dans un bloc 16B aligné, il est toujours sûr de charger l'ensemble du bloc 16B aligné.Source complète: dans un github gist .
Temps pour les itérations 40M, sur un Core2 (Merom) 2,4 GHz. gcc 5.2
-O3 -march=native
. (Ubuntu 15.10).dst != src
(nous faisons donc une copie), mais ils ne se chevauchent pas (et ne sont pas à proximité). Les deux sont alignés.(En fait chronométré avec
_mm_store
dans la boucle, non_mm_storeu
, car storeu est plus lent sur Merom même lorsque l'adresse est alignée. C'est bien sur Nehalem et plus tard. J'ai également laissé le code tel quel pour le moment, au lieu de corriger l'échec de la copie le 0 final dans certains cas, parce que je ne veux pas tout re-chronométrer.)Ainsi, pour les chaînes courtes supérieures à 16B, cela est considérablement plus rapide que la vectorisation automatique. Les longueurs d'une largeur inférieure à un vecteur ne posent pas de problème. Ils peuvent être un problème lors du fonctionnement sur place, en raison d'un blocage de transfert de magasin. (Mais notez qu'il est toujours correct de traiter notre propre sortie, plutôt que l'entrée d'origine, car toupper est idempotent).
Il y a beaucoup de possibilités pour régler cela pour différents cas d'utilisation, selon ce que le code environnant veut et la microarchitecture cible. Il est difficile d'obtenir le compilateur pour émettre du code agréable pour la partie de nettoyage. Utiliser
ffs(3)
(qui se compile en bsf ou tzcnt sur x86) semble être bon, mais évidemment ce bit a besoin d'être repensé puisque j'ai remarqué un bogue après avoir écrit la plupart de cette réponse (voir les commentaires FIXME).Des accélérations vectorielles pour des chaînes encore plus petites peuvent être obtenues avec
movq
ou desmovd
charges / stockages. Personnalisez au besoin pour votre cas d'utilisation.UTF-8:
Nous pouvons détecter quand notre vecteur a des octets avec le bit le plus élevé et, dans ce cas, revenir à une boucle scalaire prenant en charge utf-8 pour ce vecteur. Le
dst
point peut avancer d'une quantité différente de celle dusrc
pointeur, mais une fois que nous revenons à unsrc
pointeur aligné , nous ne faisons que stocker des vecteurs non alignésdst
.Pour le texte qui est UTF-8, mais qui se compose principalement du sous-ensemble ASCII d'UTF-8, cela peut être bon: hautes performances dans le cas commun avec un comportement correct dans tous les cas. Quand il y a beaucoup de non-ASCII, ce sera probablement pire que de rester dans la boucle consciente scalaire UTF-8, cependant.
Rendre l'anglais plus rapide au détriment des autres langues n'est pas une décision d'avenir si l'inconvénient est significatif.
Sensible aux paramètres régionaux:
Dans les paramètres régionaux turcs (
tr_TR
), le résultat correcttoupper('i')
est'İ'
(U0130) et non'I'
(ASCII ordinaire). Voir les commentaires de Martin Bonner sur une question concernant latolower()
lenteur sous Windows.Nous pouvons également rechercher une liste d'exceptions et un retour à scalaire, comme pour les caractères d'entrée UTF8 multi-octets.
Avec une telle complexité, SSE4.2
PCMPISTRM
ou quelque chose pourrait être capable de faire beaucoup de nos vérifications en une seule fois.la source
Avez-vous des caractères ASCII ou internationaux dans les chaînes?
Si c'est le dernier cas, "majuscule" n'est pas aussi simple que cela, et cela dépend de l'alphabet utilisé. Il existe des alphabets bicaméraux et unicaméraux. Seuls les alphabets bicaméraux ont des caractères différents pour les majuscules et les minuscules. En outre, il existe des caractères composites, comme la lettre majuscule latine 'DZ' (\ u01F1 'DZ') qui utilisent ce qu'on appelle la casse du titre . Cela signifie que seul le premier caractère (D) est modifié.
Je vous suggère de vous pencher sur l' ICU et de faire la différence entre les mappages de cas simples et complets. Cela pourrait aider:
http://userguide.icu-project.org/transforms/casemappings
la source
Ou,
la source
**
après les paramètres de la première solution?**
c'est une faute de frappe d'essayer d'utiliser une police en gras dans la syntaxe du code.toupper
est appelé avec des nombres négatifs.Ce qui suit fonctionne pour moi.
la source
toupper
est appelé avec des nombres négatifs.Utilisez un lambda.
la source
Le plus rapide si vous n'utilisez que des caractères ASCII :
Veuillez noter que ce code s'exécute plus rapidement mais ne fonctionne que sur ASCII et n'est pas une solution "abstraite".
Si vous avez besoin de solutions UNICODE ou de solutions plus conventionnelles et abstraites, optez pour d'autres réponses et travaillez avec des méthodes de chaînes C ++.
la source
C++
, mais vous avez écrit uneC
réponse ici. (Je ne suis pas un des downvoters.)'
?Tant que vous êtes bien avec ASCII uniquement et que vous pouvez fournir un pointeur valide vers la mémoire RW, il existe une ligne simple et très efficace en C:
C'est particulièrement bon pour les chaînes simples comme les identifiants ASCII que vous souhaitez normaliser dans la même casse de caractères. Vous pouvez ensuite utiliser le tampon pour construire une instance std: string.
la source
la source
for (size_t i = 0 ...
. Il n'y a également aucune bonne raison de le rendre si difficile à lire. Cela copie également la chaîne en premier puis la boucle. @ La réponse de Luke est meilleure à certains égards, sauf pour ne pas profiter des'a'
constantes de caractère.Cela fonctionnera mieux que toutes les réponses qui utilisent la fonction globale toupper, et c'est probablement ce que boost :: to_upper fait en dessous.
C'est parce que :: toupper doit rechercher les paramètres régionaux - car ils peuvent avoir été modifiés par un thread différent - pour chaque appel, alors qu'ici seul l'appel à locale () a cette pénalité. Et rechercher les paramètres régionaux implique généralement de prendre un verrou.
Cela fonctionne également avec C ++ 98 après avoir remplacé l'auto, l'utilisation de la nouvelle str.data () non const et ajouté un espace pour interrompre la fermeture du modèle (">>" à ">>") comme ceci:
la source
la source
reserve
etback_inserter
(pour que la chaîne ne soit copiée qu'une seule fois).inline std::string to_lower(const std::string &s) { std::string result; result.reserve(s.size()); std::transform(s.begin(), s.end(), std::back_inserter( result ), static_cast<int(*)(int)>(std::tolower)); return result; }
la source
toupper
est appelé avec des nombres négatifs.essayez la
toupper()
fonction (#include <ctype.h>
). il accepte les caractères comme arguments, les chaînes sont composées de caractères, vous devrez donc parcourir chaque caractère individuel qui, une fois mis en place, comprend la chaînela source
toupper
est appelée avec des nombres négatifs. Vous auriez dû mentionner le casting nécessaire pourunsigned char
.Voici le dernier code avec C ++ 11
la source
toupper
est appelé avec des nombres négatifs.Utilisation de Boost.Text, qui fonctionnera pour le texte Unicode
la source
La réponse de @dirkgently est très inspirante, mais je tiens à souligner qu'en raison de l'inquiétude indiquée ci-dessous,
l'utilisation correcte de
std::toupper
devrait être:Production:
la source
pas sûr qu'il y ait une fonction intégrée. Essaye ça:
Incluez les bibliothèques ctype.h OU cctype, ainsi que stdlib.h dans le cadre des directives du préprocesseur.
la source
toupper
est appelé avec des nombres négatifs.Ma solution (effacer le 6e bit pour alpha):
la source
toupper
est appelé avec des nombres négatifs.TOUTES ces solutions sur cette page sont plus difficiles qu'elles ne devraient l'être.
Faites ceci
RegName
est votrestring
. Obtenez votre taille de chaîne ne pas utiliserstring.size()
comme testeur réel, très désordonné et peut causer des problèmes. puis. lafor
boucle la plus basique .rappelez-vous que la taille de la chaîne renvoie également le délimiteur, utilisez donc <et non <= dans votre test de boucle.
la sortie sera: une chaîne que vous souhaitez convertir
la source
tolower
boucles simples , et la plupart d'entre elles utilisent des noms de variables de boucle standard commei
, pas les étrangesforLoop
.Sans utiliser de bibliothèques:
la source
Si vous ne vous préoccupez que des caractères 8 bits (ce que toutes les autres réponses sauf Milan Babuškov supposent également), vous pouvez obtenir la vitesse la plus rapide en générant une table de recherche au moment de la compilation à l'aide de la métaprogrammation. Sur ideone.com, cela fonctionne 7 fois plus vite que la fonction de bibliothèque et 3 fois plus vite qu'une version manuscrite ( http://ideone.com/sb1Rup ). Il est également personnalisable grâce à des traits sans ralentissement.
avec cas d'utilisation:
Pour une description en profondeur (plusieurs pages) de son fonctionnement, permettez-moi de brancher sans vergogne mon blog: http://metaporky.blogspot.de/2014/07/part-4-generating-look-up-tables-at.html
la source
la source
Cette fonction c ++ renvoie toujours la chaîne majuscule ...
la source
J'utilise cette solution. Je sais que vous n'êtes pas censé modifier cette zone de données .... mais je pense que c'est principalement pour les bogues de dépassement de tampon et le caractère nul .... les choses majuscules ne sont pas les mêmes.
la source
I know you're not supposed to modify that data area
- quelle zone de données n'êtes-vous pas censé modifier?str[i] = toupper(str[i]);
parfaitement fine (enfin, pas parfaitement fine, mais elle corrige la plupart des problèmes).