Dlaczego wektor <bool> nie jest kontenerem STL?

Punkt 18 książki Scotta Meyersa Efektywny STL: 50 konkretnych sposobów na poprawę korzystania ze standardowej biblioteki szablonów mówi, aby tego unikać, vector <bool>ponieważ nie jest to kontener STL i tak naprawdę nie zawiera bools.

Poniższy kod:

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

nie skompiluje się, naruszając wymóg kontenerów STL.

Błąd:

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

vector<T>::operator []zwracany typ ma być T&, ale dlaczego jest to specjalny przypadek vector<bool>?

Z czego tak vector<bool>naprawdę składa się?

Przedmiot dalej mówi:

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

Czy można to wykorzystać jako alternatywę dla vector<bool>?

Czy ktoś może to wyjaśnić?

Ze względu na optymalizację przestrzeni, standard C ++ (już w C ++ 98) jawnie wywołuje vector<bool>jako specjalny standardowy kontener, w którym każdy bool używa tylko jednego bitu miejsca, a nie jednego bajtu, jak zrobiłby to normalny bool (implementacja pewnego rodzaju „dynamiczny zestaw bitów”). W zamian za tę optymalizację nie oferuje wszystkich możliwości i interfejsu zwykłego standardowego kontenera.

W tym przypadku, ponieważ nie możesz wziąć adresu bitu w bajcie, rzeczy takie jak operator[]nie mogą zwrócić a, bool&ale zamiast tego zwracają obiekt proxy, który pozwala manipulować określonym bitem. Ponieważ ten obiekt proxy nie jest a bool&, nie możesz przypisać jego adresu do bool*takiego, jak byś mógł, w wyniku takiego wywołania operatora na „normalnym” kontenerze. To z kolei oznacza, że bool *pb =&v[0];nie jest to prawidłowy kod.

Z drugiej strony dequenie ma wywoływanej takiej specjalizacji, więc każdy bool zajmuje bajt i możesz wziąć adres zwracanej wartości operator[].

Na koniec zwróć uwagę, że implementacja standardowej biblioteki MS jest (prawdopodobnie) nieoptymalna, ponieważ używa małego rozmiaru fragmentu dla deques, co oznacza, że ​​użycie deque jako substytutu nie zawsze jest właściwą odpowiedzią.

vector<bool>zawiera wartości logiczne w skompresowanej formie, używając tylko jednego bitu dla wartości (a nie 8, jak to robią tablice bool []). Nie jest możliwe zwrócenie referencji do bitu w c ++, więc istnieje specjalny typ pomocnika „bit reference”, który zapewnia interfejs do niektórych bitów w pamięci i pozwala na użycie standardowych operatorów i rzutów.

Problem polega na tym, że vector<bool>zwraca obiekt odniesienia proxy zamiast prawdziwego odniesienia, więc kod w stylu C ++ 98 bool * p = &v[0];nie będzie się kompilował. Jednak współczesny C ++ 11 z auto p = &v[0];można skompilować, jeśli zwracaoperator& również obiekt wskaźnika proxy . Howard Hinnant napisał post na blogu, w którym szczegółowo opisał ulepszenia algorytmiczne podczas korzystania z takich odwołań i wskaźników proxy.

Scott Meyers ma długi artykuł 30 w bardziej efektywnym języku C ++ na temat klas proxy. Można długą drogę do prawie naśladować wbudowanych typów: dla danego typu T, parę proxy (np reference_proxy<T>a iterator_proxy<T>) mogą być wzajemnie zgodne w tym sensie, że reference_proxy<T>::operator&()i iterator_proxy<T>::operator*()są wzajemnie odwrotne.

Jednak w pewnym momencie trzeba odwzorować obiekty proxy z powrotem, aby zachowywały się jak T*lub T&. W przypadku serwerów proxy iteratorów można przeciążać operator->()i uzyskiwać dostęp do Tinterfejsu szablonu bez ponownego wdrażania wszystkich funkcji. Jednak w przypadku proxy referencyjnych musiałbyś przeciążać operator.(), a to nie jest dozwolone w obecnym C ++ (chociaż Sebastian Redl przedstawił taką propozycję na BoostCon 2013). Możesz dokonać szczegółowego obejścia, jak .get()członek wewnątrz referencyjnego proxy, lub zaimplementować cały Tinterfejs wewnątrz referencji (to jest to, co jest zrobione dlavector<bool>::bit_reference), ale spowoduje to utratę wbudowanej składni lub wprowadzenie konwersji zdefiniowanych przez użytkownika, które nie mają wbudowanej semantyki dla konwersji typów (możesz mieć co najwyżej jedną konwersję zdefiniowaną przez użytkownika na argument).

