26春CS100期中复习

26春CS100期中复习

AlexWei Lv1
  2026-05-23 19:40 2026-05-23 19:40 创建   2026-05-23 20:01:57 2026-05-23 20:01:57 更新    4.8k 字  21 分钟  

尚未完成 C部分待补充 细节待Review

C++ Part

Lec11-13 C++ Basics

Standard library

  • Standard Library中的names都被placed in std这个namespace, e.g. std::cin
  • 对C standard library的兼容: 改#include <xxx.h>为#include <cxxx>

<iostream>

std::cin, std:cout

e.g. A+B Problem

1
2
3
4
5
6
7
#include <iostream>
int main(){
  int a,b;
  std::cin >> a >> b;
  std::cout << "a+b= " << a+b << '\n';
  return 0
}

Question: std::cin >> s会忽略leading whitespaces吗?

Answer: 会. 例如用户输入” abc”, 实际读到s == "abc"

Question: std::cin >> s会读取整行吗? 什么时候停止读取?

Answer: 不会, 一旦遇到空白即停止. 例如用户输入”Hello World”, 实际读到s == "Hello"

Question: 如果我既不想忽略leading whitespaces, 又不想读取整行, 怎么做?

Answer: 使用std::getline(std::cin, s) 它会一直读到换行符\n再停(consume it) , 但并不会存储\n

<string>

定义与初始化
1
2
3
4
5
6
std::string str0 = "aaa"; //operator= overloading
std::string str1{"aaa"};//调用构造函数 equivalent(用{}更modern): std::string str1{"aaa"};
std::string str2(3,'a');//调用构造函数
//以上三种效果等价
std::string str3 = str0 //拷贝str0内容到str3
std::string str4; //默认初始化为空字符串(default constructor行为)

可以用+做拼接(concatenation), 至少一边是std::string, +是左结合

用a += b, 语义同a = a+b, 但省去了建构临时objecta+b, 拷贝a的资源浪费

直接用<,<=,>,>=,==,!=等符号即可做字典序(lexicographical)比较, 不用像C一样用strcmp

Member functions
  • .size()
  • .empty()

<vector>

动机: 一个”better dynamic array”, 自动管理内存, 提供一系列内置方法, 自动拷贝, 有默认空初始化

  • 存储不同<类型>成员的std::vector不是同一类型
Create a std::vector

回忆: constructor相关知识

1
2
3
4
5
std::vector<int> v{2, 3, 5, 7}; // A vector of `int`s,
																// whose elements are {2, 3, 5, 7}.
std::vector<int> v2 = {2, 3, 5, 7}; // Equivalent to ↑
//补充写法:C++17 CTAD 让编译器自己deduce类型 下句会自动推断为vector<int>
std::vector v3= {2, 3, 5, 7}
Copy a std::vector
1
2
3
std::vector<int> v2 = v; // `v2`` is a copy of `v`
std::vector<int> v3(v); // Equivalent
std::vector<int> v4{v}; // Equivalent
内置方法(类成员函数)

.size()

.empty()

.push_back()(加到末尾 回忆python list.append())

.pop_back() (删除末尾 回忆python list.pop())

.front()和.back() 返回首/尾位置的引用

.at(index) 比[index]更好的下标访问, 有边界检查, 越界会throw exception: std::out_of_range

References (左值)引用

概念理解: 把一个别名(alias)绑定到一个对象(object)上

syntax: ReferredType &reference_name = some_referred_to_object

行内声明多个同类型references时, &要写在每一个reference_name前

错误示范: 

1
2
int& x = ival, y = ival, z = ival;
// Only `x` is a reference. `y` and `z` are of type `int`.

一个引用只能被一次性绑定到一个对象, 不可重复绑定, 但一个对象可以有多个引用

补充: * and &各种用途大汇总

Both symbols have many identities!

  • In a declaration like Type *x = expr ,* is a part of the pointer type Type *. *声明指针

  • In a declaration like Type &r = expr , & is a part of the reference type Type & . &声明引用

  • In an expression like *opnd where there is only one operand, * is the dereference operator. *解引用

  • In an expression like &opnd where there is only one operand, & is the address-of operator.&取地址

  • In an expression like a * b where there are two operands, * is the multiplication operator. *做乘法

  • In an expression like a & b where there are two operands, & is the bitwise-and operator. &二进制与

