STL的使用

STL的使用

STL

vector  //变长数组，倍增的思想
//使用时要尽量减少申请空间的次数

vector<int> a(10,1);//定义一个长度为10，每个数都是1的vector
vector<int> a;
    a.size()   //返回元素个数
    a.empty()  //返回是否为空
    a.clear()  //清空
    a.front()/back()
    a.push_back()/pop_back()
    begin()/end() //迭代器，begin是第0个数，end是最后一个数的后面一个数
    [] //支持这种类似数组的访问方法
    //vector支持比较运算，按字典序
for(int i=0;i<10;i++)a.push_back(i);

for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
for(auto i=a.begin();i!=a.end();i++)cout<<*i<<" ";
for(auto x:a)cout<<x;
//三种遍历方式


//二分
lower_bound (起始地址，结束地址，要查找的数值) //返回的是 第一个大于等于待查找数值 出现的位置（迭代器）。
upper_bound (起始地址，结束地址，要查找的数值) //返回的是 第一个大于待查找数值 出现的位置（迭代器）。
binary_search (起始地址，结束地址，要查找的数值)  //返回的是是否存在这么一个数，是一个bool值。


pair<int, int> p;
    first   //第一个元素
    second  //第二个元素
    //两个元素类型可以不一样 
    //支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
    p=make_pair(1,10);
	p={1,10};//两种不同的初始化方式
	pair<int,pair<int,int>>  //嵌套实现处理三个不同的

        
string //字符串
    size()/length()  //返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  //返回子串
    c_str()  //返回字符串所在字符数组的起始地址
    //支持 + == > < 等运算

        
queue  //队列
    size()
    empty()
    push()   //向队尾插入一个元素
    front()  //返回队头元素
    back()   //返回队尾元素
    pop()    //弹出队头元素

        
priority_queue   //优先队列，默认是大根堆
    size()
    empty()
    push()  //插入一个元素
    top()   //返回堆顶元素
    pop()   //弹出堆顶元素
    //定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

        
stack    //栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()   返回栈顶元素
    pop()   弹出栈顶元素

        
deque  //双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

        
set, map, multiset, multimap  //基于平衡二叉树（红黑树），动态维护有序序列
//set中没有重复元素,multiset有重复元素
    size()
    empty()
    clear()
    begin()/end()
    ++, -- //返回前驱和后继，时间复杂度 O(logn)
set/multiset:
    insert();//插入一个数
	find(); //查找一个数
	count();//返回某一个数的个数
	erase();//如果输入一个数x，删除所有x； 如果输入一个迭代器，删除这个迭代器
map/multimap:
	insert();//插入的数是一个pair（映射）
	erase(); //输入的参数是pair 或 迭代器
	[]  //可以像数组一样访问，但是时间复杂度是O(logn)


unordered_set, unordered_map, unordered_multiset, unordered_multimap // 哈希表
    //和上面类似，增删改查的时间复杂度是 O(1)
    //不支持 lower_bound()/upper_bound()， 迭代器的++，--

        
bitset   //压位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()   //返回有多少个1

    any()     //判断是否至少有一个1
    none()    //判断是否全为0

    set()     //把所有位置成1
    set(k, v) //将第k位变成v
    reset()   //把所有位变成0
    flip()    //等价于~
    flip(k)   //把第k位取反