C++ STL使用技巧

vector：变长数组，数组长度是可以动态变化的，倍增的思想

string：字符串，常用函数：substr()：返回某一个子串、c_str()：返回这个 string 对应字符数组的头指针

queue：队列，常用函数：push()：往队尾插入一个元素、front()：返回队头元素、back()：返回队尾元素、pop()：把队头弹出

priority_queue：优先队列，其实是一个堆，常用函数：push()：往堆中插入一个元素、top()：返回堆顶、pop()：把堆顶弹出

stack：栈，常用函数：push()：向栈顶插入一个元素、top()：返回栈顶元素、pop()：弹出栈顶元素

deque：双端队列，队头队尾都可以插入删除，而且可以支持随机访问，相当于一个加强版的 vector

set、map、multiset、multimap：都是基于平衡二叉树(红黑树)来实现的，本质上是动态维护一个有序序列

unordered_set、(无序)unordered_map、unordered_multiset、unordered_multimap：基于哈希表来实现的

bitset：压位 状态压缩

vector

c++ STL容器 --- 动态数组vector_小雪菜本菜的博客-CSDN博客

size() 和 empty() 所有容器都有，时间复杂度是 O( 1 )

vector是自动变长的，操作系统有一个很大的特点，当系统为某一个程序 / 某一个进程分配空间的时候，有一个很大的特点：它所需的时间基本上与空间大小无关，与申请次数有关

让操作系统为我们分配一个长度是 100 的数组和让操作系统为我们分配一个长度是 1 的数组，所需要的时间基本上是一样的，所需时间只与请求次数有关，一次直接申请一个长度是 1 k 的数组和申请1 k 个长度是1 的数组，可能需要的时间就是 1 k 倍的区别

因此在申请空间的时候，变长数组要尽量减少申请空间的次数，但是可以浪费空间，是一个倍增的思想

最一开始给它分配一个长度不大的空间，一个个往数组里面插入元素，当元素个数大于 32 / 数组长度不够的时候，就把数组长度乘以 2(再申请一个长度是 64 的空间)，然后把之前的元素重新 copy 到长度是 64 的数组里面

假设要申请一个长度是 n = 10^6 的数组，一共会 copy 多少次呢？

数组长度最一开始是 1，第一次 copy 一个数，第二次 copy 两个数，第 3次 copy 四个数. . .以此类推

额外 copy 的数的次数大概就是 10^6，所以总共额外 copy 的时间均摊下来就是 O( 1 )

每次往 vector 中加入一个数，可以看成平均情况下，每插入一个数的时间复杂度是 O( 1 )

长度是 n，申请空间的次数是 O( logn )，额外 copy 的次数均摊下来大概是 O( 1 )，申请次数不多，效率高，而且额外的操作也不多
    //清空
    clear()：并不是所有容器都有

    //返回vector的第一个数
    front()

    //返回vector的最后一个数
    back()

    //向vector的最后插入一个数
    push_back()
    
    //把vector的最后一个数删除
    pop_back()
    
    //vector的迭代器 begin()：vector的第0个数 end()：vector的最后一个数的后面一个数
    begin() / end()

    //vector支持随机寻址，与数组一样
    [ ]

    //支持比较运算，按字典序来比较   

#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
 
int main()
{
    //vector的初始化
    vector<int> a;
    //定义一个长度为10的vector
    vector<int> a(10);
    //定义一个长度为10的vector并且把里面的每一个数初始化成一个特定的数
    vector<int> a(10, -3);
    for(auto x : a) cout << x << "\t";
    
    //定义一个vector数组
    vector<int> a[10];
 
    //返回vector里面元素的个数 标准库里面有一个专门的变量存储size 不是把所有元素遍历一遍计算个数
    a.size();
 
    //返回a是不是空的 是空的就返回true 否则返回false 
    a.empty();
 
    //插入10个数
    for(int i = 0;i < 10;i++ ) a.push_back(i);
 
    //遍历vector 用数组下标来遍历
    for(int i = 0;i < a.size();i++ ) cout << a[i] << ' ';
 
    //用迭代器做遍历:迭代器可以看成是指针 *可以解引用
    for(/* auto:c++新关键字可以让系统自动推断变量的类型 */
    vector<int>::iterator i = a.begin();/* a[0]的迭代器 */i != a.end();/* a.size():最后一个数的后面一个数 */i++) 
    cout << *i << ' ' << endl;
    
    //c++的范围遍历 c++11的新语法
    for(auto x : a) cout << x << ' ';
 
    //可以判断两个vector的大小:比较方式是按字典序来比较 3333 < 444
    vector<int> a(4,3),b(3,4);
    if(a < b) puts("a < b");
 
    return 0;
}
/* -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 
   a < b */

