学习笔记|STL

本文最后更新于:4 years ago

STL 是 C++ 的标准模版库,Standard Template Library。其中包含4个组件,分别为算法、容器、函数、迭代器。

一、函数模版

1.基本语法

编写代码时,可以忽略类型。

1
2
3
4
5
// template<class T>
template<typename T1, typename T2>
int MySwap(T1 &a, T2 &b){
//...
}
  • 可以定义多个虚拟类型,T1,T2…
  • 为了让编译器区分函数模版、普通函数,需要在函数模版前面写 template<class T>

2.自动类型推导和显式指定类型

调用函数模版时,函数模版自动推导类型和显式指定类型。

1
2
3
4
5
6
7
int main() {
int a = 0, b = 0;
// 自动类型推导
MySwap(a, b);
// 显式指定类型
MySwap<int>(a, b);
}

3.函数模版和普通函数的区别

  • 函数模版不提供隐式转换
  • 普通函数会进行隐式转换,

**情境一:**当普通函数和函数模版重载,优先 调用普通函数。

**情境二:**当需要发生隐式转换时,只能 调用普通函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
void Fun(T a, T b) {
cout << a << " <T, T> " << b << endl;
return;
}

void Fun(int a, int b) {
cout << a << " <int, int> " << b << endl;
return;
}

int main() {
int a = 97, b =98;
char c = 'a';
Fun(a, b); // <int, int> 存在满足要求的普通函数,优先调用普通函数。
Fun(c, a); // <char, int> 需要隐式转换的,必须调用普通函数。
return 0 ;
}

**情境三:**若要显式调用函数模版时,加 <>

1
Fun<>(a, b);

4.模版函数的实现原理

过程:

注意:

  • 编译器不能直接调用函数模版。编译器不是把函数模板处理成能够处理任意类的函数。
  • 编译器根据具体的函数类型,生成模版函数。
  • 编译器对函数模版进行两次编译:
    1. 在声明函数模版的地方,对函数模版本身进行编译。
    2. 在调用模版函数的地方,替换参数后,进行编译。

二、类模版

1.基本格式

  • 定义类时,要写 template<class T>
  • 实例化对象时,必须显式提供所泛化的具体类型。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class T>
class A {
public:
A(T id, T age){
this->id_ = id;
}
void Show(){
cout << "id = " << this->id_ << endl;
}

private:
T id_; // 类中成员变量可用 T 表示。
};

int main(){
A<char> a(97, 98); // 实例化对象时,必须显式提供所泛化的具体类型。
a.Show();
return 0;
}

2.类模版的派生

(1)模版类派生普通类

若派生类是普通类,需要显式提供基类的类型。

派生类从基类继承,需要让编译器知道,父类的数据类型具体是什么。(数据类型的本质:固定大小内存块的别名。)

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
template<class T>
class Animal {
public:
T age_;
Animal(T age){
this->age_ = age;
}
void Print(){
cout << "age = " << age_ << endl;
}
};

class Cat : public Animal<int>{ // 【显式地提供参数类型】
public:
Cat(int age) : Animal(age){ }
void Print(){
cout << "I am Cat!" << endl;
Animal::Print();
}
};

int main(){
Cat cat(10);
cat.Print();
return 0;
}

(2)模版类派生模版类

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
// 若子类是类模版,父类类型可以用 T 表示。
template<class T>
class Animal {
public:
T age_;
Animal(T age){
this->age_ = age;
}
void Print(){
cout << "age = " << age_ << endl;
}
};

template<class T> // 【派生类也需要写明 "template<class T> "】
class Cat : public Animal<T>{
public:
Cat(T age) : Animal<T>(age){ } // 【调用基类构造时,需要写明 泛型<T>】
void Print(){
cout << "I am Cat!" << endl;
Animal<T>::Print(); // 【使用类的限定符时,需要写明泛型<T>】
}
};

int main(){
Cat<int> cat(10);
cat.Print();
return 0;
}

3.类模版+友元函数

(1)类模版+普通/友元+类内定义

普通类+普通/友元 相比,没有什么特殊的,一切正常。

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
template <class T>
class Person {
public:
Person(string name, T age){
this->name_ = name;
this->age_ = age;
}
void Print(){ // 普通函数的类内定义
cout << "name = " << this->name_ << endl;
cout << "age = " << this->age_ << endl;
return;
}
friend ostream &operator<<(ostream &os, Person<T> &person){ // 友元函数的类内定义
os << "name = " << person.name_ << endl;
os << "age = " << person.age_ << endl;
return os;
}

public:
string name_;
T age_;
};

int main(){
Person<int> person_01("Tom", 13);
person_01.Print();
cout << person_01;
}

(2)类模版+普通函数+类外定义

类模版+普通函数+类外定义时,需要注意一下两点:

  1. 类外实现类成员函数时,需要写明 template <class T>

  2. 使用 类作用域符 时,需要写明泛型。

  • person.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#pragma once
#include <iostream>
#include <string>
using namespace std;

template <class T>
class Person {
public:
Person(string name, T age);
void Print();

public:
string name_;
T age_;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
#include "person.h"

template <class T> // 类成员函数,类外实现时,需要用 template <class T>
Person<T>::Person(string name, T age){ // 使用 类作用域符 时,需要写明泛型<T>
this->name_ = name;
this->age_ = age;
}

template <class T>
void Person<T>::Print(){
cout << "name = " << this->name_ << endl;
cout << "age = " << this->age_ << endl;
}
1
2
3
4
5
6
7
8
#include "person.h"

int main(){
Person p_01("Tom", 11);
p_01.Print();
return 0;
}

(3)分文件编程报错

按照 类模版+普通函数+类外定义 的方式,会报错如下,原因是无法正确链接文件。

1
2
3
4
5
6
7
Undefined symbols for architecture x86_64:
"Person<int>::Print()", referenced from:
_main in main-02af6c.o
"Person<int>::Person(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, int)", referenced from:
_main in main-02af6c.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

解决方案:

person.cc 改为 person.hpp ,并在 main.cc 中 引用 #include "person.hpp"

  • person.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#pragma once
#include <iostream>
#include <string>
using namespace std;

template <class T>
class Person {
public:
Person(string name, T age);
void Print();

public:
string name_;
T age_;
};
  • person.hpp

person.cc 改为 person.hpp 。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include "person.h"

template <class T> // 类成员函数,类外实现时,需要用 template <class T>
Person<T>::Person(string name, T age){ // 使用 类作用域符 时,需要写明泛型<T>
this->name_ = name;
this->age_ = age;
}

template <class T>
void Person<T>::Print(){
cout << "name = " << this->name_ << endl;
cout << "age = " << this->age_ << endl;
}
1
2
3
4
5
6
7
8
#include "person.hpp"   // 由 #include "person.h" 改为  #include "person.hpp"

int main(){
Person p_01("Tom", 11);
p_01.Print();
return 0;
}

(4)C++编译机制

**独立编译:**当分文件编程时,每个文件都是单独编译,生成若干个 .o 文件,并用链接器寻找相关文件,完成运行。

**二次编译:**类模版先编译一次,检测语法错误,分析语义,再根据实际的类型,生成模版函数,进行第二次编译。

**冲突:**独立编译后,才进行二次编译,所以链接器找不到类外定义的函数模版 所生成的 模版函数。容易发生的错误如下:

1
2
3
4
"operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Person<int>&)", referenced from:
_main in 友元+类模版+友元+重载左移动-c601b9.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

(5)类模版+友元函数+类外定义

第一种格式:二重模版

定义友元函数时,使用一个新的泛型 T2 表示。

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

template <class T>
class Person {
public:
Person(string name, T age);
void Print();
template<class T2> // 定义一个泛型 T2
friend ostream &operator<<(ostream &os, Person<T2> &person);

public:
string name_;
T age_;
};
  • person.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "person.h"

template <class T>
Person<T>::Person(string name, T age){
this->name_ = name;
this->age_ = age;
}

template <class T>
void Person<T>::Print(){
cout << "name = " << this->name_ << endl;
cout << "age = " << this->age_ << endl;
return;
}

template <class T2> // 函数实现时,也需要声明泛型 T2
ostream &operator<<(ostream &os, Person<T2> &person){
os << "name = " << person.name_ << endl;
os << "age = " << person.age_ << endl;
return os;
}
1
2
3
4
5
6
7
#include "person.hpp"

int main(){
Person<int> person_01("Tom", 13);
person_01.Print();
cout << person_01;
}
第二种格式:声明前置

在类的定义和友元函数的定义前面,加上二者的声明。

  • person.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 前置声明 类
template <class T>
class Person;

// 前置声明 友元函数
template <class T>
ostream &operator<<(ostream &os, Person<T> &person);

template <class T>
class Person {
public:
Person(string name, T age);
void Print();
// 在 函数名和参数列表之间 声明泛型 <T>
friend ostream &operator<< <T> (ostream &os, Person<T> &person);

public:
string name_;
T age_;
};
  • person.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "person.h"

template <class T>
Person<T>::Person(string name, T age){
this->name_ = name;
this->age_ = age;
}

template <class T>
void Person<T>::Print(){
cout << "name = " << this->name_ << endl;
cout << "age = " << this->age_ << endl;
return;
}

template <class T>
ostream &operator<<(ostream &os, Person<T> &person){ // 函数实现时,无需添加 泛型<T>
os << "name = " << person.name_ << endl;
os << "age = " << person.age_ << endl;
return os;
}
1
2
3
4
5
6
7
#include "person.hpp"

int main(){
Person<int> person_01("Tom", 13);
person_01.Print();
cout << person_01;
}

4.类模版+static成员

static 变量属于 实际的类,而不属于 类模版。

实际的类 由实际的 泛型 <T> 最后的值决定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class T>
class Person {
public:
static int a;
};

template<class T>
int Person<T>::a = 0; // 类外初始化 static 变量。

int main(){
Person<int> p1, p2; // 类模版为 int 的类,共用 static 变量。
Person<int> p3, p4;

Person<char> c1, c2; // 类模版为 char 的类,共用 static 变量。

p2.a = 10;
cout << p4.a; // 10
cout << c1.a; // 0
}

5.实例:MyArray

自定义一个数组的模版类。

