• 预习篇

    • STL是Standard Template Library的缩写，在信息学竞赛中经常可以起到简化代码的作用，也可以在自己还未学会一些数据结构的时候，提前使用这种数据结构的功能来做题。
    大部分STL都在namespace std中，只需在程序开头写上using namespace std;就不用每次都要写std::了。下文默认已经有using namespace std;了。

    预习篇

    1. std::vector

    vector是一种不定长数组，它可以在运行程序的过程中改变数组的长度。同时vector也提供了一些函数来方便地完成一些常见数组操作。
    使用vector需要先引入头文件#include <vector>。
    可以对照下表来了解vector的常用功能：

    功能使用方法备注
    定义类型为type的不定长数组vvector<type> v;type既可以是int，double等原生类型，也可以是结构体其他容器。
    查询v的长度int len = v.size();所需运行时间与v的长度无关。需要注意.size()的返回值是无符号整数，int len = v.size();实际存在一个隐式类型转换。
    向v的末尾插入一个元素cv.push_back(c);c的类型和v的类型匹配，如果不相同则会进行隐式类型转换，如无法类型转换则会报错。
    向v的开头插入一个元素cv.insert(0, c);运行时间与v的长度正相关，数据范围较大时慎用。
    向v的第k个元素之前插入一个元素cv.insert(k, c);运行时间与k以后的长度正相关，数据范围较大时慎用。
    访问v的第i个元素v[i]或*(v.begin() + i)使用前者显然更加方便。i从0开始计数，如果v不存在第i个元素则可能出错。
    删除v的最后一个元素v.pop_back();运行时间与v的长度无关，一般来说可以放心使用。
    删除v的第k个元素v.erase(v.begin() + k);运行时间与k以后的长度正相关，数据范围较大时慎用。
    把v2赋值给v1v1 = v2;需要v1和v2的类型相同。
    清空vv.clear();执行后，删除v内的所有元素，v.size()也会变为0。

    2. std::sort

    sort可以将数组从小到大排序。
    使用sort需要先引入头文件#include <sort>。
    sort遵循左闭右开的性质，即包括左端点不包括右端点。请结合“左闭右开”四个字理解下表：

    功能代码
    a是原生数组，对a[0]到a[n - 1]排序sort(a, a + n);
    a是原生数组，对a[1]到a[n]排序sort(a + 1, a + n + 1);
    a是原生数组，对a[L]到a[R]排序sort(a + L, a + R + 1);
    a是vector，对它所有的元素排序sort(a.begin(), a.end());
    a是vector，对它的前k个数排序sort(a.begin(), a.begin() + k);
    a是vector，对a[L]到a[R]排序sort(a.begin() + L, a.begin() + R + 1);

    3. std::string

    在C语言中，我们通常使用char数组来存储一个字符串。而在C++中，使用string有时会更加方便。
    使用string需要先引入头文件#include <string>，注意不是cstring。
    可以对照下表来了解char数组和string的异同：


    		char[]string
    定义char s[数组长度];string s;
    输入scanf("%s", s);或cin >> s;cin >> s;
    输出printf("%s", s);或cout << s;cout << s;
    求长度int len = strlen(s);
    所需运行时间与s的长度成正比。    		int len = s.size();
    所需运行时间与s的长度无关。
    把s2赋值给s1strcpy(s1, s2);s1 = s2;
    比较s1和s2的字典序int t = strcmp(s1, s2);
    如果t == 0，则s1与s2相同。
    如果t < 0，则s1的字典序更小。
    如果t > 0，则s2的字典序更小。    		如果s1 == s2，则s1与s2相同。
    如果s1 < s2，则s1的字典序更小。
    如果s1 > s2，则s2的字典序更小。
    此外，<=，>=，!=，也可以使用。
    把s2拼接到s1后面strcat(s1, s2);s1 += s2;
    把s2拼接到s1前面无法直接使用已有函数实现，可以使用循环或者strcat实现。s1 = s2 + s1;
    把字符c拼接到s后面s[len] = c; s[len++] = '\0';s.push_back(c);或s += c;
    把字符c拼接到s前面无法直接使用已有函数实现，可以使用循环或者strcat实现。s = c + s;
    删除s中的字符无法直接使用已有函数实现，可以使用循环或者strcat实现。s.erase(p);表示删去第p个字符及以后所有的字符。
    s.erase(p, n);表示删去第p个字符开始总共n个字符。