C++中STL容器使用技巧

vector(变长数组，倍增的思想)

头文件：#include <vector>

• 数组如何变长？
  基于此思想：系统为某一程序分配空间时，所需时间与空间大小无关，与申请次数有关。
  最开始系统分配一个长度为n(如:32)的预留空间，如果存入的长度超过预留空间，就扩大两倍(64)，将原来的数组copy过来。

//初始化：
① vector<int> a;
② vector<int> a(n,e);//n为分配的空间，e为初始化值。
    size()//返回元素个数//时间复杂度为O(1)
    empty()//返回是否为空
    clear()//清空
    front()/back()//返回第0(指下标)个数/返回最后一个数
    push_back()/pop_back()//在最后面添加一个数/将最后一个数删除
    begin()/end()//vector的第0个数/vector的最后一个数的后一个数。
    []//支持随机寻值
    //支持比较运算，按字典序

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> a;

    //①添加元素
    for (int i = 0;i < 10; i ++) a.push_back(i);

    //②遍历vector
    for (int i = 0;i < a.size(); i ++) cout << a[i] << " ";
    cout << endl;

    for (vector<int>::iterator i = a.begin(); i != a.end(); i ++) cout << *i << endl;
    cout << endl;
    for (auto i = a.begin(); i != a.end(); i ++) cout << *i << endl;
    cout << endl;

    for (auto x : a) cout << x << " ";
    cout << endl;

    //③比较运算,按字典序比较
    vector<int> b(3,4),c(3,5);
    if (b < c) puts("b < c");
    else puts("b > c");

    //随机寻值
    cout << a[9] << endl;
}

pair<int,int>

可以存储一个二元组。
我们可以用它来存储两个相关联的的元素，将需要排序的元素放在first中。

    first//获取第一个元素
    second//获取第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（也是按字典序）

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
    pair<int,string> p;
    pair<int,pair<int,int>> p1;//存储三个元素

    //初始化
    p = make_pair(10,"lyw");
    p = (20,"abc");

    return 0;
}

string，字符串

    size()/length()//返回字符串长度
    empty()//返回是否为空
    clear()//清空字符串
    substr(起始下标，(子串长度)) //返回子串
    c_str()//返回字符串所在字符数组的起始地址

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
    string str = "lyw";

    //通过"+"实现增长数组
    str += "def";
    str += "c";

    cout << str << endl;

    //substr
    cout << str.substr(1,3) << endl;
    cout << str.substr(1,10) << endl;//当超过字符串实际长度或者没有指定长度时，输出到最后一个字符为止。
    cout << str.substr(1) << endl;

    printf("%s\n",str);//返回字符串的地址
    printf("%s\n",str.c_str());
}

函数c_str()就是将C++的string转化为C的字符串数组，c_str()生成一个const char *指针，指向字符串的首地址。

char *p=s[10];
string a=“welcome”;
strcpy(p,a.c_str());
cout<<p;

结果为”welcome”.

queue, 队列

头文件：#include <queue>

    size()
    empty()
    //无clear()函数
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

queue没有clear()函数，如果要清空一个队列，就直接重写构造一个新的。
代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;

    q = queue<int>();

    return 0;
}

priority_queue, 优先队列，定义的堆默认是大根堆

头文件：#include <queue>
实现原理：堆

    size()
    empty()
    //无clear()函数
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

定义小跟堆：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> heap;

    //没有clear()
    //heap.clear();

    int x = 1;

    //如何定义小根堆
    //方式一：插入数时，插入这个数的负数，然后从大到小排序，其实就是从小到大排序。
    heap.push(-x);
    //方式二：直接定义小根堆。
    priority_queue<int, vector<int>, greater<int>> heap1;

    return 0;
}

大顶堆和小顶堆的区别

堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

stack, 栈

头文件：#include <stack>

    size()
    empty()
    //无clear()函数
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列

头文件：#include <queue>
支持的操作很多，故效率很慢。

    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []//随机寻值

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列

头文件：#include <set>,#include <map>.

    size()
    empty()
    clear()
    begin()/end()
    迭代器的++, -- 返回前驱和后继，时间复杂度 O(logn)
    一个有序序列的迭代器中，当前元素的前一个元素为前驱，后一个元素为后继。

    set/multiset
        insert()  插入一个数
        find()  查找一个数，返回这个数的迭代器。
        count()  返回某一个数的个数(set返回0,1，multiset返回0~多个)
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn) (k是x的个数)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器

    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

    unordered_set, unordered_map, unordered_multiset, unordered_multimap, 基于哈希表实现,内部是无序的。
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

map可以像数组一样使用，示例如下：

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

int main()
{
    map<string, int> a;

    a["yxc"] = 1;

    cout << a["yxc"] << endl;

    return 0;
}

bitset, 圧位

C++中bool为一个字节(B)。1024B = 1KB 1MB = 1024KB
举例说明:开一个1024个bool类型的数组，我们通过压位实现1位存一个bool，这样只需要128个字节。
应用场景：
10^8 = 一亿。
这里有10000×10000的bool矩阵，把该需要100MB空间，而题目限制为64MB,使用压位只需要大约12MB。

    bitset<10000> s;//<>中是个数。
    支持所有位运算。
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反