  • <T> 对象元素必须能够被拷贝。
  • 容器都是值寓意,而非引用寓意,放入容器的元素,都是拷贝份。
  • 元素成员有指针,注意深拷贝。
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
template<class T>
class MyArray {
public:
MyArray(const int max_size);
MyArray(const MyArray<T> &another);
T &operator[](const int &index);
MyArray<T> &operator=(const MyArray<T> &another);
void Print();
void PushBack(const T &data); // 用 const 引用,来接收 变量、常量。
~MyArray();

public:
// 数组大小
int max_size_;
// 数组当前元素个数
int size_;
// 数组头指针
T *arr_ptr_;
};

template<class T>
MyArray<T>::MyArray(const int max_size){ // 使用 类作用域符 时,需要写 泛型<T>
this->max_size_ = max_size;
this->arr_ptr_ = new T[this->max_size_];
this->size_ = 0;
}

template<class T>
MyArray<T>::MyArray(const MyArray<T> &another){
//【拷贝构造】,不需要判断指针是否为空,【等号操作符】需要。
this->max_size_ = another.max_size_;
this->size_ = another.size_;
this->arr_ptr_ = new T[this->max_size_];
for (int i = 0; i < this->size_; i++) {
this->arr_ptr_[i] = another.arr_ptr_[i];
}
}

template<class T>
T &MyArray<T>::operator[](const int &index){
if (this->size_ <= index){
cout << "索引越界!" << endl;
return this->arr_ptr_[0];
}
return this->arr_ptr_[index];
}

template<class T>
MyArray<T> &MyArray<T>::operator=(const MyArray<T> &another){
// 【等号操作符】,需要先判断数组指针是否为空,而不是判断 size 大小。
//【拷贝构造】,不需要判断指针是否为空。
if (this->arr_ptr_ != nullptr) {
delete[] this->arr_ptr_;
this->arr_ptr_ = nullptr;
}
this->max_size_ = another.max_size_; // 类的三个成员变量 都需要考虑到,不要只拷贝数组。
this->size_ = another.size_;
this->arr_ptr_ = new T[this->max_size_];
for (int i = 0; i < this->size_; i++) {
this->arr_ptr_[i] = another.arr_ptr_[i];
}
return *this;
}

template<class T>
void MyArray<T>::Print(){
for (int i = 0; i < this->size_; i++) {
cout << this->arr_ptr_[i] << " ";
}
cout << endl;
return;
}

template<class T>
void MyArray<T>::PushBack(const T &data){
if (this->size_ == this->max_size_) {
cout << "数组已满!" << endl;
return;
}
this->arr_ptr_[this->size_] = data;
this->size_ ++;
return;
}

template<class T>
MyArray<T>::~MyArray(){
if (this->arr_ptr_ != nullptr) {
delete[] this->arr_ptr_;
this->arr_ptr_ = nullptr;
}
}

int main(){
MyArray<int> arr1(3), arr2(5);
arr1.PushBack(10);
arr1.PushBack(9);
arr1.PushBack(8);
arr1.PushBack(7);
arr1.PushBack(6);
arr2 = arr1;
MyArray<int> arr4 = arr2;
arr4.Print();
}

三、类型转换

static_cast内置的数据类型转换,以及具有继承关系的指针和引用的转换。【父类转换为子类时,不安全】不会进行安全检查。
dynamic_cast具有继承关系的指针和引用的转换。【只能从子类转换为父类转换之前,进行对象类型的安全检查
const_cas增加或去除 const 。
reinterpret_cast无关的指针类型的转换,或者函数指针之间的转换。

1.static_cast

static_cast<目的类型>(待转换变量)

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 a = 100;
char c = static_cast<char>(a);

// 基础数据类型指针【报错!】
// int *p1 = nullptr;
// char *p2 = static_cast<char *>(p1);

// 非继承关系的指针和引用【报错!】
// class ObjA {};
// class ObjB {};
// ObjA *p1 = nullptr;
// ObjB *p2 = static_cast<ObjB *>(p1);

// 具有继承关系的指针和引用
class ObjA {};
class ObjB : public ObjA {};
// 1.父类指针转化为子类指针
ObjA *p1 = nullptr;
ObjB *p2 = static_cast<ObjB *>(p1);
// 2.子类指针转化为父类指针
ObjB *p3 = nullptr;
ObjA *p4 = static_cast<ObjA *>(p3);
// 3.父类引用转化为子类引用
ObjA obj_a_1;
ObjA &obj_aaa_1 = obj_a_1;
ObjB &obj_bbb_1 = static_cast<ObjB &>(obj_aaa_1);
// 4.子类引用转化为父类引用
ObjB obj_b_2;
ObjB &obj_bbb_2 = obj_b_2;
ObjA &obj_aaa_2 = static_cast<ObjA &>(obj_bbb_2);

2.dynamic_cast

转换之前,进行对象类型的安全检查,所以只能从子类转换到父类。避免父类指针转化为子类指针,操作安全区域之外的内存。

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
// 基础数据类型【报错!】
// int a = 100;
// char c = dynamic_cast<char>(a);

// 非继承关系的指针和引用【报错!】
// class ObjA {};
// class ObjB {};
// ObjA *p1 = nullptr;
// ObjB *p2 = dynamic_cast<ObjB *>(p1);

// 具有继承关系的指针和引用
class ObjA {};
class ObjB : public ObjA {};
// 1.父类指针转化为子类指针【报错!】
// ObjA *p1 = nullptr;
// ObjB *p2 = dynamic_cast<ObjB *>(p1);
// 2.子类指针转化为父类指针
ObjB *p3 = nullptr;
ObjA *p4 = dynamic_cast<ObjA *>(p3);
// 3.父类引用转化为子类引用【报错!】
// ObjA obj_a_1;
// ObjA &obj_aa_1 = obj_a_1;
// ObjB &obj_bb_1 = dynamic_cast<ObjB &>(obj_aa_1);
// 4.子类引用转化为父类引用
ObjB obj_b_2;
ObjB &obj_bb_2 = obj_b_2;
ObjA &obj_aa_2 = dynamic_cast<ObjA &>(obj_bb_2);

3.const_cast

1
2
3
4
5
6
7
8
9
10
11
12
13
// 基础数据类型的引用
int a = 10;
const int &b = a;
int &c = const_cast<int &>(b);

// 普通指针类型
// 去 const
const int *p1 = nullptr;
int *p2 = const_cast<int *>(p1);
// 加 const
int *p3 = nullptr;
const int *p4 = const_cast<const int *>(p3);
const int *p5 = p3;

4.reinterpret_cast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef int (*FUN_P_1)(int);
typedef int (*FUN_P_2)(int, char);

int main(){
// 无关的指针类型
class ObjA {};
class ObjB {};
ObjA *p_a = nullptr;
ObjB *p_b = reinterpret_cast<ObjB *>(p_a);

// 函数指针的转换
FUN_P_1 fun01;
FUN_P_2 fun02 = reinterpret_cast<FUN_P_2>(fun01);
}

5.建议

  • 转换前应该知道,转换前后的类型是什么,后果是什么。(尤其是,指针转换前后,可操作的内存区域的变化)。

  • 不建议使用。

四、异常

1.异常的好处

在c语言中,我们使用函数返回值来表示异常。

例如以下程序:当发生异常(b 等于 0),返回 -1 表示错误。

1
2
3
4
5
6
double division(int a, int b){
if (b == 0) {
return -1; // 返回 -1 表示错误
}
return (double)a/b;
}
  • 函数返回值可以忽略;但异常不能忽略。如果程序出现异常,但未被捕获,程序就会终止。

  • 整型返回值没有任何语义;而异常可以包含语义(比如类名)。

  • 整型返回值没有上下文;而异常作为一个类,可以拥有自己的成员,传递足够完整的信息。

  • 对于函数的多级调用,使用整型返回值,需要每一级函数都进行处理;而异常是跨函数的,使用异常处理的栈展开机制,只需在其中一级函数中处理就可以。

2.基础语法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Division(int a, int b){
if (b == 0) {
throw b; // 抛出异常
}
return a / b;
}

int main(){
try { // 尝试捕获异常
Division(10, 0);
}
catch (int e) { // 捕获异常
cout << "除数为" << e << endl;
}
return 0;
}

3.跨函数 和 不可忽略

跨函数性

执行(入栈)顺序:main -> Fun01 -> Fun02 -> divison。

divison 抛出异常,Fun02 没处理,往顶层抛,抛给 Fun01,Fun01 处理异常。

不可忽略,必须处理

若在顶层也没有处理异常,程序就会终止。

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
int Division(int a, int b){         // 抛出异常
if (b == 0) {
throw b;
}
return a / b;
}

int Fun02(int a, int b){ // 没有处理异常
return Division(a, b);
}

int Fun01(){ // 处理异常
int res = 0;
try {
res = Fun02(10, 0);
}
catch (int e) {
cout << "除数为" << e << endl;
}
return res;
}

int main(){
Fun01();
return 0;
}

4.栈解旋(unwinding)

异常抛出后,从进入 try 块,到异常被抛出之前,此期间,栈上构造的所有对象,都会被自动析构。

跑异常的过程中,注意两个不执行:

  • throw 后的代码并不执行。
  • try中,抛出异常后的代码并不执行。
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
class Obj {
public:
Obj(const int &num){
this->num = num;
cout << num << " 正在构造.." << endl;
}
~Obj(){
cout << num << " 正在析构..." << endl;
}

public:
int num;
};

int Devision(int a, int b){
Obj obj_1(1); // 栈解旋
if (b == 0) {
throw b;
Obj obj_2(2); // throw 后的代码并不执行。
}
Obj obj_2_1(21);
return a / b;
}

int main(){
try {
Obj obj_3(3); // 栈解旋
Devision(10, 0); // 抛出异常
Obj obj_4(4); // try中,抛出异常后,代码并不执行。
}
catch (int e) {
cout << "捕获异常" << endl;
}
return 0;
}

5.异常接口的声明

