Почему vector ‹bool› не является контейнером STL?

Многие считают специализацию vector<bool> ошибкой.

В статье «Устранение устаревших частей библиотеки в C + +17 "
Есть предложение пересмотреть частичную специализацию векторов.

Имеется долгая история частичной специализации bool для std :: vector, не удовлетворяющей требованиям контейнера, и, в частности, его итераторы не удовлетворяют требованиям итератора с произвольным доступом. Предыдущая попытка исключить этот контейнер была отклонена для C ++ 11, N2204.

Одна из причин отказа заключается в том, что неясно, что будет означать отказ от определенной специализации шаблона. К этому можно было бы обратиться с осторожной формулировкой. Более серьезная проблема заключается в том, что (упакованная) специализация вектора предлагает важную оптимизацию, которую действительно ищут клиенты стандартной библиотеки, но которая больше не будет доступна. Маловероятно, что мы сможем отказаться от этой части стандарта, пока не будет предложена и принята замена, например N2050. К сожалению, в настоящее время Рабочей группе по эволюции библиотек таких пересмотренных предложений нет.

Посмотрите, как это реализовано. STL в значительной степени строится на шаблонах, и поэтому заголовки содержат код, который они содержат.

например, посмотрите на реализацию stdc ++ здесь.

Также интересен, хотя и не соответствующий stl битовый вектор, это llvm :: BitVector из здесь.

суть llvm::BitVector - это вложенный класс с именем reference и подходящая перегрузка операторов, чтобы BitVector вел себя аналогично vector с некоторыми ограничениями. Приведенный ниже код представляет собой упрощенный интерфейс, показывающий, как BitVector скрывает класс с именем reference, чтобы реальная реализация вела себя почти как реальный массив bool без использования 1 байта для каждого значения.

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

у этого кода есть приятные свойства:

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.

В этом коде действительно есть недостаток, попробуйте запустить:

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

не будет работать, потому что assert( (&b[5] - &b[3]) == (5 - 3) ); выйдет из строя (в пределах llvm::BitVector)

это очень простая версия llvm. В std::vector<bool> также есть рабочие итераторы. таким образом вызов for(auto i = b.begin(), e = b.end(); i != e; ++i) будет работать. а также std::vector<bool>::const_iterator.

Однако в std::vector<bool> все еще есть ограничения, из-за которых в некоторых случаях он ведет себя иначе.

Это происходит из http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool Это специализированная версия вектора, которая используется для элементов типа bool и оптимизируется для пространства.

Он ведет себя как неспециализированная версия вектора со следующими изменениями:

• Хранилище не обязательно является массивом значений типа bool, но реализация библиотеки может оптимизировать хранилище, чтобы каждое значение хранилось в одном бите.
• Элементы не создаются с использованием объекта-распределителя, но их значение напрямую устанавливается в соответствующий бит во внутренней памяти.
• Флип функции члена и новая подпись для замены члена.
• Специальный тип члена, ссылка, класс, который обращается к отдельным битам во внутренней памяти контейнера с помощью интерфейса, который имитирует ссылку типа bool. И наоборот, тип члена const_reference является простым логическим значением.
• Типы указателя и итератора, используемые контейнером, не обязательно не являются ни указателями, ни соответствующими итераторами, хотя они должны имитировать большую часть своего ожидаемого поведения.

Эти изменения обеспечивают необычный интерфейс для этой специализации и отдают предпочтение оптимизации памяти над обработкой (которая может соответствовать вашим потребностям, а может и не соответствовать). В любом случае невозможно напрямую создать неспециализированный шаблон вектора для bool. Обходные пути, чтобы избежать этого диапазона, от использования другого типа (char, unsigned char) или контейнера (например, deque) для использования типов-оболочек или дальнейшей специализации для определенных типов распределителей.

bitset - это класс, который обеспечивает аналогичную функциональность для массивов битов фиксированного размера.