C++ STL 速查表

---

---

这份 C++ STL 速查表涵盖了从基本的 STL（例如 向量、哈希映射、集合等）到高级概念（例如函数对象、迭代器等）的广泛主题。它专为希望快速阅读关键概念以及语法和相关示例的程序员而设计。

介绍

标准模板库 (STL) 是一个 C++ 库，包含所有 类 和 函数 模板。它用于实现基本的数据结构（例如 哈希集、堆、列表等）和函数（例如数学、算法等），并包含 C++ 编程语言中所有可用的容器。

STL 的组成部分

标准模板库包含多个容器和函数，可以按以下方式分类：

• 容器
• 函数对象
• 算法
• 迭代器

STL 容器

STL 容器模板类包含诸如动态数组（或向量、列表）、哈希映射、哈希集、树、链表等数据结构。这些用于存储和对数据执行操作。

容器模板具有以下组成部分：

• 顺序容器
• 容器适配器
• 关联容器
• 无序容器

每个容器都有其各自的头文件，可以在程序开始时包含。例如，std::vector 包含在 #include<vector> 库中。

顺序容器

顺序容器实现具有顺序访问的数据结构。这些包括：

• 向量
• 列表
• 双端队列
• 数组
• 前向列表

容器适配器

容器适配器通过为顺序容器提供不同的接口来实现队列、堆栈等数据结构。这些包括：

• 堆栈
• 队列
• 优先队列

关联容器

关联容器用于存储有序数据，可以使用其键值快速搜索。这些包括：

• 集合
• 多重集合
• 映射
• 多重映射

无序容器

无序容器类似于关联容器，但唯一的区别是它们不存储排序数据。尽管如此，这些容器仍使用键值对提供快速的搜索时间。它们是：

• 无序集合
• 无序多重集合
• 无序映射
• 无序多重映射

现在我们已经建立了所有容器的学习图，我们将简要解释 STL 中每个容器以及示例代码：

STL 中的向量

向量在运行时初始化为动态数组，其大小是可变的。它可以在 C++ <vector> 头文件中找到。

语法

vector<data_type> vec1; //1D vector
vector<vector<data_type>> vec2; //2D vector
vector<container_type<data_type>> vec3; //2D vector of other container
vector<data_type> vec1(n); //vector of size n
vector<data_type> vec1(n,k); // vector of size n, with each element=k

向量模板中有多个函数。这些函数在下面的表格中简要解释：

此处，时间复杂度表示向量模板的不同成员函数的时间复杂度。有关时间复杂度的更多信息，请访问本文：时间复杂度。

示例

// C++ program to illustrate the vector container
#include <iostream>
#include <vector>
using namespace std;

int main(){
   int n=2;
   vector<int> vec1 = { 1, 2, 3, 4, 5 };
   vector<int> vec2(n,0);

   vector<vector<int>> vec3(n,vector<int>(2*n,1));

   vec1.push_back(6);

   cout << "vec1: ";
   for (int i = 0; i < vec1.size(); i++) {
      cout << vec1[i] << " ";
   }
   cout << endl<<"vec2: ";
   for (int i = 0; i < vec2.size(); i++) {
      cout << vec2[i] << " ";
   }
   cout << endl;

   vec1.erase(vec1.begin() + 4);

   cout << "vec1 after erasing: ";
   for (auto i = vec1.begin(); i != vec1.end(); i++) {
      cout << *i << " ";
   }
   cout << endl;

   cout << "vec3:-" << endl;
   for (auto i : vec3) {
      for (auto j : i) {
         cout << j << " ";
      }
      cout << endl;
   }
   cout << endl;

   vector<pair<int,int>> vec4;
   vec4.push_back({2,3});
   vec4.push_back({4,3});

   cout<<"vector of pairs, vec4 : "<<endl;
   for(auto i: vec4){
      cout<<i.first<<" "<<i.second<<endl;
   }
   return 0;
}

输出

vec1: 1 2 3 4 5 6 
vec2: 0 0 
vec1 after erasing: 1 2 3 4 6 
vec3:-
1 1 1 1 
1 1 1 1 

vector of pairs, vec4 : 
2 3
4 3

STL 中的列表

列表容器初始化为双向链表，而对于实现单向链表，我们使用前向列表。它可以在 C++ <list> 头文件中找到。

语法

list<data_type> list1;

