Lane
面向对象程序设计

面向对象程序设计

2025年01月14日 4.6k 字 大概 24 分钟

week 1

C++的介绍

the first c++ programme

1
2
3
4
5
6
7
8
9
# include <iostream>
using namespace std;

int main()
{
    cout <<"Hello,World! I am "<< 18
         <<" Today!"<< endl;//endl理解为回车
         return 0;
}

read input

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;

int main()
{
    cout << "Please enter your age: ";
    int age;
    cin >> age;
    cout << "Hello ,World! I am" << age <<" years old!"<< endl;
    return 0;
}

Using Objects

The string 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//在程序的开头引用头文件
#include <string>
//定义string变量
string str;
//初始化
string str = "Hello";
//读和写
cin >> str;
cout  << str;
//assignment
char cstr1[20];
char cstr2[20]="jaguar";
string str1;
string str2= "panther";
cstr1=cstr2;//非法
str1= str2; //合法
//Concatenation
string str3;
str3= str1+ str2;
str1+=str2;
str1+= "a string literal";
// constructors(Ctors)
string (const char *cp, int len);
string (const string& s2, int pos);
string (const string& s2, int pos ,int len);
// sub-string
substr(int pos ,int len);
//Modification
assign(...);
insert(...);
insert(int pos,const string& s);
erase(...);
append(...);
replace(...);
replace (int pos, int len,const string& s);
//search
find (const string& s);

string 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
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str1="foo";
    string str2="bar";
    string str3=str1+str2;
    cout <<"str3 = "<<str3 <<endl;
    str2+=str1;
    cout <<"str2 = "<<str2 << endl;

    str3 = "hello, china!";
    string str4("hello, zju!");
    string str5(str3);
    string str6(str3, 7, 5);
    cout <<"str4 = "<<str4 <<endl;
    cout <<"str5 = "<<str5 <<endl;
    cout <<"str6 = "<<str6 <<endl;

    string str7 =str3.substr(7,5);
    cout <<"str7 = " << str7 << endl;
    string str8 = str3;
    str8.replace(7,5,"hangzhou");
    cout <<"str8 = "<< str8 <<endl;

    str8.assign(10, 'A');
    cout <<"str8 = "<< str8 <<endl;

    string str9 = "hello, hangzhou city";
    cout << "str9 = " << str9 << endl;
    string str_to_find = "hangzhou";
    cout << str9.find(str_to_find) << endl;
    str9.replace(str9.find(str_to_find),str_to_find.length(),"beijing");
    cout <<"str9 = "<< str9 <<endl;
}

File I/O

1
2
3
4
5
6
7
8
9
#include <ifstream> //read from file
#include <ofstream> //write to file

ofstream File1("C:\\test.txt");
File1 << "Hello world" << std::endl;

ifstream File2("C:\\test.txt");
std::string str;
File2 >> str;

I/O example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include <fstream>
#include <string>
using namespace std;

int main()
{
    string str1= "foo, bar!";
    ofstream fout("out.txt");
    fout << str1 << endl;

    ifstream fin("out.txt");
    string str2, str3;
    fin >> str2 >> str3;
    cout << "str2= " << str2 << endl;
    cout << "str3= " << str3 << endl;
}

regex example(替换字符)

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
#include<regex>
#include <string>
using namespace std;

int main()
{
    string s ="hello,student@zju!";
    regex re("a|e|i|o|u");
    string s1 = regex_replace(s,re,"*");
    cout << s << "\n" << s1 << "\n";
}

week 2

A Quick Tour of C++

  • 这一节课cx老师通过介绍排序算法引出c++中的模板、自定义类、类的继承，快速介绍了c++中的几个性质（cx老师也说如果这一节课的每个步骤完全弄懂，这门课不用来听了bushi）
  • 首先用c++写了选择排序的程序，和C语言大差不差
  • 以下的例子介绍了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
40
41
42
43
44
45
46
#include<iostream>
#include<string>
template<typename T>
int min_element(T arr[],int begin,int end)
{
    int min_idx=begin;
    for(int i=begin+1;i<end;i++)
    {
        if(arr[i]<arr[min_idx])
          min_idx=i;
    }
    return min_idx;
}
template<typename T>
void swap(T a,T b)
{
    T temp=a;
    a=b;
    b=temp;
}
template<typename T>
void selection_sort(T arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        int min_idx=min_element(arr,i,n);
        if(min_idx!=i)
          swap(arr[min_idx],arr[i]);
    }
}
template<typename T>
void print_array(T arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        std::cout <<arr[i] << ' ';
    }
}

