只有脚踩上去才知其远近和曲折

STL简记

STL

六大组件

https://www.cnblogs.com/welen/articles/3533008.html

  • 容器(Container)

  • 算法(Algorithm)

  • 迭代器(Iterator)

  • 仿函数(Function object)

  • 适配器(Adaptor)

  • 空间配置器(allocator)

容器分类

第一种:顺序容器

1、vector:可变数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢;vector的另一个常见的问题就是clear操作。clear函数只是把vector的size清为零,但vector中的元素在内存中并没有消除,所以在使用vector的过程中会发现内存消耗会越来越多,导致内存泄露,现在经常用的方法是swap函数来进行解决:

vector<int> V;
V.push_back(1); 
V.push_back(2);
V.push_back(1); 
V.push_back(2);
vector<int>().swap(V); 
//或者 V.swap(vector<int>());

利用swap函数,和临时对象交换,使V对象的内存为临时对象的内存,而临时对象的内存为V对象的内存。交换以后,临时对象消失,释放内存。

2、deque:双端队列。支持快速随机访问。在头尾位置插入/删除速度很快;

3、list:双向链表。只支持双向顺序访问。在list任何位置进行插入/删除操作速度都很快;

A) 如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
B) 如果你需要大量的插入和删除,而不关心随即存取,则应使用list
C) 如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque

4、forward_list:单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快;

5、array:固定大小数组。支持快速随机访问。不能添加或删除元素;

6、string:与vector相似的容器,但专门用于保存字符。随机访问快。在尾部插入/删除速度快;

第二种:关联容器

按关键字有序保存元素:

1、map:关联数组。保存关键字-值对;

2、set:关键字即值,即只保存关键字的容器;

3、multimap:关键字可重复出现的map;

4、multiset:关键字可重复出现的set;

无序集合:

1、unordered_map:用哈希函数组织的map;

2、unordered_set:用哈希函数组织的set;

3、unordered_multimap:用哈希函数组织的map,关键字可以重复出现;

4、unordered_multiset:用哈希函数组织的set,关键字可以重复出现。

emplace_back

添加一个新元素到结束的容器。该元件是构成在就地,即没有复制或移动操作进行。就是empace_back与push_back相比,替我们省去了拷贝构造。

比如:emplace_back直接在vector的堆上构造对象,而不需要经过构造后再移动。所以emplace_back比push_back效率高。

STL定义了五个全局函数

作用于未初始化空间上。这样的功能对于容器的实现很由帮助。前两个函数是用于构造的construct()和用于析构的destroy()。另外三个函数uninitialized_copy(),uninitialized_fill()和uninitialized_fill_n()函数,分别对应copy(),fill()和fill_n()函数——这些都是STL算法。

请你来介绍一下STL的allocaotr

参考回答:

STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中,其内存配置和释放如下:

new运算分两个阶段:(1)调用::operator new配置内存;(2)调用对象构造函数构造对象内容

delete运算分两个阶段:(1)调用对象希构函数;(2)掉员工::operator delete释放内存

为了精密分工,STL allocator将两个阶段操作区分开来:内存配置有alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造由::construct()负责,对象析构由::destroy()负责。

同时为了提升内存管理的效率,减少申请小内存造成的内存碎片问题,SGI STL采用了两级配置器,当分配的空间大小超过128B时,会使用第一级空间配置器;当分配的空间大小小于128B时,将使用第二级空间配置器。第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放,而第二级空间配置器采用了内存池技术,通过空闲链表来管理内存。

空间配置函数allocate()

  1. 如果申请内存大于128 bytes,就调用第一级配置器,否则说明申请内存小于128 bytes,转到2
  2. 根据申请内存的大小n在16个free lists中找出其对应的my_free_list
  3. 如果对应的my_free_list中没有空闲区块,分配器首先将申请内存的大小上调至8的倍数n,调用refill(),准备重新填充my_free_list
  4. 否则说明有可用的空闲区块,更新my_free_list并将第一块空闲区块返回
union obj
  {
      union obj* free_list_link;
      char client_data[1];
  };

