STL讲义

• 指针
• • 声明
  • 赋值
  • 读取、操作指针上的值
  • 数组与指针的关联
  • 函数与指针的关联
• Standard Template Library
• • STL 部件
  • 算法
  • • 交换 swap
    • 排序 sort
    • • 对数组升序排序
      • 对数组降序排序 - 仿函数的介绍
      • 对结构体排序
      • 当然，我们也可以重载小于号完成此操作
    • 去重 unique
    • 二分查找 x_bound / binary_search
    • • 在降序排序数组中的二分查找
    • 全排列 x_permutation
    • 倒置 reverse
    • 填充 fill / fill_n
  • 容器
  • • 共有操作
    • 容器的遍历
    • 线性容器
    • • • 可变长数组 vector
        • 内含的倍增设计
        • 可以 sort
        • 常用的离散化操作
        • shrink_to_fit 操作（销毁vector）
      • 字符串 string
      • • 输入方式
        • 重要方法们
      • 栈 stack
      • 队列 queue
      • 双端队列 deque
      • 优先队列 priority_queue
      • 链表 list
      • 二进制位运算 bitset
    • 非线性容器
    • • 辅助容器：Pair 与 Tuple
      • • pair

指针与 STL

• 声明变量时，每个值都有自己在内存（实际上是ROM）中对应的地址。如果想要通过这些地址来管理上面存储的变量，需要使用指针。
• 指针是存储变量地址的变量，也即是说，其本身也有地址的概念。在此基础上。我们可以定义多级指针。在多级指针上的操作，是精巧而微妙的，像是一条链一般，将一些指针紧紧关联在一起，如果破坏这个链，则可能发生意料不到的结果（游戏外挂的实现原理就是将回调函数篡改为其他函数）。

type * var_name; // 声明一个 type 类型的指针，名是 var_name
type * p, * q;   // 声明两个 type 类型的指针，注意每一个都要加上 *
type * tp, tq;   // 声明了一个 type 类型的指针 tp, 一个 type 类型的变量 tq

我们总是将变量的地址交给指针，让这个指针来管理该地址上的变量。

• 这句话是概括性的，实际上阐述了指针变量的赋值操作。

int n1 = 1;
int * p  = &n1; // & 作为单目操作符号时，作用是取地址 「我们总是将变量的地址交给指针」
int n2 = 2;
p = &n2; // 「我们总是将变量的地址交给指针」

• 使用小星星 ( * ) 符号读取一个指针管理地址对应的值，对指针的操作同时也作用于其管理的变量。

int n = 1;
int * p = &n;
(*p) ++; // 单目运算优先级不同
cout << n << 'n'; // 2
cout << *p << 'n'; // 2

• 一个经典的例子是在 C 语言中设计一个交换函数：

 #include 
 void mySwap(int* a, int *b) {
     int t = *a;
     *a = *b;
     *b = t;
 }
 int main() {
     int a = 1, b = 2;
     mySwap(&a, &b); // 「我们总是将变量的地址交给指针」
     printf("a = %d, b = %d", a, b);
     // a = 2, b = 1
     return 0;
 }

一个基本的事实是，数组的名就是该数组起始位置对应的指针。形式化地讲，对于数组 arr[N]， arr = &arr[0]。

很自然的，函数也存储于内存中，因而也有地址。这一部分的知识点被称作「函数指针」，简单来讲，就是可以将函数作为参数传入函数，这里暂且不谈。

指针的内涵相当丰富，正是有了指针才有了各种关于 C 语言的传奇。我相信任何程序员都承认，指针是 C 语言的精髓所在。不过受文章长度与笔者水平限制，就先介绍到这里，这些简单知识对于竞赛完全足够，当然还是建议学有余力的选手尝试自学包括但不限于「函数指针、回调函数」，「多级指针」，「垃圾回收机制」等知识点。

不过更重要的，是这种把变量映射到另一变量的想法。

• 即标准模板库，简称 STL， 是 C++ 内置的一些库。客观的讲，竞赛手所使用的「C++」，不如称为「C + STL」。
• 何为模板？首先我们引入重载函数的概念，当我们要实现一个功能，与类型无关的时候，函数名可以重复（即参数列表且仅有参数列表不同），我们可以实现一些同名函数。不过这样依然容易造成代码冗余，进而有了模板的概念：模板可以作用于函数与结构体（类）上，表示函数参数列表 / 结构体（类）类型列表可以变化。简单来说，我们可以用更少的代码实现一类函数，这些函数的功能仅与类型无关。特别的，这些函数不妨称作「模板函数」，而这些类、结构体，不妨称作「模板类」。STL 则包含了这两类。
• 关于头文件：

