Skip to content

Container Adapters

Stack

The STL Stack (std::stack) is a Last In, First Out (LIFO) container adapter. It only supports querying or deleting the last inserted element (the top element) and does not support random access. To ensure strict data ordering, it does not support iterators.

Header File

1
#include <stack>

Definition

1
2
3
std::stack<TypeName> s;  // Uses the default underlying container deque, data type is TypeName
std::stack<TypeName, Container> s;  // Uses Container as the underlying container
std::stack<TypeName> s2(s1);        // Constructs s2 by copying s1

Member Functions

All functions below have constant time complexity.

  • top() Accesses the top element of the stack (error if the stack is empty)
  • push(x) Inserts element x into the stack
  • pop() Removes the top element from the stack
  • size() Returns the number of elements in the container
  • empty() Checks whether the container is empty

Simple Example

1
2
3
4
5
6
7
8
9
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 only supports querying or deleting the first inserted element (the front element) and does not support random access. To ensure strict data ordering, it does not support iterators.

Header File

1
#include <queue>

Definition

1
2
3
4
std::queue<TypeName> q;  // Uses the default underlying container deque, data type is TypeName
std::queue<TypeName, Container> q;  // Uses Container as the underlying container

std::queue<TypeName> q2(q1);  // Constructs q2 by copying q1

Member Functions

All functions below have constant time complexity.

  • front() Accesses the front element of the queue (error if the queue is empty)
  • push(x) Inserts element x into the queue
  • pop() Removes the front element from the queue
  • size() Returns the number of elements in the container
  • empty() Checks whether the container is empty

Simple Example

1
2
3
4
5
6
7
8
9
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 type of heap, typically a binary heap.

Header File

1
#include <queue>

Definition

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
std::priority_queue<TypeName> q;             // Data type is TypeName
std::priority_queue<TypeName, Container> q;  // Uses Container as the underlying container
std::priority_queue<TypeName, Container, Compare> q;
// Uses Container as the underlying container and Compare as the comparison type

// By default, uses vector as the underlying container
// Comparison type is less<TypeName> (in this case, top() returns the maximum value)
// If you want top() to return the minimum value, set the comparison type to greater<TypeName>
// Note: You cannot skip Container and directly pass Compare

// Starting from C++11, if using a lambda function to customize Compare,
// it must 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 functions below have constant time complexity.

  • top() Accesses the top element of the heap (the priority queue must not be empty)
  • empty() Checks whether the container is empty
  • size() Returns the number of elements in the container

All functions below have logarithmic time complexity.

  • push(x) Inserts an element and sorts the underlying container
  • pop() Removes the top element of the heap (the priority queue must not be empty)

Simple Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::priority_queue<int> q1;
std::priority_queue<int, std::vector<int>> q2;
// Spaces can be omitted after C++11
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();
// Heap elements: [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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用