Job Interview Notes: C++ - random nonsense

[ C++ , interview ]

学习笔记没有很强的逻辑性，而且有很强的个人属性。学到哪里写哪里，哪里不会记哪里。学习笔记本来应该针对现代c++，但是由于本科时候学c++已经是很久以前，学了之后又从来没有正经使用过，因此笔记里会有很多很基础的c++语法或面向对象编程的相关内容和相对高级的c++特性夹杂在一起。

语言关键字，语法

const 相关
1. const 变量真的不能修改吗？考虑code example：
```
const int global_a = 10;
int main() {
  const int local_a = 10;
  return 0;
}
```
  使用lldb查看 global_a 和 local_a 的memory region，结果如下：
```
(lldb) memory region &global_a
[0x0000000100000000-0x0000000100004000) r-x __TEXT
Modified memory (dirty) page list provided, 1 entries.
Dirty pages: 0x100000000.
(lldb) memory region &local_a
[0x000000016f604000-0x000000016fe00000) rw-
Modified memory (dirty) page list provided, 6 entries.
Dirty pages: 0x16fde8000, 0x16fdec000, 0x16fdf0000, 0x16fdf4000, 0x16fdf8000, 0x16fdfc000.
```
  事实上只有 global_a 在内存中是只读的，local_a 在内存中是可写的。const 变量只是告诉编译器这个变量是只读的，但是并不会真的将这个变量放在只读内存区域。也就是说，const 变量不是真的不能改，而是编译器会拒绝这个代码。
2. 我真的想改 const 变量！
  1. 最简单的想法：既然内存是可以改的，那我拿到内存地址，直接改就行了！
    const int global_a = 10; int main() { const int local_a = 10; int *local_a_ptr = &local_a; *local_a_ptr = 20; return 0; }
    事实是，编译器仍然会拒绝这样的代码。
    test.cpp:4:8: error: cannot initialize a variable of type 'int *' with an rvalue of type 'const int *' 4 | int *local_a_ptr = &local_a; | ^ ~~~~~~~~ 1 error generated.
    编译器为什么会拒绝这样的代码呢？因为指针类型和指向的类型需要匹配，我们只能用 const int * 来指向 const int，而不能用 int * 来指向 const int。否则 const 的意义也太弱了。
  2. 如果硬要改，其实还是很简单的，但是会出现一些预期外的行为。
    #include <iostream> int main() { const int a = 10; // NOT ALLOWED by the compiler // int *a_ptr = static_cast<int *>(&a); int *a_ptr = (int *)&a; *a_ptr = 11; std::cout << a << " " << *a_ptr << std::endl; std::cout << &a << " " << a_ptr << std::endl; return 0; }
    上面的代码输出：
    10 11 0x16d8ff428 0x16d8ff428
    可以看到，a输出的值没有改变，但是a_ptr指向的值改变了，但他们本来应该是同一个值。因为编译器对声明为const的变量做了优化，默认在运行时不会改变，自然不需要再从内存访问。通过指针这样改变const变量的值，这样的行为是未定义的，不应该这样做。当然，也可以把a声明为volatile const int，这样起码输出的值是对的。C++还提供了const_cast来去掉const属性，但是int *a_ptr = const_cast<int *>(&a);这样的代码也是未定义行为。
3. const和指针/引用。C++中指针/引用类型和指向/引用的类型需要匹配，但是const是一个例外，例如:
```
int a = 10;
const int &a_ref = a; // a_ref is a reference to const int but a is non-const int
const int *a_ptr = &a; // a_ptr is a pointer to const int but a is non-const int
a = 11; // OK
// a_ref = 12; // NOT ALLOWED by the compiler
// *a_ptr = 13; // NOT ALLOWED by the compiler
```
4. const pointer VS pointer to const
  1. const pointer: int *const a_ptr = &a;，a_ptr是一个指向int的常量指针，指针本身是常量，指向的对象不是常量，a_ptr不能指向其他对象，但是可以改变指向对象的值。
  2. pointer to const: const int *a_ptr = &a;，a_ptr是一个指向const int的指针，指针本身不是常量，指向的对象是常量，a_ptr可以指向其他对象，但是不能改变指向对象的值。
  3. 技巧：从右到左读。int *const里面，int是base type，*const是type declarator。const int *里面，const int是base type，*是type declarator。
5. const, type alias and pointer
  1. 给出如下代码片段：
    using int_ptr = int *; int b = 0; const int_ptr ptr0 = &b; const int *ptr1 = &b; int *const ptr2 = &b; // ptr0 = nullptr; // error: cannot assign to variable 'ptr0' with const-qualified type 'const int_ptr' (aka 'int *const') *ptr0 = 1; // *ptr1 = 2; // error ptr1 = nullptr; *ptr2 = 3; // ptr2 = nullptr; // error
    需要注意的是，ptr0实际上是和ptr2等价。不能把type alias当作一个宏一样的机制来替换。type alias声明的是‘base type’，const修饰的也是base type，这个时候const修饰的是整个int *，而不只是int（ptr1）。