STL的第二级内存配置器主动将任何小额区块的内存需求量上调至8的倍数(例如客户端需求30bytes。就自动调整为32bytes),并维护了一个free-list数组,分别用于管理8, 16, 24, 32,40,56,64,72,80,88,96,104,112,120,128 bytes的小额区块,free-list的节点结构如下:

空间释放函数deallocate()

​ 该函数首先判断区块大小,大于128bytes就调用第一级配置器,小于128bytes就找出对应的free list,将区块回收。

lower_bound和upper_bound

lower_bound(val): 返回容器中第一个值【大于或等于】val的元素的iterator位置。
upper_bound(val): 返回容器中第一个值【大于】val的元素的iterator位置。

左闭右开区间

template< class ForwardIterator, class Type > 
ForwardIterator
lower_bound( ForwardIterator first, ForwardIterator last, const Type &value );  


template< class ForwardIterator, class Type, class Compare >
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const Type &value, Compare comp );

测试

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
    return a>b;
}
int main(){
    int num[6]={1,2,4,7,15,34}; 
    sort(num,num+6);                           //按从小到大排序 
    int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
    int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
    cout<<pos1<<" "<<num[pos1]<<endl;
    cout<<pos2<<" "<<num[pos2]<<endl;
    sort(num,num+6,cmd);                      //按从大到小排序
    int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
    int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
    cout<<pos3<<" "<<num[pos3]<<endl;
    cout<<pos4<<" "<<num[pos4]<<endl;
    return 0;    
}

greater<> 和 less<> 仿生函数

两个函数的头文件是<functional>

建堆的时候,默认是大根堆,第三个参数用greater<T>会变成小根堆;

排序的时候,默认是从小到大,但是第三个参数用greater<T>会变成从大到小

另外说一句,make_heap等heap操作函数在头文件<algorithm>里。

greater

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;
};

less

template <class T> struct less {
  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;
};

在sort()函数中使用greater<>()less<int>()

#include<iostream>
#include<vector>
#include<iterator>
#include<functional>
#include<algorithm>
using namespace std;

int main()
{
    int A[]={1,4,3,7,10};
    const int N=sizeof(A)/sizeof(int);
    vector<int> vec(A,A+N);
    ostream_iterator<int> output(cout," ");

    cout<<"Vector vec contains:";
    copy(vec.begin(),vec.end(),output);

    cout<<"\nAfter greater<int>():";
    sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小 
    copy(vec.begin(),vec.end(),output);

    cout<<"\nAfter less<int>():";
    sort(vec.begin(),vec.end(),less<int>());   //内置类型小大到大 
    copy(vec.begin(),vec.end(),output);
    return 0;
}

std::heap等操作

原理https://www.cnblogs.com/yyxt/p/4979681.html

// range heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

  std::cout << '\n';

  return 0;
}

unique

unique函数属于STL中比较常用函数,它的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除,并不是真的删除,而是指重复元素的位置被不重复的元素给占领了(详细情况,下面会讲)。由于它”删除”的是相邻的重复元素,所以在使用unique函数之前,一般都会将目标序列进行排序。

函数原型

unique函数的函数原型如下:

1.只有两个参数,且参数类型都是迭代器:

iterator unique(iterator it_1,iterator it_2);

这种类型的unique函数是我们最常用的形式。其中这两个参数表示对容器中[it_1,it_2)范围的元素进行去重(注:区间是前闭后开,即不包含it_2所指的元素),返回值是一个迭代器,它指向的是去重后容器中不重复序列的最后一个元素的下一个元素

2.有三个参数,且前两个参数类型为迭代器,最后一个参数类型可以看作是bool类型:

iterator unique(iterator it_1,iterator it_2,bool MyFunc);

该类型的unique函数我们使用的比较少,其中前两个参数和返回值同上面类型的unique函数是一样的,主要区别在于第三个参数。这里的第三个参数表示的是自定义元素是否相等。也就是说通过自定义两个元素相等的规则,来对容器中元素进行去重。

shrink_to_fit

