Mengapa vektor <bool> bukan container STL?

Item 18 dari buku Scott Meyers Effective STL: 50 Specific Ways to Impro your Use of Standard Template Library mengatakan untuk menghindari vector <bool>karena ini bukan wadah STL dan tidak benar-benar menahan bool.

Kode berikut:

vector <bool> v; 
bool *pb =&v[0];

tidak akan dikompilasi, melanggar persyaratan kontainer STL.

Kesalahan:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

vector<T>::operator []tipe pengembalian seharusnya T&, tetapi mengapa ini kasus khusus vector<bool>?

Sebenarnya vector<bool>terdiri dari apa?

Item lebih lanjut mengatakan:

deque<bool> v; // is a STL container and it really contains bools

Bisakah ini digunakan sebagai alternatif vector<bool>?

Adakah yang bisa menjelaskan ini?

Untuk alasan pengoptimalan ruang, standar C ++ (sejauh C ++ 98) secara eksplisit memanggil vector<bool>sebagai wadah standar khusus di mana setiap bool hanya menggunakan satu bit ruang daripada satu byte seperti yang biasa dilakukan bool (mengimplementasikan semacam "bitset dinamis"). Sebagai imbalan atas pengoptimalan ini, ia tidak menawarkan semua kemampuan dan antarmuka penampung standar normal.

Dalam kasus ini, karena Anda tidak dapat mengambil alamat bit dalam satu byte, hal-hal seperti operator[]tidak dapat mengembalikan bool&tetapi sebaliknya mengembalikan objek proxy yang memungkinkan untuk memanipulasi bit tertentu yang dimaksud. Karena objek proxy ini bukan a bool&, Anda tidak dapat menetapkan alamatnya bool*seperti yang Anda bisa dengan hasil dari panggilan operator seperti itu pada wadah "normal". Pada gilirannya ini berarti itu bool *pb =&v[0];bukan kode yang valid.

Di sisi lain dequetidak memiliki spesialisasi seperti itu yang dipanggil sehingga setiap bool mengambil byte dan Anda dapat mengambil alamat dari pengembalian nilai operator[].

Terakhir perhatikan bahwa implementasi pustaka standar MS (bisa dibilang) suboptimal karena menggunakan ukuran potongan kecil untuk deques, yang berarti bahwa menggunakan deque sebagai pengganti tidak selalu merupakan jawaban yang tepat.

vector<bool>berisi nilai boolean dalam bentuk terkompresi hanya menggunakan satu bit untuk nilai (dan bukan 8 bagaimana array bool [] lakukan). Tidak mungkin mengembalikan referensi ke sedikit di c ++, jadi ada jenis pembantu khusus, "referensi bit", yang memberi Anda antarmuka ke beberapa bit dalam memori dan memungkinkan Anda menggunakan operator dan cast standar.

Masalahnya adalah bahwa vector<bool>mengembalikan objek referensi proxy dan bukan referensi yang benar, sehingga kode gaya C ++ 98 bool * p = &v[0];tidak dapat dikompilasi. Namun, C ++ 11 modern dengan auto p = &v[0];dapat dibuat untuk dikompilasi jika operator&juga mengembalikan objek penunjuk proxy . Howard Hinnant telah menulis entri blog yang merinci peningkatan algoritmik saat menggunakan referensi dan penunjuk proxy tersebut.

Scott Meyers memiliki Item panjang 30 di C ++ Lebih Efektif tentang kelas proxy. Anda bisa datang jauh untuk hampir meniru tipe bawaan: untuk tipe tertentu T, sepasang proxy (misalnya reference_proxy<T>dan iterator_proxy<T>) dapat dibuat saling konsisten dalam arti reference_proxy<T>::operator&()dan iterator_proxy<T>::operator*()merupakan kebalikan satu sama lain.

Namun, pada titik tertentu seseorang perlu memetakan objek proxy kembali untuk berperilaku seperti T*atau T&. Untuk proxy iterator, seseorang dapat membebani operator->()dan mengakses Tantarmuka template tanpa menjalankan kembali semua fungsionalitasnya. Namun, untuk proxy referensi, Anda perlu melakukan overload operator.(), dan hal itu tidak diizinkan di C ++ saat ini (meskipun Sebastian Redl mempresentasikan proposal seperti itu di BoostCon 2013). Anda dapat membuat pekerjaan verbose seperti .get()anggota di dalam proxy referensi, atau menerapkan semua Tantarmuka di dalam referensi (inilah yang dilakukan untukvector<bool>::bit_reference), tetapi ini akan kehilangan sintaks bawaan atau memperkenalkan konversi yang ditentukan pengguna yang tidak memiliki semantik bawaan untuk konversi jenis (Anda dapat memiliki paling banyak satu konversi yang ditentukan pengguna per argumen).

TL; DR : tidak vector<bool>bukan wadah karena Standar memerlukan referensi nyata, tetapi dapat dibuat untuk berperilaku hampir seperti wadah, setidaknya lebih dekat dengan C ++ 11 (otomatis) daripada di C ++ 98.