  • 只能抛出 int, float, char 三种类型异常。
1
2
3
int Fun01() throw(int, float, char){
throw "abc"; // 抛出不是以上三种类型时,【程序报错】。
}
  • 不能抛出任何类型的异常
1
2
3
int Fun02() throw(){
throw -1; // 抛出了异常,【程序报错】。
}
  • 可以抛出所有类型异常
1
2
3
int Fun03() throw(){

}
  • 捕获多种类型的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(){
try {
Fun01();
}
catch (int e) { // 捕获 int,没捕获到继续执行
cout << e << endl;
}
catch (char e) { // 捕获 char,没捕获到继续执行
cout << e << endl;
}
catch (...) { // 省略号,可以捕获所有类型异常。
cout << “未知类型异常” << endl;
}
}

6.对象做异常类型

抛对象异常throw Exception("此处出现异象的原因是......");和捕捉对象异常catch (Exception e)的中间,有一个拷贝构构造存在。(如果 e 是引用,见 异常对象的生命周期

抛出的对象,不适用于 拷贝省略

所以,如果对象中有指向堆区的指针,类中要写清楚拷贝构造函数(深拷贝),不能使用默认的拷贝构造(浅拷贝)。浅拷贝导致两个指针指向一个堆区空间,析构时会产生错误。

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
// 异常类
class Exception {
public:
Exception(const char *str){
cout << "开始构造!" << endl;
this->error = new char[strlen(str) + 1];
strcpy(error, str);
}
// 必须写拷贝构造,不可以用默认拷贝构造(浅拷贝)
Exception(const Exception &e){
cout << "开始拷贝!" << endl;
this->error = new char[strlen(e.error) + 1];
strcpy(this->error, e.error);
}
void Show(){
cout << this->error << endl;
}
~Exception(){
if (this->error != nullptr) {
delete[] this->error;
this->error = nullptr;
cout << "开始析构!" << endl;
}
}
public:
char *error;
};

void Fun(){
throw Exception("此处出现异象的原因是......");
};

int main(){
try {
Fun();
}
catch (Exception e) { // 捕捉异常后,调用类中函数。
e.Show();
e.~Exception();
}
}

/*
开始构造! // throw Exception("此处出现异象的原因是......");
开始拷贝! // catch (Exception e)
此处出现异象的原因是...... // e.Show();
开始析构! // e.~Exception();
开始析构! // Exception().~Exception() // catch 处理完异常对象,析构。
*/

7.异常对象的生命周期

  • 普通类型

普通类型,异常对象,在 catch 大括号处理完之后,析构。

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 Exception {
public:
Exception(){ cout << "开始构造!" << endl; }
Exception(const Exception &e){ cout << "开始拷贝!" << endl; }
~Exception(){ cout << "开始析构!" << endl; }
};

void Fun(){
throw Exception();
};

int main(){
try {
Fun();
}
catch (Exception e /*【此处普通类型】*/) { // e 的生命周期:catch 大括号结束。
cout << "捕获异常" << endl;
}
}

/*
开始构造! // throw Exception();
开始拷贝! // catch (Exception e)
此处出现异象的原因是...... // cout << "捕获异常" << endl;
开始析构! // e.~Exception();
开始析构! // Exception().~Exception() // catch 处理完异常对象,析构。
*/
  • 引用

引用,不用调用拷贝构造,异常对象 catch 处理完之后,析构。

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 Exception {
public:
Exception(){ cout << "开始构造!" << endl; }
Exception(const Exception &e){ cout << "开始拷贝!" << endl; }
~Exception(){ cout << "开始析构!" << endl; }
};

void Fun(){
throw Exception();
};

int main(){
try {
Fun();
}
catch (Exception &e/*【此处引用】*/) { // e 的生命周期:catch 大括号结束。
cout << "捕获异常" << endl;
}
}

/*
开始构造! // throw Exception();
捕获异常 // cout << "捕获异常" << endl;
开始析构! // Exception().~Exception() // catch 处理完异常对象,析构。
*/
  • 指针

传递完指针,还未进入 catch 大括号,就会被立刻析构掉,但是异常类对象还在栈上(还可以调用函数,但是不能使用堆区空间)。

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
class Exception {
public:
Exception(){ cout << "开始构造!" << endl; }
Exception(const Exception &e){ cout << "开始拷贝!" << endl; }
~Exception(){ cout << "开始析构!" << endl; }
};

void Fun(){
Exception tmp;
throw &tmp;
};

int main(){
try {
Fun();
}
catch (Exception *e) {
cout << "捕获异常" << endl;
e->~Exception();
}
}

/*
开始构造! // Exception tmp;
开始析构! // catch (Exception *e); // 执行完 Exception *e,还没进入 catch 大括号,就被析构。
捕获异常 // cout << "捕获异常" << endl;
开始析构! // e->~Exception(); 析构堆区的空间,若无堆区空间,可多次析构。
*/

五、输入输出流

1.流的概念和流类库

键盘输入数据到程序:标准输入 input

程序输出到显示器:标准输出 output

标准输入 + 标准输出 = 标准I/O

文件的输入输出 = 文件I/O

cout:全局的流对象(ostream类),默认与屏幕关联。

cin:全局的流对象(istream类),默认与键盘关联。

cerr:标准错误,无缓冲区。

clog:标准日志,有缓冲区。

2.缓冲区

缓冲区:一块内存。

程序从输入缓冲区读数据,发现输入缓冲区没有数据,程序阻塞,等待键盘输入。

输出时,输出缓冲区满,或者刷新输出缓冲区,才可以输出到屏幕上。

**PS:**在 windos 下,cout << "hello world"; 会立即从缓冲区打印到屏幕上。

在 Linux 下,cout << "hello world"; 不会立刻打印在屏幕,而是输出到输出缓冲区。

cout << "hello world << endl;" 会立刻打印在屏幕上。endl 的作用:输出换行符,并刷新缓冲区。

用以下代码验证:(注意 “有endl的cout”,“有endl的cout” 的打印时间)

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

int main(){
cout << "请输入";
int a;
cin >> a;
cout << "有endl的cout" << endl; // 从缓冲区立即打印到屏幕。
cout << "没有endl的cout"; // 不会立即打印到屏幕,for循环运行结束才会打印。
for (int i = 0; i < 100000000; i++) {
int num = i + i - i;
}
cout << a;
return 0;
}

3.cin的特点

遇到 Tab、空格space、回车Enter时结束,并且空格换行符会留在缓冲区。

4.cin.get()

(1)无参数

从输入缓冲区读取一个字符,返回值为读取到的字符。

可以读空格、读回车。

1
2
3
while((ch = cin.get()) != EOF){  // 判断是否是结束
cout << ch << endl;
}

(2)一个参数

读取一个字符,给变量赋值。

可以读空格、读回车。

1
2
char ch;
cin.get(ch); // 参数为:字符变量

(3)两个参数

读取一个字符串,并给变量赋值。

字符串中可以包含空格,不可以包含回车。

遇到回车结束,并将回车键保留在缓冲区(和 cin 一样)。(所以不能连续使用 cin.get() )

注意最后有结束符,所以 cin.get(chars, 5); 最多只能读取 4 个字符。

1
2
3
4
5
char chars[10] = {0};
cin.get(chars, 5); // 参数为:字符串变量名, 获取字符串的长度为5

char* p = new char[10];
cin.get(p, 10); // 参数为:字符串首地址, 获取字符串的长度为10

5.cin.getline()

读取一行字符串。

字符串中可以包含空格,不可以包含回车。

重要】遇到回车结束,并删除该回车键,不在缓冲区保留。(和 cin、cin.get(buf, 10) 的区别)。

cin.getline(buf, 10); 减去字符串结束符,最多只能读取 9 个字符,若越界,后面其他的 cin语句 不会执行。

1
2
3
4
5
char ch;
char buf[5] = {0};
cin.getline(buf, 5); // 读取一个字符串。并去除回车键,以免下一行的 cin.get() 读到回车键。
cin.get(ch);
cout << "==" << ch << "==";

PS:遇到特定字符结束:

加入第三个参数,表示遇到该字符时,结束读取,并且该字符不在缓冲区保留。

1
2
3
4
char buf[5] = {0};
cin.getline(buf, 5, '9');
// 当输入 “19” 时,buf = “1”;
// ‘9’既不保存在 buf 中,也不保存在 缓冲区 中。

6.cin.ignore()

忽略缓冲区当前的字符。

比如 cin 之后,碰到空格结束,但是空格还在缓冲区,就可以使用 cin.ignore() 删除缓冲区当前字符。

1
2
3
4
5
char a[10], b;
cin.get(a, 10);
cin.ignore()
cin.get(b);
// 当输入 “xxx\ny” 时,变量 b 不是回车,而是 ‘y’,因为 ‘\n’ 被忽略了。

**PS:**无参数和有参数

1
2
3
4
5
6
7
8
// 表示忽略 1 个字符
cin.ignore();

//表示忽略 10 个字符
cin.ignore(10);

// 表示忽略 10 个字符,如果碰到 ‘\n’,停止忽略。
cin.ignore(10, '\n');

7.cin.peek()

看一看缓冲区的第一个字符,但是不取走。返回值为缓冲区的第一个字符。

1
char ch = cin.peek();

举个例子:实现功能:识别输入的是字符串还是数字。

1
2
3
4
5
6
7
8
9
10
char ch = cin.peek;              // 看一看缓冲区的第一个字符是什么。
if (ch >= '0' && ch <='9') { // 对第一个字符进行判断。
int number;
cin >> number; // 真正读取缓冲区数据。
cout << "输入的是数字:" << number << endl;
} else {
char buf[100];
cin >> buf; // 真正读取缓冲区数据。
cout << "输入的是字符串:" << buf << endl;
}

8.cin.putback()

把字符放回缓冲区。

1
2
char ch = ‘a’;
cin.putback(ch);

举个例子:实现和上面相同的功能:识别输入的是字符串还是数字。

1
2
3
4
5
6
7
8
9
10
11
char ch = cin.get();             // 读取缓冲区第一个字符。
cin.putback(ch); // 将第一个字符放回缓冲区。
if (ch >= '0' && ch <='9') { // 对第一个字符进行判断。
nt number;
cin >> number; // 读取缓冲区数据。
cout << "输入的是数字:" << number << endl;
} else {
char buf[100];
cin >> buf; // 读取缓冲区数据。
cout << "输入的是字符串:" << buf << endl;
}

9.getline()

cin.getline() 是 istream 类的成员函数,在头文件 <istream> 中。

getline() 是普通函数,在头文件 <string> 中。

区别在于 getline() 可以读取 string 字符串。

先看一下函数声明:

1
2
3
4
5
6
7
8
// 类的成员函数
istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

// 普通函数(需要将类对象传递进去)
istream& getline (istream& is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream& is, string& str);

与 cin.getline() 一样,可以读取空格,不可以读取回车。

1
2
string s;
getline(cin, s);

10.cout.flush()

刷新缓冲区

如果缓冲区没满,或者程序没有结束,cout 是不会输出的,必须刷新缓冲区才可以。

1
2
cout.flush();
// 类似的函数:int fflush(FILE *stream);

11.cout.put()

向 输出缓冲区 写入一个字符。

1
2
3
4
5
char c = 'c';
cout.put(c);

// 支持链式编程
cout.put(c).put(c).put(c) << endl;

12.cout.write()

按长度向 输出缓冲区 写入字符串。

第一个参数为字符串地址,第二个参数为输出字符的个数(不算结束符’\0’)

1
2
3
char s[] = "abcdef";
cout.write(s, strlen(s)) << endl;
cout.write(s, 3) << endl;

13.cout.width()、cout.fill()、cout.setf()

输出格式控制

通过成员方法的方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int number = 10;

// 控制进制
cout.unsetf(ios::dec); // 卸载当前默认的 10 进制输出方式。
cout.setf(ios::oct); // 设置成八进制输出
cout.setf(ios::showbase); // 显示八进制数字前的0,十六进制数字前的0x
cout << number << endl; // 此时,打印为:012

// 控制宽度
cout.width(5); // 设置为宽度为 5
cout.fill('*'); // 默认右对齐,多余的位置使用 * 填充
cout << number << endl; // 此时,打印为:**012

// 设置左对齐
cout.setf(ios::left); // 设置左对齐
cout << number << endl; // 此时,打印为:012**

通过控制符的方式:

需要引入头文件 #include <iomanip>

1
2
3
4
5
6
7
8
int number = 10;
cout << oct //八进制输出
<< setiosflags(ios::showbase) // 显示八进制数字前的0,十六进制数字前的0x
<< setw(5) // 设置为宽度为 5
<< setfill('*') // 多余的位置使用 * 填充
<< setiosflags(ios::left) // 设置左对齐
<< number
<< endl;

六、文件操作

继承关系:

  • iostream 多继承于 istream 和 ostream。
  • fstream 继承于 iostream。
graph TD
A(istream) --> B(ifstream) 
A --> E(iostream)
C(ostream) --> E
C --> D(ofstream)
E --> F(fstream)

1.文本文件

(1)文件读写的头文件

1
#include <fstream>

(2)打开文件

通过 ifstream 类的构造函数打开文件。

1
2
3
4
5
string source_file_name = "/test_source/STL/todo.txt";   // 文件路径。
ifstream ism(source_file_name, ios::in); // 只读的方式打开。

string target_file_name = "/test_source/STL/todo_copy.txt";
ofstream osm(target_file_name, ios::out | ios::app);

通过 ifstream 类的成员函数打开文件。

1
2
ifstream osm;
osm.open(source_file_name, ios::in);

标志含义:

标志含义
ios::app所有写入的字符追加在文件末尾。
ios::in只读的方式打开。
ios::out写入的方式打开。
ios::trunc如果文件存在,清空文件。
ios::binary二进制的方式打开。

可以多个标志结合使用:

1
2
// 写入的方式打开,并将写入的内容追加在文件末尾。
osm.open(target_file_name, ios::out | ios:: app);

(3)判断是否为空

fstream 重载了 ! 符号。

1
2
3
if (!ism || !osm) {
cout << "文件打开失败!" << endl;
}

(4)读写文件

因为 fstream 是多继承于 iostream 的,所以 cin、cout 的成员函数:get(),getline(),ignore() 等等都可以使用。

1
2
3
4
5
6
// 读文件 & 写文件
char ch;
while(ism.get(ch)) {
cout << ch;
osm.put(ch);
}

(5)关闭文件

依旧是类的成员函数。

1
2
ism.close();
osm.close();

实例:拷贝文件

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 <fstream>

int main() {

// 打开读文件
string source_file_name = "/test_source/STL/todo.txt";
ifstream ism(source_file_name, ios::in);
// ifstream ism;
// ism.open(source_file_name, ios::in);

// 打开写文件
string target_file_name = "/test_source/STL/todo_copy.txt";
ofstream osm(target_file_name, ios::out | ios::app);

if (!ism || !osm) {
cout << "文件打开失败!" << endl;
}

// 读文件 & 写文件
char ch;
while(ism.get(ch)) {
cout << ch;
osm.put(ch);
}


// 关闭文件
ism.close();
osm.close();

return 0;
}

2.二进制文件

与文本文件不一样的地方是:打开文件的时候,使用 ios::binary 标签。

1
ofstream osm(target_file_name, ios::out | ios::binary);

实例:对象序列化

对象序列化:以流的形式,将对象保存到磁盘文件中。

值得注意的地方,写文件时,对对象取地址,并强转为 char* 类型。

1
osm.write((char*)&p1, sizeof(Person));

完整如下:

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

class Person {
public:
Person(int age, int id) : age(age), id(id){}
void Show() {
cout << "age = " << age << endl;
cout << "id = " << id << endl;
}
private:
int age;
int id;
};

int main(){

// 创建类对象
Person p1(10, 20), p2(30, 40);

// 1.打开文件
string target_file_name = "/Users/STL/todo";
ofstream osm(target_file_name, ios::out | ios::binary); // 二进制的方式打开。

// 2.检查是否打开
if (!osm) {
cout << "打开文件失败" << endl;
}

// 3.写文件
osm.write((char*)&p1, sizeof(Person)); // 【取地址后强转为 char*】
osm.write((char*)&p2, sizeof(Person));

// 4.关闭文件
osm.close();

return 0;
}

实例:对象反序列化

值得注意的是,读文件时,对对象取地址,并强转为 char* 类型。

1
ism.read((char*)&p1, sizeof(Person));

完整如下:

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

class Person {
public:
Person(int age, int id) : age(age), id(id){}
Person(){}
void Show() {
cout << "age = " << age << endl;
cout << "id = " << id << endl;
}
private:
int age;
int id;
};

int main(){

// 创建类对象
Person p1, p2;

// 1.打开文件
string target_file_name = "/Users/STL/todo";
ifstream ism(target_file_name, ios::in);

// 2.检查是否打开
if (!ism) {
cout << "打开文件失败" << endl;
}

// 3.读文件
ism.read((char*)&p1, sizeof(Person));
ism.read((char*)&p2, sizeof(Person));

// 4.关闭文件
ism.close();

p1.Show();
p2.Show();

return 0;
}

七、STL 概述

STL(Standard Template Library,标准模版库)

STL分为:容器(container)算法(algorithm)迭代器(iterator)

1.容器(container)

序列式容器:容器元素的位置,由进入的时机决定。比如 vector。

关联性容器:容器已有规则,与进入的时机有关。比如 set、map。

补充:size() 返回值是 unsigned int,不可以和 负数 比较。

解决办法:提前将 size() 存入变量。

1
2
3
4
5
6
string s = "123";
int a = -1;
while (a < s.size()) {
// 无法进入循环体内。
// 因为 size() 是 unsigned int,和 负数 a 比较,编译器会将 a 强制转换为 unsigned int。
}

2.迭代器(iterator)

迭代器类似于指针,实际上迭代器是一个类,类中封装了指针,并重载了 ++、–、* 等等操作符。

其中 begin() 指向首地址,end() 指向 最后一个元素的下一个地址。【但迭代器 如begin() 不等于地址】

(1)为什么使用迭代器

迭代器是容器和算法之间的桥梁。实现算法时,传递的是容器的迭代器。

(2)迭代器类型

迭代器类型(以 vector 为例):vector<int>::iterator

1
vector<int>::iterator p_begin = a.begin();

(3)容器算法分离案例

为了使容器和算法互相独立。

实现功能:统计数组中出现某元素个数。

基本思路:容器为数组,迭代器分别指向数组的首部和尾部,将迭代器传入算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 算法
int MyCount(int* p_begin, int* p_end, int num) { // 传入迭代器
int count = 0;
for (int* p = p_begin; p!= p_end; p++) {
if (*p == num) {
count++;
}
}
return count;
}

int main() {
// 容器
int arr[] = {1, 2, 2, 3, 4, 2};

// 迭代器
int *p_begin = &arr[0];
int *p_end = &arr[sizeof(arr) / sizeof(int)];

cout << MyCount(p_begin, p_end, 2);
return 0;
}

3.算法(algorithm)

注意头文件 #include <algorithm>

(1)for_ench()

第一个是 begin(),第二个是 end(),第三个是 回调函数,比如 Print() 打印数据。

1
2
// 函数声明
for_each(_InputIterator __first, _InputIterator __last, _Function __f);
1
2
3
4
5
6
7
8
9
10
void Print(int val) {
cout << val;
return;
}

int main(){
vector<int> a(5);
for_each(a.begin(), a.end(), Print);
return 0;
}

类似功能实现遍历(以类对象为例):

<> 中是什么,*it 就代表什么。比如,vector<Person>*it 表示 Person 类对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Person {
public:
int age;
int id;
Person(int age, int id) : age(age), id(id) {}
};


int main(){
vector<Person> v;
Person p1(10, 20), p2(30, 40);
v.push_back(p1);
v.push_back(p2);
for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
cout << (*it).age << endl;
}
return 0;
}

八、string

1.特性

