C++—lambda表达式+优先队列 prority_queue+关键字decltype

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

链接：

/*
struct listnode{
    int val;
    listnode *next;
    listnode(int x) : val(x),next(null) {}
};
*/
class solution {                        //优先队列解题
public:
    listnode *mergeklists(vector<listnode*>& lists) {
        listnode dummy(0);
        listnode *tail = &dummy;
        auto comp=[](listnode *a, listnode *b) {return a->vl > b->val;}; 
        priority_queue<listnode*, vector<listnode*>, decltype(comp)> q(comp);
        for(listnode* list : lists)
          if(list)q.push(list);
        while(!q.empty())
        {
           tail->next = q.top();
           q.pop();
           tail = tail->next;
           if(tail->next)
             q.push(tail->next);
        }
        return dummy.next;
    }
};

优先队列 — priority_queue

一、相关定义

　　优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载“<”操作符来重新定义比较规则。

　　优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue，因为list的迭代器不是任意存取iterator，而pop中用到堆排序时是要求random access iterator 的!)：

　　priority_queue<vector<int>, less<int> > pq1; 　　　 // 使用递增  less<int> 函数对象排序
　　priority_queue<deque<int>, greater<int> > pq2; 　　// 使用递减  greater<int> 函数对象排序
　　其成员函数有“判空(empty)” 、“尺寸(size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

二、基本操作

empty() 　　   如果队列为空，则返回真

pop()　　　　删除对顶元素，删除第一个元素

push() 　　     加入一个元素

size() 　　　  返回优先队列中拥有的元素个数

top() 　　　　返回优先队列对顶元素，返回优先队列中有最高优先级的元素

在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。

头文件：   #include <queue>

声明方式：

1、普通方法

priority_queue<int> q;   　　　　　　　　　　　　    //通过操作，按照元素从大到小的顺序出队

priority_queue<int,vector<int>, greater<int> > q;  　　//通过操作，按照元素从小到大的顺序出队

2、自定义优先级

struct cmp {     

　　operator bool ()(int x, int y)     

　　{        

　　　　 return　x > y;　　 // x小的优先级高       //也可以写成其他方式，如： return p[x] > p[y];表示p[i]小的优先级高

　　}

};

priority_queue<int, vector<int>, cmp> q;    //定义方法

//其中，第二个参数为容器类型。第三个参数为比较函数。

3、结构体声明方式

struct node {     

　　int x, y;     

　　friend bool operator < (node a, node b)     

　　{         

　　　　return a.x > b.x;    //结构体中，x小的优先级高     

　　}

};

priority_queue<node>q;   //定义方法

//在该结构中，y为值, x为优先级。

//通过自定义operator<操作符来比较元素中的优先级。

//在重载”<”时，最好不要重载”>”，可能会发生编译错误

三、代码实现

优先队列，其构造及具体实现我们可以先不用深究，我们现在只需要了解其特性，及在做题中的用法。
以一个例子来解释吧(呃，写完才发现，这个代码包函了几乎所有我们要用到的用法，仔细看看吧)：

/*优先队列的基本使用*/ 
#include<stdio.h> 
#include<functional> 
#include<queue> 
#include<vector> 
using namespace std; 
//定义结构，使用运算符重载,自定义优先级1 
struct cmp1{ 
    bool operator ()(int &a,int &b){ 
        return a>b;//最小值优先 
    } 
}; 
struct cmp2{ 
    bool operator ()(int &a,int &b){ 
        return a<b;//最大值优先 
    } 
}; 
//定义结构，使用运算符重载,自定义优先级2 
struct number1{ 
    int x; 
    bool operator < (const number1 &a) const { 
        return x>a.x;//最小值优先 
    } 
}; 
struct number2{ 
    int x; 
    bool operator < (const number2 &a) const { 
        return x<a.x;//最大值优先 
    } 
}; 
int a[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
   
int main() 
{   priority_queue<int>que;//采用默认优先级构造队列 
   
    priority_queue<int,vector<int>,cmp1>que1;//最小值优先 
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先 
   
    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误， 
                                                      //这是右移运算符，所以这里用空格号隔开 
    priority_queue<int,vector<int>,less<int> >que4;////最大值优先 
   
    priority_queue<number1>que5; 
    priority_queue<number2>que6; 
   
    int i; 
    for(i=0;a[i];i++){ 
        que.push(a[i]); 
        que1.push(a[i]); 
        que2.push(a[i]); 
        que3.push(a[i]); 
        que4.push(a[i]); 
    } 
    for(i=0;num1[i].x;i++) 
        que5.push(num1[i]); 
    for(i=0;num2[i].x;i++) 
        que6.push(num2[i]); 
   
   
    printf("采用默认优先关系:\n(priority_queue<int>que;)\n"); 
    printf("queue 0:\n"); 
    while(!que.empty()){ 
        printf("%3d",que.top()); 
        que.pop(); 
    } 
    puts(""); 
    puts(""); 
   
    printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n"); 
    printf("queue 1:\n"); 
    while(!que1.empty()){ 
        printf("%3d",que1.top()); 
        que1.pop(); 
    } 
    puts(""); 
    printf("queue 2:\n"); 
    while(!que2.empty()){ 
        printf("%3d",que2.top()); 
        que2.pop(); 
    } 
    puts(""); 
    puts(""); 
    printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n"); 
    printf("queue 3:\n"); 
    while(!que3.empty()){ 
        printf("%3d",que3.top()); 
        que3.pop(); 
    } 
    puts(""); 
    printf("queue 4:\n"); 
    while(!que4.empty()){ 
        printf("%3d",que4.top()); 
        que4.pop(); 
    } 
    puts(""); 
    puts(""); 
    printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n"); 
    printf("queue 5:\n"); 
    while(!que5.empty()){ 
        printf("%3d",que5.top()); 
        que5.pop(); 
    } 
    puts(""); 
    printf("queue 6:\n"); 
    while(!que6.empty()){ 
        printf("%3d",que6.top()); 
        que6.pop(); 
    } 
    puts(""); 
    return 0; 
} 
/*
运行结果 ：
采用默认优先关系:
(priority_queue<int>que;)
queue 0:
83 72 56 47 36 22 14 10  7  3
  
采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
queue 1:
 7 10 14 22 36 47 56 72 83 91
queue 2:
83 72 56 47 36 22 14 10  7  3
  
采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
queue 3:
 7 10 14 22 36 47 56 72 83 91
queue 4:
83 72 56 47 36 22 14 10  7  3
  
采用结构体自定义优先级方式二:
(priority_queue<number>que)
queue 5:
 7 10 14 22 36 47 56 72 83 91
queue 6:
83 72 56 47 36 22 14 10  7  3
*/ 

lambda表达式（c++11）

　　使用场景

　1. lambda表达式又叫匿名函数(可以理解为一个未命名的内联函数),那么肯定就跟函数挂上关系了,通常情况写你在编程的时候需要将这段代码封装到一个函数里面再来调用,那这个时候就避免不了取函数名了,那么这个时候你就要想起我们的lambda表达式了,它可以很好的帮你解决函数命名困难这个问题。 

　2. 在你的整个项目编程中,你独立出来一个函数,但这个函数实现相对简单并且可能在整个项目只使用了一次(即不存在复用的情况),那么这个时候我们就可以考虑使用下lambda表达式了,这样可以让代码更加紧凑,更加容易维护。

　　简单应用

先看看lambda表达式变量截取的方式：

[] 不截取任何变量

[&] 截取外部作用域中所有变量，并作为引用在函数体中使用

[=] 截取外部作用域中所有变量，并拷贝一份在函数体中使用

[=, &foo] 截取外部作用域中所有变量，并拷贝一份在函数体中使用，但是对foo变量使用引用

[bar] 截取bar变量并且拷贝一份在函数体重使用，同时不截取其他变量

[this] 截取当前类中的this指针。如果已经使用了&或者=就默认添加此选项。

场景一

比较两个数的大小,第一个数比第二个数大的时候返回true,反之返回false。

//  1 传统解法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int& a, int& b)
{
　　return a > b;
}
int main(void)
{
　　int data[6] = { 3, 4, 12, 2, 1, 6 };
　　vector<int> testdata;
　　testdata.insert(testdata.begin(), data, data + 6);
    // 排序算法
　　sort(testdata.begin(), testdata.end(), compare); // 升序
　　return 0;
}

//2  lambda表达式的解法:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
　　int data[6] = { 3, 4, 12, 2, 1, 6 };
　　vector<int> testdata;
　　testdata.insert(testdata.begin(), data, data + 6);
　　sort(testdata.begin(), testdata.end(), [](int a, int b){ return a > b; });
　　return 0;
}

场景二　　

　　使用auto来接收一个lambda表达式,当然我们也可以直接使用c++11里面的新特性function来接收lambda表达式,两者等价的,因为auto是自动类型转换,所以在某些场合使用起来更方便。

#include <iostream>
#include <functional>
using namespace std;
int main(void)
{
　　int x = 8, y = 9;
　　auto add = [](int a, int b) { return a + b; };
　　std::function<int(int, int)> add = [=](int a, int b) { return a + b; };
　　cout << "add: " << add(x, y) << endl;
　　cout << "add: " << add(x, y) << endl;
　　return 0;
}
//最终的运行结果都是：17 
//解析： function中的第一个int是返回值类型，括号里面的两个int都是函数的参数类型.

场景三

使用lambda表达式来实现递归算法 

递归题目:已知f(1)=1,f(2)=2,那么请实现f(n)=f(n-1)+f(n-2),此处的n>2

#include <iostream>
#include <functional>
using namespace std;
int main()
{
　　std::function<int(int)> recursion = [&recursion](int n) { return n < 2 ? 1 : recursion(n - 1) + recursion(n - 2); };
　　cout << "recursion(2):" << recursion(2) << endl;
　　cout << "recursion(3):" << recursion(3) << endl;
　　cout << "recursion(4):" << recursion(4) << endl;
　　return 0;
}

//运行结果:

//recursion(2):2 
//recursion(3):3 
//recursion(4):5 

链接：

decltype关键字（c++11）

一、decltype意义

　　有时我们希望从表达式的类型推断出要定义的变量类型，但是不想用该表达式的值初始化变量（如果要初始化就用auto了）。为了满足这一需求，c++11新标准引入了decltype类型说明符，它的作用是选择并返回操作数的数据类型，在此过程中，编译器分析表达式并得到它的类型，却不实际计算表达式的值。

二、decltype用法

　　1.基本用法

int getsize();
int main(void)
{
    int tempa = 2;
    
    /*1.dcltempa为int*/
    decltype(tempa) dcltempa;
    /*2.dcltempb为int，对于getsize根本没有定义，但是程序依旧正常，因为decltype只做分析，并不调用getsize，*/
    decltype(getsize()) dcltempb;

    return 0;
}

　　2.与const结合

    double tempa = 3.0;
    const double ctempa = 5.0;
    const double ctempb = 6.0；
    const double *const cptrtempa = &ctempa;
   
　　 /*1.dcltempa推断为const double（保留顶层const，此处与auto不同）*/
    decltype(ctempa) dcltempa = 4.1;
    /*2.dcltempa为const double，不能对其赋值，编译不过*/
    dcltempa = 5;
    /*3.dcltempb推断为const double * const*/
    decltype(cptrtempa) dcltempb = &ctempa;
    /*4.输出为4（32位计算机）和5*/
    cout<<sizeof(dcltempb)<<"    "<<*dcltempb<<endl;
    /*5.保留顶层const，不能修改指针指向的对象，编译不过*/
    dcltempb = &ctempb;
    /*6.保留底层const，不能修改指针指向的对象的值，编译不过*/
    *dcltempb = 7.0;

　　3.与引用结合

    int tempa = 0, &reftempa = tempa;

    /*1.dcltempa为引用，绑定到tempa*/
    decltype(reftempa) dcltempa = tempa;
    /*2.dcltempb为引用，必须绑定到变量，编译不过*/
    decltype(reftempa) dcltempb = 0;
    /*3.dcltempc为引用，必须初始化，编译不过*/
    decltype(reftempa) dcltempc;
    /*4.双层括号表示引用，dcltempd为引用，绑定到tempa*/
    decltype((tempa)) dcltempd = tempa;
    
    const int ctempa = 1, &creftempa = ctempa;
    
    /*5.dcltempe为常量引用，可以绑定到普通变量tempa*/
    decltype(creftempa) dcltempe = tempa;
    /*6.dcltempf为常量引用，可以绑定到常量ctempa*/
    decltype(creftempa) dcltempf = ctempa;
    /*7.dcltempg为常量引用，绑定到一个临时变量*/
    decltype(creftempa) dcltempg = 0;
    /*8.dcltemph为常量引用，必须初始化，编译不过*/
    decltype(creftempa) dcltemph;
    /*9.双层括号表示引用,dcltempi为常量引用，可以绑定到普通变量tempa*/
    decltype((ctempa))  dcltempi = ctempa;

　　4.与指针结合

    int tempa = 2;
    int *ptrtempa = &tempa;
    /*1.常规使用dcltempa为一个int *的指针*/
    decltype(ptrtempa) dcltempa;
    /*2.需要特别注意，表达式内容为解引用操作，dcltempb为一个引用，引用必须初始化，故编译不过*/
    decltype(*ptrtempa) dcltempb;

三、decltype总结

decltype和auto都可以用来推断类型，但是二者有几处明显的差异：

1.auto忽略顶层const，decltype保留顶层const；

2.对引用操作，auto推断出原有类型，decltype推断出引用；

3.对解引用操作，auto推断出原有类型，decltype推断出引用；

　　4.auto推断时会实际执行，decltype不会执行，只做分析。

总之在使用中过程中和const、引用和指针结合时需要特别小心。

连接：