CONTENTS

Chapter 10. Special Containers

The C++ standard library provides not only the containers for the STL framework, but also some containers that fit some special needs and provide simple, almost self-explanatory interfaces. You can group these containers into

10.1 Stacks

The class stack<> implements a stack (also known as LIFO). With push(), you can insert any number of elements into the stack (Figure 10.1). With pop(), you can remove the elements in the opposite order in which they were inserted ("last in, first out").

Figure 10.1. Interface of a Stack

graphics/10fig01.gif

To use a stack, you have to include the header file <stack>[1]:

   #include <stack>

In <stack>, the class stack is defined as follows:

   namespace std {
       template <class T,
                 class Container = deque<T> >
       class stack;
   }

The first template parameter is the type of the elements. The optional second template parameter defines the container that is used internally by the queue for its elements. The default container is a deque. It was chosen because, unlike vectors, deques free their memory when elements are removed and don't have to copy all elements on reallocation (see Section 6.9, for a discussion of when to use which container).

For example, the following declaration defines a stack of integers[2]:

   stack<deque<int> > st;
				
   std::stack<int> st;     // integer stack

The stack implementation simply maps the operations into appropriate calls of the container that is used internally (Figure 10.2). You can use any sequence container class that provides the member functions back(), push_back(), and pop_back(). For example, you could also use a vector or a list as the container for the elements:

Figure 10.2. Internal Interface of a Stack

graphics/10fig02.gif

   std::stack<int,std::vector<int> > st;     // integer stack that uses a vector

10.1.1 The Core Interface

The core interface of stacks is provided by the member functions push(), top(), and pop():

Note that pop() removes the next element but does not return it, whereas top() returns the next element without removing it. Thus, you must always call both functions to process and remove the next element from the stack. This interface is somewhat inconvenient, but it performs better if you only want to remove the next element without processing it. Note that the behavior of top() and pop() is undefined if the stack contains no elements. To check whether the stack contains elements, the member functions size() and empty() are provided.

If you don't like the standard interface of stack<>, you can easily write a more convenient interface. See Section 10.1.4, for an example.

10.1.2 Example of Using Stacks

The following program demonstrates the use of class stack<>:

   // cont/stack1.cpp

   #include <iostream>
   #include <stack>
   using namespace std;

   int main()
   {

       stack<int> st;

       // push three elements into the stack
       st.push(l);
       st.push(2);
       st.push(3);

       // pop and print two elements from the stack
       cout << st.top() << ' ';
       st.pop() ;
       cout << st.top() << ' ';
       st.pop() ;

       // modify top element
       st.top() = 77;

       // push two new elements
       st.push(4);
       st.push(5);

       // pop one element without processing it
       st.pop() ;

       // pop and print remaining elements
       while (!st.empty()) {
           cout << st.top() << ' ';
           st.pop() ;
       }
       cout << endl;
   }

The output of the program is as follows:

   3  2  4  77

10.1.3 Class stack<> in Detail

The stack<> interface is so small, you can understand it easily by reading its typical implementation:

   namespace std {
      template <class T, class Container = deque<T> >
      class stack {
        public:
          typedef typename Container::value_type value_type;
          typedef typename Container::size_type  size_type;
          typedef          Container             container_type;
          protected:
            Container c;     // container
          public:
            explicit stack(const Container& = Container());

            bool        empty() const             { return c.empty(); }
            size_type   size()    const           { return c.size(); }
            void push   (const value_type& x)     { c.push_back(x); }
            void        pop()                     { c.pop_back(); }
            value_type& top()                     { return c.back(); }
            const value_type& top() const         { return c.back(); }
      };

      template <class T, class Container>
        bool operator==(const stack<T, Container>&,
                        const stack<T, Container>&);
      template <class T, class Container>
        bool operator< (const stack<T, Container>&,
                        const stack<T, Container>&);
      ...// (other comparison operators)
   }

The following subsections describe the members and operations in detail.

Type Definitions

stack:: value_type

stack:: size_type

stack:: container_type

Operations

stack::stack ()

explicit stack:: stack (const Container& cont)

size_type stack::size () const

