C++ STL介绍

vector

• 定义：变长数组

  vector<typename> name;
  vector<int> name;
  vector<vector<int> >; //二维数组

• 元素访问

  1.和数组一样通过下标索引的方式访问，索引范围[0,vi.size()-1];
  2.通过迭代器访问,类似于指针

  vector<typename>::iterator it;

  然后可以通过*it访问vector里面的元素。

• 常用函数

  1.push_back(x):在vector后面添加一个元素x，时间复杂度O(1)。
  2.pop_back():删除vector尾元素，时间复杂度O(1)。
  3.size():获取元素个数，时间复杂度O(1)。
  4.clear():清空所有元素，时间复杂度O(n)。
  5.insert(it,x):在迭代器it处插入一个元素x,时间复杂度O(n)。
  6.erase(it):删除迭代器it处的元素，时间复杂度O(n)。
  7.erase(first,last):删除[first,last)内的所有元素，时间复杂度O(n)。参数类型为迭代器类型。

set

内部自动有序且不含重复元素的容器

• 定义：

  set<typename> name;

• 元素访问方式

  只能通过迭代器访问

  set<typename>::iterator it;

  *除了vector和string之外的STL容器都不支持(it+i)的访问方式，因此只能按照通过的迭代器访问方式访问。

  • 常用函数

  1.insert(x)：将x插入容器，并自动递增排序和去重，时间复杂度O(logn)。
  2.find(value)：找到值为value的迭代器，时间复杂度O(logn)。
  3.erase(it)：删除单个元素，时间复杂度O(1)。
  4.erase(value)：删除元素的值，时间复杂度O(logn)。
  5.erase(first,last)：删除一个区间(first,last]内的所有元素，时间复杂度为O(first-last)。
  6.size()：获取元素个数，O(1)。
  7.clear()：清空元素。O(n)。

  multiset：不去重
  unordered_set：去重但是不排序

string

string用的比较多，关于定义和访问方式就不在赘述了，直接总结一下常用的函数和字符数组的转化方式。

• string->字符数组

  str.c_str():可以将string类型转化为字符数组

• 字符数组->string

  string(char* a):直接使用强制转换

• insert(int pos,string str):在pos位置插入字符串str

• insert(it,it2,it3)：it为原字符串待插入的位置，it2和it3为待插入字符串首尾迭代器
• erase(it):删除单个元素，it为要删除元素的迭代器。
• erase（first,last):删除[first,last)区间的元素。
• erase(int pos,int length):pos为开始删除元素的起始位置，length为删除个数。
• clear():清空，复杂度O(1)。
• substr(int pos,int len):返回从pos位开始，长度为len的子串。时间复杂度O(len)。
• find(string str2):当str2是str的子串时，返回str2第一次出现的位置；如果不是，则返回string::nops。
• find(string str2,int pos):从pos位开始匹配。
• replace(pos,len,str2):从pos位开始将长度为len的子串替换为str2。
• replace(it1,it2,str2):将[it1,it2)范围内的子串替换成str2。

map

• 定义：

  map<typename1,typename2> mp;

• 访问方式

  迭代器访问：it->first,it->second;

• 常用函数

• find(key):返回键为key的迭代器，时间复杂度O(logn)。

• erase(it):删除单个元素，it为迭代器，时间复杂度O(1)。
• erase(key):删除单个元素，key为键值，时间复杂度O(logn)。
• erase(first,last):删除[first,last)区间内的元素，时间复杂度O(last-first)。
• size()：获取映射对数。时间复杂度O(1)。
• clear()：清空。时间复杂度O(N)。

queue

• 定义：

  queue<typename> name;

• 元素访问

  push()  //入队
  front() //访问队首元素
  back()  //访问队尾元素

• 常用函数

  pop()   //队首元素出队 O(1)
  empty() //判断是否为空
  size()  //返回元素个数

priority_queue

优先队列，底层采用堆来实现。队首元素优先级最高。

• priority_queue元素优先级设置

  对于基本数据类型，一般是大的优先级高，下面两种定义的方式是等价的：

  priority_queue<int> q;
  priority_queue<int,vector<int>,less<int> > q;

  vector参数填写的是承载底层数据结构的容器，第三个参数less,表示数字越大，优先级越高；而greater表示数字越小优先级越高。

• 结构体优先级设置
  重载小于号。

  struct fruit{
  string name;
  int price;
  friend bool operator <(fruit f1,fruit f2)
  	return f1.price<f2.price;
  }

  这样定义之后，价格高的排在队首。如果把小于号改为大于号，则价格低的排在队首。

stack

• 定义：

  stack<typename> name;

• 元素访问及常用函数

  top()  //访问栈顶元素
  push() // 入栈
  pop()  //出栈
  empty() //判断是否为空
  size()  //返回元素个数

pair

头文件#include,map内部实现了pair，在添加map头文件时，也会自动添加utility头文件。

• 定义：

  pair<typename1,typename2> name;
  pair<string,int> p("hello",5) //添加括号直接进行初始化

• 元素的访问

  p.first;
  p.second;

• pair常用函数
  比较操作数：直接用比较符进行比较，比较规则：先以first大小作为标准，当first相等时，然后以second大小作为标准

• 用途

  作为map的键值对插入

  map<string,int> mp;
  mp.insert(make_pair("hello",5));
  mp.insert(pair<string,int>("helllo",5));

algorithm头文件常用函数

• max() min() abs(int a) 最大值 最小值 绝对值
• swap(x,y) 交换x,y的值
• reverse(it,it2) 将[it,it2)之间的元素进行反转
• next_permutation() 给出一个序列在全排列中的下一个序列
• fill() 把数组或者容器内某一段区间赋为某个相同的值，可以是任意的值
  和memset()函数不同，memset只能赋值为0或1
• sort() 排序函数
• lower_bound(first,last,val) 用来寻找数组或者容器中[first,last)范围内第一个大于或等于val的元素，返回指针或迭代器
• upper_bound(first,last,val) 用来寻找数组或者容器中[first,last)范围内第一个大于val的元素，返回指针或迭代器
  如果没有要寻找的元素，则返回可以插入该元素的位置指针或迭代器