Mengapa vektor libc ++ <bool> :: const_reference bukan bool?

92

Bagian 23.3.7 Kelas vector<bool>[vector.bool], paragraf 1 menyatakan:

template <class Allocator> class vector<bool, Allocator> {
public:
    // types:
    typedef bool              const_reference;
    ...

Namun program ini gagal untuk dikompilasi saat menggunakan libc ++:

#include <vector>
#include <type_traits>

int
main()
{
    static_assert(std::is_same<std::vector<bool>::const_reference, bool>{}, "?");
}

Lebih lanjut saya perhatikan bahwa standar C ++ telah konsisten dalam spesifikasi ini sampai ke C ++ 98. Dan saya lebih lanjut mencatat bahwa libc ++ secara konsisten tidak mengikuti spesifikasi ini sejak pengenalan pertama libc ++.

Apa motivasi untuk ketidaksesuaian ini?

Howard Hinnant
sumber

Jawaban:

99

Motivasi untuk ekstensi ini, yang dapat dideteksi oleh program yang sesuai, dan dengan demikian tidak sesuai, adalah untuk membuat vector<bool>berperilaku lebih mirip vector<char>sehubungan dengan referensi (const dan sebaliknya).

pengantar

Sejak 1998, vector<bool>telah diejek sebagai "bukan wadah." LWG 96 , salah satu isu POKJA pertama, meluncurkan debat. Hari ini, 17 tahun kemudian, vector<bool>sebagian besar tetap tidak berubah.

Makalah ini membahas beberapa contoh spesifik tentang bagaimana perilaku vector<bool>berbeda dari setiap instansiasi lainnya vector, sehingga merugikan kode generik. Namun makalah yang sama membahas panjang lebar tentang properti kinerja yang sangat bagus vector<bool>jika diterapkan dengan benar.

Ringkasan : vector<bool>bukan wadah yang buruk. Ini sebenarnya cukup berguna. Itu hanya memiliki nama yang buruk.

Kembali ke const_reference

Seperti yang diperkenalkan di atas, dan dirinci di sini , yang buruk tentang itu vector<bool>adalah perilakunya berbeda dalam kode generik daripada vectorcontoh lainnya . Berikut adalah contoh konkretnya:

#include <cassert>
#include <vector>

template <class T>
void
test(std::vector<T>& v)
{
    using const_ref = typename std::vector<T>::const_reference;
    const std::vector<T>& cv = v;
    const_ref cr = cv[0];
    assert(cr == cv[0]);
    v[0] = 1;
    assert(true == cv[0]);
    assert(cr == cv[0]);  // Fires!
}

int
main()
{
    std::vector<char> vc(1);
    test(vc);
    std::vector<bool> vb(1);
    test(vb);
}

Spesifikasi standar mengatakan bahwa assert yang ditandai // Fires!akan terpicu, tetapi hanya jika testdijalankan dengan file vector<bool>. Saat dijalankan dengan vector<char>(atau vectorselain boolsaat non-default yang sesuai Tditetapkan), pengujian berhasil.

Implementasi libc ++ berusaha meminimalkan efek negatif karena vector<bool>berperilaku berbeda dalam kode generik. Satu hal itu untuk mencapai ini adalah untuk membuat vector<T>::const_referencesebuah proxy referensi , seperti yang ditentukan vector<T>::reference, kecuali bahwa Anda tidak dapat menetapkan melalui itu. Artinya, di libc ++, vector<T>::const_referencepada dasarnya adalah penunjuk ke bit di dalam vector, bukan salinan dari bit itu.

Di libc ++, langkah di atas testuntuk vector<char>dan vector<bool>.

Berapa biayanya?

Sisi negatifnya adalah ekstensi ini dapat dideteksi, seperti yang ditunjukkan dalam pertanyaan. Namun, sangat sedikit program yang benar-benar peduli dengan jenis alias ini secara tepat, dan lebih banyak program yang peduli dengan perilakunya.

Apa motivasi untuk ketidaksesuaian ini?

Untuk memberikan klien libc ++ perilaku yang lebih baik dalam kode generik, dan mungkin setelah pengujian lapangan yang memadai, usulkan ekstensi ini ke standar C ++ mendatang untuk kemajuan seluruh industri C ++.

Proposal semacam itu mungkin datang dalam bentuk wadah baru (misalnya bit_vector) yang memiliki API yang hampir sama seperti saat ini vector<bool>, tetapi dengan beberapa peningkatan seperti yang const_referencedibahas di sini. Diikuti dengan penghentian (dan akhirnya penghapusan) vector<bool>spesialisasi. bitsetbisa juga menggunakan sedikit peningkatan di departemen ini, misalnya menambah const_reference, dan satu set iterator.

Artinya, di belakang bitsetadalah vector<bool>(yang harus diganti namanya menjadi bit_vector- atau apa pun), sebagaimana arrayadanya vector. Dan analogi tersebut harus benar apakah yang kita bicarakan boolsebagai value_typedari vectordan array.

Ada beberapa contoh fitur C ++ 11 dan C ++ 14 yang dimulai sebagai ekstensi di libc ++. Beginilah cara standar berkembang. Pengalaman lapangan positif yang ditunjukkan secara aktual membawa pengaruh yang kuat. Orang standar adalah kelompok yang konservatif dalam hal mengubah spesifikasi yang ada (sebagaimana mestinya). Menebak, bahkan saat Anda yakin menebak dengan benar, adalah strategi berisiko untuk mengembangkan standar yang diakui secara internasional.

Howard Hinnant
sumber
1
Pertanyaan: dapatkah / akankah draf proposal terbaru pada iterator proxy oleh @EricNiebler entah bagaimana melegitimasi ekstensi libc ++ dan menempatkannya vector<bool>pada pijakan yang lebih berkelas?
TemplateRex
Catatan: Saya lebih suka memiliki a vector_bool<Alloc>dan an array_bool<N>untuk mewakili versi yang dikemas (termasuk iterator proxy akses acak yang mengiterasi semua bit) dari vector<bool, Alloc>dan array<bool, N>. Namun, bitset<N>(dan sepupunya boost::dynamic_bitset<Alloc>) mewakili abstraksi yang berbeda: yaitu versi yang dikemas std::set<int>. Jadi saya ingin memiliki, katakanlah, bit_array<N>dan bit_vector<Alloc>menjadi penerus franchise bitset, dengan iterator dua arah yang sesuai (iterasi pada 1-bit, bukan pada semua bit). Apa pendapat Anda tentang ini?
TemplateRex
5
Draf proposal saya tentang vector<bool>pengatur proxy akan membuat wadah akses acak yang sesuai dengan standar. Itu bukan vector<bool>ide yang bagus. :-) Saya setuju dengan Howard. Itu seharusnya disebut sesuatu yang lain.
Eric Niebler
1
Mengapa tidak ada cara untuk menyisih dari ekstensi libc ++ dan mendapatkan perilaku yang benar-benar sesuai? (Saya bahkan tidak meminta untuk membuat kesesuaian sebagai default, hanya cara untuk menonaktifkan ekstensi libc ++ agar dapat menulis kode portabel). Seperti yang Anda ketahui, saya pernah digigit oleh ekstensi libc ++ tuple di masa lalu, dan baru-baru ini digigit oleh ekstensi bitset :: const_reference.
gnzlbg
5
@gnzlbg: Sumber daya ekonomi dan temporal dalam jumlah terbatas tersedia untuk pengembangan awal libc ++. Selanjutnya implementasinya ditakdirkan untuk tidak membuat setiap pengguna senang. Dengan sumber daya yang tersedia, pengorbanan teknis dilakukan dalam upaya untuk memaksimalkan jumlah pengguna yang puas, memaksimalkan manfaat bagi komunitas C ++ secara keseluruhan. Maaf tentang pengalaman Anda. Saya perhatikan bahwa ekstensi tuple yang Anda jalankan bertabrakan sekarang ada di kertas kerja C ++ 1z saat ini. Dalam masalah itu, Anda tanpa sadar berkorban agar banyak yang bisa mendapatkan keuntungan, dan mereka banyak yang berhutang budi pada Anda.
Howard Hinnant