reference-to-const

动机: 三大优点如下

  1. 避免拷贝 Avoids copy.

  2. 可绑右值(注意这点与一般reference不同) Accepts temporaries and literals (rvalues).

  3. 避免错误修改应该只读的量 The const qualification prevents accidental modifications to it.

e.g.

1
2
3
4
5
6
7
8
9
10
11
int count_lowercase(const std::string &str) { // `str` is a reference-to-`const`
	int cnt = 0;
	for (char c : str)
		if (std::islower(c))
			++cnt;
	return cnt;
}
std::string a = something(), b = some_other_thing();
int res1 = count_lowercase(a); // OK.
int res2 = count_lowercase(a + b); // OK.
int res3 = count_lowercase("hello"); // OK.

Range-based for loops

e.g. for (char c : s)

联想: 类似python中for c in s?

  • 若要对s进行修改, 需声明循环变量c为引用char &c :s

类型转换

字符串 and 数字(arithmetic numbers)

function(此处省略std::, 定义在<string>) explanation
stoi()(string to int), stol()(string to long), stoll(string to long long) 字符串–>有符号整数
stoul()(string to unsigned long), stoull()(string to unsigned long long) 字符串–>无符号整数
stof()(string to float), stod()string to double, stold()(string to long double) 字符串–>浮点数
to_string() 整数/浮点数–>字符串

Explicit Casts

const_cast

去掉low-level constness(DANGEROUS)

注意⚠️: 从const_castform的non-const access path修改const变量(top-level-const)会UB, 非必要不用const_cast 这样的危险行为

1
2
3
4
int ival = 42;
const int &cref = ival;
int &ref2 = const_cast<int &>(cref); // OK
int *ptr = const_cast<int *>(&cref); // OK
reinterpret_cast

转换指针类型(DANGEROUS)

注意⚠️: 勿忘实际指向的对象还是原类型, 不能当成一般转换后类型的指针用, 非必要不用reinterpret_cast

static_cast

详见Lec19 类型转换部分

auto

动机: 声明变量时, 让编译器推断类型, 简化某些very long types, 或者我们不知道但编译器知道的特殊类型, 如对lambda expression

一些例子:

1
2
3
4
5
6
7
8
9
auto x = 42; // `int`
auto y = 3.14; // `double`
auto &r = x; // `int &`

auto str = "hello"; // 注意⚠️ 为了C兼容性 这里推断为`const char *`, 不是`std::string`

auto it = vs.begin();

auto lam = [](int x, int y) { return x + y; } // A lambda expression.

补充:decltype(expr)函数, 可以不执行expr(它可以是对另一个函数的调用)而推断返回类型

Function overloading

总结: 共用函数名, 具有不同参数类型, 调用时分别match

a simple example

1
2
3
4
void fun(int);
void fun(double);
fun(42); // fun(int)
fun(3.14); // fun(double)

nullptr

在C++中建议用nullptr代替NULL作为空指针

nullptr has a unique type std::nullptr_t (defined in <cstddef> ), which isneither void * nor an integer.

Lec14-16 Class Basics

成员变量与成员函数

this指针

member function作为object的方法, 隐式接受对应objectclassName *类型的指针this, 并将在函数体内对成员变量xxx的访问, 隐式转换为this->xxx //等价于(*this).xxx

access control

  • private成员,只能通过成员函数或friend函数访问
  • public成员, 在程序任意处可访问

const member functions

