基础知识

长时间写python的后遗症，cpp的一些基础知识都忘得差不多了，需要强化一下记忆。

  1. 四种cast

    • reinpreter_cast 非相关的类型之间转换。操作结果只是简单的从一个指针到别的指针的值的二进制拷贝。在类型之间指向的内容不做任何类型的检查和转换
    • const_cast用于修改类型的const或volatile属性。除了const 或volatile修饰之外，type_id和expression的类型是一样的，一般用于强制消除对象的常量性。
    • static_cast但没有运行时类型检查来保证转换的安全性。它允许执行任意的隐式转换和相反转换动作,主要包括：1 用于基本数据类型之间的转换 2 把空指针转换成目标类型的指针 3 把任何类型的表达式转换成void类型 4 应用到类的指针上，它允许子类类型的指针互相转换为父类类型的指针
    • dynamic_cast只用于对象的指针和引用，主要用于执行“安全的向下转型”，可能有重大运行时代价, dynamic_cast根据RTTI信息检查操作是否有效。即在转换时dynamic_cast会检查转换是否能返回一个被请求的有效的完整对象。需要有虚函数才能判断，上行转换时，dynamic_cast和static_cast的效果是一样的；在进行下行转换时（基类需要包含虚函数），dynamic_cast具有类型检查的功能，牺牲了效率，但比static_cast安全。

  2. constexpr 与 const 区别

constexpr表示这玩意儿在编译期就可以算出来（前提是为了算出它所依赖的东西也是在编译期可以算出来的）。而const只保证了运行时不直接被修改（但这个东西仍然可能是个动态变量）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

   constexpr int foo(int i){
       return i + 5;
   }
   int main(){
       int i = 10;
       std::array<int, foo(5)> arr; // OK 
       foo(i); // Call is Ok
       std::array<int, foo(i)> arr1; // Error 
   }

STL

  1. std::sort()的复杂度 参考stl 分析

    • 复杂度计算 log2n!次比较。这就是基于比较的排序算法的复杂度下界：Ω(logn!) 斯特灵级数展开，近似 = nlogn
    • 内省式排序
      • 在数据量足够大的情况使用快速排序；
      • 在快速排序掉入陷阱(一旦递归深度超出该阈值，初始值为__lg(last - first) * 2，即 2log2n，则认掉入陷阱)时，主动切换到堆排序；避免o(n2)的情况
      • 快排 主元选择了首元素、尾元素和中央位置元素三者中的中位数，不容易让快排掉入陷阱
      • 在快速排序和堆排序已经做到基本有序的情况下，或者数据量较小的情况下，主动切换到插入排序

  2. vector与其他vector有什么区别?

这里面存的每个bool以一个bit位为一个存储单元，deque以一个byte为存储单元，为了优化空间性能

继承与多态

继承：虚继承，解决菱形继承问题，c++对象模型(vtable)

多态：静态(编译期)：函数重载 动态(运行时)：虚函数 隐藏：子类函数覆盖父类函数功能

智能指针：
  • unique_ptr： 如果内存资源的所有权不需要共享，就应当使用这个（它没有拷贝构造函数），但是它可以转让给另一个unique_ptr（存在move构造函数）。
  • shared_ptr： 如果内存资源需要共享，那么使用这个（所以叫这个名字）。
  • weak_ptr： 持有被shared_ptr所管理对象的引用，但是不会改变引用计数值。它被用来打破依赖循环（想象在一个tree结构中，父节点通过一个共享所有权的引用(shared_ptr)引用子节点，同时子节点又必须持有父节点的引用。如果这第二个引用也共享所有权，就会导致一个循环，最终两个节点内存都无法释放）。
virtual关键字作用：
  • 虚函数，提供重写多态
  • 纯虚函数+override：提供接口类
  • 虚析构：使得释放基类指针是能向下转型释放子类内存，避免内存泄漏
  • 虚继承：菱形继承问题
虚函数表：链接
C语言实现多态：

1.函数重载 __VA_ARGS__

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#define func(...) myfunc((struct mystru) { __VA_ARGS__})
struct mystru {
    const char *name;
    double d;
    int number;
};
void myfunc(struct mystru ms) {
    printf("%s, %lf, %d\n", ms.name, ms.d, ms.number);
}
 
int main(int argc, char *argv[]) {
    func();
    func("hello", 1.1);
    func("hello");
    func("hello", 1.1, 100);
    func(.name = "hello");
    func(.d = 1.1);
    func(.number = 100);
    func(.d = 1.1, .name = "hello");
	return EXIT_SUCCESS;
}

2.虚函数：函数指针实现虚表

1
2
3
4
5
6
7
8
9

typedef struct Node* linkList; 
struct Node                                         // 链表节点
{ 
   void *data;                                 // 存储的数据指针
   linkList next;                              // 指向下一个链表节点
 
   void (*insertFirst)(linkList, void *);      // 在已有链表的表头进行插入节点操作的函数指针
   void (*linkListOutput)(linkList);           // 输出链表中数据到控制台操作的函数指针
};

泛型

模板特化与偏特化：比如stl::vector

函数模板只有全特化，没有偏特化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//泛化
template<class U, class T>
class Test {
public:
    Test() {
        cout << "Test 泛化" << endl;
    }
};
//偏特化
template< class T>
class Test<int,T>{
public:
    Test() {
        cout << "Test 偏特化" << endl;
    }
};
//全特化
template<>
class Test<int, char> {
public:
    Test() {
        cout << "Test 全特化" << endl;
    }
};
左值与右值

T& 指向的是 lvalue，而 const T& 指向的，却可能是 lvalue 或 rvalue

move() 是这样一个函数，它接受一个参数，然后返回一个该参数对应的右值引用.

1
2
3
4
5
6

1 void swap(T& a, T& b)
2 {
3      T tmp = move(a);
4      a = move(b);
5      b = move(tmp);
6 }

forward() 函数的作用：它接受一个参数，然后返回该参数本来所对应的类型的引用。常和remove_reference配合使用