26 Containers library [containers]

Для оптимизации распределения пространства предусмотрена специализация вектора для bool элементов:

namespace std {
  template <class Allocator>
  class vector<bool, Allocator> {
  public:
    // types:
    using value_type             = bool;
    using allocator_type         = Allocator;
    using pointer                = implementation-defined;
    using const_pointer          = implementation-defined;
    using const_reference        = bool;
    using size_type              = implementation-defined; // see [container.requirements]
    using difference_type        = implementation-defined; // see [container.requirements]
    using iterator               = implementation-defined; // see [container.requirements]
    using const_iterator         = implementation-defined; // see [container.requirements]
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    // bit reference:
    class reference {
      friend class vector;
      reference() noexcept;
    public:
      ~reference();
      operator bool() const noexcept;
      reference& operator=(const bool x) noexcept;
      reference& operator=(const reference& x) noexcept;
      void flip() noexcept;     // flips the bit
    };

    // construct/copy/destroy:
    vector() : vector(Allocator()) { }
    explicit vector(const Allocator&);
    explicit vector(size_type n, const Allocator& = Allocator());
    vector(size_type n, const bool& value,
           const Allocator& = Allocator());
    template <class InputIterator>
      vector(InputIterator first, InputIterator last,
             const Allocator& = Allocator());
    vector(const vector<bool, Allocator>& x);
    vector(vector<bool, Allocator>&& x);
    vector(const vector&, const Allocator&);
    vector(vector&&, const Allocator&);
    vector(initializer_list<bool>, const Allocator& = Allocator()));
    ~vector();
    vector<bool, Allocator>& operator=(const vector<bool, Allocator>& x);
    vector<bool, Allocator>& operator=(vector<bool, Allocator>&& x);
    vector& operator=(initializer_list<bool>);
    template <class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const bool& t);
    void assign(initializer_list<bool>);
    allocator_type get_allocator() const noexcept;

    // iterators:
    iterator               begin() noexcept;
    const_iterator         begin() const noexcept;
    iterator               end() noexcept;
    const_iterator         end() const noexcept;
    reverse_iterator       rbegin() noexcept;
    const_reverse_iterator rbegin() const noexcept;
    reverse_iterator       rend() noexcept;
    const_reverse_iterator rend() const noexcept;

    const_iterator         cbegin() const noexcept;
    const_iterator         cend() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    const_reverse_iterator crend() const noexcept;

    // capacity:
    bool      empty() const noexcept;
    size_type size() const noexcept;
    size_type max_size() const noexcept;
    size_type capacity() const noexcept;
    void      resize(size_type sz, bool c = false);
    void      reserve(size_type n);
    void      shrink_to_fit();

    // element access:
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    const_reference at(size_type n) const;
    reference       at(size_type n);
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;

    // modifiers:
    template <class... Args> reference emplace_back(Args&&... args);
    void push_back(const bool& x);
    void pop_back();
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    iterator insert(const_iterator position, const bool& x);
    iterator insert(const_iterator position, size_type n, const bool& x);
    template <class InputIterator>
      iterator insert(const_iterator position,
                      InputIterator first, InputIterator last);
    iterator insert(const_iterator position, initializer_list<bool> il);

    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);
    void swap(vector<bool, Allocator>&);
    static void swap(reference x, reference y) noexcept;
    void flip() noexcept;       // flips all bits
    void clear() noexcept;
  };
}

Если не описано ниже, все операции имеют те же требования и семантику, что и основной vector шаблон, за исключением того, что операции, работающие с bool типом значения, сопоставляются с битовыми значениями в хранилище контейнера и allocator_­traits​::​construct не используются для создания этих значений.

Нет требования, чтобы данные хранились как непрерывное распределение bool значений. Вместо этого рекомендуется оптимизированное по пространству представление битов.

reference - это класс, моделирующий поведение ссылок одного бита в vector<bool>. Функция преобразования возвращается, true когда бит установлен, и в false противном случае. Оператор присваивания устанавливает бит, когда аргумент (преобразовывается в), true и очищает его в противном случае. flip меняет состояние долота.