CStudy

CS106L 学习笔记

This part is still under construction.

§1 类型与结构体 Types & Structs

1.1 结构体 Structs

结构体将命名变量捆绑到一个新类型中。

1
2
3
4
5
struct Order {
    string item;
    int quantity;
};
Order dozen = {"Eggs", 12};

上述例子可以使用 std::pair 代替：

1
2
3
std::pair<std::string, int> dozen {"Eggs", 12};
std::string item = dozen.first;
int quantity = dozen.second;

1.2 std标准库

std是C++的标准库。C++ 标准库提供了大量预定义的类型、函数及相关组件。在使用标准库中的特定组件之前，需要通过 #include 预处理指令引入相应的头文件。

  • #include <utility> 提供 std::pair

我们需要在标准库中的语言名称前加上 std:: 前缀。如果我们使用 using namespace std; ，我们就不必这么做，但这被认为是不良的习惯，因为这会污染命名空间。比如，如果我们自定义了一个sort函数，编译器就难以区分标准库里的sort函数和我们自己的sort函数。

1.3 using 和 auto 用于简化代码

当类型名较长时，反复完整书写会降低代码的可读性与编写效率。可以使用 using 关键字为已有类型定义别名，从而简化复杂类型的表达。

1
2
3
4
5
6
//不使用using关键字
std::pair<bool, std::pair<double, double>> solveQuadratic(double a, double b, double c);
//使用using关键字
using Zeros = std::pair<double, double>;
using Solutions = std::pair<bool, Zeros>;
Solutions solveQuadratic(double a, double b, double c);

同时，auto 关键字让编译器根据数据自己选择合适的数据类型。需要注意，auto只在定义初始决定好数据类型，后续无法更改。

1
2
//延续上述例子
auto result = solveQuadratic(double a, double b, double c);

§2 初始化与引用 Initialization & References

2.1 初始化 Initialization

直接初始化（direct initialization）：初始化的值如果不符合定义的类型，则强制转换。

1
2
int numOne = 12.0;
int numTwo(12.0);   //12.0不符合int数据类型，编译器转化为12

统一初始化（uniform initialization）：初始化的值必须符合定义的类型。

1
2
int numOne = {12};
int numTwo{12.0};   //12.0不符合int数据类型，编译器报错

结构化绑定（Structured Binding）：从固定大小的数据结构中初始化多个变量。常用于访问函数返回的多个值。该数据结构的大小必须在编译时已知。

1
2
3
4
5
6
7
std::tuple<std::string, std::string, std::string> getClassInfo() {
    std::string className = "CS106L";
    std::string buildingName = "Thornron 101";
    std::string language = "C++";
    return {className, buildingName, language}; //统一初始化
}
auto [className, buildingName, language] = getClassInfo(); //结构化绑定

2.2 引用 References

引用就是给已经存在的对象或函数起一个别名，内存地址和引用对象完全相同，通过引用可以原地改变实参的值。引用可用于函数传参等。

1
2
3
4
5
6
7
void shift(std::vector<std::pair<int, int>> &nums) {
    for (auto& [nums1, nums2] : nums) {  //运用了引用和结构化绑定
        nums1++;
        nums2++;
    }
    return;
}

2.3 使用命令行进行.cpp文件的编译（compile)

使用g++编译器按照C++23的标准将main.cpp编译成程序：

1
g++ -std=c++23 main.cpp -o main

如果是多文件程序，要把所有.cpp文件写在main.cpp的位置。

在Linux或macOS中，运行编译好的文件指令为：

1
./main

在Windows上运行，则指令为：

1
.\main.exe

§3 流 Stream

3.1 流的定义

流（stream）是C++的一种通用的输入输出抽象模式，提供了一种统一的处理外部数据的方式。

cout & cin输出：（略）

fout & fin输出：

1
2
3
4
5
6
7
8
//create a file called "data.txt"
std::ofstream fout("data.txt");
fout << "I'm writing to this file";

std::ifstream fin("data.txt");
std::string first_word;
//store the first word from the file into fin
fin >> student_input;