// VS2019
int main() {
    vector<int> arr(100);
    arr.emplace_back(10);
    cout << arr.size() << endl;  // 输出101
    cout << arr.capacity() << endl; // 输出150
    arr.shrink_to_fit();
    cout << arr.size() << endl;  // 输出101 
    cout << arr.capacity() << endl; // 输出101
    arr.swap(vector<int>());
    cout << arr.size() << endl;  // 输出0
    cout << arr.capacity() << endl; // 输出0
}
12345678910111213

  从上面可以看出,在VS下vector扩容是1.5倍(Linux下是2倍)。由于扩容了之后,多出了49*sizeof(int)的无用内存,C++11提供了shrink_to_fit函数来释放这部分这部分内存,但是这个函数只是请求,并不保证一定成功。

  而在C++11之前,都知道clear()函数是清除容器内元素个数,使其为0,但是并没有释放内存,所以一般都用swap函数来释放,现在可以clear后用shrink_to_fit函数来释放内存。

array

  引入这个容器的目的就是为了替换C中的数组,由于C中的数组是没做安全检查的,所以C++提供了这个定长容器。也是为了和C++STL兼容,虽然STL也提供了通用函数begin()和end()函数来兼容传统C,但是array更规范。

int main() {
    constexpr int size = 10;
    array<int, size> arr{ 1, 2, 5, 3, 5, 1 };
    sort(arr.begin(), arr.end());
}
12345

forward_list

  list是双向链表,而forward_list是单向链表,其效率很高,是所以容器中没有提供size()方法的容器。

无序容器

  map和set底层都是由红黑树实现,其查找/增加/删除的时间复杂度为O(log(n)),并且这两个容器是有序的,也就是元素要支持<运算符。

  C++11提供了unordered_map/set,其底层是由哈希表实现,所以时间复杂度均为O(1),而且其是无序的。

元组tuple

  tuple类似于pair的模板。每个pair的成员类型可以不相同,但是pair只有两个成员,而一个tuple可以有任意数量的成员。每个确定的tuple类型的成员数目是固定的,但一个tuple类型的成员数目可以与另一个tuple类型不同。下面是tuple支持的操作:

定义和初始化tuple

  当我们顶一个tuple时,需要指出每个成员的类型:

tuple<int, double, size_t> threeD;  // 三个成员都被初始化为0
tuple<string, vector<double>, list<int>> someVal("constants", { 3.15,22 }, { 0,1 });
12

当我们创建一个tuple对象时,可以使用tuple的默认构造函数,它会对每个成员进行值初始化;也可以像someVal一样,为每个成员显式提供一个初始值。tuple这个构造函数是explicit的,所以必须直接初始化。

  类似make_pair函数,标准库也提供了make_tuple函数,用来生成tuple对象:

auto item = make_tuple("hello", 3, 3.0); // item是一个tuple<const char*, int ,doule>类型
1

访问tuple成员

  pair只有两个成员,所以可以用first和second来访问,但是tuple的成员是不固定的,所以无法设置成员来访问。要访问tuple的一个成员,就要使用标准库函数模板get。为了使用get,必须要指定显式模板实参,指出我们想要访问第几个成员。我们传递给get一个tuple对象,返回指定成员的引用:

auto item = make_tuple("hello", 3, 3.0); // item是一个tuple<const char*, int ,doule>类型
auto book = get<0>(item);  // 返回item的第一个成员
12

  还可以通过tie进行解包:

int main() {
    auto item = make_tuple("hello", 3, 3.0); // item是一个tuple<const char*, int ,doule>类型
    using type = decltype(item);
    tuple_element<0, type>::type x;   // 这个用法下面会说
    tuple_element<1, type>::type y;
    tuple_element<2, type>::type z;
    tie(x, y, z) = item;
    cout << x << " " << y << " " << z << endl;  // 输出hello,3, 3
}
123456789

  解包时,我们如果只想解某个位置的值时,可以用std::ignore占位符来表示不解某个位置的值。

