CS106L Note

Types and Structs

1. statically typed language

• C++ is a statically typed language, statically typed: everything with a name (variables, functions, etc) is given a type before runtime.

# Python(Dynamic) VS C++(Static)
a = 3
b = "test”
def func(c):
// do something

int a = 3;
string b = "test”;
char func(string c) {
// do something
}

def div_3(x):
  return x / 3
div_3("hello")
// Crash during runtime, can’t divide a string

int div_3(int x){
  return x / 3;
}
div_3("hello")
// Compile error: this code will never run

2. auto 和 std::make_pair

• auto: auto does not mean that the variable doesn’t have a type. It means that the type is deduced by the compiler.

• std::pair< >, std::make_pair

std::pair<int, string> numSuffix = {1,"st"};
cout << numSuffix.first << numSuffix.second;

// To avoid specifying the types of a pair, use std::make_pair(field1, field2)
std::make_pair(false, 2);

Streams

1. ostream and ofstream

• std::cout is an output stream. It has type std::ostream. 在 C++ 中，std::cout 是一个标准输出流对象，用于向控制台输出数据。它是标准库中定义的 std::ostream 类型的一个实例。

• std::ofstream

  -Only receive data using the << operator

  -Converts data of any type into a string and sends it to the file stream

  -Must initialize your own ofstream object linked to your file

std::ofstream out(“out.txt”, std::ofstream::out);
out << 5 << std::endl; // out.txt contains 5

• std::cout is a global constant object that you get from #include To use any other output stream, you must first initialize it!

2. istream and ifstream

• std::cin: 首次调用 cin >> 会创建一个命令行提示符，允许用户输入内容，直到按下回车键。每个 >> 运算符只会读取到下一个空白字符（空格、制表符或换行符）之前的内容。第一个空白字符之后的所有内容都会被保存，并在下次调用 std::cin >> 时使用。这些被保存的内容存储在一个称为缓冲区的地方。缓冲区是一个临时存储区域，用于存放输入流的数据。如果缓冲区中没有等待的内容，std::cin >> 会创建一个新的命令行提示符，等待用户输入。

• std::istream

  -Can only receive data using the >> operator

  -Receives a string from the stream and converts it to data

• std::ifstreams

  -Only send data using the >> operator

  -Receives data of any type into and converts it into a string to send to the file stream

  -Must initialize your own ifstream object linked to your file

std::ifstream in(“out.txt”, std::ifstream::in);
// in is now an ifstream that reads from out.txt
string str;
in >> str; // first word in out.txt goes into str

3. », «, getline, stringstreams

• >> is the stream extraction operator or simply extraction operator
  • Used to extract data from a stream and place it into a variable
• << is the stream insertion operator or insertion operator
  • Used to insert data into a stream usually to output the data to a file, console, or string

• Reading using >> extracts a single “word” or typeincluding for strings.

• To read a whole line, use std::getline()

istream& getline(istream& is, string& str, char delim);

• stringstreams
  • What: A stream that can read from or write to a string object
  • Purpose: Allows you to perform input/output operations on a string as if it were a stream

std::string input = "123";
std::stringstream stream(input);
int number;
stream >> number;
std::cout << number << std::endl;  // Outputs "123"

Initialization & References

1. 统一初始化

• Uniform initialization: curly bracket initialization.

std::vector<int> vec{1,3,5};
  std::pair<int, string> numSuffix1{1,"st"};
  Student s{"Frankie", "MN", 21};
  // less common/nice for primitive types, but possible!
  int x{5};
  string f{"Frankie"};

2. 结构化绑定

• Structured binding lets you initialize directly from the contents of a struct

// Before
auto p = std::make_pair(“s”, 5);
string a = s.first;
int b = s.second;
// After
auto p = std::make_pair(“s”, 5);
auto [a, b] = p;

3. 左右值

• l-values vs r-values (左值 右值)

4. 引用

• Can’t declare non-const reference to const variable!

const std::vector<int> c_vec{7, 8};  // a const variable

  // BAD - can't declare non-const ref to const vector
  std::vector<int>& bad_ref = c_vec;

  // fixed
  const std::vector<int>& bad_ref = c_vec;

  // BAD - Can't declare a non-const reference as equal to a const reference!
  std::vector<int>& ref = c_ref;

