STL 常用模板

# **$vector$** ## **功能** 动态数组，可实现随时需要随时申请内存。 ## **应用方式** ### **创建（定义）** + ```vector<类型> a;``` 创建容器 + ```vector<类型> a(n);``` 创建初始容量为n,元素初始值为0的容器 + ```vector<类型> a(n, i);``` 创建初始容量为n,元素初始值为i的容器 ### **容量** + ```.size()``` 返回数组大小 + ```.empty()``` 若数组为空则返回 $true$ ，否则返回 $false$ ### **修改** + ```.push_back()``` 向数组尾部添加元素 + ```.pop_back()``` 删除数组末尾元素 + ```.insert()``` 向数组中任意部位插入元素 + ```.erase()``` 删除数组任意位置元素 + ```.swap( , )``` 交换数组任意位置的元素 + ```.clear()``` 清空数组 ### **访问** + ```.begin()``` 头部指针 + ```.end()``` 尾部指针 + ```vec[a]``` 可用下标直接访问 + ```.front()``` 访问第一个元素 + ```.back()``` 访问最后一个元素 ## **示例 $CODE$** ```cpp #include <vector> using namespace std; vector<int> v; //声明部分 int main() { v.push_back(9); v.push_back(7); v.push_back(4); v.push_back(3); v.push_back(2); v.push_back(1); v.push_back(3); //插入元素 if (!v.empty()) //判断是否为空 { v.pop_back(); //3 出 v.pop_back(); //1 出 v.pop_back(); //2 出 } //迭代器的用法 vector<int>::iterator it; for (it = v.begin(); it != v.end(); it++) //遍历元素 printf("%d\n", *it); v.insert(it, 4, 0); //vector 后面会输出 4个0 //插入的位置取决于指针的位置 for (it = v.begin(); it != v.end(); it++) //遍历元素 printf("%d\n", *it); } ``` # **$set$ 和 $multiset$** ## **功能** > $set$ 是 $C++ \ \ STL$ 中提供的容器， $set$ 是数学上的集合——具有唯一性，即每个元素只出现一次，而 $multiset$ 则是可重集，两者的内部实现是一棵**红黑树**，它们支持的函数基本相同。 $set$ 用于判断一个集合内元素的有无。（洛谷日报#7） 简单来说， $set$ 就相当于数学中的集合， $multiset$ 则相当于可重集合，并且可以自动从小到大排序。 ## **应用方式** ### **创建（定义）** ```set<类型> 名称;``` 创建容器 + ```set<int>s;``` + ```set<vector<int> >s;``` vector中提供重载 + ```set<set<int> >s;``` 类似于平衡树嵌套 + ```multiset<double>s;``` + ```cpp struct node { ......; }; set<node> s; bool operator<(const node &a, const node &b) { return a.x > b.x; } ``` 雷同于其他数据类型，为一个结构体的 $set$ 排序，需要重载运算符 ### **容量** + [迭代器](#jump) + ```.size()``` 返回集合大小（元素数量） + ```.empty()``` 集合为空则返回 $true$ ，否则返回 $false$ + ```.count(x)``` 返回集合中值为 $x$ 的元素个数，时间复杂度为 $O ( \log n )$ ### **修改** + ```.clear()``` 清空集合 + ```.insert()``` 插入元素，返回插入地址的迭代器和是否插入成功的 $bool$ 并成的 $pair$ ，时间复杂度为 $O( \log n)$ + ```.erase(参数)``` 删除元素（参数可以是元素或者迭代器），返回下一个元素的迭代器，时间复杂度为 $O( \log n)$ + 在 $multiset$ 中 $s.erase(x)$ 会删除所有值为 $x$ 的元素 ### **访问** + ```.begin()``` 返回集合的头部元素，即只想集合中最小元素的迭代器，时间复杂度为 $O(1)$ + ```.end()``` 返回集合的尾部迭代器 + 由于 $STL$ 中区间都是左闭右开的，则该函数为指向集合中最大元素的下一个位置的迭代器 + 因此， ```--s.end()``` 才是指向集合中最大元素的迭代器 + 时间复杂度为 $O(1)$ + ```.find(x)``` 在集合中查找值为 $x$ 的元素，并返回其迭代器；若不存在，则返回 ```.end()```，时间复杂度为 $O( \log n)$ + ```.lower_bound(x)``` 表示查找 $\ge x$ 的元素中最小的一个，并返回指向该元素的迭代器，时间复杂度为 $O( \log n)$ + ```.upper_bound(x)``` 表示查找 $> x$ 的元素中最小的一个，并返回指向该元素的迭代器，时间复杂度为 $O( \log n)$ ### <span id="jump">迭代器</span> + 双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持 $++$ $--$ 这两个算术操作 + 若把 $it++$，则 $it$ 将会指向“下一个”元素。这里的下一个是指在 $key$ 从小到大排序的结果中，排在 $it$ 下一名的元素。同理，若把 $it--$ ，则 $it$ 会指向排在上一个的元素 + ++ -- 操作的复杂度均为 $O( \log n)$ #### **创建** ```set<类型>::iterator it;``` ```cpp set<int>::iterator it = s.begin(); it++; it--; ``` #### **操作** + ```iterator insert(iterator it,x)``` 在迭代器 $it$ 处插入元素 $x$ + ```iterator erase(iterator it)``` 删除迭代器指针$it$ 处元素 + ```iterator erase(iterator first,iterator last)``` 删除 $[first, last)$ 之间元素 + ```iterator begin()``` 返回首元素的迭代器指针 + ```iterator end()``` 返回尾元素的迭代器指针 + ```reverse_iterator rbegin()``` 返回尾元素的逆向迭代器指针（即最后一个） + ```reverse_iterator rend()``` 返回首元素前一个位置的迭代器指针 #### **遍历 $set$ 及访问其中的元素** ```cpp //set for (set<int>::iterator it = s.begin(); it != s.end(); it++) printf("%d\n",*it); //取出这个迭代器指向的元素 //set嵌套 for (set<set<int>>::iterator it = s.begin(); it != s.end(); it++) { //首先取出set中嵌套的set for (set<int>::iterator rit = (*it).begin(); rit != (*it).end(); rit++) printf("%d ",*rit); //遍历这个set printf("\n"); } ``` # **栈 $stack$** ## **功能** + 一种先进后出的数据结构，只能操作最顶端的元素。 + 栈不允许遍历。  ## **应用方式** ### **创建（定义）** ```stack<类型> 名称``` 构造创建 ### **容量** + ```.size();``` 返回栈的大小 + ```.empty();``` 判断是否为空 ### **修改** + ```.push()``` 入栈（将元素压入栈顶） + ```pop()``` 出栈（将栈顶元素弹出） ### **访问** + ```.top()``` 返回栈顶元素 # **队列 $queue$** ## **功能** + 一种先进先出的数据结构。它有两个出口  + 只允许从一端新增元素，从另一端移除元素。 + 只有队头和队尾允许访问，其余不允许访问。 ## **应用方式** ### **创建** ```queue<类型> 名称``` 构造创建 ### **容量** + ```.size();``` 返回队列的长度 + ```.empty();``` 判断队列是否为空 ### **修改** + ```.push()``` 从队尾入队（将元素压入队尾） + ```.pop()``` 从队首出队（弹出队首元素） ### **访问** + ```.empty();``` 判断队列是否为空 + ```.size();``` 返回队列的长度 # **双端队列 $deque$** ## **功能** + 允许在头部快速插入和删除（就像在尾部一样）的容器。 + 支持随机访问，即支持 $[]$ 以及 $at()$ ，但是性能没有 $vector$ 好。 + 可以在内部进行插入和删除操作，但性能不及 $list$ 。 ## **应用方式** ### **创建（定义）** ```deque<类型> 名称``` 构造创建 + ```Constructors``` 创建一个新双向队列 + ```.assign()``` 设置双向队列的值 ### **基本操作** + ```Operators``` 比较和赋值双向队列 + ```.at()``` 返回指定的元素 + ```.back()``` 返回最后一个元素 + ```.begin()``` 返回指向第一个元素的迭代器 + ```.clear()``` 删除所有元素 + ```.empty()``` 返回真如果双向队列为空 + ```.end()``` 返回指向尾部的迭代器 + ```.erase()``` 删除一个元素 + ```.front()``` 返回第一个元素 + ```.get_allocator()``` 返回双向队列的配置器 + ```.insert()``` 插入一个元素到双向队列中 + ```.max_size()``` 返回双向队列能容纳的最大元素个数 + ```.pop_back()``` 删除尾部的元素 + ```.pop_front()``` 删除头部的元素 + ```.push_back()``` 在尾部加入一个元素 + ```.push_front()``` 在头部加入一个元素 + ```.rbegin()``` 返回指向尾部的逆向迭代器 + ```.rend()``` 返回指向头部的逆向迭代器 + ```.resize()``` 改变双向队列的大小 + ```.size()``` 返回双向队列中元素的个数 + ```.swap()``` 和另一个双向队列交换元素 # **优先队列 $priority \_ queue$** ## **功能** + 元素按照一定优先顺序排列的队列。 + 基础类型默认为大顶堆（即按从大到小的顺序） ## **应用方式** ### **创建（定义）** ```priority_queue<数据类型,容器类型,比较方式> 名称``` 构造创建 + 容器类型必须为数组实现的容器。 + ```priority_queue <int,vector<int>,greater<int> > q;``` 升序队列，小顶堆 + ```priority_queue <int,vector<int>,less<int> >q;``` 降序队列，大顶堆 + ```greater``` 和 ```less``` 是 $std$ 实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个 ```operator()``` ，这个类就有了类似函数的行为，就是一个仿函数类了） ### **容量** + ```.empty()``` 如果优先队列为空，则返回 $true$ ，否则返回 $false$ + ```.size()``` 返回优先队列中的元素个数 ### **修改** + ```.pop()``` 删除队首元素（即删除最值） + ```.push()``` 加入一个元素，自动排序 ### **访问** + ```.top()``` 返回优先队列中有最高优先级的元素 ## **示例 $CODE$** ```cpp #include <iostream> #include <queue> using namespace std; int main() { priority_queue<int, vector<int>, less<int>> q; //使用priority_queue<int> q1;一样 for (int i = 0; i < 10; i++) q1.push(i); while (!q1.empty()) { printf("%d\n",q1.top()); q1.pop(); } return 0; } ``` # **关联容器 映射 $map$ 与 多重映射 $multimap$** ## **功能** + $map$ 是一种**关联式**容器，包含“**关键字/值**”。 + 类似于 $set$ 和 $multiset$，$multimap$ 允许有重复元素，其他与 $map$ 几乎相同 ## **应用方式** ### **创建（定义）** + ```map<string , int >mapstring;``` + ```map<int ,string >mapint;``` + ```map<sring, char>mapstring;``` + ```map<char ,string>mapchar;``` + ```map<char ,int>mapchar;``` + ```map<int ,char >mapint;``` ### **基本操作** + ```.begin()``` 返回指向 $map$ 头部的迭代器 + ```.clear()``` 删除所有元素 + ```.count()``` 返回指定元素出现的次数 + ```.empty()``` 如果 $map$ 为空则返回 $true$ + ```.end()``` 返回指向 $map$ 末尾的迭代器 + ```.equal_range()``` 返回特殊条目的迭代器对 + ```.erase()``` 删除一个元素 + ```.find()``` 查找一个元素 + ```.get_allocator()``` 返回 $map$ 的配置器 + ```.insert()``` 插入元素 + ```.key_comp()``` 返回比较元素 $key$ 的函数 + ```.lower_bound()``` 返回键值 $\ge$ 给定元素的第一个位置 + ```.upper_bound()``` 返回键值 $>$给定元素的第一个位置 + ```.max_size()``` 返回可以容纳的最大元素个数 + ```.rbegin()``` 返回一个指向 $map$ 尾部的逆向迭代器 + ```.rend()``` 返回一个指向 $map$ 头部的逆向迭代器 + ```.size()``` 返回 $map$ 中元素的个数 + ```.swap()``` 交换两个 $map$ + 不是两个元素交换，是两个 $map$ 容器交换 + ```.value_comp()``` 返回比较元素 $value$ 的函数 ## **示例 $CODE$** ```cpp /* 代码来自网络。 */ #include <iostream> #include <map> #include <algorithm> int main(int argc, char *argv[]) { /* define a map */ std::map _map; /* insert */ _map.insert(std::map::value_type(0, 32.8)); _map.insert(std::map::value_type(1, 33.2)); _map.insert(std::map::value_type(2, 35.8)); _map.insert(std::map::value_type(3, 36.4)); _map.insert(std::map::value_type(4, 37.8)); _map.insert(std::map::value_type(5, 35.8)); /* 这个是常用的一种map赋值方法 */ _map[7] = 245.3; /* find by key */ std::map::iterator itr; itr = _map.find(4); if (itr != _map.end()) { std::cout << "Item:" << itr->first << " found, content: " << itr->second << std::endl; } std::cout << std::endl; /* delete item from map */ if (itr != _map.end()) { _map.erase(itr); } /* travel through a map */ std::map::iterator itr1 = _map.begin(); for (; itr1 != _map.end(); ++itr1) { std::cout << "Item:" << itr1->first << ", content: " << itr1->second << std::endl; } std::cout << std::endl; /* empty a map */ _map.clear(); return 0; } ``` # **字符串 $string$** ## **功能** + $STL$ 中对于快速方便处理字符串的一类 + 在定义 $string$ 类对象时，$string$ 类自身可以管理内存 + 可以使用输入输出流方式直接进行输入输出操作，也可以通过文件等手段进行输入输出操作 ## **应用方式** ### **创建（定义）** ```string 名称;``` 直接定义即可 ### **基本操作** + ==、!=、<、<=、>、>=： 比较字典序 + ```.size()/length()``` 返回字符串长度，时间复杂度为 $O(1)$ + ```.insert(pos, string)``` 在 $pos$ 号位置插入字符串 $string$ + ```.insert(it, it1, it2)``` $it$ 为原字符串的欲插入位置， $it2$ 和 $it3$ 为待插字符串的首尾迭代器，即串 $[it2, it3)$ 插在 $it$ 的位置上 + ```.erase(it)``` 删除迭代器 $it$ 处的字符 + ```.erase(first, last)``` 删除迭代器区间 $[first, last)$ 内的元素 + ```.erase(pos, len)```：从 $pos$ 位开始删除 $len$ 个字符 + ```.substr(pos, len)``` 返回 $pos$ 位开始、长度 $len$ 的子串，时间复杂度为 $O(len)$ + ```.find(str2)``` 返回 $str2$ 在 $str$ 第一次出现的位置；如果 $str2$ 不是子串，返回 $string::npos$ 。时间复杂度为 $O(nm)$ （ $n$ 和 $m$ 分别为 $str$ 和 $str2$ 的长度） + ```.find(str2, pos)``` 从 $str$ 的 $pos$ 位开始匹配 $str2$ ，返回值同上 + ```string::npos``` 作为 ```.find()``` 失配时的返回值 + ```.replace(pos, len, str2)``` 把 $str$ 从 $pos$ 位开始、长度为 $len$ 的子串替换为 $str2$ + ```.replace(it1, it2, str2)``` 把 $str$ 的迭代器 $[it1, it2)$ 范围的子串替换为 $str2$ 。时间复杂度为 $O(str.length())$ + ```.clear()``` 清空字符串 # **最后** 奉上作者收藏的[大佬对于**C++标准库和标准模板库**的介绍](https://www.cnblogs.com/jpfss/p/10025771.html) 鸣谢： + [洛谷日报#7](https://www.luogu.com.cn/blog/communist/stl-zheng-li-zhi-set) + [169IT](https://www.169it.com/) + [Cplusplus官网](http://www.cplusplus.com) + [淼润淽涵](https://blog.csdn.net/wcxyky/article/details/88082781) + [星朝](https://www.cnblogs.com/jpfss/p/10025771.html) + [浮生惘语](https://www.cnblogs.com/aerer/p/9931010.html) + 等等 如有侵权，请联系删除。