STL详解

发表于 更新于 分类于 阅读次数： Changyan： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*STL笔记部分*/

vector动态数组{
    size()
    empty()
    claer()...
    //系统位某一程序申请空间的所需时间与空间大小无关，与次数有关,因此需要倍增vector
    vector<int> a(10,3); //定义长度位10的vector每个数初始化为3
    遍历方式：
        vector<int>::iterator it;//迭代器遍历
        for(auto x:a) ... //C++11特性
    支持比较运算，按字典序比较大小
}

pair{
    可以存储一个二元组pair<int,int>
    p.first,p.second分别取第一个第二的元素
    支持比较运算，按照字典序，以first为第一关键字，second为第二关键字
    p=make_pair(a,b) //pair的构造
    p={a,b} //c++11
}

string字符串{
    c_str() //返回string对应的字符数组的头指针
    如果使用printf("%s",p.c_str());
}

queue 队列
priority_queue(优先队列/堆){
    //默认是大根堆
    改成小根堆：
        1.插入负数
        2.priority_queue<int,vector<int>,greater<int>> heap;
    push(); 插入
    top();
    pop();
}
stack 栈
deque(双端队列,效率低)
set,multiset{
    //set里面不能有重复元素，multiset里面可以有重复元素
    set/multiset:
        insert()
        find() //不存在返回end迭代器
        count返回某个数的个数
        erase()
            (1)erase(x),删除所有这个数
            (2)erase(it)，删除此迭代器
        lower_bound(x)返回大于等于x的最小的数
        upper_bound(x)返回大于x的最小的数
}

map,multimap 基于平衡二叉树(红黑树)实现，动态维护有序序列{
    insert();   插入的是pair
    erase();    输入的参数是pair或者迭代器
    [] 映射，O(logn)
}

(哈希表){
unordered_set
unordered_map
unordered_multiset
unordered_multima
    //增删改查是O(1);
    //不支持upper_bound和lower_bound
}
bitset(位存储，状态压缩){
    bool a[1024]=1024B,bitset<1024>=128B
    count() 返回有多少个1
    any()  判断是否至少有一个1
    none()  是否全为0
    set()  把多有位置变成1
    set(k,v) 把第k位变成v
    flip()  等价于~
    flip(k) 等价于把第k位取反
}