bool stack::empty () const

void stack::push (const value_type& elem)

value_type& stack::top ()

const value_type& stack::top () const

void stack::pop ()

bool comparison (const stack&. stack1, const stack& stack2)

10.1.4 A User-Defined Stack Class

The standard class stack<> prefers speed over convenience and safety. This is not what I usually prefer. I have written my own stack class. It has the following two advantages:

  1. pop() returns the next element.

  2. pop() and top() throw exceptions when the stack is empty.

In addition, I have skipped the members that are not necessary for the ordinary stack user, such as the comparison operations. My stack class is defined as follows:

   // cont/Stack.hpp

    /* ************************************************************
     * Stack.hpp
     *  -safer and more convenient stack class
     * ************************************************************/

    #ifndef STACK_HPP
    #define STACK_HPP

    #include <deque>
    #include <exception>

    template <class T>
    class Stack {
      protected:
        std::deque<T> c;        // container for the elements

      public:
        /* exception class for pop() and top() with empty stack
        */
       class ReadEmptyStack : public std::exception {
         public:
           virtual const char* what() const throw() {
               return "read empty stack";
           }
       };

       // number of elements
       typename std::deque<T>::size_type size() const {
           return c.size();
       }

       // is stack empty?
       bool empty() const {
           return c.empty();
       }

       // push element into the stack
       void push (const T& elem) {
           c.push_back(elem) ;
       }

       // pop element out of the stack and return its value
       T pop () {
           if (c.empty()) {
               throw ReadEmptyStack();
           }
           T elem(c.back());
           c.pop_back();
           return elem;
       }

       // return value of next element
       T& top () {
           if (c.empty()) {
               throw ReadEmptyStack();
           }
           return c.back() ;
       }
   };

   #endif /* STACK_HPP */

With this stack class, the previous stack example could be written as follows:

   // cont/stack 2.cpp

   #include <iostream>
   #include "Stack.hpp"          // use special stack class
   using namespace std;

   int main()
   {
      try {
         Stack<int> st;

         // push three elements into the stack
         st.push(l);
         st.push(2);
         st.push(3);

         // pop and print two elements from the stack
         cout << st.pop() << ' ';
         cout << st.pop() << ' ';

         // modify top element
         st.top() = 77;

         // push two new elements
         st.push(4);
         st.push(5);

         // pop one element without processing it
         st.pop();

         /* pop and print three elements
          * - ERROR: one element too many
          */
         cout << st.pop() << ' ';
         cout << st.pop() << endl;
         cout << st.pop() << endl;
      }
      catch (const exception& e) {
         cerr << "EXCEPTION: " << e.what() << endl;
      }
   }

The additional final call of pop() forces an error. Unlike the standard stack class, this one throws an exception rather than resulting in undefined behavior. The output of the program is as follows:

   3 2 4 77
   EXCEPTION: read empty stack

10.2 Queues

The class queue<> implements a queue (also known as FIFO). With push(), you can insert any number of elements (Figure 10.3). With pop(), you can remove the elements in the same order in which they were inserted ("first in, first out"). Thus, a queue serves as a classic data buffer.

Figure 10.3. Interface of a Queue

graphics/10fig03.gif

To use a queue, you must include the header file <queue>[3]:

   #include <queue>

In <queue>, the class queue is defined as follows:

   namespace std {
       template <class T,
                 class Container = deque<T> >
       class queue;
   }

The first template parameter is the type of the elements. The optional second template parameter defines the container that is used internally by the queue for its elements. The default container is a deque.

For example, the following declaration defines a queue of strings[4]:

   queue<deque<string> > buffer;
   std::queue<std::string> buffer;      // string queue

The queue implementation simply maps the operations into appropriate calls of the container that is used internally (Figure 10.4). You can use any sequence container class that provides the member functions front(), back(), push_back(), and pop_front(). For example, you could also use a list as the container for the elements:

Figure 10.4. Internal Interface of a Queue

graphics/10fig04.gif

   std::queue<std::string,std::list<std::string> > buffer;

10.2.1 The Core Interface

The core interface of queues is provided by the member functions push(), front(), back() and pop():

