# bit_vector

Category: containers | Component type: type

### Description

A `bit_vector` is essentially a `vector<bool>`: it is a Sequence that has the same interface as `vector`. The main difference is that `bit_vector` is optimized for space efficiency. A `vector` always requires at least one byte per element, but a `bit_vector` only requires one bit per element.

Warning: The name `bit_vector` will be removed in a future release of the STL. The only reason that `bit_vector` is a separate class, instead of a template specialization of `vector<bool>`, is that this would require partial specialization of templates. On compilers that support partial specialization, `bit_vector` is a specialization of `vector<bool>`. The name `bit_vector` is a `typedef`. This `typedef` is not defined in the C++ standard, and is retained only for backward compatibility.

### Example

    bit_vector V(5);
    V[0] = true;
    V[1] = false;
    V[2] = false;
    V[3] = true;
    V[4] = false;

    for (bit_vector::iterator i = V.begin(); i < V.end(); ++i)
      cout << (*i ? '1' : '0');
    cout << endl;

### Definition

Defined in the standard header vector, and in the nonstandard backward-compatibility header bvector.h.

### Template parameters

None. `Bit_vector` is not a class template.

### Model of

Random access container, Back insertion sequence.

### Type requirements

None.

### Public base classes

None.

### Members

Member | Where defined | Description
--- | --- | ---
`value_type` | Container | The type of object stored in the bit_vector: `bool`
`reference` | `bit_vector` | A proxy class that acts as a reference to a single bit. See below for details.
`const_reference` | Container | Const reference to `value_type`. In `bit_vector` this is simply defined to be `bool`.
`size_type` | Container | An unsigned integral type.
`difference_type` | Container | A signed integral type.
`iterator` | Container | Iterator used to iterate through a `bit_vector`.
`const_iterator` | Container | Const iterator used to iterate through a `bit_vector`.
`reverse_iterator` | Reversible Container | Iterator used to iterate backwards through a `bit_vector`.
`const_reverse_iterator` | Reversible Container | Const iterator used to iterate backwards through a `bit_vector`.
`iterator begin()` | Container | Returns an `iterator` pointing to the beginning of the `bit_vector`.
`iterator end()` | Container | Returns an `iterator` pointing to the end of the `bit_vector`.
`const_iterator begin() const` | Container | Returns a `const_iterator` pointing to the beginning of the `bit_vector`.
`const_iterator end() const` | Container | Returns a `const_iterator` pointing to the end of the `bit_vector`.
`reverse_iterator rbegin()` | Reversible Container | Returns a `reverse_iterator` pointing to the beginning of the reversed bit_vector.
`reverse_iterator rend()` | Reversible Container | Returns a `reverse_iterator` pointing to the end of the reversed bit_vector.
`const_reverse_iterator rbegin() const` | Reversible Container | Returns a `const_reverse_iterator` pointing to the beginning of the reversed bit_vector.
`const_reverse_iterator rend() const` | Reversible Container | Returns a `const_reverse_iterator` pointing to the end of the reversed bit_vector.
`size_type size() const` | Container | Returns the number of elements in the `bit_vector`.
`size_type max_size() const` | Container | Returns the largest possible size of the `bit_vector`.
`size_type capacity() const` | `bit_vector` | See below.
`bool empty() const` | Container | `true` if the `bit_vector`'s size is `0`.
`reference operator[](size_type n)` | Random Access Container | Returns the `n`'th element.
`const_reference operator[](size_type n) const` | Random Access Container | Returns the `n`'th element.
`bit_vector()` | Container | Creates an empty bit_vector.
`bit_vector(size_type n)` | Sequence | Creates a bit_vector with `n` elements.
`bit_vector(size_type n, bool t)` | Sequence | Creates a bit_vector with `n` copies of `t`.
`bit_vector(const bit_vector&)` | Container | The copy constructor.
    template <class InputIterator>
    bit_vector(InputIterator, InputIterator)
    [1]