ios_base是所有流的基础，用于维护状态信息、控制信息，确保信息流正常。状态信息告诉人们流是否正常，比如failbit提示存在逻辑错误，eofbit提示已到文件末尾；控制信息表示应该如何输出数据，比如dec、hex、oct等。

ios_base的组成如下：

ios_base 结构图

iostream 继承关系

输入流（input streams）是一种从源读取数据的方式，继承自 std::istream ，基本运算符是 >> ；输出流（output streams）是一种向目标输出数据的方式，继承自 std::ostream ，基本运算符是 << 。istream 和 ostream 的交叉部分称为 iostream ，这部分流同时具有输入流和输出流的特征。

3.2 stringstreams 字符串流

stringstreams是把string字符串当作流处理的一种方式，适合处理混合数据类型的用例。字符串输出流为 std::ostringstream ，字符串输入流为 std::istringstream 。

1
2
3
4
5
6
7
8
9
10
11
12
void foo() {
    std::string initial_quote = "Hi I'm Addison Rae Updates";
    // create a stringstream
    std::stringstream ss(initial_quote); //用initial_quote初始化字符串流
    // data destinations
    std::string first;
    std::string last;
    std::string language, extracted_quote;
    ss >> first >> last >> language; //从字符串流中读入
    std::getline(ss, extracted_quote);
    std::cout << first << " " << last << language << " " << extracted_quote << std::endl;
}

<< 和 >> 读取字符直到任何空格为止，这些空格包括 / \n / \t / \r / \f / \v 等。

std::getline 从输入流is中读取字符到str中直到读取到delim字符。默认情况下，delim字符设置为 \n （即换行符）。特别注意：getline 函数会读取delim字符。

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

3.3 输出流 Output Stream

缓冲区：输出流中的字符会先存储在缓冲区，然后再刷新在目标位置。

刷新的时机：

  • std::cout << std::flush
  • std::cout << std::endl
  • 当程序到达末尾时
  • 当缓冲区满了时
  • 当相连的流互相作用时（例：在使用cin输入前，输出流必须刷新）

cerr 被用于立即输出程序的错误信息，该信息不会存在缓冲区里；而 clog 被用于输出程序的错误信息，该信息会存在缓冲区里。后者常用于非必要错误信息的排查。

REMINDER: 由于 endl 会给输出流缓冲区带来不必要的刷新，因此若只是换行建议使用 \n 。

文件输出流：把数据写入文件的方式。输出流为 std::ofstream

创建文件输出流的方式：std::ofstream out("file.txt", file_flag)

其中，file_flag 表示创建输出流的模式，主要有三种：

  • std::ios::trunc 清空文件，从头写，是默认设置
  • std::ios::app 不清空，追加至末尾
  • std::ios::ate 打开后光标直接追加至末尾

文件输出流使用举例：

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    std::ofstream ofs("hello.txt");               //创建输出流
    if (ofs.is_open()) {                          //判断文件是否打开
        ofs << "Hello CS106L!" << '\n';           //在文件中输出文字
    }                                             //ofs是自己设置的输出流名称
    ofs.close();                                  //关闭文件
    ofs << "This won't get written.";
    ofs.open("hello.txt", std::ios::app);         //重新打开，模式设为追加
    ofs << "This will though! It's open again.";
    return 0;
}

文件输入流的用法和文件输出流完全对称。

3.4 输入流 Input Stream

混合型数据类型输入时，尽量不要混用cin和getline。

1
2
3
4
5
6
7
8
9
10
void cinGetline() {
    double pi;
    double tao;
    std::string name;
    std::cin >> pi;
    std::getline(std::cin, name);
    std::getline(std::cin, name);  //留意多出来的这行
    std::cin >> tao;
    std::cout << name << " " << pi << " " << tao << "\n";
}

当 getline 函数进行输入时，由于会读入 \n ，因此第一行 getline 读入的是上个输入在缓冲区遗留的换行符，第二个 getline 才会读入字符串。

§4 容器 Containers

