Kinerja apa yang dapat kita harapkan dari std :: string's c_str ()? Waktu selalu konstan?

13

Saya telah melakukan beberapa optimasi yang dibutuhkan belakangan ini. Satu hal yang telah saya lakukan adalah mengubah beberapa ostringstreams -> sprintfs. Saya sprintf'ing banyak std :: string ke ac style array, ala

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

Ternyata implementasi std :: string :: c_str () Microsoft berjalan dalam waktu konstan (hanya mengembalikan pointer internal). Tampaknya libstdc ++ melakukan hal yang sama . Saya menyadari std tidak memberikan jaminan untuk c_str, tetapi sulit membayangkan cara lain untuk melakukan ini. Jika, misalnya, mereka menyalin ke dalam memori mereka juga harus mengalokasikan memori untuk buffer (menyerahkannya kepada pemanggil untuk menghancurkannya - BUKAN bagian dari kontrak STL) ATAU mereka harus menyalin ke statis internal buffer (mungkin bukan threadsafe, dan Anda tidak memiliki jaminan seumur hidup). Jadi hanya mengembalikan pointer ke string yang diakhiri dengan null yang dipelihara secara internal tampaknya menjadi satu-satunya solusi yang realistis.

c++ performance strings Doug T.
sumber

Jawaban:

9

Jika saya ingat, standar memungkinkan string::c_str()untuk mengembalikan hampir semua hal yang memuaskan:

  • Penyimpanan yang cukup besar untuk isi string dan terminating NULL
  • Harus valid hingga anggota non-const dari stringobjek yang diberikan dipanggil

Jadi dalam praktiknya, ini berarti pointer ke penyimpanan internal; karena tidak ada cara untuk melacak kehidupan pointer yang dikembalikan secara eksternal. Saya pikir optimasi Anda aman untuk menganggap ini adalah waktu konstan (kecil).

Pada catatan terkait, jika pemformatan string membatasi kinerja; Anda mungkin lebih beruntung menunda evaluasi sampai benar-benar diperlukan dengan sesuatu seperti Boost.Phoenix .

Boost.Format Saya percaya mempertahankan format secara internal sampai hasilnya diperlukan, dan Anda dapat menggunakan objek format yang sama berulang kali tanpa mem-parsing ulang format string, yang saya temukan membuat perbedaan yang signifikan untuk logging frekuensi tinggi.

nilai
sumber
2
Dimungkinkan untuk implementasi untuk membuat buffer internal baru atau sekunder - cukup besar untuk ditambahkan pada terminator nol. Meskipun c_strmetode const (atau setidaknya memiliki overload const - saya lupa yang mana), ini tidak mengubah nilai logis, jadi mungkin merupakan alasan untuk itu mutable. Ini akan memecah pointer dari panggilan lain ke c_str, kecuali bahwa setiap pointer tersebut harus merujuk ke string logis yang sama (jadi tidak ada alasan baru untuk realokasi - pasti sudah ada terminator nol) atau ada harus sudah ada panggilan ke non Metode -const di antara keduanya.
Steve314
Jika ini benar-benar valid, c_strpanggilan dapat menjadi O (n) waktu untuk realokasi dan penyalinan. Tetapi ada juga kemungkinan bahwa ada aturan tambahan dalam standar yang saya tidak sadari akan mencegah hal ini. Alasan saya menyarankannya - panggilan ke c_strtidak benar-benar dimaksudkan untuk menjadi AFAIK biasa, sehingga mungkin tidak dianggap penting untuk memastikan mereka cepat - menghindari byte penyimpanan ekstra untuk terminator nol yang biasanya tidak perlu dalam stringhal yang tidak pernah digunakan c_strmungkin telah diutamakan.
Steve314
Boost.Formatinternal melewati stream yang internal melewati sprintfberakhir dengan overhead yang agak besar. Dokumentasi mengatakan itu sekitar 8 kali lebih lambat daripada biasa sprintf. Jika Anda ingin kinerja dan keamanan jenis, coba Boost.Spirit.Karma.
Jan Hudec
Boost.Spirit.Karmaadalah tip yang baik untuk kinerja, tetapi berhati-hatilah karena ia memiliki metodologi yang sangat berbeda yang mungkin sulit untuk mengadaptasi printfkode gaya yang ada (dan coders). Saya sebagian besar terjebak dengan Boost.Formatkarena I / O kami tidak sinkron; tetapi faktor besar adalah bahwa saya dapat meyakinkan kolega saya untuk menggunakannya secara konsisten (masih memungkinkan jenis apa pun dengan ostream<<kelebihan beban - yang dengan baik mengesampingkan.c_str() perdebatan) Angka kinerja Karma .
nilai p
23

Dalam standar c ++ 11 (saya membaca versi N 3290), bab 21.4.7.1 berbicara tentang metode c_str ():

const charT* c_str() const noexcept; const charT* data() const noexcept;

Pengembalian: Pointer p sehingga p + i == & operator untuk setiap i di [0, size ()].
Kompleksitas: waktu yang konstan.
Membutuhkan: Program tidak akan mengubah nilai-nilai yang tersimpan dalam array karakter.

Jadi, ya: kompleksitas waktu konstan dijamin oleh standar.

Saya baru saja memeriksa c ++ 03 standar, dan tidak memiliki persyaratan seperti itu, juga tidak memberitahu kompleksitasnya.

BЈовић
sumber
8

Dalam teori C ++ 03 tidak mengharuskan itu, dan karenanya string dapat berupa array char di mana keberadaan terminator nol ditambahkan hanya pada saat c_str () dipanggil. Ini mungkin memerlukan realokasi (itu tidak melanggar konstanta, jika pointer pribadi internal dinyatakan sebagai mutable).

C ++ 11 lebih ketat: membutuhkan waktu yang mahal, jadi tidak ada relokasi yang dapat dilakukan dan array harus selalu cukup lebar untuk menyimpan null pada akhirnya. c_str (), dengan sendirinya, masih dapat melakukan " ptr[size()]='\0'" untuk memastikan null benar-benar ada. Itu tidak melanggar konstanta array karena rentang [0..size())tidak berubah.

Emilio Garavaglia
sumber