tie(x, ignore, ignore) = item;   // 只解第一个成员,所以无法输出y和z
1

  C++14可以通过类型来获取tuple成员:

int main() {
    auto item = make_tuple("hello", 3, 3.0); // item是一个tuple<const char*, int ,doule>类型
    using type = decltype(item);
    cout << get<int>(item) << endl; // 输出3
    cout << get<double>(item) << endl; // 输出3
    cout << get<const char*>(item) << endl; // 输出hello
}
1234567

tuple中成员的数量和成员类型

  可以通过类模板tuple_size::value来得到给定tuple类型中成员的数量,可以通过decltype来得到tupleType;

  也可以通过类模板tuple_element<i, tupleType>::type来得到tuple类型中指定成员的类型:

int main() {
    auto item = make_tuple("hello", 3, 3.0); // item是一个tuple<const char*, int ,doule>类型
    auto book = get<0>(item);  // 返回item的第一个成员
    using type = decltype(item);
    size_t sz = tuple_size<type>::value;
    cout << sz << endl;   // 输出3
    tuple_element<1, type>::type cnt = get<1>(item);  // cnt的类型是int
}
12345678

合并tuple

  可以通过tuple_cat对两个tuple进行合并。

遍历tuple

template<typename... Args>
std::ostream& operator<<(std::ostream& os, const std::tuple<Args...>& t)
{
    os << "(" << std::get<0>(t);
    for (size_t i = 1; i < sizeof...(Args) << ++i)
        os << ", " << std::get<i>(t);
    return os << "]";
}

int main(int, char**)
{
    cout << make_tuple("InsideZhang", 23, "HeNan") << endl;
            // 编译出错,局部变量i不可作为非类型模板参数
    return 0;
}

// 这时我们便需要单独把每一位的索引拿出来作为非类型模板参数进行递归调用:
template<typename Tuple>
void tuple_print(const Tuple& t, size_t N, std::ostream& os)
{
    if (N != 1)
        tuple_print(t, N-1, os);
    os << std::get<N-1>(t);
}
123456789101112131415161718192021222324

  以上的代码, 也即通过参数传递的方式进行的非类型模板参数的赋值,仍然编译不通过。get参数必须在编译时即为常量表达式。

C++11实现tuple的遍历
template<typename Tuple, size_t N>
struct tuple_print {
    static void print(const Tuple& t, ostream& os) {
        tuple_print<Tuple, N - 1>::print(t, os);
        os << ", " << get<N - 1>(t);
    }
};
// 类模板的特化版本
template<typename Tuple>
struct tuple_print<Tuple, 1> {
    static void print(const Tuple& t, ostream& os) {
        os << "(" << get<0>(t);
    }
};

// operator<<
template<typename... Args>
ostream& operator << (ostream & os, const tuple<Args...> & t) {
    tuple_print<decltype(t), sizeof...(Args)>::print(t, os);
    return os << ")";
}


int main() {
    auto t1 = std::make_tuple("InsideZhang", 23, "HeNan");
    auto t2 = std::make_tuple("InsideLi", 23, "AnHui");
    cout << std::tuple_cat(t1, t2) << endl;
    //  (InsideZhang, 23, HeNan, InsideLi, 23, AnHui)
}

vector\

首先vector< bool> 并不是一个通常意义上的vector容器,这个源自于历史遗留问题。
早在C++98的时候,就有vector< bool>这个类型了,但是因为当时为了考虑到节省空间的想法,所以vector< bool>里面不是一个Byte一个Byte储存的,它是一个bit一个bit储存的!
因为没有直接去给一个bit来操作,所以用operator[]的时候,正常容器返回的应该是一个对应元素的引用,但是对于vector< bool>实际上访问的是一个”proxy reference”而不是一个”true reference”,返回的是”std::vector< bool>:reference”类型的对象。
而一般情况情况下

vector<bool> c{ false, true, false, true, false };
bool b = c[0];
auto d = c[0];
1234

对于b的初始化它其实暗含了一个隐式的类型转换。而对于d,它的类型并不是bool,而是一个vector< bool>中的一个内部类。
而此时如果修改d的值,c中的值也会跟着修改

