16.12 — std::vector<bool>

W lekcji O.1 — Flagi bitowe i manipulacja bitami za pomocą std::bitset omówiliśmy, jak std::bitset ma możliwość kompaktowania 8 wartości logicznych w bajcie. Te bity można następnie modyfikować za pomocą funkcji składowych std::bitset.

std::vector ma w zanadrzu ciekawą sztuczkę. Istnieje specjalna implementacja dla std::vector<bool> który może oszczędzać miejsce w przypadku wartości logicznych poprzez podobne kompaktowanie 8 wartości logicznych w bajt.

W przeciwieństwie do std::bitset, który został zaprojektowany do manipulacji bitami, std::vector<bool> brakuje funkcji składowych manipulacji bitami.

Użycie std::vector<bool>

W większości std::vector<bool> działa jak zwykle std::vector:

#include <iostream>
#include <vector>

int main()
{
    std::vector<bool> v { true, false, false, true, true };
    
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    // Change the Boolean value with index 4 to false
    v[4] = false;

    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

Na 64-bitowej maszynie autora wypisuje:

1 0 0 1 1
1 0 0 1 0

std::vector<bool> kompromisy

Jednak std::vector<bool> ma pewne kompromisy, których użytkownicy powinieneś być tego świadomy.

Najpierw std::vector<bool> ma dość duży narzut (sizeof(std::vector<bool>) to 40 bajtów na komputerze autora), więc nie zaoszczędzisz pamięci, chyba że przydzielisz więcej wartości logicznych niż narzut dla twojej architektury.

Po drugie, wydajność std::vector<bool> jest w dużym stopniu zależna od implementacji (ponieważ implementacje nie są nawet wymagane do optymalizacji, nie mówiąc już o zrób to dobrze). Per ten artykuł, wysoce zoptymalizowana implementacja może być znacznie szybsza niż alternatywy, jednak źle zoptymalizowana implementacja będzie wolniejsza.

Po trzecie i najważniejsze, std::vector<bool> nie jest wektorem (nie musi być ciągły w pamięci), ani nie przechowuje bool wartości (przechowuje zbiór bitów) ani nie spełnia definicji kontenera C++.

Chociaż std::vector<bool> zachowuje się jak wektor w większości przypadków, nie jest w pełni kompatybilny z resztą standardowej biblioteki. Kod, który działa z innymi typami elementów, może nie działać z std::vector<bool>.

Na przykład poniższy kod działa, gdy T jest dowolnym typem. z wyjątkiem bool:

template<typename T>
void foo( std::vector<T>& v )
{
    T& first = v[0]; // get a reference to the first element
    // Do something with first
}

Unikaj std::vector<bool>

Współczesny konsensus jest taki, że std::vector<bool> należy unikać, ponieważ wzrost wydajności raczej nie będzie wart problemów związanych z niekompatybilnością ze względu na nieodpowiedni kontener.

Niestety, ta optymalizująca wersja std::vector<bool> jest domyślnie włączona i nie ma możliwości jej wyłączenia na rzecz niezoptymalizowanej wersji, która w rzeczywistości jest kontenerem wezwano do zaniechania std::vector<bool> i trwają prace nad określeniem, jak mógłby wyglądać zastępczy skompresowany wektor bool (być może w przyszłości std::dynamic_bitset).

Nasze zalecenie jest następujące:

• Użyj (constexpr) std::bitset kiedy liczba potrzebnych bitów jest znana w czasie kompilacji, nie masz więcej niż umiarkowaną liczbę Wartości logiczne do przechowywania (np. poniżej 64 kB) oraz ograniczony zestaw operatorów i funkcji składowych (np. brak obsługi iteratorów) spełniają Twoje wymagania.
• Preferuj std::vector<char> kiedy potrzebujesz kontenera wartości logicznych o zmiennym rozmiarze i oszczędności miejsca, nie jest to konieczne. Ten typ zachowuje się jak normalny kontener.
• Preferuj implementację dynamicznego zestawu bitów przez inną firmę (np. jak boost::dynamic_bitset), gdy potrzebny jest dynamiczny zestaw bitów do wykonywania operacji bitowych. Takie typy nie będą udawać standardowych kontenerów bibliotecznych, jeśli nimi nie są.