  • char* 是指针,string 是类,并在类中封装了 char* ,string 是一个 char* 型容器。
  • 封装了成员方法:查找find、拷贝copy、删除delete、替换replace、插入inset。
  • 不用考虑内存释放和越界问题(string 类负责维护)。

2.初始化

1
2
3
4
5
6
7
8
9
10
11
// 无参构造
string s1;

// 有参构造
string s2(3, 'a'); // s2 == "aaa" // 这里需要传入长度,函数原型:string (size_t n, char c);
string s3("abc");

// 拷贝构造。
string s4(s3);
string s5 = s3;
string s6 = "abc";

3.赋值

1
2
3
4
5
6
7
8
9
string s1("ab"), s2("cd");

// 等号操作符
s1 = "abc";
s1 = s2;
s1 = 'a';

// assign 成员函数
s1.assign("abc");

4.取值

[] at() 区别:如果索引越界,[] 直接报错,at() 抛异常 out_of_range。

1
2
3
4
5
6
7
string s1 = "abcd";

// 重载 [] 操作符
s1[0] = '0';

// at 成员函数
s1.at(0) = '0';

5.拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 重载 += 操作符
string& operator+=(const string& str);
string& operator+=(const char* str);
string& operator+=(const char c);

// 重载 + 操作符
string operator+(const string& str);

// append 成员函数
string& append(const char* str); // 字符串 str 连接到当前字符串结尾。
string& append(const string &str);

// 参数 n 限定。
string& append(const char* str, int n); // 字符串 str 前 n 个字符连接到当前字符串结尾。
string& append(const string &str, int pos, int n); // 从 pos 开始的 n 个字符连接在当前字符串尾部。
string& append(int n, char c); // 在当前字符串结尾添加 n 个字符 c。

6.查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 从 pos 位置开始,查找字符串 str,返回第一次出现的位置。
int find(const string& str, int pos = 0) const;
int find(const char* str, int pos = 0) const;

// 从 pos 位置开始,查找字符 c,返回第一次出现的位置。
int find(const char c, int pos = 0) const;

// 从 pos 位置开始,查找字符串 str,返回最后一次出现的位置。
// 如果没有找到,返回 npos。(npos是一个很大的数18446744073709551615UL,如果传递给int变量,= -1)
int rfind(const string& str, int pos = npos);
int rfind(const char* str, int pos = npos);

// 从 pos 位置开始,查找字符 c,返回最后一次出现的位置。
int rfind(const char c, int pos = 0);

例子:

1
2
3
4
5
6
7
string s = "abcfghfg";

// 查找第一个出现的位置
int frist = s.find("fg");

// 查找最后一个出现的位置
int last = s.rfind("fg");

7.替换

1
2
3
// 从 pos 位置开始的 n 个字符,替换为字符串 str。(被替换的字符,包括 pos 位置字符)
string& replace(int pos, int n, const string& str);
string& replace(int pos, int n, const char* str);

例子:

1
2
3
string s = "abccc";
s.replace(0,2,"xyz===");
cout << s; // xyz===ccc

8.比较

compare 函数,比较 ascii 码,(大写A比小写a小。A:65,a:97)