| Sequence | Creates a bit_vector with a copy of a range.
`~bit_vector()` | Container | The destructor.
`bit_vector& operator=(const bit_vector&)` | Container | The assignment operator
`void reserve(size_t)` | `bit_vector` | See below.
`reference front()` | Sequence | Returns the first element.
`const_reference front() const` | Sequence | Returns the first element.
`reference back()` | Back Insertion Sequence | Returns the last element.
`const_reference back() const` | Back Insertion Sequence | Returns the last element.
`void push_back(const T&)` | Back Insertion Sequence | Inserts a new element at the end.
`void pop_back()` | Back Insertion Sequence | Removes the last element.
`void swap(bit_vector&)` | Container | Swaps the contents of two bit_vectors.
    void swap(bit_vector::reference x,
              bit_vector::reference y)
| `bit_vector` | See below.
`iterator insert(iterator pos, bool x)` | Sequence | Inserts `x` before `pos`.
    template <class InputIterator>
    void insert(iterator pos,
                InputIterator f, InputIterator l)
    [1]
| Sequence | Inserts the range `[f, l)` before `pos`.
    void insert(iterator pos,
                size_type n, bool x)
| Sequence | Inserts `n` copies of `x` before `pos`.
`void erase(iterator pos)` | Sequence | Erases the element at position `pos`.
`void erase(iterator first, iterator last)` | Sequence | Erases the range `[first, last)`
`void clear()` | Sequence | Erases all of the elements.
    bool operator==(const bit_vector&,
                    const bit_vector&)
| Forward Container | Tests two bit_vectors for equality. This is a global function, not a member function.
    bool operator<(const bit_vector&,
                   const bit_vector&)
| Forward Container | Lexicographical comparison. This is a global function, not a member function.

### New members

These members are not defined in the Random access container and Back insertion sequence requirements, but are specific to `vector`.

Member | Description
--- | ---
`reference` | A proxy class that acts as a reference to a single bit; the reason it exists is to allow expressions like `V[0] = true`. (A proxy class like this is necessary, because the C++ memory model does not include independent addressing of objects smaller than one byte.) The public member functions of `reference` are `operator bool() const`, `reference& operator=(bool)`, and `void flip()`. That is, `reference` acts like an ordinary reference: you can convert a `reference` to `bool`, assign a `bool` value through a `reference`, or flip the bit that a `reference` refers to.
`size_type capacity() const` | Number of bits for which memory has been allocated. `capacity()` is always greater than or equal to `size()`. [2] [3]
`void reserve(size_type n)` | If `n` is less than or equal to `capacity()`, this call has no effect. Otherwise, it is a request for the allocation of additional memory. If the request is successful, then `capacity()` is greater than or equal to `n`; otherwise, `capacity()` is unchanged. In either case, `size()` is unchanged. [2] [4]
    void swap(bit_vector::reference x,
              bit_vector::reference y)
| Swaps the bits referred to by `x` and `y`. This is a global function, not a member function. It is necessary because the ordinary version of `swap` takes arguments of type `T&`, and `bit_vector::reference` is a class, not a built-in C++ reference.

### Notes

[1] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type `const bool*` or of type `bit_vector::const_iterator`.

[2] Memory will be reallocated automatically if more than `capacity() - size()` bits are inserted into the bit_vector. Reallocation does not change `size()`, nor does it change the values of any bits of the bit_vector. It does, however, increase `capacity()`, and it invalidates [5] any iterators that point into the bit_vector.

[3] When it is necessary to increase `capacity()`, `bit_vector` usually increases it by a factor of two. It is crucial that the amount of growth is proportional to the current `capacity()`, rather than a fixed constant: in the former case inserting a series of bits into a bit_vector is a linear time operation, and in the latter case it is quadratic.

[4] `reserve()` is used to cause a reallocation manually. The main reason for using `reserve()` is efficiency: if you know the capacity to which your `bit_vector` must eventually grow, then it is probably more efficient to allocate that memory all at once rather than relying on the automatic reallocation scheme. The other reason for using `reserve()` is to control the invalidation of iterators. [5]

[5] A `bit_vector`'s iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting a bit in the middle of a bit_vector invalidates all iterators that point to bits following the insertion or deletion point. It follows that you can prevent a bit_vector's iterators from being invalidated if you use `reserve()` to preallocate as much storage as the bit_vector will ever use, and if all insertions and deletions are at the bit_vector's end.

### See also

vector

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation