C++的一些基础知识

1. 引用和指针的区别

定义上的差别

定义上来说，指针本身代表的不是变量，而是变量的地址；引用是一个变量的别名，所代表的仍是变量本身。也容易推得，指针和引用的数据类型也不同。

是否可空的差别

指针可以为空，而引用则不行，创建引用的时候必须将其初始化。

int *a; // OK
int *b = nullptr; // OK
int c = 4;
int &d = c; // OK
int &e; // Error: Declaration of reference variable 'e' requires an initializer (lsp)

在考虑传递引用还是指针给函数时，这是很重要的一个考虑点。

是否可以改变所指对象的差别

对于指针来说，可以随意改变其所指对象：

int a = 1;
int b = 2;
int *c = &a;
cout << *c << endl; // 1
c = &b;
cout << *c << endl; // 2

对于引用来说，修改引用的值，会将引用所指向的值修改掉，而引用仍指向原来的变量。

int a = 1;
int &b = a;
cout << b << endl; // 1
cout << &b << endl; // 0x7ffde8411808
b = 4;
cout << b << endl; // 4
cout << a << endl; // 4
cout << &b << endl; // 0x7ffde8411808

2. 值类型(Value categories)

参考：

1. https://en.cppreference.com/w/cpp/language/value_category
2. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3055.pdf
3. https://stackoverflow.com/questions/6107914/how-to-test-whether-expression-is-a-temporary/6114546#6114546
4. https://www.zhihu.com/question/46599246/answer/102830868

lvalue-左值

左值（历史上如此称呼，因为左值可以出现在赋值表达式的左侧）指定一个函数或一个对象。可以理解为，在汇编语句中，具有实际存储地址的值。

xvalue-将亡值

将亡值也指对象，通常接近其生命周期结束（例如，以便可以move其资源）。xvalue是涉及右值引用的某些类型表达式的结果。

glvalue-广义左值

广义左值就是左值和将亡值。

rvalue-右值

右值（历史上所谓的右值，因为右值可能出现在赋值表达式的右侧）是xvalue、临时对象或其子对象，或者不与对象关联的值。可以理解为，在汇编语句中，使用寄存器保存的值和立即数。

prvalue-纯右值

不是xvalue的右值。

测试一下！

有如下宏定义，可以表示一个变量的类型；又编写了一些函数，定义一些变量，用于测试：

#define IS_LVALUE(...) std::is_lvalue_reference<decltype((__VA_ARGS__))>::value
#define IS_XVALUE(...) std::is_rvalue_reference<decltype((__VA_ARGS__))>::value
#define IS_PRVALUE(...) !std::is_reference<decltype((__VA_ARGS__))>::value

int TestFunction() {
    int a = -1;
    return a;
}

int& TestFunctionRef() {
    int a = 3;
    return &a;
}
int a = 3;
int *b = &a;

做出如下测试，结果如下：

1. 变量a是左值，因为其表示一个对象。
2. TestFunction是左值，因为其是一个函数。
3. 字符串是左值，因为在编译阶段，其存放在内存的常量空间里，详见:Linux下Hello World是如何输出的。
4. 对变量a取地址是右值，对b取值是左值。
5. TestFunction()是纯右值，因为函数返回值存储在对应的寄存器中，是一个临时的值。
6. this是一个纯右值。

有什么用？

对于std::move()等方法来说，需要明确区分这几个值的类型。

详见https://zhuanlan.zhihu.com/p/402251966。

3. STL相关

Algorithms + Data Structures = Programs

——Niklaus Wirth

所有源代码都在64位Arch Linux下查看，所使用的g++版本为13.1.1。

如果感兴趣，可以查看:https://love-la.in/1e7Ug5。

基本知识

STL无非就那几个容器。STL的关键部分为分配器(allocator)，算法(algorithm)，适配器(adapter)，容器(containers)，迭代器(iterator)和仿函数(functor)组成。

容器是一种数据结构。使用的时候需要先通过分配器在内存中为对应的容器分配空间，接着通过能够访问容器中元素的迭代器将算法应用到容器上。

适配器允许我们将本无法应用到容器上的算法，改变一下，使之能够应用到容器上，而仿函数则是一个类，内部重载了()运算符，其使我们能够拥有更多对容器的操纵方式，比如说:

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;
using namespace std::placeholders;

int main(int argc, char **argv) {
  vector<int> my_list;
  for(int i = 10; i >= 0; i--) {
    my_list.push_back(i);
  }

  auto target_index_iter = find_if(my_list.begin(), my_list.end(), bind(greater<int>(), _1, 9));
  cout << *target_index_iter << endl;
  return 0;
}

这段代码实现了寻找vector中大于9的元素的功能。

find_if的第三个参数需要一个一元谓词，类似于一个接收一个变量的函数指针，单独编写一个判断是否大于9的函数有些麻烦，我们可以通过适配器+仿函数来简单地达成这个目的。代码中的bind()是一个适配器，允许我们简单的通过二元仿函数greater()来对容器进行操作。我们提前将9绑定为greater()函数的第二个参数，这样bind()返回了一元谓词，符合参数规范要求。

