Saya mendengar beberapa orang mengungkapkan kekhawatiran tentang operator "+" di std :: string dan berbagai solusi untuk mempercepat penggabungan. Apakah semua ini benar-benar diperlukan? Jika ya, apa cara terbaik untuk menggabungkan string di C ++?

Pekerjaan ekstra mungkin tidak sepadan, kecuali jika Anda benar-benar membutuhkan efisiensi. Anda mungkin akan memiliki efisiensi yang jauh lebih baik hanya dengan menggunakan operator + = sebagai gantinya.

Sekarang setelah pelepasan tanggung jawab hukum itu, saya akan menjawab pertanyaan Anda yang sebenarnya ...

Efisiensi kelas string STL bergantung pada implementasi STL yang Anda gunakan.

Anda dapat menjamin efisiensi dan memiliki kendali yang lebih besar dengan melakukan penggabungan secara manual melalui c fungsi bawaan.

Mengapa operator + tidak efisien:

Lihat antarmuka ini:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Anda dapat melihat bahwa objek baru dikembalikan setelah setiap tanda +. Itu berarti buffer baru digunakan setiap saat. Jika Anda melakukan banyak + operasi tambahan, itu tidak efisien.

Mengapa Anda bisa membuatnya lebih efisien:

• Anda menjamin efisiensi daripada mempercayai seorang delegasi untuk melakukannya secara efisien untuk Anda
• kelas std :: string tidak tahu apa-apa tentang ukuran maksimal string Anda, atau seberapa sering Anda akan menggabungkannya. Anda mungkin memiliki pengetahuan ini dan dapat melakukan sesuatu berdasarkan informasi ini. Hal ini akan mengurangi alokasi ulang.
• Anda akan mengontrol buffer secara manual sehingga Anda dapat yakin bahwa Anda tidak akan menyalin seluruh string ke buffer baru saat Anda tidak ingin hal itu terjadi.
• Anda dapat menggunakan tumpukan untuk buffer Anda daripada heap yang jauh lebih efisien.
• string + operator akan membuat objek string baru dan mengembalikannya menggunakan buffer baru.

Pertimbangan untuk implementasi:

• Perhatikan panjang senar.
• Pertahankan penunjuk ke akhir string dan awal, atau hanya awal dan gunakan awal + panjang sebagai offset untuk menemukan akhir string.
• Pastikan buffer tempat Anda menyimpan string cukup besar sehingga Anda tidak perlu mengalokasikan ulang data
• Gunakan strcpy sebagai pengganti strcat sehingga Anda tidak perlu mengulang panjang string untuk menemukan ujung string.

Struktur data tali:

Jika Anda membutuhkan penggabungan yang sangat cepat, pertimbangkan untuk menggunakan struktur data tali .

Pesan ruang terakhir Anda sebelumnya, lalu gunakan metode append dengan buffer. Misalnya, Anda mengharapkan panjang string akhir Anda menjadi 1 juta karakter:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Aku tidak akan khawatir tentang hal itu. Jika Anda melakukannya dalam satu loop, string akan selalu mengalokasikan memori untuk meminimalkan realokasi - cukup gunakan operator+=dalam kasus itu. Dan jika Anda melakukannya secara manual, seperti ini atau lebih lama

a + " : " + c

Kemudian itu membuat temporaries - bahkan jika kompilator bisa menghilangkan beberapa salinan nilai yang dikembalikan. Itu karena dalam pemanggilan berturut-turut operator+tidak mengetahui apakah parameter referensi mereferensikan objek bernama atau sementara dikembalikan dari sub operator+pemanggilan. Saya lebih suka tidak khawatir tentang itu sebelum tidak membuat profil terlebih dahulu. Tapi mari kita ambil contoh untuk menunjukkannya. Kami pertama kali memperkenalkan tanda kurung untuk memperjelas pengikatan. Saya meletakkan argumen langsung setelah deklarasi fungsi yang digunakan untuk kejelasan. Di bawah itu, saya tunjukkan apa ekspresi yang dihasilkan kemudian:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Sekarang, sebagai tambahan, tmp1adalah apa yang dikembalikan oleh panggilan pertama ke operator + dengan argumen yang ditampilkan. Kami menganggap kompilator benar-benar pintar dan mengoptimalkan salinan nilai kembalian. Jadi kita berakhir dengan satu string baru yang berisi penggabungan dari adan " : ". Sekarang, ini terjadi:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Bandingkan dengan yang berikut ini:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

Ini menggunakan fungsi yang sama untuk sementara dan untuk string bernama! Jadi kompilator harus menyalin argumen ke string baru dan menambahkannya dan mengembalikannya dari badan operator+. Itu tidak bisa mengambil memori sementara dan menambahkannya. Semakin besar ekspresi, semakin banyak salinan string yang harus dilakukan.

