Theoyu

『 CS106L 』课程笔记

  • Theoyu
  • Jul 30, 2022

在这门课之前，我对 c++ 了解多少呢？

#include<iostream>
using namespace std;

应该只是开头上面两行，然后再加上几个cin、cout 罢了。

当然让我做几个算法题那也没什么问题，但 c++ 作为我学习的第一门语言，我很难去承认我学过它，大一无数个昏昏欲睡的早八已给我留下了不可磨灭的印象，老师如同复读机一般念叨 ppt 上的各种概念，我一度对自己是否适合计算机专业产生怀疑…

CS106L 是 Stanford 面向大一的 c++ 实验课，对应理论课为 CS106B。这两门课的上课方式并没有什么不同，只是 CS106B 对应的是 c++ 的基础语法还有数据结构知识，而 CS106L 将会涉及到更多的 Morden C++ 特性。

从课程安排上来看，CS106L 一共分为4个部分，分别是

  1. 视频：每门课都有对应录制的视频，这部分内容可以在 youtube 或者 bilibili 上观看。

  2. slides：在 CS106L 官网，可以直接下载每门课对应的幻灯片，制作的非常精美，如下：。

    image-20220713113730343

  3. code：每一门课都有对应的代码练习，并且给出了代码框架以及参考答案，只需要对着框架里面填写即可。

  4. project：课程一共设有两个的 project，非常有趣，这部分我在后面会单独介绍，并且这两个project 可以说把之前所学的知识点 全部贯通了起来。

因为我是在工作期间学习这门课，也是考虑时间因素所以我并没有选择观看视频（ slides + code 足够学习 ），前16个 cource 我大概每天晚上花 1个小时多就能完成一个课程，两个 project 大概是2+3 5个小时 ，总计时长20小时左右。

从课程内容上来看，CS106L 可以分为以下四个大部分，如下图：

image-20220706142947266

C++ Fundamentals

主要涉及了

  1. basic type 、Structures
  2. Streams
  3. Uniform Initialization、Reference

Standard Template Library

主要涉及了

  1. container 基础

    image-20220713235903618

  2. iterator and pointers
  3. class template、function template（还提了一下屠龙之术—模板元编程）
  4. predicate、function pointers 、functors、lambdas

OOP

主要涉及了

  1. Operator Overloading
  2. Special Member Functions

modern c++

主要涉及了：

  1. Move Semantics

    image-20220714224847990

    （关于移动语意，补充推荐阅读 这一篇文章 。）

  2. RAII (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

  3. Smart Pointers

课程还包含了的两个 PROJECT ，代码量不大，主要是对之前所学的 C++ 一些特性进行综合联系。

project 1 WikiRacer

project 1 用一个 冷知识 开启序幕：

Aside: did you know that if you click the first link on any Wikipedia page repeatedly, you’ll eventually always end up at Philosophy 97% of the time?

你知道吗？如果你随机点击任何一个维基百科的第一个链接，然后重复操作，你将最终有百分之 97 的概率到达 『 哲学 』的页面。

简而言之，这个游戏需要我们完成就是：给定一个维基百科的 start_page 和 end_page，找出一条从 start_page 到 end_page 的路线图。把一个大象放进冰箱需要三步，这个游戏同理：

  1. 首先我们需要有一个类似爬虫的功能，获取到一个页面的 html 信息，不过这一步项目的 skeleton 已经用 cpr 包帮我们准备好了。

  2. 我们需要提取 html 中所有链接信息，我可以用用一个 unordered_set<string> 把需要进一步搜索的 name 进行存储，我们注意维基百科的链接通常是这样的形式：

    es, and <a href="/wiki/Database" title="Database">database</a> theory concerns the m

    这里我们使用 std::search 正则提取出来。

    不过符合上述要求也有非预期的结果，比如：

    image-20220719001509091

    这不是我们希望看到的，所以我们还可以用到一个std::all_of 结合 predicate 去去除杂项。

  3. 最后一项也就是遍历搜索了。一般寻找最短路径我们会使用广度优先，一层一层遍历。但是注意每个页面之间不是毫无关系的，如果我们可以找到一个页面间的优先级，使用 priority_queue 效果应该会好一些。

    那么如何定义这个优先级呢？比如我们希望找到从学科到马克思的最短路径。在学科下有语文、英语、政治、计算机等链接，优先级就是页面与 end_page 的相关程度，我们把每个页面的链接和 end_page 中的链接进行比较，如果相同的链接数越多，则优先级越高，上述中毫无疑问政治和马克思应该会拥有最多的相同链接数目，所以在第二层中优先考虑政治。这在 priority_queue 可以用 lambda 表达式非常简洁的实现。

测试了两组数据：

input-big.txt:
2
Fruit Strawberry
Ultrasound Force

Available input files: input-big.txt, input-small.txt, sample-outputs.txt, random.txt.
Enter a file name: input-big.txt
Ladder found:
	{Fruit, Strawberry}
Ladder found:
	{Ultrasound, Fluid_mechanics, Force}

第一组大概是秒出，第二次组大概花了4分钟( 可能是代理的网速比较慢 )，主要时间开销还是在优先级队列的 compare 上。

总结：

​ 项目的skeleton足够强大，只需要填写几个简单函数的实现即可，主要是学习了 predicate 和 lambda 表达式在实际编程中的简便使用。

project 2 STL HashMap

刚开始我以为是自己实现一个 HashMap，没想到 skeleton 基本上已经给出了 90 %的代码，并且每个函数都有详细的注释，我们需要做的只有两点：

  1. Add Const-Correctness

    大部分实现都没有考虑 Const-Correctness ，只需要在其基础上重栽即可。

  2. Add Special Member Functions and Move Semantics

    • Default constructor (implemented for you)
    • Destructor (implemented for you)
    • Copy constructor
    • Copy assignment operator
    • Move constructor
    • Move assignment operator

    前两个已经给出，只需完成后面四组。

同时项目给的测试用例 tests.cpp 十分强劲，足足有 2k 的代码。

通过这个项目，我算是深刻理解了常量和多种构造函数的具体运用，总的来说收获繁多。

还有关于这个 project 还有几个纸面问题，我的也不一定是正确，就不贴了：

Assignment 3: STL HashMap (short answer questions)
Names: 

1. at() vs []
Q: Explain the difference between at() and the implementation of the operator []. Wy did you have to overload one and not the other?

2. HashMap::find vs std::find
Q: In addition to the HashMap::find member function, there is also a std::find function in the STL algorithms library. If you were searching for key k in HashMap m, is it preferable to call m.find(k) or std::find(m.begin(), m.end(), k)?

3. RAII
Q: This HashMap class is RAII-compliant. Explain why.

4. Increments
Q: Briefly explain the implementation of HashMapIterator's operator++, which we provide for you. How does it work and what checks does it have?

5. Attachment Issues
Q: Why is it that we need to implement the special member functions in the HashMap class, but we can default all the special member functions in the HashMapIterator class?

6. Move Semantics
Q: In your move constructor or move assignment operator, why did you have to std::move each member, even though the parameter (named rhs) is already an r-value reference?

最后

通过这门课，也是一定意义上弥补了本科生涯中的一些遗憾。生活还得继续，But

This is just the beginning.

Search