CS106L笔记

CS106L

前言：

Lec 0 Intro

the course’s goal:

  • Learn the feature of cpp
  • Become comfortable with cpp documentation
  • Familiar with the design philosophy of modern cpp

History:

Assembly->C->C++

C’s weakness

  • No objects or classes

  • Difficult to write code that worked generically

  • Tedious when writing large programs

Design Philosophy of C++:

  • Allow the programmer full control, responsibility, and choice if they want it.
  • Express ideas and intent directly in code.
  • Enforce safety at compile time whenever possible
  • Do not waste time or space
  • Compartmentalize messy constructs

cpp is a multi-paradigm programming language

  • generic programming
  • object-oriented programming
  • ..

Lec 1&2 Stream

stringstream

two key steps:

state bits:

four standard output ways:

variables declared in the loop can only be used within the loop. They can’t be used outside the loop.

还是直接上代码的好..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// 先介绍stringstream
// ostringstream 联想到 cout，istringstream 则联想到 cin
void stringStreamTest() {
    ostringstream oss("Ito En Green Tea "); // default open mode
    // 这个时候这个stream里的指针摆在第一个("I")的位置上
    // 可以更改位置，例如：
    // oss("..",stringstream::ate)
    // 即将指针放在最末尾(at the end)
    
    // 用str()提取文字
    cout << oss.str() << endl; // "Ito En Tea"
    
    //oss.tellp()显示当前的指针位置。目前是在最开始
    auto pos = oss.tellp();
    
    // 移动到pos以后3个字符
    oss.seekp(pos + streamoff(3));
    
    // 所谓type conversion，转到string representation
    oss << 16.9 << " Ounce ";
    // 是的，因为在最开始写入，前面的内容被覆盖了
    cout << oss.str() << endl; // "16.9 Ounce 1"

    oss << "(Pack of " << 12 << ")";
    cout << oss.str() << endl; // "Ito En Tea 16.9 Ounce (Pack of 12)"
	
    // iss以oss的文本内容来构造
    istringstream iss(oss.str());
}

void stringPositionTest() {
    string token;
    ostringstream oss("Ito En Green Tea"); // position is at 0
    oss << 16.9; // 指针在最开始
    cout << oss.str() << endl; // "16.9En Green Tea", position at 4


    auto pos = oss.tellp() + streamoff(3); // fpos = position, off = offset
    oss.seekp(pos); // moves the position down 3 characters, position at 7
    oss << "Black";
    cout << oss.str() << endl; // "16.9En Black Tea", position at 12


    // moves position down 1 from current, position at 13
    // 另外一种用法
    // ostream& seekp (streamoff off, ios_base::seekdir way);
    // 第一个参数表示offset，后一个表示位置
    oss.seekp(streamoff(1), stringstream::cur);
    oss << "Milk";
    cout << oss.str() << endl; // "16.9En Black Milk", position at 17
}

void printBitInfo(istream& s) {
    cout << "State bits: ";
	
    // stream的四种状态
    cout << (s.good() ? "G" : "-"); // 表示输入正常，可继续接受输入
    cout << (s.fail() ? "F" : "-"); // 表示输入出现异常(Type mismatch, file can't be opened, seekg failed, so on)，未来不可以继续接受输入
    cout << (s.eof() ? "E" : "-"); // Reach the end
    cout << (s.bad() ? "B" : "-"); // Couldn't move characters to buffer from external resource(e.g. the file is suddenlt deleted)

    cout << endl;
    cout << "-----------" << endl;
}

// 非常合规的获得一个整数的方法
// prompt表示提示文字，reprompt表示错误重新提示文字
// const& 允许右值，同时也不会修改左值
int getInteger(const string& prompt,
               const string& reprompt) {
    while (true) { // 循环，直到满足条件
        cout << prompt; // 输出文字提示
        string line;
        if (!getline(cin, line)) { // getline，避免cin设置state麻烦，空格读取不了等各种情况
            throw std::domain_error("getLine: End of input reached while waiting for line.");
        }
        istringstream iss(line); //以这个string初始化istringstream
        int value;
        char extra; // 测试有没有多余的字符
        if (iss >> value && !(iss >> extra)) 
            return value; // 当且仅当iss输入value成功并且输入extra（多余的字符）失败（即没有多余的字符）时，才通过
        // 当iss(cin同理)输入数据时，返回的iss(cin)本身可以隐式转换为boolean值，代表输入是否成功
        cerr << reprompt << endl; // 输出错误提示
    }
}