Visual Studio dan GCC berikutnya akan mendukung semantik pemindahan c ++ 1x (melengkapi semantik salinan ) dan rvalue referensi sebagai tambahan eksperimental. Itu memungkinkan untuk mengetahui apakah parameter mereferensikan sementara atau tidak. Ini akan membuat penambahan seperti itu sangat cepat, karena semua hal di atas akan berakhir dalam satu "pipa tambahan" tanpa salinan.

Jika ternyata menjadi hambatan, Anda tetap bisa melakukannya

 std::string(a).append(" : ").append(c) ...

The appendpanggilan menambahkan argumen untuk *thisdan kemudian kembali referensi untuk diri mereka sendiri. Jadi tidak ada penyalinan sementara yang dilakukan di sana. Atau sebagai alternatif, operator+=dapat digunakan, tetapi Anda akan membutuhkan tanda kurung yang jelek untuk memperbaiki prioritas.

Untuk sebagian besar aplikasi, itu tidak masalah. Cukup tulis kode Anda, tanpa menyadari bagaimana tepatnya operator + bekerja, dan hanya menangani masalah dengan tangan Anda sendiri jika itu menjadi hambatan yang nyata.

Tidak seperti .NET System.Strings, std :: strings C ++ dapat berubah, dan oleh karena itu dapat dibangun melalui penggabungan sederhana secepat melalui metode lainnya.

mungkin std :: stringstream sebagai gantinya?

Tetapi saya setuju dengan sentimen bahwa Anda mungkin harus membuatnya tetap dapat dipelihara dan dimengerti dan kemudian profil untuk melihat apakah Anda benar-benar mengalami masalah.

Dalam Imperfect C ++ , Matthew Wilson menyajikan penggabung string dinamis yang menghitung sebelumnya panjang string akhir agar hanya memiliki satu alokasi sebelum menggabungkan semua bagian. Kita juga bisa mengimplementasikan concatenator statis dengan bermain dengan template ekspresi .

Ide semacam itu telah diimplementasikan dalam implementasi STLport std :: string - yang tidak sesuai dengan standar karena peretasan yang tepat ini.

std::string operator+mengalokasikan string baru dan menyalin dua string operan setiap saat. ulangi berkali-kali dan itu menjadi mahal, O (n).

std::string appenddan operator+=di sisi lain, tingkatkan kapasitas sebesar 50% setiap kali tali perlu tumbuh. Yang mengurangi jumlah alokasi memori dan operasi penyalinan secara signifikan, O (log n).

Untuk string kecil tidak masalah. Jika Anda memiliki string besar, sebaiknya Anda menyimpannya dalam bentuk vektor atau di koleksi lain sebagai bagian. Dan tambahkan algoritme Anda untuk bekerja dengan kumpulan data seperti itu, bukan dengan satu string besar.

Saya lebih suka std :: ostringstream untuk penggabungan kompleks.

Seperti kebanyakan hal, lebih mudah untuk tidak melakukan sesuatu daripada melakukannya.

Jika Anda ingin mengeluarkan string besar ke GUI, mungkin apa pun yang Anda hasilkan dapat menangani string dalam potongan lebih baik daripada sebagai string besar (misalnya, menggabungkan teks dalam editor teks - biasanya mereka membuat baris terpisah struktur).

Jika Anda ingin mengeluarkan ke file, streaming data daripada membuat string besar dan mengeluarkannya.

Saya tidak pernah menemukan kebutuhan untuk membuat penggabungan lebih cepat diperlukan jika saya menghapus penggabungan yang tidak perlu dari kode lambat.

Mungkin performa terbaik jika Anda mengalokasikan (memesan) ruang sebelumnya dalam string yang dihasilkan.

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Pemakaian:

std::string merged = concat("This ", "is ", "a ", "test!");

Larik karakter sederhana, yang dikemas dalam kelas yang melacak ukuran larik dan jumlah byte yang dialokasikan adalah yang tercepat.

Triknya adalah dengan melakukan satu alokasi besar di awal.

di

https://github.com/pedro-vicente/table-string

Tolak ukur

Untuk Visual Studio 2015, x86 debug build, peningkatan substansial melalui C ++ std :: string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |  

Anda dapat mencoba yang ini dengan reservasi memori untuk setiap item:

namespace {
template<class C>
constexpr auto size(const C& c) -> decltype(c.size()) {
  return static_cast<std::size_t>(c.size());
}

constexpr std::size_t size(const char* string) {
  std::size_t size = 0;
  while (*(string + size) != '\0') {
    ++size;
  }
  return size;
}

template<class T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) noexcept {
  return N;
}
}

template<typename... Args>
std::string concatStrings(Args&&... args) {
  auto s = (size(args) + ...);
  std::string result;
  result.reserve(s);
  return (result.append(std::forward<Args>(args)), ...);
}