本章记录STL相关内容,记录STL概述，顺序容器，后边会依次介绍关联容器，无序容器，迭代器，算法，tuple, string 函数对象等。

第8章 C++STL

8.1 STL总述、发展史、组成与数据结构谈

8.1.1几个概念与推荐书籍

1.C++标准库

英文名字是C++Standard Library。一般来讲,只要安装了C++编译器(如VisualStudio2019),那么,这些标准库都会被安装进来,这样就可以在程序中使用这些标准库里提供的各种功能。例如已经很熟悉的vector容器等,都是标准库里面提供的。

2.标准模板库

这个词相信很多读者都熟悉,英文名字是Standard Template Library(STL)。包含在C++标准库之中,作为C++标准库的一个重要组成部分或者说是C++标准库的核心,深深影响着标准库。

3.泛型编程

英文名字是 Generic Programming。
所谓泛型编程,是使用模板(Template)为主要的编程手段来编写代码(模板在前面已经详细学习过)。可以认为,标准模板库就是用泛型编程的编码方式所写的一套供程序员非常方便使用的库。

8.1.2算法和数据结构关系

C++中标准库中的容器底层原理都是数据结构与算法，下面分别讲解每种容器的底层实现。

8.1.3 STL发展史和各个版本

STL的实现有很多版本,例如:
(1) HPSTL:惠普STL,是所有STL实现版本的始祖。
(2) SGISTL:参考惠普STL实现出来,Linux下的GNUC++(gcc、g++)用的就是这个。
(3) P,J.Plauger STL:参考惠普STL实现出来,Visual C++(包括笔者所用的 VisStudio 2019 中的 C++开发环境)一般使用这个(打开iostream 文件在底下能看到P.!Plauger 字样)。

8.1.4标准库的使用说明

包含命名空间。

using namespace std;

8.1.5 ST的组成部分

C++标准库非常庞大,而标准模板库STL作为C++标准库的重要组成部分是本章讲解的核心内容。

1.容器

最常用的vector、map、list等。前面详细讲解过vector 容器。

2.迭代器

用于遍历或访问容器中的元素。前面也详细讲解过迭代器,类似一个指针,选代器一般服务于容器。多数情况下,每种容器也都会提供适合自己的迭代器。

3.算法

算法可以理解成STL提供的一些函数,用来实现一些功能,例如查找用到search,排序用到sort,复制用到copy等。这种算法大概也有数十上百个,是否常用取决于具体项目和程序员的开发习惯。

4.分配器

分配器一般不太常用。前面在内存高级话题学习到内存池时,说到内存池存在的主要意义是针对频繁分配小块内存时,减少内存空间的浪费,并有一定的提升分配内存效率的作用。所以,分配器也有这个作用,只不过一般来讲使用的都是默认分配器,不需要程序员明确指定。这里谈的分配器应该叫作内存分配器,是服务于容器的。当在main主函数中输人vector<int, _Alloc=allocator…> 字样就是分配器。

8.1.6 容器的三种分类

STL 容器一般分三类。
顺序容器：放入的时候在哪里，就在哪里。比如，array,vector,deque,list,forward_list
关联容器：每个元素是键值(key value)方式存储，根据key把这个元素自动添加到容器某个位置。内部使用树形结构存储。根据key，自动存放在一个合适的位置。比如,set,multiset,map,multimap。
无序容器：这是C++11引入的，这也应该属于是关联容器，常用的无需容器，unordered_set, unordered_map, unordered_multiset, unordered_multimap。
下面依次讲解顺序容器，关联容器和无序容器。

8.2顺序容器

顺序容器是说，这些容器底层的数据结构是线性结构。

8.2.1 array

C++中的array是对C数组的包装，是一个大小固定的数组，空间连续，大小固定，不能动态增加大小。
C++中的array与C数组对比：
1 存储与开销
std::array：元素内联、连续存储，sizeof(std::array<T,N>) == sizeof(T)N，无额外开销。
C 数组：同样连续存储。
2 语义与可用性
std::array：可复制/赋值/返回；有成员函数（size(), data(), begin()/end()），可与 STL 算法协同；at() 有越界检查；array当函数参数时，不会隐式退化为指针。
C 数组：不能整体赋值或作为返回值（需要包装或使用指针）；作为函数参数，很容易衰变为指针，丢失长度信息。
3 接口互通
使用array时，需要 C 接口时，用 arr.data() 获取 T，再配合 arr.size() 传长度即可。

	void test()
	{
		array<string, 5> myarray = { "I","Love","China" };
		myarray[3] = "I love china";
		myarray[4] = "I love china";
		for (int i = 0; i < 5; ++i)
		{
			const char* p = myarray[i].c_str();
			cout << myarray[i] << endl;
			printf("数组地址为： =  %p\n", &myarray[i]);
			printf("字符串地址为： =  %p\n", p);
		}
		cout << myarray.size() << endl;
	}

