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
The so-called container adapters
These containers adapt standard STL containers to fit special needs. There are three standard container adapters:
Stacks
Queues
Priority queues
Priority queues are queues in which the elements are sorted automatically according to a sorting criterion. Thus, the "next" element of a priority queue is the element with the "highest" value.
A special container, called a bitset
A bitset is a bitfield with an arbitrary but fixed number of bits. You can consider it a container for bits or Boolean values. Note that the C++ standard library also provides a special container with a variable size for Boolean values:
vector<bool>.It is described in Section 6.2.6.
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").
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 stack 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]:
std::stack<int> st; // integer stackThe 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:
std::stack<int,std::vector<int> > st; // integer stack that uses a vectorThe core interface of stacks is provided by the member functions push(), top(), and pop():
push()inserts an element into the stack.top()returns the next element in the stack.pop()removes an element from the stack.
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.
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(1); 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
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.
stack:: value_type
The type of the elements.
It is equivalent to container::
value_type.
stack:: size_type
The unsigned integral type for size values.
It is equivalent to container::
size_type.
stack:: container_type
The type of the container.
stack::stack
()
The default constructor.
Creates an empty stack.
explicit
stack::
stack (const Container&
cont)
Creates a stack that is initialized by the elements of cont.
All elements of cont are copied.
size_type
stack::size
() const
Returns the current number of elements.
To check whether the stack is empty (contains no elements), use
empty()because it might be faster.
bool
stack::empty
() const
Returns whether the stack is empty (contains no elements).
It is equivalent to stack::
size()==0,but it might be faster.
void
stack::push (const
value_type& elem)
Inserts a copy of elem as the new first element in the stack.
value_type& stack::top
()
const
value_type& stack::top
() const
Both forms return the next element of the stack. The next element is the element that was inserted last (after all other elements in the stack).
The caller has to ensure that the stack contains an element
(size()>0);otherwise, the behavior is undefined.The first form for nonconstant stacks returns a reference. Thus, you could modify the next element while it is in the stack. It is up to you to decide whether this is good style.
void
stack::pop
()
Removes the next element from the stack. The next element is the element that was inserted last (after all other elements in the stack).
This function has no return value. To process this next element, you must call
top()first.The caller must ensure that the stack contains an element
(size()>0);otherwise, the behavior is undefined.
bool
comparison (const
stack&. stack1,
const
stack& stack2)
Returns the result of the comparison of two stacks of the same type.
comparison might be any of the following:
operator == operator != operator < operator > operator <= operator >=
Two stacks are equal if they have the same number of elements and contain the same elements in the same order (all comparisons of two corresponding elements must yield
true).To check whether a stack is less than another stack, the stacks are compared lexicographically. See the description of the
lexicographical_compare()algorithm on page 360.
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:
pop()returns the next element.pop()andtop()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(1); 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
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.
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]:
std::queue<std::string> buffer; // string queueThe 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:
std::queue<std::string,std::list<std::string> > buffer;
The core interface of queues is provided by the member functions push(), front(), back() and pop():
push()inserts an element into the queue.front()returns the next element in the queue (the element that was inserted first).back()returns the last element in the queue (the element that was inserted last).pop()removes an element from the queue.
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.
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
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.
queue::value_type
The type of the elements.
It is equivalent to container::
value_type.
queue::size_type
The unsigned integral type for size values.
It is equivalent to container::
size_type.
queue:: container_type
The type of the container.
queue::queue
()
The default constructor.
Creates an empty queue.
explicit
queue::queue (const Container&
cont)
Creates a queue that is initialized by the elements of cont.
All elements of cont are copied.
size_type
queue::size
() const
Returns the current number of elements.
To check whether the queue is empty (contains no elements), use
empty()because it might be faster.
bool
queue::empty
() const
Returns whether the queue is empty (contains no elements).
It is equivalent to queue::
size()==0,but it might be faster.
void
queue::push (const value_type& elem)
Insert a copy of elem as the new last element in the queue.
value_type& queue::front
()
const value_type& queue::front
() const
Both forms return next element of the queue. The next element is the element that was inserted first (before all other elements in the queue).
The caller has to ensure that the queue contains an element
(size()>0);otherwise, the behavior is undefined.The first form for nonconstant queues returns a reference. Thus, you could modify the next element while it is in the queue. It is up to you to decide whether this is good style.
value_type& queue::back
()
const value_type& queue::back
() const
Both forms return the last element of the queue. The last element is the element that was inserted last (after all other elements in the queue).
The caller must ensure that the queue contains an element
(size()>0);otherwise, the behavior is undefined.The first form for nonconstant queues returns a reference. Thus, you could modify the last element while it is in the queue. It is up to you to decide whether this is good style.
void
queue::pop
()
Removes the next element from the queue. The next element is the element that was inserted first (before all other elements in the queue).
Note that this function has no return value. To process the next element, you must call
front()first.The caller must ensure that the queue contains an element
(size()>0);otherwise, the behavior is undefined.
bool
comparison (const
queue& queue1,
const
queue& queue2)
Returns the result of the comparison of two queues of the same type.
comparison might be any of the following:
operator == operator != operator < operator > operator <= operator >=
Two queues are equal if they have the same number of elements and contain the same elements in the same order (all comparisons of two corresponding elements must yield
true).To check whether a queue is less than another queue, the queues are compared lexicographically. See the description of the
lexicographical_compare()algorithm on page 360.
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:
pop()returns the next element.pop()andfront()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
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.
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]:
std::priority_queue<float> pbuffer; // priority queue for floatsThe 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.
The core interface of priority queues is provided by the member functions push(), top(), and pop():
push()inserts an element into the priority queue.top()returns the next element in the priority queue.pop()removes an element from the priority queue.
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().
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.
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.
priority_queue:: value_type
The type of the elements.
It is equivalent to container::
value_type.
priority_queue::size_type
The unsigned integral type for size values.
It is equivalent to container::
size_type.
priority_queue::container_type
The type of the container.
priority_queue::priority_queue
()
The default constructor.
Creates an empty priority queue.
explicit
priority_queue::priority_queue
(const CompFunc&
op)
Creates an empty priority queue with op used as the sorting criterion.
See page 191 and page 213 for examples that demonstrate how to pass a sorting criterion as a constructor argument.
priority_queue::priority_queue
(const CompFunc&
op
const Container&
cont)
Creates a priority queue that is initialized by the elements of cont and that uses op as the sorting criterion.
All elements of cont are copied.
priority_queue::priority_queue
(InputIterator
beg,
InputIterator
end)
Creates a priority queue that is initialized by all elements of the range [beg,end).
This function is a member template (see page 11), so the elements of the source range might have any type that is convertible into the element type of the container.
priority_queue::priority_queue
(InputIterator
beg,
InputIterator
end,const CompFunc&
op)
Creates a priority queue that is initialized by all elements of the range [beg,end) and that uses op as the sorting criterion.
This function is a member template (see page 11), so the elements of the source range might have any type that is convertible into the element type of the container.
See page 191 and page 213 for examples that demonstrate how to pass a sorting criterion as a constructor argument.
priority_queue::priority_queue
(InputIterator
beg,
InputIterator
end,
const CompFunc&
op,
const Container&
cont)
Creates a priority queue that is initialized by all elements of the container cont plus all elements of the range [beg,end) and that uses op as the sorting criterion.
This function is a member template (see page 11). So, the elements of the source range might have any type that is convertible into the element type of the container.
size_type
priority_queue::size
() const
Returns the current number of elements.
To check whether the priority queue is empty (contains no elements), use
empty()because it might be faster.
bool
priority_queue::empty
() const
Returns whether the priority queue is empty (contains no elements).
It is equivalent to priority_queue::
size()==0,but it might be faster.
void priority_queue::push (const
value_type& elem)
Inserts a copy of elem into the priority queue.
const
value_type& priority_queue::top
() const
Returns the next element of the priority queue. The next element is the element that, of all elements in the priority queue, has the maximum value. If more than one element has the maximum value, which element it returns is undefined.
The caller must ensure that the queue contains an element
(size()>0);otherwise, the behavior is undefined.
void priority_queue::pop
()
Removes the next element from the queue. The next element is the element that, of all elements in the priority queue, has the maximum value. If more than one element has the maximum value, which element it removes is undefined.
Note that this function has no return value. To process the next element, you must call
top()first.The caller must ensure that the queue contains an element
(size()>0);otherwise, the behavior is undefined.
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.
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 bitset for 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]) { ... } } } }
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]
The bitset class provides the following 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
()
The default constructor.
Creates a bitset with all bits initialized with zero.
For example:
bitset<50> flags; // flags: 0000...000000 // thus, 50 unset bits
bitset<bits>::bitset (unsigned long
value)
Creates a bitset that is initialized according to the bits of the integral value value.
If the number of bits of value is too small, the leading bit positions are initialized to zero.
For example:
bitset<50> flags (7); // flags: 0000...000111
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)
All forms create a bitset that is initialized by the string str or a substring of str.
The string or substring may contain only the characters
'0'and'1'.str_idx is the index of the first character of str that is used for initialization.
If str_num is missing, all characters from str_idx to the end of str are used.
If the string or substring has fewer characters than necessary, the leading bit positions are initialized to zero.
If the string or substring has more characters than necessary, the remaining characters are ignored.
Throw
out_of_rangeif str_idx > str.size().Throw
invalid_argumentif one of the characters is neither'0'nor'1'.Note that this constructor is a member template (see page 11). For this reason no implicit type conversion from
const char* to stringfor the first parameter is provided.[8]For example:
bitset<50> flags(string("1010101")); // flags: 0000...0001010101 bitset<50> flags(string("1111000"),2,3); // flags: 0000...0000000110
size_t
bitset<bits>::size
() const
Returns the number of bits (thus, bits)
size_t
bitset<bits>::count
() const
Returns the number of set bits (bits with value
1).
bool
bitset<bits>::any
() const
Returns whether any bit is set.
bool
bitset<bits>::none
() const
Returns whether no bit is set.
bool
bitset<bits>::test (size_t
idx) const
Returns whether the bit at position idx is set.
Throws
out_of_rangeif idx >size().
bool
bitset<bits>::operator == (const bitset<bits>& bits) const
Returns whether all bits of *
thisand bits have the same value.
bool
bitset<bits>::operator != (const bitset<bits>& bits) const
Returns whether any bits of *
thisand bits have a different value.
bitset<bits>& bitset<bits>::set()
Sets all bits to
true.Returns the modified bitset.
bitset<bits>& bitset<bits>::set (size_t
idx)
Sets the bit at position idx to
true.Returns the modified bitset.
Throws
out_of_rangeif idx >size().
bitset<bits>& bitset<bits>::set (size_t
idx, int value)
Sets the bit at position idx according to value.
Returns the modified bitset.
value is processed as a Boolean value. If value is equal to 0, the bit is set to
false.Any other value sets the bit totrue.Throws
out_of_rangeif idx >size().
bitset<bits>& bitset<bits>::reset()
Resets all bits to
false(assigns 0 to all bits).Returns the modified bitset.
bitset<bits>& bitset<bits>::reset (size_t
idx)
Resets the bit at position idx to
false.Returns the modified bitset.
Throws
out_of_rangeif idx >size().
bitset<bits>& bitset<bits>::flip
()
Toggles all bits (sets unset bits and vice versa).
Returns the modified bitset.
bitset<bits>& bitset<bits>::flip (size_t
idx)
Toggles the bit at position idx.
Returns the modified bitset.
Throws
out_of_rangeif idx >size().
bitset<bits>& bitset<bits>::operator^= (const bitset<bits>& bits)
The bitwise exclusive-or operator.
Toggles the value of all bits that are set in bits and leaves all other bits unchanged.
Returns the modified bitset.
bitset<bits>& bitset<bits>::operator | = (const bitset<bits>& bits)
The bitwise or operator.
Sets all bits that are set in bits and leaves all other bits unchanged.
Returns the modified bitset.
bitset<bits>& bitset<bits>::operator &= (const bitset<bits>& bits)
The bitwise and operator.
Resets all bits that are not set in bits and leaves all other bits unchanged.
Returns the modified bitset.
bitset<bits>& bitset<bits>::operator <<= (size_t
num)
Shifts all bits by num positions to the left.
Returns the modified bitset.
The last num bits are set to
false.
bitset<bits>& bitset<bits>::operator >>= (size_t
num)
Shifts all bits by num positions to the right.
Returns the modified bitset.
The last num bits are set to
false.
bitset<bits>::reference bitset<bits>::operator [ ] (size_t
idx)
bool
bitset<bits>::operator [ ] (size_t idx) const
Both forms return the bit at position idx
The first form for nonconstant bitsets uses a proxy type to enable the use of the return value as a modifiable value (lvalue). See the next paragraphs for details.
The caller must ensure that idx is a valid index; otherwise, the behavior is undefined.
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:
reference& operator=(bool)Sets the bit according to the passed value.
reference& operator= (constreference&)Sets the bit according to another reference.
reference& flip()Toggles the value of the bit.
operator bool
() constConverts the value into a Boolean value (automatically).
booloperator~() constReturns 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 }
bitset<bits> bitset<bits>::operator ~
() const
Returns a new bitset that has all bits toggled with respect to *
this.
bitset<bits> bitset<bits>::operator << (size_t
num) const
Returns a new bitset that has all bits shifted to the left by num position.
bitset<bits> bitset<bits>::operator >> (size_t
num) const
Returns a new bitset that has all bits shifted to the right by num position.
bitset<bits> operator & (const bitset<bits>& bits1,
const bitset<bits>& bits2)
Returns the bitwise computing of operator and of bits1 and bits2.
Returns a new bitset that has only those bits set in bits1 and in bits2.
bitset<bits> operator | (const bitset<bits>& bits1,
const bitset<bits>& bits2)
Returns the bitwise computing of operator or of bits1 and bits2.
Returns a new bitset that has only those bits set in bits1 and in bits2.
bitset<bits> operator^ (const bitset<bits>& bits1,
const bitset<bits>& bits2)
Returns the bitwise computing of operator exclusive-or of bits1 and bits2.
Returns a new bitset that has only those bits set in bits1 and not set in bits2 or vice versa.
unsigned long
bitset<bits>::to_ulong
() const
Returns the integral value that the bits of the bitset represent.
Throws
overflow_errorif the integral value can't be represented by typeunsigned long.
string
bitset<bits>::to_string
() const
Returns a string that contains the value of the bitset as a binary representation written with characters
'0'for unset bits and'1'for set bits.The order of the characters is equivalent to the order of the bits with descending index.
This function is a template function that is parameterized only by the return type. According to the language rules, you must write the following:
bitset <50> b; ... b.template to_string<char,char_traits<char>,allocator<char> >()
istream& operator>> (istream& strm,
bitset<bits>& bits)
Reads into bits a bitset as a character sequence of characters
'0'and'1'.Reads until any one of the following happens:
At most, bits characters are read.
End-of-file occurs in strm.
The next character is neither
'0'nor'1'.
Returns strm.
If the number of bits read is less than the number of bits in the bitset, the bitset is filled with leading zeros.
If this operator can't read any character, it sets
ios::failbitin strm, which might throw the corresponding exception (see Section 13.4.4,).
ostream& operator << (ostream& strm,
const bitset<bits>& bits)
Writes bits converted into a string that contains the binary representation (thus, as a sequence of
'0'and'1').Uses
to_string()(see page 468) to create the output characters.Returns strm.
See page 462 for an example.
[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:
stack<deque<int> > st;
[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:
queue<deque<string> > buffer;
[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:
priority_queue<vector<float>,less<float> > buffer;
[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("1010101")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.