左值，右值，左值引用，右值引用，完美转发，引用折叠，移动/拷贝语义，std::move和std::forward，引用折叠

左值：表达式结束后仍然存在的对象，可以取地址，通常出现在赋值语句的左侧。
右值：临时对象，通常不能出现在赋值语句的左侧。
左值引用：用于引用左值，是引用对象的别名。
右值引用：用于引用右值，是引用对象的别名。主要的功能是实现移动语义和完美转发。

std::move：将一个左值转换为右值引用，用于实现移动语义。std::move的实现也相对简单：

template <class _Tp>
_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __libcpp_remove_reference_t<_Tp>&&
move(_LIBCPP_LIFETIMEBOUND _Tp&& __t) _NOEXCEPT {
  typedef _LIBCPP_NODEBUG __libcpp_remove_reference_t<_Tp> _Up;
  return static_cast<_Up&&>(__t);
}

std::forward：将参数保留原有的值类别（左值/右值）。常用于模板函数中的完美转发。std::forward的实现也相对简单：

template <class _Tp>
_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Tp&&
forward(_LIBCPP_LIFETIMEBOUND __libcpp_remove_reference_t<_Tp>& __t) _NOEXCEPT {
  return static_cast<_Tp&&>(__t);
}

左值引用和右值引用都是左值。

  int &&rref = 10;
  // int &&rref2 = rref;            // error：rref是左值
  int &&rref3 = std::move(rref);    // ok

移动语义：减少了内存拷贝。例如在作为参数传递时，传入左值时，左值会被拷贝一份，造成内存的浪费；传入右值时，不会发生内存拷贝。
拷贝语义：将所有资源进行深拷贝。

移动语义vs拷贝语义。

#include <iostream>
#include <utility>
#include <vector>

class MyVector {
public:
    std::vector<int> data;

    // 移动构造函数
    MyVector(std::vector<int> &&d) : data(std::move(d)) {}
    // 拷贝构造函数
    MyVector(const std::vector<int> &d) : data(d) {}
};

int main() {
    std::vector<int> vec = {1, 2, 3};
    MyVector cp(vec);            // vec的数据被拷贝到mv.data
    std::cout << vec.size() << std::endl; // output 3
    MyVector mv(std::move(vec)); // vec的数据被移动到mv.data
    std::cout << vec.size() << std::endl; // output 0
}

引用折叠：在模板函数中，引用折叠是指当一个引用被绑定到另一个引用时，编译器会将这两个引用合并为一个引用。引用折叠的规则如下：
1. T& & -> T&
2. T& && -> T&
3. T&& & -> T&
4. T&& && -> T&&

算法小技巧

由leetcode简单题27. 移除元素 - 力扣（LeetCode）想到的
1. 参数使用引用传递容易理解：要修改原本的vector
2. vector在不使用引用传递时的行为是什么？
  
  值传递，拷贝一份，开销大，因为是深拷贝（underlying memory也会拷贝，而不只是拷贝一份指针）
3. 这个行为是谁来做的？是编译器还是类声明的拷贝构造函数？
  
  不是编译器做的，是vector类自己声明的拷贝构造函数。
4. 在算法题中，自己声明的函数里，参数总是使用引用传递以提高效率。
push_back() vs emplace_back()
1. push_back() 的参数如果是一个临时变量，会调用拷贝构造函数在末尾添加，如果是一个右值对象（MyClass()），会调用移动构造函数在末尾添加
2. emplace_back() 的参数如果是构造函数的参数如 vec.emplace_back()（空构造函数），会直接在末尾调用构造函数来添加对象
3. emplace_back() 的参数如果是临时变量或者右值，则没有性能差异。
4. emplace_back() 的简单实现（placement new + 可变参数模板+完美转发）：
```
template <typename... Args>
void emplace_back(Args&&... args) {
    if (size_ == capacity_) {
        reserve(capacity_ == 0 ? 1 : capacity_ * 2);
    }
    new (data_ + size_) T(std::forward<Args>(args)...);
    ++size_;
}
```
5. 总是使用 emplace_back()。

现代C++