Note that pop() removes the next element but does not return it, whereas front() and back() return the next element without removing it. Thus, you must always call front() and pop() to process and remove the next element from the queue. This interface is somewhat inconvenient, but it performs better if you only want to remove the next element without processing it. Note that the behavior of front(), back(), and pop() is undefined if the queue contains no elements. To check whether the queue contains elements, the member functions size() and empty() are provided.

If you don't like the standard interface of queue<>, you can easily write a more convenient interface. See Section 10.2.4, for an example.

10.2.2 Example of Using Queues

The following program demonstrates the use of class queue<>:

   // cont/queue1.cpp

    #include <iostream>
    #include <queue>
    #include <string>
    using namespace std;

    int main()
    {

        queue<string> q;

        // insert three elements into the queue
        q.push("These ");
        q.push("are ");
        q.push("more than ");

        // read and print two elements from the queue
        cout << q.front();
        q.pop();
        cout << q.front();
        q.pop();

        // insert two new elements
        q.push(''four ");
        q.push("words!");
        // skip one element
        q.pop();

        // read and print two elements
        cout << q.front();
        q.pop();
        cout << q.front() << endl;
        q.pop();

        //print number of elements in the queue
        cout << "number of elements in the queue: " << q.size()
             << endl;
   }

The output of the program is as follows:

   These are four words!
   number of elements in the queue: 0

10.2.3 Class queue<> in Detail

Similar to stack<>, the typical queue<> implementation is rather self-explanatory:

   namespace std {
       template <class T, class Container = deque<T> >
       class queue {
         public:
           typedef typename Container::value_type value_type;
           typedef typename Container::size_type size_type;
           typedef          Container            container_type;
         protected:
           Container c;     // container
         public:
           explicit queue(const Container& = Container());

           bool     empty() const              { return c.empty(); }
           size_type size() const              { return c.size(); }
           void     push(const value_type& x)  { c.push_back(x); }
           void     pop()                      { c.pop_front(); }
           value_type&      front()            { return c.front(); }
           const value_type& front()const      { return c.front(); }
           value_type&       back()            { return c.back(); }
           const value_type& back() const      { return c.back(); }
       };

       template <class T, class Container>
         bool operator==(const queue<T, Container>&,
                         const queue<T, Container>&);
       template <class T, class Container>
         bool operator< (const queue<T, Container>&,
                         const queue<T, Container>&);
         //(other comparison operators)
   }

The following subsections describe the members and operations in detail.

Type Definitions

queue::value_type

queue::size_type

queue:: container_type

Operations

queue::queue ()

explicit queue::stack (const Container& cont)

size_type queue::size () const

bool queue::empty () const

void queue::push (const value_type& elem)

value_type& queue::front ()

const value_type& queue::front () const

value_type& queue::back ()

const value_type& queue::back () const

void queue::pop ()

bool comparison (const queue& queue1, const queue& queue2)

10.2.4 A User-Defined Queue Class

The standard class queue<> prefers speed over convenience and safety. This is not what I usually prefer. I have written my own queue class. It has the following two advantages:

  1. pop() returns the next element.

  2. pop() and front() throw exceptions when the queue is empty.

In addition, I have skipped the members that are not necessary for the ordinary queue user, such as the comparison operations and the back() member function. My queue class is defined as follows:

   // cont/Queue.hpp

    /* ************************************************************
     * Queue.hpp
     * -safer and more convenient queue class
     * ************************************************************

    #ifndef QUEUE_HPP
    #define QUEUE_HPP

    #include <deque>
    #include <exception>
    template <class T>
    class Queue {
      protected:
        std::deque<T> c;             // container for the elements

      public:
        /* exception class for pop() and top() with empty queue
        */
       class ReadEmptyQueue : public std::exception {
          public:
            virtual const char* what() const throw() {
                return "read empty queue";
           }
       };

       // number of elements
       typename std::deque<T>::size_type size() const {
           return c.size();
       }

       //is queue empty?
       bool empty() const {
           return c.empty();
       }

       // insert element into the queue
       void push (const T& elem) {
           c.push_back(elem);
       }

       // read element from the queue and return its value
       T pop () {
           if (c.empty()) {
               throw ReadEmptyQueue();
           }
           T elem(c.front());
           c.pop_front();
           return elem;
       }

       // return value of next element
       T& front () {
           if (c.empty()) {
               throw ReadEmptyQueue();
           }
           return c.front();
           }
       };

       #endif /* QUEUE_HPP */