4.1 STL (Standard Template Library)

STL是C++中非常实用的一个标准库，隶属于std标准库。STL包括四个部分：容器（containers）、迭代器（iterators）、函子（functors）和算法（algorithm）。

4.2 顺序容器 Sequence Container

顺序容器实现了可以按顺序访问的数据结构，如 vector / deque / array / list 。

vector容器：可调整大小的连续数组（动态数组）。

访问vector元素：

1
2
3
4
5
vector<int> vec(13);
for (size_t i = 0; i < 13; i++) {
    vec[i]++;    //不会检查i是否越界
    vec.at(i)++; //会检查i是否越界
}

vector 是如何调整大小的？

当 push_back 时发现 size == capacity，vector 会申请一块更大的连续内存，把旧元素搬过去，再插入新元素，然后释放旧内存。时空复杂度是O(1)。

一般而言，vector申请的连续内存是翻倍的。但这不是C++的强制规定。

另：vector::insert 插入中间元素时，为了保持连续存储和元素顺序，必须移动插入点之后的元素，所以它通常是O(n)，不像数组下标访问那样是O(1)。

deque容器：有两端的队列。同时存在 push_back 和 push_front 。

deque容器是如何演化的？

  1. Map（控制块）

    deque 的核心可以理解为一个“指针的动态数组”。这些指针，也就是图中紫色的小格子，并不直接存放你的数据，而是存放 数据块（Data Blocks） 的内存地址。正因为如此，deque 的数据在内存中不需要像 vector 那样完全连续存放。

  2. 头尾 O(1) 增长

    当你执行 push_front 或 push_back 时，deque 会先检查当前边缘的数据块是否还有空位。如果没有空位，它就会分配一个新的固定大小的数据块，并把这个新数据块的地址放入 Map 中下一个可用的位置。

    因为这个过程中只需要新增一个指针，已有元素本身并不会在内存中移动。所以 deque 在增长时，指向已有元素的指针和引用通常仍然有效。

  3. 重新居中的增长方式

    如果你一直向同一侧插入元素，最终会到达控制块 Map 的边界。这时 deque 不会把所有实际数据整体移动，而是会分配一个更大的指针数组，并把原来的指针复制到新数组的中间位置。

    这种“双重间接寻址”机制保证了 deque 可以继续向两端增长，同时又避免了对实际数据进行大规模搬移。

  4. 随机访问的计算方式

    当访问 deque[i] 时，CPU 并不会从头开始一个一个遍历。它会通过计算确定元素所在的数据块和块内位置：

    1
    2
    block = (i + offset) / block_size;
    cell  = (i + offset) % block_size;

    其中 block 用来找到 Map 中对应的数据块指针，cell 用来找到该数据块内部的具体元素。

    和 vector 的一次寻址相比，deque 通常需要两次跳转；但它同时保留了类似链表的两端灵活增长能力，以及接近数组的随机访问速度。

4.3 关联容器 Associative Container

关联容器实现了可以快速排序的有序数据结构。如：map / set

map容器：储存键值对，并按键排序。

即使没有定义键值对，编译器也会把未定义的键赋予一个默认值（通常为0）。

std::map 底层通常是一棵红黑树。插入 key-value 对时，map 会按照 key 的大小把节点放进树里，并通过旋转和变色保持平衡，所以它能自动有序，并且查找、插入、删除通常都是 O(log n)。

set容器：没有值的map，储存不重复的元素并排序。

4.4 无序关联容器 Unordered Associative Container

就是关联容器的无序版本，通常来说性能更快。如 unordered_set / unordered_map 。

底层实现是哈希表，因此时间复杂度更快。

总结：STL各容器的算法速度比较

STL各容器的算法速度比较

§5 迭代器 Iterators

5.1 迭代器基础知识

迭代器是STL中用于遍历容器的通用位置对象。