When should use stringstream?

  • Processing strings
  • Formatting input/output
  • Parsing different types

When u want to just concatenate some strings, it’s faster to use str.append()!!

Type

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Next topic: Type
// 像下面的type表示起来很麻烦，还很容易报错
std::unordered_map<forward_list<Student>,unordered_set>::iterator begin = studentMap.cbegin();
// 该怎么解决呢？
// Method 1,name alias
using map_iterator = std::unordered_map<forward_list<Student>,unordered_set>::iterator;
map_iterator end = studentMap.cend();
// Method 2,auto
auto autoEnd = studentMap.end();

// auto 顺带还解决了一波多参数
// 从Python学习而来
// pair可以同时传递两个参数
pair<int, int> pairTest() {
	int smallNum = 1, largeNum = 2;
	return {smallNum,largeNum}; // uniform initialization
    // another way is 
    // make_pair(smallNum,largeNum);
}

// tuple则长度任意
tuple<int, double, string> tupleTest() {
	return { 1,2.0,"a str" }; // make_tuple(1, 2.0, "a str")
}

// in main():
int main(){
    auto test = pairTest();
	cout << test.first << " " << test.second << endl; // pair的第一种用法，用first和second
	auto [num1, num2] = pairTest(); // 第二种用法，Structured Bindings，但是仅限于c17之后
	// 一些深入研究：https://www.fluentcpp.com/2018/06/19/3-simple-c17-features-that-will-make-your-code-simpler/
    // 注意编译器的编译标准，可能会报错
    
	int a; double b; string c;
	tie(a, b, c) = tupleTest(); // tuple的接收，在c17之前只能用tie，或者更复杂的get(0)...
	auto [c, d, e] = tupleTest(); // c17之后，带上auto有如Python一样灵活
}

// Method 3 Structure
struct PriceRange
{
    int min, max;
};
// then you can return this struct

uniform initialization

c++ has many many initializations.

Therefore, a automatically deduced declaration is highly praised. This is called Uniform initialization in C++ 11.

1
2
3
4
5
6
7
8
9
struct Course{
    string code;
    int id;
};

int main(){
    Course now {"CS106L",123};
    vector<int> vec{3,1,2,2,3};
}

reference

1
2
3
4
5
6
7
8
string str = "hello";
auto c1 = str[2];
c1 = 'a';
cout << str << endl; // hello

auto& c2 = str[2];
c2 = 'a';
cout << str << endl; // healo

Lecture 3 Sequence Containers

example

With the power of STL, some operations can be done in a few steps. This gives you the extra time to understand the problem in more depth.

1
2
3
4
5
6
int main () {
    vector<int> vec(kNumInts);
    std::generate(vec.begin(), vec.end(), rand);
    std::sort(vec.begin(), vec.end());
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, "\n"));
    return 0;

sequence containers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// we will introduce vector and deque
// vector's key difference with basic array
// is that vector has at(),which will have bounds check
vector<int> vec(15,5); // a vector with 15 elements,all assigned as 5
cout << vec.at(20); // will throw an error
cout << vec[20]; // still work
// however, this is not set as default
// because if u can write correctly, the boundary check will just slow down the speed
// this is opposed to cpp's philosophy 

// vector has another disadvantage
// its push_front func executes slowly
// deque is more suitable for this job(double ended queue)
// its push_back/pop_back/push_front/pop_front are faster(especially *_front are faster than vector)
deque<int> deq;
deq.push_front(1); // faster than vec.push_front(1);

// whereas, it's still recommended to use vector by default,as its common operations like element access are faster than deque.

Lec 4 Associative Containers

Container Adaptors

using deque

Associative Adaptors

map/set: iterate

unorderd_map/unordered_set : access individual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// map
while(stream >> word) {
    // This single line is doing a ton of work. The square bracket notation for
    // accessing values in maps will return a reference to the value associated
    // with the specified key. We can then modify it with ++ directly.
    //
    // However, if response is not already a key in the map, the square brackets
    // do a bit of extra work first. They automatically insert a new key-value
    // pair into the map, where the key is response and the value is a
    // reasonable default value -- in the case of integers, 0.
    ++frequencyMap[word];
}

//another way
frequencyMap.insert({"word",1}) // using pair(with uniform constructor)