list

list本身是一个双向环形链表，详情参考<bits/stl_list.h>。显然，不支持随机访问。

forward_list

forward_list是个线性单向链表。显然，不支持随机访问。

vector

vector是一个可变长的数组，更具体的来讲，是一个扩张因子为2的动态表。这个数据结构在《算法导论》中有提及，作为平摊分析的一个例子来讲解。

什么是扩张因子为2的动态表？具体来说，您不断地向vector当中插入元素，一旦满了，就在内存中申请新的两倍于原先大小的空间。这会造成一定的开销。

然而，sizeof(vector)的大小并非可变值，而是3个指针的长度，因为其底层定义里，vector类的成员只包含三个指针——begin,end和end_of_storage。

显然，支持随机访问。

array

array是一个定长数组。支持随机访问。

deque

全称为double-ended queue。由一个map和多个vector组成。注意这里的map不是STL的map，更像是vector。deque可以理解为双头队列，也可以近似理解为是一个vector<vector>。

如果查看源代码，会发现，一个deque类包含四个成员，一个map，一个map_size，和两个迭代器start、finish。map里的每一个单元都指向一个vector，头插的时候，就在单元所对应的第一个有数据的vector的头部插入，尾插就在最后一个有数据的vector的尾部插入。

deque里的迭代器是一个类，有四个部分，first，last，cur和node。前两者指向迭代器所对应vector（也称作缓冲区）的头和尾，cur指向当前数据，node则指向该map中，指向该vector的地址。也就是map里对应的地址。

看不懂的话，在<bits/stl_deque.h>中，有如下的注释说明：

• For any nonsingular iterator i:

  • i.node points to a member of the %map array. (Yes, you read that correctly: i.node does not actually point to a node.) The member of the %map array is what actually points to the node.

  • i.first == *(i.node) (This points to the node (first Tp element).)

  • i.last == i.first + node_size

  • i.cur is a pointer in the range [i.first, i.last). NOTE: the implication of this is that i.cur is always a dereferenceable pointer, even if i is a past-the-end iterator.

  • Start and Finish are always nonsingular iterators.

缓冲区大小一般是512，如果一个元素的大小大于512，就让一个缓冲区放1个元素。

这种设计是为了保证deque表面的连续性，某些情况下，cur指针迭代出当前vector范围，就要通过node进行计算，指向下一个vector的区间内。

另外，deque的扩容方式和扩张因子为2的动态表一致。

当指定位置插入的时候，deque会计算，此位置是不是start或者finish，若非，是离start近，还是离finish近，从而进行不同的插入表现。

允许随机访问。

queue/stack

queue和stack严格来说不是容器，而是适配器。

它们底层都是deque，将deque阉割一下就能得到这两种数据结构。双端开口改为一端开口，仅保留部分的push和pop操作即可。二者无法被遍历。

对于stack，查看<bits/stl_stack.h>:

This is not a true container, but an @e adaptor. It holds another container, and provides a wrapper interface to that container. The wrapper is what enforces strict first-in-last-out %stack behavior. The second template parameter defines the type of the underlying sequence/container. It defaults to std::deque, but it can be any type that supports @c back, @c push_back, and @c pop_back, such as std::list, std::vector, or an appropriate user-defined type.

stack底层可以是list，也可以是vector，也可以是自定义的数据结构，默认是deque。

对于queue，查看<bits/stl_queue.h>:

This is not a true container, but an @e adaptor. It holds another container, and provides a wrapper interface to that container. The wrapper is what enforces strict first-in-first-out %queue behavior. The second template parameter defines the type of the underlying sequence/container. It defaults to std::deque, but it can be any type that supports @c front, @c back, @c push_back, and @c pop_front, such as std::list or an appropriate user-defined type.

其底层可以是list，可以是自定义的数据结构，默认是deque。

有个细节，为什么queue不能用vector做底层结构呢？其实很简单，因为后者没有pop_front()。

set/multiset

二者的底层都是红黑树。二者想要表示的都是数学上集合的概念，不同点在于，set里的元素不可以重复，而multiset里的元素可以重复。二者里的数据都是排好序的。在<bits/stl_set.h>中，set定义如下：

  template<typename _Key, typename _Compare = std::less<_Key>,
	   typename _Alloc = std::allocator<_Key> >
    class set
...

如您所见，其默认的排序方式是从小到大排序。multiset也是如此。

插入、删除、查找的复杂度都是$O(logn)$。

map/multimap

二者底层都是红黑树，和set/multiset不同的是，二者存储的数据以键值对的方式存在，排序的时候以键的值为排序准则。

unordered_map/unordered_set

底层是哈希表，查找的效率为$O(1)$，最坏为$O(n)$。

默认的哈希算法是开链法。

4. 简单的小知识

new/delete VS malloc()/free()

new的时候，先调用malloc()分配空间，然后调用类的构造函数。delete的时候，先调用析构函数，然后调用free()回收空间。

const VS #define

#define所做的，是简单的替换。在预处理阶段进行处理。

有如下代码：