• Use const references to avoid making copies whenever possible

class BigObject {
public:
    // 假设 BigObject 有复杂的数据结构和大量的成员变量
    // ...
};

void processBigObject(const BigObject& obj) {
    // 对大型对象进行一些处理，但不修改它的值
    // ...
}

int main() {
    BigObject obj;  // 创建一个大型对象
    processBigObject(obj);  // 使用常量引用传递对象进行处理
    return 0;
}

Containers

• Unordered maps/sets
  • Ordered maps/sets require a comparison operator to be defined.
  • Unordered maps/sets require a hash function to be defined. Simple types are already natively supported; anything else will need to be defined yourself.
  • Unordered containers are faster, but can be difficult to get to work with nested containers/collections
  • If using complicated data types/unfamiliar with hash functions, use an ordered container
• Container Adaptors: A wrapper on an object changes how external users can interact with that object. eg. stack, queue, priority_queue

Iterators and Pointers

• 迭代器分为五类

// use iterator
std::set<int> set{3, 1, 4, 1, 5, 9};
for (auto iter = set.begin(); iter != set.end(); ++iter) {
     const auto& elem = *iter;
     cout << elem << endl;
 }

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

// iterator is evolving!
std::set<int> set{3, 1, 4, 1, 5, 9};
for (const auto& elem : set) {
 	cout << elem << endl;
}

std::map<int> map{{1, 6}, {1, 8}, {0, 3}, {3, 9}};
for (const auto& [key, value] : map) {
 	cout << key << ":" << value << ", " << endl;
}

Classes

1. 模板类语法及头文件

• Writing a Template Class: Syntax

//mypair.h
template<typename First, typename Second> class MyPair {
      public:
          First getFirst();
          Second getSecond();
          void setFirst(First f);
          void setSecond(Second f);
      private:
          First first;
          Second second;
};

//mypair.cpp
#include “mypair.h”
// Must announce every member function is templated
template<typename First, typename Second>
// The namespace of the class isn’t just MyPair, it's 'MyPair<First, Second>'
First MyPair<First, Second>::getFirst(){
  return first;
}

• Templates don’t emit code until instantiated, so include the .cpp in the .h instead of the other way around!

Template Classes and Const Correctness

1. Member Types

• Member Types: Syntax

//vector.h
template<typename T> class vector {
    public:
      using iterator = T*;  // something internal like T*
      iterator begin();
}

//vector.cpp
template <typename T>
iterator vector<T>::begin() {...}
//compile error! Why?
//iterator is a nested type in namespace vector<T>::

// OK!
typename vector<T>::iterator vector<T>::begin() {...}

1. “Member Types: Summary-Used to make sure your clients have a standardized way to access important types.” 成员类型用于确保客户端以标准化的方式访问重要类型。这意味着在类中定义的成员类型可以提供对类中重要类型的访问，并确保客户端代码能够以一致的方式使用这些类型。

2. “Lives in your namespace: vector<T>::iterator.” 成员类型存在于命名空间中，即 vector<T>::iterator 是在命名空间中定义的。这意味着使用 vector 类时，可以直接使用 vector<T>::iterator 来表示迭代器类型。

3. “After class specifier, you can use the alias directly (e.g. inside function arguments, inside function body).” 在类说明符（class specifier）之后，可以直接使用成员类型的别名。这意味着在类的函数参数或函数体内部，可以直接使用成员类型的别名，而不需要再使用完整的类型名称。

4. “Before class specifier, use typename.” 在类说明符（这里指类型别名，即 using iterator = T*) 之前，需要使用 typename 关键字。这是因为在类说明符之前，编译器无法确定成员类型是一个类型还是其他实体（如成员变量）。通过使用 typename 关键字，我们明确指示该名称是一个类型。

5. When returning nested types (like iterator types), puttypename ClassName<T1, T2..>::member_type as return type, not just member_type

2. Const Class

• Const and Classe: All member functions marked const in a class definition. Objects of type const ClassName may only use the const-interface.

