【c++ primer 笔记】第9章 顺序容器

❄️9.1 顺序容器概述

• 顺序容器（sequential container）：为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。
• 顺序容器都提供了快速顺序访问元素的能力。
• 所有容器都提供高效的动态内存管理

顺序容器类型

• vector\deque\string\array 都是顺序存储结构。 list 是链式存储结构。但是他们都是顺序容器
• farward_list 没有 size 操作
• array 是一种比内置数组更好的类型。
• list 的额外内存开销相比其他大很多。

容器的选择

• 通常使用vector是最好的选择，除非你有很好的理由选择其他容器。
• 如果有很多小的元素且空间开销很重要，不用 list
• 如果需要在中间位置插入/删除，用 list或forward_list
• 如果需要在头尾位置插入/删除，用 deque
• 如果需要随机访问，用 vector 或 deque

• 如果需要在中间位置插入，而后随机访问：

  • 如果可以通过排序解决，就像插到尾部，而后排序
  • 在输入阶段用 list ，输入完成后拷贝到 vector 中

❄️9.2 容器库概述

'类型别名'
iterator
const_iterator
value_type           // 容器元素类型。定义方式： vector<int>::value_type
reference            // 元素类型的引用。定义方式： vector<int>::reference
const_reference      // 元素的 const 左值类型
size_type
difference_type     //带符号整形，保存俩个迭代器之间的距离

'构造函数'-'三种通用的构造函数：同类拷贝、迭代器范围初始化、列表初始化'
C c1(c2);            // 拷贝构造函数，容器类型与元素类型必须都相同
C c1(c2.begin(),c2.end());   // 要求两种元素类型可以转换即可。
C c1{a,b,c,...};    // 使用初始化列表，容器的大小与初始化列表一样大

C c(n);             // 这两种接受大小参数的初始化方式只有顺序容器能用，且 string 无法使用
C c(n,t);

'赋值与swap'
c1 = c2;
c1 = {a,b,c,....}
a.swap(b);
swap(a, b);         // 两种 swap 等价

'大小'
c.size();
c.max_size();       // c 可以保存的最大元素数目，是整个内存层面的容量，不是已分配内存。不同于 caplity, caplity 只能用于 vector，queue，string
c.empty();

'添加/删除元素（不适用于array）'
c.insert(args);    // 将 args 中的元素拷贝进 c
c.emplace(inits);  // 使用 inits 构造 c 中的一个元素
c.erase(args);     // 删除指定的元素
c.clear();

'关系运算符'
==; !=; <; <=; >; >=   // 所有容器都支持相等和不等运算符。无序关联容器不支持大于小于运算符。

'获取迭代器'
c.begin(); c.end(); 
c.cbegin(); c.cend();  // 返回 const_iterator

'反向容器的额外成员'
reverse_iterator       // 逆序迭代器，这是一个和 iterator 不同的类型
const_reverse_iterator 
c.rbegin();c.rend();
c.crbegin();c.crend();

⛄️9.2.1 迭代器

• 迭代器范围是左闭右开,[begin(), end())
• begin()指向容器的第一个元素，end()指向容器最后元素的下一位，当begin() == end()则容器为空。
• 所有迭代器都可以递增，forward_list 不可以递减

vector<int>::iterator iter = vec.begin();   // 准确定义迭代器的方式。

'c++11新特性'
auto iter = vec.begin();

⛄️9.2.3 begin 和 end 成员

c.begin(); c.end();    // 返回 iterator
c.cbegin(); c.cend();  // 返回 const_iterator
c.rbegin();c.rend();   //反向迭代器，返回reverse_iterator
c.crbegin();c.crend(); //返回const_reverse_iterator

当不需要写访问时应该使用cbegin() 和 cend()

⛄️9.2.4 容器定义和初始化

将一个容器初始化为另一个容器的拷贝有俩种方法

1. 直接拷贝整个容器
2. 拷贝由一个迭代器对指定的元素范围

list<string> authors = {"hello", "world", "xdn"}
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors)   //正确类型匹配
deque<string> de(authors)     //错误，容器类型不匹配
vector<string> word(articles) //错误，元素类型不匹配
list<string> words(articles.begin(), articles.end());  // 正确， const char* 类型可以转换成 string类型

