摘要：面向对象

防卫式头文件

在头文件前后加

#ifndef ALGORITHM_COMPETITION_TRAINING_GUARD_H
#define ALGORITHM_COMPETITION_TRAINING_GUARD_H

...
...
    
#endif //ALGORITHM_COMPETITION_TRAINING_GUARD_H

ALGORITHM_COMPETITION_TRAINING_GUARD_H名字随便取

类

类分两种
- 一种带指针，大多是需要写析构函数的
- 一种不带指针，一般(九成以上)是不用在类内写析构函数的

构造函数

高级的写法

赋值时，使用列表参数

class Complex {
private:
    double re, im;
public:
    Complex(double r = 0, double i = 0) : re(r), im(i) {

    }

};

上面写法等价于：

Complex(double r = 0, double i = 0) {
      re = r;
      im = i;
  }

两者的区别是第一种更加高效。

重载
1
2
3
4
5
6
7
8
9
class Complex {
private:
double re, im;
public:
Complex(double r, double i) : re(r), im(i) {
}

Complex() : re(0), im(0) {}//与上面冲突
};
- 由于带参的构造函数是有默认参数的，所以Complex() : re(0), im(0) {}会发生冲突。因为如果类外定义了一个Complex c1; 那么它会去找构造函数，发现两个构造函数都可以，就不知道要哪一个，所以报错
https://www.bilibili.com/video/BV1gb411g7pa?p=3
构造函数如果放在私有里面，则外面是无法创建对象调用的

const

对于不改变函数里面的数据的，加上const，好习惯

class Complex {
private:
    double re, im;
public:
    Complex(double r, double i) : re(r), im(i) {
    }
    double real() const{//不改变函数里面的数据
        return re;
    }
    double imag() const {//不改变函数里面的数据
        return im;
    }

};

比如在设计一个类时，有些方法是拿数据出来而不改变数据，就加上const
如果不加const，那么在类外用const Complex complex(2, 1);会报错

操作符重载

所有的成员函数都有this参数，只是没写出来
谁调用改成员函数，谁就是this
https://www.bilibili.com/video/BV1gb411g7pa?p=5

类外定义的，必定不用返回引用类型，因为函数调用已结束所有局部变量就消失了，所以返回的是值

inline Complex operator + (const Complex &x, const Complex &y) {
    return Complex(x.real() + y.real(), x.imag() + y.imag());
}

inline Complex operator+(const Complex &x, const double y) {
    return Complex(x.real() + y, x.imag());
}

inline Complex operator+(const double x, const Complex &y) {
    return Complex(y.real() + x, y.imag());
}

inline Complex operator+(const Complex &x) {
    return x;
}

inline Complex operator-(const Complex &x) {
    return Complex(-x.real(), -x.imag());
}

如果返回引用类型，说明得到的结果会放在一个已经存在的变量里面，如下是this

class Complex {
private:
    double re, im;
public:
    Complex(double r, double i) : re(r), im(i) {
    }

    Complex() {}

    double real() const {
        return re;
    }

    double imag() const {
        return im;
    }

    double fun(const Complex &c) {
        return c.re + c.im;
    }
    Complex& operator += (const Complex&);//声明

};

inline Complex& Complex::operator += (const Complex& complex) {
    this->re += complex.re;
    this->im += complex.im;
    return *this;//返回引用类型
}

输出<<重载见https://www.bilibili.com/video/BV1gb411g7pa?p=5

拷贝和析构

拷贝构造

构造函数的参数是该类的类型
拷贝赋值
如果类中有指针成员，那么一定要写拷贝构造和拷贝赋值，拷贝构造即深拷贝

不写的话是浅拷贝，会造成内存泄漏

class MakeString {
private:
    char *data1;
public:
    char *data;
    MakeString(const char *str);

    MakeString(const MakeString &str);//拷贝构造
    MakeString& operator=(const MakeString &str);//拷贝赋值