With this queue class, the previous queue example could be written as follows:

   // cont/queue 2.cpp

   #include <iostream>
   #include <string>
   #include "Queue.hpp"          // use special queue class
   using namespace std;

   int main()
   {
      try {
         Queue<string> q;

         // insert three elements into the queue
         q.push("These ");
         q.push(''are ");
         q.push(''more than ");

         // read and print two elements from the queue
         cout << q.pop();
         cout << q.pop();

         // push two new elements
         q.push("four ");
         q.push(''words!");

         // skip one element
         q.pop();

         // read and print two elements from the queue
         cout << q.pop();
         cout << q.pop() << endl;

         // print number of remaining elements
         cout << "number of elements in the queue: " << q.size()
              << endl;

         // read and print one element
         cout << q.pop ) << endl;
      }
      catch (const exception& e) {
         cerr << "EXCEPTION: " << e.what() << endl;
       }
   }

The additional final call of pop() forces an error. Unlike the standard queue class, this one throws an exception rather than resulting in undefined behavior. The output of the program is as follows:

   These are four words!
   number of elements in the queue: 0
   EXCEPTION: read empty queue

10.3 Priority Queues

The class priority_queue<> implements a queue from which elements are read according to their priority. The interface is similar to queues. That is, push() inserts an element into the queue, whereas top() and pop() access and remove the next element (Figure 10.5). However, the next element is not the first inserted element. Rather, it is the element that has the highest priority. Thus, elements are partially sorted according to their value. As usual, you can provide the sorting criterion as a template parameter. By default, the elements are sorted by using operator < in descending order. Thus, the next element is always the "highest" element. If more than one "highest" element exists, which element comes next is undefined.

Figure 10.5. Interface of a Priority Queue

graphics/10fig05.gif

Priority queues are defined in the same header file as ordinary queues, <queue>[5]:

   #include <queue>

In <queue>, the class priority_queue is defined as follows:

   namespace std {
       template <class T,
                 class Container = vector<T>,
                 class Compare = less<typename Container::value_type> >
       class priority_queue;
   }

The first template parameter is the type of the elements. The optional second template parameter defines the container that is used internally by the priority queue for its elements. The default container is a vector. The optional third template parameter defines the sorting criterion that is used to find the next element with the highest priority. By default, it compares the elements by using operator <.

For example, the following declaration defines a priority queue of floats[6]:

   priority_queue<vector<float>,less<float> > buffer;

			
   std::priority_queue<float> pbuffer;      // priority queue for floats

The priority queue implementation simply maps the operations into appropriate calls of the container that is used internally. You can use any sequence container class that provides random access iterators and the member functions front(), push_back(), and pop_back(). Random access is necessary for sorting the elements, which is performed by the heap algorithms of the STL (the heap algorithms are described in Section 9.9.4,). For example, you could also use a deque as the container for the elements:

   std::priority_queue<float,std::deque<float> > pbuffer;

To define your own sorting criterion you must pass a function or function object as a binary predicate that is used by the sorting algorithms to compare two elements (for more about sorting criteria, see Section 6.5.2, and Section 8.1.1,). For example, the following declaration defines a priority queue with reverse sorting:

   std::priority_queue<float,std::vector<float>,
                             std::greater<float> > pbuffer;

In this priority queue the next element is always one of the elements with the lowest value.

10.3.1 The Core Interface

The core interface of priority queues is provided by the member functions push(), top(), and pop():

As for the other container adapters, pop() removes the next element but does not return it, whereas top() returns the next element without removing it. Thus, you must always call both functions to process and remove the next element from the priority queue. And, as usual, the behavior of top() and pop() is undefined if the priority queue contains no elements. If in doubt, you must use the member functions size() and empty().

10.3.2 Example of Using Priority Queues

The following program demonstrates the use of class priority_queue<>:

   // cont/pqueue1. cpp

    #include <iostream>
    #include <queue>
    using namespace std;

    int main()
    {
        priority_queue<float> q;

        // insert three elements into the priority queue
        q.push(66.6);
        q.push(22.2);
        q.push(44.4);

        // read and print two elements
        cout << q.top() << ' ';
        q.pop();
        cout << q.top() << endl;
        q.pop();

        // insert three more elements
        q.push(11.1);
        q.push(55.5);
        q.push(33.3);

        // skip one element
        q.pop();

        //pop and print remaining elements
        while (!q.empty()) {
            cout << q.top() << ' ';
            q.pop();
        }
        cout << endl;
    }

The output of the program is as follows:

   66.6 44.4
   33.3 22.2 11.1

As you can see, after 66.6, 22.2, and 44.4 are inserted, the program prints 66.6 and 44.4 as the highest elements. After three other elements are inserted, the priority queue contains the elements 22.2, 11.1, 55.5, and 33.3 (in the order of insertion). The next element is skipped simply via a call of pop(), so the final loop prints 33.3, 22.2, and 11.1 in that order.

10.3.3 Class priority_queue<> in Detail

Most of the priority_queue<> operations are as self-explanatory as stack<> and queue<>:

   namespace std {
      template <class T, class Container = vector<T>,
                class Compare = less<typename Container::value_type> >
      class priority_queue {
        public:
          typedef typename Container::value_type value_type;
          typedef typename Container::size_type  size_type;
          typedef          Container             container_type;
        protected:
          Compare comp; // sorting criterion
          Container c;  // container
        public:
          // constructors
        explicit priority_queue(const Compare& cmp = Compare(),
                                const Container& cont = Container())
         : comp(cmp), c(cont) {
            make_heap(c.begin(),c.end(),comp);
        }

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last,
                       const Compare& cmp = Compare(),
                       const Container& cont = Container())
         : comp(cmp), c(cont) {
            c.insert(c.end(),first,last);
            make_heap(c.begin(),c.end(),comp);
         }

         void push(const value_type& x); {
            c.push_back(x);
            push_heap(c.begin(),c.end(),comp);
         }
         void pop() {
            pop_heap(c.begin(),c.end(),comp);
            c.pop_back();
         }

         bool              empty() const { return c.empty(); }
         size_type         size() const  { return c.size(); }
         const value_type& top() const   { return c.front(); }
      };
   }

As you can see, the priority queue uses the STL's heap algorithms. These algorithms are described in Section 9.9.4. Note that, unlike other container adapters, no comparison operators are defined.

The following subsections describe the members and operations in detail.

Type Definitions

priority_queue:: value_type

priority_queue::size_type

priority_queue::container_type

Constructors

priority_queue::priority_queue ()

explicit priority_queue::priority_queue (const CompFunc& op)

priority_queue::priority_queue (const CompFunc& op const Container& cont)

priority_queue::priority_queue (InputIterator beg, Inputlterator end)

priority_queue::priority_queue (InputIterator beg, Inputlterator end,const CompFunc& op)

priority_queue::priority_queue (InputIterator beg, InputIterator end, const CompFunc& op, const Container& cont)

Other Operations

size_type priority _queue::size () const

bool priority_queue::empty () const

void priority _queue::push (const value_type& elem)

const value_type& priority_queue::top () const

void priority_queue::pop ()

10.4 Bitsets

Bitsets model fixed-sized arrays of bits or Boolean values. They are useful to manage sets of flags, where variables may represent any combination of flags. C and old C++ programs usually use type long for arrays of bits and manipulate the bits with the bit operators, such as &, |, and ~. The class bitset has the advantage that bitsets may contain any number of bits, and additional operations are provided. For example, you can assign single bits, and read and write bitsets as a sequence of zeros and ones.

Note that you can't change the number of bits in a bitset. The number of bits is the template parameter. If you need a container for a variable number of bits or Boolean values, you can use the class vector<bool> (described in Section 6.2.6).

The class bitset is defined in the header file <bitset>:

   #include <bitset>

In <bitset>, the class bitset is defined as a template class with the number of bits as the template parameter:

   namespace std {
       template <size_t Bits>
       class bitset;
   }

In this case the template parameter is not a type but an unsigned integral value (see page 10 for details about this language feature).

Templates with different template arguments are different types. You can compare and combine bitsets only with the same number of bits.

10.4.1 Examples of Using Bitsets

Using Bitsets as Set of Flags

The first example of using bitsets demonstrates how to use bitsets to manage a set of flags. Each flag has a value that is defined by an enumeration type. The value of the enumeration type is used as the position of the bit in the bitset. In particular, the bits represent colors. Thus, each enumeration value defines one color. By using a bitset, you can manage variables that might contain any combination of colors:

   // cont/bitsetl.cpp

   #include <bitset>
   #include <iostream>
   using namespace std;
   int main()
   {
       /* enumeration type for the bits
        * - each bit represents a color
        */
       enum Color { red, yellow, green, blue, white, black, ...,
                    numColors };

       // create bitsetfor all bits/colors
       bitset<numColors> usedColors;

       // set bits for two colors
       usedColors.set(red);
       usedColors.set(blue);

       // print some bitset data
       cout << "bitfield of used colors: " << usedColors
            << endl;
       cout << "number of used colors: " << usedColors.count()
            << endl;
       cout << "bitfield of unused colors: " << ~usedColors
            << endl;

       // if any color is used
       if (usedColors.any()) {
           // loop over all colors
           for (int c = 0; c < numColors; ++c) {
               // if the actual color is used
               if (usedColors[(Color)c]) {
                   ...
               }
           }
       }
   }
Using Bitsets for I/O with Binary Representation

A useful feature of bitsets is the ability to convert integral values into a sequence of bits and vice versa. This is done simply by creating a temporary bitset:

   // cont/bitset2.cpp

   #include <bitset>
   #include <iostream>
   #include <string>
   #include <limits>
   using namespace std;

   int main()
   {
       /* print some numbers in binary representation
        */
       cout << "267 as binary short: "
            << bitset<numeric_limits<unsigned short>::digits>(267)
            << endl;

       cout << "267 as binary long: "
            << bitset<numeric_limits<unsigned long>::digits>(267)
            << endl;

       cout << "10,000,000 with 24 bits: "
            << bitset<24>(1e7) << endl;
       /* transform binary representation into integral number
        */
       cout << "\"1000101011\" as number: "
            << bitset<100>(string("1000101011")).to_ulong() << endl;
   }

Depending on the number of bits for short and long, the program might produce the following output:

   267 as binary short:     0000000100001011
   267 as binary long:      00000000000000000000000100001011
   10,000,000 with 24 bits: 100110001001011010000000
   "1000101011" as number:  555

In this example,

   bitset<numeric_limits<unsigned short>::digits>(267)

converts 267 into a bitset with the number of bits of type unsigned short (see Section 4.3, for a discussion of numeric limits). The output operator for bitset prints the bits as a sequence of characters 0 and 1.

Similarly,

   bitset<100>(string("1000101011"))

converts a sequence of binary characters into a bitset, for which to_ulong() yields the integral value. Note that the number of bits in the bitset should be smaller than sizeof (unsigned long). This is because you get an exception when the value of the bitset can't be represented as unsigned long.[7]

10.4.2 Class bitset in Detail

The bitset class provides the following operations.

Create, Copy, and Destroy Operations

For bitsets, some special constructors are defined. However, there is no special copy constructor, assignment operator, and destructor defined. Thus, bitsets are assigned and copied with the default operations that copy bitwise.

bitset<bits>::bitset ()

bitset<bits>::bitset (unsigned long value)

explicit bitset<bits>::bitset (const string& str)

bitset<bits>::bitset (const string& str, string::size_type str_idx)

bitset<bits>::bitset (const string& str, string::size_type str_idx, string::size_type str_num)

Nonmanipulating Operations

size_t bitset<bits>::size () const

size_t bitset<bits>::count () const

bool bitset<bits>::any () const

bool bitset<bits>::none () const

bool bitset<bits>::test (size_t idx) const

bool bitset<bits>::operator == (const bitset<bits>& bits) const

bool bitset<bits>::operator != (const bitset<bits>& bits) const

Manipulating Operations

bitset<bits>& bitset<bits>::set()

bitset<bits>& bitset<bits>::set (size_t idx)

bitset<bits>& bitset<bits>::set (size_t idx, int value)

bitset<bits>& bitset<bits>::reset()

bitset<bits>& bitset<bits>::reset (size_t idx)

bitset<bits>& bitset<bits>::flip ()

bitset<bits>& bitset<bits>::flip (size_t idx)

bitset<bits>& bitset<bits>::operator^= (const bitset<bits>& bits)

bitset<bits>& bitset<bits>::operator | = (const bitset<bits>& bits)

bitset<bits>& bitset<bits>::operator &= (const bitset<bits>& bits)

bitset<bits>& bitset<bits>::operator <<= (size_t num)

bitset<bits>& bitset<bits>::operator >>= (size_t num)

Access with Operator [ ]

bitset<bits>::reference bitset<bits>::operator [ ] (size_t idx)

bool bitset<bits>::operator [ ] (size_t idx) const

Operator [ ] returns a special temporary object of type bitset<>::reference when it is called for nonconstant bitsets. That object is used as a proxy[9] that allows certain modifications with the bit that is accessed by operator []. In particular, for references the following five operations are provided:

  1. referencefe& operator= (bool)

    Sets the bit according to the passed value.

  2. reference& operator= (const reference&)

    Sets the bit according to another reference.

  3. reference& flip ()

    Toggles the value of the bit.

  4. operator bool () const

    Converts the value into a Boolean value (automatically).

  5. bool operator~ () const

    Returns the complement (toggled value) of the bit.

For example, you can write the following statements:

   bitset<50> flags;
   ...
   flags [42] = true;             // set bit 42
   flags [13] = flags[42];        // assign value of bit 42 to bit 13
   flags [42].flip();             // toggle value of bit 42
   if (flags [13]) {              // if bit 13 is set,
       flags [10] = ~flags [42];  // then assign complement of bit 42 to bit 10
   }
Creating New Modified Bitsets

bitset<bits> bitset<bits>::operator ~ () const

bitset<bits> bitset<bits>::operator << (size_t num) const

bitset<bits> bitset<bits>::operator >> (size_t num) const

bitset<bits> operator & (const bitset<bits>& bits1, const bitset<bits>& bits2)

bitset<bits> operator | (const bitset<bits>& bits1, const bitset<bits>& bits2)

bitset<bits> operator^ (const bitset<bits>& bits1, const bitset<bits>& bits2)

Operations for Type Conversions

unsigned long bitset<bits>::to_ulong () const

string bitset<bits>::to_string () const

Input/Output Operations

istream& operator>> (istream& strm, bitset<bits>& bits)

ostream& operator << (ostream& strm, const bitset<bits>& bits)



[1]  In the original STL the header file for stacks was <stack.h>.

[2]  In previous versions of the STL you could pass the container as the only template parameter. Thus, a stack of integers had to be declared as follows:

[3]  In the original STL the header file for queues was <stack.h>

[4]  In previous versions of the STL you could pass the container as the only template parameter. Thus, a queue of strings had to be declared as follows:

[5]  In the original STL the header file for priority queues was <stack.h>.

[6]  In previous versions of the STL you always had to pass the container and sorting criterion as mandatory template arguments. Thus, a priority queue of floating values had to be declared as follows:

[7]  Note that you have to convert the initial value to type string explicitly. This is probably a mistake in the standard because it was possible to use

   bitset<100>("1000101011")

in earlier versions of the standard. By accident this implicit type conversion was ruled out when this constructor was templified for different string types. There is a proposed resolution to fix this problem.

[8]  This is probably a mistake in the standard because it was possible to use

   bitset<50> flags("l0l0l0l")

in earlier versions of the standard. By accident this implicit type conversion was ruled out when this constructor was templified for different string types. There is a proposed resolution to fix this problem.

[9]  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.

CONTENTS
Browser Based Help. Published by chm2web software.