C++复习（入门）#

1
// Enum type in C:
2
enum ColorPallet1 { Red, Green, Blue };
3
enum ColorPallet2 { Yellow, Orange, Red };
4

5
// Enum Class in C++
6
// Declaration
7
enum class ColorPalletClass1 { Red, Green, Blue };
8
enum class ColorPalletClass2 { Yellow, Orange, Red };
9

10
// Assignment
11
ColorPalletClass1 col1 = ColorPalletClass1::Red;
12
ColorPalletClass2 col2 = ColorPalletClass2::Red;

1
for (auto n : my_vector){
2
  std::cout<< n;
3
}

1
int a = 1;
2
int* pp = &a;
3
int** r = &pp;
4
std::cout << "r: " << r << std::endl;
5
std::cout << "*r: " << *r << std::endl;
6
std::cout << "**r: " << **r << std::endl;
7
// 如果写
8
int* r = &pp;
9
//会报错，因为&pp的类型是int**，而定义的r是int*
10
//int* r 和 int *r 的两种写法是等价的，最好固定一种写法
11
//另外，在定义时不要写成
12
int* p,q; //这实际上定义的是一个指针p和一个整型q, 另外，指针定义的时候，要初始化：int* p = nullptr

1
int i = 5;
2
int* p = new int;
3
p = &i; //上面定义new int的地址就已经丢失了
4
delete p;// 忘记delete会导致内存泄漏

1
int i = 10;
2
int& j = i;
3
j++;

1
int main() {
2
  std::vector<int> my_vector = {1, 2, 3, 4, 5, 6, 7, 8};
3
  for (auto n : my_vector) {
4
    n++;
5
  }
6
  // What is the value of my_vector? 不变
7
  for (auto &n : my_vector) {
8
    n *= 10;
9
  }
10
  //{10, 20, 30, 40, 50, 60, 70, 80}
11
  return 0;
12
}

1
arr = new int[size];
2
delete [] arr;
3
push_back(int*& arr, int& size, int new_item)//和动态数组相关的函数，也需要加入size这个参数

1
std::pair<std::string, int> p1("Ari", 3);
2
std::pair<std::string, int> p2("Ted", 4);
3
std::pair<std::string, int> p3 = p1;
4

5
std::cout << "p1.first: " << p1.first << std::endl;
6
std::cout << "p1.second: " << p1.second << std::endl;

1
std::vector<int> v = {1, 2, 3, 4, 5};
2
// An easy way of iteration
3
for (int n : v) {
4
std::cout << "n: " << n << std::endl;
5
}
6
// General way of iteration
7
std::vector<int>::iterator it;
8
for (it = v.begin(); it != v.end(); ++it) {
9
int n = *it;//可以理解为一个指针
10
std::cout << "n: " << n << std::endl;
11
}

1
// using auto
2
std::set<int> s = {1, 2, 3, 4, 5};
3
for (auto it = s.begin(); it != s.end(); ++it) {
4
const int &n = *it;//const防止修改，引用防止复制。想要修改就把const去掉
5
std::cout << "n: " << n << std::endl;
6
}

1
// Insert a number before 3
2
std::vector<int> v = {1, 2, 3, 4, 5};
3
for (auto it = v.begin(); it != v.end(); ++it) {
4
  const int &n = *it;
5
  if (n == 3) {
6
    it = v.insert(it, 12);//这里会返回一个迭代器对象，必须重新对it赋值，不能只调用，因为插入后，原来的it失效了，下一次使用*it时，会报UB的错(Undefined Behavior!)
7
    ++it;
8
  }
9
}

1
int BinaryOperation(int a, int b, std::function<int(int, int)> func) {
2
return func(a, b);
3
}
4
int Add(int a, int b) { return a + b; }
5
int Mult(int a, int b) { return a * b; }
6

7
int main() {
8
int result1 = BinaryOperation(10, 20, Add);
9
int result2 = BinaryOperation(10, 20, Mult);
10
}

1
int IncrementByTen(int a) { return a + 10; }
2

3
int main() {
4
std::vector<int> inputs = {0, 1, 2, 3, 4, 5, 6, 7, 8};
5
std::vector<int> outputs(inputs.size());
6
// Increment all of them
7
std::transform(inputs.begin(), inputs.end(),
8
outputs.begin(), IncrementByTen);
9
}
10

11
bool IsOdd(int i) { return ((i % 2) == 1); }
12

13
int main() {
14
std::vector<int> inputs = {0, 1, 2, 3, 4, 5, 6, 7, 8};
15
std::vector<int> outputs(inputs.size()); // {0, 0, ...,0}
16
// Increment all of them
17
std::copy_if(inputs.begin(), inputs.end(),
18
outputs.begin(), IsOdd);
19
// Output = {1, 3, 5, 7, 0,...,0}
20
}

1
Point(const Point &rhs){//引用传递，另外const表示让数据来源“只读”，不会被意外修改
2
  //非指针的属性，正常赋值
3
  //动态内存的属性，要新开一块内存，然后把老对象的值复制给新的
4
}

1
void F(Point local_p) {
2
  //会调用拷贝构造函数和析构函数
3
  std::cout << "Inside F. Pass by value" << std::endl;
4
  std::cout << "local_p.i_: " <<local_p.i_ << ", local_p.j_: " << local_p.j_<< std::endl;
5
}