#include  // 万能头文件，包含了 STL 以及更多常用库
using namespace std;     // 为了防止多用户的命名有冲突，将这些 变量、类型、函数 都放在命名空间中，作为区分
// 要访问一个namespace 中的对象，使用域操作符 ( :: ) 例如 std::cout << "Hello World!" << 'n';
// STL 以及其他标准函数定义于 std 下，这句话的意思就是引入 std 下的所有对象命名
// 形式化的说，加入了这句话，就不需要 std::cout << 'n' 而直接 cout << 'n' 了

总共有四个部分：「容器」、「算法」、「迭代器」、「函数」，四者关系如下图所示：

也即容器通过迭代器，辅以函数调用算法。我们首先来看一些常用算法：

• STL 中的算法都是左闭右开的，因为大多数算法更容易用这样的区间描述。

• 是的，C++ 实现了 swap，通过上面对模板函数的讲解，相信你已然猜测到，swap支持多种类型，实际上确实是这样。下面的 Demo 演示了这一点：

#include 
#include  // swap 在 algorithm 下
using namespace std;
int main() {
    int a = 1, b = 2;
    swap(a, b); // 当然也可以选择 swap(a, b) 这种写法，不过本人并不推荐
    cout << "a = " << a << ", b = " << b << 'n';
    // a = 2, b = 1
    return 0;
}

自然也可以应用于多种类型，默认对区间（左闭右开，下文不再赘述）升序排序。

只能对数组、vector、string、deque 使用 sort。（具体原因是，仅有这三种容器实现了 RandomAccessIterator，这是迭代器，不严谨地说，即指针）

下面的几个 Demo 有助于帮助你理解该函数的用法。

#include 
#include 
#include 
using namespace std;

int main() {
  srand(time(nullptr));
  int n; cin >> n; int arr[n];
  for (int i = 0; i < n; ++i) arr[i] = rand() % 1000;

  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];
  // " n"[i + 1 == n] 是一个常用技巧，用于输出一个数组，用空格分隔，行尾无空格
    
  sort(arr, arr + n);
  // 升序排序
  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];

  return 0;
}

19
586 190 608 2 303 498 877 990 272 327 490 148 314 132 371 715 159 580 591
2 132 148 159 190 272 303 314 327 371 490 498 580 586 591 608 715 877 990

将原数组升序排序后再反转虽然不失为一种做法，不过略微笨拙了一些。

• sort

#include 
#include 
#include 
using namespace std;

int main() {
  srand(time(nullptr));
  int n; cin >> n; int arr[n];
  for (int i = 0; i < n; ++i) arr[i] = rand() % 1000;

  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];

  sort(arr, arr + n, greater<>());
    // 同名函数，不同参数列表 -> 重载的函数
    // 实际上写作 greater()， 但函数可以省略类型，注意不能省略 '<>'
  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];

  return 0;
}

19
586 190 608 2 303 498 877 990 272 327 490 148 314 132 371 715 159 580 591
990 877 715 608 591 586 580 498 490 371 327 314 303 272 190 159 148 132 2

#include 
#include 
#include 
using namespace std;

struct node {
  int a, b, c;
};

bool cmp(node x, node y) {
  return x.c > y.c;
  // 将 node::c 作为关键字，降序排序
}

int main() {
  int n; cin >> n;
  node a[n]; // C++ 声明结构体不需要 struct node a[n];
  for (int i = 0; i < n; ++i) {
    a[i] = (node) { rand() % 100, rand() % 100, rand() % 100 };
  }

  for (int i = 0; i < n; ++i) {
    cout << a[i].a << " " << a[i].b << " " << a[i].c << 'n';
  }
  cout << "-----" << 'n';
    
  sort(a, a + n, cmp);
    // 将函数传入函数，这边是「函数指针」的思维，也叫回调函数
  for (int i = 0; i < n; ++i) {
    cout << a[i].a << " " << a[i].b << " " << a[i].c << 'n';
  }

  return 0;
}

7
83 86 77
15 93 35
86 92 49
21 62 27
90 59 63
26 40 26
72 36 11
-----
83 86 77
90 59 63
86 92 49
15 93 35
21 62 27
26 40 26
72 36 11

• 重载操作符是 C++ 的一大重要特性，简单来讲，他将函数包装在操作符中。当然，有一些操作符是不允许重载的，更具体的可以百度学习。
• 简单来说，要使用 sort 对结构体排序，下面的格式是固定的，少一个部分都是错误的。

bool friend operator < (const _struct & a, const _struct & b) {
    return a.x < b.x;
} // 友元重载
// 或者有另一种写法，更为简洁：
bool operator < (const _struct & t) const {
    return this->x < t.x;
    // return x < t.x;
}

下面是一个 Demo :

#include 
#include 
#include 
using namespace std;

struct node {
  int a, b, c;
  bool operator < (const node & _node) const {
    return this->c < _node.c;
  }
  // bool friend operator < (const node & a, const node & b) {
  //   return a.c < b.c;
  // }
};

