Open katarXu opened 3 years ago
c++有三种适配器,其中stack、queue基于deque实现,priority_queue基于vector实现 适配器相当于屏蔽了原容器的一些接口
priority_queue(type, container, functional)
构造函数中的 functional 具体是什么样的在#include<funcitonal>
中可以看到
template <class T> struct greater {
bool operator() (const T& x, const T& y) const {return x>y;}
typedef T first_argument_type;
typedef T second_argument_type;
typedef bool result_type;
};
故functional实际上是一个包含operator()
函数重载的结构体,故我们可以这么构造优先队列
struct cmp{
bool operator() (int &a, int &b) { return a < b; }
};
priority_queue<int, vector<int>, cmp> heap;
还能看到另外一种声明方式:
auto cmp = [](const int &a, const int &b) { return a < b; };
priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);
这里有一种常见错误是写成
priority_queue<int, vector<int>, decltype(cmp)> heap;
会报出错误C3497:无法构造lambda实例,这是因为C++11中删除了lambda默认构造函数,而在初始化heap时,因为没有默认参数,故会先生成一个空的lambda实例,再用cmp去赋值,这样就出错了
push
和 emplace
的区别push添加元素时,需要先拷贝构造一个对应元素 emplace是C++11中的新增特性,添加元素时调用移动构造函数(就地构造,之后不再拷贝),节约了内存时间
且要注意:
vector<pair<int, int>> a;
a.push_back({ 1, 2 });
a.emplace_back(1, 2);
std::vector<std::vector<int>> v;
v.push_back({1,2,3}); // OK
//v.emplace_back({1,2,3}); // error
v.emplace_back(std::vector<int>{1,2,3}); // OK
v.emplace_back<std::vector<int>>({1,2,3}); // OK
std::vector<std::regex> v;
v.push_back(nullptr); // 编译出错
v.emplace_back(nullptr); // 通过编译,但运行时抛出异常并且难以定位
Q : vector数组在执行
push_back()
、insert()
、pop_back()
、erase()
时size()和capacity()的变化执行
push_back()
、insert()
时,若size() == capacity(),那么会先新申请capacity() + capacity()/2
大小的空间,随后size加1执行
pop_back()
、erase()
时,只会使size减少,capacity不发生变化