基本知识

• 右值引用

  C++11新特性，在出现右值引用之前，只有左值可以被引用，方法为&（例如int& a）。与之对应的右值引用，方法为&&（例如int&& a）。

  首先说一下什么是左值和右值，简单来说，等号左边的就是左值，右边的就是右值。比如：

  int a = 1;
  int b = 2;
  int c = a+b;
  

  其中，等号左边的a、b、c是左值，右边1、2、a+b便是右值。右值的最大特点是，在该语句结束后，便会被销毁。我们以int c = a+b;这条语句为例，系统首先为a+b的结果生成了一个临时变量c'，然后将c'的值拷贝给c，然后销毁c'。而事实上，更加高效的方法是，直接将c变为对c'的引用，并且并不销毁c'。当然，编译器是可以做这种优化的，这里我们只是举一个例子。

  事实上，右值引用出现的目的便是，避免不必要的拷贝构造，而使用转移构造，在std模板库里面也提供了相关的模板，std::move()，包括以下几种情况：

  1. 函数的返回值，尤其当返回的是一个对象的时候，非右值引用可能会导致而外的拷贝构造和析构代价；
  2. swap函数，在下面的例子中，不使用右值引用会导致三次模板T的拷贝构造函数，而使用了右值引用后，只会调用三次模板T的转移构造函数（也就是说本质上并没有移动数据），从而降低开销。

  // 不使用右值引用，而使用左值引用
  template <class T> swap(T& a, T& b){ 
       T temp(a);  
       a = b; 
       b = temp;
  }  
  

  // 使用右值引用，不使用左值引用
  template <class T> swap(T&& a, T&& b){ 
       T temp(std::move(a));  
       a = std::move(b); 
       b = std::move(temp);
  }  
  

  注意的是，只有传入右值才会调用形参为右值引用的（构造）函数，而某个变量（例如a）是不会为右值的，也就不会调用形参为右值引用的函数，除非强制类型转换（T&&）或者使用std::move()。

  右值引用的另一个作用是实现精确传递（Perfect Forwarding），简单来说，对于一个成员函数，每个形参变量都需要写两个重载，一个是T &，另一个是const T &，因此对于有N个形参的成员函数来说，原则上我们需要2^N个重载，显然是很不方便的。因此，C++11中规定，可以使用T &&替代T &和const T &，而函数接受到的形参类型就是传入的类型，从而降低了重载的代价。

C++容器

• priority_queue，优先队列

  优先队列是一种从队尾插入元素，队首删除元素的容器，并且始终保持队首的元素是最大（小）。

  由于维护了队首是最大（小）元素的结构，优先队列的插入、删除时间复杂度为log(N)。

  优先队列的一种实现方式是利用堆（heap）。堆是一种以二叉树方式组织的数据结构，其特点是父节点永远比子节点大（小），因此与优先队列一样，堆的根结点的是最大（小）的元素，其插入与删除操作的过程如下：

  插入时，堆在二叉树的叶结点增加插入元素，当其小于父节点元素的时候，便与父节点交换

       2              2               2              1 
     /   \          /   \           /   \          /   \
    7     4  -->   7     4  -->    7     1  -->   7     2
   / \   /        / \   / \       / \   / \      / \   / \
  8   9 5        8   9 5   1     8   9 5   4    8   9 5   4
  

  删除时，堆从根节点开始，将较小的叶结点填充至删除节点，直至到叶结点

       2                              4              4 
     /   \          /   \           /   \          /   \
    7     4  -->   7     4  -->    7        -->   7     5
   / \   /        / \   /         / \   /        / \  
  8   9 5        8   9 5         8   9 5        8   9    
  

  通过这种方式，优先队列/堆可以实现出容器元素永远是最大（小）的，其入、删除时间复杂度为log(N)。

  C++提供了priority_queue容器，包含于头文件<queue>中，模板为

  template <
      class T, 
      class Container = vector<T>,
      class Compare = less<typename Container::value_type>
  > class priority_queue;
  

  含义如下

  模板	含义
  T	优先队列中的元素类型
  Container	优先队列的容器，默认为vector<T>
  Compare	优先队列的出队（比较规则）

  其中Compare的一种定义方式如下

  struct compare{
      bool operator()(const T A, const T B){
          return A > B;
      }
  };
  

  成员函数包括

  成员函数	含义
  empty	判断是否为空
  size	返回大小
  top	读取队首元素
  push	插入元素
  emplace
  pop	删除队首元素
  swap

其他知识点

• 类的私有成员可以被拷贝构造函数以及重载=访问，也就是说，如果一个类的拷贝构造函数的形参为某个对象的引用（必须是同一个类），那么便可以在拷贝构造函数中，对被引用类的私有成员进行访问。