int main()
{
    std::string arr[]={"hello","boys","and","girls","zju"};
    int n=sizeof(arr)/sizeof(arr[0]);
    selection_sort(arr,n);
    print_array(arr,n);
}

  • 设计结构体来排序

    1. 引用传递(&):直接访问原始对象，这样能方便我们不额外开辟一个空间，直接修改原始对象。（当然对于常量变量并不会修改原始对象）
    2. 值传递：会额外开辟一个原始对象的副本。
    3. 对于我们的选择排序对于我们自定义的变量，我们需要自己定义我们的比较规则与输出规则。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    struct student{
      int id;
      std::string name;
       };
     bool operator<(const student &s1,const student &s2){
          return s1.id<s2.id;
      }
      std::ostream &operator<<(std::ostream&out,const student& s)
      {
      return out << "("<<s.id<<","<<s.name<<")";
      }

  • 引入自定义类,class(其中类里面的字段为private)，而前面的结构体其实本质上的字段是public，所以我们在main函数中对class进行初始化程序会报错。这就涉及到我们在自定义类构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Triangle{
    private:
      double a,b,c;
      double area, perimeter;
    public:
      Triangle(double a,double b,double c):a(a),b(b),c(c) {}
      void calc_area(){
        double p=(a+b+c)/2;
        area=sqrt(p*(p-a)*(p-b)*(p-c));
      }
      void calc_perimeter(){
        perimeter=a+b+c;
      }
};
//初始化时
Triangle arr3[]={Triangle(2,3,4),Triangle(3,4,5)};
  • 我们思考是否有一个抽象类，类似于前面的抽象类型来管理多个性质与成员相同的类。这就涉及c++的继承
    1. 注意抽象类的定义，抽象类定义为纯虚函数，即没有函数体，只有函数声明，其子类必须实现该函数。子类实现的函数的值存在在抽象类的protected域中。
    2. 继承的语法为：class 子类:访问修饰符 父类{};
    3. 子类实现父类的纯虚函数时，子类必须使用override关键字来修饰。
  • 此时在main函数中我们通常涉及指针数组来方便操作对象
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
class Shape{
protected:
  double area,perimeter;
public:
  virtual void calc_area()=0;
  virtual void calc_perimeter()=0;
};
class Rectangle:public Shape{
    private:
      double w,h;
     // double area, perimeter;
    public:
      Rectangle(double w,double h):w(w),h(h) {}
      void calc_area() override {
        area= w*h;
      }
      void calc_perimeter() override {
        perimeter=2*(w+h);
      }
};
//main函数调用
Shape* arr[]={new Rectangle(2,3),new Rectangle(5,5),new Circle(3),new Triangle(2,3,4)};
for (Shape* s:arr)
    {
        s->calc_area();
        s->calc_perimeter();
    }
  • 我们又仿照前面的结构体,按照下面的代码想要输出我们刚刚得到的结果，但是发现无法访问area和perimeter。因为我们的shape类的成员变量area和perimeter是protected的，所以无法访问。
  • 我们可以在Shape类中定义一个输出函数并采取friend字段。
  • 我们却发现输出的流却像地址,我们回到我们的打印的模板，此时的T其实是Shape*，所以此时的arr的类型就是指针，所以输出的流便是地址。
    我们可以额外再写一个T抽象函数专门针对指针类型
  • 我们继续前进：修改shape类，添加一个虚拟函数，想要输出每个类的名字，同时每个子类都实现这个函数。但是我们会发现程序报错：
    1. 因为我们输出函数中的Shape变量前有const修饰，说明我们不能改变它的状态，所以我们在输出函数中调用name()函数是不可行的。
    2. 我们想要解决需要在shape类中对name()函数用const修饰。显式告诉编译器我们在函数中不会改变状态。
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
std:: ostream &operator <<(std::ostream& out,const Shape& s)
{
  return out <<"("<<s.area<<","<<s.perimeter<<")";
}
//修改shape类
class Shape{
protected:
  double area,perimeter;
public:
  virtual void calc_area()=0;
  virtual void calc_perimeter()=0;
  friend std:: ostream &operator <<(std::ostream& out,const Shape&);
};
//添加print函数
template<typename T>
void print_array(T* arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        std::cout << *arr[i] << ' ';
    }
}
//shape类中添加虚拟函数
 virtual std::string name()=0;
 //同时输出流也改变一下
 std:: ostream& operator <<(std :: ostream& out,const Shape & s )
 {
    return out <<"("<<s.name()<<","<<s.area<<","<<s.perimeter<<")"
 }
