本篇博文应该归类于Cpp语言部分,但是我太懒了,不想去找图片,添加一些东西emmm

vector:动态数组,倍增思想

定义:

   包含于头文件 #include <vector>
   定义一个数组:vector<Type>v:Type是数据类型
   vector<int>v[N]
   固定的一维是N,第二维是动态的

常用操作:

   v.push_back(i):在尾部增加元素
   v.size():元素个数
   v.empty():判断是否位空。空返回ture,非空返回false
   v.insert(v.begin()+i,k):在第i个元素前面插入k
   v.insert(v.end(),10,5):尾部插入10个值为5的元素
   v.pop_back(i):删除尾部元素
   v.erase(v.begin()+i,v.begin()+j):删除区间[i,j)的元素
   v.erase(v.begin()+2):删除第三个元素
   v.clear():清空数组
   v.resize(n):数组大小变为n
   reverse(v.begin(),v.end()):翻转数组
   sort(v.begin(),v.end()):从小到大排序
   []
   支持比较运算,按字典序

pair

定义:

   pair<Type,type> P,Type是数据类型

常用操作:

   P.first:取第一个元素
   P.second:取第二个元素

string:字符串

定义:

   string s;

常用操作:

   s = "";清空操作
   getline(cin,s):输入含有空格的字符串
   s.size()/s.length():返回字符串长度
   s.empty():判断是否为空
   s.clear():清空
   substr(起始下标,(子串长度)):返回子串,若省略子串长度,返回起始下标到字符串结束
   s_str():返回字符串所在字符数组的起始地址

stack:先进后出

定义:

   包含于头文件 #include <stack>
   定义一个栈 stack<Type> s,Type是数据类型

常用操作

   s.push(i):把i加入栈顶
   s.top():返回栈顶元素
   s.pop():弹出栈顶元素
   s.size():返回栈中的元素个数
   s.empty():判断栈是否为空,空返回true,非空返回false

queue:先进先出

定义:

    包含于头文件 #include <queue>
    定义一个队列 queue<Type> q,Type是数据类型

常用操作:

   q.push(i):把i放进队列
   q.front():返回队首元素
   q.pop():删除队首元素
   q.back():返回队尾元素
   q.size():返回元素个数
   q.empty():判断队列是否为空,空返回true,非空返回false

deque:双端队列

定义:

   包含于头文件 #include <deque>
   deque<Type> D;

常用操作:

   D.size():返回元素个数
   D.empty():判断是否为空
   D.clear():清空
   D.front():返回第一个元素
   D.back():返回最后一个元素
   D.push_back(i):在尾部插入i
   D.pop_back():队尾弹出最后一个数
   D.push_front(i):队首插入一个数i
   D.pop_front():队首弹出一个数
   D.begin():迭代器开始
   D.end():迭代器结束
   []:随机选取

priority_queue:优先级高的先出队。

定义:

   包含于头文件 #include <queue>
   定义一个优先队列 priority_queue<Type> p,Type是数据类型

常用操作:

   p.top():返回具有优先级高的元素值
   p.pop():删除最高优先级的元素
   p.push(i):插入新元素
   定义成小根堆:priority_queue<Type,vector<Type>,greater<Type>> Q;
   priority_queue<Type> heap; heap.push(-x);
   无clear()函数

list:存储空间不连续,双向链表

定义:

   vector:插入和删除操作少,随机访问元素频繁
   list:插入和删除频繁,随机访问少
   list<Type>L,Type是数据类型

常用操作

   L.push_back(i):赋值
   L.erase(i):删除i

set:集合中的元素是排好序并且只出现一次

定义:

   访问元素的时间复杂度O(logn)
   set<Type> s,Type是数据类型

常用操作 set/multiset(允许重复元素)

   s.insert(i):把i放进集合s
   s.erase(i):删除元素i
   (1):输入一个数i,删除所以i,O(k+logn),k为i的个数
   (2):输入一个迭代器,删除这个迭代器
   s.clear():清空集合s
   s.empty():判断是否为空,空返回true,非空返回false
   s.size():返回元素个数
   s.find(k):查找k,若没找到返回end(),找到返回指向k的迭代器
   s.lower_bound(k):返回一个迭代器,指向键值不小于k的第一个元素
   s.upper_bound():返回一个迭代器,指向键值大于k的第一个元素

map:关联容器,查找的时间复杂度O(logn)

定义:

   map<string,int> mp,存储string类型和int类型,第一个是key,第二个是value
   赋值:mp["Tom"] = 15

常用操作:map/multimap

   insert():插入的数是pair类型
   find():查找一个数,不存在返回迭代器end()
   count():返回某一个数的个数。
   erase():
   (1):输入一个数i,删除所以i,O(k+logn),k为i的个数
   (2):输入一个迭代器,删除这个迭代器
   []:multimap不支持此操作,O(logn)
   lower_bound(k):返回一个迭代器,指向键值不小于k的第一个元素
   upper_bound():返回一个迭代器,指向键值大于k的第一个元素

set,map,multiset,multimap:基于平衡二叉树,动态维护有序序列

都支持的操作:

   size():O(1)
   empty():O(1)
   clear()
   begin()/end()
   ++,--:返回前驱和后继,O(logn)
undered_set,undered_map,undered_multiset,undered_multimap,哈希表
和上面类似,增删改查的时间复杂度是O(1)
不支持 lower_bound()/upper_bound(),迭代器++,--

bitset:压位 1kb=1024b

定义:

   bitset<10000> s:定义长度为1万的bitset,10000b

常用操作:

   ~,&,|,^
   >>,<<
   ==,!=
   []:取某一位
   count():返回多少个1
   any():判断是否至少有一个1
   none():判断是否全为0
   set():把所有位置成1
   set(k,v):将第k位置成v
   reset():把所以位变成0
   flip():等价于~
   flip(k):把第k位按位取反

一个爱折腾且喜欢研究算法的大学生