列表模板中有多个函数。这些函数在下面的表格中简要解释：

示例

#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main(){
   list<int> list1 = { 1, 5, 9, 1, 4, 6 };

   cout << "List1 first and last element: " << list1.front() <<" "<<list1.back()<<endl;

   // adding element
   list1.insert(list1.begin(), 5);

   // deleting element
   list1.erase(list1.begin());

   // traversing list1
   cout << "list1: ";
   for (auto i = list1.begin(); i != list1.end(); i++) {
      cout << *i << " ";
   }
   cout << endl;

   return 0;
}

输出

List1 first and last element: 1 6
list1: 1 5 9 1 4 6 

STL 中的双端队列

双端队列容器初始化为双端队列，可以在队列的两端推送和弹出元素。它可以在 C++ <deque> 头文件中找到。

语法

deque<data_type> dq1;

双端队列模板中有多个函数。这些函数在下面的表格中简要解释：

示例

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

int main(){

   deque<int> dq = { 1, 2, 3, 4, 5 ,6, 8 };
   cout<<"Initial Deque: "<<endl;
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;
   dq.push_front(dq.back());
   dq.pop_back();
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;

   dq.push_front(dq.back());
   dq.pop_back();
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;

   dq.pop_back();
   dq.pop_front();
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;

   dq.push_front(11);
   dq.push_back(99);

   for (auto i : dq) {
      cout << i << " ";
   }

   return 0;
}

输出

Initial Deque: 
1 2 3 4 5 6 8 
8 1 2 3 4 5 6 
6 8 1 2 3 4 5 
8 1 2 3 4 
11 8 1 2 3 4 99 

STL 中的堆栈

堆栈容器初始化为后进先出 (LIFO) 容器，可以在顶部推送元素，并从顶部弹出元素。因此，最后一个进入的元素是第一个从容器中退出的元素。它可以在 C++ <stack> 头文件中找到。

语法

stack<data_type> s1;

堆栈模板中有多个函数。这些函数在下面的表格中简要解释：

示例

// C++ Program to illustrate the stack
#include <bits/stdc++.h>
using namespace std;

int main(){
   stack<int> s;

   s.push(2);
   s.push(9);
   s.push(3);
   s.push(1);
   s.push(6);

   cout << "Top is: " << s.top() << endl;

   while (!s.empty()) {
      cout<<"size is: "<<s.size()<<" ";
      cout << "element is: "<<s.top() << endl;
      s.pop();
   }
   return 0;
}

输出

Top is: 6
size is: 5 element is: 6
size is: 4 element is: 1
size is: 3 element is: 3
size is: 2 element is: 9
size is: 1 element is: 2

STL中的队列

队列容器初始化为一个先进先出(FIFO)容器，元素可以从队尾压入，从队首弹出。因此，第一个进入的元素也是第一个离开容器的元素。它可以在C++的``头文件中找到。

语法

queue<data_type> q1;

在队列模板中，有不同的函数。这些函数在下面的表格中简要解释：

示例

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

int main(){
   queue<int> q;
   q.push(1);
   q.push(1);
   q.push(6);
   q.push(1);

   cout << "Front element: " << q.front() << endl;
   cout << "Back element: " << q.back() << endl;

   cout << "q: ";
   int size = q.size();

   for (int i = 0; i < size; i++) {
      cout << q.front() << " ";
      q.pop();
   }

   return 0;
}

输出

Front element: 1
Back element: 1
q: 1 1 6 1 

STL中的哈希集合/集合

集合容器初始化为唯一元素存储的数据结构，它也实现了排序（升序和降序）。它通常使用红黑树作为底层数据结构。它可以在C++的``头文件中找到。

语法

set<data_type> set;
set<data_type, greater<data_type>> set2; //this is a set in descending order
set<data_type, comparator/lambda_function> set3; //this is a set in custom order

在集合模板中，有不同的函数。这些函数在下面的表格中简要解释：

示例

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main(){
   set<int> set;
   set.insert(9);
   set.insert(11);
   set.insert(9);
   set.insert(11);

   bool flag=set.find(9)!=set.end();

   cout<<"Is there a 9 in the set? "<<flag<<endl;

   set.insert(21);

   for (auto i : set) {
      cout << i << " ";
   }
   cout << endl;
   return 0;
}

输出