//修改虚拟函数以及各个子类实现的函数
virtual std::string name() const=0;
std:: string name() const override{
    return "Rectangle";
}
  • 我们再回到这堂课的最初出发点：selection sort，我们现在想要根据面积和周长分别进行排序，那这样我们需要添加一个selection_sort函数和find_min函数，因为此时我们的接口多了一个自定义的比较函数。
    1. 在这里需要注意的是我们的自定义的比较函数不能直接访问Shape类的成员变量，我们需要在Shape类中定义get函数。
    2. 其实当我们定义好get函数后，我们可以将Shape类中的freind修饰的输出函数删除，我们的输出函数可以通过调用get函数而不需要访问Shape类的成员变量。
  • 除了单独书写一个比较函数，我们还可以在主函数调用时直接在主函数中传入比较函数。
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
//扩充的选择排序
template<typename T,typename Compare>
int min_element(T arr[],int begin,int end,Compare comp)
{
    int min_idx=begin;
    for(int i=begin+1;i<end;i++)
    {
        if(comp(arr[i],arr[min_idx]))
          min_idx=i;
    }
    return min_idx;
}
template<typename T,typename Compare>
void selection_sort(T arr[],int n,Compare comp)
{
    for(int i=0;i<n;i++)
    {
        int min_idx=min_element(arr,i,n,comp);
        if(min_idx!=i)
          swap(arr[min_idx],arr[i]);
    }
}
//我们自定义的比较函数与修改的父类
class Shape{
protected:
  double area,perimeter;
public:
  virtual void calc_area()=0;
  virtual void calc_perimeter()=0;
  virtual std::string name() const=0;
  friend std:: ostream &operator <<(std::ostream& out,const Shape&);
  double get_area() const {return area;}
  double get_perimeter() const {return perimeter;}
};
bool less_shape_area(Shape * s1,Shape * s2)
{
   return s1->get_area()<s2->get_area();
}
//直接传入比较函数
selection_sort(arr,n,[](Shape* s1,Shape* s2){return s1->get_area()<s2->get_area();})

week 3

STL

What is STL

  • C++的标准模板库的一部分
  • 封装C++的数据结构与算法
  • 包含：
    1. 容器：class templates，common data structures
    2. 算法
    3. 迭代器：泛化的指针，在容器与算法间打交道

Why should I use STL

  • 节省时间与工作量
  • 增加程序可读性

Containers

  • 线性容器
    1. array(static),vector(dynamic)
    2. deque(double-ended queue)
    3. forward_list(signlely linked list),list(doubly linked list)
  • 关联性容器(本质上是用红黑树)
    1. set(collection of unique keys)
    2. map(collection of key-value pairs)
    3. multiset,multimap
  • Unordered associative
    1. hashed by keys
    2. unordered_set,unordered_map
    3. unordered_multiset,unordered_multimap
  • Adaptors
    1. stack
    2. queue
    3. priority_queue

vector example

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
#include <iostream>
#include <vector>
using namespace std;

int main()
{
   //初始化
   vector<int> evens {2,4,6,8};
   //push_back
   evens.push_back(20);
   evens.push_back(22);
   //insert,在指定位置插入5个10
   evens.insert(evens.begin()+4,5,10);
   //四种遍历方式,但是如果想要在指定范围内输出我们需要使用迭代器
   for (int i=0;i<evens.size();i++)
     cout << evens[i] <<" ";
    cout<< endl;
    for (vector<int> :: iterator it = evens.begin();it < evens.end();it++)
      cout << *it << " ";
    cout<< endl;
    for(auto it = evens.begin();it < evens.end();it++)
      cout << *it << " ";
    cout << endl;
    for(int e : evens)
      cout << e << " ";
    cout<< endl;
}

other containers

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
# include <iostream>
#include <string>
#include <list>
#include <map>
using namespace std;