int main() {
  int n; cin >> n;
  node a[n]; // C++ 声明结构体不需要 struct node a[n];
  for (int i = 0; i < n; ++i) {
    a[i] = (node) { rand() % 100, rand() % 100, rand() % 100 };
  }

  for (int i = 0; i < n; ++i) {
    cout << a[i].a << " " << a[i].b << " " << a[i].c << 'n';
  }
  cout << "-----" << 'n';
    
  sort(a, a + n);
  // 这里便不需要加入自定义的比较器了
  for (int i = 0; i < n; ++i) {
    cout << a[i].a << " " << a[i].b << " " << a[i].c << 'n';
  }

  return 0;
}

7
83 86 77
15 93 35
86 92 49
21 62 27
90 59 63
26 40 26
72 36 11
------
72 36 11
26 40 26
21 62 27
15 93 35
86 92 49
90 59 63
83 86 77

• 将重复的元素移动至容器的末尾(并未删除)，并返回第一个去重好内容的最后一个元素的下一个位置的迭代器（思考一下，为什么要这样设计？）。
• 下面的代码可以完成去重的升序排序：

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 2, 4, 45, 2, 3, };
  int n = sizeof arr / sizeof arr[0];
  // C 语言基本操作
  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];
  
  sort(arr, arr + n);
  n = unique(arr, arr + n) - arr; // 返回在数组中的对应位置，左闭右开的设计更利于下面的实现
  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];
    
  return 0;
}

1 2 3 2 4 45 2 3
1 2 3 4 45

• 二分查找的前提是容器有序，与刚才的 RandomAccessIterator 不同，x_bound 支持 ForwardIteraor，即支持 ++ 迭代器的容器都可以使用。不过我们常常用于数组。

• lower_bound(l, r, val) 返回 [l, r) 中第一个 ≥ val 的元素所在迭代器

• 而 upper_bound(l, r, val) 则返回 [l, r) 中第一个＞ val 的元素所在迭代器

• binary_search(l, r, val) 返回 [l, r) 中是否存在一个值是 val

• 上文提到，迭代器是指针。因而根据最先提到的关于指针的内容，我们可以使用小星星 ( * ) 来读取与操作该指针所管理的变量，因而我们当然可以：

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 5, 6, 7, }; // already sorted
  // is_sorted(arr, arr + n) --> yes
  int n = sizeof arr / sizeof arr[0];

  *lower_bound(arr, arr + n, 5) = 8;
  for (int i = 0; i < n; ++i) cout << arr[i] << " n"[i + 1 == n];
  return 0;
}

1 2 3 4 8 6 7

• 与 sort 一样，传入仿函数 greater<>() 或 cmp 作为的第四个参数即可：

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 5, 6, 7, }; // already sorted
  // is_sorted(arr, arr + n) --> yes
  int n = sizeof arr / sizeof arr[0];
  sort(arr, arr + n, greater<>());

  int l_pos = lower_bound(arr, arr + n, 4, greater<>()) - arr;
  cout << l_pos << " : " << arr[l_pos] << 'n';

  cout << (binary_search(arr, arr + n, 7) ? "YES" : "NO" ) << 'n';
    // 未正确使用比较器
  cout << (binary_search(arr, arr + n, 7, greater<>()) ? "YES" : "NO" ) << 'n';
    // 正确使用
  return 0;
}

3 : 4
NO
YES

这时候就有问题了：如果未找到，会返回什么呢？

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 5, 6, 7, }; // already sorted
  // is_sorted(arr, arr + n) --> yes
  int n = sizeof arr / sizeof arr[0];
  sort(arr, arr + n, greater<>());

  int l_pos = lower_bound(arr, arr + n, 8, greater<>()) - arr;
  // cout << l_pos << " : " << arr[l_pos] << 'n';
  cout << l_pos << ':' << n << 'n';

  return 0;
}

0:7

• 更多有关结构体，同sort，不做赘述。

• 首先思考一下，全排列最多有多少种呢？我们考虑完全互异的 n n n 长数组，由高中数学知识，我们知道这个复杂度是 A n n = n ! A_n^n = n! Ann​=n! 的。
• 下面要介绍一下「字典序」：正如你翻字典那般，我们总是从第一位开始比较。举个例子，字典序意义下：11 < 2。

#include 
#include 
#include 
using namespace std;

int main() {
  string s = "abdd";
  do {
    cout << s << 'n';
  } while (next_permutation(s.begin(), s.end()));
    // 先不必在意 begin, end 具体是什么，下面容器中有

  return 0;
}

abdd
adbd
addb
badd
...
dbad
dbda
ddab
ddba

• 如果将上面的 s = "1234" ，那么就有

1234
1243
1324
1342
...
4213
4231
4312
4321

• 如果要得到字典序递减的，可以使用 prev_permutation，用法一致，不做赘述。

• 内部实现实际上是一个双指针算法。

string s = "1234567890";
reverse(s.begin(), s.end());
cout << s << 'n'; // 0987654321