C++11不再允许将字符串字面量赋值给一个 char*，而只能赋值给一个 const char*。
1. 原因：字符串字面量本来就存储在不可写的内存区域，而 char* 是可写的，如果将字符串字面量赋值给 char*，可能会破坏这个不可写的内存区域，导致未定义行为。
2. 如果需要一个可写的字符串，可以使用 std::string = "hello" 或者 char str[] = "hello"。std::string 实际上是通过重载 = 操作符来实现的将.rodata段上的字符串拷贝到堆上，而 char str[] 实际上是编译器进行的栈上内存分配和拷贝。
类型推断:模板函数，auto和decltype
1. 模板函数类型推断。
```
template<typename T>
void f(ParamType param);
```
  1. 如果ParamType是一个指针或者引用，对T的推断会首先去除掉传入的参数类型中的引用部分，再与ParamType做模式匹配。
    template<typename T> void f(T& param); int x = 42; const int cx = x; const int& rx = x; f(x); // T is int, param is int&: not reference, pattern match `int` with T -> T is int f(cx); // T is const int, param is const int&: not reference, pattern match `const int` with T -> T is const int f(rx); // T is const int, param is const int&: is reference, remove reference, pattern match `const int` with T -> T is const int
    如果f()的ParamType是const T&，那么T都会是int（模式匹配），f(x)推断的ParamType则会是const int&。
  2. 如果ParamType是一个转发引用（Forwarding Reference。Effective Modern C++称通用引用，Universal Reference），需要区分传入的参数的类型。
    1. 如果传入的参数本身是一个右值，情况和1一样。也就是说，T会被推断为不带引用的类型例如int，ParamType会被推断为int&&。
    2. 如果传入的参数本身是一个左值，T和ParamType都会被推断为左值引用。
  3. 如果ParamType不是引用，如果传入的参数本身是引用，同样去掉引用。此时参数是值传递的，也就是参数会被复制一份。值传递的参数自然不需要保护其const性质，所以const限定也被去除，同样还有volatile限定。需要区分const char*和char * const的情况：前者的const限定会被保留，而后者的const限定会被去除，因为前者的const不是顶层const，也就是说修饰的是指向的对象而不是指针本身，而后者是顶层const，修饰的是指针本身，指针本身会被复制一份，所以const限定会被去除。
    #include <iostream> #include <type_traits> template <typename T> void func(T param) { if (std::is_same_v<decltype(param), int *>) { std::cout << "int *" << std::endl; } if (std::is_same_v<decltype(param), const int *>) { std::cout << "const int *" << std::endl; } if (std::is_same_v<decltype(param), const int *const>) { std::cout << "const int *const" << std::endl; } if (std::is_same_v<decltype(param), const int>) { std::cout << "const int" << std::endl; } if (std::is_same_v<decltype(param), int>) { std::cout << "int" << std::endl; } } int main() { int ci = 42; const int *ptr = &ci; int *const cptr = &ci; const int &cref = ci; func(ptr); // const int * func(cptr); // int * func(cref); // int }
  4. 对于数组类型的参数，形如T的类型推断会退化为指针类型，而形如T &的类型推断则不会退化，保持原有的数组类型。即对 const int arr[3]，f(T param)中T会被推断为const int *，而f(T &param)中T会被推断为const int[3]，param的类型则会是const int (&)[3]。书上提到了有趣的用途是constexpr std::size_t arraySize(T (&)[N]) noexcept {return N;}，可以用来获取数组的长度。函数类型的参数和数组相似。
2. auto类型推断
  1. 与模板函数类型推断的一致性
    template<typename T> void f1(T param); template<typename T> void f2(T& param); template<typename T> void f3(T&& param); template<typename T> void f4(const T& param); auto x = 10; // -> f1(x) -> T is int, type of x is int auto& y = x; // -> f2(y) -> T is int, type of y is int& auto&& z = x; // -> f3(z) -> T is int&, type of z is int& auto&& w = 10; // -> f3(w) -> T is int, type of w is int&& const auto& u = x; // -> f4(u) -> T is int, type of u is const int&
  2. 特殊情况：使用{}初始化时，auto类型推断会推断为std::initializer_list<T>。
    
    So the only real difference between auto and template type deduction is that auto assumes that a braced initializer represents a std::initializer_list, but template type deduction doesn’t.
  3. 使用auto推断函数参数和返回值类型时采用的不是auto类型推断，而是模板函数类型推断。
    
    However, these uses of auto employ template type deduction, not auto type deduction.
3. decltype
  1. 基本用法: 用来获取变量的类型，可以用类似 std::is_same_v<decltype(var), int> 的方式判断是否是某数据类型。
  2. 常见于模板函数中返回值类型取决于参数类型的情况: decltype(auto) f() {return xxx;} 。为什么不直接使用auto f() {return xxx;}? 因为auto 使用的是template type deduction, 如果返回值是引用类型，则引用会被忽略而造成错误。
  3. 特殊情况:传入的左值不是变量名而是表达式时，decltype 总是返回T&而不是T。
  4. 代码示例。注意还需要使用转发引用和std::forward 来处理传入的参数是右值的情况。
    template<typename Container, typename Index> decltype(auto) authAndAccess(Container&& c, Index i) { authenticateUser(); return std::forward<Container>(c)[i]; }
