关于STL的用法_牛客博客

😎vector 可增长数组

插n个数，申请o(logN)，copy平均o（1）；

申请三法：

    vector<int> a;
    vector<int> b(3);//建3个空间
    vector<int> c(3,4);//建3个空间，每个是4

遍历三法：

    for(int i=0;i<a.size();i++) a[i];//下标遍历
    for(auto i=begin();i!=end();i++) *i;//迭代器遍历
    for(auto x:a) x;//范围遍历

支持比较运算（按字典序）

    vector<int> a(3,4),b(4,3);
    a>b

😎pair<int,int>有序对

first 第一元素 second第二元素

支持比较运算：以first为第一关键字，second为第二关键字

赋值二法

    pair<int,string> p;
    p=make_pair(10,"abc");
    p={20,"abc"};

三个属性

    pair<int,pair<int,string>> p;

😎string

支持加法，直接加在字符串后面

    string a="a";
    a+="bc";
//a现在为“abc”

substr（1（，2））函数——返回指定子串

    cout<<a.substr(1,2);//1为子串起始下标，2为子串长度（可省）如果大于实际长度则有多少返回多少

c_str()——把string按char形式返回

    printf("%s",a.c_str());

😎queue队列
无clear（）函数；

😎priority_queue优先队列

无clear（）；

默认为大根堆

变成小根堆的方法：

1.插入-x，出来时转成x

    priority_queue<int,vector<int>,greater<int>>q;

greater<>里面不可以放结构体

😎deque双端队列

效率慢！！

有clear（）；

push_back() pop_back()

push_front() pop_front()
[ ]支持随机存储

头尾 begin(),end()

😎set集合（不可有重复元素，有后者忽略） multiset（可以存在重复）

set红黑树（平衡二叉树）询问时间复杂度为o（log₂n）

multiset搜索二叉树

set和multiset的唯一“卵用”：求大于（大于或等于）value的前几个元素是什么（lower，upper），频繁插入删除，随时询问

其它用一般用unordered_set看在不在集合里

对于可重复元素用unordered_map检查是否在集合里

erase（x）

———— x是一个数，删除所有x 时间复杂度o（x的个数+logN）

———— x是一个迭代器，删除这个迭代器所指

lower_bound（x）返回大于等于x最小数的迭代器，针对可重复返回最前面

upper_bound（x）返回大于x最小数的迭代器

++后继 --前驱时间复杂度o(logN)

😎map映射 multimap可重复映射

map询问时间复杂度为o（log₂n），询问为o（1）

multimap插入复杂度为o（log₂n），询问为o（1）

insert（x）x为一个pair

erase（x）x为一个pair或者迭代器

[ ]支持随机存储

    map<string,int> m;
    m["abc"]=1;
    cout<<m["abc"]<<endl;//取读操作时间复杂度o（logN）

😎unordered_ 无序的set，multiset，map，multimap等

底层用的是hash

增删改查的时间复杂度为o（1）；

但不支持lower_bound、upper_bound、和迭代器++ -- 等于排序有关的操作

unordered_set<> , unordered_map<>，里面都不可以放结构体，只能放基本类型

对于迭代器，vector和deque，string可相互加减，map，set系列只有++，--

😎bitset压位

每个字节可用8个01——优化bool，使同样空间是bool存储的8倍

支持所有位运算

[ ]支持随机存储

定义：bitset<长度> bi(赋值可有可无——string/char[])

count（）返回有多少个1

any（）是否至少有一个1

none（）是否全是0

set（）把所有位置成1 set（k，v）把k位变成v

reset（）把所有位变成0

flip（）是所有位取反 flip（k）第k位取反