int main()
{
    //list
    list <string> s;
    s.push_back("hello");
    s.push_back("world");
    s.push_back("stl");

    list <string>::iterator p;
    //需要注意的是我们遍历的时候用!=,因为我们的内存是分散的，比较迭代器的地址没有意义
    for(p=s.begin();p!=s.end();p++)
      cout << *p <<" ";
    cout << endl;

    //map
    map<string,int> price_list;
    price_list["apple"]=3;
    price_list["orange"]=5;
    price_list["banana"]=1;
    
    for (const auto & pair:price_list)
      cout<< "{" << pair.first<<":"<<pair.second<<"}"<<" ";
    cout<<endl;

    string item;
    double total=0;
    //如果输入的item在前面并不存在，我们会发现值会被悄悄插进map去且赋值为零
    /*while(cin>>item)
      total+=price_list[item];
      */
    //注意我们使用的contains在编译时要使用c++20
    while(cin>>item)
    {
        if(price_list.contains(item))
           total+=price_list[item];
        else
          cout<<"Mistake"<<endl;
    }
    cout << total <<endl;
    for (const auto & pair:price_list)
      cout<< "{" << pair.first<<":"<<pair.second<<"}"<<" ";
    cout<<endl;

    //再举一个例子
    map<string,int> word_map;
    for(const auto & w : {"we","are","not","humans","we","are","robots","!!!!"})
         word_map[w]++;
    for (const auto& [word,count]:word_map)
       cout << count <<" occurrence(s) of word"<<word<<endl;
   

}

Algorithms

  • works on a range defined as [first,last]
  • for_each,find,count
  • copy,fill,transform,replace,rotate
  • sort,partial_sort,nth_element
  • set_difference,set_union
  • min_element,max_element
  • accumulate,partial_sum

ex

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
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <list>
#include <vector>
#include "infix_iterator.h"
using namespace std;
int main()
{
    vector<int> v ={1,2,3,5};
    reverse(v.begin(),v.end());
    //但是此时u没有东西，程序不知道在哪里开始
    //我们想要在copy时自动插入，我们换一个迭代器
    vector<int> u;
   // copy(v.begin(),v.end(),u.begin());
   copy(v.begin(),v.end(),back_inserter(u));
   copy(u.begin(),u.end(),ostream_iterator<int>(cout,","));
   cout<<endl;

   list<int> l;
   //每次在头部插入，相当于又reversse了一次所以结果与最初相同
   copy(v.begin(),v.end(),front_inserter(l));
   copy(l.begin(),l.end(),ostream_iterator<int>(cout,","));
   cout<<endl;
   //要注意下面的初始化方式的含义是10个8
   vector <int> t(10,8);
   copy(v.begin(),v.end(),t.begin());
   copy(t.begin(),t.end(),ostream_iterator<int>(cout,","));
   //想要消掉最后的逗号,可以基于ostream_iterator自己实现一个迭代器
   copy(t.begin(),t.end(),infix_ostream_iterator<int>(cout,","));
   cout<<endl;
}

iterators

  • connect containers and algorithms
  • 后面的课会讲到

pitfalls

  • access safety

    1. accessing an element out of range
    2. use push_back() for dynamic expansion
    3. preallocate with constructor
    4. reallocate with resize()

  • silent insertion

    1. map<>中如果没有对应的pair，可能悄悄添加
    2. 通常用count() or contains()(基于c++20)来检查

  • size() on list<>

    1. my_list.size() might cost linear time before C++11
    2. Constant time guaranteed:my_list.empty()

  • invalid iterator

    1. using invalid iterator
    1
    2
    3
    4
    5
    6
    7
    list <int> L;
    list <int>:: iterator li;
    li=L.begin();
    L.erase(li);
    ++li;//wrong
    //我们需要重新调整
    li=L.erase(li);

week 4

memory model

what are these variables?

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
int i; //global vars
static int j; //static global vars

void f()
{
    int k; //local vars
    static int l; //static local vars

    int *p= malloc(sizeof(int)); //allocated vars
}
//一个例子
#include <cstdlib>
#include <iostream>
using namespace std;