关于auto 我们需要知道的
1. 使用auto 的好处：
  1. 防止未初始化的变量：auto 要求变量必须被初始化。不然怎么推断类型呢？
  2. 不用写超长的变量类型了。
  3. auto 可以用来声明lambda表达式：lambda表达式的类型只有编译器知晓，如果不使用auto 就无法声明一个lambda 类型的变量来后续使用。虽然std::function 也可以用来声明lambda表达式，但是它使用的是一个泛型模板，这个模板不论函数或者闭包的类型，所占用的内存空间都是一样的，如果闭包的参数较多，可能出现预分配的内存不够的情况，可能需要申请动态内存。auto 则不会有这个问题，其所占用的内存大小和闭包实际需要的内存大小是一致的。甚至使用std::function 的闭包由于实现细节，运行速度也会慢于使用auto 的。
  4. 防止type mismatch 。示例包括不注意的隐式类型转换:
    std::vector<int> v; unsigned sz = v.size(); // wrong! 32bit system 32bit unsigned but 64 bit std::vector<int>::size_type auto sz = v.size(); // good! std::unordered_map<std::string, int> m; for (const std::pair<std::string, int> &p : m) {} // wrong! right type is std::pair<const std::string, int>. implicit casting will happend to cause performance issue. for (const auto &p : m) {} // good!
2. 坏处可能是代码可读性但一般不成问题。
3. auto 应该被避免的场景：”invisible proxy class type” 。比如std::vector<bool> 的[] 运算符的返回结果并不是bool，而是一个 proxy class ，这时候就可能需要进行显式的类型转换：prefer auto ret = static_cast<bool>vec[i]; to bool ret = vec[i]; to auto ret = vec[i] which is wrong。
std::function

面向对象

类的virtual function
1. virtual function的调用是通过虚函数表来进行的（动态绑定，运行时多态）
2. 每一个类对象的内存布局最前方保存了一个 vptr，指向这个对象的虚函数表，虚函数表中再指向了具体的函数实现，虚函数在调用时，只与对象的实际类型有关，而与当前指针的静态类型无关
3. 普通函数的调用是编译器直接在编译时决定了调用地址，callq 0x1210 就可调用了，而不需要在运行时计算调用的地址。类的普通成员函数实质上是类的作用域中的全局函数，也就是和一个普通的函数没有区别，都是按照绝对的内存地址来调用的。类的内存布局里实际上只包含 vptr 和成员变量，而不包含普通成员函数。
4. code example
```
#include <iostream>

class A {
public:
    virtual void foo(void) {
        std::cout<<"A foo"<<std::endl;
    }

    void bar(void) {
        std::cout<<"A bar"<<std::endl;
    }
};

class B : public A {
    void foo(void) override {
        std::cout<<"B foo"<<std::endl;
    }

    void bar(void) {
        std::cout<<"B bar"<<std::endl;
    }
};

int main() {
    B b;
    A* a = &b;
    a->foo(); // B foo
    a->bar(); // A bar
    return 0;
}
```
Plain Old Data（POD）
1. POD服从C ABI，可以进行二进制传递
2. POD = trivial && standard_data_layout
3. is_pod_v(obj)(deprecated)=is_standard_data_layout_v(obj) && is_trivial_v(obj)
4. Trivial: 所有的构造、析构、移动、拷贝、赋值都是由编译器自动生成的，可以通过简单的memcpy来复制，memmove来移动
5. Standard-layout：符合C语言中struct的标准内存排列
  1. 所有非静态成员都是相同的访问控制（public，private，protected）
  2. 没有虚函数或虚基类
  3. 所有非静态数据成员在基类中的顺序与其声明顺序一致。
  4. 不能有多个基类中包含相同类型的成员
虚基类（virtual base）
1. 解决菱形继承问题

Data member pointer

data member pointer（数据成员指针）是指向类的成员变量（非静态成员）的指针。它允许通过指针来访问类的某个成员变量，而不是通过对象直接访问。
为什么不能是静态成员？data member pointer是一个相对于对象的内存布局的offset，而静态成员位于单独的内存区域，不和任何一个对象有关系。

code example

#include <iostream>
using namespace std;

class X {
public:
  int a;
  void f(int b) {
    cout << "The value of b is "<< b << endl;
  }
};

int main() {

  // declare pointer to data member
  int X::*ptiptr = &X::a;

  // declare a pointer to member function
  void (X::* ptfptr) (int) = &X::f;

  // create an object of class type X
  X xobject;

  // initialize data member
  xobject.*ptiptr = 10;

  cout << "The value of a is " << xobject.*ptiptr << endl;

  // call member function
  (xobject.*ptfptr) (20);
}

标准库

revision history

ToC

语言关键字，语法

算法小技巧

现代C++

面向对象

标准库