• 所以何时可以将一个类成员函数声明为 const？换句话说，哪个函数可以被 const object 使用？

3. static_cast and const_cast

• static_cast and const_cast

• Should begin() and end() be const?

注意现在这里是 const std::string*，指针指向的是常量，不可修改常量

• auto will drop all const and &, so be sure to specify

Template Functions

1. implicitly or explicitly call

• Default Types

template <typename Type>
Type myMin(Type a, Type b){
  return a<b ? a: b;
}
cout << myMin<int>(3, 4) << endl; // 3

• Template functions can be called (instantiated) implicitly or explicitly
• Template parameters can be explicitly provided or implicitly deduced

  template <typename T, typename U>
  auto smarterMyMin(T a, U b) { // auto, implicitly deduced
  return a < b ? a : b;
  }
cout << myMin(3.2, 4) << endl; // implicitly
cout << myMin<double, int>(3.2, 4) << endl; // explicitly

2. template type deduction

• Template type deduction

当模板函数的参数是引用或指针时，类型推导（Type Deduction）的规则如下：

1. 忽略 “&”：在类型推导过程中，会忽略参数类型中的 “&” 符号。这意味着无论参数是引用还是非引用类型，在类型推导时都将被视为非引用类型。

2. 匹配参数类型和输入参数：编译器会根据函数调用时传递的参数类型，与函数模板的参数类型进行匹配。如果参数类型匹配成功，则进行类型推导。

   • 如果传递的参数是非引用类型（例如 int、double），则类型推导直接使用传递的参数类型。

     template <typename T>
     void foo(T param);
     
     int x = 10;
     foo(x);  // T 推导为 int
     

   • 如果传递的参数是引用类型（例如 int&、const double&），则类型推导会忽略引用，并将参数类型视为非引用类型。

     template <typename T>
     void bar(T param);
     
     int y = 20;
     const double& z = 3.14;
     bar(y);  // T 推导为 int
     bar(z);  // T 推导为 double
     

   • 如果传递的参数是指针类型（例如 int*、const double*），则类型推导会忽略指针，并将参数类型视为非指针类型。

     template <typename T>
     void baz(T param);
     
     int* ptr1 = new int(30);
     const double* ptr2 = new double(3.14);
     baz(ptr1);  // T 推导为 int
     baz(ptr2);  // T 推导为 double
     

   • 添加 const 修饰符：如果传递的参数是 const 类型（例如 const int、const double*），则在类型推导过程中会添加 const 修饰符。

      template <typename T>
      void qux(T param);
     
      const int a = 40;
      const double* b = new double(3.14);
      qux(a);  // T 推导为 const int
      qux(b);  // T 推导为 const double*
     

3. 模板元编程(TODO)

• Template Metaprogramming: Writing code that runs during compilation (instead of run time)

4. constexpr

• constexpr: There are other ways in C++ to make code run during compile time.

Operator Overloading

• Member Functions

• Non-Member Functions

  • 在 Member Functions 中定义符号重载的局限：

    成员函数操作符（例如运算符重载函数）只能在对象的左操作数上调用。这意味着操作符函数必须作为调用对象的成员函数存在，而不是作为右操作数的成员函数。 在某些情况下，可能无法控制操作的左操作数，尤其是当你想要比较两个不同类型的对象时。例如，你想要比较一个 double 和一个 Fraction 对象。由于 double 是内置类型，你无法为其定义成员函数操作符。因此，你无法直接在 double 对象上调用 对 Fraction 类的成员函数操作符。

    解决这个问题的一种方法是使用非成员函数操作符重载。例如，你可以定义一个非成员函数 operator== 来比较 double 和 Fraction 对象。

    bool operator==(double d, const Fraction& f) {
        // 比较逻辑
    }
    

  • 当你想要定义一个非成员函数时，你可以在函数定义中不使用类作用域来声明该函数。这样你就可以在任何地方定义该函数，并且它不会作为类的成员函数存在。

  • 当想访问类的私有成员时，可以声明为友元函数

    class Time {
        public:
         friend bool operator == (const Time& lhs, const Time& rhs);
        private:
         int hours, minutes, seconds;
    }
    
    // 没有用域解析运算符::，说明是一个非成员函数
    bool operator == (const Time& lhs, const Time& rhs) {
        return lhs.hours == rhs.hours && lhs.minutes == rhs.minutes && lhs.seconds == rhs.seconds;
    }
    

  • 重载«

    std::ostream& operator << (std::ostream& out, const Time& time) {
    	out << time.hours << ":" << time.minutes << ":" << time.seconds;
    	return out;
    }
    // in time.h -- friend declaration allows access to private attrs
    public:
    	friend std::ostream& operator << (std::ostream& out, const Time& time);
    // now we can do this!
    cout << t << endl; // 5:22:31
    

    

