526互联

C++ STL

发布时间 2023-09-14 20:54:05作者: Hszzzx

Dev-C++ 可在 工具 -> 编译选项 -> 代码生成 / 优化 -> 代码生成 -> 语言标准 中选择 “ISO C++11” 或 “GNU C++11” 来支持 C++11 的新特性（蓝Dev 还不支持 C++14）

不声明下，区间均为左闭右开区间，typename 表示一个数据类型而不是 C++ 的关键字。

Containter（容器）

vector

vector<typename> v：声明一个内部元素为 typename 的可变长度数组 v

v.begin()：返回 v 首元素的迭代器

v.end()：返回 v 尾元素后一个的迭代器

v.push_back(x)：在 v 尾部插入元素 x

v.size()：返回 v 存储数据个数

v.capacity()：返回 v 实际占用空间

v.resize(k, val)：调整容器 v 的大小，使其包含 k 个元素

  1. 如果 n 小于当前容器的大小，则将内容减少到其前n个元素，删除超出范围的元素并销毁它们

  2. 如果 n 大于当前容器的大小，则通过在末尾插入所需数量的元素来扩展内容，以达到 n的大小。如果指定了val，则将新元素初始化为 val，否则初始化为 0

  3. 如果 n 也大于当前容器容量 capacity，将自动重新分配已分配的存储空间。

v.reverse(k)：改变 v 实际占用空间为 k，若 k < capacity，忽略

v.clear()：将所有元素置零，并不释放空间

如欲释放空间

void ClearV(vector<int> &a)
{
    vector<int> b;
    b.swap(a);
}
ClearV(a);
//当然，a现在不能使用了

遍历（C++11 及以上）（CSP 已支持 C++14）

for (auto i : a)
{
    cout << i;
}//此方法中i的改变并不会改变a中的值

for (auto &&i : a)
{
    cout << i;
}//此方法中i的改变会改变a中的值

C++11 以下

for (vector<int>::iterator it = a.begin(); it != v.end(); ++it)
{
    cout << (*it);
}

priority_queue

定义：

  1. 小根堆：

    priority_queue<typename, vector<typename>, greater<typename> >; greater在 <functional> 库中（被 <algorithm> 和 <queue> 包含）

  2. 大根堆：priority_queue<typename>;

小根堆定义中第三个参数为小于比较方式，大根堆可重载运算符变为小根堆

struct Node
{
    int a, b;
    bool operator<(const Node &ovo) const
    {
        return this->b < ovo.b;
    }
};
priority_queue<Node> Q;//按照b从大到小排

struct Node
{
    int a, b;
    bool operator<(const Node &ovo) const
    {
        return this->b > o.b;
    }
};
priority_queue<Node> Q;//按照b从小到大排

set

集合（每个元素只会出现一次）

内部使用红黑树实现，有序。

定义：set<typename> a;

a.begin()：头迭代器

a.end()：尾迭代器

a.insert(x)：插入 x

a.erase(x)：删除 x

a.count(x)：查询 x 是否出现在集合内

a.find(x)：找值为 x 的元素，如果有，返回 x 的迭代器；否则返回 a.end()

a.lower_bound()：找最小的 \(\ge x\) 的数

a.upper_bound()：找最小的 \(> x\) 的数

insert,erase 单次 \(O(\log n)\)

遍历均摊 \(O(n)\)

multiset

允许集合中有重复元素

定义：multiset<typename> a;

a.erase(x)：删除所有等于 x 的值

a.erase(iterator)：删除 iterator 所指向的元素

例：

multiset<int> a;
a.insert(1), a.insert(1), a.insert(4);
a.insert(5), a.insert(1), a.insert(4);
a.erase(1); //set 还剩下 {4, 5, 4};
a.erase(a.find(1)); //set 还剩下 {1, 4, 5, 1, 4}

unordered_set

定义：unordered_set<typename> a;

通过 hash 实现，常数大，内部无序，期望复杂度 \(O(1)\)，上界 \(O(n)\)（会被卡）

map

定义：map<typename1, typename2> m;

等价于 set<pair<typename1, typename2> > m;

遍历

map<string, bool> m;
m["I AK IOI"] = false;
for (auto &&u : m)
{
    u.first;//"IAKIOI"
    u.second;//false
    cout << m["hsbhzz AK IOI"];
    //生成m["hsbhzz AK IOI"],值为false;
}

m.count(x)：返回 bool ，x 是否存在

unordered_map

通过 hash 实现，期望复杂度 \(O(1)\)

定义：unordered_map<typename1, typename2> m;

bitset

本质是一个长度非常长的 bool 数组,一位占用一个 bit

bitset<n> a 生成一个 n 位的 bitset

b.set(pos, value)：把第 pos 位修改为 value

b.test(pos)：返回 pos 的 value

支持位运算

单点修改 \(O(1)\)

位运算 \(O(n/\text{字长})\) 32位或64位

pair

位于 <utility> 库中（被 <algorithm> 包含）

pair<string, int> a 声明一个 first 为 string，second 为 int 的二元组 a

已定义默认比较器，first 第一关键字，second 第二关键字

Algorithm（算法）