1
2
3
4
5
6
container.begin()  //指向容器第一个元素的迭代器
container.end()    //指向容器最后一个元素后面的一个位置的迭代器
auto it = c.begin();   //直接初始化迭代器
++it;                  //迭代器向前进一个位置（使用it++会增加一个复制步骤，因此推荐++it）
auto& elem = *it;      //迭代器解引用
if (it == c.end())...  //判断迭代器是否到达结尾

迭代器的数据类型由所属的容器决定：

1
2
std::map<int, int> m{{1, 2}, {3, 4}};
std::map<int, int>::iterator it = m.begin();

5.2 迭代器的种类

输入迭代器（input iterators）：最基础的迭代器，允许读取元素。

特点：只能单次读取，只读，不可回退。

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    std::cout << "Enter numbers (Ctrl+D to stop)\n";
    std::istream_iterator<int> start(std::cin);      //设置迭代器从输入开始阅读
    std::istream_iterator<int> end;                  //设置终止迭代器
    std::vector<int> numbers(start, end);            //把读取的数全部读入vector
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

如果指向的元素是结构体，可以使用operator -> 来访问元素。

输出迭代器（output iterators）：允许写入元素的迭代器。

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    std::ostream_iterator<int> it(std::cout, ", ");
    //上面代码的意思是：创建输出迭代器，每输入一个数，迭代器输入到cout输出流里并在后面加“， ”
    *it = 10;
    ++it;      //实际上这个自增没有实际意义，因为没有所谓的下一个元素
    *it = 20;
    ++it;
    *it = 30;  //output: 10, 20, 30,
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    std::vector<int> v;
    std::back_insert_iterator<std::vector<int>> it(v);
    //上面代码的意思是：定义一个动态数组，并定义指向动态数组的迭代器
    *it = 10;  //相当于v.push_back(10)
    ++it;      
    *it = 20;
    ++it;
    *it = 30;  //v现在的值为{10, 20, 30}
    return 0;
}

前向迭代器（forward iterator）：可以从前往后一个一个遍历元素，并且可以重复遍历同一段数据的迭代器。

特点：可以多次读取，只读，不可回退。

注意：对于流来说，前向迭代器容易导致错误，所以不要在流中使用前向迭代器。

1
2
3
//支持的语法
it1 == it2 //判断两迭代器是否相等
++it1 == ++it2

双向迭代器（bidirectional iterator）：可以从前往后遍历，也可以从后往前退回去的迭代器。

典例：std::map / std::set 的迭代器。

1
2
//支持的语法
--it;      //可以往回退，但不能随机游走

随机访问迭代器（random access iterator）：可以像数组下标一样直接跳到任意相对位置的迭代器。

典例：std::vector / std::deque 

1
2
3
4
5
6
7
8
//支持的语法
++it;      // 向后走一步
--it;      // 向前退一步
it + n;    // 向后跳 n 个位置
it - n;    // 向前跳 n 个位置
it2 - it1; // 计算两个迭代器之间的距离
it[n];     // 访问 it 后面第 n 个元素
it1 < it2  // 比较位置先后

为什么迭代器的类型很重要？

  • 一些内部储存的算法需要特定的迭代器类型才能实现；
  • 容器的底层实现方式决定了迭代器的种类。随机访问迭代器适用于顺序容器，因为访问很快；相比之下，关联容器的随机访问就慢很多，所以关联容器一般采用双向迭代器。

§6 类 Classes

6.1 类的定义

面向对象编程（OOP, Object-oriented Programming）：以对象为中心的编程方式，专注于类的设计和实现。

类就是用户自定义的可以被声明为对象的类型。类包含一系列不同类型的对象、一组用于操作这些对象的函数，以及一组对这些对象和函数的访问限制。

容器就是在STL中被定义的类。

类包含 public 和 private 两个区域，public 是可以被外界访问的，private 只能被类里的元素访问。

构造函数（constructor）：初始化新产生的类的函数。

自定义构造函数：如果类定义在头文件，则 .h 文件写：

1
2
3
4
5
6
7
8
9
10
11
12
class MyID {
private:
    std::string name;
    std::string sunet;
    int idNumber;
public:
    MyID(std::string name, std::string sunet, int idNumber);
    //头文件可以写明构造函数的具体内容，也可以只是声明。构造函数需要与类同名，不需要写类型。
    std::string getName();
    std::string getSunet();
    int getID();
};