// Returns the number of keys equal to response.
// In anything but a multimap/multiset, this is
// either going to be 1 or 0.
if (frequencyMap.count(response)) {
    cout << frequencyMap[response] << " entries found." << endl;
} else {
    cout << "None." << endl;
}

// set
// using insert
set<string> groceryList;
groceryList.insert("milk");
groceryList.insert("eggs");

// This set contains "milk".
if (groceryList.count("milk")) {
    cout << "We are getting milk!" << endl;
} else {
    cout << "Well, no use crying..." << endl;
}

// remove
groceryList.erase("eggs");

iterator

non-linear to linear

(inner method: in-order traversal)

*iter to dereference

.end()

advantage: tackle problems in a standardised way

five kinds of iterators:

  • Input Iterators.(can only access elements)
  • Output Iterators.(can only assign elements)
  • Forward Iterator.(input & output, but can only move in the forward direction)
  • Bidirectional Iterators.(Forward, and can also move backwards)
  • Random-Access Iterators.(move randomly like pointers)

Lec 5 Advanced Containers

Multimaps

the same key has multiple values

examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// usage of find
// we can also use the find algorithm to look for an element
// in a collection and return an iterator to it
vector<int>::iterator it = std::find(vec.begin(), vec.end(), 5);
if(it != vec.end()) {
    cout << "Found elem " << *it << endl;
} else {
    cout << "Element not found " << endl;
// find is slightly faster than count(count is based on find)

// another words,the find in string is a little bit different
    std::string s = "hell[o";
if (s.find('[') != std::string::npos)
    ; // found
else
    ; // not found
    
// after c++23,the string supports contains() to find
// it will return a boolean
s.contains("hello");
s.contains('h');
    
// upper_bound versus inner_bound
    
set<int> mySet{4,1,3,5,55,5, 9, 22, 19, 28};

// we can iterate through a range of elements in
// a sorted collection
    
// (sort first!)
// .lower_bound(value) (the first value >= value)
// .upper_bound(value) (the first value > value)
// below code means [7,28]
set<int>::iterator iter = mySet.lower_bound(7);
set<int>::iterator end = mySet.upper_bound(28);
    
// map<string,int> -> pair<string,int>
// pair.first
// pair.second 
// when using map iterators, notice the brackets
// e.g. (*i).first
// notice the parentheses

Lec 6 Templates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// a good example that shows how to get a value of any type
template <typename DataType>
DataType getType() {
    while(true) {
    /* First we get a line of input from the user. */
        string line;
        std::getline(cin, line);
        /*
        * We'll again use an istringstream because we only want to pull data
        * out of the stream once we have put the string's contents in it.
        */
        std::istringstream converter(line);
        /*
        * Try getting an DataType from the stream. If this is not succesful
        * then user input was not a valid input.
        */
        DataType result;
        if(converter >> result) {
            /*
            * See if we can extract a char from the stream.
            * If so, the user had junk after a valid int in their input.
            */
            char remaining;
            if(converter >> remaining) {
                cout << "Unexpected character. Try again." << endl;
            } else {
                /*
                * Input was succesfully converted to DataType with no
                * trailing stuff at the end.
                */
                return result;
            }
        } else {
            cout << "Not a valid input. Try again." << endl;
        }
    }
}

Lec 7 Templates and Functions

Implicit Interface

1
2
3
4
5
template <typename Collection, typename DataType>
int countOccurences(const Collection<DataType>& list,DataType val)
// above is better compared to
// int countOccurences(T1 list,T2 val)
// as it may cause dismatch when executing like "list[0] == val"

In c++ 20, it added named requirements on the template arguments.

lambda

my problem: need a generic function like

1
2
3
4
5
6
DataType input(judgeFunc){
	while(input){
		if (judgeFunc(input) == true)
			return input;
		}
}

how to tackle?

  1. using function pointer
  2. lambda

（上学期写数据结构的时候正好考虑到了这个需求，并且想得一模一样！听到这里真的很激动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<Student> StudentDatabase::studentsInYear(std::string yearToFind) {
    vector<Student> ret;
	// STL algorithm function
    // copy element in db(database) that meets the command of lambda from begin to end,and insert into ret from  back
    // ret means return(woo)
    std::copy_if(db.begin(), db.end(), std::back_inserter(ret),
                                        [&yearToFind](Student s) -> bool {
                                                return s.classLevel() == yearToFind;
                                        });


    return ret;
}

// the lambda actually is a class constructed by c++ compiler
// before c++11, similar behaviors can only be reached by creating a class that overloads the () operator by yourself

Lec 8 Functions and Algorithms

Remain

using reference capture in lambda: auto someFunc = [&vec](){ //.. };

Algorithms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
double total = std::accumulate(nums.begin(), nums.end(), 0.0);

/* The nth_element function will sort the array *a little bit*.  That means that
*   * The nth element (where n is a parameter) will be in the same position
*     it would be in if the array was sorted.
*   * All elements to the left of the nth element will be less than it, and
*     all elements to the right or it will be greater than it.
*
* The first property guarantees that if we call nth_element with n being
* halfway between begin and end we can recover the median by simply reading
* that element.
*/
std::nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
int median = nums[nums.size() / 2];

std::sort(nums.begin(), nums.end());
std::reverse(nums.begin(), nums.end());

erase-remove idiom

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool IsOdd(int i) { return i & 1; }

int main() {
    // Initializes a vector that holds numbers from 0-9.
    std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // Removes all elements with the value 5.
    // remove or remove_if will put the elements that meet the command
    // to the end of the vector
    // and will return the iterator pointing to the first element meeting the commmand
    // remove can't just move out these elements
    // as it is just a algorithm so that it can't change the in
    v.erase(std::remove(v.begin(), v.end(), 5), v.end());

    // Removes all odd numbers.
    v.erase(std::remove_if(v.begin(), v.end(), IsOdd), v.end());
    
    // in c++20 std::erase and std::erase_if provide the method that directly move and erase the elements
}

ostream_iterator

1
2
3
4
5
6
7
8
9
10
// usage: iterator for output to ostream
// e.g. write elements to cout
// after C++11
#include<iterator>

std::vector<int> data = { 1, 21, 31, 41, 51, 61, 71, 81 };
// bind to cout,separated by ','
std::ostream_iterator<int> dataIter(std::cout, ", ");
// copy the data from begin to end to the ostream_iterator
std::copy(data.begin(), data.end(), dataIter);

bind and placeholders

https://www.geeksforgeeks.org/bind-function-placeholders-c/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Driver function to demonstrate bind()
void func(int a, int b, int c)
{
    cout << (a - b - c) << endl;
}

int main(){
    
// C++ code to demonstrate placeholder
// property 1
#include <iostream>
#include <functional> // for bind()
using namespace std;
  
// for placeholders
using namespace std::placeholders;
  
// Driver function to demonstrate bind()
void func(int a, int b, int c)
{
    cout << (a - b - c) << endl;
}
  
int main ()
{
    // for placeholders
    using namespace std::placeholders;
  
    // Second parameter to fn1() is assigned
    // to 'a' in fun().
    // 2 is assigned to 'b' in fun
    // First parameter to fn1() is assigned
    // to 'c' in fun().
    auto fn1 =  bind(func, _2, 2, _1);
  
    // calling of function
    cout << "The value of function is : ";
    fn1(1, 13); // 13 - 2 - 1 = 10
}

Lec 9 STL Summar

Iterator Adapter:

1
2
3
// back_inserter
copy(source.begin(), source.end(), back_inserter(target));
fill_n(back_inserter(vec.end()), 3, -1 ) // {a,b,..-1,-1,-1}

more applications like boost library, multi-thread programming..

Key Concept: Abstraction

这堂课带着写代码，还是挺有收获的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<iterator> // ostream_iterator
#include<algorithm> // transform

// alias
// particular declarition
// 尤其是在编写大项目时，为了避免发生命名冲突和重载
// 不建议直接使用using namespace std;
// 而是使用alias
using std::cout;	using std::endl;

// 接下来很有讲头
while (std::getline(file,line)){ 
    // getline实际上返回的是一个stream
    // 但是stream可以隐式地转换为bool，表示输入是否成功
    // 以此可读取整个文件
    // 但是！不建议再在循环里读取文本！可能会影响到外面的循环！
    
	std::transform(line.begin(), line.end(), std::ostream_iterator<char>(cout, ","), ::tolower);
    // transform是algorithm里的一个有用的算法，相当于对一段range进行for循环，然后对每个元素采取操作
    // 前两个参数表示开始点和结束点
    // 第四个参数是转小写，前面的::是表示全局空间里的作用域符，可以不加
    // 第三个参数是一个iterator adapter，它会将转为小写后的char送到绑定的cout这个ostream里，并且每个以“，”间隔
    
}

Lec 10 Classes and Const Correctness

c/c++ extensions

from this link:

There are at least four different extensions usable for C++ files:

  • .C
    Not very popular since it requires a case-sensitive file system (otherwise, it would clash with old .c file names), and even a few modern OS are not case-sensitive.
  • .c++
    Some OS or file systems don’t support the + character in file names.
  • .cpp
    That’s very portable across file systems.
    But, it might be less consistent than .cxx
  • .cxx
    Very portable across file systems (not more than .cpp)
    Using the name CXX for C++ is quite popular because CPP usually designates the C (and C++) pre-processor.

For headers, there are at least five extensions:

  • .h
    Traditional C header files.
    Since the compiler doesn’t do anything based on this extension, it can be used for C++ header files too.
    Furthermore, there are a lot of header files that are designed to be included by both C and C++ translation units.
    In that case, it’s natural to give them this extension.
  • .H, .hpp or .hxx
    That’s very natural to give one of these extensions for C++ header files (being consistent with the name of C++ translation units).
    That’s not a bad idea to use one of these name for pure C++ header files only (containing class definitions, or templates, or any other feature not supported by C).
  • No extension
    That’s internally used by a number of C++ compilers for iostream, vector, algorithm and all others new-style C++ headers.

why don’t use global variables

  • “Global variables can be read or modified by any part of the
    program, making it difficult to remember or reason about
    every possible use”

  • “A global variable can be get or set by any part of the
    program, and any rules regarding its use can be easily broken
    or forgotten”

  • “Non-const variables can be read or modified by any part of
    the function, making it difficult to remember or reason about
    every possible use”

  • “A non-const variable can be get or set by any part of the
    function, and any rules regarding its use can be easily broken
    or forgotten”

const

const value

1
const int a = 4;

const member function

1
2
3
4
5
6
7
8
class Foo{
    void foo() const;
};

void Foo::foo() const{
    std::cout << "foo" << std::endl;
    return;
}

const class non-const class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Foo{
    void foo1();
    void foo2() const;
};

void Foo::foo1(){
    std::cout << "foo1" << std::endl;
    return;
}

void Foo::foo2() const{
    std::cout << "foo2" << std::endl;
    return;
}

int main(){
    const Foo f1;
    foo f2;
    f2.foo1();
    f2.foo2(); // all feasible
    
    f1.foo2();
    //f1.foo1(); // compile error
    // const class can only call const member functions
}

const pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
// method:
// read from right to left

//constant pointer to a non-constant int
int * const p; // p is a const int*

//non-constant pointer to a constant int
const int* p;
int const* p; // *p is a const int 

//constant pointer to a constant int
const int* const p;
int const* const p; // const p is a const int*

const iterators

1
2
3
4
const vector<int>::iterator iter1 = vec.begin(); // equal to int * const p
// the finger is fixed, but the value which the finger points to is changable

vector<int>::const_iterator iter2 = vec.begin(); // finger is changable but not value

Lec 11 Operators

operator overloading

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// return as reference
// so when it is returned
// the return value could be used as left value
vector<string>& vector<string>::operator+=(const string& element){
    push_back(element);
    return *this;
}

// not recommend
// set as non-member function
StringVector StringVector::operator+(const StringVector& other){
    StringVector result = *this; // copy constructor
    for (const std::string& s : other){
        result.push_back(s);
    }
    return result;
}

operator overloading is or is not a member function?

  1. Assignment (=), subscript ([]), function call (“()”), and member selection (->) operators must be defined as member functions
  2. some(like <<) must be be defined as non-member(we write for rhs, but not lhs)
  3. symmetric operation should be non-member functions, so we can prevent situations like, a + 1 is legal, 1 + a is illegal
  4. unary operation should be used as member function, so we can easily change the private value
  5. some binary operation(e.g. +=) should be member function, too. Or it’s hard to change the inner value.

POLA

principle of least astonishment

if a necessary feature has a high astonishment factor, it may be necessary to redesign the feature.

copy

shallow copy/deep copy

比如说，对于一个对象，如果里面有new出来的数组，如果只是对其浅拷贝，那么它默认只会获取new的那个指针，而不是整个数组，因而拷贝和被拷贝的对象的数组，指向的是同一段内容。而深拷贝则需要手动制定，以将两者区别开来。

Lec 12 Special Member Functions

recap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// if you want to overload [] 
// then you should consider overload const and non-const version,or the const object can't use it 
// e.g. if only have non-const

// const object can't call it
int& myVector::operator[](size_t index){
    return _elems[index];
}

// const object can only overload [] with this below
//const int& myVector::operator[](size_t index) const{
//    return _elems[index];
//}

int main(){
    myVector v1;
    const myVector v2;
    v1[0] = 0;
    int elem1 = v1[0];
    
    //int elem2 = v2[0]; // const can't use it, so compile error.
}

copy construction vs copy assignment

these special functions will be created by compiler, but they won’t always work, especially with something irrelated to the class itself(like heap, stream, etc)

  • default construction

  • copy construction

  • copy assignment

  • destruction

what’s the difference between construction and assignment?

https://www.geeksforgeeks.org/copy-constructor-vs-assignment-operator-in-c/

https://www.geeksforgeeks.org/copy-constructor-in-cpp/

(geeksforgeeks is really recommended!)

e.g.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Test foo(){
    Test test;
    return test; // copy constructor(the original will diminish as the function ends)
}

myVector& add(const int& value){ // not copy! by reference!
    push_back(value);
    return *this;
}

int main()
{
  Test t1, t2; // default constructor
  t2 = t1; // copy assignment (don't create new space)
  Test t3(); // a function
  Test t3 = t1; // copy constructor (create new space)

}

Therefore, the codes below can’t run correctly, cause the copy is just a shallow copy.

这部分还是挺重要的，还是切换成中文说吧。下面这样copy = vec，在没有自己定义复制构造函数的情况下，只会执行系统默认编写的复制构造函数。系统自己写的特点是什么呢？只能浅拷贝（shallow copy），如果成员有复制构造函数可以拷贝，就直接拷贝，而不能直接调用class之外（例如，new出来的内存）之类的东西。

再看下面这个函数。他的第二句话vector<int> copy = vec;，实际上就是直接执行了系统编写的浅拷贝。原来vector里的size等变量，可以直接浅拷贝过来。但如果vector里面，还有一个*elem数组，并且new出了一段内存来存储数据的话，那么这个复制构造函数，并不会将所有数据全部拷贝到一个新数组里，而只是构造出一个指针，指向的内容还是原来的数组。但是在退出函数时，copy就被销毁了，不仅没有拷贝回来，还带回来一个野指针。

1
2
3
4
5
6
7
vector<int> operator+(const vector<int>&vec, int elem){
    vector<int> copy = vec; // constructor
    // but the default is only shallow
    copy += element;
    return copy; // copy constructor
    // and the copy is freed !!
}

这个时候，就需要我们自己写一个copy constructor：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// copy constructor
// allocate new and copy
// e.g.
template<typename Type>
myVector<Type>(const myVector<Type>& other):size(other.size){
    elems = new Type[size];
    std::copy(other.begin(),other.end(),begin());
}

// copy assignment
// 1 compare
// 2 free old
// 3 allocate new and copy
// e.g.
template<typename Type>
myVector& myVector<Type>::operator=(const myVector<Type>& other){ // return as reference
    if (&other != this){
    	size = other.size;
        delete[]elems;
        elems = std::new Type[size];
        std::copy(other.begin(),other.end(),begin());
    }
	return *this; // return itself for chain operation(though bad code)
}

rule of three/zero

When do you need to write your own special member functions?

when the default one generated by the compiler does not work.(e.g. pointers, streams, those are pointed to outside resources.

Rule of Three: If you explicitly define (or delete) a copy constructor, copy assignment, or destructor, you should define(or delete) all three.

1
2
3
~myVector(); // deconstructor
myVector(const myVector& other); // copy constructor
myVector& myVector::operator=(const myVector& other); // copy assignment

RVO

**Return Value Optimization**，即，编译器会对函数的返回值进行编译优化，减少不必要的copy。

例如，某函数要return的是函数体内的一个x变量，然后我们将其赋给main里的变量a（即，a = func();），照道理x需要再被拷贝一下（尽管这不是必要的），然后返回这个copy，然后x被摧毁。但是此时编译器会捕捉到这个细节，直接在a上进行赋值，减少拷贝。

去掉这种优化的办法：

1
g++ xxxxx.cpp -std=c++11 -fno-elide-constructors -o move

Lec 13 Move Semantics

c++的vector里有emplace_back和push_back两种函数，前者接收右值，后者接收左值。示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <vector>
#include <string>
#include <cassert>
#include <iostream>
 
struct President
{
    std::string name;
    std::string country;
    int year;
 
    President(std::string p_name, std::string p_country, int p_year)
        : name(std::move(p_name)), country(std::move(p_country)), year(p_year)
    {
        std::cout << "I am being constructed.\n";
    }
    President(President&& other)
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)
    {
        std::cout << "I am being moved.\n";
    }
    President& operator=(const President& other) = default;
};
 
int main()
{
    std::vector<President> elections;
    std::cout << "emplace_back:\n";
    // support after c++17 
    auto& ref = elections.emplace_back("Nelson Mandela", "South Africa", 1994);
    assert(ref.year == 1994 && "uses a reference to the created object (C++17)");
 
    std::vector<President> reElections;
    std::cout << "\npush_back:\n";
    reElections.push_back(President("Franklin Delano Roosevelt", "the USA", 1936));
}

wasted copy->move directly

lvalues vs rvalues

lvalue:

  • can find name(identity) -> &var is valid

rvalue:

  • opposite: can’t find &var

move constructor and assignment

move(steal) from rvalue

rvalue can be copyed or moved, as it’s disposable.

这是一种可行但是并没有真正用到rvalue和move精髓的代码：

为什么呢？因为尽管它传入的是右值的引用，但事实上，在这个函数里，它是一个左值，这个时候，就需要用到move表示其为右值：

原课程的PPT：

因此，原先的rule of three变为了rule of five，即需要额外指定move constructor and move assignment：

swap

在原先的swap基础上，加上move使其转为右值，以减少原先作为左值的额外拷贝。

1
2
3
4
5
6
template<typename T>
void swap(T& a, T& b){
    T temp = std::move(a);
    a = std::move(b);
    b = std::move(temp);
}

perfect forwarding

读了很多，很有意思，不过也很难..其实主要解决的问题还是，在函数参数中的右值引用，在函数本体里仍然有可能作为一个左值存在。

Perfect forwarding requires forwarding references in order to preserve the ref-qualifiers of the arguments. Such references appear only in a deduced context. That is:

1
2
3
4
5
template<class T>
void f(T&& x) // x is a forwarding reference, because T is deduced from a call to f()
{
 g(std::forward<T>(x)); // g() will receive an lvalue or an rvalue, depending on x
}

The following does not involve perfect forwarding, because T is not deduced from the constructor call:

1
2
3
4
5
template<class T>
struct a
{
 a(T&& x); // x is a rvalue reference, not a forwarding reference
};

在template的帮助下，函数可以对x的类型作出推断，判断其为左值或右值，这样在接下来的函数里，就不会出现右值变成左值的可能。

Lec 14 Inheritance

1
const int* const myClassMethod(const int* const & param) const;

namespace

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// in the previous code we see a lot of alias
using std::endl;
using std::cout;

// lead into conflict
#include<algorithm>
using namespace std;
int main(){
    int count; // its precedence is higher
    vector<int> vec{1,2,1,1,3};
    
    // cout << "count 1 by algorithm" << count(vec.begin(),vec.end(),1) << endl; // conflict and error
    cout << "count 1 by algorithm" << std::count(vec.begin(),vec.end(),1) << endl; // ok
    return 0;
}

// syntax
namespace Lecture{
    int count(vector<int> vec,int target){
        int num = 0;
        for (const auto &i:vec.size()){
            if (vec[i] == target)
            	num++;
        }
        return num;
    }
}

// so now you can use it..
int main(){
    vector<int> vec{1,2,1,1,3};
    cout << "count 1 by Lecture" << Lecture::count(vec,1) << endl; // ok
}

inheritance

感觉上不如软荣上实践得来的经验多..得去CS108才能得到更好的锻炼。

不过有一句还是值得摘录的：No “virtual” members - instead, if a member has the same name as as inherited member,it hides it.

技术
#技术 #c++
CS106L笔记
http://baokker.github.io/2022/08/07/CS106L笔记/
作者
Baokker
发布于
2022年8月7日
更新于
2022年8月17日
许可协议