    ~MakeString();
};

inline MakeString::MakeString(const char *str) {
    if (str) {
        data = new char[strlen(str) + 1];
        strcpy(data, str);
    } else {//未指定初值
        data = new char[1];
        *data = '\0';
    }
}

//深拷贝
inline MakeString::MakeString(const MakeString &str) {
    data = new char[strlen(str.data) + 1];
    strcpy(data, str.data);
}

MakeString &MakeString::operator=(const MakeString &str) {
    if (this == &str) {//检测自我赋值，一定要写
        return *this;
    }
    delete[] data;
    data = new char[strlen(str.data) + 1];
    strcpy(data, str.data);
    return *this;
}

MakeString::~MakeString() {
    delete[] data;
}

//test MakeString
 MakeString *m1 = new MakeString("hello");
 MakeString m2("");
 MakeString m3("world");
 cout<<m3.data<<endl;
 cout<<m1->data<<endl;
 m2 = m3;
 cout<<m2.data<<endl;
 MakeString m4(m3);
 cout<<m4.data<<endl;

world
hello
world
world

Process finished with exit code 0

堆栈

只要用到array new，就一定要用array delete

Static

类内加了static的变量是所有类内成员函数共享的
静态函数和一般的成员函数的区别是：静态函数没有this指针
- 所以静态函数只能存取处理静态数据

定义了静态数据后，一定要在类外加一行，如下所示：

class Account {
public:
    static double rate;

    static void set_rate(const double &x) {
        rate = x;
    }
};

double Account::rate = 5.0;

int main() {

    Account account;
    cout<<Account::rate<<endl;
    account.set_rate(9);//Account::set_rate(9);
    cout<<Account::rate<<endl;
    
    return 0;
}

5
9

Process finished with exit code 0

静态变量可以通过对象或者类名调用

static https://www.bilibili.com/video/BV1gb411g7pa?p=10

模板类

class template类模板

template<typename T>
class People {
private:
    T a, b;
public:
    People(T a1, T b1) : a(a1), b(b1) {}

    T function(T a1, T b1) {
        return a1 * b1;
    }
};

int main() {
    People<int> people1(2, 3);
    People<double> people2(1.2, 3.4);
    
    return 0;
}

function template函数模板

//函数模板
template<class T>//或者template<typename T>
T &min(T &a1, T &b1) {
    return a1 < b1 ? a1 : b1;
}

int main(){
	int a = 9, b = 7;
    float c = 1, d = 3;
    cout << min(a, b) << endl;
    cout << min(c, d) << endl;
    return 0;
}

namespace

标准库的所有东西都放在namespace std里面
1
2
3
namespace std{
...
}

三种使用方式

第一种最常用

#include <iostream.h>
using namespace std;
int main()
{
	cin << ...;
	cout << ...;
	return 0;
}

#include <iostream.h>
using std::cout;
int main()
{
    std::cin << ...;
    cout << ...;
    return 0;
}

#include <iostream.h>
int main()
{
    std::cin << ;
    std::cout << ...;
    return 0;
}

几种关系

组合

一个类里面的数据类型是另一个类

class B{
    ...
};
template<class T>
class A{
  B <T> data;
};

构造顺序是由内到外，如上是先调用B的构造函数，再A的
析构顺序是由外到内

委托

class StringRep;
class String {
public:
    String();
    String(const char* s);
    String(const String& s);
    String &operator=(const String& s);
    ~String();
    . . . .
private:
    StringRep* rep; // pimpl
};

然后把具体的实现放在StringRep类里面

继承

先调用父类的构造函数，再子类的(构造由内到外)
先定义子类的析构函数，再父类的(析构由外到内)
父类的析构函数必须是virtual的//养成良好的编程习惯

继承搭配虚函数使用更好