d = true;
for(auto i:c)
    cout<<i<<" ";
cout<<endl;
//上式会输出1 1 0 1 012345

而如果c被销毁,d就会变成一个悬垂指针,再对d操作就属于未定义行为。

所以对于容器一些基本的操作它并不能满足,诸如取地址给指针初始化操作【因为没有办法给单一一个bit来取地址,或者搞引用】

vector<bool> c{ false, true, false, true, false };
bool &tmp = c[0];   //错误,不能编译,对于引用来说,因为c[0]不是一个左值
bool *p = &c[0];    //错误,不能编译,因为无法将一个临时量地址给绑定到指针123

所以为什么说vector< bool>不是一个标准容器,就是因为它不能支持一些容器该有的基本操作。

multimap

multimap和map的功能类似,就不一一介绍了,下面主要说一下这两者的不同:

1、multimap中的key可以重复

2、multimap中没有重载operator[ ]功能

multimap输出键值为key的所有元素

1、使用find和count:

​ count(k) 求出键k的出现次数

  find(k) 返回第一个拥有键k的实例

multimap<int, int>::size_type  cnt = testMap.count(searchItem);
multimap<int, int>::iterator  iter = testMap.find(searchItem);
for(;cnt > 0; cnt--, iter++)
{
      cout<<iter->first<<" "<<iter->second<<endl;
}

2、使用lower_bound与upper_bound:

​ lower_bound(k)返回迭代器指向不小于K的第一个元素

​ upper_bound(k)返回迭代器指向 大于k的第一个元素

multimap<int, int>::iterator iterBeg = testMap.lower_bound(searchItem);
multimap<int, int>::iterator iterEnd = testMap.upper_bound(searchItem);
for(;iterBeg != iterEnd;iterBeg++)
{
     cout<<iterBeg->first<<"->"<<iterBeg->second<<endl;    
}

3、使用equal_range:

​ equal_range(k):函数的返回值是一个pair,分别存放相同键k的迭代器区间。

auto ret = testMap.equal_range(searchItem);
auto it = ret.first;
while(it!=ret.second)
{
     cout<<it->first<<"->"<<it->second<<endl;
     ++it;
}

4、程序测试:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{

    multimap<int, int> testMap;
    testMap.insert(make_pair(5,1));
    testMap.insert(make_pair(5,2));
    testMap.insert(make_pair(5,3));
    testMap.insert(make_pair(5,4));
    int searchItem = 5;

    /*第一种方法*/
    multimap<int, int>::size_type  cnt = testMap.count(searchItem);
    multimap<int, int>::iterator  iter = testMap.find(searchItem);
    for(;cnt > 0; cnt--, iter++)
    {
          cout<<iter->first<<"->"<<iter->second<<endl;
    }
    cout<<endl;

    /*第二种方法*/
    multimap<int, int>::iterator iterBeg = testMap.lower_bound(searchItem);
    multimap<int, int>::iterator iterEnd = testMap.upper_bound(searchItem);
    for(;iterBeg != iterEnd;iterBeg++)
    {
        cout<<iterBeg->first<<"->"<<iterBeg->second<<endl;    
    }
    cout<<endl;

    /*第三种方法*/
    auto ret = testMap.equal_range(searchItem);
    auto it = ret.first;
    while(it!=ret.second)
    {
        cout<<it->first<<"->"<<it->second<<endl;
         ++it;
    }
    return 0;
}

deque

https://blog.csdn.net/terence1212/article/details/52326945?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param

https://www.cnblogs.com/alionxd/articles/3028711.html

deque是一个双向队列,优化了对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成,第一个区块朝某方向发展,最后一个区块朝另一个方向发展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块,而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

deque的特点:

1、支持随机访问,即支持[]以及at(),但是性能没有vector好

2、可以在内部进行插入和删除操作,但性能不及list。

deque和vector的不同之处:

1、deque两端都能够快速的插入和删除元素。vector只能在尾端进行。

