CS106L Notes

Lecture 1: Welcome

Design Philosophy of C++

• Only add features if they solve an actual problem

  （C++ 标准委员会（负责语言发展的团队）在添加新特性（如 C++11, 14, 17, 20）时，会要求提案者证明这个新功能能解决一个现实世界中 C++ 程序员正面临的、且现有功能无法很好解决的问题。这就是为什么 C++ 的很多特性（比如 lambda 表达式、智能指针）都直接对应着特定的编程痛点。）

• Programmers should be free to choose their own style

• Compartmentalization is key
  **

• Allow the programmer full control if they want it

  （这是 C++ 最著名（也最危险）的原则之一，常被称为 “你不需要为你不用的东西付出代价”。C++ 提供了非常底层的能力，让你可以直接操控硬件和内存，例如：

  1. 指针 (Pointers): 允许你直接读写任意内存地址。
  2. 手动内存管理 (new/delete): 让你精确控制对象的生命周期和它在内存中的位置。
  3. 内联汇编 (Inline Assembly): 允许你在 C++ 代码中直接嵌入汇编语言指令。
     虽然现代 C++ 提供了更安全的替代品（如智能指针 std::unique_ptr），但它从不移除这些底层工具，以备你需要榨干最后一点性能时使用。）

• Don’t sacrifice performance except as a last resort

  （性能是 C++ 的立身之本。 C++ 的设计目标始终是使其成为运行速度最快的语言之一（与 C 和 Fortran 并驾齐驱）。这条原则意味着，C++ 的许多高级特性被设计为 “零成本抽象” (Zero-Cost Abstractions)。
  零成本抽象：指那些让你代码更易读、更安全的高级功能，但在编译后，它们产生的机器码和你自己手写底层 C 风格代码一样高效，不会增加任何运行时的开销。例子：

  1. 模板 (Templates): std::vector 在编译时就会生成一个专门处理 int 的类，其访问效率与 C 语言的 int[] 数组完全相同。
  2. std::sort 算法: 编译器通常会将其高度优化，运行速度往往比你自己随手写的快速排序更快。）

• Enforce safety at compile time whenever possible

Lecture 2: Types and Structs

*

auto d = “Hello”; // const char* (a C string)

这样用 `auto` 会被 compiler 推断为一个常量字符串的指针，若想修改字符串中的元素，会有报错。

:!g++ auto.cpp -o auto -Wall -Wshadow -Wextra -g -lm -O2 -std=c++11 && ./auto
auto.cpp:15:10: error: read-only variable is not assignable 

• auto is a keyword that tells the compiler to deduce the type of a variable, it should be used when the type is obvious or very cumbersome to write out.

Lecture 3: Initialization & References

• When do we use references/const references?

  • If we’re working with a variable that takes up little space in memory (e.g. int, double), we don’t need to use a reference and can just copy the variable
  • If we need to alias the variable to modify it, we can use references
  • If we don’t need to modify the variable, but it’s a big
    variable (e.g. std::vector), we can use const references

• You can return references as well!

  // Note that the parameter must be a non-const reference to return
  // a non-const reference to one of its elements!
  int& front(std::vector<int>& vec) {
      // assuming vec.size() > 0
      return vec[0];
  }
  int main() {
      std::vector<int> numbers{1, 2, 3};
      front(numbers) = 4; // vec = {4, 2, 3}
      return 0;
  }

Lecture 4: Streams

Lecture 5: Containers

• Container: An object that allows us to collect other objects together and interact with them in some way.

• Containers: Sequence and Associative
  Sequence: the position of element is up to programmer.
  Associative: access elements by keys, underlying core is complex data structure.

• Container Adaptors
  Container Adaptors are a “repackaging” of existing containers, which enforce specific data access rules (such as LIFO or FIFO) by limiting their functionality.
  e.g. stack is based on deque, queue is based on deque, priority_queue is based on vector

  std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
  // for Min-Heap, you cannot skip the intermediate parameters to set the third parameter.

Lecture 6: Iterators and Pointers

• Iterators: vector are accessed by index, map by key, and list can only be traversed sequentially. Is there a unified method to iterate over all these containers? Iterators.

• Iterators is a finger pointing to the file cabinet (containers). For any containers, iterators can:

  1. Dereference: Read/Write the file currently pointed to.
  2. Increment: Move to the next file.
  3. Comparison: Check whether we have already moved to the last file.

• Iterator Categories

  1. Forward Iterator: only support ++, e.g. unordered_map, unordered_set.
  2. Bidirectional Iterators: only support ++ and --, e.g. map, set, list.
  3. Random Access Iterators: support any random access. e.g. vector, deque.
  4. no Iterators: stack, queue, priority_queue.

• In Iterator, ++iter is faster than iter++.
  From now on, make a habit of using ++i instead of using i++!!

• convinient map iterator loop:

  std::map<int, int> map{{1, 6}, {2, 8}, {0, 3}, {3,9}};
  for (auto iter = map.begin(); iter != map.end(); ++iter) {
      const auto& [key, value] = *iter; // structured binding!
  }

• Iterators are a particular type of pointers!
  Iterators “point” at particular elements in a container, and Pointers can “point” at any objects in your code!

• Iter->first

  If you have a pointer ptr pointing to an object, you want to access the member variable var of this object.

  • old: (*ptr).var
  • new: ptr->var

  Iterators are pointers! so when checking elements [key, value] in map we can use Iter->first and Iter->second.