Is there a 9 in the set? 1
9 11 21

STL中的哈希映射/映射

映射是一个容器，它以键值对的形式存储数据，并按键的升序排序，每个键都是唯一的。它使用红黑树数据结构实现。它包含在`

语法

map<key_type,value_type> map;

在映射模板中，有不同的函数。这些函数在下面的表格中简要解释：

示例

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

int main(){
   map<char,int> map;
   string s="abbacdbbac";
   for(char c: s){
      map[c]++;
   }

   for(auto it:map){
      cout<<it.first<<" : "<<it.second<<endl;
   }
   cout<<"after erasing element 'c' : "<<endl;
   map.erase('c');
   for(auto it:map){
      cout<<it.first<<" : "<<it.second<<endl;
   }
   return 0;
}

输出

a : 3
b : 4
c : 2
d : 1
after erasing element 'c' : 
a : 3
b : 4
d : 1

STL中的无序集合

无序集合容器存储唯一的数据值，但与集合的区别在于数据没有按照任何顺序存储。它使用``头文件实现。

语法

unordered_set<data_type> set;

在无序集合模板中，有不同的函数。这些函数在下面的表格中简要解释：

示例

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main(){
   unordered_set<int> set;
   set.insert(19);
   set.insert(10);
   set.insert(13);
   set.insert(21);

   bool flag=set.find(9)!=set.end();

   cout<<"Is there a 9 in the set? "<<flag<<endl;

   set.insert(21);

   for (auto i : set) {
      cout << i << " ";
   }
   cout << endl;
   return 0;
}

输出

Is there a 9 in the set? 0
21 13 10 19 

STL中的无序映射

在无序映射容器中，数据存储方式与映射容器类似，但存储数据的顺序是随机的，因此不遵循升序或降序。它包含在``头文件中。

语法

unordered_map<key_type, value_type> map;

在无序映射模板中，有不同的函数。这些函数在下面的表格中简要解释：

示例

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

int main(){
   unordered_map<char,int> map;
   string s="abbacdbbac";
   for(char c: s){
      map[c]++;
   }

   for(auto it:map){
      cout<<it.first<<" : "<<it.second<<endl;
   }
   cout<<"after erasing element 'c' : "<<endl;
   map.erase('c');
   for(auto it:map){
      cout<<it.first<<" : "<<it.second<<endl;
   }
   return 0;
}

输出

d : 1
c : 2
b : 4
a : 3
after erasing element 'c' : 
d : 1
b : 4
a : 3

C++ STL中的仿函数

函数对象或仿函数是C++ STL中的对象，其行为类似于方法/函数。这些包含在``头文件中。这些需要重载()圆括号运算符。

C++ STL中的主要仿函数如下：

• equal_to
• not_equal_to
• greater
• less
• plus
• minus

成员函数

非成员函数

运算符类

示例

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

int main(){
   equal_to<int> obj1;
   not_equal_to<int> obj2;
   greater<int> obj3;
   less<int> obj4;
   plus<int> obj5;
   minus<int> obj6;

   cout << "Functors and their usage: \n";
   cout << "Are these equal? " << obj1(11, 22) << endl;
   cout << "Are these different? " << obj2(11, 22) << endl;
   cout << "Is first index greater than second? " << obj3(10, 20) << endl;
   cout << "Is first index smaller than second? " << obj4(10, 2) << endl;
   cout << "After adding: " << obj5(10, 20) << endl;
   cout << "After subtracting: " << obj6(10, 8) << endl;

   return 0;
}

输出

Functors and their usage: 
Are these equal? 0
Are these different? 1
Is first index greater than second? 0
Is first index smaller than second? 0
After adding: 30
After subtracting: 2

C++ STL中的算法

在C++ STL中，算法模板为用户提供了各种操作，这些操作对于实现关键算法至关重要，例如搜索、排序、从容器中返回最大/最小值等等。可以使用``头文件访问这些算法。

C++中的``库提供了许多有用的函数。下面给出一些最常用的函数：

• Sort（排序）
• Copy（复制）
• Find（查找）
• Max Element（最大元素）和Min Element（最小元素）
• For Each（遍历）
• Swap（交换）

C++中的sort()

sort()算法用于按升序、降序或自定义顺序（使用比较器或lambda函数）对给定数据进行排序。

语法

sort(start_iterator,end_iterator)
sort(start,end, comparator_function) //for custom sorting

示例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(){
   vector<int> v = {999, 1252, 3117, 122222 , 10, 88, 2, 9, 45, 82, 546, 42, 221 , -1};
   cout<<"Ascending order: ";
   sort(v.begin(),v.end());
   for(int i:v) cout<<i<<" ";
      cout<<endl;

   cout<<"Descending order: ";
   sort(v.begin(),v.end(),greater<int>());
   for(int i:v) cout<<i<<" ";
      cout<<endl;
   return 0;
}

输出

Ascending order: -1 2 9 10 42 45 82 88 221 546 999 1252 3117 122222 
Descending order: 122222 3117 1252 999 546 221 88 82 45 42 10 9 2 -1 

C++中的copy()

copy()算法用于将元素从一个容器复制到另一个容器。

语法

copy(start_iterator,end_iterator, destination_operator)

示例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(){
   vector<int> v = { 1, 2, 3, 4, 5 , 4 ,3 , 2, 1};
   vector<int> newvec(9);
   copy(v.begin(), v.end(), newvec.begin());

   for(int &i:newvec) cout<<i<<" ";
   cout<<endl;
   return 0;
}

输出

1 2 3 4 5 4 3 2 1 

C++中的find()

find()算法用于在给定元素范围内查找关键元素。

语法

find (firstIterator, lastIterator, value);

示例

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(){
   vector<int> v= { 1,3,5,2,3,1,55,41};

   // finding 5
   auto itr = find(v.begin(), v.end(), 55);
   if (itr != v.end()) {
      cout << *itr << " Element found !!!" << endl;
   }else {
      cout << "Element not present !!!" << endl;
   }

   return 0;
}

输出

55 Element found !!!

C++中的max_element()和min_element()

max_element()和min_element()用于在给定元素范围内查找最大值和最小值。

语法

max_element (firstIterator, lastIterator);
min_element (firstIterator, lastIterator);

示例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(){
   vector<int> v = {999, 1252, 3117, 122222 , 10, 88, 2, 9, 45, 82, 546, 42, 221 , -1};

   cout << "Maximum Element: " << *max_element(v.begin(),v.end())<<endl;
   cout<<"Minimum Element: "<<*min_element(v.begin(),v.end()) <<"\n";
   return 0;
}

输出

Maximum Element: 122222
Minimum Element: -1

C++中的for_each()

for_each()算法用于对容器中的一系列元素应用给定的操作或指令。

语法

for_each (firstIterator, lastIterator, unaryFunction);

示例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(){
   vector<int> vec1 = { 1, 2, 3, 4, 5 };

   for_each(vec1.begin(), vec1.end(), [](int& i){
      i++;
   });

   for(int i:vec1) cout<<i<<" ";
      cout<<endl;

   return 0;
}

输出

2 3 4 5 6 

C++中的swap()

swap()算法用于就地将一个元素替换为另一个元素，因此元素交换位置。

语法

swap(container1,container2)

示例

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {

   vector<int> vec1 = {1, 2, 3};
   vector<int> vec2 = {4, 5, 6};

   swap(vec1,vec2);
   cout<<"vec 1: "<<endl;
   for(int i:vec1) cout<<i<<" ";
      cout<<endl;

   cout<<"vec 2: "<<endl;
   for(int i:vec2) cout<<i<<" ";
      cout<<endl;
   return 0;
}

输出

vec 1: 
4 5 6 
vec 2: 1 2 3 

C++ STL中的迭代器

迭代器可以被认为是用于顺序迭代容器的指针。这些迭代器在C++中使用``头文件包含。

每个容器都有自己的迭代器。为了避免混淆，在遍历容器时，可以使用`auto`关键字定义迭代器。

迭代器有五种类型：

• 输入迭代器
• 输出迭代器
• 前向迭代器
• 双向迭代器
• 随机迭代器

示例

#include <bits/stdc++.h>
using namespace std;

int main(){
   vector<int> myvec={1,5,2,4,3,6,6,9,8};
   set<int>set(myvec.begin(),myvec.end());

   for(auto itr:myvec) cout<<itr<<" ";
      cout<<endl;
   for(auto itr:set) cout<<itr<<" ";
      cout<<endl;

   return 0;
}

输出

1 5 2 4 3 6 6 9 8 
1 2 3 4 5 6 8 9