2、deque的元素存取和迭代器操作会稍微慢一些。因为deque的内部结构会多一个简介过程。

3、迭代器时特殊的智能指针,而不是一般指针。它需要在不同的区块之间跳转。

4、deque可以包含更多的元素,其max_size可能更大。因为不止使用一块内存。

5、不支持对容量和内存分配时机的控制。

容器的选择:

1、强调快速随机访问,则vector比list好得多。

2、已知要存储元素的个数。vector好于list。

3、强调增删且不要在两端插入修改元素,则list显然要比vector好。

4、除非我们需要在容器首部插入和删除元素,deque好于vector。

priority_queue

priority_queue容器的使用方法

priorityqueuepriorityqueue容器的使用方法大致如下表所示:

用法 作用
q.top() 返回priority_queue的首元素
q.push() 向priority_queue中加入一个元素
q.size() 返回priority_queue当前的长度(大小)
q.pop() 从priority_queue末尾删除一个元素
q.empty() 返回priority_queue是否为空,1为空、0不为空

注意:priority_queue取出队首元素是使用top,而不是front,这点一定要注意!!

其中q.top()为查找操作,在最小优先队列中搜索优先权最小的元素,在最大优先队列中搜索优先权最大的元素。q.pop()为删除该元素。优先队列插入和删除元素的复杂度都是O(lgn),所以速度很快;另外,在优先队列中,元素可以具有相同的优先权。

priority_queue模板原型

template< class T ,class Sequence=vector<T> ,classCompare=less<typenameSequence::value_type> >class priority_queue;

优先队列常用定义和重载运算符方法

struct cmp1 {  
    bool operator ()(int &a,int &b)
    {  
        return a>b;//最小值优先   
    }  
};

struct cmp2 {  
    bool operator ()(int &a,int &b)
    {  
        return a<b;//最大值优先   
    }  
};

struct node1 {  
    int u;  
    bool operator < (const node1 &a) const 
    {  
       return u>a.u;//最小值优先   
    }  
}; 

struct node2 {  
    int u;  
    bool operator < (const node2 &a) const 
    {  
        return u<a.u;//最大值优先   
    }  
}; 

priority_queue<int>q1;//采用默认优先级构造队列     
priority_queue<int,vector<int>,cmp1>q2;//最小值优先   
priority_queue<int,vector<int>,cmp2>q3;//最大值优先   
priority_queue<int,vector<int>,greater<int> >q4;//注意“>>”会被认为错误,   
                                                //这是右移运算符,所以这里用空格号隔开,最小值优先 
priority_queue<int,vector<int>,less<int> >q5;//最大值优先    
priority_queue<node1>q6;  //自定义优先级
priority_queue<node2>q7;

默认优先级:

#include <queue>
using namespace std;

priority_queue<int> q;

通过<操作符可知在整数中元素大的优先级高。

传入一个比较函数,使用functional.h函数对象作为比较函数。

#include <queue>
#include <functional>
using namespace std;

priority_queue<int, vector<int>, greater<int> > q;

此时整数中元素小的优先级高。

传入比较结构体,自定义优先级。

#include <queue>
using namespace std;

struct cmp{
    bool operator ()(int a,int b){    //通过传入不同类型来定义不同类型优先级
        return a>b;    //最小值优先
    }
};

/**
struct cmp{
    bool operator ()(int a,int b){
        return a<b;    //最大值优先
    }
};
**/

priority_queue<int, vector<int>, cmp > q;

自定义数据结构,自定义优先级。

#include <queue>
using namespace std;

struct node {
    int priority;
    int value;
    friend bool operator < (const node &a, const node &b) {  
        return a.priority < b.priority;
    }

    /* 这样写也可以
    bool operator < (const node &a) const {
        return priority < a.priority;
    }
    */
};

/**
因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。而且自定义类型的<操作符与>操作符并无直接联系,故会编译不过。

struct node {
    int priority;
    int value;
    friend bool operator > (const node &a, const node &b) {   //错误示范
        return a.priority > b.priority;  
    }
};
**/
priority_queue<node> q;
点赞