pair

c++ 中常用的模板，可以存储一个二元组，前后两个变量类型可以任意

c++ STL容器 --- 单映射map、多重映射multimap_小雪菜本菜的博客-CSDN博客

支持比较运算，按字典序来比较   以 first 为第一关键字，以 second 为第二关键字(也是字典序，只不过可以看成是一个长度为 2 的字符串)

pair 可以用来干什么？

假设有一个东西有两种不同的属性，我们就可以用 pair 来存储，这两种属性可能需要按照某一个属性来排序，我们就可以把它们用 pair 来存储，把要排序的关键字放到 first 里面，把不需要排序的关键字放到 second 里面，然后直接对整个 pair 排序就可以了

当然 pair 也可以用来存储 3 个东西，某一种东西有 3 种属性的话也可以用 pair 来存储：pair< int，pair<int，int>> p；

可以看成标准库把我们实现了一个有两个变量的结构体，而且自带一个比较函数

pair 可以随便嵌套

#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
 
int main()
{
    pair<int,string> p;
 
    //取pair的第一个元素
    p.first
 
    //取pair的第二个元素
    p.second
    
    //构造一个pair
    p = make_pair(10,"yxc");
 
    //在c++11中支持
    p = {20,"abc"};
}

string

用字符数组存储 string 有很多不方便的地方，c++ 对字符串进行的封装很方便

c++封装string类、strcpy_s()、strcat_s()、memset()、strcmp()函数解析_小雪菜本菜的博客-CSDN博客

size()

empty()

clear()

length()：作用和  size 一模一样。都是返回字符串长度

#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
 
int main()
{
    string a = "yxc";
    //可以在某个字符串后面加上一个字符串
    a += "def";
    //也可以加上一个字符
    a += 'c';
    cout << a << endl;
    //返回的是某一个子串:1.要返回的子串的起始位置:下标从0开始,这里选择从下标1开始返回 2.要返回子串的长度:返回2个字母
    //当第2个参数很大/超过数组长度的时候,就会输出到最后一个字母为止
    //也可以把第2个参数省略掉:直接返回从1开始的整个子串
    cout << a.substr(1,2) << endl;
    //如果想用printf输出一个string,输出的其实是这个字符数组的起始地址
    //用c_str()可以返回string a存储字符串的字符数组的起始地址
    printf("%s\n",a.c_str());
    return 0;
}
 
/* yxcdefc 
   xc     
从第2个字母开始
   yxcdefc */

queue

从队尾插入，从队头弹出，是一个先进先出的关系

size()

empty()

c++ STL容器 --- 普通队列queue_小雪菜本菜的博客-CSDN博客

queue 没有 clear() 这个函数，如果想清空一个 queue 怎么办？

直接重新构造一个 queue 就可以了

#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
 
int main()
{
    queue<int> q;
    q = queue<int>();
    return 0;
}

priority_queue 

c++ STL容器 --- 优先队列priority_queue_小雪菜本菜的博客-CSDN博客

实现原理：是用堆来实现的，一般定义的堆默认是大根堆

如果想定义一个小根堆该怎么办？

①向堆中插入一个数的时候，直接插入负数就可以了，把 - x 按照从大到小的顺序排序，就是按 x 从小到大排序

②在定义的时候，直接定义成小根堆

需要一个中间容器充当优先队列的容量

#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
 
int main()
{
    //定义一个堆 默认是大根堆
    priority_queue<int> heap;
    //向堆中插入一个数的时候，直接插入负数就可以了
    heap.push(-x);
    //在定义的时候,多加两个参数就是小根堆
    priority_queue<int, vector<int>, greater<int>> heap;	   
    return 0;
}

stack

和队列基本上差不多

size()

empty()

没有 clear() 函数

c++ STL容器 --- 栈stack_小雪菜本菜的博客-CSDN博客_c++容器栈

deque

c++ STL容器 --- 双向队列deque_小雪菜本菜的博客-CSDN博客

加强版的 vector

size()

empty()

clear()

front()：返回第一个元素

back()：返回最后一个元素