• 常用于初始化数组（多次对数组的操作需要对数组赋初始值）：

int arr[maxn]; // 假定该 maxn 已在上面定义

memset(arr, 0x3f, sizeof arr); // 将 arr 中的所有元素都置为 0x3f3f3f3f (如果arr[]是int的话)
// 简言之， memset 按照字节清空

fill(arr, arr + n, -1); // 将 [arr, arr + n) 的元素都置为 -1
// 注意区分 memset(arr, -1, sizeof arr); 实际上将元素置为 0xffffffff (补码)

fill_n(arr, n, -1); // 将 [arr, arr + n) 的元素都置为 -1

STL 实际上包含更多算法，上面介绍的是一些比较常用的。除了这些以及几乎每个人都会使用到的min, max外，笔者还常常使用 min_elememt, partial_sum, iota, accumulate。

• 上面对于算法的介绍中穿插了迭代器与仿函数，竞赛需要知道的关于两者的知识点基本都融入其中，因而下面只介绍容器。
• STL 中的容器实际上是一些常用数据结构的实现，数据结构可以理解为「一些元素按照一定规则形成的整体」。从关联度来看，可以分为「一对一」的线性结构与「一对多」的非线性结构。

实际上的 STL 包含容器，配接器。这里为了叙述方便，归为一类。

• 但不论何种容器，大多都支持下面的一些操作：

• 对某些对象的特定操作函数，用点操作符(.)（如果本身是一个指针变量，需要使用(->) 箭头操作符）来访问。
• 这些函数，通常称作「方法」，与普通函数做区分。

• 有的容器并不支持数组那样的随机访问，但下面的遍历方式总是有效的：

// 这里的 auto 是 C++ 11 加入的特性，可用于推导类型
// 也可以写成 container::iterator
for (auto it = container.begin(); it != container.end(); ++ it) {
    cout << *it << ' ';
}

• 我们也可以使用 for each 的方式来遍历，确保编译器支持 C++11 即可

for (auto i : container) {
    cout << i << ' ';
}

• 反向遍历

当然，你可以使用刚才的 reverse(container.begin(), container.end()) ，随后按照上面的方式遍历。不过有更好的方法 —— 反向迭代器 ：

for (auto it = container.rbegin(); it != container.rend(); ++ it) {
    cout << *it << ' ';
}

• 用 push_back 或者 emplace_back 来向 vector 末尾加入元素。
• 用 pop_back 来删除末尾的元素。

在数组中删除一个元素的效率是 O ( n − o r d ) mathcal O(n - mathrm{ord}) O(n−ord) 的，也就是说，只有删除最后一个元素是 O ( 1 ) mathcal O(1) O(1) 的。

• front() 访问首个元素，back() 访问最后一个元素。
• 构造参数可以是以下三种：

#include 
#include 
#include 
#include 
using namespace std;

int main() {
  int arr[] = { 1, 2, 3, 4, 4};
  int n = sizeof arr / sizeof * arr;

  vector vc(arr, arr + n);
  for (int i : vc) cout << i << ' '; cout << 'n';

  vector vc2(n);
  for (int i : vc2) cout << i << ' '; cout << 'n';

  vector vc3(n, 1);
  for (int i :vc3) cout << i << ' '; cout << 'n';

  return 0;
}

1 2 3 4 4
0 0 0 0 0
1 1 1 1 1

上面提到 size() 查看元素个数。对于 vector ，有一个方法叫做 capacity() ，可以查看容量。不妨思考一个问题，它是怎样做到变长的呢？实际上，其内部存储方式依然是数组，数组的大小需要在声明时给出，因而只有一种可能了：要变长时，它将会把自己拷贝到另一块连续的空间中。变长一次拷贝一次的复杂度是 O ( n ) mathcal O(n) O(n) 的，并不优秀（基于一个计算机常识，分配内存的时间花费与大小无关，仅与次数有关，因而我们总是避免小块内存频繁分配的操作）。实际上，vector 内部隐含了一个倍增的算法：当需要边长时，将 capacity() 扩展至原来的两倍，由基本的算法知识，我们知道，这个复杂度是 O ( log ⁡ n ) mathcal O(log n) O(logn) 的，非常优秀。

可以用下面的 Demo 来验证上面的过程：

#include 
#include  // vector needed
#include 
using namespace std;
int main() {
  vector vc;
  for (int i = 0; i < 1025; ++i) {
    vc.emplace_back(i);
    cout << vc.size() << " / " << vc.capacity() << 'n';
  }
  return 0;
}

除上面演示过的 sort 之外，需要降序时，可使用反向迭代器完成相同的工作。

#include 
#include 
#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 4, 1, 2, 3, 4, 4, 9, };
  vector S;
  int n = sizeof arr / sizeof arr[0];
  for (int i = 0; i < n; ++i) S.emplace_back(arr[i]);
  sort(S.rbegin(), S.rend());
  for (int I : S) cout << I << ' '; cout << 'n';

  return 0;
}
// 9 4 4 4 4 3 3 2 2 1 1

