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
#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; -
struct node { ......; }; set<node> s; bool operator<(const node &a, const node &b) { return a.x > b.x; }雷同于其他数据类型，为一个结构体的 \(set\) 排序，需要重载运算符
容量
-
.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)\)
迭代器
-
双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持 \(++\) \(--\) 这两个算术操作
-
若把 \(it++\)，则 \(it\) 将会指向“下一个”元素。这里的下一个是指在 \(key\) 从小到大排序的结果中，排在 \(it\) 下一名的元素。同理，若把 \(it--\) ，则 \(it\) 会指向排在上一个的元素
-
++ -- 操作的复杂度均为 \(O( \log n)\)
创建
set<类型>::iterator it;
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 及访问其中的元素
//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
#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
/*
代码来自网络。
*/
#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++标准库和标准模板库的介绍
鸣谢：
如有侵权，请联系删除。