class Shape {
public:
    virtual void draw( ) const = 0;//纯虚函数后面带const = 0，一定要重写
    virtual void error(const std::string& msg);//可以被重写
    int objectID( ) const;//不可被重写
    ...
};
class Rectangle: public Shape { ... };
class Ellipse: public Shape { ... };

如果是父类中想要子类被重写的函数，就加virtual

继承+组合

class A {
public:
    int age;

    A(int age1) : age(age1) {
        cout << "age birth is " << age << endl;
    }

    ~A() {
        cout << "over A class\n";
    }
};

class Dad {
private:
    string name;
public:
    Dad(string str) : name(str) {
        cout << "father is " << name << endl;
    }

    ~Dad() {
        cout << "over father\n";
    }
};

class Son : public Dad {
private:
    string name;
    A age;
public:
    Son(const string &str, const string &name1, const A &age1) : Dad(str), name(name1), age(age1) {
        cout << "son is " << name << endl;
    }

    ~Son() {
        cout << "over son\n";
    }
};

int main() {
    Son("Nick", "Tom", 20);
    return 0;
}

age birth is 20
father is Nick
son is Tom
over son
over A class
over father
over A class

Process finished with exit code 0

调用构造函数的顺序是：先A类，再父类，再子类
析构的顺序与构造相反

STL基础

string

输入输出字符串

#include <bits/stdc++.h>
using namespace std;

int main(){
//    string s = "12312hello world...";
    string s;
    getline(cin, s);//输入字符串
    cout<<s;
    return 0;
}

1
2
3

21314 hello woefsdcsd
21314 hello woefsdcsd
Process finished with exit code 0

字符串拼凑

#include <bits/stdc++.h>
using namespace std;

int main(){
//    string s = "12312hello world...";
    string s;
    s += "shda s";
    s += "shda s";
    s += '5';

    cout<<s;
    return 0;
}

1 2	shda sshda s5 Process finished with exit code 0

排序

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "1523525431873";
    sort(s.begin(), s.end());
    cout << s;
    return 0;
}

1 2	1122333455578 Process finished with exit code 0

s.begin(), s.end()是迭代器，可以看成是指针
如果要访问最后一个字符，应该是*(--s.end())

erase删除

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "1523525431873";
    s.erase(s.begin());
    s.erase(--s.end());
    cout << s;
    return 0;
}

1 2	52352543187 Process finished with exit code 0

substr取子串

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "1523525431873";
    s = s.substr(2, 3);//从索引为2开始取，往后取三个
    cout << s;
    s = "1523525431873";
    s = s.substr(6, -1);//从索引为6开始取，直到最后一个
    cout << endl << s;
    return 0;
}

1
2
3

235
5431873
Process finished with exit code 0

几种循环方式

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s = "1523525431873";
    for (int i = 0; i < s.length(); ++i)
        cout << s[i];

    cout << '\n';
    for (string::iterator iter = s.begin(); iter != s.end(); iter++)
        cout << *iter;
    
    cout << '\n';
    for (auto i : s)
        cout << i;


    cout << endl << s;
    return 0;
}

1523525431873
1523525431873
1523525431873
1523525431873
Process finished with exit code 0

vector

初始化、打印

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v(3, 1);//初始化3个1
    vector<int> v1(3);//初始化3个0
    vector<int> v2{1, 2, 3, 4, 5};//初始化5个数
    for (auto x:v)cout << x;
    cout << '\n';
    for (auto x:v1)cout << x;
    cout << '\n';
    for (auto x:v2)cout << x;
    cout << '\n';
    return 0;
}

111
000
12345

Process finished with exit code 0

取元素 []或者at()

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5};//初始化5个数
    //取某个元素
    cout<<v[2];//取索引为2 元素
    cout<<v.at(4);//取索引为4的元素
    return 0;
}

追加push_back

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5};//初始化5个数
    v.push_back(7);
    v.push_back(7);
    v.push_back(7);
    for (auto x:v) cout << x;
    return 0;
}

