stlab.adobe.com Adobe Systems Incorporated

bit_vector

containers.gif
type.gif
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

RandomAccessContainer, BackInsertionSequence.

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 ReversibleContainer Iterator used to iterate backwards through a bit_vector.
const_reverse_iterator ReversibleContainer 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() ReversibleContainer Returns a reverse_iterator pointing to the beginning of the reversed bit_vector.
reverse_iterator rend() ReversibleContainer Returns a reverse_iterator pointing to the end of the reversed bit_vector.
const_reverse_iterator rbegin() const ReversibleContainer Returns a const_reverse_iterator pointing to the beginning of the reversed bit_vector.
const_reverse_iterator rend() const ReversibleContainer 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) RandomAccessContainer Returns the n'th element.
const_reference operator[](size_type n) const RandomAccessContainer 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() BackInsertionSequence Returns the last element.
const_reference back() const BackInsertionSequence Returns the last element.
void push_back(const T&) BackInsertionSequence Inserts a new element at the end.
void pop_back() BackInsertionSequence 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&)
ForwardContainer Tests two bit_vectors for equality. This is a global function, not a member function.
bool operator<(const bit_vector&, 
               const bit_vector&)
ForwardContainer Lexicographical comparison. This is a global function, not a member function.

New members

These members are not defined in the RandomAccessContainer and BackInsertionSequence 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 InputIterator. 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 © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google