C++的STL

This is my study note of C++.

vector

代码	含义
c.front()	返回第一个数据 O (1)
c.back()	返回最后一个数据 O (1)
c.pop_back()	删除最后一个数据 O(1)
c.push_back(element)	在尾部加一个数据 O(1)
c.size()	返回实际数据个数（unsigned类型） O(1)
c.clear()	清除元素个数 O(N),N为元素个数
c.resize(n,v)	改变数组大小为n,n个空间数值赋为v，如果没有默认赋值为0
c.insert(it,x)	向任意迭代器it插入一个元素x O(N)
例：c.insert(c.begin()+2,-1)	将-1插入c[2]的位置
c.erase(first,last)	删除[first,last)的所有元素
c.begin()	返回首元素的迭代器（通俗来说就是地址）
c.end()	返回最后一个元素后一个位置的迭代器（地址）
c.empty()	判断是否为空，为空返回真，反之返回假

迭代器法，类似指针一样的访问

vector<int>::iterator it = vi.beigin();
for(it = vi.begin(); it != vi.end(); it++)
{
    cout<<*it<<endl;
}

栈只能对栈顶元素进行操作，先入后出。

一种先进先出结构。

代码	含义
front()	返回队首元素 O(1)
back()	返回队尾元素 O(1)
push()	尾部添加一个元素副本进队O(1)
pop()	删除第一个元素出队 O(1)
size()	返回队列中元素个数，返回值类型unsigned int O(1)
empty()	判断是否为空，队列为空，返回true O(1)

首尾都可插入和删除的队列。

代码	含义
push_back(x)/push_front(x)	把x压入后/前端
back()/front()	访问(不删除)后/前端元素
pop_back() pop_front()	删除后/前端元素
erase(iterator it)	删除双端队列中的某一个元素
erase(iterator first,iterator last)	删除双端队列中[first,last）中的元素
empty()	判断deque是否空
size()	返回deque的元素数量
clear()	清空deque

在正常队列的基础上加上了优先级，保证队首每次都是优先级最大的。

1	priority_queue<数据类型, vector<数据类型>， less<int>> pq;

类似python的字典，一个键对应一个值。

代码	含义
mp.find(key)	返回键为key的映射的迭代器 O(logN) 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end()
mp.erase(it)	删除迭代器对应的键和值O(1)
mp.erase(key)	根据映射的键删除键和值 O(logN)
mp.erase(first,last)	删除左闭右开区间迭代器对应的键和值 O(last-first)
mp.size()	返回映射的对数 O(1)
mp.clear()	清空map中的所有元素 O(N)
mp.insert()	插入元素，插入时要构造键值对
mp.empty()	如果map为空，返回true，否则返回false
mp.begin()	返回指向map第一个元素的迭代器（地址）
mp.end()	返回指向map尾部的迭代器（最后一个元素的下一个地址）
mp.rbegin()	返回指向map最后一个元素的反向迭代器（地址）
mp.rend()	返回指向map第一个元素前面(上一个）的反向迭代器（地址）
mp.count(key)	查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0
mp.lower_bound()	返回一个迭代器，指向键值>= key的第一个元素
mp.upper_bound()	返回一个迭代器，指向键值> key的第一个元素

set中的元素不会重复，并自动从小到达排序。

代码	含义
s.begin()	返回set容器的第一个元素的地址（迭代器）
s.end()	返回set容器的最后一个元素的下一个地址（迭代器）
s.rbegin()	返回逆序迭代器，指向容器元素最后一个位置
s.rend()	返回逆序迭代器，指向容器第一个元素前面的位置
s.clear()	删除set容器中的所有的元素,返回unsigned int类型O(N)
s.empty()	判断set容器是否为空
s.insert()	插入一个元素
s.size()	返回当前set容器中的元素个数O(1)
erase(iterator)	删除定位器iterator指向的值
erase(first,second）	删除定位器first和second之间的值
erase(key_value)	删除键值key_value的值
s.find(元素)	查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器
s.lower_bound(k)	返回大于等于k的第一个元素的迭代器
s.upper_bound(k)	返回大于k的第一个元素的迭代器

只能包含两个元素，可以看作是两个元素的结构体。
pair<int, string> p(1, “pair”);

bitset 在 bitset 头文件中，它类似数组，并且每一个元素只能是０或１，每个元素只用１bit空间。