1 2	12345777 Process finished with exit code 0

resize重置大小，后面补0

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5};//初始化5个数
    v.push_back(7);
    v.push_back(7);
    v.push_back(7);
    for (auto x:v) cout << x;
    v.resize(20);//进行重置大小，后面补0
    cout<<endl;
    for (auto x:v) cout << x;
    return 0;
}

1
2
3

12345777
12345777000000000000
Process finished with exit code 0

erase删除，在vector中的复杂度为O(n)

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5};//初始化5个数
    v.push_back(7);
    v.push_back(7);
    v.push_back(7);
    for (auto x:v) cout << x;
    cout<<endl;
    //删除,在这里的复杂度为O(n)
    v.erase(v.begin());
    v.erase(--v.end());
    for (auto x:v) cout << x;

    return 0;
}

1
2
3

12345777
234577
Process finished with exit code 0

front(),back()

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5};//初始化5个数
    v.push_back(7);
    v.push_back(7);
    v.push_back(7);
    for (auto x:v) cout << x;
    cout << endl;
    //取元素
    cout << v.front() << ' ' << v.back() << endl;
    cout << *v.begin() << ' ' << *(--v.end()) << ' ' << v[v.size() - 1];
    return 0;
}

12345777
1 7
1 7 7
Process finished with exit code 0

排序sort

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> v{1, 55, 15, 4, 25};//初始化5个数
    v.push_back(7);
    v.push_back(7);
    v.push_back(7);
    for (auto x:v) cout << x << ' ';
    cout << endl;

    sort(v.begin(), v.end());
    for (auto x:v) cout << x << ' ';
    cout << endl;

    sort(v.rbegin(), v.rend());
    for (auto x:v) cout << x << ' ';
    cout << endl;

    return 0;
}

1 55 15 4 25 7 7 7
1 4 7 7 7 15 25 55
55 25 15 7 7 7 4 1

Process finished with exit code 0

从大到小还可以用
sort(v.begin(), v.end(), greater<>());

循环与string的类似
用的较多的是for (auto x:v) cout << x << ' ';

stack

初始化

一般刷算法题都直接这样写 stack<int> s;

如果不用<bits/stdc++.h>,那要用<stack>

#include <bits/stdc++.h>
using namespace std;
int main() {
    stack<int> s;
    cout << endl;
    return 0;
}

push, pop, top

#include <bits/stdc++.h>

using namespace std;

int main() {
    stack<int> s;
    s.push(2);
    s.push(1);
    s.push(3);
    cout << s.top();
    s.pop();
    cout << s.top();
    return 0;
}

push 入栈
pop出栈
top取栈顶
size取长度
cout << s.empty(); 是空就返回1，否则为0
十进制转二进制

#include <bits/stdc++.h>

using namespace std;

int tenToTwo(int decimal) {
    stack<int> s;
    int res = 0;
    while (decimal != 0) {
        s.push(decimal % 2);
        decimal /= 2;
    }
    while (!s.empty()) {
        res = res * 10 + s.top();
        s.pop();
    }
    return res;
}

int main() {
    cout << tenToTwo(11);
    return 0;
}

1 2	1011 Process finished with exit code 0

逆序输出句子单词

#include <bits/stdc++.h>
using namespace std;
int main() {
    stringstream ss;
    string str;
    getline(cin, str);
    ss << str;
    stack<string> s;
    while (ss >> str) {
        s.push(str);
    }
    while (!s.empty()) {
        cout << s.top();
        if (s.size() != 1) cout << ' ';
        s.pop();
    }
    return 0;
}

1
2
3

we are young man
man young are we
Process finished with exit code 0

字符串转化为数字

方法一

#include <bits/stdc++.h>
using namespace std;
int main() {
    stringstream ss;
    string str = "12455";
    //把字符串转换为数字
    ss << str;//先把“12345”流入ss
    int num;
    ss >> num;//再从ss流入整型num
    cout << num;
    return 0;
}

