『ACM-XCPC | Data Structure』STL

太多了呜呜呜就分块啦(叉腰

Posted by GJ on July 25, 2020

<list>链表:插入删除操作为O(1),不能使用[]访问

<vector>可变长度数组

一般数  
front a.front(); 返回a的第一个元素
back a.back(); 返回a的最后一个元素
  a.size(); 返回a中元素的个数;
a.max_size() vector最大可以为多大
a.end() 得到数组的最后一个单元+1的指针
a.rbegin() 将vector反转后的开始指针返回(其实就是原来的end-1)
a.rend() 将vector反转后的结束指针返回(其实就是i原来的begin+1)
成员函数  
assign a.assign(b.begin(), b.begin()+3); b为向量,将b的0~2个元素构成的向量赋给a
a.assign(4,2);是a只含4个元素,且每个元素为2
push_back a.push_back(5); 在a的最后一个向量后插入一个元素,其值为5 O(n)
pop_back a.pop_back(); 删除a向量的最后一个元素 O(n)
insert a.insert(a.begin()+1,5); 在a的第1个元素(从第0个算起)的位置插入数值5,如a为1,2,3,4,插入元素后为1,5,2,3,4
a.insert(a.begin()+1,3,5); 在a的第1个元素(从第0个算起)的位置插入3个数,其值都为5 a.insert(a.begin()+1,b+3,b+6); b为数组,在a的第1个元素(从第0个算起)的位置插入b的第3个元素到第5个元素(不包括b+6),如b为1,2,3,4,5,9,8,插入元素后为1,4,5,9,2,3,4,5,9,8
erase a.erase(a.begin()+1,a.begin()+3); 删除a中第1个(从第0个算起)到第2个元素,也就是说删除的元素从a.begin()+1算起(包括它)一直到a.begin()+3(不包括它)
swap a.swap(b); b为向量,将a中的元素和b中的元素进行整体性交换
clear a.clear(); 清空a中的元素,大小变为0
empty a.empty(); 判断a是否为空,空则返回ture,不空则返回false
resize a.resize(10); 将a的现有元素个数调至10个,多则删,少则补,其值随机
a.resize(10,2); 将a的现有元素个数调至10个,多则删,少则补,其值为2
capacity a.capacity(); 返回a在内存中总共可以容纳的元素个数
reserve a.reserve(100);将a的容量(capacity)扩充至100,也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才显得有意义,因为这将避免内存多次容量扩充操作(当a的容量不足时电脑会自动扩容,当然这必然降低性能)
  a==b; b为向量,向量的比较操作还有!=,>=,<=,>,<

<stack>栈

成员函数  
q.push(a) 入队。将一个元素a置入队列q中
q.pop() 出队。从队列q中移除第一个元素 //并不返回该元素
q.top() 返回队列q内的第一个元素(也就是第一个被置入的元素)
q.empty() 判断队列q是否为空,当队列q为空时,返回ture;否则返回false
q.size() 访问队列q中的元素个数。

单调栈

  • 复杂度:O(n)

  • 应用
    • 对于某个元素i:
    • 左边区间第一个比它小的数,第一个比它大的数
    • 确定这个元素是否是区间最值
    • 右边区间第一个大于它的值
    • 到 右边区间第一个大于它的值 的距离
    • 确定以该元素为最值的最长区间
  • 代码

    //在“尾部”添加元素
    while (r != 0 || ms[r] <= x) r--;
    ms[++r] = x;
      
    //查询栈顶元素
    if (r != 0) printf("%d\n", ms[r]);
    else printf("-1");
    

<queue>队列

成员函数  
q.push(a) 入队。将一个元素a置入队列q中
q.pop() 出队。从队列q中移除第一个元素 //并不返回该元素
q.front() 返回队列q内的第一个元素(也就是第一个被置入的元素)
q.back() 返回队列q中最后一个元素(也就是最后被插入的元素)
q.empty() 判断队列q是否为空,当队列q为空时,返回ture;否则返回false
q.size() 访问队列q中的元素个数。

<priority_queue>优先队列

  • 升序队列:priority_queue <int,vector<int>,greater<int> > q;

    降序队列:priority_queue <int,vector<int>,less<int> >q;

  • 插入元素的复杂度:O(logn),删除元素的复杂度:O(1)

成员函数  
q.push(a) 入队。将一个元素a置入队列q中
q.pop() 出队。从队列q中移除第一个元素 //并不返回该元素
q.top() 返回队列q内的第一个元素(也就是第一个被置入的元素)
q.back() 返回队列q中最后一个元素(也就是最后被插入的元素)
q.empty() 判断队列q是否为空,当队列q为空时,返回ture;否则返回false
q.size() 访问队列q中的元素个数。
create() 创建一个空的优先队列
size() 返回队列中的元素数目
max() 返回具有最大优先权的元素
insert(x) 将x插入队列
deleteMax(x) 从队列中删除具有最大优先权的元素,并将该元素返回至x

<deque>双端队列

构造函数  
deque<elem>c 创建一个空的deque
deque<elem>c1(c2) 复制一个deque
deque<elem>c(n) 创建一个deque,含n个数据
deque<elem>c(n,elem) 创建一个含有n个elem拷贝的deque
deque<elem>c(beg,end) 创建一个以[beg;end)区间的deque
~deque<elem>() 销毁所有数据,释放内存
成员函数  
c.begin() 返回第一个元素的迭代器
c.end() 返回指向最后一个元素下一个位置的迭代器
c.rbegin() 返回指向反向队列的第一个元素的迭代器
c.rend() 返回指向反向队列的最后一个元素的下一个位置
c.assign(n,num) 将n个num拷贝复制到容器c
c.assign(beg,end) 将[beg,end)区间的数据拷贝复制到容器c
c.at(pos) 返回索引为pos的位置的元素,会执行边界检查,如果越界抛出out_of_range异常
c.operator[] 下标运算符重载
c.empty() 判断c容器是否为空
c.front() 返回c容器的第一个元素
c.back() 返回c容器的最后一个元素
c.size() 返回c容器中实际拥有的元素个数
c.max_size() 返回c容器可能存放元素的最大数量
c.clear() 清除c容器中拥有的所有元素
c.insert(pos,num) 在pos位置插入元素num
c.insert(pos,n,num) 在pos位置插入n个元素num
c.insert(pos,beg,end) 在pos位置插入区间为[beg,end)的元素
c.erase(pos) 删除pos位置的元素
c.erase(beg,end) 删除区间为[beg,end)的元素
c.push_back(num) 在末尾位置插入元素
c.pop_back() 删除末尾位置的元素
c.push_front(num) 在开头位置插入元素
c.pop_front() 删除开头位置的元素
c.resize(num) 重新定义容器大小
c1.swap(c2) 交换容器c1,c2
swap(c1,c2) 交换容器c1,c2

单调队列

  • 复杂度:O(n)
  • 应用

    • 可以查询区间最值(不能维护区间k大,因为队列中很有可能没有k个元素)
    • 优化DP
  • 单调队列一般是用于优化动态规划方面问题的一种特殊数据结构,且多数情况是与定长连续子区间问题相关联。

  • 代码:

    //在“尾部”添加元素x
    while (l != r && mq[r] <= x) r--;
    mq[++r] = x;
      
    //查询队首元素
    if (l != r) printf("%d\n", mq[l+1]);
    else printf("-1\n");
      
    //弹出队首元素
    if (l != r) l++;
    

<set>集合

  • 每次访问复杂度O(logN)
成员函数  
begin() 返回指向第一个元素的迭代器
end() 返回指向最后一个元素的迭代器
clear() 删除set容器中的所有的元素
empty() 判断set容器是否为空
insert(x) 往set容器中插入x
max_size() 返回set容器包含的元素最大个数
size() 返回当前set容器中的元素个数
erase(it) 删除迭代器指针it处元素
count(a) 查找set中某个元素出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了。
find(a) 查找set中某个元素出现的位置。如果找到,就返回这个元素的迭代器,如果这个元素不存在,则返回 s.end() 。 (最后一个元素的下一个位置,s为set的变量名)
equal_range() 返回集合中与给定值相等的上下限的两个迭代器
get_allocator() 返回集合的分配器
lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器
key_comp() 返回一个用于元素间值比较的函数
rbegin() 返回指向集合中第一个元素的反向迭代器
swap() 交换两个集合变量
upper_bound() 返回大于某个元素的迭代器
value_comp() 返回一个用于比较元素间的值的函数

<multiset>多重集合

<map>映射

  • 每次访问复杂度O(logN)
  • 红黑树//对数据自动排序

<unordered_map>多重映射

  • 每次访问复杂度O(1)
  • 哈希表存储

<string>字符串

成员函数  
assign() 用于赋予新值,assign函数用于将一个字符串的部分内容赋值给另一个string对象
swap() 交换两个字符串的内容
+=、append()、push_back() 在字符串尾部追加内容,”+=”可追加string对象,字符以及C风格字符串,append函数则可以追加string对象和C风格字符串,push_back函数则只能追加字符
insert() 用于插入字符串
erase() 用于删除字符
clear()、~string() clear()删除str的全部字符,后者销毁所有字符,释放内存
size()、length() 返回字符串的字符数
empty() 判断字符串是否为空

其他

运算符重载

struct node{
    string name;
    double score;
    bool operator < (const node &a) const{ // 重载“<”操作符,自定义排序规则   
        return a.score < score;//按score由大到小排序。如果要由小到大排序,使用“>”即可。
    }
};