push_back()：向最后插入一个元素

pop_back()：弹出最后一个元素

push_front()：向队首插入一个元素

pop_front()：从队首弹出一个元素

缺点是速度比较慢，比一般的数组要慢好几倍

支持随机寻址[ ]

支持 begin() / end() 迭代器

set / multiset

c++ STL容器 --- 单集合set、多重集合multiset_小雪菜本菜的博客-CSDN博客

set 里面是不能有重复元素的，如果向里面插入一个重复的元素，这个操作就会被忽略掉

multiset 里面是可以有重复元素的

size()：返回元素个数

empty()：时间复杂度为 O( 1 )

clear()

支持 insert()：插入一个数，时间复杂度为 O( logn )

find()：查找一个数，如果不存在的话返回的是 end() 迭代器

count()：返回的是某一个数的个数（在 set 里面只有 0 和 1 两种情况，在 multiset 里面有几个就返回几个）

在 set 中没有区别，在 multiset 中有区别 (x 可能有多个，如果直接删除 x，会把所有 x 都删掉；如果是删除迭代器，就只会删除这个迭代器)

 erase()：①如果输入是一个数 x，删除所有等于 x 的，时间复杂度为 O( k + logn )，k 是 x 的个数

               ②输入一个迭代器，删除这个迭代器

核心操作：

lower_bound() / upper_bound()

lower_bound()：返回大于等于 x 的最小的数的迭代器

upper_bound()：返回大于 x 的最小的数的迭代器

如果不存在返回 end()

#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <set>
 
int main()
{
    set<int> S;
    multiset<int> MS;
}

map / multimap

c++ STL容器 --- 单映射map、多重映射multimap_小雪菜本菜的博客-CSDN博客

begin() / end()，支持 ++、- - 操作，返回前驱(前一个数)和后继(后一个数)

维护的是一个有序序列

支持 insert() 和 erase() 操作

insert()：插入的数是一个 pair

erase()：参数是 pair 或者迭代器

find()：查找一个数，如果不存在的话返回的是 end() 迭代器

[ ]：完全可以像数组一样使用 map，时间复杂度是 O( logn )

数组直接取下标的时间复杂度是 O( 1 )

数组的第一个元素就是定义的第一个类型的变量，数组返回的值就是定义的第二个类型的变量

lower_bound() / upper_bound()

#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
 
int main()
{
    //把string映射成一个整数
    map<string,int> a;
    a["yxc"] = 1;
    cout << a["yxc"] << endl;
}

unordered_set、(无序)unordered_map、unordered_multiset、unordered_multimap

操作和上面类似，增删改查的时间复杂度是 O( 1 )

内部无序，不支持排序的操作：lower_bound() / upper_bound()，以及迭代器的 ++、- -

#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <unordered_map>
 
int main()
{
    unordered_map<string,int> a;
}

bitset

c++ STL容器 --- bitset容器_小雪菜本菜的博客-CSDN博客

一个整数 4 字节、32 位，但是很多题目想压位来计算(只需要知道每一位上的数是 0 还是 1)

c++ 里面的 bool 是一个字节，想开一个长度是 1024 的 bool 数组，就需要 1024 字节 = 1kb 内存

如果我们把它压到每一位里面的话，每一个字节存八位，只需要开 128 个字节就可以了

bitset 就是每一个字节上存 8 位，比正常的 bool 数组要省 8 倍内存，使用空间是正常 bool 数组的 1 / 8

使用情况：

存储 1w × 1w 的 bool 矩阵，如果用 bool 变量来存储，就需要 10^8 个 bool，大概是 100M 的空间，但是题目的空间限制是 64 M，就可以用 bitset 来存储，可以省 8 倍空间，就只需要 12M 的空间就可以了

可以把 bitset 看成是一个整数

支持各种位运算操作：取反~、与&、或|、异或^、移位<<、>>、==、！=

[ ]：可以取出某一位是 0 是 1

count()：返回有多少个 1

any()：判断是否至少有一个 1

none()：判断是否全为 0

如果 x 里面每一位都是 0 的话，none() 为 true，any()为 false

set()：把所有位置成 1

set(k，v)：将第 k 位变成 v

reset()：把所有位变成 0

filp()：把所有位取反，等价于~

filp(k)：把第 k 位取反

#include <bitset>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
 
int main()
{
    //传入个数/不需要传类型
    bitset<10000> S;
}