#STL
STL是标准模板库
常分为容器、算法、迭代器
容器和算法通过迭代器无缝连接
六大组件
容器、算法、迭代器、仿函数、适配器(配接器)、空间适配器
容器：用来存放数据，有各种数据结构vector、list、deque、set、map
算法：各种算法，比方sort
迭代器：容器算法 set.md 沟通桥梁
仿函数：行为类似函数，协助算法完成策略
适配器(配接器)：修饰容器
空间适配器：空间的配置和管理
容器、算法、迭代器
容器:存放数据，分为：
-
序列式容器：强调值的排序，容器内每个值都有固定的顺序
即按照输入的顺序进行排列
-
关联式容器：二叉树结构，各元素之间没有物理上的顺序
输入时进行排序
算法:有序的步骤内解决逻辑或者数学问题，分为
-
质变算法：运算时会改变区间内元素的位置，例如拷贝、删除、替换
-
非质变算法：运算时不会改变原来区间内的元素，例如查找、遍历、寻找最大最小值
**迭代器：**是算法和容器沟通的桥梁，每种容器都有自己对应的迭代器，有点类似指针
-
种类
种类 功能 输入迭代器 只能读取数据 输出迭代器 只能写入数据 前向迭代器 能读写数据，向前推进迭代器 双向迭代器 能读写数据，向前向后推进迭代器 随机访问迭代器 读写数据，可任意访问数据，最强迭代器
栈（stack）
先进后出
后进先出
栈不允许有遍历的行为，只有栈顶的元素才可以被访问
栈可以判断是否为空以及大小
构造
| 方式 | 说明 |
|---|---|
stack<type> 变量 | 默认构造 |
数据存取
| 方式 | 说明 |
|---|---|
st.push(value) | 入栈 |
st.pop() | 出栈，不会返回任何值 |
st.top() | 返回栈顶元素 |
大小
| 方式 | 说明 |
|---|---|
st.size() | 返回栈的大小 |
st.empty() | 栈是否为空 |
set
所有元素在插入时被自动排序，属于关联式容器
set容器分为set和multiset
multi(多)
区别
set不允许有重复元素
multiset允许重复元素
用法
| 形式 | 用途 |
|---|---|
set类型变量=set类型变量 | 赋值 |
变量.insert(数据/变量) | 插入 |
变量.size() | 查看长度 |
变量.swap(变量1) | 互换 |
变量.clear() | 清空 |
变量.erase(值) | 删除元素 |
变量.find() | 此时为指针(迭代器) |
变量.count | 若为set，结果只有0或1 |
构造和赋值
####构造
-
set<类型> 变量默认构造 -
set(set型变量)拷贝构造-
拷贝构造示例
vector<int>a{1,4,6,657,8,48,58}; set<int>st(a.begin(),a.end());
-
赋值
set类型变量=set类型变量
插入数据
变量.insert(数据/变量)
遍历输出
#####1.方法1
#include <bits/stdc++.h>
using namespace std;
int main()
{
set<int> st;
st.insert(10);
st.insert(20);
st.insert(30);
st.insert(40);
int q = 50;
st.insert(q);
for (auto c : st)
cout << c << endl;
return 0;
}
2.方法2
使用迭代器进行访问
#include<bits/stdc++.h>
int main()
{
set<int>st;
//插入数据
for(set<int>::iterator i=st.begin();i<st.end();i++)
cout<<*i;
return 0;
}
查看长度
变量.size()
容器互换
变量.swap(变量1)
交换变量和变量1的值
清空所有元素
变量.clear()
删除某个元素
变量.erase(值)
查找元素
变量.find()此时为指针(迭代器)
惯用法
set<int>a;
//插入元素
set<int>::iterator i=a.find(变量);
if(i!=a.end())
找到元素
统计元素的个数
int 变量1=变量.count(数据)
当变量为set是数据的个数只有0或者1个，因为不允许插入重复元素
当变量为multiset时，才能真正起作用
multiset输出方式与set一致，使用迭代器遍历输出时也一样
判断set元素是否插入成功
pair<set<int>::iterator,bool> temp =变量.insert(变量/值)；
如果插入成功，则temp.second的值为true，发否则为false
对组pair
- 功能：成对出现的数据，可以用来返回两个数据
- 创建方式**
pair<type,type>p(v1,v2)pair<type,type>p=make_pair(v1.v2)
调用
pair<string,int>p("name",99);//第一种定义方式
cout<<p.first<<p.second;
pair<string,int>p=make_pair("name",99);//第二种定义方式
first指向第一个类型的数据，second指向第二个
queue队列
先进先出，first in first out
队头只能出数据，队尾只能入队
只有队头和队尾才能被外界使用，因此队列不允许有遍历行为
| 操作 | 说明 |
|---|---|
q.size() | 队列大小 |
q.empty() | 队列是否为空 |
queue<type>q | 创建 |
q.push(element) | 入队 |
q.pop() | 出队 |
q.front() | 返回队头元素 |
q.back() | 返回队尾元素 |
map
map也被称为键值对，也分为map和multimap，与set类似
定义/初始化
map<type,type>v;
第一个type通常称为键(key)值，第二个为值(value)，两者成对出现
插入值也可以用pair
v.insert(pair<int,int>(1,2))
输出
输出需要迭代器
使用方法：
map<int,int>m;
//插入
for(map<int,int>i=m.begin();i!=m.end();i++)
{
cout<<i->first<<(*i).second;//链表输出形式
}
基本操作
| 形式 | 说明 |
|---|---|
| m.empty() | 检查m是否为空 |
| m.swap(m2) | 交换m,m2 |
| m.erase(值) | 删除key为3的值,只按key删val不会删 |
| m.erase(begin,end) | 删除区间内的值[) |
| m.clear() | 清空整个容器 |
插入
插入时可用对组pair插入
方法1v.insert(pair<int,int>(1,2))
方法2v.insert(make_pair(1,2))
方法3v[键值]=值
map<int,int>m;
//插入
m[99]=98;
cout<<m[99];//输出结果为98
//若m[90]不存在，使用cout输出时结果为0，但再次使用迭代器进行遍历输出时，会将90,0添加到m中
当key值存在时，使用insert进行插入时不会生效
当key值存在时，执行m[存在的值]=值时会直接替换
map的统计和查找
| 形式 | 作用 |
|---|---|
| m.find(key值) | 查找键值为key的是否存在，不存在则为end() |
| m.count(key值) | 若为map,值为0或1，multimap可存在多个，返回值为整形 |
map的默认排序规则是按照key从小到大的顺序排列
map与pair搭配时
map<pair<int,int>,int>a;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
a.insert(make_pair((make_pair(i,j)),j));
//或者
a[make_pair(i,j)]=j;
}
}
List 链表
将数据进行链式存储
方法
| 方法 | 含义 |
|---|---|
list<int>l | 默认构造 |
l.push_back(value) | 尾插 |
l.assign(begin,end) | 区间复制 |
swap(l1,l2) | 交换链表 |
l.assign(n,element) | 复制n个element到l |
l.resize(num) | 指定大小 |
l.size() | 返回长度 |
l.empty() | 是否为空 |
l.pop_back() | 删除最后的 |
l.pop_front() | 删除最前面的 |
l.push_front(element) | 头插 |
l.insert(pos,n,element) | pos位置插入n个元素，n可省略，省略后代表插入一个 |
l.clear() | 清除所有元素 |
l.erase(begin,end) | 清除[begin,end]之间的元素，如果省略end，代表删除begin位置的元素 |
l.remove(value) | 清除与value的值匹配的元素 |
l.front() | 返回最开头的元素 |
l.back() | 返回末尾元素 |
Q.E.D.