注意：

• 直接拷贝整个容器，要求俩个容器的类型以及元素的类型必须匹配
• 拷贝迭代器范围，不要求俩个容器的类型以及元素的类型必须匹配，只要元素可以进行转换就可以

array 初始化

• 定义array既要指定元素类型，还要指定容器大小

array<int,42>;              // 定义一个有42个int 的数组
array<int,42>::size_type;   // 定义数组类型也需要包括元素类型和大小

• 只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
• array具有固定大小。
• 和其他容器不同，默认构造的array是非空的。
• array 不支持普通容器的构造函数
• array 列表初始化时，列表元素个数小于等于 array 大小，剩余元素默认初始化为 0
• array 只能默认初始化或列表初始化，如果定义的数组很大并且需要初始化，可以先默认初始化然后用 fill 函数填充值。

array赋值

• 不能对内置数组拷贝或赋值，但是 array 可以。
• 使用一个 array 对另一个 array 赋值，需要两个array 元素类型与大小都相同。
• 不能用花括号列表对 array 赋值（只可以初始化）
• 要求俩个array的元素类型和大小都要一样

'数组'
int digs[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
int copy[10] = digs;    //错误,内置数组不支持拷贝或赋值

'array'
array<int, 10> ar = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
array<int, 10> br = ar; //正确，只要数组类型匹配即可

br = {0};                //错误，只能用花括号初始化，不能赋值

⛄️9.2.5 赋值和swap

• 下面操作适用于所有容器。除array外
• array 类型不支持assign操作，也不允许用花括号的值列表进行赋值，只能进行初始化。
• 对容器使用赋值运算符（除 array 外），将会使该容器的所有元素被替换。如果两个容器大小不等，赋值后都与右边容器的原大小相同。

使用assign(仅顺序容器)

• assign 是赋值操作，可以用于顺序容器。
• “=” 要求两边类型相同， assign 要求只要可以转换即可

lst.assign(vec.begin(), vec.end()); // 使用迭代器范围赋值
lst.assign(il);                     // il是一个花括号包围的元素值列表
lst.assign(n, t);                   // 将 lst 的元素替换为 n 个 t
'操作等价于'
lst.clear();
lst.insert(lst.begin(), n, t);

swap

• 对 array ，swap 交换两个 array 中的元素值。指针、引用和迭代器绑定的元素不变（值变）。
• 对于其他容器，swap 不交换元素，只交换数据结构，因此 swap 操作非常快。
• 对于 string，swap 后，指针、引用和迭代器会失效。对于其他容器，交换后指针指向了另一个容器的相同位置。迭代器并不失效
• 统一使用 swap(a,b)，而非 a.swap(b)
• 对于 array，swap 操作的时间与元素数目成正比，对于其他容器，swap 操作的时间是常数。

⛄️9.2.6 容器大小操作

• 所有的容器都支持上面操作，只有forword_list没有size()操作

俩个容器内的元素进行比较需要保证俩点

1. 俩个容器必须是相同类型的容器，并且保存相同类型的元素
2. 元素类型要支持关系运算符（例如你随便定义一个类类型，如果里面没有重载关系运算符，那么你这俩个类类型，不能进行比较）

❄️9.3 顺序容器操作

⛄️9.3.1 向顺序容器添加元素

• 注意向 vector、string 或 deque 插入元素会使所有指向容器的迭代器、引用和指针失效。

• 添加的都是元素的拷贝，不是元素本身。
• 头尾添加返回 void，中间添加返回指向新添加元素的迭代器

• 因为这些操作会改变大小，因此不适用于array。

push

• vector 和 string 不支持 push_front 和 emplace_front；
• forward_list 不支持 push_back 和 emplace_back；
• forward_list有自己专有版本的insert和emplace。

c.push_back(t);   // 尾部添加一个 t
c.push_front(t);  // 头部添加一个 t

insert

• insert 返回值是指向添加的元素中第一个元素的迭代器
• inset 是在迭代器指向的位置之前插入一个值
• emplace 函数在容器中直接构造元素，传递给emplace函数的参数必须与元素类型的构造函数相匹配，因此一般可以为空（默认初始化）。

emplace(c++ 11)

• 新标准引入三个新成员- emplace_front, emplace_back, emplace
• 当调用push 或insert成员函数时，是将元素拷贝到容器中，而emplace 则将参数传递给元素类型的构造对象。
• emplace 返回值是指向添加元素的迭代器

c.emplace_back(args);  // 在尾部添加一个由 args 构建的元素
c.emplace_front(args); // 在头部添加一个由 args 构建的元素
c.emplace(p,args);     // 在迭代器 p 所指元素之前添加一个由 args 构建的元素

⛄️9.3.2 访问元素

• 访问元素要确保容器非空，不然会出现错误
• at和下标操作只适用于string、vector、deque、array。

begin/end

• begin()/end() 返回迭代器

front/back

• front()/back() 返回元素的引用,可以对元素进行修改

c.front();
c.back();   //返回的是尾元素的引用（注意不同于尾后迭代器）

at

• at返回下标为 n 的元素的引用
• at可以快速随机访问的容器都可以使用下标。
• 使用下标一定要保证下标不越界，可以用 at 函数。当下标越界，at 函数会抛出一个 out_of_range 异常

c[n]
c.at(n);   //返回下标为 n 的元素的引用

auto 获得引用

• 如果要通过 auto 获得元素的引用，定义时一定要记得加上引用符号

c.front() = 42;        //将42赋予c中的第一个元素
auto &v = c.back();    //获取指向最后一个元素的引用
v = 1024;              //通过引用可以改变元素的值

auto v2 = c.back();    //v2不是一个引用，它是c.back()的一个拷贝
v2 = 0;                //未改变c中的元素

理解：

1. c.front() 返回的是引用，因此可以通过 c.front() = 32; 来给 c 的首元素赋值。
2. 而 auto b = c.front() 得到的 b 是等号右端元素的拷贝，不是引用

⛄️9.3.3 删除元素

• 头尾删除返回 void，特定位置删除返回被删除元素之后元素的迭代器
• vector/string 不支持 pop_front，forward_list 不支持 pop_back。
• forward_list 有自己特殊版本的 erase。

• 删除迭代器所指定的元素，返回一个指向被删除元素之后元素的迭代器

删除多个元素

c.clear();
c.erase(c.begin(), c.end());  // 和 c.clear() 等价

总结

• 删除之前要确保元素存在
• 删除 deque 种除首尾之外的任何元素都会使所有迭代器、引用和指针失效。
• 删除 vector 或 string 中的元素会使指向删除点之后位置的迭代器、引用和指针失效。
• 删除 list 中的元素不会影响指向其他位置的迭代器、引用、指针。

⛄️9.3.4 特殊的forward_list操作

• forward_list 是单向链表，添加和删除操作都会同时改变前驱和后继结点，因此一般的添加和删除都不适用于 forward_list
• forward_list定义了before_begin，即首前（off-the-begining）迭代器，允许我们再在首元素之前添加或删除元素。

• inster_after在迭代器p之后的位置上插入元素，返回的是一个指向最后一个插入元素的迭代器

⛄️9.3.5 改变容器大小

• resize() 用来增大或缩小容器。
• 如果要求的大小小于当前大小，尾部会被删除，如果要求的大小大于当前大小，会把新元素添加到尾部

• resize函数接收可选参数，用来初始化添加到容器中的元素，如果未提供此参数，新元素会值初始化。
• 假如容器保存的是类类型，且resize向容器添加元素，我们必须提供初始值，或者元素类型必须提供默认构造函数

总结

• 对于往容器插入元素（insert()),在迭代器p指向的元素之前，插入一个元素，返回指向新元素的迭代器
• 对于往容器删除元素（erase()）,删除迭代器p所指向的元素，返回一个指向删除元素之后的元素的迭代器
• 对于forward_list插入操作（insert_after()）,在迭代器p之后插入元素，返回一个指向最后一个插入元素的迭代器。
• 对于forward_list删除操作（erase_after()）, 删除迭代器p之后的元素，返回一个指向被删除元素之后元素的迭代器
• 值初始化：对于容器而言，可以只提供元素个数而省略初始值，此时库会创建一个值初始化元素初值，并把它赋给容器中的所有元素。这个值初始化有容器当中元素类型决定（例如int，容器自动初始化为0，string容器自动初始化为空字符串）

