供自己用的 记录算法基础课的stl笔记

vector 变长数组，倍增的思想

size()  返回元素个数
empty()返回是否为空
clear()清空
front()/back()//返回第一个数，返回最后一个数字
push_back()/pop_back()在最后面加一个数/删除最后的一个数
begin()/end()
vector支持随机寻址

pair< int , int >p;

p.first是第一个元素
p.second是第二个元素

string 字符串

substr()
c_str()
size()/length()
empty()
clear()

queue,队列[kjuː]

size()
empty()
push()向队尾插入一个元素
front()返回队头元素
back()返回队尾元素
pop()弹出队头元素
//queue，priority_queue，stack是没有clear函数的
//如果想清空一个q可以
//q=queue<int>();

priority_queue 优先队列

//默认大根堆
//用堆实现的
push()插入一个元素
top()返回堆顶元素
pop()弹出堆顶元素
//定义小根堆的方法
priority_queue<int,vector<int>,greater<int>>heap;

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,基于平衡二叉树(红黑树),动态维护有序序列

size()
empty()
clear()
begin()/end() ++,--  返回前驱和后继 前驱指前面一个数 后继指后面一个数 O(logn)

set/multiset
    insert()插入一个数
    find()查找一个数 ，如果查不到 返回end()迭代器
    count()返回某一个数的个数
    //set里只有0/1的情况
    //multiset可以有多个
    erase()
       (1)输入是一个数x，删除所有x ，复杂度O(k+logn) (k是x的个数)
       (2）输入一个迭代器，删除这个迭代器
    set最核心的部分
    lower_bound()/upper_bound()
        lower_bound()返回大于等于x的最小的数的迭代器
         upper_bound返回大于x的最小的数的迭代器
map/multimap
    insert()//插入的数是一个pair
    erase()//输入的参数是pair或者迭代器
    find()
    //map最nb的部分hh
    []   时间复杂度是O(logn)
    //用法见下面的代码
    lower_bound()/upper_bound()

unordered_set,unordered_map,unordered_multiset,unordered_multimap、哈希表

和上面类似，好处是增删查改的时间复杂度为O(1)(上面的几个的为O(logn)
但缺点是不支持 lower_bound()/upper_bound()
也不支持迭代器的++,--

bitset，压位

/*c++里的bool是一个字节
比如开一个1024个大小的bool数组
需要1024字节
但是如果用bitset按位存只需要128字节 省八倍空间*/
bitset<1000>S;//<>里是元素个数
~,&,|,^
<<, >>
[]//支持取出来某一位是0/1
count()返回有多少个1
any()判断是否至少有一个1
more()判断是否全为0
set()把所有位置成1
set(k,v)将第k位变成v
reset()把所有位变成0
flip()等价于~
flip(k)把第k位取反

vector

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace st;
int main(){
    vecotr<int> a(10,-3);//初始化十个-3；
    vector<int>a(10);//初始化数组大小为10
    vector<int>a[10];//vector数组
    a.size();//时间复杂度为O(1)
    a.empty();
    for(int i=0;i<10;i++)a.push_back(i);
    for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
    cout<<endl;
    for(vector<int>::iterator i=a.begin();i!=a.end();i++)cout<<*i<<' ';//迭代器可以看成指针
    //也可以写成 for(auto i=a.begin();i!=a.end();i++)
    //a.begin()是a[0]
    //a.end()是a[size]
    cout<<endl;
    for(auto x:a)cout<<x<<' ';//范围遍历 效率略快，代码略短
    vector<int>a(4,3),b(3,4);
    if(a<b)puts("a<b");//vector支持比较运算，字典序比较
    /*
    系统为某一程序分配空间时，所需要的时间，基本上与空间大小无关，与申请次数有关，减少申请空间的次数
最开始分配个32的空间，一个一个往里插元素，当元素超过32时，再申请64个空间大小再把原来32个数字copy过来。申请空间的次数为logn ，再加一个数的复杂度为O(1)
*/
}

pair< int, int>

pair<int ,string>p;
p.first是第一个元素
p.second是第二个元素
//构造pair时可以使用make_pair(10,"yxc");
p={20,"anc"};//c++11支持这种写法
pair<int,pair<int,int>>//此种写法可以存储三元组

string

string a="yxc";
a+="def";
a+='c';
cout<<a<<endl;
/*substr有两个参数，第一个参数是子串的起始位置(串从0开始)，第二个参数是子串的长度。
*/
cout<<a.substr()<<endl;
printf("%s\n",a.c+str());//如果想用printf输出string 那么可以用c_str()

priority_queue

priority_queue<int>heap;
heap.push(-x);//可以实现小根堆hh
//定义小根堆的方法
priority_queue<int,vector<int>,greater<int>>heap;

set multiset

set<int>S;//不能有重复元素 ，如果插入一个重复元素就会被忽略掉
multiset<int>MS;//可以有重复元素

map/multimap

map<string,int> a;
a["yxc"]=1;
cout<<a["yxc"]<<endl;
//输出结果为1