  • 对象 > s 时返回 对象-s的值(正值);
  • 对象 < s 时返回 对象-s的值(负值);
  • 对象 = s 时返回 0;
1
2
3
// 与字符串 s 比较大小。
int compare(const string& s) const;
int compare(const string& s) const;

例子:

1
2
string s1 = "abc", s2 = "aB";
cout << s1.compare(s2); // 32(‘b’ - 'B' 的值)

9.截取

1
2
// 返回由 pos 开始的 n 个字符组成的字符串。
string substr(int pos = 0, int n = npos) const;

例子:

1
2
3
string s = “abcd”
cout << s.substr(1); // "bcd"
cout << s.substr(2, 2) // "bd"

10.插入

【注意】

  • pos 位置可以用 整型 表示,并函数返回值为 字符串本身。
  • pos 位置可以用 迭代器 表示,并返回插入后迭代器的位置 或 无返回值。(不返回字符串本身,所以不能直接打印。)
  • (vector、string 的迭代器可以加整型数字;list 的迭代器只能自加。(因为 list 不支持随机访问))
1
2
3
4
5
6
7
8
9
10
11
// 从 pos 位置开始,插入字符串 s。(原第 pos 位置字符的前面)
string& insert(int pos, const char* s);
string& insert(int pos, const string& s);

// 在 pos 位置处,插入 n 个字符 c。
string& insert(int pos, int n, char c);

// 用迭代器表示位置。————————————————————————————————————————————————————————
iterator insert(iterator it, char c);//在it处插入字符c,返回插入后迭代器的位置
void insert(iterator it, const_iterator first, const_iteratorlast);//在it处插入从first开始至last-1的所有字符
void insert(iterator it, int n, char c);//在it处插入n个字符c

例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string s = "abcde";
char p[] = "==gg==";
cout << s.insert(3, p); // abc==gg==de
cout << s.insert(3, 5, '+'); // abc+++++==gg==de

//用迭代器表示位置。————————————————————————————————————————————————————————
// 从第 3 位开始插入 ‘A’(有第 0 位)
s.insert(s.begin()+3, 'A'); // 等同于 s.insert(3, 1, 'A');

// 从第 3 位开始插入 10 个‘A’(有第 0 位)
s.insert(s.begin()+3, 10, 'A'); // 等同于 s.insert(3, 10, 'A');

// 插入区间 [ s.begin()+1, s.end() ) 一段字符串。
s.insert(s.begin()+3, s.begin()+1, s.end());

11.删除

1
2
// 删除从 pos 开始的 n 个字符。
string& erase(int pos, int n = npos);

例子:

1
2
3
string s = "abcde";
cout << s.erase(1, 2); // 从 1 号元素开始,删除两个元素。 // ade
cout << s.earse(1); // 从 1 号元素开始,删到末尾。 // a

12.string 转 char*

接收的变量类型不能是 char * ,而是 const char* ,因为 c_str 返回的是 const char *。不能用安全性低的变量接受安全性高的数据。

1
2
3
string s = "hello";
const char* s_ptr = s.c_str();
cout << s_ptr << endl; // hello

13.char 转 string

1
2
3
4
5
char c = 'a';
string s1(1, c);
string s3(3, c);
cout << s1 << endl; // "a" // char 转 string
cout << s3 << endl; // "aaa"

九、vector

动态数组,单口容器。

1.动态增长原理与特性

当插入新元素时,若空间不足,

  1. 则重新申请更大的内存(两倍空间),
  2. 将原空间数据拷贝到新空间,
  3. 释放旧空间的数据,
  4. 再把新元素插入新空间中。

【注意:】将原空间数据拷贝到新空间时,会调用拷贝构造函数。

特性:

  • 指定位置插入效率低,最坏情况要移动整个数组,时间复杂度 O(n)。
  • 随机读取效率高,O(1)。

2.初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 无参构造函数
vector<int> v1;

// 有参构造
vector<int> v2(v1.begin(), v1.end()); //用迭代器初始化。
vector<int> v3(5, 1); // 五个元素,都为 1。
vector<int> v4(5); // 五个元素,都为 0。

// 拷贝构造
vector<int> v5(v2);

// 用数组初始化
int arr[] = {1, 2, 3};
vector<int> v6(arr, arr + sizeof(arr) / sizeof(int)); // 类似于 begin() 和 end()。

3.赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> v1(5, 0);
vector<int> v2;

// 迭代器赋值
v2.assign(v1.begin(), v1.end());

// 用数组(类似于迭代器)
int arr[] = {1, 2, 3, 4, 5};
v2.assign(arr, arr + sizeof(arr) / sizeof(int));

// 赋值 n 个 num
v2.assign(5, 0);

// 重载 = 操作符
v2 = v1;

//交换整个容器
v2.swap(v1); // v1变为v2,v2变为v1。

4.swap 函数交换原理

栈区有两个 vector 类对象,类成员变量中有一个指针,指向堆区的一块内存。

swap 函数,并非交换所有数据,只是交换指针。

对象地址为:&v;数据地址为:&(v[0]).

5.大小操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> v;

// 容器大小
v.size();

// 改变容器大小
// 若 n 比原来大,用 elem 填充新增的空间,无 elem 默认用 0 填充。
// 若 n 比原来小,删除愿容器中多余的数据。
v.resize(int n, elem); // 【只能改变大小,不能改变容量。】

// 容器是否为空
v.empty(); // 空返回 true,不空返回 false
if (v.empty()) {
cout << "v 为空!";
}

// 容器的容量 // 只有string 和 vector 有 capacity 属性
v.capacity(); // 增加空间要拷贝内存,耗时,所以最好一开始申请足够的容量。

6.取值

1
2
3
4
5
6
7
8
9
10
11
12
13
vector v;

// 抛异常
v.at(0) = 0;

// 不抛异常,重载 [] 操作符
v[0] = 0;

// 返回容器第一个元素
v.front();

// 返回容器最后一个元素
v.back();

7.插入删除

【注意】:vector 的 insert函数 pos 位置,只能用 迭代器,(vector、string 的迭代器可以加整型数字;list 的迭代器只能自加。(因为 list 不支持随机访问))

1
2
3
4
5
6
// 样例:
int a = 3;
v.insert(v.begin() + a, 5, 0);

// v.insert(a, 5, 0); // error
// v.insert(2, 5, 0); // error
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector v;
// 在 pos 位置插入 1 个元素 0。
v.insert(v.begin(), 0);

// 在 pos 位置插入 5 个元素 0。
v.insert(v.begin(), 5, 0);

// 在尾部插入 1;
v.push_back(1);

// 在尾部删除 1;
v.pop_back();

// 删除迭代器指向的元素
v.erase(const_iterator pos);

// 删除从迭代器 start 到 end 之间的元素。
v.erase(const_iterator start, const_iterator end); //【左闭右开】

// 清空容器
v.clear();

8.用 swap 收缩空间

用 v 初始化匿名对象(按照 size 的大小初始化,而非 capacity ),并交换 匿名对象 和 v。

1
vector<int>(v).swap(v);

例如下面程序,虽然 size 是 10w,但是 capacity 是 13w。因为在扩大空间时,是默认按照两倍空间扩增的。

1
2
3
4
5
6
7
8
9
10
vector<int> a;
for (int i = 0; i < 100000; i++) {
a.push_back(i);
}

cout << "a.size() = " << a.size() << endl; // a.size() = 100000
cout << "a.capacity() = " << a.capacity() << endl; // a.capacity() = 131072

// 当想要将 容量capacity 缩小成和 大小size 一致时,
vector<int>(a).swap(a);

9.reserve 预留空间

reserve 和 resize 区别:

  • reserve 是预留空间,不是创建真正的元素对象,未添加对象之前,不能引用容器内元素。
  • resize 是改变容器大小 size(不改变 容量capacity ),调用此函数后,能引用容器内元素。
1
2
vector<int> v;
v.reserve(100000);

预留空间的作用: 减少容器扩容时的拷贝。

计算拷贝次数:

