ReadMe

看这学期能不能挤时间学一门新的课程，把我的C++的coding水平提一提，为以后上数据结构做准备。

我从大一开始一直都是写的 C++ 代码，直到学完这门课我才意识到，我写的 C++ 代码大概只是 C 语言 + cin/cout 而已。

这门课会深入到很多标准 C++ 的特性和语法，让你编写出高质量的 C++ 代码。例如 auto binding, uniform initialization, lambda function, move semantics，RAII 等技巧都在我此后的代码生涯中被反复用到，非常实用。

值得一提的是，这门课的作业里你会实现一个 HashMap（类似于 STL 中的 unordered_map), 这个作业几乎把整个课程串联了起来，非常考验代码能力。特别是 iterator 的实现，做完这个作业我开始理解为什么 Linus 对 C/C++ 嗤之以鼻了，因为真的很难写对。

总的来讲这门课并不难，但是信息量很大，需要你在之后的开发实践中反复巩固。Stanford 之所以单开一门 C++ 的编程课，是因为它后续的很多 CS 课程 Project 都是基于 C++的。例如 CS144 计算机网络和 CS143 编译器。这两门课在本书中均有收录。

就选这门cs106l了。如果这学期鸽掉，那就寒假再学吧。

课程网址：CS 106L: Standard C++ Programming (stanford.edu)

版本：2022spring

Exercises and assignments：

Types and Structs

We won’t use “using namespace std” most of the time. It’s not good style!

Types

即int, char, float, double等

C++是一种静态语言（statically typed language）

statically typed：everything with a name is given a type before runtime.

type1 function_name(type 2 variable);

​ type2—>type1

If we want two versions of a function for two different types, we can use polymorphism（多态）.

For example:

1
2
3
4
5
6
int half(int x){
    return x/2
}
double half(double x){
    return x/2
}

Struct

struct: a group of names variables each with their own type. A way to bundle different types together.

For example:

1
2
3
4
5
struct Student{
	string name; //these are called firlds
    string state;
    int age;
}

To initial a struct:

1
2
3
4
5
6
Student s;
s.name="Frankie";
s.state="MN";
s.age=21;
//is the same as...
Student s={"Frankie",'MN',21};

Pair

std::pair An STL built-in struct with two fields of any type.

A template: You specify the types of the fields inside <> for each pair object you make.

The fields in std::pairs are named first and second.

For example:

1
2
3
4
5
6
7
8
std::pair<int,string> numSuffix={1,"st"};
//or you can write the code like in another way:
//struct Pair{
//	fill_in_type first;
//	fill_in_type second;
//};
cout<<numSuffix.first<<numSuffix.second;
//prints 1st

You can also use std::pair to write a function. For example:

1
2
3
4
5
6
7
8
9
std::pair<bool, Student>lookupStudent(string name){
Student blank;
if (found(name))
    return std::make_pair(false,blank);
Student result =getStudentWithName(name);
return std::make_pair(true,result);
}
//to use the function
std::pair<bool,Student>output=lookupStudent("Keith");

Type Deduction（类型推断） with auto

auto：Keyword used in lieu of type when declaring a variable（当申明一个变量时用来代替类型的关键词）, tells the compiler to deducethe type.

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

For example:

1
2
3
auto a=3;
auto b=4.3;
auto e=std::make_pair(3,'Hello');

Streams

Pay attention! Here thinks out the streams, so the single cin or cout is out of our discussion.

stream：an abstraction for input/output. Streams convert between data and the string representation of data.

std::cout is an output stream. It has type std::ostream

  • output streams：

    • have type std::ostream
    • can only send data using the << operator.（converts any type into string and sends it to the stream.）

  • output file streams：

    • have type std::ofstream

  • can only send data using the << operator.（converts data of any type into string and sends it to the file stream.）

    • must initialize your own ofstream object linked to your file.

  • std::ofstream out(“out.txt”);
    out<<5<<std::endl;

Input streams

Input Streams:

  • have type std::istream
  • can only reveive strings using the >> operator
  • receives a string from the stream and converts it to data

each >> ONLY reads util the next whitespace

-whitespace=tab, space, newline

whilespace is eaten: it won’t show up in output.

Reading using >> extracts a single “word” or type including for strings.

To read a whole line, use std::getline(istream&stream, string&line);

For example:

1
2
std::string line;
std::getline(cin,line);

Don’t mix >> with getline!

  • >> reads up to the next whitespace character and does not go past that whitespace character
  • getline reads up to the next delimiter (by default, ‘\n’), and does go past that delimiter.

Input File Streams

  • have type std::ifstream
  • only receives strings using the >> operator
  • receives strings from a file and converts it to data of any type

Stringstreams

  • Input stream: std::istringstream
    • Give any data type to the istringstream, it’ll store it as a string!
  • Output stream: std::ostringstream
    • Make an ostringstream out of a string, read from it word/type by word/type!

The same as the other i/ostreams you’ve seen!

Initialization and References

InitializationHow we provide initial values to variables.

two ways to intial a struct：

1
2
3
4
5
6
 Student s;
 s.name = "Frankie"; 
 s.state = "MN";
 s.age = 21; 
 //is the same as ...
Student s = {"Frankie", "MN", 21};

multiple ways to initial a pair：