TL; DR : no vector<bool>nie jest kontenerem, ponieważ Standard wymaga prawdziwego odniesienia, ale można go sprawić, aby zachowywał się prawie jak kontener, przynajmniej znacznie bliżej w C ++ 11 (auto) niż w C ++ 98.

Wielu uważa vector<bool>specjalizację za błąd.

W artykule „Wycofanie szczątkowych części biblioteki w C ++ 17”
jest propozycja ponownego rozważenia częściowej specjalizacji wektorów .

Istnieje długa historia częściowej specjalizacji bool std :: vector, która nie spełniała wymagań kontenera, aw szczególności jego iteratory nie spełniały wymagań iteratora o dostępie swobodnym. Poprzednia próba wycofania tego kontenera została odrzucona dla C ++ 11, N2204 .

Jednym z powodów odrzucenia jest to, że nie jest jasne, co oznaczałoby wycofanie określonej specjalizacji szablonu. Można temu zaradzić, używając ostrożnego sformułowania. Większy problem polega na tym, że (upakowana) specjalizacja wektora oferuje ważną optymalizację, której klienci biblioteki standardowej naprawdę szukają, ale nie byłaby już dostępna. Jest mało prawdopodobne, abyśmy byli w stanie zrezygnować z tej części standardu do czasu zaproponowania i zaakceptowania instrumentu zastępczego, takiego jak N2050 . Niestety, obecnie nie ma takich poprawionych propozycji, które są oferowane grupie roboczej Library Evolution.

Zobacz, jak to jest realizowane. STL w dużej mierze opiera się na szablonach i dlatego nagłówki zawierają kod, który robią.

na przykład spójrz na implementację stdc ++ tutaj .

Interesująca choć nie jest zgodny STL bitowy wektor jest llvm :: BitVector od tutaj .

istotą llvm::BitVectorjest zagnieżdżona klasa wywołana referencei odpowiednie przeciążenie operatora, aby zachować BitVectorpodobne zachowanie vectorz pewnymi ograniczeniami. Poniższy kod jest uproszczonym interfejsem, który pokazuje, jak BitVector ukrywa klasę wywołaną, referenceaby rzeczywista implementacja zachowywała się prawie jak prawdziwa tablica bool bez używania 1 bajtu dla każdej wartości.

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;      
};

ten kod tutaj ma ładne właściwości:

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.

Ten kod faktycznie ma wadę, spróbuj uruchomić:

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

nie zadziała, ponieważ assert( (&b[5] - &b[3]) == (5 - 3) );zawiedzie (w ciągu llvm::BitVector)

to jest bardzo prosta wersja llvm. std::vector<bool>ma również działające iteratory. w ten sposób połączenie for(auto i = b.begin(), e = b.end(); i != e; ++i)zadziała. a także std::vector<bool>::const_iterator.

Jednak nadal istnieją ograniczenia, std::vector<bool>które powodują, że w niektórych przypadkach zachowuje się inaczej .

Pochodzi z http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool Jest to wyspecjalizowana wersja wektora, która jest używana dla elementów typu bool i optymalizowana pod kątem przestrzeni.

Zachowuje się jak niespecjalizowana wersja wektora, z następującymi zmianami:

• Pamięć niekoniecznie jest tablicą wartości bool, ale implementacja biblioteki może zoptymalizować pamięć, tak aby każda wartość była
  przechowywana w jednym bicie.
• Elementy nie są konstruowane przy użyciu obiektu alokatora, ale ich wartość jest ustawiana bezpośrednio na odpowiednim bicie w pamięci wewnętrznej.
• Odwrócenie funkcji składowej i nowy podpis do zamiany elementów członkowskich.
• Specjalny typ elementu członkowskiego, referencja, klasa, która uzyskuje dostęp do poszczególnych bitów w pamięci wewnętrznej kontenera za pomocą interfejsu
  emulującego odwołanie bool. I odwrotnie, typ elementu członkowskiego const_reference to zwykły bool.
• Typy wskaźników i iteratorów używane przez kontener nie muszą być ani wskaźnikami, ani zgodnymi iteratorami, chociaż
  powinny symulować większość ich oczekiwanego zachowania.

Te zmiany zapewniają dziwaczny interfejs dla tej specjalizacji i faworyzują optymalizację pamięci zamiast przetwarzania (co może, ale nie musi odpowiadać Twoim potrzebom). W każdym razie nie jest możliwe bezpośrednie utworzenie instancji niespecjalizowanego szablonu wektora dla bool. Obejścia umożliwiające uniknięcie używania innego typu (char, unsigned char) lub kontenera (np. Deque) w tym zakresie w celu użycia typów otoków lub dalszej specjalizacji dla określonych typów alokatorów.

bitset to klasa, która zapewnia podobną funkcjonalność dla tablic bitów o stałym rozmiarze.