1
void F_reference(Point &p) {//只传递地址，没有新对象产生，本质是一个别名
2
  std::cout << "Inside F. Pass by reference" << std::endl;
3
}//

1
class SinglyLinkedList {
2
public:
3
  SinglyLinkedList() { }
4
  ~SinglyLinkedList() { }
5
  ListNode *head_;
6
  // ...
7
};
8

9
//错完的版本
10
SinglyLinkedList(const SinglyLinkedList& head_){
11
  if ()
12
  ListNode* newNode = new ListNode();
13
  newNode->value = head_->value;
14
  newNode->next = head_->next;
15
}
16

17
//正确的
18
// 1. 这是一个拷贝构造函数，没有返回类型，参数是常量引用以保证性能和安全
19
SinglyLinkedList(const SinglyLinkedList& other) {
20
    if (other.head_ == nullptr) {
21
        head_ = nullptr;
22
        return;
23
    }
24

25
    // 2. 首先复制头节点，申请新内存
26
    head_ = new ListNode(other.head_->value);//由于ListNode的构造函数的默认实现，next指向nullptr
27

28
    ListNode* currentNew = head_;
29
    ListNode* currentOld = other.head_->next;
30

31
    // 3. 循环遍历旧链表，逐个“克隆”
32
    while (currentOld != nullptr) {
33
        // 为新节点申请独立内存，而不是直接指向旧地址
34
        currentNew->next = new ListNode(currentOld->value);
35

36
        // 移动指针继续往后走
37
        currentNew = currentNew->next;//此时为nullptr
38
        currentOld = currentOld->next;
39
    }
40
}

1
class Point {
2
public:
3
  // PARAMETERIZED Constructor Version 1
4
  Point(int i, int j) {
5
    std::cout << "**PARAMETERIZED constructor." << std::endl;
6
    i_ = i;
7
    j_ = j;
8
    z_ = new int;
9
  }
10
  // PARAMETERIZED Constructor Version 2 初始化列表
11
  Point(int i, int j) : j_(j), i_(i) { //先i后j
12
    std::cout << "**PARAMETERIZED constructor." << std::endl;
13
    z_ = new int;
14
  }
15
private:
16
  int i_;
17
  int j_;
18
};

1
std::list<int> myList = {10, 20, 30, 40};
2
auto it = myList.begin();
3
std::advance(it, 2); // 手动移动到索引 2 的位置（即第三个元素 30）
4
std::cout << *it;

1
struct ListNode {
2
  int val;
3
  ListNode *next;
4
  ListNode(int x) : val(x), next(nullptr) {} //initialization list
5
};

1
class MapSetGraph {
2
Public:
3
  void DFS(int root){
4
    std::map<int, int> &marks;
5
    DFS_helper(root, marks);
6
  }
7
  void DFS_helper(int root, std::map<int, int> &marks);
8
  std::map<int, std::set<int>> edge_map_;
9
};
10

11
void DFS_helper(int root, std::map<int, int> &marks) {
12
  marks[root] = 1;
13
  std::cout << "visited: " << root << std::endl;
14
  for (const int child : edge_map_[root]) {
15
    if (marks[child] != 1) {
16
      DFS_helper(child, marks);
17
    }
18
  }
19
}

1
void MapSetGraph::BFS(int root) {
2
  std::map<int, bool> visited;
3
  std::queue<int> q;
4
  q.push(root);
5
  visited[root] = true;
6
  while (!q.empty()) {
7
    int cur = q.front();
8
    q.pop();
9
    for (auto &n : edge_map_[cur]) {
10
      if (!visited[n]) {
11
        visited[n] = true;
12
        q.push(n);
13
      }
14
    }
15
  }
16
}

1
// without memoization
2
int Fibonacci(int n) {
3
  if (n == 0 || n == 1) {
4
    return 1;
5
  }
6
  int l = Fibonacci(n - 2);
7
  int r = Fibonacci(n - 1);
8
  return r + l;
9
}//存在多次重复计算
10

11
//With memoization
12
std::unordered_map<int, int> memo;
13

14
int Fibonacci(int n) {
15
  if (n == 0 || n == 1) {
16
    return 1;
17
  }
18

19
  if (memo.count(n) > 0) {
20
    return memo[n];
21
  } else {
22
    memo[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
23
  }
24
  return memo[n];
25
}//计算出来的数存起来，下次用时候直接拿，避免重复计算

1
//Tabulation
2
int Fibonacci(int n) {
3
  // Allocate for 0 to n included
4
  std::vector<int> d(n + 1);
5
  d[0] = d[1] = 1;
6

7
  for (int i = 2; i <= n; i++) {
8
    d[i] = d[i - 1] + d[i - 2];
9
  }
10
  return d[n];
11
}
12

13
//Memoization
14
std::unordered_map<int, int> memo;
15
int Fibonacci(int n) {
16
  if (n == 0 || n == 1) {
17
    return 1;
18
  }
19

20
  if (memo.count(n) > 0) {
21
    return memo[n];
22
  } else {
23
    memo[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
24
  }
25
  return memo[n];
26
}