• 即去重排序后重新编号，如果当前处理的问题只与元素相对大小有关，便可以将大值域离散化到小值域上（根本原因：竞赛题目中数组不够大，就算能开那么大，也有许多浪费的空间）。

vector vc;
// 假设已经有值了
sort(vc.begin(), vc.end());
erase(unique(vc.begin(), vc.end()), vc.end());
// 把不需要的部分抹除即可
// 随后可以编号，实现较为轻松，交给读者
// 当然也可以维护两个数组完成离散化的操作

你当然可以自己写一个 Demo 来尝试一下，clear() 之后 size() 与 capacity() 的变换是怎样的。

答案是，size() 变为了 0 0 0，而 capacity() 并没有变换。简单来讲，clear() 操作并没有真正地删除整个 vector

那该如何销毁一个 vector 呢？我们当然可以使用 vc = vector(); 来重新创建一个数组，不过我们也可以使用下面的一种叫做shrink_to_fit 的操作来销毁：

vector().swap(vc);

• 对于字符串，首先当然就要考虑如何输入啦！下面的 Demo 演示了如何获取字符串：

#include 
#include 
#include 
using namespace std;
int main() {
  string s;
  cin >> s;
  cout << s << 'n';
  cin.ignore();

  stringstream ss;
  getline(cin, s);
  ss << s;
  string str;
  while (!ss.eof()) {
    ss >> str;
    cout << str << 'n';
  }
  return 0;
}

// input
abcdefg
abc efg hij klm
// output
abcdefg
abc
efg
hij
klm

• 字符串的操作覆盖了大多数 vector 的操作，包括排序 hhh。简单提两个重要的方法：
  1. c_str() 这个方法可将 string 转化为对应的 char[](或者理解为 char * )，随后就可以调用 中的算法了。包括但不限于KMP算法 : strstr(), strtok()。以后的周赛，都默认选手已掌握这些算法。
  2. swap() ，与刚才的 vector 相同，释放内存，依然需要shrink_to_fit，这次直接 string("").swap(str) 即可。
• 同时，字符串重载了一些操作符：

• 栈是经典的数据结构，满足「先进后出」的规则。可以想象一个装了书的箱子（假设一层只能放下一本书），限制不可从箱底拿书的话，我们只能从箱顶取出书，我们给书编上号，依次将 [ 1 , 2 , 3 , 4 , 5 ] [1,2,3,4,5] [1,2,3,4,5] 放入书箱，那么取出最后一本书的话，顺序将会是 [ 5 , 4 , 3 , 2 , 1 ] [5,4,3,2,1] [5,4,3,2,1]。

• 细心的你一定发现了，这就是函数的实现机制，的确，函数通过系统栈进行实现，与这里的原理相同，倘若函数调用过多（递归过深），系统栈将不够用（爆栈）。

• C++ 虽然实现了栈，但我们建议手写一个栈（因为实现难度较低，而 STL 常数太大，同时有的时候我们还需要对栈排序或者二分查找 hhh）。

栈的常用场景：记录元素并倒序输出、括号匹配问题、改写递归函数。

与栈一样，队列也是常用数据结构。不过正如其名，讲究「先来后到」，倘若入队序列为 [ 1 , 2 , 3 , 4 , 5 ] [1,2,3,4,5] [1,2,3,4,5]，那么出队序列就会是 [ 5 , 4 , 3 , 2 , 1 ] [5,4,3,2,1] [5,4,3,2,1] 。处于同样的原因，我依然建议手写队列：

• 之所以不推荐使用 STL 中的 queue 与 stack，一部分原因是实现简单，另一部分原因就是C++ 在 stack 与 deque 中内含了 deque 。形式化地讲，stl 用 deque实现了stack,queue。
• 什么是 deque 呢？double end queue 双端队列，顾名思义，元素现在不仅可以从队头出队，也能从队尾出队；不仅能从队尾入队，也能从队头入队。且：这些操作都是 O ( 1 ) mathcal O(1) O(1) 的。

其方法常用的有 push_x 与 pop_x ，其中 x 表示 back 与front()，与队列理解类似，不做赘述。

• 其内部实现依赖于线性容器 (实际上是这样的数据结构我们称其为配接器)。
• 该数据结构**（堆）**可以快速维护一个序列中的动态最大值，也就是说，即使其中的元素可能变化，我们依然能快速 ( O ( log ⁡ n ) mathcal O(log n) O(logn) ) 求出这些元素中的最大值。我们通过下面的 Demo 来理解一下：

#include 
#include  // 引入 queue
#include 
using namespace std;
int main() {
  priority_queue pq;
  for (int i = 1; i <= 19; ++i) {
    int x = rand() % 1234 - 517;
    cout << x << ' ';
    pq.push(x); // push
  }
  cout << 'n';
  while (pq.size()) {
    cout << pq.top() << ' ';
    pq.pop();
  }
  return 0;
}