Functions and Lambdas

• Predicate Functions: Any function that returns a boolean value is a predicate!

• Function Pointers

• Lambdas

• lambdas 原理

当我们使用 lambda 表达式时，实际上编译器会创建一个匿名的 lambda 类，该类提供了一个重载的operator()来实现 lambda 表达式的功能。这个 lambda 类就是一个函数对象，也就是一个 Functor。我们可以将 lambda 表达式赋值给变量或将其作为参数传递给函数，从而创建函数对象的实例。

在运行时，当我们使用 lambda 表达式创建一个闭包（Closure）时，编译器会实例化对应的 lambda 类，并生成一个闭包对象。闭包是 lambda 表达式的实例，可以将其视为函数对象的实例。闭包包含了 lambda 表达式中的代码以及其捕获的变量的状态。

• How do functors, lambdas, and function pointers relate?

Special Member Function(SMFs)

1. What is SMFs

These functions are generated only when they’re called (and before any are explicitly defined by you), We don’t have to write out any of these! They all have default versions that are generated automatically:

• all SMFs are public and inline function, meaning that wherever it’s used is replaced with the generated code in the function
• Copy Constructor : Object created as a copy of existing object (member variable-wise)
• Copy Assignment Operator : Existing object replaced as a copy of another existing object.

2. Initializer Lists(鼓励使用)

上图第一个是默认的构造函数：members are first default constructed (declared to be their default values)， Then each member is reassigned. This seems wasteful!

第二个则 Directly construct each member with a starting value!

3. Why override SFMs?

1. Sometimes, the default special member functions aren’t sufficient!

   By default, the copy constructor will create copies of each member variable. This is member-wise copying! If your variable is a pointer, a member-wise copy will point to the same allocated data, not a fresh copy!

   Many times, you will want to create a copy that does more than just copies the member variables.
   e.g. deep copy: an object that is a complete, independent copy of the original

Example 1: How do we fix the default copy constructor?（根据另一个现有的对象创建新的对象）

    template <typename T>
     vector<T>::vector<T>(const vector::vector<T>& other) :
        _size(other._size),
        _capacity(other._capacity),
        _elems(new T[other._capacity]) { //create a new array and copy all of the elements over. And use initializer list!
        std::copy(other._elems,
                  other._elems + other._size, _elems);
     }

Example 2: How do we fix the default copy assignment operator?(现有的对象由另一个现有的对象覆盖)

  template <typename T>
   vector<T>& vector<T>::operator = (const vector<T>& other) {
   	if (&other == this) return *this; 	// 处理edge情况
  	_size = other._size;
   	_capacity = other._capacity;
   	delete[] _elems;	// 小心内存泄漏
   	_elems = new T[other._capacity];
   	std::copy(other._elems, other._elems + other._size, _elems);
   	return *this;	//	注意函数签名及返回值
  }

4. = delete and = default

Adding = delete; after a function prototype tells C++ to not generate the corresponding SMF!

Adding = default; after a function prototype tells C++ to still generate the default SMF, even if you’re defining other SMFs!

5. Rule of 0 and Rule of 3: When should we rewrite SMFs?

• Rule of 0: If the default operations work, then don’t define your own!

• When should redefine? Most common reason: there’s a resource that our class uses that’s not stored inside of our class. e.g. dynamically allocated memory, our class only stores the pointers to arrays, not the arrays in memory itself!
• Rule of 3: If you explicitly define a copy constructor, copy assignment operator, or destructor, you should define all three! Why? If you’re explicitly writing your own copy operation, you’re controlling certain resources manually. You should then manage the creation, use, and releasing of those resources!