1 2	12455 Process finished with exit code 0

方法二

int main() {
    stringstream ss;
    string str = "12455";
    //把字符串转换为数字
    int num = stoi(str);
    cout << num;
    return 0;
}

1 2	12455 Process finished with exit code 0

数字转换为字符串

方法一

#include <bits/stdc++.h>
using namespace std;

int main() {
    stringstream ss;
    string str;
    //数字转化为字符串
    int num = 12556;
    ss << num;
    ss >> str;
    cout << str;
    return 0;
}

1 2	12556 Process finished with exit code 0

方法二

#include <bits/stdc++.h>
using namespace std;

int main() {
    stringstream ss;
    string str;
    //数字转化为字符串
    int num = 12556;
    str = to_string(num);
    cout << str;
    return 0;
}

queue

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    q.push(4);
    q.push(3);
    q.push(5);
    cout<<q.size()<<' '<<q.front();
    return 0;
}

3 4

map 和 unordered_map

map: 有序的，底层是树状结构

#include <bits/stdc++.h>

using namespace std;

int main() {
    map<int, int> dict;
    dict[1] = 2;
    dict[2] = 0;
    dict[4] = 12;
    //打印
    for (auto item: dict)
        cout << item.first << ' ' << item.second << endl;
    //另一种打印方式
    for (auto iterator = dict.begin(); iterator != dict.end(); iterator++)
        cout << iterator->first << ' ' << iterator->second << endl;
    return 0;
}

1 2
2 0
4 12
1 2
2 0
4 12

Process finished with exit code 0

unordered——map：无序的，底层是哈希结构

#include <bits/stdc++.h>

using namespace std;

int main() {
    unordered_map<int, int> dict;
    dict[1] = 2;
    dict[2] = 0;
    dict[4] = 12;
    //打印
    for (auto item: dict)
        cout << item.first << ' ' << item.second << endl;
    //另一种打印方式
    for (auto iterator = dict.begin(); iterator != dict.end(); iterator++)
        cout << iterator->first << ' ' << iterator->second << endl;
    return 0;
}

4 12
1 2
2 0
4 12
1 2
2 0
Process finished with exit code 0

打印出来是无序的
set

#include <bits/stdc++.h>

using namespace std;


int main() {
    unordered_set<int> s;
//    set<int> s;
    s.insert(2);
    s.insert(2);
    s.insert(3);

    cout << s.size();
    for (auto i:s)
        cout << i;
    return 0;
}

1 2	232 Process finished with exit code 0

deque

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> deque;
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(3);
    deque.push_front(4);
    for (auto i: deque)
        cout << i;
    deque.pop_back();
    deque.pop_front();
    cout<<endl;
    for (auto i: deque)
        cout << i;
    return 0;
}

1
2
3

4312
31
Process finished with exit code 0

可以排序

#include <bits/stdc++.h>

using namespace std;


int main() {
    deque<int> deque;
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(3);
    deque.push_front(4);
    for (auto i: deque)
        cout << i;
    sort(deque.begin(), deque.end());
    cout<<endl;
    for (auto i: deque)
        cout << i;
    return 0;
}

1
2
3

4312
1234
Process finished with exit code 0

list

#include <bits/stdc++.h>

using namespace std;


int main() {
    list<int> list;
    list.push_front(2);
    list.push_front(3);
    list.push_back(4);
    list.push_back(1);
    for (auto i: list)
        cout << i << ' ';
    cout << endl;
    //插入
    list.insert(++list.begin(), 99);
    for (auto i: list)
        cout << i << ' ';
    cout << endl;
    //里面的值
    list.remove(3);
    for (auto i: list)
        cout << i << ' ';
    return 0;
}

3 2 4 1
3 99 2 4 1
99 2 4 1
Process finished with exit code 0