⛄️9.3.6 容器操作可能使迭代器失效

• 添加和删除元素都可能使指针、引用、迭代器失效。使用失效的指针、引用、迭代器是很严重的错误。

• 在向容器添加元素后：

  • 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针、引用都会失效。
  • 对于deque，插入到除首尾位置之外的任何位置都会导致指向容器的迭代器、指针、引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在元素的引用和指针不会失效。
  • 对于list和forward_list，指向容器的迭代器、指针和引用依然有效。

• 在从一个容器中删除元素后：

  • 对于list和forward_list，指向容器其他位置的迭代器、引用和指针仍然有效。
  • 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、指针、引用都会失效；如果是删除deque的尾元素，则尾后迭代器会失效，但其他不受影响；如果删除的是deque的头元素，这些也不会受影响。
  • 对于vector和string，指向被删元素之前的迭代器、引用、指针仍然有效。

编写改变容器的循环程序

• 必须保证每次改变容器后都更新迭代器。
• insert 和 erase 都会返回迭代器，更新很容易。调用 erase 后，不需要递增迭代器，调用 insert 后，需要递增两次。

不要保存 end() 返回的迭代器

• push、pop、首尾 emplace 操作都没有返回值，但是都会改变尾后迭代器，因此不能保存 end() 返回值。
• for 循环判断条件中的 end() 每轮都会重新获取迭代器进行判断，因此不用担心（也因此速度会略慢，当不改变容器大小时，采用下标更快）