// a.c
#define A 3

int main() {
  int a = A;
  return 0;
}

经过预处理：

gcc -E a.c -o a.i

有：

// a.i
# 0 "defineTest.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "defineTest.c"


int main() {
  int a = 3;
  return 0;
}

而对于const定义的常量来说，其具有数据类型，也在后续阶段被处理，相对来说更加安全。此外，const也可以在函数内被定义，定义一个局部常量，也更加灵活。

此外，const也有多种功能:

const int a = 4; // 常量
int* const a = &x; // 指向常量的指针
const int* a = &x; // 指向非常量变量的指针
class A {
    int foo() const; // 成员函数内不可修改类成员值
}

static的用法

1. static可以用来声明静态成员，但是一定要在类外初始化，否则在链接时会报错。
2. static也可以用来设定类的静态方法，无须初始化就可以调用这个方法。静态方法无法调用非静态成员变量。
3. static可以表明一个普通函数只在当前文件中有效。
4. static可以修饰一个变量，在函数内修饰，表明不论函数调用多少次，这个变量只初始化一次；若在函数外修饰，则在程序运行之前就创建该变量。

this

在一个类里面，this可以理解为，指向自己的指针，与此同时，this是一个右值。

有如下代码：

#include <bits/stdc++.h>

#define IS_PRVALUE(...) !std::is_reference<decltype((__VA_ARGS__))>::value

class Foo {
public:
  int a = 3;
  
  void bar() {
    std::cout << IS_PRVALUE(this) << std::endl;
  }

  int test() const {
    return a;
  }
};

int main() {
  Foo* test = new Foo();
  test->bar(); // 1
  return 0;
}

在普通的成员函数Foo::bar()里，this的类型是Foo*，也是一个纯右值。在Foo::test()里，this的类型是const Foo*，这也保证在这种函数里面，没法修改成员变量的值。

explicit关键字

其常用于声明类的构造函数，规避对构造函数的隐性调用和复制初始化。

::与:的用法

总结一下，::有如下用法：

1. 声明所调用变量为全局变量，有如下代码：

   #include <iostream>
   
   int var_g = 3;
   static int var_sg = 4;
   
   int main() {
     int var_g = 20;
     int var_sg = 21;
     std::cout << ::var_g << std::endl; // 3
     std::cout << ::var_sg << std::endl;  // 4
     std::cout << var_g << std::endl; // 20
     std::cout << var_sg << std::endl; // 21
   }

2. 用于访问命名空间和类下的函数/方法，如std::cout或Foo::test()。

而:用法如下：

1. 表示类的继承关系，如class Foo : public Father。

2. 用于初始化列表，如：

   class Foo {
   public:
     int i;
     Foo(int a) : i(a){}
   };

Some OOP stuff-一些面向对象的理论

1. 有时候面试会问“C++的三大特点”，倒不如问“OOP”的三大特点了，是封装、继承和多态。
2. C++的多态有两种：早绑定/晚绑定(编译时多态/运行时多态，静态多态/动态多态)，前者依靠方法的重写，后者则依靠虚函数。对于Java来说，有interface和abstract关键字，而在C++里则没有这两个关键字声明接口和抽象类，这两个功能也好实现，只有纯虚函数的类叫做接口，有纯虚函数的类叫做抽象类。
3. 阐明几个名词：重写是子类重新写父类的方法；重载是同一个名称函数在同一个类中的，能够接收不同参数的实现；覆盖是指子类实现了父类的虚函数，覆盖了父类的实现。
4. 由于STL没有虚析构函数，尽量不要继承它——自己写一个适配器就行嘛！

类型转换

1. static_cast，常用于T到各个类型的转换、数值之间的转换。
2. reinterpret_cast，按位转换，常用于各种指针间的转换。
3. const_cast，用于将常量转换为变量。
4. dynamic_cast，可以将多态基类（包含虚函数的基类）的指针强制转换为派生类的指针，也可以转换引用，且检查安全性。

5. 智能指针

unique_ptr

翻译自https://en.cppreference.com/w/cpp/memory/unique_ptr：unique_ptr 是一个智能指针，它通过指针拥有和管理另一个对象，并在 unique_ptr 超出作用域时处置该对象。有如下代码：

#include <bits/stdc++.h>

class Foo {
public:
  Foo() {
    std::cout << "Halo!" << std::endl;
  }
  ~Foo() {
    std::cout << "No!" << std::endl;
  }
};

void foo() {
  std::unique_ptr<Foo> p1 = std::make_unique<Foo>();
}

int main(void) {
  foo();
  std::cout << "Nah!" << std::endl;
  return 0;
}

// Output: 
// Halo!
// No!
// Nah!

调用完foo()，直接调用生成Foo对象的析构，而不是等到最后再去销毁该对象。

shared_ptr

shared_ptr其实就是对资源做引用计数——当引用计数为 0 的时候，自动释放资源。

参考:https://zhuanlan.zhihu.com/p/150555165

但这种指针会出现循环引用的问题，所以引出了weak_ptr。

weak_ptr

其指向对象，但不改变其引用计数。