int globalx=100;
//我们可以发现存放的区域的位置
//全局变量和静态变量放在一个区域
//局部变量放在一个区域
//动态分配的又在一个区域
int main()
{
    static int staticx=30;
    int localx=3;
    int *px=(int*)malloc(sizeof(int));
     cout<<"&globalx="<<&globalx<<endl;
     cout<<"&staticx="<<&staticx<<endl;
     cout<<"&localx="<<&localx<<endl;
     cout<<"&px="<<&px<<endl;
     cout<<"px="<<px<<endl;
}

分配位置

1

不同的变量介绍

  • 全局变量（global）
    1. vars defined outside any functions
    2. can be shared btw .cpp files
    3. extern（用其他模块的全局变量）
      3.1 extern is a declaration says there will be such a variable somewhere in the whole program
      3.2 “such a” means the type and the name of the variable
      3.3 global variable is a definition , the place for that variable
    4. static
      4.1 static global variable inhibits access from outside the .cpp file（只有在本模块使用）
      4.2 so as the static function
      4.3 static local variable keeps value between visits to the same function(存储与全局变量相同，并且第一次调用时初始化)

指针

1
2
string s ="hello";
string *ps = &s;
  • operators with pointers
    1. get address
    2. get the object
    3. call the function
  • two ways to access
    1. string s;
      1.1 s is the object itself
      1.2 at this line,object s is created and initialized
    2. string *ps;
      2.1 ps is a pointer to an object
      2.2 the object ps points to is not konwn yet

Reference

Defining references

  • references are a new data type in C++
  • type& refname =name;
    1. for ordinary variable definitions
    2. an initial value is required
  • type& refname;
    1. In parameter lists or member variables
    2. Binding defined by caller or constructor
1
2
3
char c;//a character
char* p = &c;//a pointer to a character
char& r =c;//a reference to a character

Rules of references

  • 引用变量创造时必须初始化
  • 初始化建立了binding，并且不能再重新和另一个变量绑定
1
2
void f (int& x);
f(y);//在函数被调用时初始化
  • 引用变量的本质就是给已经存在的变量多了个名字
  • non-const的reference不能绑定表达式
1
2
void func (int &);
func(i*3);//Wrong!!

Type restrictions

  • No references to references
  • No pointers to references,but reference to pointer is ok
1
2
int& * p;//illegal
void f(int*& p);//ok
  • No arrays of references

Dynamically allocated memory

Dynamic memory allocation

  • new expression
    new int;
    new Stash;
    new int[10];
  • delete expression
    delete p;
    delete [] p;
  • new与malloc的差异在于：new在动态分配内存的同时还通过构造函数初始化对象，我们下面的例子就说明了这点。
  • 同时对于数组的删除，我们可以发现删除的顺序是从后往前删除的。
    1. 注意对于数组的删除采取 delete [] p;但是如果我们写delete p，只能删除第一个元素。
  • new、delete和malloc、free不能混用。
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
#include <cstdlib>
#include <iostream>
using namespace std;
struct Student{
   int id; 
   //构造函数
   Student(){
    id = 0;
    cout <<"Student::Student()"<<endl;
   }
   //delete时会调用这个函数
   ~Student(){
    cout <<"Student::~Student()"<<endl;
   }
};
int main()
{
    int *pa= new int(1024);
    cout << *pa << endl;
    int *parr =new int[10];
    for(int i=0;i<10;i++)
      parr[i]=i;
    for(int i=0;i<10;i++)
      cout << parr[i] << endl;
      delete pa;
      delete [] parr;

      Student * psl=(Student*)malloc(sizeof(Student));
      cout <<"ps1->id = " <<psl->id <<endl;
      Student * psl2=new Student;
      cout <<"ps2->id = " <<psl2->id <<endl;
      free(psl);
      delete psl2;
}
  • 下面的例子告诉我们new出来的东西一定要及时删干净，否则迟早占用完内存。并且内存不能释放两次。
  • 还需要区分被释放的空间和零指针NULL没有任何关系。也就是说NULL也占据了动态空间的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdlib>
#include <iostream>
#include <thread>
using namespace std;

void f()
{
    int *p=new int[1000];
    p[0]=2024;
    p[1]=3;
    p[2]=22;

    cout <<"we are in f() "<<p <<endl;
}
int main()
{
    while(true)
    {
        f();
        this_thread::sleep_for(1s);
    }
}
本文作者：Lane
本文链接：https://lakerswillwin.github.io/2025/01/14/oop/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
cs课程