❄️9.4 vector对象是如何增长的

• vector和string在内存中是连续存储的，为了避免每添加一个元素就要重新分配一次空间，在每次获取新的内存空间时，vector和string通常会分配比新空间需求更大的内存空间。容器预留这些空间作为备用，可以保存新的元素。
• 虽然每次重新分配需要移动所有元素，但是其扩张操作通常比list和deque快

管理容量的成员函数

• shrink_to_fit只适用于vector、string和deque
• capacity和reverse只适用于vector和string。

注意

• c.reserve(n) 不会减小容量，只会增大容量，当需求容量大于当前容量，才会分配内存，否则什么都不做。
• c.resize(), 只改变容器中元素的数目，并不改变容器的容量
• c.shrink_to_fit() 只是一个请求，实现时标准库可能会不执行。

capacity和size

• capacity表示不分配新的内存空间前提下它最多保存多少元素
• size是指它已经保存元素的数目。

❄️9.5 额外的string操作

• 除了与顺序容器共同的操作之外，string提供了一些额外的操作。主要用于c风格字符串和下标访问,允许用下标代替迭代器。

⛄️9.5.1 构造string的其他方法

• string 的构造函数可以接受一个 string 或 const char* 参数用来指定开始位置，然后接受一个计数值用来指定范围。
• 当用const char *创建string时，指针指向的数组必须是以空字符串结尾，拷贝操作遇到空字符串时停止。
• 如果传递的是string对象，那么可以提供一个可选位置和一个计数值
• 如果传递的是数组对象,那么如果传递了数组，并且加上计数值，那么数组就不需要以空字符串结尾，否则没有计数值的话，会出现未定义错误。

const char *cp = "hello world!!!"   //以空字符串结束的数组
char a[] = {'H', 'W'};             //不是以空字符串结束的数组

string s1(cp);        //正确，一空字符串结尾
string s2(a);         //错误，不是空字符串结尾，而且也没有提供计数值
string s3(a, 2);      //正确

string s4(cp + 6, 5)  //正确,从cp[6]开始拷贝，拷贝85个字符
string s5(s1, 6, 5)   //正确，对象时string,从下标6的位置开始，拷贝5个字符   

substr

• s.substr(pos,n) 返回 s 的一部分或全部拷贝，范围由参数指定。

string s2 = s1.substr(0,5);  // 返回从下标 0 开始，长度为 5 的子序列
string s2 = s1.substr(6);    // 返回从下标 6 开始到最后的子序列

总结