  • 注意:&v 不是 数据的地址,是栈中 v 对象的地址;而数据储存在堆区,可用 &(v[0]) 表示。
  • 迭代器不是地址,是一个类对象,无法直接和地址比较。
1
2
3
4
5
6
7
8
9
10
11
12
// 方法一:判断 v.begin() 的值是否改变。
vector<int> v;
int count = 0;
vector<int>::iterator address = v.begin();
for (int i = 0; i < 100000; i++) {
v.push_back(i);
if (v.begin() != address) {
address = v.begin();
count++;
}
}
cout << count << endl; // 18次
1
2
3
4
5
6
7
8
9
10
11
12
// 方法二:判断 v[0] 的地址是否改变。
vector<int> v;
int count = 0;
int* address = nullptr;
for (int i = 0 ;i < 100000; i++) {
v.push_back(i);
if (address != &(v[0])) {
address = &(v[0]);
count++;
}
}
cout << count << endl; // 18次

若加入 v.reserve(100000) 则一次也不需要拷贝。

十、deque

double-ended queue 双端队列,(更像 双端 vector).

deque:[/'di:ke/] queue:[/kju/]

分片存储原理:

  • 左边是一个 map 数组,节点中保存的是 右边缓冲区内存片段 的地址。
  • 右边是缓冲区,有若干连续的内存片段,片段之间不连续,片段内部连续。

1.特性:

  • 双端插入和删除元素效率高。
  • 指定位置插入会导致数据元素移动,效率低。
  • 随机存取效率高。
  • 分块储存,排序效率非常低,【deque 特有的特点】。所以可以拷到 vector 容器中排序再拷回 deque容器。

**总结:**与其说是双端队列,不如说是 双端vector,特性基本相同,API基本相同(差别在于:deque 可以双端插入和删除,vector 只能一端插入删除)。

2.初始化

API 和 vector 相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 无参构造
deque<int> q1;

// 有参构造
deque<int> q2(q1.begin(), q2.end());
deque<int> q3(5, 1); // 初始化为 5 个 1;
deque<int> q4(5); // 初始化为 5 个 0;

// 数组初始化
int arr[] = {1, 4, 3, 6, 3};
deque<int> q6(arr, arr + sizeof(arr)/sizeof(int));

//拷贝构造
deque<int> q5(q1); // deque<int> q4(const deque &deq);

3.赋值

API 和 vector 相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
deque<int> q1, q2(10, 1);

// 迭代器赋值
q1.assign(q2.begin(), q2.end());

// 用数组(类似于迭代器)
int arr[] = {1, 2, 3, 4};
q1.assign(arr, arr + sizeof(arr) / sizeof(arr[0]));

// 赋值 n 个 num
q1.assign(10, 2);

// 重载 = 操作符
q1 = q2;

// swap 函数交换
q1.swap(q2);

4.大小操作

  • API 和 vector 相同。

  • 唯一不同:deque 没有 容量capacity 属性(只有string 和 vector 有 capacity 属性)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
deque<int> q(10, 2);

// 返回元素个数
q.size();

// 改变容器大小
// 若 n 比原来大,用 elem 填充新增的空间,无 elem 默认用 0 填充。
// 若 n 比原来小,删除愿容器中多余的数据。
q.resize(int n, elem);

// 容器是否为空
q.empty(); // 空返回 true,不空返回 false
if (q.empty()) {
cout << "q 为空!";
}

5.双端插入删除

1
2
3
4
5
6
7
8
deque<int> q;
// 从后面操作
q.push_back(1);
q.pop_back(1);

// 从前面操作
q.push_front(1);
q.pop_front(1);

6.取值

API 和 vector 相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
deque<int> q(10, 5);

// 抛异常
q.at(0) = 0;

// 不抛异常,重载 [] 操作符
q[0] = 0;

// 返回容器第一个元素
q.front();

// 返回容器最后一个元素
q.back();

十一、stack

1.特性

  • 不能遍历,不能随机读取;只能通过 栈顶元素 访问或删除。
  • 不提供迭代器(意味着 不能遍历)。

2.初始化

1
2
3
4
5
// 默认构造
stack<int> stk;

// 拷贝构造
stack<int> stk(const stack<int> &stk);

3.赋值

1
2
3
4
stack<int> stk1, stk2;

// 重载 = 操作符
stk1 = stk2;

4.大小操作

1
2
3
4
5
6
7
stack<int> stk;

// 元素个数
stk.size();

// 是否为空
stk.empty(); // 空返回 true

5.插入删除

1
2
3
4
5
6
7
8
9
10
stack<int> stk;

// 插入
stk.push(10);

// 删除
stk.pop();

// 访问顶部元素
stk.top();

十二、queue

1.特性

  • 不支持随机访问。
  • 不提供迭代器,所以不能遍历。

2.初始化

1
2
3
4
5
// 默认构造
queue<int> q;

// 拷贝构造
queue<int> q(const queue<int> &another_q);

3.赋值

1
2
3
4
queue<int> q1, q2;

// 重载 = 号操作符
q1 = q2;

4.大小操作

1
2
3
4
5
6
7
queue<int> q;

// 元素个数
q.size();

// 是否为空
q.empty();

5.插入删除

1
2
3
4
5
6
7
queue<int> q;

// 队尾插入元素
q.push(10);

// 队首删除元素
q.pop();

6.取值

1
2
3
4
5
6
7
queue<int> q;

// 返回队首元素
q.back();

// 返回队尾元素
q.front();

十三、list

简要图:

实际上的图:

  • 有头节点 head_node:data 是随机值,next 指向 begin() 位置节点。
  • 首尾相连,end() 指向头节点位置。

验证:

1
2
3
4
5
int arr[] = {1, 4, 3, 6, 3};
list<int> l(arr, arr + sizeof(arr)/sizeof(int));

cout << *l.end(); // 随机值
cout << *(++l.end()); // begin() 位置的节点的 data。

1.特性

  • 节点包括两个域:数据域、指针域;

  • 不需要连续的内存空间;

  • 添加和删除元素效率高;

  • 链表需要的时候,才分配内存;

  • 链表需要额外的空间保存节点关系(前驱后继)。

2.初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
 // 默认构造 
list<int> l1;

// 有参构造
list<int> l2(l1.begin(), l1.end()); // 用迭代器
list<int> l3(10, 5); // 初始化为 10 个 5

// 用数组初始化
int arr[] = {1, 4, 3, 6, 3};
list<int> l(arr, arr + sizeof(arr)/sizeof(int));

// 拷贝构造
list<int> l4(l3);

3.赋值

1
2
3
4
5
6
7
8
9
10
11
12
list<int> l1, l2(5, 0);

// 用区间 [l2.begin() + 1, l2.end()) // list 的迭代器不可以加整型,只能自加。
l1.assign(++l2.begin(), l2.end());

l1.assign(5, 1); // 将 l1 赋值为 5 个 1。

// 重载 = 操作符
l1 = l2;

// 交换链表
l1.swap(l2);

4.大小操作

1
2
3
4
5
6
7
8
9
10
11
12
list<int> l(10, 5);

// 节点个数
l.size();

// 是否为空
l.empty();

// 重新指定大小
l.resize(num);
// 若容器变长,以 elem 填充,否则以 0 填充。
l.resize(num, elem);

5.取值

1
2
3
4
5
6
7
8
list<int> l(10, 1);
// 返回第一个元素
l.front();
// 返回最后一个元素
l.back();

// 迭代器取星
*l.begin() = 10;

6.插入删除

  • insert 函数只能使用迭代器。

  • list 的迭代器,不可以加整数,只能自加(因为 list 不支持随机访问)。

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
list<int> l(10, 5);

l.push_back(0);
l.pop_back();
l.push_front(1);
l.pop_front();

// 使用迭代器。
l.insert(l.begin(), 8);
l.insert(++l.begin(), 2, 8);

list<int>::iterator it = l.begin();
it++;
it++;
it++;
l.insert(it, 2, 8); // 迭代器只能自加。

// l.insert(l.begin() + 3, 2, 8); // error,只能自加。
l.insert(l.end(), l.begin(), l.end());

// 清空
l.clear();

// 删除区间 [it, l.end()) 的内容。
list<int>::iterator it = l.begin();
it++;
l.erase(it, l.end());

// 删除匹配的所有值
l.remove(5); // 删除所有 5;

7.链表反转和排序

1
2
3
4
5
6
7
8
9
10
11
list<int> l(10, 5);

// 翻转链表
l.reverse();

// 链表元素排序
bool compare(int a, int b) {
return a > b;
}

l.sort(compare); // 调用回调函数 compare, 若无参数,默认按从小到大。

8.为什么有成员函数 sort?

list 不支持随机访问,如果使用算法中的 sort 函数,效率不稳定。

十四、set/multiset

基于红黑树(平衡二叉树的一种)实现的。

1.特性

  • 属于关联容器:元素位置由容器规则实现的;

  • 查找效率非常高(元素自动排序);

  • set 不可以有重复元素,multiset 可以有重复元素。

  • 提供迭代器,但是不能通过迭代器改变数的值(如何改变元素数值,删除旧数据,添加新数据)。

    和 map 一样,不可以修改 key, 因为 key 关系到容器元素的顺序。

2.初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 默认构造函数
set<int> s1;
multiset<int> s2;

// 用数组初始化
int arr[] = {1, 4, 3, 5, 2};
set<int> s4(arr, arr + sizeof(arr)/sizeof(int));

// 用迭代器初始化
set<int> s5(s4.begin(), s4.end());

// 拷贝构造函数
set<int> s2 = s1;
set<int> s6(s1);

3.赋值

1
2
3
4
5
6
7
set<int> s1, s2;

// 重载 = 操作符
s1 = s2;

// 交换两个容器
s1.swap(s2);

4.大小操作

1
2
3
4
5
6
7
set<int> s1;

// 返回元素个数
s1.size();

// 判断容器是否为空
s1.empty();

5.插入删除

erase 的位置参数只能使用迭代器(只有 string 可以使用数字代表位置 pos ),迭代器不能加常量,只能自加。(因为 set 不支持随机访问)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
set<int> s;

// 插入元素
s.insert(elem);

// 清空数组
s.clear();

// 删除迭代器所指元素,返回下一个元素的迭代器。
s.erase(s.begin());

set<int>::iterator it = s.begin();
it++;
it++;
s.erase(it);

// 删除迭代器区间的元素,返回下一个元素的迭代器。
s.erase(++s.begin(), s.end());

// 删除 值为 elem 的全部元素(set 无重复,multiset 有重复)。
s.erase(elem);

6.查找

如果 set 存储的是对象,那么按照 什么变量 排序,find 函数查找时,就是把 什么变量 当作 key。

见: 如果排序对象呢?

1
2
3
4
5
6
7
8
9
10
11
// 1.找到,则返回当前位置的迭代器;2.未找到,返回 s.end() 迭代器。
s.find(3);

// 返回第一个 key >= keyElem 元素的迭代器。(lower_bound:下界)
lower_bound(keyElem);

// 返回第一个 key > keyElem 元素的迭代器。 (upper_bound:上界)
upper_bound(keyElem);

// 返回 lower_bound、upper_bound 函数的两个迭代器。
equal_range(keyElem);

例子:

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
int arr[] = {1, 7, 3, 5, 2};
set<int> s(arr, arr + sizeof(arr)/sizeof(int));

// s.find(3); 1.找到,则返回当前位置的迭代器;2.未找到,返回 s.end() 迭代器。
set<int>::iterator res = s.find(3);
if (res == s.end()) {
cout << "Not found" << endl;
} else {
cout << "Got it:" << *res << endl; // Got it:3
}

// lower_bound(3); 返回第一个 key >= keyElem 元素的迭代器。
res = s.lower_bound(3);
if (res == s.end()) {
cout << "Not found" << endl;
} else {
cout << "Got it:" << *res << endl; // Got it:3
}

// upper_bound(3); 返回第一个 key > keyElem 元素的迭代器。
res = s.upper_bound(3);
if (res == s.end()) {
cout << "Not found" << endl;
} else {
cout << "Got it:" << *res << endl; // Got it:5
}

// equal_range(3); 返回 lower_bound、upper_bound 函数的两个迭代器。pair 对组。
pair<set<int>::iterator, set<int>::iterator> pair_res = s.equal_range(3);

if (pair_res.first == s.end()) {
cout << "lower_bound: Not found" << endl;
} else {
cout << "lower_bound: Got it:" << *pair_res.first << endl; // Got it:3
}

if (pair_res.second == s.end()) {
cout << "upper_bound: Not found" << endl;
} else {
cout << "upper_bound: Got it:" << *pair_res.second << endl; // Got it:5
}

7.pair 对组

对组 pair 将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值分别用 pair 的两个公有函数 first 和 second 访问。

类模版:

1
template<class T1, class T2> struct pair.

如何创建对组?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 第一种构造
pair<string, int> pair_01(string("name"), 20);
pair<string, int> pair_02("name", 20);

pair<string, int> pair_03 = make_pair("name", 20);

// 拷贝构造
pair<string, int> pair_04 = pair_03;
pair<string, int> pair_05(pair_04);

// 重载 = 操作符
pair_04 = pair_02;

// 取值
cout << pair_03.first << endl;;
cout << pair_03.second << endl;

8.仿函数(函数对象)

  • 函数对象也叫仿函数。
  • 函数对象是类,不是函数,只是重载了 () 操作符。
  • 行为类似于函数的对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 以下代码用于更改 set 排序顺序

template<class T>
class Compare {
public:
bool operator()(const T &a, const T &b) { // 重载了 () 操作符,并且传入参数。
return a > b;
}
};

/* // 第二种写法:
template<class T>
struct Compare {
bool operator()(const T &a, const T &b) {
return a > b;
}
};
*/

int main() {
Compare<int> com;
cout << com(1, 2);
}

**仿函数的另外一个作用:**函数对象超出函数的概念,函数对象可以保存函数调用的状态。

  • 当统计函数调用次数时,就可以使用函数对象。函数对象可以用成员变量保存次数。

  • 如果使用普通函数,就需要用全局变量保存次数,开发中,应少用全局变量。

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
class MyPrint {
public:
MyPrint(){
num = 0;
}
MyPrint& operator()(int number) {
cout << number << endl;
num++; // 调用一次,num 就 ++。
return *this;
}
int getNum() {
return this->num;
}
private:
int num; // 记录函数调用多少次
};

int main() {
vector<int> v(10, 5);
MyPrint print_01;
// 将对象 print_01 传入,for_each 会拷贝该对象,执行完后会将拷贝的对象作为返回值返回。
// 1.print_01 中的 num = 0;
// 2.for_each 实际调用的是 print_01 的拷贝对象,并将拷贝对象返回;
// 3.实例化一个新的对象来接收返回值。
MyPrint print_02 = for_each(v.begin(), v.end(), print_01);
cout << print_01.getNum(); // 0
cout << print_02.getNum(); // 10
}

9.更改默认排序

写一个仿函数 Compare,并把 Compare 当错参数传入 set 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 仿函数
template<class T>
class Compare {
public:
bool operator()(const T &a, const T &b) {
return a > b; // 从大到小
}
};


int main() {
int arr[] = {1, 7, 3, 5, 2};

// 添加仿函数为参数。
set<int, Compare<int> > s(arr, arr + sizeof(arr)/sizeof(int));

// for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
// cout << *it << " ";
}
}

如果排序对象呢?

以下面代码为例,如果以 Person 的 id 进行排序,find 函数查找时,就是按照 id 为key 进行查找,并且查找过程中不关心 age 的值。

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
// 定义一个类
class Person {
public:
Person(int id, int age) {
this->id = id;
this->age = age;
}
int id;
int age;
};

// 排序规则:以 Person 类的 id 进行大小排序
class Compare {
public:
bool operator()(const Person &a, const Person &b) {
return a.id > b.id;
}
};

int main() {
Person p1(10, 20), p2(20, 30), p3(30, 40);

// 初始化容器时,将仿函数传入。将是按照 id 的大小排序,并且 id 成为 key。
set<Person, Compare> s;
s.insert(p1);
s.insert(p2);
s.insert(p3);

for (set<Person>::iterator it = s.begin(); it != s.end(); it++) {
cout << it->id << " ";
}

// find 函数以 id 为 key 进行查找。
Person p4(10, 11);
cout << "id: " << s.find(p4)->id << " age: " << s.find(p4)->age;
}

十五、map/multimap

基于红黑树(平衡二叉树的一种)实现的。

map 把数据封装成一个 pair 键值对,有键值 key、实值 value,(pair 第一个值是键值,第二个值是实值),所有元素根据键值自动排序。(相比于 set,区别在于 set 键值实值是一个值)

1.特性

