4.4.1 Container Adaptors

Stack. A stack can be instantiated either with a vector, a list or a deque. The member functions empty, size, top, push and pop are accessible to the user.

stack<vector<int> > s1;
stack<list<int> >   s2;
stack<deque<int> >  s3;

s1.push(1); s1.push(5);
cout << s1.top() << endl;
s1.pop();
cout << s1.size() << endl;
s1.empty()? cout << "empty" : cout << "not empty";

Output: 5

Output: 1

Output: not empty

top returns the element on the top of the stack, pop removes the top element from the stack. For comparison of two stacks, operator== and operator< are defined.

Queue. A queue can be instantiated with a list or a deque.

queue<list<int> >  q1;
queue<deque<int> > q2;

Its public member functions are empty, size, front, back, push and pop. front returns the next element from the queue, pop removes this element. back returns the last element pushed to the queue with push. As with the stack, two queues can be compared using operator== and operator<.

Priority queue. A priority queue can be instantiated with a vector or a deque. A priority queue holds the elements added by push sorted by using a function object comp of type Compare.

// use less as compare object
priority_queue<vector<int>, less<int> > pq1;		

// use greater as compare object
priority_queue<deque<int>, greater<int> > pq2;	

vector v(3, 1);
// create a priority_queue out of a vector, use less as compare object
priority_queue<deque<int>, less<int> > pq3 (v.begin(), v.end() );	

top returns the element with the highest priority, pop removes this element. The element with the highest priority is determined by the sorting order imposed by comp. Note, that a priority queue internally is implemented using a heap. So, when less is used as compare object, the element with the highest priority h will be one of the elements for which the following condition holds: less (h, x) == false for all elements x in the priority queue.

Additionally, the member functions empty and size are provided. Note that no comparison operators for priority queues are provided. For the implementations of the container adaptors, read [2], 11.1.

Continue with section 4.4.2

Back to index