class vector in c++

Class vector<bool>

For Boolean elements of a vector, the C++ standard library provides a specialization of vector. The goal is to have a version that is optimized to use less size than a usual implementation of vector for type bool. Such a usual implementation would reserve at least 1 byte for each element. The vector<bool> specialization usually uses internally only 1 bit for an element, so it is typically eight times smaller. Note that such an optimization also has a snag: In C++, the smallest addressable value must have a size of at least 1 byte. Thus, such a specialization of a vector needs special handling for references and iterators.

As a result, a vector<bool> does not meet all requirements of other vectors (for example, a vector<bool>::reference is not a true lvalue and vector<bool>::iterator is not a random access iterator). Therefore, template code might work for vectors of any type except bool. In addition, vector<bool> might perform slower than normal implementations because element operations have to be transformed into bit operations. However, how vector<bool> is implemented is implementation specific. Thus, the performance (speed and memory) might differ.

Note that class vector<bool> is more than a specialization of vector<> for bool. It also provides some special bit operations. You can handle bits or flags in a more convenient way.

vector<bool> has a dynamic size, so you can consider it a bitfield with dynamic size. Thus, you can add and remove bits. If you need a bitfield with static size, you should use bitset rather than a vector<bool>.

Table : Special Operations of vector<bool>

The additional operations of vector<bool> are shown in Table above. The operation flip(), which processes the complement, can be called for all bits and a single bit of the vector. Note that you can call flip() for a single Boolean element. This is surprising, because you might expect that the subscript operator returns bool and that calling flip() for such a fundamental type is not possible. Here the class vector<bool> uses a common trick, called a proxy: For vector<bool>, the return type of the subscript operator (and other operators that return an element) is an auxiliary class. If you need the return value to be bool, an automatic type conversion is used. For other operations, the member functions are provided. The relevant part of the declaration of vector<bool> looks like this:

Note: A proxy allows you to keep control where usually no control is provided. This is often used to get more security. In this case, it maintains control to allow certain operations, although the return value in principle behaves as bool.

namespace std {

   class vector<bool> {

      public:

      //auxiliary type for subscript operator

      class reference {

        ...

        public:

        //automatic type conversion to bool

        operator bool() const;

        //assignments

        reference& operator= (const bool);

        reference& operator= (const reference&);

        //bit complement

        void flip();

     }

     ...

    //operations for element access

    //-return type is reference instead of bool

    reference operator[](size_type n);

    reference at(size_type n);

    reference front();

    reference back();

    ...

  };

}

As you can see, all member functions for element access return type reference. Thus, you could also use the following statement:

c.front().flip(); // negate first Boolean element

c.at(5) = c.back(); // assign last element to element with index 5

As usual, to avoid undefined behavior, the caller must ensure that the first, last, and sixth -elements exist.

The internal type reference is only used for nonconstant containers of type vector<bool>. The constant member functions for element access return ordinary values of type bool.