702 383 -472 -432 106 -276 119 695 532 -498 -419 -90 293 -226 60 363 -347 453 205
702 695 532 453 383 363 293 205 119 106 60 -90 -226 -276 -347 -419 -432 -472 -498

• 如果想要从小到大，一种具有技巧性的操作是，维护原有数值的相反数即可。我们下面给出另一种声明方式：

#include 
#include 
#include 
#include  // vector needed
using namespace std;
int main() {
  priority_queue< int, vector, greater > pq;
  // > > 分开，防止编译器版本过低而认为这是一个 >> 右移操作
  for (int i = 1; i <= 19; ++i) {
    int x = rand() % 1234 - 517;
    cout << x << ' ';
    pq.push(x); // push
  }
  cout << 'n';
  while (pq.size()) {
    cout << pq.top() << ' ';
    pq.pop();
  }
  return 0;
}

702 383 -472 -432 106 -276 119 695 532 -498 -419 -90 293 -226 60 363 -347 453 205
-498 -472 -432 -419 -347 -276 -226 -90 60 106 119 205 293 363 383 453 532 695 702

部分时候，需要手写堆，暂时不提。

• 实际上是双向链表。链表依然是线性结构，不过其地址可能并非连续，这样的设计使得插入与删除都是 O ( 1 ) mathcal O(1) O(1) 的效率。而在数组意义下的两种操作，则最坏需要花费 O ( n ) mathcal O(n) O(n)。
• 但坏处是，由于地址不连续，该结构并不能做到快速查找某个值，例如，要到链表的第 n n n 个位置，需要先到第 n − 1 n-1 n−1 个位置 ⋯ cdots ⋯，最坏需要花费 O ( n 2 ) mathcal O(dfrac{n}{2}) O(2n​) 的时间，想一想，为什么？ 答案其实是，前面提到过，这是一个双向链表，因而我们可以比较要访问的位置距离两端的较小距离，最坏自然是中位。

思考一下，能否设计出一种数据结构，插入、删除、寻址都是很快的呢？

下面的小 Demo 演示了链表的一些操作：

#include 
#include 
#include 
using namespace std;
int main() {
  list l;
  for (int i = 1; i <= 12; ++i) {
    int x = rand() % 123 - 62;
    l.push_back(x);
  }
  cout << "Order is as follows:" << 'n';
  for (int I : l) { cout << I << ' '; } cout << 'n';

  cout << "Reversed order as : " << 'n';
  for (auto it = l.rbegin(); it != l.rend(); it ++) {
    cout << *it << ' ';
  }
  cout << 'n';

  cout << "After sorted : " << 'n';
  l.sort();
  for (int I : l) { cout << I << ' '; } cout << 'n';

  cout << "Replace lower_bound(45) with 114514, then :" << 'n';
  *lower_bound(l.begin(), l.end(), 45) =  114514;
  for (int I : l) { cout << I << ' '; } cout << 'n';

  cout << "After erasing upper_bound(1) :" << 'n';
  l.erase(upper_bound(l.begin(), l.end(), 1));
  for (int I : l) { cout << I << ' '; } cout << 'n';

  cout << "After inserting 23333 into the position after 1st :" << 'n';
  l.insert(++ l.begin(), 23333);
  for (int I : l) { cout << I << ' '; } cout << 'n';

  return 0;
}

Order is as follows:
-16 56 -62 2 27 -43 26 52 43 -4 6 26
Reversed order as :
26 6 -4 43 52 26 -43 27 2 -62 56 -16
After sorted :
-62 -43 -16 -4 2 6 26 26 27 43 52 56
Replace lower_bound(45) with 114514, then :
-62 -43 -16 -4 2 6 26 26 27 43 114514 56
After erasing upper_bound(1) :
-62 -43 -16 -4 6 26 26 27 43 114514 56
After inserting 23333 into the position after 1st :
-62 23333 -43 -16 -4 6 26 26 27 43 114514 56

• 实际上，在算法竞赛中，用到链表的地方依然是少之又少。即使要用，我们可能也不会优先选择 STL，而是手写一个链表，或者使用「链式前向星」，用于建图，在图论章节，将会有学长讲解该知识点。实际上，另一种常用存图方式借助于 STL 中的 vector 。

• 虽然 bool 只有两种状态，可内部实现依然占了 8 b i t s 8rm bits 8bits，这是浪费空间的。尤其是我们想用 vector 或者是 bool[] 的时候，这显得非常庞大。我们当然可以用一个 int 保存八个位的数据。当然如果你学过 C语言内存管理的话，根据内存对齐，单个结构体里八个位域也不是不可以
• 下面介绍更优秀的二进制容器：bitset。

下面的内容，默认读者已具备二进制基本常识。

bitset 的定义需要先声明位数，可带一个原型来构造二进制串，同时它支持所有的位运算操作符。下面来演示一下基本用法：