8.2.2 vector

8.2.2.1内部实现

代码实现时候，vector有三个指针，first指向第一个元素；last指向最后一个元素的后继位置；end指向数组元素的最后一个位置的后继。

8.2.2.2 工作中使用的方法总结

增加元素：push_back(20) ,insert(it,20)

vec.push_back(20), 在容器的末尾添加元素，时间复杂度O(1)，在末尾插入元素可能导致扩容。扩容会带来性能开销，假如vector中存放的是对象，扩容后，要将之前元素的内容进行拷贝构造，然后再析构掉之前的元素，最后将之前的内存释放掉。

其中，对象的构造和析构都是通过空间适配器实现的，空间适配器的四个方法，
allocate
deallocate
construct
destroy
通过迭代器方式，向vector中指定的位置插入元素，这可能导致元素的移动，时间复杂度是O(n)。

删除元素：pop_back(), vec.erase(it)

从数组末尾删除元素，pop_back()；
从数组的指定位置删除元素，vec.erase(it);

查询元素

vec[5]，访问第5个元素，通过运算符重载[]实现，时间复杂度O(1)；
iterrator方式，推荐方式
find
foreach, 底层也是通过调用迭代器实现。

迭代器的失效问题

对容器进行连续的insert和erase之后，迭代器就会失效。一定要更新迭代器，否则出错。更新方式如下：
当插入元素时候，要让迭代器++两次，
当删除元素时候，迭代器不用++，直接从当前位置继续向后遍历即可。

常用方法：size(), empty(), reserve(), resize(), swap()

size() : 获取vector中数据元素的数量。
empty() ：查看vector是否为空。
reserve()方法预留出空间，避免的频繁扩容带来的消耗。
resize(): 设置vector的大小，同时添加元素。默认是int()，添加的是0.
swap() 两个容器元素进行交换。
reserve()方法预留空间
reserve之后，可以使用push_back()方法，但是不能直接使用[]运算符插入。

    vector<int> vec;
    vec.reserve(5);         // 预留出空间，可以使用push_back()，不能使用 [] 运算符直接插入，下面这样是错误的，默认从0号位置开始插入。
    cout << vec.size() << endl;     // 0
    cout << vec.capacity() << endl; // 5 
    vec.push_back(1);
    vec.push_back(2);
    // vec[2] = 3;             // 这是错误的；
    cout << vec.size() << endl;  // 3 
    cout << vec.capacity() << endl; // 5

resize()对数组进行扩充

resize() 可以对数组进行扩充。使用resize(8)之后，直接使用[]。如果使用Push_back()出现如下情况，将数据直接添加到了第9个位置。

找最值和索引std::max_element

std::max_element找最大值。传入的两个参数分别是开始索引和结束索引，返回最大值位置。然后使用std::distance可以找出索引。

	vector<int> vec{ 1,2,3,54 };
    int* p = &vec[0];
    cout << p[0] << endl;
    cout << p[1] << endl;
    cout << p[2] << endl;
    cout << p[3] << endl;
    std::vector<int>::iterator it = std::max_element(vec.begin(), vec.end());
    int index = std::distance(vec.begin(), it);
    cout << index << endl;

清空vector

下面方式清空vector后，size和capacity() 都为0

vector v{ 2, 3, 5, 7, 11 };
vector().swap(v);

std::copy() std::copy_if() std:: back_inserter

std::back_inserter 是在 C++98 中引入的; 通常用于与标准库算法一起使用，例如 std::copy、std::transform 等，std::back_inserter 返回一个特殊的插入迭代器，可以在容器的末尾插入新的元素。
调用了std::back_inserter方法。
copy_if() ，对复制的每个元素使用lambda表达式进行处理。