cin/cout读入优化（关闭流同步）

比快读快（by：一扶苏一）

警告！！！：如果有 freopen() 时再写关闭流同步，不保证输入正确！！！（参见 **_sync_closer）

热知识：return 0; 会自动 fclose();

//cin, cout 关闭流同步
ios::sync_sith_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);

使用后 cin 和 scanf 不可混用, cout 和 printf 不可混用

使用 endl 会导致加速效果消失，建议使用 '\n'

当然，可以同时使用 cin 和 printf，或 cout 和 scanf

nth_element

\(O(n)\)

nth_element(a.begin(),a.begin() + k - 1, a.end());

作用：找到一个无序数列第k小的数

会把第 k 小的数放在返回的迭代器的位置上，并使该位置左边的数都小于该数，该位置右边的数都大于该数

next_permutation

\(O(n)\)

next_permutation(a.begin(), a.end());

生成给定数列的严格下一个排列

//枚举全排列要用do-while(毕竟还包含这个序列本身)
do
{
    //do sth
}while (next_permutation(a, a + i);

generate

generate(a.begin(), a.end(), ACTIVE);

返回 void

作用：以 ACTIVE 的结果填充 \([\ a.begin(), a.end()\ )\) 的元素内容

generate_n

generate_n(a.begin(), n, ACTIVE);

返回一个迭代器

作用：以 ACTIVE 的结果填充 \([\ a.begin(),a.begin()+n\ ]\) 的元素内容

beautifully，你可以把自己写的快读放进去

例：

int read(void);
generate(a, a + n, read);
//等价于
generate_n(a, n, read);
//还等价于
for (int i = 0; i < n; ++i) a[i] = read();

__gcd

时间复杂度没有查

__gcd(a, b);

作用：返回 \(\gcd(a,b)\)

max({initializer_list}), min({initializer_list})

initializer list [ɪˈnɪʃəˌlaɪzər lɪst] n.初始值列表

盲猜 \(O(n)\)

作用：返回 initializer_list 中的最大，最小值

例 x = max({1, 2, 3, 4, 5, 114514, 1919810});//x = 1919810

reverse

\(O(n)\)

reverse(a.begin(), a.end());

作用：翻转给定数列

string v = "114514";
std::reverse(v.begin(), v.end());
// v = 415411

lower_bound

lower_bound(a.begin(), a.end(), x);

使用前需保证数列有序

\(O(\log n)\)

作用：找 \([\ a.begin(), a.end()\ )\) 中第一个 \(\geq x\) 的数

upper_bound

同上

作用：找序列中第一个 \(>x\) 的数

unique

unique(a.begin(), a.end());

作用：把一个有序序列去重，返回去重后数列的尾指针 + 1;

如果是结构体，需要重载运算符 ==

struct Node 
{
    int a, b;
}
bool operator==(Node x, Node y)
{
    return x.a == y.a && x.b == y.b;
}
//重载运算符不太确定, 应该是可以的
//我也不会在结构体里重载(丢人现眼)

多的元素其实被放到了序列末尾

去重后元素的个数为 unique(a.begin(), a.end()) - a.begin();

sort(lambada引出符[])

sort(v.begin(), v.end(), [](const int &a, const int &b) {return a > b;});

不用写函数，减少码量（）

sort 复杂度会被卡到 \(O(n^2)\)，平均时间复杂度 \(O(n\log n)\)

若需要稳定排序（即相等元素排序后不改变顺序）可使用 stable_sort()，其内部基于归并排序，时间复杂度为稳定的 \(O(n\log n)\)

fill

\(O(n)\)

memset() 按字节填充，故不能初始化诸如 1 等数字

fill(a.begin(), a.end(), FILL_NUM);

作用：把数列中的每一个元素初始化为 FILL_NUM

count

\(O(n)\)

count(a.begin(), a.end(), COUNT_NUM);

作用：返回 COUNT_NUM 出现的次数

cmath库

sqrt 支持 double，sqrtl 支持 long double

abs 支持 int，llabs 支持 long long 等等

可在 Dev-C++ 中输入函数，在输括号时会弹出其形参列表，便于查看

简单说一说

你的短板一般分三种

  1. 思维

    • 刷 CF 的题

    • 刷 SPOJ GSS（据说是仅次于 ynoi 的毒瘤题，初二的同志们不要再卷了）

    • 做题，见识不同的套路

    • 做结论题

    • 除非实在想不出来，不要看题解（可以复制 Markdown 题面到 marktext一类的阅读器中，将网页最小化）

    • 如果看了题解，记住套路，尽量让自己再做到同类题时有思维方向

  2. 技能树

    • 网上学习

    • 刷题（模板 2~5 道后尝试锻炼思维的题）

    • 不要点的太快（短时间内学习太多技能）

  3. 代码能力

    • 大模拟并不会提升你的代码能力

    • 多刷题

    • 打模拟赛

推荐题单

P.S.：

Q：初中学习和OI怎么安排？

A：看中考卷的程度

OS：衡水。。。

听课的时候打笔记累到手抽筋。

P.S. 这是去年的，但是应该没错（）

看不懂的话可以去 https://zh.cppreference.com/w/