位置: 参数列表(T param)后 function body {前

e.g.bool graduated(int year) const {...}

用于只访问不修改 成员变量 的 成员函数

函数内的this指针也自动带上了const成为const X *

Constructors 构造函数

  • 名字同类名

  • 构造函数没有返回值 没有返回类型

初始化列表 initializer list

The initializer list starts with : , and contains initializers for each data member, separated by , . The initializers must be of the form(...)or{...}, not = ... .

概括: 接在参数列表后, 冒号开头, 以成员变量名(初始化值)或成员变量名{初始化值}格式

e.g.

1
2
Student(const std::string &name_, const std::string &id_)
  : name(name_), id(id_), entranceYear(std::stoi(id_.substr(0, 4))) {}
  • 成员按照声明的顺序初始化, 并非按照initializer list

顺序不一致会发生什么?

If the initializers appear in an order different from the declaration order, the compiler will generate a warning.

Typical mistake: entranceYear is initialized in terms of id , but id is not initialized yet!

1
2
3
4
5
6
7
8
class Student {
std::string name;
int entranceYear; // !!!
std::string id;
public:
	Student(const std::string &name_, const std::string &id_)
		: name(name_), id(id_), entranceYear(std::stoi(id.substr(0, 4))) {}
};

Q: **(重要)**为什么不在constructor函数体内部用赋值初始化? 就像这样:

1
2
3
4
5
6
7
8
class Student{
  //...
public:
  Student(const std::string &name_, const std::string &id_){
    name = name_;
    id = id_;
  }
}

A: 在进入函数体之前, 由于没有写initializer list, 编译器会先将成员变量都做默认初始化, 可万一某个类型不能默认初始化呢? 这不就出错了吗

不能默认初始化/被赋值的类型们:

  • T & 引用 不能初始化 不能被赋值
  • const 对象 不能被赋值
  • 被设计为拒绝默认初始化的class

默认构造函数 Default Constructors

格式: 没有输入参数的Constructor 如Point2d() : x(0), y(0) {}

作用: 规定对象的默认初始化行为

如果没有任何自定义constructor, 编译器才会synthesize a default constructor

如果有自定义constructor, 还需要synthesized default constructor,使用className() = default

Copy Constructor& Copy-assignment operator

动机: 避免shallow copy(指向同一块内存)

type syntax 适用 备注
Copy Constructor className(const className &other):xxx(yyy){....} 拷贝初始化(copy-initialization)T s2=s1(declaration statement), T s2(s1), T s2{s1} /
Copy-assignment operator className &operator=(const className &other) 赋值表达式s1 = s2(expression) 注意self-assignment safe
  • 用或删synthesized one: = default, =delete

The rule of three

要么自定义0个, 要么自定义3个

更完备的版本: 详见Lec17 The Rule of Five

  • copy constructor
  • copy-assignmnet constructor
  • destructor

Destructors 析构函数

动机: 当一个object生命周期结束时, 需要释放掉对应内存资源

格式: ~ClassName() {...}

What’s more: 在析构函数中, 成员变量在函数体执行后再摧毁, 摧毁顺序和declare相反

Type alias members 类型别名成员

动机: A better way of declaring type aliases

与传统C相比较

1
2
3
4
// C-style
typedef long long LL;
// C++-style
using LL = long long;

作为class member定义时, usage: className::TypeAliasName

All standard library containers (and std::string ) define the type alias member size_type as the return type of .size()

1
std::vector<int>::size_type j = v.size();

static members

static data members

  • 理解为一种”global variable”
  • 属于类本身, 不属于类的任何对象, 但可以通过对象用.来访问
  • 用className::来调用(回忆 type alias members)

static member functions

  • 同静态数据成员, 属于类本身, 不属于类的任何对象, 但可以通过对象用.来访问, 但不会绑定到this指针

friend functions

动机: 如何在一个类外定义的非成员函数中访问类内private members呢?

syntax: 随便定义在class的哪里(但通常在首尾), 照抄函数定义在{//function body...}前的内容, 前面加friend关键字, 删掉参数名

即在类内声明(declare)这个函数. 回忆: 类似function prototype (*this is not covered in CS100)

e.g.

1
2
3
4
5
6
7
void print(const Student &stu) {
//function body
}
class Student {
//something
	friend void print(const Student &);
}

What’s more:

  • 一个class也可以是friend
  • 用::可以在类外定义成员函数

Lec17 右值引用和移动

右值引用

动机：s=a+b时, 右值a+b会被拷贝给临时变量再赋值给s, 太慢了, 能否直接steal the contents

1
int &&rr = 42 //'rr' is an rvalue reference

class的移动函数

move assignment operator范例

1
2
3
4
5
6
7
8
9
10
11
class Dynarray{
public:
  Dynarray &operator=(Dynarray &&other) noexcept{ //勿忘noexcept move函数都需要 确保不抛出异常
    if (this != &other){ //self-assignment safe! 不然移动自己就删除掉了
      delete[] m_storage; // Avoid memory leaks! 先删掉this的m_storage以前指向的array 准备被新的资源move过来
      m_storage = other.m_storage; m_length = other.m_length; //Steal the resources from 'other'
      other.m_storage = nullptr; other.m_length = 0;//确保被转移的资源 现在只有this这唯一的owner
    }
    return *this;
  }
}

有了如上的move assignment operator后, 右值被移动,左值被拷贝

1
2
3
a = concat(b, c); // calls move assignment operator,
// because `concat(b, c)` generates an rvalue.
a = b; // copy assignment operator

The Rule of Five

The Rule of Five: Define zero or five of them.

  • copy constructor
  • copy assignment operator
  • move constructor
  • move assignment operator
  • destructor

std::move

动机: m_label = other.m_label;这会call copy assignment operator, 因为other.m_label是左值, 那如果我想要移动呢?

Defined in <utility>

std::move将左值转换为右值, 方便我们移动(call move assignment operator)

Copy Elision&NRVO

copy elision(拷贝省略)(since C++17): 以下代码不发生拷贝或移动, 直接将a+b的结果构造在s的内存上

1
2
3
4
std::string foo(const std::string &a, const std::string &b) {
return a + b; // a temporary
}
std::string s = foo(a, b);

NRVO=Named Return Value Optimization 理解为特殊的copy elision

例如

1
2
3
4
5
6
7
Named Return Value Optimization, NRVO
Dynarray concat(const Dynarray &a, const Dynarray &b) {
Dynarray result(a.size() + b.size());
// ...
return result;
}
Dynarray a = concat(b, c); // 事实上没有发生拷贝, 直接将result结果构造在了a的内存位置

Lec18 智能指针

std::unique_ptr

规范构造方法 使用std::make_unique<Type>(args)

1
auto p = std::make_unique<std::string>(5,'c'); // 管理字符串"ccccc"

unique所有权, 只能move不能copy

1
auto r = std::move(p) //正确, p变为null, 管理对象所有权转交给r

错误示范❌

1
auto q = p; //错误! 不允许copy 不要这样写!

std::shared_ptr

规范构造方法 使用std::make_shared<Type>(args);

1
auto p = std::make_shared<std::string>(10,'c');

拥有方法use_count()，返回reference counter计数，用途是通过追踪有多少个std::shared_pointer正共享资源，当计数归零时可释放资源

Lec19 Operator Overloading

运算符重载语法

举例如下

1
bool operator<(const Rational &lhs, const Rational &rhs) {...}

特殊例子1(重载标准输入输出)

1
2
3
4
5
6
class Rational {
	friend std::ostream &operator<<(std::ostream &, const Rational &);
};
std::ostream &operator<<(std::ostream &os, const Rational &r) {
	return os << r.m_num << '/' << r.m_denom;
}

注意要点

  • std::ostream类型匹配std::cout, std::istream类型匹配std::cin
  • 操作的应当是原来的输入输出流, 因此流对象std::cout, std::istream应该以引用&方式传入和返回

特殊例子2(++与–的prefix与postfix)

1
2
3
4
5
6
7
8
9
class Rational {
public:
  Rational &operator++() {++m_num; simplify(); return *this; } //prefix ++aaa 先加后返回
  Rational operator++(int){ //postfix aaa++ //先返回后加
    auto tmp=*this;
    ++*this;
    return tmp;
  }
}

类型转换

区分显式转换与隐式转换: 显式转换<–>目标类型U在转换表达式中显式写出

显式转换三种形式

表达式 解释 举例
✅ what_cast<U>(expr) C++ named casts static_cast<int>(3.14)将3.14转换为int
✅U(expr) 类比构造函数使用(constructor call) std::string("xx") 将const char[3]转换为std::strng
❗不推荐 (U)expr C-style 兼容但不推荐在C++中继续使用 (int)3.14

类型转换运算符

在自定义class中定义了转换到double的运算符operator double() const {...},

此时可以自动发生隐式转换,如double dval = r;

  • 记得加const
  • 若要禁止隐式转换调用, 在返回之前加explicit关键字,如explicit operator double() const {...}

Lec20&23 Iterators and Algorithms

迭代器基础

动机: Iterator是更generalized的”pointer”, 用来获取容器成员量

每个 container 都有对应的iterator，类型为 Container::iterator，实际使用时用 auto 让编译器自动推断即可。

1
for (auto it = str.begin(); it!= str.end(); it++){...}

普通指针也是iterator，例如数组Type a[N], 初始迭代器为a, 终止迭代器为a+N

在<iterator>中定义了std::begin和std::end函数, 统一了返回STL容器或数组begin/end iterator的接口

数组的delete[],std::vector的push_back(),pop_back()等方法会导致原先iterator的无效化(invalidation)

迭代器的分类

  1. Forward Iterators 只能向前移动

  2. Bidirection Iterator 可以双向移动

  3. Random Access Itertator 可以任意移动(it+n,it[n],…)

    std::vector, 指针是经典的随机访问迭代器

    std::sort必须接受Random Access Iterator

用迭代器范围初始化STL容器

1
2
3
std::vector<char> v = {'a','b','c','d','e','f','g','h','i'};
std::vector v2(v.begin() + 2, v.end() - 3); // {'c','d','e','f'}
std::string s(v.begin(), v.end()); // "abcdefghi"

STL algorithms 参数格式

接受pairs of iterators来表示范围

1
2
3
4
int a[N];
std::vector<int> v;
std::sort(a, a+N);
std::sort(v.begin(), v.end());

STL algorithms 返回值格式

返回值通常用迭代器表示位置, 若要取值需*解引用

“找不到”通常返回end迭代器

附: if语句也可以在condition内补scope内初始化值 方便在expression中复用

if (init_expr; condition)

STL algorithms 注意事项

STL algorithms NEVER insert or delete elements in the containers!

传入的是迭代器, 所以永远不会修改容器长度

常用STL algorithms

定义在<algorithm>的

  • std::replace：替换区间内所有等于指定值的元素

    1
    std::replace(vec.begin(), vec.end(), 0, 42);

  • std::sort：排序区间元素，可自定义比较

    1
    std::sort(vec.begin(), vec.end(), cmp); //若第三个可选参数传一个函数`cmp`, 会用`cmp(x,y)`代替`x<y`来比较(作为“x 是否应该排在 y 前面”的判断)

  • std::nth_element 将第n个元素放到假设该序列排序后的位置,但：

    • 左边元素都 ≤ 它
    • 右边元素都 ≥ 它
    • 左右两边不保证有序
1
std::nth_element(begin, nth, end, cmp);//若第四个可选参数传一个函数`cmp`, 会用`cmp(x,y)`代替`x<y`来比较(作为“x 是否应该排在 y 前面”的判断)
  • std::unique：把重复项扔到最后, 没有删除, 返回迭代器pos, 使得[begin, pos)部分无重复. 常配合 erase 删除多余元素
1
2
auto it = std::unique(vec.begin(), vec.end());
vec.erase(it, vec.end());

  • std::partition：按条件划分区间，满足的放前面, 不满足的放后面, 返回分界位置(第一个不满足的)迭代器

    1
    auto mid = std::partition(vec.begin(), vec.end(), [](int x){ return x <= 5; });

  • std::iota：按递增值填充区间

    1
    std::iota(vec.begin(), vec.end(), 1);

  • std::for_each：对区间每个元素执行操作

    1
    std::for_each(vec.begin(), vec.end(), [](int& x){ x *= 2; });

  • std::prev_permutation：生成上一个字典序排列

    1
    bool ok = std::prev_permutation(vec.begin(), vec.end());

  • std::lexicographical_compare：按字典序比较两个序列

    1
    bool less = std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());

  • std::equal：判断两个序列是否相等

    1
    2
    bool same = std::equal(a.begin(), a.end(), b.begin()); //
    bool same = std::equal(a.begin(), a.end(), b.begin(), b.end()); //检查长度相等

定义在<numeric>的

  • accumulate(begin, end, initValue) : 从 [begin, end) 求和, 再加到初始值 initValue 上.

accumulate(v.begin(), v.end(), 0) 返回v中的元素求和 .

  • inner_product(begin1, end1, begin2, initValue) 求向量内积, 再加到初始值 initValue 上.

Predicates

含义: 如find_if(begin, end, pred)找到[begin, end)范围中的第一个满足pred(element)为真的值, pred是callable object, 可以是function, function object, 也可以用lambda表达式代替

Function Objects

定义: 将operator()重载了的struct对象

fo(arg1, arg2, ...)is equivalent to fo.operator()(arg1, arg2, ...)

Lambda expressions

动机: 简化代码, 一次性使用的函数不用单独定义, 用表达式取代

1
[capture_list](params) -> return_type { function_body }
  • capture_list “捕获”列表, 从外部scope”捕获”并存到内部scope的量(对应: function object成员变量), 避免拷贝可以加&直接取引用
  • params: 参数, 对应一般函数接收参数 记得表明类型, 放在STL algorithms时会自动将[first, end)范围内每个迭代器传入
  • function_body: 对应一般函数体, 无特殊要点

Sequence containers

std::string不是container

containers 解释
std::vector<T> 动态连续数组 任意位置增减慢
std::deque<T> double-ended queue 双向 头尾快速增删
std::array<T,N> container版本的built-in arrayT[N] 支持STL container方法 不会转为pointer
std::list<T> 双向链表 数据不连续排放 任意位置快速增删 不可快速随机访问
std::forward_list<T> 单向链表 数据不连续排放

不同数据组织形式 Interfaces汇总

连续存储:std::string,std::vector,std::array

​ 不支持push_front,emplace_front,pop_fornt

链表结构:std::list<T>,std::forward_list<T>

​ 不支持:operator[],at

construct

  • Container c(b,e)
  • 标题: 26春CS100期中复习
  • 作者: AlexWei
  • 创建于 : 2026-05-23 19:40:00
  • 更新于 : 2026-05-23 20:01:57
  • 链接: https://www.alexwei.top/2026/05/23/CS100-Midterm-Review-26Spring/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
26春CS100期中复习
  1. C++ Part
    1. Lec11-13 C++ Basics
      1. Standard library
        1. <iostream>
        2. <string>
          1. 定义与初始化
          2. Member functions
        3. <vector>
          1. Create a std::vector
          2. Copy a std::vector
          3. 内置方法(类成员函数)
      2. References (左值)引用
        1. 补充: * and &各种用途大汇总
        2. reference-to-const
      3. Range-based for loops
      4. 类型转换
        1. 字符串 and 数字(arithmetic numbers)
        2. Explicit Casts
          1. const_cast
          2. reinterpret_cast
          3. static_cast
      5. auto
      6. Function overloading
      7. nullptr
    2. Lec14-16 Class Basics
      1. 成员变量与成员函数
        1. this指针
        2. access control
      2. const member functions
      3. Constructors 构造函数
        1. 初始化列表 initializer list
        2. 默认构造函数 Default Constructors
        3. Copy Constructor& Copy-assignment operator
        4. The rule of three
      4. Destructors 析构函数
      5. Type alias members 类型别名成员
      6. static members
        1. static data members
        2. static member functions
      7. friend functions
    3. Lec17 右值引用和移动
      1. 右值引用
      2. class的移动函数
      3. The Rule of Five
      4. std::move
      5. Copy Elision&NRVO
    4. Lec18 智能指针
      1. std::unique_ptr
      2. std::shared_ptr
    5. Lec19 Operator Overloading
      1. 运算符重载语法
      2. 类型转换
        1. 显式转换三种形式
        2. 类型转换运算符
    6. Lec20&23 Iterators and Algorithms
      1. 迭代器基础
      2. 迭代器的分类
      3. 用迭代器范围初始化STL容器
      4. STL algorithms 参数格式
      5. STL algorithms 返回值格式
      6. STL algorithms 注意事项
      7. 常用STL algorithms
        1. 定义在<algorithm>的
        2. 定义在<numeric>的
      8. Predicates
        1. Function Objects
        2. Lambda expressions
      9. Sequence containers
        1. 不同数据组织形式 Interfaces汇总
        2. construct