void testvec()
{
        std::vector<int> vec1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        std::vector<int> vec2{10,20};  // 这里不能直接写成vec2(vec1.size()),因为 std::back_inserter(tTacho) 从末尾插入
        std::vector<int> vec3;
        int tmp = 5;
        std::copy(vec1.begin(), vec1.end(), std::back_inserter(vec2));
        // std::copy_if(tDiff.begin(), tDiff.end(), std::back_inserter(tTacho), [xDiff](double val) { return val == 2; });
        for (auto v : vec2)
        {
            cout << v << " ";
        }
        cout << endl;	// 10 20 1 2 3 4 5 6 7 8 9
		std::copy_if(vec1.begin(), vec1.end(), std::back_inserter(vec3), [tmp](int val) {return val > tmp; });

	for (auto v : vec3)
	{
		cout << v << endl;
	}
}

std::lower_bound 和 upper_bound

lower_bound 和 upper_bound 区别
std::lower_bound 和 std::upper_bound 都是在已排序的序列中进行二分查找，但它们的行为略有不同：
• std::lower_bound(first, last, value) 返回一个迭代器，指向在范围 [first, last) 中第一个不小于（即大于或等于）value 的元素。如果所有元素都小于 value，那么返回的迭代器将指向范围的末尾。
• std::upper_bound(first, last, value) 返回一个迭代器，指向在范围 [first, last) 中第一个大于 value 的元素。如果所有元素都不大于 value，那么返回的迭代器将指向范围的末尾。
这两个函数都假设序列已经按升序排序。如果序列没有排序，那么这两个函数的结果可能是不正确的。
例如，对于一个升序序列 {10, 20, 30, 40, 50}：
• lower_bound 对于 value = 30，返回的迭代器指向 30。
• upper_bound 对于 value = 30，返回的迭代器指向 40。
这是因为 30 是序列中第一个不小于 30 的元素，而 40 是序列中第一个大于 30 的元素。

swap 原理

如果两个容器，进行交换操作
swap只是交换了两个容器的成员变量的指针。
如果两个容器用的空间适配器allocator相同，直接交换两个容器的指针，效率高。
如果不同，再进行开辟数组，交换操作。

erase() 删除从指定位置到末尾的所有元素

		auto it = std::upper_bound(candidates.begin(), candidates.end(), target);
		candidates.erase(it, candidates.end());

寻找vector中的最大值和最小值

	double minValue = *std::min_element(veckey.begin(), veckey.end());
	double maxValue = *std::max_element(veckey.begin(), veckey.end());

项目中的使用：

std::max_element(result->cmsfftResult.multi_rotor_amp.begin(), result->cmsfftResult.multi_rotor_amp.end());

函数原型：

template< class ForwardIt >
ForwardIt max_element( ForwardIt first, ForwardIt last );

自定义比较器：

template< class ForwardIt, class Compare >
ForwardIt max_element( ForwardIt first, ForwardIt last, Compare comp );

函数参数说明
· first, last: 定义要搜索的元素范围的迭代器（半开区间 [first, last)）
· comp: 二元比较函数对象，定义排序准则（可选）
返回值
返回指向范围中最大元素的迭代器。如果有多个元素等于最大值，则返回第一个这样的元素。如果范围为空，则返回last。

transform() 使用

transform 处理已经给出的容器，接受一个输入范围，这个范围由两个迭代器指定，还接受一个输出迭代器，以及一个函数对象。
下面的例子中：将nums中的每个元素的值取平方得到 每个值的平方。

void testTransform()
{
	std::vector<int> nums = { 1, 2, 3, 4, 5 ,8,9,10 };
	std::transform(nums.begin(), nums.end(), nums.begin(), [](int i) {return i * i; });

	for (int v : nums)
	{
		cout << v << " ";
	}
	// 1 4 9 16 25 64 81 100
	return;
}

注意：使用 transform() 时不能使用reserve() 函数，可以使用resize() 函数。

void testTransform()
{
	std::vector<int> nums = { 1, 2, 3, 4, 5 ,8,9,10 };
	std::vector<int> nums2;
	//nums2.reserve(10);  // 错误
	nums2.resize(10);  //
	int size = nums2.size();		// size = 10
	int cap = nums2.capacity();		// cap = 10

	std::transform(nums.begin(), nums.end(), nums2.begin(), [](int i) {return i * i; });
	// 

	for (int v : nums)
	{
		cout << v << " ";
	}
	// 1 4 9 16 25 64 81 100
	return;
}