#include 
#include 
using namespace std;

int main() {
  int n = 1024;
  bitset<15> bs (n); cout << bs.to_string() << 'n';
  bitset<15> bs2 (1024);
  cout << ((bs == bs2) ? "YES" : "NO") << 'n';
  bs |= 1; cout << bs.to_string() << 'n';
  bs ^= bitset<15>(1); cout << bs.to_string() << 'n';
  bs &= bitset<15>(64); cout << bs.to_string() << 'n';
  bs = ~bs; cout << bs.to_string() << 'n';
  return 0;
}

000010000000000
YES
000010000000001
000010000000000
000000000000000
111111111111111

左移右移交给读者尝试。除基本位运算之外，他还支持一些复合操作：

• 下面的程序可用于验证。

#include 
using namespace std;
#define lowbit(_) ((_)&-(_))

string helper(int x, int mask = 31) {
  string s = "";
  for (int i = 0; i <= mask; ++i)
    s += "01"[x >> i & 1];
  reverse(s.begin(), s.end());
  int idx = -1;
  while (s[++idx] == '0');
  return idx == s.size() ? "0" : s.substr(idx);
}

int c = 0;
#define judge(con) cout << ++ c << " " << (con ? "Passed" : "Error") << 'n'

int main() {
  int n = 114514;
  cout << helper(n) << "n";
  bitset<31> bs(n);
  // 访问第 k 位
  int cnt = 0;
  for (int k = 0; k <= 31; ++k)
    cnt += bs[k] == (n >> k & 1);
  judge(cnt == 32);
  // 统计 1 的个数
  cnt = 0;
  int t = n;
  while (t) ++ cnt, t -= lowbit(t);
  judge(cnt == bs.count());
  // 是否存在 1
  judge((n != 0) == bs.any());
  // 是否全是 0
  judge(!n == bs.none());
  // 将所有位置为 1
  auto bs2 = bs;
  bs2.set();
  judge(bs2 == ~(n&0));
  // 将第 k 位置为 v
  cnt = 0;
  int v;
  for (int k = 0; k <= 30; ++k) {
    int res = n;
    v = rand() & 1;
    if (v & 1) {
      if (!(res >> k & 1))
        res += 1 << k;
    } else {
      if (res >> k & 1) 
        res -= 1 << k;
    }
    bs2 = bs;
    bs2.set(k, v);
    cnt += bs2 == res;
  }
  judge(cnt == 31);
  // reset 是上述问题的子问题
  bs2 = bs;
  bs2.flip();
  judge(bs2 == ~(n));

  bs2 = bs;
  cnt = 0;
  for (int k = 0; k <= 30; ++k) {
    bs2 = bs;
    bs2.flip(k);
    cnt += bs2 == ( n ^ (1 << k) );
  }
  judge(cnt == 31);

  return 0;
}

11011111101010010
1 Passed
2 Passed
3 Passed
4 Passed
5 Passed
6 Passed
7 Passed
8 Passed

• 使用 bitset，我们能快速得到二进制意义下的数据，相当强大。同时在后面的章节中，二进制这种压缩信息的方式也常常能使用到，非常重要。

即树形结构，下面将会介绍大致两类：有序容器、无序容器。

但在此之前，需要介绍辅助的 STL：pair， 以及tuple：

#include 
#include 
#include 
using namespace std;

inline void print(pair p12) {
  cout << "(" << p12.first << ", " << p12.second << ")" << 'n';
}

int main() {
  pair pii(1, 2);
  auto pii2 (pii);
  auto pii3 = make_pair(3, 4);
  print(pii);
  print(pii2);
  print(pii3);
  cout << "---------------" << 'n';

  vector< pair > piis;
  for (int i = 0; i < 6; ++i) {
    piis.emplace_back(make_pair(rand() % 123, - rand() % 123));
  }
  sort(piis.begin(), piis.end());
  for (auto p : piis) {
    print(p);
  }

  cout << "---------------" << 'n';
  sort(piis.begin(), piis.end(), greater<>());
  for (auto p : piis) {
    print(p);
  }

  return 0;
}

(1, 2)
(1, 2)
(3, 4)
---------------
(19, -89)
(58, -105)
(64, 0)
(88, -68)
(114, -88)
(118, -46)
---------------
(118, -46)
(114, -88)
(88, -68)
(64, 0)
(58, -105)
(19, -89)

#include 
#include 
#include 
using namespace std;

int main() {
  vector< pair > piis;
  for (int i = 0; i < 6; ++i) {
    piis.emplace_back(make_pair(rand() % 123, - rand() % 123));
  }
  sort(piis.begin(), piis.end());
  for (auto [x, y] : piis) {
    cout << x << ' ' << y << 'n';
  }
  return 0;
}

19 -89
58 -105
64 0
88 -68
114 -88
118 -46

