¿Cómo se puede convertir una cadena a mayúsculas? Los ejemplos que he encontrado en google solo tienen que ver con caracteres.
268
Impulsar algoritmos de cadena:
#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
probablemente asume ASCII.std::string newstr(boost::to_upper_copy<std::string>("Hello World"));
fuente
toupper()
se puede implementar como una macro. Esto puede causar un problema.toupper
. ¿Algunas ideas?Solución corta usando C ++ 11 y toupper ().
fuente
c
sería delconst char
tipo (deauto
)? Si es así, no puede asignarlo (debido a unaconst
parte) a lo que devuelvetoupper(c)
.c
necesita ser lanzadounsigned char
para que esto sea corregido.Nota: Un par de problemas con la solución principal:
Lo que significa que los
cctype
miembros pueden ser macros no aptos para el consumo directo en algoritmos estándar.Otro problema con el mismo ejemplo es que no arroja el argumento ni verifica que esto no sea negativo; Esto es especialmente peligroso para los sistemas en los que
char
se firma sin formato . (La razón es: si esto se implementa como una macro, probablemente usará una tabla de búsqueda y sus argumentos indexados en esa tabla. Un índice negativo le dará UB).fuente
Este problema es vectorizable con SIMD para el conjunto de caracteres ASCII.
Comparaciones de aceleración:
Pruebas preliminares con x86-64 gcc 5.2
-O3 -march=native
en un Core2Duo (Merom). La misma cadena de 120 caracteres (ASCII minúscula y no minúscula mixta), convertida en un bucle 40M veces (sin línea cruzada entre archivos, por lo que el compilador no puede optimizar ni sacar nada del bucle). Las mismas memorias intermedias de origen y destino, por lo que no hay sobrecarga malloc o efectos de memoria / caché: los datos están calientes en la caché L1 todo el tiempo, y estamos puramente vinculados a la CPU.boost::to_upper_copy<char*, std::string>()
: 198.0s . Sí, Boost 1.58 en Ubuntu 15.10 es realmente tan lento. Realicé un perfil y escalé el asm en un depurador, y es muy, muy malo: ¡hay una transmisión dinámica de una variable local por carácter! (Dynamic_cast toma múltiples llamadas a strcmp). Esto sucede conLANG=C
y conLANG=en_CA.UTF-8
.No probé usando un RangeT que no sea std :: string. Tal vez la otra forma de
to_upper_copy
optimiza mejor, pero creo que lo hará siemprenew
/malloc
espacio para la copia, por lo que es más difícil de probar. Tal vez algo que hice difiere de un caso de uso normal, y tal vez normalmente detenido g ++ puede levantar el material de configuración regional del bucle por carácter. Mi ciclo de lectura de astd::string
y escritura en achar dstbuf[4096]
tiene sentido para las pruebas.loop call glibc
toupper
: 6.67s (sin embargo, no se verifica elint
resultado de un posible UTF-8 de varios bytes. Esto es importante para el turco).cmov
, con la tabla activa en L1 de todos modos.Consulte también esta pregunta sobre la
toupper()
lentitud en Windows cuando se establece una configuración regional .Me sorprendió que Boost sea un orden de magnitud más lento que las otras opciones. Verifiqué dos veces que había
-O3
habilitado, e incluso un solo paso para ver lo que estaba haciendo. Es casi exactamente la misma velocidad con clang ++ 3.8. Tiene una gran sobrecarga dentro del bucle por personaje. Elperf record
/report
resultado (para elcycles
evento perf) es:Autovectorización
Gcc y clang solo vectorizarán automáticamente los bucles cuando el recuento de iteraciones se conozca antes del bucle. (es decir, los bucles de búsqueda como la implementación de C simple de
strlen
no se autovectorizarán).Por lo tanto, para las cadenas lo suficientemente pequeñas como para caber en la memoria caché, obtenemos una aceleración significativa para las cadenas de ~ 128 caracteres de largo de hacer
strlen
primero. Esto no será necesario para cadenas de longitud explícita (como C ++std::string
).Cualquier libc decente tendrá una eficiencia
strlen
mucho más rápida que el bucle de un byte a la vez, por lo que los bucles strlen y toupper vectorizados por separado son más rápidos.Línea de base: un bucle que comprueba un 0 final sobre la marcha.
Tiempos para iteraciones de 40M, en un Core2 (Merom) 2.4GHz. gcc 5.2
-O3 -march=native
. (Ubuntu 15.10).dst != src
(así que hacemos una copia), pero no se superponen (y no están cerca). Ambos están alineados.Algunos resultados son un poco diferentes con el sonido metálico.
El bucle de microbenchmark que llama a la función está en un archivo separado. De lo contrario, se alinea y
strlen()
se saca del circuito, y se ejecuta dramáticamente más rápido, especialmente. para 16 cadenas de caracteres (0.187s).Esto tiene la gran ventaja de que gcc puede auto-vectorizarlo para cualquier arquitectura, pero la mayor desventaja es que es más lento para el caso generalmente común de cadenas pequeñas.
Entonces, hay grandes aceleraciones, pero la vectorización automática del compilador no es un gran código, especialmente. para la limpieza de los últimos hasta 15 caracteres.
Vectorización manual con intrínsecos SSE:
Basado en mi función de cambio de mayúsculas y minúsculas que invierte las mayúsculas y minúsculas de cada carácter alfabético. Aprovecha el "truco de comparación sin signo", donde puedes hacer
low < a && a <= high
una sola comparación sin signo mediante el desplazamiento de rango, de modo que cualquier valor menor que selow
ajusta a un valor mayor quehigh
. (Esto funciona silow
yhigh
no están demasiado separados).SSE solo tiene una comparación con signo mayor, pero aún podemos usar el truco de "comparación sin signo" al cambiar el rango al final del rango firmado: Reste 'a' + 128, por lo que los caracteres alfabéticos varían de -128 a -128 +25 (-128 + 'z' - 'a')
Tenga en cuenta que sumar 128 y restar 128 son lo mismo para los enteros de 8 bits. No hay a dónde ir el transporte, por lo que es solo xor (complemento sin transporte), volteando el bit alto.
Dada esta función que funciona para un vector, podemos llamarlo en un bucle para procesar una cadena completa. Como ya estamos apuntando a SSE2, podemos hacer una verificación de fin de cadena vectorizada al mismo tiempo.
También podemos hacerlo mucho mejor para la "limpieza" de los últimos 15 bytes restantes después de hacer los vectores de 16B: la mayúscula es idempotente, por lo que volver a procesar algunos bytes de entrada está bien. Hacemos una carga no alineada de los últimos 16B de la fuente y la almacenamos en el búfer de destino superponiendo la última tienda de 16B del bucle.
El único momento en que esto no funciona es cuando toda la cadena está por debajo de 16B: incluso cuando
dst=src
la lectura-modificación-escritura no atómica no es lo mismo que no tocar algunos bytes, y puede romper el código multiproceso.Tenemos un bucle escalar para eso, y también para
src
alinearnos. Como no sabemos dónde estará la terminación 0, una carga desalineadasrc
podría pasar a la página siguiente y volverse por defecto. Si necesitamos bytes en un bloque 16B alineado, siempre es seguro cargar todo el bloque 16B alineado.Fuente completa: en un github gist .
Tiempos para iteraciones de 40M, en un Core2 (Merom) 2.4GHz. gcc 5.2
-O3 -march=native
. (Ubuntu 15.10).dst != src
(así que hacemos una copia), pero no se superponen (y no están cerca). Ambos están alineados.(Realmente cronometrado con
_mm_store
el bucle, no_mm_storeu
, porque storeu es más lento en Merom incluso cuando la dirección está alineada. Está bien en Nehalem y más tarde. También dejé el código tal como está por ahora, en lugar de arreglar el error al copiar la terminación de 0 en algunos casos, porque no quiero volver a cronometrar todo).Entonces, para cadenas cortas de más de 16B, esto es dramáticamente más rápido que el vectorizado automático. Las longitudes uno-menos-que-un-ancho-vector no presentan un problema. Pueden ser un problema al operar en el lugar, debido a un puesto de reenvío de la tienda. (Pero tenga en cuenta que todavía está bien procesar nuestra propia salida, en lugar de la entrada original, porque toupper es idempotente).
Hay muchas posibilidades para ajustar esto para diferentes casos de uso, dependiendo de lo que quiera el código circundante y la microarquitectura objetivo. Conseguir que el compilador emita un buen código para la parte de limpieza es complicado. Usar
ffs(3)
(que se compila en bsf o tzcnt en x86) parece ser bueno, pero obviamente ese bit necesita un replanteamiento ya que noté un error después de escribir la mayor parte de esta respuesta (ver los comentarios de FIXME).Aceleraciones vectoriales para cadenas aún más pequeñas se pueden obtener con
movq
omovd
cargas / tiendas. Personalice según sea necesario para su caso de uso.UTF-8:
Podemos detectar cuándo nuestro vector tiene bytes con el conjunto de bits alto, y en ese caso recurrir a un bucle escalar utf-8-aware para ese vector. El
dst
punto puede avanzar en una cantidad diferente alsrc
puntero, pero una vez que volvamos a unsrc
puntero alineado , seguiremos haciendo almacenamientos de vectores no alineadosdst
.Para el texto que es UTF-8, pero que consiste principalmente en el subconjunto ASCII de UTF-8, esto puede ser bueno: alto rendimiento en el caso común con comportamiento correcto en todos los casos. Sin embargo, cuando hay una gran cantidad de no ASCII, probablemente sea peor que permanecer todo el tiempo en el circuito consciente escalar UTF-8.
Hacer que el inglés sea más rápido a expensas de otros idiomas no es una decisión a prueba de futuro si el inconveniente es significativo.
Locale-aware:
En el entorno local turco (
tr_TR
), el resultado correctotoupper('i')
es'İ'
(U0130), no'I'
(ASCII simple). Vea los comentarios de Martin Bonner sobre una pregunta acerca detolower()
ser lento en Windows.También podemos verificar si hay una lista de excepciones y una reserva para escalar allí, como para los caracteres de entrada UTF8 de varios bytes.
Con tanta complejidad, SSE4.2
PCMPISTRM
o algo así podría hacer muchas de nuestras comprobaciones de una sola vez.fuente
¿Tiene caracteres ASCII o internacionales en cadenas?
Si es el último caso, "mayúsculas" no es tan simple, y depende del alfabeto utilizado. Hay alfabetos bicamerales y unicamerales. Solo los alfabetos bicamerales tienen caracteres diferentes para mayúsculas y minúsculas. Además, hay caracteres compuestos, como la letra mayúscula latina 'DZ' (\ u01F1 'DZ') que utilizan el llamado caso de título . Esto significa que solo se cambia el primer carácter (D).
Le sugiero que busque en la UCI y la diferencia entre las asignaciones de casos simples y completas. Esto podría ayudar:
http://userguide.icu-project.org/transforms/casemappings
fuente
O,
fuente
**
después de los parámetros en la primera solución?**
es un error tipográfico al intentar usar una fuente en negrita en la sintaxis del código.toupper
se llama con números negativos.Lo siguiente funciona para mí.
fuente
toupper
se llama con números negativos.Usa una lambda.
fuente
El más rápido si usa solo caracteres ASCII :
Tenga en cuenta que este código se ejecuta más rápido pero solo funciona en ASCII y no es una solución "abstracta".
Si necesita soluciones UNICODE o soluciones más convencionales y abstractas, busque otras respuestas y trabaje con métodos de cadenas C ++.
fuente
C++
, pero escribió unaC
respuesta aquí. (No soy uno de los'
?Siempre que esté bien con ASCII solo y pueda proporcionar un puntero válido a la memoria RW, hay una línea simple y muy efectiva en C:
Esto es especialmente bueno para cadenas simples como identificadores ASCII que desea normalizar en el mismo caso de caracteres. Luego puede usar el búfer para construir una instancia de std: string.
fuente
fuente
for (size_t i = 0 ...
. Tampoco hay una buena razón para que sea tan difícil de leer. Esto también copia la cadena primero y luego repite sobre ella. La respuesta de @ Luke es mejor en algunos aspectos, excepto por no aprovechar las'a'
constantes de los personajes.Esto funcionará mejor que todas las respuestas que usan la función global toupper, y es presumiblemente lo que boost :: to_upper está haciendo debajo.
Esto se debe a que :: toupper tiene que buscar el entorno local, porque podría haber sido cambiado por un hilo diferente, para cada invocación, mientras que aquí solo la llamada a locale () tiene esta penalización. Y buscar la configuración regional generalmente implica tomar un candado.
Esto también funciona con C ++ 98 después de reemplazar el auto, usar los nuevos str.data () no constantes y agregar un espacio para romper el cierre de la plantilla (">>" a ">>") así:
fuente
fuente
reserve
yback_inserter
(haciendo que la cadena solo se copie una vez).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; }
fuente
toupper
se llama con números negativos.pruebe la
toupper()
función (#include <ctype.h>
). acepta caracteres como argumentos, las cadenas están formadas por caracteres, por lo que tendrá que iterar sobre cada carácter individual que, cuando se junta, comprende la cadenafuente
toupper
se llama con números negativos. Deberías haber mencionado el elenco necesario paraunsigned char
.Aquí está el último código con C ++ 11
fuente
toupper
se llama con números negativos.Usando Boost.Text, que funcionará para texto Unicode
fuente
La respuesta de @dirkgently es muy inspiradora, pero quiero enfatizar eso debido a la preocupación que se muestra a continuación,
El uso correcto de
std::toupper
debe ser:Salida:
fuente
No estoy seguro de que haya una función incorporada. Prueba esto:
Incluya las bibliotecas ctype.h o cctype, así como stdlib.h como parte de las directivas de preprocesador.
fuente
toupper
se llama con números negativos.Mi solución (borrar 6 bits para alfa):
fuente
toupper
se llama con números negativos.TODAS estas soluciones en esta página son más difíciles de lo necesario.
Hacer esto
RegName
es tustring
. Obtenga el tamaño de su cadena no usestring.size()
como su probador real, muy desordenado y puede causar problemas. luego. Elfor
bucle más básico .recuerde que el tamaño de cadena también devuelve el delimitador, así que use <y no <= en su prueba de bucle.
la salida será: alguna cadena que quieras convertir
fuente
tolower
bucles simples , y la mayoría de ellos usan nombres de variables de bucle estándar comoi
, no los extrañosforLoop
.Sin usar ninguna biblioteca:
fuente
Si solo le interesan los caracteres de 8 bits (que todas las otras respuestas, excepto Milan Babuškov también asumen), puede obtener la velocidad más rápida generando una tabla de búsqueda en tiempo de compilación utilizando metaprogramación. En ideone.com, esto funciona 7 veces más rápido que la función de biblioteca y 3 veces más rápido que una versión escrita a mano ( http://ideone.com/sb1Rup ). También es personalizable a través de rasgos sin ralentización.
con caso de uso:
Para una descripción en profundidad (muchas páginas) de cómo funciona, permítame conectar descaradamente mi blog: http://metaporky.blogspot.de/2014/07/part-4-generating-look-up-tables-at.html
fuente
fuente
Esta función de c ++ siempre devuelve la cadena de mayúsculas ...
fuente
Yo uso esta solución Sé que se supone que no debes modificar esa área de datos ... pero creo que eso es principalmente por errores de desbordamiento de búfer y caracteres nulos ... las cosas de mayúsculas no son lo mismo.
fuente
I know you're not supposed to modify that data area
- ¿Qué área de datos no debes modificar?str[i] = toupper(str[i]);
perfectamente bien (bueno, no perfectamente bien, pero corrige la mayoría de las cosas mal).