transform 比 for的优点：

1. 代码简洁：std::transform可以在一行代码中完成循环和操作，使代码更简洁，更易于阅读。
2. 抽象级别更高：std::transform隐藏了循环的细节，让你可以专注于你想要对每个元素执行的操作。
3. 更容易优化：编译器可能会对std::transform进行优化，例如自动并行化，这是手动循环难以做到的。
4. 更容易测试和重用：你可以将操作封装在一个函数或函数对象中，然后传递给std::transform，这样你就可以在其他地方重用这个函数，并且可以独立地测试它。
   transform() 不确定 输出迭代器大小，可以使用std::back_inserter()

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2;
std::transform(v1.begin(), v1.end(), std::back_inserter(v2), [](int i) { return i * i; });

generate()

std::generate函数是C++标准库中的一个算法，它可以用来填充一个范围内的元素。第一个参数是开始迭代器，第二个参数是结束迭代器，第三个参数是一个Lambda表达式，用来表示

void testGenerate()
{
	std::vector<double> v(10);
	double i = 0;
	std::generate(v.begin(), v.end(), [&i]() ->double {i++; return i / 120; });
	for (double v1 : v)
	{
		cout << v1 << " ";
	}
	// 0.00833333 0.0166667 0.025 0.0333333 0.0416667 0.05 0.0583333 0.0666667 0.075 0.0833333
	return;
}

generate() 和 transform() 区别

Transform 要一起定义好一个输入序列，将第四个lambda函数应用于输入序列中的每个元素。这个函数是可以任何可以接受输入序列元素类型的函数，并返回一个可以存储在输出序列中的值。

std::vector<int> nums = {1, 2, 3, 4, 5};
std::vector<int> squares;
std::transform(nums.begin(), nums.end(), std::back_inserter(squares), [](int i) { return i * i; });

std::generate：这个算法接受一个输出序列和一个函数（或函数对象），然后将这个函数的结果存储在输出序列的每个元素中。这个函数不接受任何参数，所以它通常用于生成一个序列，例如生成一系列的随机数或生成一个递增的序列。

std::vector<int> nums(5);
std::generate(nums.begin(), nums.end(), [n = 0]() mutable { return n++; });

总的来说，std::transform用于基于一个现有序列的元素生成新的元素，而std::generate用于生成一个全新的序列。

8.2.2.3 vector的insert方法总结

insert有多重重载版本，下面分别总结每个重载版本的用法。

1 在指定位置插入元素

下面的例子中，使用insert方法插入元素，在指定的位置插入一个值，并返回新插入的元素位置的迭代器。
如果要插入的元素是一个类，可以使用std::move() 移动语义将资源转移到vector中。

	iterator insert(iterator pos, const T& value);  // C++03
	iterator insert(const_iterator pos, const T& value);  // C++11
	参数1：迭代器
	参数2：value值
	返回值：返回插入新元素位置的迭代器

	std::vector<int> vec = { 1,2,3,4 };
	std::vector<int>::iterator it = vec.begin();
	// 在第二个元素后插入元素5 
	std::vector<int>::iterator it2 = vec.insert(it + 1, 5);  
	// 	it2指向 5的位置 		
	// 输出：1 5 2 3 4		
	for (auto i : vec)
	{
		qDebug() << i << " ";
	}
	// 使用移动语义插入元素
	std::string s = "world";
	std::vector<std::string> vecStr = { "hello" };
	vecStr.insert(vecStr.begin(), std::move(s));  
	// 输出：world hello
	// 插入后，s的值变为未定义

2 在指定位置插入多个相同元素

	iterator insert(iterator pos, size_type count, const T& value);  // C++03
	iterator insert(const_iterator pos, size_type count, const T& value);  // C++11
	作用：在pos位置插入count个value值
	参数1：迭代器位置
	参数2：插入元素个数
	参数3：插入元素值
	返回值：返回插入新元素位置的迭代器
	例子：在第二个元素位置插入3个5；在末尾插入2个3；
	std::vector<int> vec = { 1,2,3,4 };
	vec.insert(vec.begin() + 1, 3, 5);  // 在第二个元素后插入3个5
	vec.insert(vec.end(), 2, 3);  // 在末尾插入2个3
	// 输出：1 5 5 5	2 3 4		3 3

3 向vector中插入一个范围内的元素

