Bagaimana seseorang bisa mengkonversi string ke huruf besar. Contoh yang saya telah ditemukan dari googling hanya harus berurusan dengan karakter.
struct convert {
void operator()(char& c) { c = toupper((unsigned char)c); }
};
// ...
string uc_str;
for_each(uc_str.begin(), uc_str.end(), convert());
Catatan: beberapa masalah dengan beberapa solusi:
21.5 Null-terminated urutan utilitas
isi dari header ini akan sama seperti Standar C Library header <ctype.h>, <wctype.h>, <string.h>, <wchar.h>, dan <stdlib.h> [...]
Yang berarti bahwa cctype
anggota mungkin akan macro tidak cocok untuk konsumsi langsung dalam algoritma standar.
Masalah lain dengan contoh yang sama adalah bahwa hal itu tidak melemparkan argumen atau memverifikasi bahwa ini adalah non-negatif; hal ini terutama berbahaya bagi sistem di mana polos char
ditandatangani. (Alasannya: jika hal ini dilaksanakan sebagai makro mungkin akan menggunakan lookup table dan argumen anda indeks ke meja itu. Indeks negatif akan memberikan anda UB.)
Pengujian awal dengan x86-64 gcc 5.2 -O3 -maret=asli
pada Core2Duo (Merom). String yang sama dari 120 karakter (campuran huruf kecil dan non-ASCII huruf kecil), yang dikonversi dalam satu lingkaran 40M kali (dengan tidak ada cross-file inlining, sehingga penyusun dapat't mengoptimalkan diri atau hoist semua itu keluar dari loop). Sumber yang sama dan dest buffer, sehingga tidak ada malloc overhead atau memori/cache efek: data panas di L1 cache sepanjang waktu, dan kami're murni CPU-bound.
boost::to_upper_copy<char*, std::string>()
: 198.0 s. Ya, Meningkatkan 1.58 pada Ubuntu 15.10 adalah benar-benar lambat. Saya diprofilkan dan satu-melangkah asm di debugger, dan's benar-benar, benar-benar ** buruk: ada's dynamic_cast dari lokal variabel terjadi per karakter!!! (dynamic_cast mengambil beberapa panggilan untuk strcmp). Hal ini terjadi dengan LANG=C
dan dengan LANG=en_CA.UTF-8
.
Aku't test menggunakan RangeT lain dari std::string. Mungkin bentuk lain dari to_upper_copy
mengoptimalkan baik, tapi saya pikir itu akan selalu baru
/malloc
ruang untuk copy, jadi itu's sulit untuk menguji. Mungkin sesuatu yang saya lakukan berbeda dari yang normal-kasus penggunaan, dan mungkin biasanya berhenti g++ dapat mengerek lokal penataan barang keluar per-karakter loop. Loop saya membaca dari sebuah std::string
dan menulis untuk char dstbuf[4096]
masuk akal untuk pengujian. toupper
: 6.67 s (tidak memeriksa int
hasil untuk potensi multi-byte UTF-8, meskipun. Hal ini penting untuk turki.) cmov
, dengan meja panas di L1 pula. toupper()
menjadi lambat pada Windows ketika locale set. Saya terkejut bahwa Boost adalah urutan besarnya lebih lambat daripada pilihan lainnya. Aku mengecek bahwa saya telah -O3
diaktifkan, dan bahkan satu-melangkah asm untuk melihat apa yang dilakukannya. It's hampir kecepatan yang sama dengan dentang++ 3.8. Memiliki overhead besar dalam per-karakter loop. Masa se record
/ laporan
hasil (untuk siklus
perf event) adalah:
32.87% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNK10__cxxabiv121__vmi_class_type_info12__do_dyncastElNS_17__class_type_info10__sub_kindEPKS1_PKvS4_S6_RNS1_16
21.90% flipcase-clang- libstdc++.so.6.0.21 [.] __dynamic_cast
16.06% flipcase-clang- libc-2.21.so [.] __GI___strcmp_ssse3
8.16% flipcase-clang- libstdc++.so.6.0.21 [.] _ZSt9use_facetISt5ctypeIcEERKT_RKSt6locale
7.84% flipcase-clang- flipcase-clang-boost [.] _Z16strtoupper_boostPcRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
2.20% flipcase-clang- libstdc++.so.6.0.21 [.] strcmp@plt
2.15% flipcase-clang- libstdc++.so.6.0.21 [.] __dynamic_cast@plt
2.14% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNKSt6locale2id5_M_idEv
2.11% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNKSt6locale2id5_M_idEv@plt
2.08% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNKSt5ctypeIcE10do_toupperEc
2.03% flipcase-clang- flipcase-clang-boost [.] _ZSt9use_facetISt5ctypeIcEERKT_RKSt6locale@plt
0.08% ...
Gcc dan dentang hanya akan auto-vectorize loop ketika jumlah iterasi lebih dikenal di depan lingkaran. (yaitu pencarian loop seperti polos-C pelaksanaan strlen
tidak't autovectorize.)
Dengan demikian, untuk string yang cukup kecil untuk muat di cache, kita mendapatkan yang signifikan speedup untuk string ~128 karakter lama dari melakukan strlen
pertama. Ini won't perlu secara eksplisit panjang string (seperti C++ std::string
).
// char, not int, is essential: otherwise gcc unpacks to vectors of int! Huge slowdown.
char ascii_toupper_char(char c) {
return ('a' <= c && c <= 'z') ? c^0x20 : c; // ^ autovectorizes to PXOR: runs on more ports than paddb
}
// gcc can only auto-vectorize loops when the number of iterations is known before the first iteration. strlen gives us that
size_t strtoupper_autovec(char *dst, const char *src) {
size_t len = strlen(src);
for (size_t i=0 ; i<len ; ++i) {
dst[i] = ascii_toupper_char(src[i]); // gcc does the vector range check with psubusb / pcmpeqb instead of pcmpgtb
}
return len;
}
Apapun yang layak libc akan memiliki efisien strlen
yang's jauh lebih cepat dari perulangan byte pada satu waktu, sehingga terpisah vectorized strlen dan toupper loop lebih cepat.
Baseline: loop yang memeriksa untuk mengakhiri 0 on the fly.
Kali 40M iterasi, pada Core2 (Merom) 2.4 GHz. gcc 5.2 -O3 -maret=asli
. (Ubuntu 15.10). dst != src
(jadi kita membuat salinan), tetapi mereka don't tumpang tindih (dan tidak't terdekat). Keduanya sejajar.
strlen()
akan mengangkat keluar dari loop, dan itu berjalan secara dramatis lebih cepat, esp. untuk 16 char string (0.187 s).
Ini memiliki keuntungan besar yang gcc bisa auto-vectorize untuk setiap arsitektur, tetapi kelemahan utama yang's lebih lambat untuk biasanya-kasus umum dari string kecil. Jadi ada big pemercepat, tapi compiler auto-vektorisasi doesn't membuat kode besar, esp. untuk pembersihan terakhir yang up-to-15 karakter.
Berdasarkan pada saya kasus-fungsi flip yang membalikkan kasus dari setiap karakter abjad. Ia mengambil keuntungan dari "unsigned membandingkan trik", di mana anda dapat melakukan rendah < a && a <= tinggi
dengan satu unsigned perbandingan dengan rentang pergeseran, sehingga setiap nilai kurang dari rendah
membungkus nilai-nilai yang's lebih besar dari tinggi
. (Ini bekerja jika rendah
dan tinggi
tidak't terlalu jauh.)
SSE hanya telah ditandatangani membandingkan-besar, tapi kita masih bisa gunakan "unsigned
bandingkan" trik oleh berbagai pergeseran ke bawah menandatangani range: Mengurangi 'a'+128, sehingga karakter abjad berkisar dari -128 untuk -128+25 (-128+'z'-'a')
Perhatikan bahwa menambahkan 128 dan mengurangkan 128 adalah hal yang sama untuk 8bit bilangan bulat. Ada's tempat untuk membawa pergi, jadi itu's hanya xor (carryless add), membalik bit yang tinggi.
#include <immintrin.h>
__m128i upcase_si128(__m128i src) {
// The above 2 paragraphs were comments here
__m128i rangeshift = _mm_sub_epi8(src, _mm_set1_epi8('a'+128));
__m128i nomodify = _mm_cmpgt_epi8(rangeshift, _mm_set1_epi8(-128 + 25)); // 0:lower case -1:anything else (upper case or non-alphabetic). 25 = 'z' - 'a'
__m128i flip = _mm_andnot_si128(nomodify, _mm_set1_epi8(0x20)); // 0x20:lcase 0:non-lcase
// just mask the XOR-mask so elements are XORed with 0 instead of 0x20
return _mm_xor_si128(src, flip);
// it's easier to xor with 0x20 or 0 than to AND with ~0x20 or 0xFF
}
Diberikan fungsi ini yang bekerja untuk salah satu vektor, kita bisa menyebutnya dalam loop untuk memproses seluruh string. Karena kita're sudah menargetkan SSE2, kita bisa melakukan vectorized end-of-string check pada waktu yang sama.
Kita juga dapat melakukan jauh lebih baik untuk "pembersihan" yang terakhir up-to-15 byte yang tersisa setelah melakukan vektor 16B: atas-casing idempotent, jadi re-processing beberapa byte masukan baik-baik saja. Yang kita lakukan tidak selaras beban lalu 16B sumber, dan menyimpannya ke dalam dest penyangga tumpang tindih terakhir 16B toko dari loop.
Satu-satunya saat ini doesn't bekerja adalah ketika seluruh string di bawah 16B: Bahkan ketika dst=src
, non-atom read-modify-write adalah tidak hal yang sama tidak menyentuh beberapa byte pada semua, dan dapat mematahkan multithreaded kode.
Kami memiliki sebuah skalar loop untuk itu, dan juga untuk mendapatkan src
selaras. Karena kita don't tahu di mana mengakhiri 0 akan, tidak selaras beban dari src
mungkin menyeberang ke halaman berikutnya dan segfault. Jika kita perlu setiap byte dalam sebuah sejajar 16B chunk, it's selalu aman untuk memuat seluruh selaras 16B chunk.
Sumber lengkap: di gist github.
// FIXME: doesn't always copy the terminating 0.
// microbenchmarks are for this version of the code (with _mm_store in the loop, instead of storeu, for Merom).
size_t strtoupper_sse2(char *dst, const char *src_begin) {
const char *src = src_begin;
// scalar until the src pointer is aligned
while ( (0xf & (uintptr_t)src) && *src ) {
*(dst++) = ascii_toupper(*(src++));
}
if (!*src)
return src - src_begin;
// current position (p) is now 16B-aligned, and we're not at the end
int zero_positions;
do {
__m128i sv = _mm_load_si128( (const __m128i*)src );
// TODO: SSE4.2 PCMPISTRI or PCMPISTRM version to combine the lower-case and '\0' detection?
__m128i nullcheck = _mm_cmpeq_epi8(_mm_setzero_si128(), sv);
zero_positions = _mm_movemask_epi8(nullcheck);
// TODO: unroll so the null-byte check takes less overhead
if (zero_positions)
break;
__m128i upcased = upcase_si128(sv); // doing this before the loop break lets gcc realize that the constants are still in registers for the unaligned cleanup version. But it leads to more wasted insns in the early-out case
_mm_storeu_si128((__m128i*)dst, upcased);
//_mm_store_si128((__m128i*)dst, upcased); // for testing on CPUs where storeu is slow
src += 16;
dst += 16;
} while(1);
// handle the last few bytes. Options: scalar loop, masked store, or unaligned 16B.
// rewriting some bytes beyond the end of the string would be easy,
// but doing a non-atomic read-modify-write outside of the string is not safe.
// Upcasing is idempotent, so unaligned potentially-overlapping is a good option.
unsigned int cleanup_bytes = ffs(zero_positions) - 1; // excluding the trailing null
const char* last_byte = src + cleanup_bytes; // points at the terminating '\0'
// FIXME: copy the terminating 0 when we end at an aligned vector boundary
// optionally special-case cleanup_bytes == 15: final aligned vector can be used.
if (cleanup_bytes > 0) {
if (last_byte - src_begin >= 16) {
// if src==dest, this load overlaps with the last store: store-forwarding stall. Hopefully OOO execution hides it
__m128i sv = _mm_loadu_si128( (const __m128i*)(last_byte-15) ); // includes the \0
_mm_storeu_si128((__m128i*)(dst + cleanup_bytes - 15), upcase_si128(sv));
} else {
// whole string less than 16B
// if this is common, try 64b or even 32b cleanup with movq / movd and upcase_si128
#if 1
for (unsigned int i = 0 ; i <= cleanup_bytes ; ++i) {
dst[i] = ascii_toupper(src[i]);
}
#else
// gcc stupidly auto-vectorizes this, resulting in huge code bloat, but no measurable slowdown because it never runs
for (int i = cleanup_bytes - 1 ; i >= 0 ; --i) {
dst[i] = ascii_toupper(src[i]);
}
#endif
}
}
return last_byte - src_begin;
}
Kali 40M iterasi, pada Core2 (Merom) 2.4 GHz. gcc 5.2 -O3 -maret=asli
. (Ubuntu 15.10). dst != src
(jadi kita membuat salinan), tetapi mereka don't tumpang tindih (dan tidak't terdekat). Keduanya sejajar.
_mm_store
dalam lingkaran, tidak _mm_storeu
, karena storeu lebih lambat pada Merom bahkan ketika alamat sejajar. It's baik pada Nehalem dan kemudian. I've juga meninggalkan kode-untuk sekarang, bukannya memperbaiki kegagalan untuk menyalin mengakhiri 0 dalam beberapa kasus, karena aku don't ingin kembali saat semuanya.)
Jadi untuk string pendek lagi dari 16B, hal ini secara dramatis lebih cepat dari auto-vectorized. Panjang satu-kurang-dari-a-vektor-lebar don't ada masalah. Mereka mungkin menjadi masalah ketika beroperasi di tempat, karena toko-forwarding kios. (Tetapi perhatikan bahwa's masih baik-baik saja untuk proses kita sendiri output, daripada input asli, karena toupper adalah idempotent).
Ada's banyak ruang untuk tuning ini untuk penggunaan yang berbeda-beda, tergantung pada apa kode sekitarnya inginkan, dan target mikroarsitektur. Mendapatkan compiler untuk memancarkan kode yang bagus untuk pembersihan bagian yang rumit. Menggunakan sl(3)
(yang mengkompilasi bsf atau tzcnt pada x86) tampaknya menjadi baik, tapi jelas bahwa sedikit perlu berpikir ulang karena saya melihat bug setelah menulis sebagian dari jawaban ini (lihat FIXME komentar).
Vektor pemercepat bahkan lebih kecil string dapat diperoleh dengan movq
atau movd
beban/toko. Menyesuaikan seperti yang diperlukan untuk kasus penggunaan anda. dst
titik dapat maju dengan jumlah yang berbeda dari src
pointer, tapi setelah kami kembali ke penginapan selaras src
pointer, kita'll masih saja melakukan unaligned toko vektor untuk dst
.
Untuk teks yang's UTF-8, tetapi sebagian besar terdiri dari ASCII subset dari UTF-8, hal ini dapat baik: kinerja tinggi dalam kasus umum dengan perilaku yang benar dalam semua kasus. Ketika ada's banyak non-ASCII, mungkin akan lebih buruk daripada tinggal di skalar UTF-8 menyadari loop sepanjang waktu, meskipun.
Membuat inggris lebih cepat dengan mengorbankan dari bahasa lain tidak masa depan-bukti keputusan jika the downside adalah signifikan. Dalam bahasa lokal (tr_TR
), hasil yang benar dari toupper('i')
adalah 'I'
(U0130), bukan 'I'
(ASCII biasa). Lihat Martin Bonner's komentar pada pertanyaan tentang tolower()
menjadi lambat pada Windows.
Kami juga dapat memeriksa pengecualian-daftar dan mundur ke skalar ada, seperti untuk multi-byte UTF8 input karakter.
Dengan ini banyak kompleksitas, SSE4.2 PCMPISTRM
atau sesuatu yang mungkin bisa melakukan banyak kami cek dalam satu pergi.
Apakah anda memiliki ASCII atau Internasional karakter dalam string?
Jika itu's kasus terakhir, "uppercasing" tidak sesederhana itu, dan itu tergantung pada alfabet yang digunakan. Ada bikameral dan unikameral huruf. Hanya bikameral huruf memiliki karakter yang berbeda untuk bagian atas dan bawah kasus. Juga, ada karakter komposit, seperti huruf Latin 'DZ' (\u01F1 'DZ') yang menggunakan apa yang disebut judul kasus. Ini berarti bahwa hanya karakter pertama (D) akan berubah.
Saya sarankan anda melihat ke ICU, dan perbedaan antara Sederhana dan Penuh Hal Pemetaan. Hal ini mungkin dapat membantu:
string StringToUpper(string strToConvert)
{
for (std::string::iterator p = strToConvert.begin(); strToConvert.end() != p; ++p)
*p = toupper(*p);
return p;
}
Atau,
string StringToUpper(string strToConvert)
{
std::transform(strToConvert.begin(), strToConvert.end(), strToConvert.begin(), ::toupper);
return strToConvert;
}
Berikut ini bekerja untuk saya.
#include <algorithm>
void toUpperCase(std::string& str)
{
std::transform(str.begin(), str.end(), str.begin(), ::toupper);
}
int main()
{
std::string str = "hello";
toUpperCase(&str);
}
Lebih cepat satu jika anda hanya menggunakan karakter ASCII:
for(i=0;str[i]!=0;i++)
if(str[i]<='z' && str[i]>='a')
str[i]-=32;
Harap dicatat bahwa kode ini berjalan lebih cepat, tetapi hanya bekerja pada ASCII dan bukan "abstrak" solusi.
Jika anda membutuhkan UNICODE solusi atau yang lebih konvensional dan abstrak solusi, pergi untuk jawaban yang lain dan bekerja dengan metode C++ string.
Asalkan kau baik-baik saja dengan ASCII-saja dan anda dapat memberikan yang valid pointer ke RW memori, ada yang sederhana dan sangat efektif one-liner di C:
void strtoupper(char* str)
{
while (*str) *(str++) = toupper((unsigned char)*str);
}
Hal ini terutama baik untuk string sederhana seperti ASCII pengidentifikasi yang anda inginkan untuk menormalkan menjadi karakter yang sama-kasus. Anda kemudian dapat menggunakan buffer untuk membangun sebuah std:string contoh.
//works for ASCII -- no clear advantage over what is already posted...
std::string toupper(const std::string & s)
{
std::string ret(s.size(), char());
for(unsigned int i = 0; i < s.size(); ++i)
ret[i] = (s[i] <= 'z' && s[i] >= 'a') ? s[i]-('a'-'A') : s[i];
return ret;
}
#include <string>
#include <locale>
std::string str = "Hello World!";
auto & f = std::use_facet<std::ctype<char>>(std::locale());
f.toupper(str.data(), str.data() + str.size());
Ini akan tampil lebih baik dari semua jawaban yang menggunakan global toupper fungsi, dan agaknya apa boost::to_upper lakukan di bawahnya.
Hal ini karena ::toupper untuk mencari lokal - karena mungkin've telah diubah oleh thread yang berbeda untuk setiap doa, sedangkan di sini hanya panggilan lokal() memiliki hukuman ini. Dan mencari lokal umumnya melibatkan mengambil kunci.
Ini juga bekerja dengan C++98 setelah anda mengganti auto, penggunaan non-const str.data(), dan menambahkan ruang untuk istirahat template penutupan (">>" "> >") seperti ini:
std::use_facet<std::ctype<char> > & f =
std::use_facet<std::ctype<char> >(std::locale());
f.toupper(const_cast<char *>(str.data()), str.data() + str.size());
typedef std::string::value_type char_t;
char_t up_char( char_t ch )
{
return std::use_facet< std::ctype< char_t > >( std::locale() ).toupper( ch );
}
std::string toupper( const std::string &src )
{
std::string result;
std::transform( src.begin(), src.end(), std::back_inserter( result ), up_char );
return result;
}
const std::string src = "test test TEST";
std::cout << toupper( src );
tidak yakin ada yang dibangun di fungsi. Coba ini:
Termasuk ctype.jam ATAU cctype perpustakaan, serta stdlib.jam sebagai bagian dari preprocessor directive.
string StringToUpper(string strToConvert)
{//change each element of the string to upper case
for(unsigned int i=0;i<strToConvert.length();i++)
{
strToConvert[i] = toupper(strToConvert[i]);
}
return strToConvert;//return the converted string
}
string StringToLower(string strToConvert)
{//change each element of the string to lower case
for(unsigned int i=0;i<strToConvert.length();i++)
{
strToConvert[i] = tolower(strToConvert[i]);
}
return strToConvert;//return the converted string
}
Solusi saya (kliring 6 bit untuk alpha):
#include <ctype.h>
inline void toupper(char* str)
{
while (str[i]) {
if (islower(str[i]))
str[i] &= ~32; // Clear bit 6 as it is what differs (32) between Upper and Lowercases
i++;
}
}