《算法笔记》第六章

vector

vector是向量，可以理解成“变长数组”，使用前需要添加下列语句

1
2
#include <vector>
using namespace std;

定义

1
2
3
vector<typename> name;//单独定义
vector<typename> Arrayname[arraySize];//定义数组，相当于二元数组，这样定义的一维长度是固定的
vector<vector<int> > name;//定义二维数组，二维均是变长的

访问

1
name[index]//下标访问

函数

1
2
3
4
5
6
7
8
9
push_back(i);//在vi后面添加i
pop_back();//删除末尾元素
size()//获取vector个数
clear();//清空vector
begin()//首元素地址
end()//尾元素的下一个地址
insert(it,x);//在it处添加元素x
erase(it);//删除it处的元素
erase(first.last);//删除[first,last)的所有元素

迭代器

可以理解成指针

1
vector <typename>::iterator it=vi.begin();//定义迭代器it指向首元素地址，此时*it就代表了vi的首元素

set

set是集合，自动递增排序，元素互不重复，使用前需要添加头文件

可以用来去重并升序排序

1
2
#include <set>
using namespace std;

定义

1
2
set <typename> name;//单独定义
set<typename> Arrayname[arraySize];//定义数组，数组中每一个都是set容器

访问

set只能用迭代器访问

1
set<typename>::iterator it;//可以通过*it访问，但不能用*(it+i)

函数

1
2
3
4
5
6
insert(x);//插入x
find(value);//返回值为value的迭代器
erase(it);//删除迭代器为it的元素
erase(value);//删除值为value的元素
erase(first,last);//删除[first,last)区间的元素
clear();//清空所有元素

string

字符串，使用前需添加头文件

字符串可以直接通过加法拼接，直接比较大小（字典序）

1
2
#include <string>
using  namespace std;

定义

string str="abc";

访问

str[i]

输入输出只能用cin和cout

迭代器

1
string::iterator it;

string迭代器支持直接加减某个数字

函数

1
2
3
4
5
6
7
8
9
10
11
length()//返回str的长度，即存放的字符数
insert(pos,string);//在pos的位置插入字符串string
insert(it,it2,it3);//在it的位置插入字符串[it2,it3)
erase(it);//删除迭代器为it的元素
erase(first,last);//删除[first,last)区间的元素
erase(pos,length)://删除从pos开始的length个字符
clear();//清空字符串
substr(pos,len)//返回从pos开始长度为len的子串
find(str2)//若str2为子串，返回第一次出现的位置，如果不是，返回string::npos
replace(pos,len,str2);//把从pos开始长度为len的子串替换为str2
replace(it1,it2,str2);//把[it1,it2)替换为str2

map

map可以将基本类型映射到基本类型，基本类型也可以是STL容器，使用前需添加头文件

可以用来建立字符（串）与整数之间的联系，判断大整数或者其他类型是否存在的题目，把map当bool数组用

1
2
#include <map>
using namespace std;

定义

如果是字符串到整数的映射必须使用string而不是char

1
map<typename1,typename2> mp;

访问

1
mp[type1]//相当于mp[type2]

迭代器

1
2
3
map<typename1，typename2>::iterator it;
it ->first//当前映射的键
it ->second//当前映射的值

函数

1
2
3
4
5
6
find(key)//返回键为key的迭代器
erase(it);//删除迭代器为it的元素
erase(key);//删除键为key的元素
erase(first,last);//删除迭代器为[first,last)的元素
size()//映射的对数
clear();//清空

queue

队列，使用前需添加头文件

1
2
#include <queue>
using namespace std;

定义

1
queue <typename> name;

访问

使用front和back之前要先用empty判断一下队列是否为空

1
2
front()//队首元素
back()//队尾元素

函数

1
2
3
4
push(x);//将x入队
pop();//令首元素出列
empty()//检测queue是否为空，返回true则空，返回false则空
size()//队列元素个数

priority_queue

优先队列

定义

先添加和queue一样的头文件

1
2
3
#include <queue>
using namespace std;
priority_queue<typename>name;

访问

1
top()//访问优先级最高的元素

函数

1
2
3
4
push(x);//将x入队
pop();//令队首元素出队
empty()//检测queue是否为空，返回true则空，返回false则非空
size()//队列元素个数

优先级

基本数据类型

一般是数字大的优先级高，定义如下

1
2
priority_queue<int> q;
priority_queue<int,vector<int>,less<int>> q;//两者等价

想让数字小的优先级大只需

1
priority_queue<int,vector<int>,greater<int>> q;

结构体类型

在结构体里面重载小于号即可

1
2
3
4
5
6
7
struct fruit{
  string name;
  int price;
  friend bool operator < (fruit f1,fruit f2){
    return f1.price < f2.price;//把小于号改成大于号就反一下
  }
};

这样之后f1<f2就等价于f1.price<f2.price

再定义fruit类型的优先队列，内部就是以价格高的水果为优先级高

也可以把重载函数写在结构体外面

1
2
3
4
5
6
struct cmp{
  bool operator () (fruit f1, fruit f2){
    return f1.price>f2.price;
  }
}
priority_queue<fruit, vector<fruit>, cmp> q;//定义

stack

栈，后进先出的容器，使用前需加上头文件

1
2
3
#include <stack>
using namespace std;
stack<typename> name;//定义

访问

1
top()//访问栈顶元素

函数

1
2
3
4
push(x);//将x入栈
pop();//弹出栈顶元素
empty()//返回true则空，返回false则非空
size()//返回元素个数

pair

把两个元素绑在一起作为一个合成元素，可以看成有两个元素的结构体

定义

1
2
3
#include <utility>//添加map头文件后会自动添加utility
using namespace std;
pair<typename1,typename2> name(value1,value2);//value为初始化元素

访问

++
1
2
pair.first//访问第一个元素
pair.second//访问第二个元素

比较

两个pair类型比较是先比较first再比较second

algorithm

使用前需添加头文件

1
2
3
4
5
6
7
8
9
10
11
#include <algorithm>
using namespace std;
max(x,y)//返回较大值
min(x.y)//返回较小值
abs(x)//返回绝对值
swap(x,y);//交换x,y的值
reverse(it,it2);//将[it,it2)的元素进行反转
next_permutation(序列);//给出一个序列在全排列中的下一个序列
fill(区间,值);//把某段区间赋为相同的某个值
lower_bound(first,last,val)//寻找在[first,last)范围内第一个值大于等于val的位置，如果是数组则返回指针，如果是容器则返回迭代器，如果没有要寻找的元素则返回可以插入该元素的指针或迭代器
upper_bound(first,last,val)//寻找在[first,last)范围内第一个值大于等于val的位置，如果是数组则返回指针，如果是容器则返回迭代器，如果没有要寻找的元素则返回可以插入该元素的指针或迭代器

sort

1
sort(首元素地址，尾元素地址，比较函数（非必填）)；;//默认从小到大排序

如果需要从大到小，则需要使用比较函数

1
2
3
bool bmp(int a,int b){
  return a>b;//当a大于b时把a放在b前面，即降序
}

STL容器中，只有vector，string，deque可以用sort