举例：在vector中一个范围内的元素，将另一个vector中的元素插入到vector中；
将一个 int arr[]数组中的元素插入到vector中。

	template <class InputIt>
	iterator insert(iterator pos, InputIt first, InputIt last);  // C++03

	template <class InputIt>
	iterator insert(const_iterator pos, InputIt first, InputIt last);  // C++11

	作用：在pos位置插入[first, last)范围内的元素
	参数1：迭代器位置
	参数2：插入元素的起始迭代器
	参数3：插入元素的结束迭代器
	返回值：返回插入新元素起始位置的迭代器

std::vector<int> vec1 = { 1,2,3,4 };
std::vector<int> vec2 = { 5,6,7,8 };

// 在vec1末尾插入vec2的元素
auto it = vec1.insert(vec1.end(), vec2.begin(), vec2.end());
qDebug() << *it;  // 输出：5
// 输出：1 2 3 4 5 6 7 8


// 从数组中插入元素
int arr[] = { 9,10,11,12 };
vec1.insert(vec1.end(), arr, arr + 4);
for (auto i : vec1)
{
	qDebug() << i << " ";
}
// 输出：1 2 3 4	 5 6 7 8	9 10 11 12

4 在指定位置插入初始化列表中的元素

	iterator insert(const_iterator pos, std::initializer_list<T> ilist);
	作用：在pos位置插入初始化列表中的元素
	参数1：迭代器位置
	参数2：初始化列表
	std::vector<int> vec = { 1, 2, 3 };
	// 在第二个元素前插入初始化列表{4, 5, 6}
	vec.insert(vec.begin() + 1, { 4, 5, 6 });
	// 现在vec包含: {1, 4, 5, 6, 2, 3}

	// 在末尾插入多个元素
	vec.insert(vec.end(), { 7, 8, 9 });
	// 现在vec包含: {1, 4, 5, 6, 2, 3, 7, 8, 9}

5 使用 std::move_iterator迭代器插入元素

在insert中使用移动语义迭代器插入元素。
在插入类时，推荐使用 移动语义迭代器，更高效。

	std::vector<std::string> source = { "hello","world" };
	std::vector<std::string> dest = { "c++" };
	std::move_iterator itbegin = std::make_move_iterator(source.begin());
	std::move_iterator itend = std::make_move_iterator(source.end());
	dest.insert(dest.end(), itbegin, itend);
	for (auto v : source)
	{
		qDebug() << v << " ";
	} 
	// 输出 ： "" "" 两个空字符串

8.2.3 deque

8.2.3.1实现原理

deque: 双端队列容器，有两个指针，分别是first和last。
底层的数据结构是动态开辟的二维数组，一维数组初始大小为2，以2倍方式进行扩容；二维数组从新的第一维数组的下标oldsize / 2开始存放，新的二维数组上下都有相同的行，方便支持deque的首位元素添加。
deque 初始时，first 和 last 指针指向中间位置，以便在std::deque 前后添加和删除元素。

8.2.3.2 方法总结

deque deq;
 增加元素：头增加，尾增加和指定位置增加
deq.push_front(20) 从头增加元素 O(1)
deq.push_back(20), 从末尾添加元素 O(1)
deq.insert(it,20) 从it指定位置插入元素 O(n)

 删除元素：头删，尾删，指定位置删除
deq.pop_back() 从末尾删除元素 O(1)
deq.push_front() 从头删除元素 O(1)
deq.erase(it) 从it指向位置删除元素 O(n)
插入和删除一定要注意迭代器失效问题。

8.2.4 list

底层用双向链表实现，所以每个节点 pre data next。
list mylist;
 增加元素：
mylist.push_front(20) 从头增加元素 O(1)
mylist.push_back(20), 从末尾添加元素 O(1)
mylist.insert(it,20) 从it指定位置插入元素 O(1) ,但是找到it这个位置时间复杂度是O(n)
 删除元素：头删，尾删，指定位置删除
mylist.pop_back() 从末尾删除元素 O(1)
mylist.pop_front() 从头删除元素 O(1)
mylist.erase(it) 从it指向位置删除元素 O(1)，遍历it所花费时间复杂度是O(n)
 迭代器失效问题
插入和删除也要考虑迭代器失效问题。
 deque 和 list ，vector方法对比
deque与list的增加和删除方法一模一样，它们都比vector多了push_front方法和pop_front方法。