在 .cpp 文件写声明：

1
2
3
4
5
6
7
MyID::MyID(std::string name, std::string sunet, int idNumber) {  //注意声明域
    this->name = name;              //直接赋值时，表示类里定义的变量需要加this指针以示区分
    this->sunet = sunet;
    if (idNumber > 0) {
        this->idNumber = idNumber;  //如果不满足条件而没有自定义默认的构造函数，则默认初始化为0
    }
}

也可以（更推荐）使用成员初始化列表：

1
2
3
4
5
6
7
MyID::MyID(std::string name, std::string sunet, int idNumber) {
    name{name}, sunet{sunet} {};      //此处不能写this指针，留意末尾的{}
    if(idNumber > 0) idNumber{idNumber} {};
}
MyID::MyID() {
    name{EzraYang}, sunet{EzraY}, idNumber{2552778} {};
} //构造函数允许重载，没有参数意味着是默认构造函数，注意需要在头文件声明

析构函数（destructor）：在类执行完周期后，销毁类内变量的函数。

一般析构函数不会被显式调用，而是自动调用，当对象超出作用域的时候就会被调用。

1
2
3
MyAnotherID::~MyAnotherID() {
    delete[] my_array;
} //如果类内有动态申请过空间的变量要在此处释放

6.2 类的继承 Inheritance

类的继承指让一个子类基于父类已有的成员和接口继续扩展或改写功能，从而表达“子类是一种父类”的关系。

类的继承的两个作用：

1.动态多态：不同类型的对象可能需要同样的接口。

2.可扩展性：可以先写一个比较抽象的父类，然后再写更具体的子类。

类的继承举例：（一般写在头文件里方便使用，不过也能写在.cpp文件里）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Shape {
public:
    virtual double area() const = 0;
    //这行代码称为纯虚函数，在父类定义，在子类中重写，表示允许被继承
    //它的意思是：定义一个纯虚函数area，返回double，并且该函数不会修改对象本身
    //“= 0”的意思是：该函数在父类只提供接口，不修改对象本身
};
class Circle : public Shape {  //定义Circle子类，以public的方式继承Shape父类
public:
    Circle(double radius): _radius{radius} {};  //子类的构造函数，用初始化列表绑定
    double area() const {
        return 3.14 * _radius * _radius;
    }  //重写area函数
private:
    double _radius;  //继承的另一个优点：能够封装类内变量
};

上文中的 class Circle : public Shape 里的 public 指的是类的继承类别。类别主要有 public / private / protected 三类，它们的区别是：

继承方式 父类 public 成员到子类里 父类 protected 成员到子类里 父类 private 成员
public 继承 还是 public 还是 protected 子类不能直接访问
protected 继承 变成 protected 还是 protected 子类不能直接访问
private 继承 变成 private 变成 private 子类不能直接访问

6.3 虚继承 Virtual Inheritance

菱形继承问题：假设子类B和C都继承自父类A，一个类D又同时继承B和C，A、B、C都定义了一个 func() 函数，那么在D中，如何定义 func() 函数不会导致混淆？

答：引入虚继承。虚继承的意思是：最终派生类，也就是这里的 D，对于共同的基类 A，应该只保留一份实例，而不是通过 B 和 C 各继承一份。此处，应该让B和C变为虚继承：

1
2
3
4
5
6
7
8
9
class A {
public:
    int x;
};

class B : virtual public A {}; //虚继承
class C : virtual public A {};

class D : public B, public C {};

结合虚拟性的多态性意味着我们可以获得动态类型。当父类指针/引用指向子类对象，并且调用的是 virtual 函数时，程序不会只看“变量声明成什么类型”，而会在运行时看“它实际指向的对象是什么类型”，然后调用对应子类的函数。

§7 类模板 Template Classes

7.1 类模板