• 所有的拷贝或者substr有四种情况：

  1. 括号中俩个参数(p, n)，p + n没有超过string大小，分别是从下标p位置，拷贝n个字符
  2. 括号中俩个参数(p, n)，p + n超过string大小，此时会拷贝到字符尾部
  3. 括号中一个参数(p)，从下标p的位置，一直拷贝到最后
  4. 括号中一个参数，但是该参数超过了string的值，此时会抛出异常

⛄️9.5.2 改变string的其他方法

string 支持顺序容器的 assign、insert、erase 操作，此外还增加了两个额外的操作

1. 接受下标版本的 insert 和 erase
2. 接受 C 风格字符数组的 insert 和 assign
3. append 和 replace 函数

接受下标的 insert 和 erase

• insert 和 erase 接受下标的版本返回的是一个指向 s 的引用（区别于迭代器版本返回指向第一个插入字符的迭代器）。
• insert 的所有版本都是第一部分参数为 pos，后面的参数为待插入的字符
• erase 的所有版本的参数都是 pos，pos 分为 起始位置 和 终止位置/长度

s.insert(s.size(), 5, '!');       // 在 s 末尾（s[s.size()]之前）插入 5 个感叹号，注意实际上不存在 s[s.size()];
s.insert(0, s2, 3, s2.size()-3);  // 在 s[0] 之前插入 s2 第四个字符开始的 s2.size()-3 个字符
s.erase(s.size()-5, 5);           // 从 s 删除最后 5 个字符

接受 C 风格字符数组的 insert 和 assign

• assign 的所有版本的参数都是要赋的值，由 起始位置 + 终止位置/长度 组成
• replace 的所有版本的参数都是第一部分参数为要删除的范围，第二部分为要插入的字符。

const char* cp = "stately,plump Buck";
s.assign(cp, 7);             // 用从 cp 开始的前 7 个字符向 s 赋值
s.insert(s.size(), cp+7);    // 将从 cp+7 开始到 cp 末尾的字符插入到 s 末尾

append 和 replace

• append：在 string 末尾进行插入操作。
• replace：等价于调用 erase 和 insert 操作。

s.append(" 4th Ed.");        // 等价于 s.insert(s.size()," 4th Ed.");

s.erase(11, 3);
s.insert(11, "5th")        //等价于
s.replace(11, 3, "5th");   // 从下标 11 开始，删除三个字符并插入 3 个新字符

⛄️9.5.3 string搜索操作

• string类提供了6个不同的搜索函数，每个函数都有4个重载版本。
• 每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos的static成员（类型是string::size_type，初始化值是-1，也就是string最大的可能大小）。

注意：

• find 和 rfind 查找的是给定的整个 args，而剩下的查找的是给定的 args 中包含的任意一个字符。

s.find(args);               // 查找 s 中 args 第一次出现的位置
s.rfind(args);              // 查找 s 中 args 最后一次出现的位置
s.find_first_of(args);      // 查找 s 中 args 的任意一个字符第一次出现的位置
s.find_last_of(args);       // 查找 s 中 args 的任意一个字符最后一次出现的位置
s.find_first_not_of(args);  // 查找 s 中第一个不在 args 中的字符
s.find_last_not_of(args);   // 查找 s 中最后一个不在 args 中的字符

'args为以下形式'
c,pos         // 字符，pos 为搜索开始位置(    从s中位置pos开始查找字符c。pos默认是0)
s2,pos       // 字符串(    从s中位置pos开始查找字符串s。pos默认是0)
cp,pos       // 以空字符结尾的 c 风格字符串(从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串。pos默认是0)
cp,pos,n     // c 风格字符串的前 n 个字符(    从s中位置pos开始查找指针cp指向的前n个字符。pos和n无默认值。)

使用 pos 循环查找所有 str 包含的字符的位置

string::size_type pos = 0;
while((pos=s.find_first_of(str,pos)) != string::npos ){
    cout << pos << endl;
    ++pos;}

⛄️9.5.4 compare 函数

• 逻辑类似于C标准库的strcmp函数，根据s是等于、大于还是小于参数指定的字符串
• 俩个string对象比较或者一个string对象一个字符数组, 可以比较整体或一部分字符串
• s.compare返回0、正数或负数。