8.2.5 vector deque list对比

8.2.5.1 vector和deque之间的区别？

区别1：底层数据结构
vector动态开辟的一维数组，内存是连续的，以2倍方式进行扩容。刚实例化一个vector时候，vector vec时候，size()为0，还没有开辟空间，之后内存以2倍方式扩容。
deque动态开辟的二维数组，第一维是固定长度的，起始长度是2；第二维是4096/sizeof(T)，扩容的时候，第一维进行二倍扩容，然后将第二维指向新扩容的oldsize / 2部分。并且，deque数组的单独的某段第二维是连续，但是段与段之间不是连续的。

区别2：前中后插入删除元素的时间复杂度
vector插入: 末尾 O(1) 头插和指定位置插入 O(n)；
vector删除：尾部删除O(1) 头部删除 O(n)
deque插入：头插 尾插 O(1) 指定位置O(n)
deque删除：头删，尾删 O(1) 指定位置删除O(n)
可以看到，vector头插头删除，都是O(n)，而deque是O(1)；
区别3：内存的使用效率
vector内存必须是连续的，deque内存段与段之间的内存不必连续，只要满足段大小即可。
区别4：在中间插入元素，哪个更好？
在中间插入元素，他们的时间复杂度都是O(n)；因为都涉及到元素的移动。
但是vector内存连续，所以移动元素更简单。deque内存不连续，移动元素更复杂，更慢。
不是连续的内存移动，比连续的内存移动，操作更麻烦。元素的移动比vector慢。

8.2.5.2 vector和list之间的区别？

vector和list对比，就是在考察什么情况下使用链表，什么情况使用数组？
增加删除多，用链表；
随机访问多，用数组

8.2.6 容器适配器 stack, queue, priority_queue

容器适配器的定义：

1. 适配器底层没有自己的数据结构，而是用了现有的容器，对现有容器的一种封装，它的方法全部由底层依赖的容器实现。
2. 容器适配器没有自己的迭代器，不能用迭代器遍历。所以，stack, queue, priority_queue只能通过逐个遍历实现。
3. 容器适配器也不需要遍历，而如果遍历deque，内存不连续，效率不如vector。

8.2.6.1 stack 栈的实现

stack就是通过双端队列deque实现的，实现代码如下：

template<typename T, typename Container=deque<T>>
class Stack
{
public:
	void push(const T &val) { con.push_back(val); }
	void pop() { con.pop_back(); }
	T top()const { return con.back(); }
private:
	Container con;
};

栈的方法总结：
stack st;
入栈 : st.push(10)
出栈: st.pop(20)
栈顶元素: int a = st.top()
判断栈空： st.empty()
返回元素个数： size()

面试问题：栈的实现使用的双端队列deque，为什么不使用vector呢？

原因有2个：

1. 内存使用角度：因为vector的初始化时，内存默认是0，没有deque好，实例化一个vectorvec ,对于这点，在stack中实现的时候，可以自己reverse()，调整到一个大的内存。
2. deque有双端队列有先进先出的功能。stack 先进后出，使用deque插入删除效率，O(1); 如果使用vector，增加和删除涉及元素的移动，时间复杂度O(n)；

8.2.6.2 queue队列的实现

对于队列，其特点是先入先出，后入后出，所以就需要有两个指针，头指针和尾指针。使用双端队列deque方便头部删除和尾部插入。

面试问题：queue底层用什么实现

队列的底层实现也是用的deque双端队列。如果用vector实现队列，出队时候需要大量的移动，效率很低。vector需要大片连续的内存，而deque不用，所需要的内存满足4096 / sizeof(T)即可。
queue的常用方法：
queue que;
入队： que.push(10);
出队： que.pop();
查看队头： que.front()
查看队尾： que.back()
判断队空： que.empty()
元素个数： que.size()

8.2.6.3 priority_queue堆的实现

优先级队列是基于大根堆的，实现的时候用的是vector.
优先级队列常用方法：
priority_queue pque;
入队： pque .push()
出队： pop()
查看堆顶元素： top()
判断队空： empty()
返回元素个数： size()

面试题：priority_queue为什么要用vector实现

为什么用vector存放大根堆，因为要用数组的下标来标记每个堆节点；如果数组不连续，则不能正确标记每个节点的关系。

而如果使用deque双向队列实现，内存不连续，没办法表示节点之间的关系