Banyak yang menganggap vector<bool>spesialisasi sebagai kesalahan.

Dalam makalah "Deprecating Vestigial Library Parts in C ++ 17"
Ada proposal untuk Mempertimbangkan Kembali Vector Partial Specialization .

Telah ada sejarah panjang spesialisasi parsial bool dari std :: vector tidak memenuhi persyaratan container, dan khususnya, iteratornya tidak memenuhi persyaratan iterator akses acak. Upaya sebelumnya untuk menghentikan penampung ini ditolak untuk C ++ 11, N2204 .

Salah satu alasan penolakan adalah tidak jelas apa yang dimaksud dengan penghentian spesialisasi tertentu dari suatu template. Itu bisa diatasi dengan kata-kata yang hati-hati. Masalah yang lebih besar adalah bahwa (dikemas) spesialisasi vektor menawarkan pengoptimalan penting yang benar-benar dicari oleh klien pustaka standar, tetapi tidak lagi tersedia. Kami tidak mungkin dapat menghentikan bagian standar ini sampai fasilitas pengganti diusulkan dan diterima, seperti N2050 . Sayangnya, saat ini tidak ada proposal yang direvisi yang ditawarkan ke Library Evolution Working Group.

Lihatlah bagaimana ini diterapkan. STL sangat banyak dibangun di atas template dan oleh karena itu header berisi kode yang mereka lakukan.

misalnya lihat implementasi stdc ++ di sini .

juga menarik meskipun bukan vektor bit sesuai stl adalah llvm :: BitVector dari sini .

inti dari llvm::BitVectorini adalah kelas bersarang yang dipanggil referencedan operator yang overloading cocok untuk membuat BitVectorperilaku serupa vectordengan beberapa batasan. Kode di bawah ini adalah antarmuka yang disederhanakan untuk menunjukkan bagaimana BitVector menyembunyikan kelas yang dipanggil referenceuntuk membuat implementasi nyata hampir berperilaku seperti array bool nyata tanpa menggunakan 1 byte untuk setiap nilai.

class BitVector {
public:
  class reference {
    reference &operator=(reference t);
    reference& operator=(bool t);
    operator bool() const;
  };
  reference operator[](unsigned Idx);
  bool operator[](unsigned Idx) const;      
};

kode ini di sini memiliki properti yang bagus:

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool 
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

Kode ini sebenarnya memiliki kekurangan, coba jalankan:

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

tidak akan berfungsi karena assert( (&b[5] - &b[3]) == (5 - 3) );akan gagal (dalam llvm::BitVector)

ini adalah versi llvm yang sangat sederhana. std::vector<bool>juga bekerja iterator di dalamnya. dengan demikian panggilan itu for(auto i = b.begin(), e = b.end(); i != e; ++i)akan berhasil. dan juga std::vector<bool>::const_iterator.

Namun masih ada batasan std::vector<bool>yang membuatnya berperilaku berbeda dalam beberapa kasus.

Ini berasal dari http://www.cplusplus.com/reference/vector/vector-bool/

Vektor bool Ini adalah versi khusus dari vektor, yang digunakan untuk elemen tipe bool dan mengoptimalkan ruang.

Ini berperilaku seperti versi vektor yang tidak terspesialisasi, dengan perubahan berikut:

• Penyimpanan tidak harus berupa larik nilai bool, tetapi implementasi pustaka dapat mengoptimalkan penyimpanan sehingga setiap nilai
  disimpan dalam satu bit.
• Elemen tidak dibuat menggunakan objek pengalokasi, tetapi nilainya secara langsung ditetapkan pada bit yang tepat di penyimpanan internal.
• Flip fungsi anggota dan tanda tangan baru untuk pertukaran anggota.
• Tipe anggota khusus, referensi, kelas yang mengakses bit individu dalam penyimpanan internal wadah dengan antarmuka yang
  mengemulasi referensi bool. Sebaliknya, tipe anggota const_reference adalah bool biasa.
• Jenis pointer dan iterator yang digunakan oleh container belum tentu bukan pointer atau iterator yang sesuai, meskipun keduanya
  harus mensimulasikan sebagian besar perilaku yang diharapkan.

Perubahan ini memberikan antarmuka unik untuk spesialisasi ini dan mendukung pengoptimalan memori daripada pemrosesan (yang mungkin sesuai atau tidak sesuai dengan kebutuhan Anda). Dalam kasus apapun, tidak mungkin untuk membuat contoh template vektor yang tidak terspesialisasi untuk bool secara langsung. Solusi untuk menghindari rentang ini dari menggunakan jenis yang berbeda (char, unsigned char) atau wadah (seperti deque) untuk menggunakan jenis pembungkus atau lebih mengkhususkan diri untuk jenis pengalokasi tertentu.

bitset adalah kelas yang menyediakan fungsionalitas serupa untuk array bit berukuran tetap.