1
2
3
4
5
std::pair<int, string> numSuffix1 = {1,"st"};
std::pair<int, string> numSuffix2;
numSuffix2.first = 2;
numSuffix2.second = "nd";
std::pair<int, string> numSuffix2 = std::make_pair(3, "rd");

initialization of vectors：

1
2
3
4
5
std::vector<int> vec1(3,5); 
// makes {5, 5, 5}, not {3, 5}!
std::vector<int> vec2;
vec2 = {3,5};
// initialize vec2 to {3, 5} after its declared

Uniform initialization：curly bracket initialization（花括号）.Available for all types, immediate initialization on declaration.

$$less common/nice for primitive types, but possible.

P.S. about vector initialization

1
2
3
4
std::vector<int> vec1(3,5);
//makes {5,5,5}
std::vector<int> vec2{3,5};
//makes {3,5}

using auto to reduce long type names

For example:

1
std::pair<bool, std::pair<double,double>>result=quadratic(a,b,c);
1
auto quadratic(a,b,c);

Reference

Reference：An alias (another name) for a names variable.

reference vs copy：

1
2
3
4
5
6
7
8
9
10
11
12
void changeX(int& x){ //changes to x will persist
x = 0;
}
void keepX(int x){
x = 0;
}
int a = 100;
int b = 100;
changeX(a); //a becomes a reference to x
keepX(b); //b becomes a copy of x
cout << a << endl; //0
cout << b << endl; //100
1
2
3
vector<int> original{1, 2};
vector<int> copy = original;
vector<int>& ref = original;

“=” automatically makes a copy! Must use & to avoid this.

const and const references

const indicates a variable can’t be modified!

can’t declare non-const reference to const variable! For example:

1
2
3
std::vector<int>& bad_ref=c_rec;
//fixed
const std::vector<int>& bad_ref=c_vec;

use references to have multiple aliases to the same thing

use const references to avoid making copies whenever possible

Containers

Standard Template Library（STL） contains：

containers，iterators，functions，algorithms.

How to use STL?

two steps:

  1. Import the relevant STL feature
  2. Use it with “std::“”

For example:

1
2
3
4
5
#import <vector>
int main(){
    std::vector<int> vec;
    ...
}

Sequence Containers

Simple

  • <>vector (adding + removing elements at end)

  • ⇅ deque (adding + removing elements anywhere but end)：

    • 先把现有的填满，超出的可以向前向后延申。

  • ↓ list (adding + removing elements anywhere, but no random access)

  • () tuple (different data types, but immutable)

  • size：number of elements in a vector
  • capacity：amount of space saved for a vector（开的空间大小）

summary：

  • std::vector: use for almost everything
  • std::deque: use if you are frequently inserting/removing at front
  • std::list: use very rarely, and only if you need to split/join multiple lists

container adaptors

  • stack（栈）：adding/removing elements from the front
    • LIFO(last-in, first-out)
  • queue：adding elements from the front, removing from the back
    • FIFO(first-in, first-out)
  • priority_queue：adding elements with a priority, always removing the highest priority-element

Container adaptors are wrappers in C++.

It provides a different interface（接口） for sequence containers. We can choose what the underlying container is. For instance, let’s choose a deque as our underlying container, and let’s implement a queue.

Concrete examples with std::queue

1
2
std::queue<int>stack_deque;            //Container=std::deque
std::queue<int,std::list<int>>stack_list;  //Container=std::list

Associative Containers

Ordered

  • {} set (unique elements)
  • {:} map (key value pairs)

Every std::map<K,V> is actually backed by: std::pair<const K, V>

hint: std::pair’s are just two-element tuples!

Unordered

  • {} unordered_set
  • {:} unordered_map

if using simple data types/you’re familiar with hash functions, use unordered associative containers.

the difference from the unordered and the ordered：

Each STL set/map comes with an unordered sibling. They’re almost the same, except：

  • Instead of a comparison operator, the set/map type must have a hash function defined for it.
  • unordered_map/unordered_set are generally faster than map/set.

Iterators and Pointers

Iterators

Iterations allow iterating over any container** whether ordered, unordered, sequence, or associative!

An iterator is like a “claw”, it has an “ordering” over elements.

1
2
3
4
5
6
std::set<type> s={0,1,2,3,4};
std::set::iterator iter =s.begin();  //at 0
++iter;  //at 1
*iter;  //to access the element pointed at by the iterator(dereference)
(iter != s.end());
auto second_iter=iter;  //"copy construction"

There are a few different types of iterators, since containers are different.

  • input iterators can be on the RHS (right hand side) of an =sign:
    • auto elem =*it;
  • output iterators can be on the LHS of =:
    • *elem = value;
Container Type of iterator
Vector Random-Access
Deque Random-Access
List Bidirectional
Map Bidirectional
Set Bidirectional
Stack No iterator
Queue No iterator
Priority Queue No iterator

P.S. Random access iterators support indexing by integers!

These are equivalent :

1
2
auto key = (* iter).first;
auto key =iter->first;

Pointers（指针）

Pointers are objects that store an address and type of a variable.

Iterators are a form of pointers.

Pointers are more generic iterators. (can point to any object, not just elements in a container)

Classes

Template Classes and Const Correctness

Template Functions

Functions and Lambdas

Midquarter Review

Operators

Special Member Functions

Move Semantics

std::optional and Type Safety

RALL, Smart Pointers, and Building C++ Projects

Class Review

Guest Lecture from Ethan Chi: C++ for Data Science and ML