  • 属于关联容器:元素位置由容器规则实现的;

  • map 中 key 不能重复,multimap 中 key 可以重复。

  • 可以通过 迭代器 改变 map 的 key 吗?

    不能!和 set 容器一样,key 关系到容器内的元素的排列规则,任意改变键值会破坏容器的排列规则。(set 和 map 只能删了旧 key, 再添加新的。)

2.初始化

1
map<int, int> m;

3.插入

【map】

  • 插入的一个 pair 对组,并且 key 不能重复。
  • insert 有返回值 pair<iterator, bool>。
  • [] 访问,不存在则创建(有值则为所的赋值,无值则为默认值),存在则修改实值。

【multimap】

  • insert 有返回值 iterator,标记插入位置的迭代器。
  • 不能用 [] 访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// insert 返回值是 pair<iterator, bool>,第一个值标记着插入位置的迭代器,第二个值标记着是否插入成功。
pair<map<int, int>::iterator, bool> res = m.insert(map<int, int>::value_type(0, 10));
if (res.second) {
cout << "插入成功!" << endl;
} else {
cout << "插入失败!" << endl;
}
m.insert(pair<int, int>(10, 10));
m.insert(make_pair(20, 10));

// 如果 m[30] 不存在,创建 m[30];
// 如果 m[30] 存在,修改实值。
m[30] = 10;
m[40]; // 只要访问,默认创建 m[40] = 0;(int 的默认值是 0,string 的默认值是 “”)

4.遍历

1
2
3
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
cout << “key:” << it->first << endl; // it 指向的是一个对组
}

5.删除

erase 的位置参数只能使用迭代器(只有 string 可以使用数字代表位置 pos ),迭代器不能加常量,只能自加。(因为 map 不支持随机访问)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 清空元素。
m.clear();

// 删除迭代器 pos 位置 的元素,返回下一个元素的迭代器。
map<int, int>::iterator pos = m.begin();
pos++;
pos++;
m.erase(pos);

// 删除迭代器区间 [++m.begin(), m.end()] 的元素。
m.erase(++m.begin(), m.end());

// 删除容器中 key = key_elem 的对组。
m.erase(key_elem);

6.查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 查找键值 key 是否存在,存在返回该键迭代器,不存在,则返回 m.end()。
m.find(key);

// 返回键值 key 的个数。
m.count(key);

// 返回第一个 >= key 的元素的迭代器。
m.lower_bound(key);

// 返回第一个 > key 的元素的迭代器。
m.upper_bound(key);

// 返回 lower_bound 和 upper_bound 的两个迭代器
m.equal_range(key);

7.更改排序规则

  • 加入规则时,可以使用 class 和 struct 。
  • bool operator() 函数必须限定返回值为 const 修饰。
  • 以对象为 key,必须有规则。
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
// 规则写法一:
struct Compare {
bool operator()(const MyKey &a, const MyKey &b) const { // const 修饰返回值
return a.index > b.index;
}
};

// 规则写法二:
// class Compare {
// public:
// bool operator()(const MyKey& a, const MyKey& b) const { // const 修饰返回值
// return a.index > b.index;
// }
// };

int main() {
// 带上规则初始化
map<MyKey, int, Compare> m;

// 插入元素(对组)
m.insert(pair<MyKey, int>(MyKey(1, 2), 10));
m.insert(make_pair(MyKey(2, 3), 10));
m.insert(map<MyKey, int, Compare>::value_type(MyKey(3, 4), 10));

// 遍历,打印对象
for (map<MyKey, int, Compare>::iterator it = m.begin(); it != m.end(); it++) {
cout << it->first.index << ":" << it->first.id << " " << it->second << endl;
}
}

十六、STL

1.容器的共性机制

【拷贝】:

  • STL 容器提供的都是值(value)寓意,而非引用(reference)寓意。

  • 当我们插入元素时,容器内部实施了拷贝动作:拷贝值到容器,而不是将原数据放入容器。

  • 【提供给容器的元素必须能被拷贝。】

【迭代器】:

  • 除 queue 和 stack 外,每个容器都有迭代器。
  • string、vector、deque 的迭代器可以加常数,list、set、map 只能迭代器自加(不空随机访问)。

【异常】

  • 一般不会抛异常,需要传入正确的参数。

【大小的函数】

size、empty 所有容器都有。

2.容器深拷贝和浅拷贝

当元素插入容器时,容器将拷贝该元素,而且应该是深拷贝。

因为程序结束时,p 调用一次析构函数,v 中的元素也会调用一次析构函数,对堆区同一内存进行析构,报错!

【如果容器元素为对象,类中必须有拷贝构造函数(深拷贝)、重载等号操作符(深拷贝)】

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
class Person {
public:
Person(const char *name) {
this->name = new char[strlen(name) + 1];
strcpy(this->name, name);
}

/* // 如果没有拷贝构造函数,将会报错。
Person(const Person& another) {
this->name = new char[strlen(another.name) + 1];
strcpy(this->name, another.name);
}

// 等号操作符,也要注意深拷贝。
Person& operator=(const Person& another) {
if (this->name != nullptr) {
delete this->name;
}
this->name = new char[strlen(another.name) + 1];
strcpy(name, another.name);
return *this;
}
*/

~Person() {
if (this->name != nullptr) {
delete this->name;
}
}

private:
char* name;
};

int main(){
Person p("Tom");
vector<Person> v;
v.push_back(p);
return 0;
}

3.谓词

谓词:返回值为 bool 类型的普通函数 或者 返回值为 bool 类型的重载 operator() 的仿函数。

  • 如果 operator() 接收一个参数,叫一元谓词。
  • 接收两个参数,叫二元谓词。

4.内建函数对象

什么是函数对象:仿函数(函数对象)

