Container Adapters

Stack

The STL stack (std::stack) is a last-in, first-out (LIFO) container adapter. It supports only querying or deleting the last element added (the top element), does not support random access, and does not support iterators in order to guarantee strict data ordering.

Header

#include <stack>

Definition

std::stack<TypeName> s;  // Use the default underlying container deque, with element type TypeName
std::stack<TypeName, Container> s;  // Use Container as the underlying container
std::stack<TypeName> s2(s1);        // Copy s1 to construct s2

Member functions

All of the following functions have constant complexity

• top() access the top element (this causes an error if the stack is empty)
• push(x) insert element x into the stack
• pop() delete the top element
• size() query the number of elements in the container
• empty() check whether the container is empty

Simple example

std::stack<int> s1;
s1.push(2);
s1.push(1);
std::stack<int> s2(s1);
s1.pop();
std::cout << s1.size() << " " << s2.size() << std::endl;  // 1 2
std::cout << s1.top() << " " << s2.top() << std::endl;    // 2 1
s1.pop();
std::cout << s1.empty() << " " << s2.empty() << std::endl;  // 1 0

Queue

The STL queue (std::queue) is a first-in, first-out (FIFO) container adapter. It supports only querying or deleting the first element added (the front element), does not support random access, and does not support iterators in order to guarantee strict data ordering.

Header

#include <queue>

Definition

std::queue<TypeName> q;  // Use the default underlying container deque, with element type TypeName
std::queue<TypeName, Container> q;  // Use Container as the underlying container

std::queue<TypeName> q2(q1);  // Copy q1 to construct q2

Member functions

All of the following functions have constant complexity

• front() access the front element (this causes an error if the queue is empty)
• push(x) insert element x into the queue
• pop() delete the front element
• size() query the number of elements in the container
• empty() check whether the container is empty

Simple example

std::queue<int> q1;
q1.push(2);
q1.push(1);
std::queue<int> q2(q1);
q1.pop();
std::cout << q1.size() << " " << q2.size() << std::endl;    // 1 2
std::cout << q1.front() << " " << q2.front() << std::endl;  // 1 2
q1.pop();
std::cout << q1.empty() << " " << q2.empty() << std::endl;  // 1 0

Priority queue

The priority queue std::priority_queue is a heap, generally a binary heap.

Header

#include <queue>

Definition

std::priority_queue<TypeName> q;             // Element type is TypeName
std::priority_queue<TypeName, Container> q;  // Use Container as the underlying container
std::priority_queue<TypeName, Container, Compare> q;
// Use Container as the underlying container and Compare as the comparison type

// The default underlying container is vector
// The comparison type is less<TypeName> (in this case, top() returns the maximum value)
// To make top() return the minimum value, set the comparison type to greater<TypeName>
// Note: Container cannot be skipped when passing Compare directly

// Starting from C++11, if a lambda function is used to customize Compare,
// it needs to be passed as a constructor argument, for example:
auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) {
  return l.second < r.second;
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                    decltype(cmp)>
    pq(cmp);

Member functions

All of the following functions have constant complexity

• top() access the top element (the priority queue must not be empty)
• empty() check whether the container is empty
• size() query the number of elements in the container

All of the following functions have logarithmic complexity

• push(x) insert an element and sort the underlying container
• pop() delete the top element (the priority queue must not be empty)

Simple example

std::priority_queue<int> q1;
std::priority_queue<int, std::vector<int>> q2;
// After C++11, the space can be omitted
std::priority_queue<int, std::deque<int>, std::greater<int>> q3;
// q3 is a min-heap
for (int i = 1; i <= 5; i++) q1.push(i);
// Elements in q1:  [1, 2, 3, 4, 5]
std::cout << q1.top() << std::endl;
// Output: 5
q1.pop();
// Elements in the heap: [1, 2, 3, 4]
std::cout << q1.size() << std::endl;
// Output: 4
for (int i = 1; i <= 5; i++) q3.push(i);
// Elements in q3:  [1, 2, 3, 4, 5]
std::cout << q3.top() << std::endl;
// Output: 1