#include 
#include 
#include 
#include 
using namespace std;

int main() {
  tuple tiii (1, 2, 3);
  auto tiisc = make_tuple(1, 2, "3", '4');

  auto [x, y, z] = tiii;
  cout << x << ' ' << y << ' ' << z << 'n';

  auto [a, b, s, c] = tiisc;
  cout << a << ' ' << b << ' ' << s << ' ' << c << 'n';


  return 0;
}

1 2 3
1 2 3 4

#include 
#include 
#include 
#include 
using namespace std;

int main() {
  tuple tiii (1, 2, 3);
  cout << get<1>(tiii) << 'n';
    // 2
  return 0;
}

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 4, 1, 2, 3, 4, 4, 9, };
  set S;
  int n = sizeof arr / sizeof arr[0];
  for (int i = 0; i < n; ++i) S.insert(arr[i]);

  for (set::iterator it = S.begin(); it != S.end(); ++it)
    cout << *it << ' ';
  cout << 'n';

  for (auto it = S.rbegin(); it != S.rend(); ++it)
    cout << *it << ' ';
  cout << 'n';


  set::iterator l_pos = S.lower_bound(3);
  cout << "lower_bound(3) = " << *l_pos << 'n';

  set::iterator r_pos = S.upper_bound(3);
  cout << "upper_bound(3) = " << *r_pos << 'n';

  S.erase(1);
  S.erase(S.find(2));
    // 除了这两种，如果是 set.erase(l, r) 将会删除值在这个区间内的全部值

  cout << (S.count(3) ? "Find 3." : "Not find 3.") << 'n';
    // 如果存在 3 返回 true
    
  for (int s : S)
    cout << s << ' ';
  cout << 'n';
  return 0;
}

1 2 3 4 9
9 4 3 2 1
lower_bound(3) = 3
upper_bound(3) = 4
Find 3.
3 4 9

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 4, 1, 2, 3, 4, 4, 9, };
  set> S;
  int n = sizeof arr / sizeof arr[0];
  for (int i = 0; i < n; ++i) S.insert(arr[i]);

  for (set::iterator it = S.begin(); it != S.end(); ++it)
    cout << *it << ' ';
  cout << 'n';

  set::iterator l_pos = S.lower_bound(3);
  cout << "lower_bound(3) = " << *l_pos << 'n';

  set::iterator r_pos = S.upper_bound(3);
  cout << "upper_bound(3) = " << *r_pos << 'n';

  for (int s : S)
    cout << s << ' ';
  cout << 'n';
  return 0;
}

9 4 3 2 1
lower_bound(3) = 3
upper_bound(3) = 2
9 4 3

#include 
#include 
using namespace std;

struct myDS {
  myDS(int _x, int _y) : x(_x), y(_y) {}
  int x, y;
};

struct comp {
  bool operator() (const myDS&a, const myDS& b) const {
    return a.x * 5e5 + a.y < b.x * 5e5 + b.y;
  }
};

int main() {
  set S;
  S.insert({ 1, 2 });
  S.insert({ 2, 2 });
  for (myDS it : S)
    cout << it.x << " " << it.y << 'n';
  return 0;
}

1 2
2 2

#include 
#include 
using namespace std;
int main() {
  int arr[] = { 1, 2, 3, 4, 4, 1, 2, 3, 4, 4, 9, };
  multiset S;
  int n = sizeof arr / sizeof arr[0];
  for (int i = 0; i < n; ++i) S.insert(arr[i]);

  auto pos = S.equal_range(3);

  cout << "lower_bound(3) = [" << *(pos.first) << ", " << *(pos.second) << "]" << 'n';

  S.erase(1);
  S.erase(S.find(2));

  cout << (S.count(3) ? "Find 3." : "Not find 3.") << 'n';

  for (int s : S)
    cout << s << ' ';
  cout << 'n';
  return 0;
}

lower_bound(3) = [3, 4]
Find 3.
2 3 3 4 4 4 4 9

#include 
#include 

1 -1
2 -2
3 -3
4 -4
5 -5
map.find(3)->first = 3
mp.upper_bound(3)->first4
****************
5 -5
4 -4
3 -3
2 -2
1 -1
****************
4 -4
3 -3
2 -2
1 -1
****************
1 2
2 7
3 1
4 1

#include 
#include 

999999: 3
1234567890: 2
234567894564: 3

#include 
#include 

// map
Running time is: 9745ms
// unordered_map
Running time is: 4954ms

#include 
#include 

(6 -1) 2
(45 -1) 1
(78927 -1) 1
(4 -1) 1
(3 -1) 1
(9999 -1) 2
(2 -1) 1
(49999 -1) 1
(1 -1) 1

#define  all(c) c.begin(),  c.end()
#define rall(c) c.rbegin(), c.rend()
#define pub emplace_back
#define mkp make_pair
#define fi first
#define se second

typedef double db;
typedef complex cp;
typedef pair pii;