STL 内建了一些函数对象:算术类函数对象、关系运算类函数对象,逻辑运算类函数对象。

使用需要引用头文件:#include <functional>

举个例子:list 的自己的成员函数,sort 中的关于排序规则的参数,默认使用自己的内建函数对象。

1
2
3
4
5
6
7
8
list<int> l;
l.sort(); // 无参数,默认调用内建函数对象,排序从小到大

// 链表元素排序
bool compare(int a, int b) {
return a > b;
}
l.sort(compare); // 有回调函数

算术类函数对象:

1
2
3
4
5
6
template<class T> T plus<T>       //加法仿函数
template<class T> T minus<T> //减法仿函数
template<class T> T multiplies<T> //乘法仿函数
template<class T> T divides<T> //除法仿函数
template<class T> T modulus<T> //取模仿函数
template<class T> T negate<T> //取反仿函数

关系类函数对象:

1
2
3
4
5
6
template<class T> bool equal_to<T>      //等于
template<class T> bool not_equal_to<T> //不等于
template<class T> bool greater<T> //大于
template<class T> bool greater_equal<T> //大于等于
template<class T> bool less<T> //小于
template<class T> bool less_equal<T> //小于等于

逻辑运算类函数对象:

1
2
3
template<class T> bool logical_and<T> //逻辑与
template<class T> bool logical_or<T> //逻辑或
template<class T> bool logical_not<T> //逻辑非

5.函数对象适配器

注意:C++17 已废弃!

需要头文件 #include <functional>

(1)绑定适配器 bind1st、bind2nd

将一个二元的函数对象转变为一元的函数对象。

【需求】:for_each 调用仿函数 MyPrint,想打印 val + 100 的数值,并不修改 MyPrint。

【问题】:for_each 调用仿函数,只能调用一个 一元函数对象。如何将 100 当作参数传入一元函数对象?

1
2
3
4
5
6
7
// for_each 的定义
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
for (; __first != __last; ++__first)
__f(*__first); // 只能传入一个参数,为一元函数或者一元函数对象。
return __f;
}

【解决】:使用 bind2nd,将一个二元的函数对象转变为一元的函数对象。

  • MyPrint 要继承 binary_function<T> 类,类型中写 <参数类型, 参数类型, 返回值类型>。
  • operator() 函数要用 const 修饰,因为 bind2nd 参数是 const 修饰的。
1
2
bind2nd(const __Operation& __op, const _Tp& __x)
{return binder2nd<__Operation>(__op, __x);}

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyPrint : public binary_function<int, int, void> {   // 继承 + 类型
public:
void operator()(int val, int number) const { // const 修饰
cout << val + number << endl;
}
};

int main() {
vector<int> v(10, 5);
MyPrint print;
for_each(v.begin(), v.end(), bind2nd(print, 100)); // 使用 bind2nd
}

bind1st 和 bind2nd 有什么区别?

  • bind1st 将 100 绑定为函数对象的第一个参数。

  • bind2nd 将 100 绑定为函数对象的第二个参数。

(2)取反适配器 not1、not2

注意:C++17 已废弃!

not1:一元谓词取反。

not2:二元谓词取反。

【需求】:sort 排序时,需要传入规则 Compare,(否则默认按照从小到大排序),不过不想更改规则,如何将从大到小变成从小到大排序?

【解决】:使用取反适配器,因为比较两个值大小,所有使用 not2(二元仿函数)。

  • Compare 要继承 binary_function<T> 类,类型中写 <参数类型, 参数类型, 返回值类型>。
  • operator() 函数要用 const 修饰。
  • 【注意】一元仿函数继承 unary_function,二元仿函数继承 binary_function。

完整代码:

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
struct Compare : public binary_function<int, int, bool> {   // 继承 binary_function,类型为 <参数类型,参数类型,返回值类型>
bool operator()(const int &a, const int &b) const { // 返回值用 const 修饰
return a > b;
}
};

int main() {
vector<int> v;
// 生成随机数
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++) {
v.push_back(rand() % 100);
}

// 遍历
for (int i = 0; i < 10; i++) {
cout << v[i] << " ";
}
cout << endl << "=====================================" << endl;

// 排序
sort(v.begin(), v.end(), not2(Compare())); // 使用取反适配器

// 遍历
for (int i = 0; i < 10; i++) {
cout << v[i] << " ";
}
}

/*
71 0 97 44 92 37 75 25 41 20
=====================================
0 20 25 37 41 44 71 75 92 97
*/

(3)函数对象适配器

将普通函数修饰为函数对象。

**ptr_fun:**普通函数无法使用 bind2st 适配器,所以需要先将普通函数修饰为函数对象。

1
2
3
4
5
6
7
8
9
10
11
// 普通函数
void Print(int val, int tmp) {
cout << val + tmp << endl;
return;
}

int main() {
vector<int> v(10, 5);
// 【ptr_fun(Print)】 将普通函数 修饰为 函数对象。
for_each(v.begin(), v.end(), bind2nd(ptr_fun(Print), 100));
}

**mem_fun_ref、mem_fun:**将类的成员函数 修饰为 函数对象。

调用方式比较特殊:mem_fun_ref(&Person::Show) 取类的地址 :: 对象名。

mem_fun、mem_fun的区别:

  • 如果存放的是对象,使用 mem_fun_ref。
  • 如果存放的是对象指针,使用 mem_fun。
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
class Person {
public:
Person(int age, int id) {
this->age = age;
this->id = id;
}
void Show() {
cout << "id:" << id << " age:" << age << endl;
}
void NewID(int val) {
cout << "new_id:" << id + val << endl;
}
private:
int age;
int id;
};

int main() {
Person p1(10, 20), p2(30, 40);
vector<Person> v;
v.push_back(p1);
v.push_back(p2);


// 【mem_fun_ref(&Person::Show)】 将类中的函数修饰成函数对象。
for_each(v.begin(), v.end(), mem_fun_ref(&Person::Show));
// 【bind2nd(mem_fun_ref(&Person::NewID), 1999)】 使用 bind2nd,使二元的函数对象,修饰为 一元的函数对象。
for_each(v.begin(), v.end(), bind2nd(mem_fun_ref(&Person::NewID), 1999));


vector<Person*> v_ptr;
v_ptr.push_back(&p1);
v_ptr.push_back(&p2);
// 【mem_fun(&Person::Show)】 将类中的函数修饰成函数对象。
for_each(v_ptr.begin(), v_ptr.end(), mem_fun(&Person::Show));

return 0;
}

6.常用的查找算法

(1)find

find(v.begin(), v.end(), 5)

若找到,返回迭代器;没找到,返回 end 迭代器。

  • 【打印之前需要判断是否等于 end() 】

  • 【若是储存元素为对象,应写重载 == 操作符】

1
2
3
4
5
6
7
8
// 源码
find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
{
for (; __first != __last; ++__first)
if (*__first == __value_) // 此处用 == 判断,所以类要重载 == 操作符。
break;
return __first;
}

样例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 普通元素
vector<int> v(10);
for (int i = 0; i < 10; i++) {
int tmp = rand() % 10;
v[i] = tmp;
}

// find 函数:找到,返回迭代器;没找到,返回 end 迭代器。
vector<int>::iterator it = find(v.begin(), v.end(), 5);
if (it != v.end()) {
cout << "找到啦!" << endl;
} else {
cout << "没有找到!" << endl;
}
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
// 元素为对象
class Person {
public:
Person(int id) {
this->id = id;
}
// 重载 == 操作符
bool operator==(const Person& another) const {
if (this->id == another.id) {
return true;
}
return false;
}
private:
int id;
};

int main() {
Person p1(10), p2(20);
vector<Person> v;
v.push_back(p1);
v.push_back(p2);

vector<Person>::iterator it = find(v.begin(), v.end(), p1);
if (it != v.end()) {
cout << "找到啦!" << endl;
} else {
cout << "没有找到!" << endl;
}
}

二分查找,只能用于有序序列。

  • 返回值为 bool,若找到返回 true,没找到返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
int main() {
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
// 二分查找
bool res = binary_search(v.begin(), v.end(),5);
if (res) {
cout << "找到啦!" << endl;
} else {
cout << "没有找到!" << endl;
}
}

(3)adjacent_find

查找重复相邻的元素。

  • 返回值:相邻元素的第一个位置的迭代器。
  • 若无相邻重复的元素,返回 end()。
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
v.push_back(9);

vector<int>:: iterator it = adjacent_find(v.begin(), v.end());
if (it == v.end()) {
cout << "没有找到!" << endl;
} else {
cout << "找到:" << *it << endl;
}

(4)find_if

调用回调函数,判断是否找到。

1
2
3
4
5
6
7
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (__pred(*__first))
break;
return __first;
}

举个列子:找到第一个大于 6 的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// find_if 调用回调函数 MySearch,把 *it 传入 MySearch,如果得到 true 则找到。
bool MySearch(int val) {
if (val > 5) {
return true;
}
return false;
}

int main() {
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
v.push_back(9);

vector<int>:: iterator it = find_if(v.begin(), v.end(), MySearch); // 回调函数,也可以是 仿函数。
if (it == v.end()) {
cout << "没有找到!" << endl;
} else {
cout << "找到!" << *it << endl;
}
return 0;
}

(5)count、count_if

count:元素出现次数

count_if:根据回调函数,统计元素符合条件的个数。

1
2
3
4
5
6
7
8
9
10
11
12
// count
int main() {
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
v.push_back(9);

int num = count(v.begin(), v.end(), 9); // 查找元素 9 出现的次数。
cout << "num: " << num << endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// count_if
struct MySearch {
bool operator()(int val) {
if (val > 5) { // 大于 5 出现的元素个数。
return true;
}
return false;
}
};


int main() {
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
v.push_back(9);

MySearch m;
int num = count_if(v.begin(), v.end(), m); // 调用回调函数
cout << "num: " << num << endl;
return 0;
}

7.常用的遍历

(1)for_each

见:遍历容器

1
for_each(iterator begin, iterator end, _callback);

(2)transform

将一个容器的元素搬运到另一个容器中。

参数:原容器的begin(),原容器的end(),新容器的begin(),回调函数。

1
transform(iterator begin1, iterator end, iterator begin2, _callback);

实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int CallBack(int val) {
return val;
}

int main() {
vector<int> v1, v2;
for (int i = 0; i < 10; i++) {
v1.push_back(rand() % 100);
}

// 1.先初始化足够的空间。
v2.resize(v1.size());
// 2.搬运元素。
transform(v1.begin(), v1.end(), v2.begin(), CallBack);
return 0;
}