6. Move constructors and move assignment operators

&&： 右值引用（Rvalue Reference）的运算符。右值引用是 C++11 引入的一种引用类型，用于绑定到临时对象（右值）。它与左值引用（左值引用使用符号&）相对应。右值引用的主要目的是支持移动语义（Move Semantics）和完美转发（Perfect Forwarding）。

Move Semantics

1. some confused things

注意到 Only l-values can be referenced using &! 这里可行是因为 r-values can be bound to const & (we promise not to change them)

SMFs 分析

2. && 操作符

int main() {
      int x = 1;
      change(x); //this will call version 2
      change(7); //this will call version 1
  }
  void change(int&& num){...} //version 1 takes r-values
  void change(int& num){...}  //version 2 takes l-values

The compiler will pick which vector::operator= to use based on whether the RHS is an l-value or an r-value：

3. std::move

-std::move(x) doesn’t do anything except cast x as an r-value

-It is a way to force C++ to choose the && version of a function

cint main() {
    int x = 1;
    change(x); //this will call version 2
    change(std::move(x)); //this will call version 1
}
void change(int&& num){...} //version 1 takes r-values
void change(int& num){...}  //version 2 takes l-values

• Where else should we use std::move?

-Notice: we need both a copy assignment AND a move assignment(例如前面重载=操作符的例子)

-Rule of Thumb: Wherever we take in a const & parameter in a class member function and assign it to something else in our function.

-Don’t use std::move outside of class definitions, never use it in application code!

-If your class has copy constructor and copy assignment defined, you should also define a move constructor and move assignment（出于高效率的考虑，可参考前面的 SMFs 分析部分）

4. Rule of Five（continue 3 and 5）

-If you define custom copy constructor/assignment operator, you should define move constructor/assignment operator as well

-Why? This is about efficiency rather than correctness. It’s inefficient to make extra copies (although it is “correct”)

Type Safety and std::optional

• const-interface: All member functions marked const in a class definition. Objects of type const ClassName may only use the const-interface.

• Type Safety(原则): The extent to which a function signature guarantees the behavior of a function.

• What is std::optional?

//The problem
 valueType& vector<valueType>::back(){
 	return *(begin() + size() - 1);
 }
//Dereferencing a pointer without verifying it points to real memory is undefined behavior!

// can do better
valueType& vector<valueType>::back(){
     if(empty()) throw std::out_of_range;
     return *(begin() + size() - 1);
 }
// now it's deterministic behavior

// Deterministic behavior is great, but can we do better?
// There may or may not be a “last element” in vec.
// The function signature gives us a false promise! Promises to return an something of type valueType. How can vec.back() warn us of that when we call it?
// What if back() returned an optional?
std::optional<valueType> vector<valueType>::back(){
     if(empty()){
        return {};
     }
     return *(begin() + size() - 1);
}

void removeOddsFromEnd(vector<int>& vec){
     while(vec.back().value() % 2 == 1){
     vec.pop_back();
     }
}
// Now, if we access the back of an empty vector, we will at least reliably get the bad_optional_access error

• std::optional<T&> is not available!

RAII, Smart Pointers, and C++ Project Building

1. RALL, Resource Acquisition Is Initialization

• All resources used by a class should be acquired in the constructor
• All resources used by a class should be released in the destructor

Some examples that are not RALL complaint:

结合 exceptions-catch，在 application code 显式调用 new 的确容易造成问题

2. Smart Pointers

Some problems:

3. Building C++ Projects

After your program is written, it needs to be translated to a language your computer can understand. This is done through the process known as compiling !A compiler is just any program that turns translates code from one language to another. A common one for C++ to machine-readable code is g++!

4. make, cmake, makefile

写在最后

这篇笔记本是存在本地的，建了博客网站后想着拿一篇文章放上去看效果，通过修改笔记格式的同时复习了一遍内容，同时也能对博客主题美中不足之处进行美化修改，从而这份笔记也顺势成为了我博客中的第一篇文章了，算是有个纪念意义。