类模板（class template）是用于生成类的模板。通过类模板，我们可以用不同的数据类型实例化出结构相似、功能相近的不同类。STL 中的 std::vector 就是一个经典例子：std::vector 本身是一个类模板，通过 vector<int>、vector<string> 等形式，可以生成用于存储不同数据类型的动态数组类。

1
2
3
4
5
6
7
8
template <typename T>
class Vector {
public:
    T& at(size_t index);
    void push_back(const T& elem);
private:
    T* elems;
}

同时，非类型模板参数（non-typename template parameters）是被允许存在的。比如，有时我们会选择使用 std::array 而不是 std::vector ，为了避免堆内存分配。

1
2
3
template<typename T, std::size_t N>
struct std::array { /*...*/ };
std::array<std::string> arr;

类模板的几个注意事项：

  1. 在头文件定义的类模板，在 .cpp 文件里需要再次声明 template 语句。如：

    若在头文件写

    1
    2
    3
    4
    5
    template <typename T>
    class Vector {
    public:
        T& at(size_t i);
    }

    那么在 .cpp 文件中就要写

    1
    2
    3
    4
    template <typename T>
    T& Vector<T>::at(size_t i) {  //留意这一行的Vector<T>
        // Implementation...
    }

  2. 对于非类型模板参数而言，cpp文件需要引用头文件；对于类型模板参数而言，头文件需要在结尾引用cpp文件。如，上例中头文件需要在末尾写上：

    1
    #include "Vector.cpp"

  3. 在模板参数列表中，typename 和 class 是等价的。（但更建议写前者，易于区分）

7.2 常量正确性 Const correctness

const 关键字让被修饰对象无法被修改。

从设计上讲，设计类的时候，给不会改变对象的函数或方法最好加上 const 。如：若cpp文件定义函数：

1
2
3
4
5
6
void printVec(const Vector<int>& v) {       //注意此处也有const
    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v.at(i) << " ";
    }
    std::cout << std::endl;
}

则头文件要声明：

1
2
3
4
5
6
7
8
9
template<class T>
class Vector {
public:
    size_t size() const;
    bool empty() const;
    T& operator[](size_t index);   //会改变对象的函数不能加const
    T& at(size_t index) const;  
    void push_back(const T& elem);
}

加上 const 关键字，是在告诉编译器，该函数或方法不会改变类内的对象。未加常量修饰的函数不能作用于加了常量修饰的对象。

此处会自然地产生一个问题：那么，加了 const 关键字的函数如果要对对象作出修改，怎么办呢？

以下有三种方法：

  1. 使用 const 重载（overloading）

    定义两个该函数，一个修饰，一个不修饰，这样编译器会自己选择使用哪种。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    template <class T>
    class Vector {
    public:
        const T& at(size_t index) const;
        //上面这行代码的两个const的意义是：
        //第一个const修饰返回值，表示：返回的元素不能被改。
        //第二个const修饰成员函数，表示：这个函数不能修改当前对象，并且可以被const对象调用。
        T& at(size_t index);
    }

  2. 使用 const_cast

    该函数可以临时强制将某个值转换成常量，可以绕过编译器。不过一般来说非常少使用这种方法，如果这种函数需要改变对象，那就一开始别加常量修饰。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    template <typename T>
    T& Vector<T>::findElement(const T& value) {
        for (size_t i = 0; i < logical_size; i++) {
            if (elems[i] == elem) return elems[i];
        }
        throw std::out_of_range("Element not found");
    }
    template <typename T>
    const T& Vector<T>::findElement(const T& value) const {
        return const_cast<Vector<T>&>(*this).findElement(value);
    }

  3. 使用 mutable 关键字

    mutable 可以绕过 const 关键字。这种方法一般用于debug。

    1
    2
    3
    4
    5
    6
    struct MutableStruct {
        int dontTouchThis;
        mutable double iCanChange;
    }
    const MutableStruct cm;
    cm.iCanChange = 3.14;

About this Post

This post is written by Ezra Yang, licensed under CC BY-NC 4.0.

#notes #C++

Comments