Dlaczego wektor <bool> nie jest kontenerem STL?

103

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ć?

P0W
źródło
22
To był błąd projektowy w C ++ 98, teraz zachowany ze względu na kompatybilność.
Oktalist
8
@ g-makulik, Nie chodzi o to, że jego użycie się nie skompiluje, po prostu nie możesz przechowywać adresu elementu we wskaźniku do bool, ponieważ element nie ma własnego adresu.
chris
1
@ g-makulik std::vector<bool> v;się skompiluje. &v[0]nie (przyjmując adres tymczasowy).
Oktalist
4
vector<bool>ma złą reputację, ale nie do końca uzasadnione, więc: isocpp.org/blog/2012/11/on-vectorbool
TemplateRex

Odpowiedzi:

120

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ą.

Mark B.
źródło
5
czy mamy inny typ danych, dla którego inny kontener STL jest wyspecjalizowany lub wyraźnie nazywany?
P0W
3
Czy to dotyczy C ++ 11 std :: array <bool>?
Sergio Basurco
4
@chuckleplant nie, std::arrayjest jedynie szablonowym opakowaniem otaczającym surową tablicę T[n]z kilkoma funkcjami pomocniczymi, takimi jak size()semantyka kopiowania / przenoszenia i dodanymi iteratorami, aby był zgodny z STL - i (na szczęście) nie narusza własnych zasad (zwróć uwagę na moje sceptycyzm tych :) „specjalizuję się” w „ bool”.
underscore_d
Tylko drobiazg - sizeof (bool) niekoniecznie musi być bajtem. stackoverflow.com/questions/4897844/…
Uri Raz
30

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.

Ivan Smirnov
źródło
1
@PrashantSrivastava deque<bool>nie jest wyspecjalizowana, więc to dosłownie bools deque holding.
Konrad Rudolph
@PrashantSrivastava vector<bool>ma określoną implementację szablonu. Wydaje mi się, że inne kontenery STL, takie jak „ deque<bool>nie”, więc przechowują wartości logiczne jak wszystkie inne typy.
Ivan Smirnov
Oto pytania zadające podobną rzecz w rdzeniu, gdzie zabroniono jednobitowych wartości booleans stackoverflow.com/questions/48875251/ ...
andy boot
25

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.

TemplateRex
źródło
10

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.

Trevor Hickey
źródło
5

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 .

Alexander Oh
źródło
3

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.

kvv
źródło
1
To nie odpowiada bezpośrednio na pytanie. W najlepszym przypadku wymaga to od czytelnika wywnioskowania, które rzeczy wyjaśnione w tym ogólnym podsumowaniu sprawiają, że nie jest to STL.
underscore_d