int cmp = s.compare(s2);
int cmp = s.compare(pos1,n1,s2);          // 将 s 中 pos1 开始的前 n1 个字符与 s2 比较
int cmp = s.compare(pos1,n1,s2,pos2,n2);  // 将 s 中 pos1 开始的前 n1 个字符与 s2 中从 pos2 开始的 n2 个字符进行比较
int cmp = s.compare(cp)                   // 将 s 与 cp 指向的字符数组比较
int cmp = s.compare(pos1,n1,cp);
int cmp = s.compare(pos1,n1,cp,n2);

⛄️9.5.5 数值转换

例子

string s2 = "pi = 3.14";
double d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
// 先使用查询方法找出第一个数值字符(因为+ - . 0 1 2在s2中都不存在，所以继续找下一个为3，此时3在s2中是下标为5的位置)，返回5，就变成了stod(s2.substr(5)),将字符串从下标为5的位置一直到结束，转换成double类型

❄️9.6 容器适配器

• 标准库定义了三个顺序容器适配器:stack、queue、priority_queue。
• 容器，函数，迭代器都有适配器
• 适配器是一种机制，是某种事物的行为看起来像另一种事物。

适配器的通用操作和类型

size_type;
value_type;
container_type;  // 实现适配器的底层容器类型。

A a;             //创建一个名为a的空适配器
A a(c)           //创建一个名为a的适配器，带有容器c的一个拷贝
关系运算符        //每个适配器都支持所有关系运算符：==、!=、<、 <=、>、>=这些运算符返回底层容器的比较结果
a.empty()       //若a包含任何元素，返回false;否则返回true
a.size()        //返回a中的元素数目
swap(a, b)      //交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同
a.swap(b)       //同上

• 所有适配器要求容器具有添加和删除元素的能力，因此array不能当适配器

初始化操作

• 默认情况下，stack 和 queue 是基于 deque 实现的， priority_queue 是在 vector 之上实现的。
• 因此可以直接用一个 deque 来初始化 stack 和 queue。注意：是直接使用容器对象，不是使用迭代器表示的范围。
• priority_queue 不能使用无序的 vector 初始化。

deque<int> deq;
stack<int> sta(deq);  // 用 deq 初始化 sta

如果要使用其他顺序容器实现适配器，要在创建适配器时用一个顺序容器作为第二个类型参数。

stack<int, vector<int>> sta;  // 定义基于 vector 实现的 stack

总结

• stack 可以构造于 vector, list, deque 之上。
• queue 可以构造于 list, deque 之上。
• priority_queue 可以构造于 vector、deque 之上。

栈适配器：stack

s.pop();
s.push(item);
s.emplace(args);  // 由 args 构造元素并压入栈顶
s.top();
s.size();
s.empty();
swap(s, s2); s.swap(s2);

队列适配器：queue

q.pop();          // 删除 queue 的首元素
q.push(item);     // 在 queue 末尾插入一个元素
q.emplace(args);  // 构造元素

q.front();        // 返回首元素
q.back();         // 返回尾元素。

q.size();
q.empty();
swap(q,q2);q.swap(q2);

• queue 为先进先出队列。
• queue 和 priority_queue 都定义在头文件 queue 中。

优先队列：priority_queue

• 创建 stack, queue, priority_queue 时都可以用一个顺序容器作为第二个类型参数，此外创建 priority_quque 时还可以额外传递第三个参数：一个函数对象来决定如何对 priority_queue 中的元素进行排序。

大根堆和小根堆

• priority_queue 默认采用的是 less ，默认情况下 q.top() 是最大的元素，即大根堆。

 priority_queue <int> q;      // 默认采用 vector 作为容器，采用 less<Type> 比较元素，是大根堆
 priority_queue <int, vector<int>, greater<int> > q;  // 采用 greater<Type> 比较元素，生成小根堆

其他操作：

q.pop();          // 删除 priority_queue 的最高优先级元素
q.push(item);     // 在 priority_queue 适当的位置插入一个元素
q.emplace(args);  // 构造元素
q.top();          // 返回最高优先级元素
q.size();
q.empty();
swap(q, q2); q.swap(q2);

• priority_queue 为元素建立优先级。新加入的元素排在所有优先级比它低的元素之前。priority_queue 元素可以重复
• priority_queue 不能使用无序的 vector 初始化。