目录
c语言中动态内存管理方式malloc/calloc/realloc
operator new 与operator delete 函数
operator new与operator delete函数(重点)
为什么选择deque作为stack和queue的底层默认容器
c++入门
c++关键字
C++总计63个关键字,C语言32个关键字
命名空间
在C/C++中,变量、函数和后面要学到的类都是大量存在的,这些变量、函数和类的名称将都存
在于全局作用域中,可能会导致很多冲突。使用命名空间的目的是对标识符的名称进行本地化,
以避免命名冲突或名字污染,namespace关键字的出现就是针对这种问题的
#include <stdio.h>
#include <stdlib.h>
int rand = 10;
// C语言没办法解决类似这样的命名冲突问题,所以C++提出了namespace来解决
int main()
{
printf("%d\n", rand);
return 0;
}
// 编译后后报错:error C2365: “rand”: 重定义;以前的定义是“函数”
命名空间定义
定义命名空间,需要使用到namespace关键字,后面跟命名空间的名字,然后接一对{}即可,{}
中即为命名空间的成员。
// bit是命名空间的名字,一般开发中是用项目名字做命名空间名。
// 我们上课用的是bit,大家下去以后自己练习用自己名字缩写即可,如张三:zs
// 1. 正常的命名空间定义
namespace bit
{
// 命名空间中可以定义变量/函数/类型
int rand = 10;
int Add(int left, int right)
{
return left + right;
}
struct Node
{
struct Node* next;
int val;
};
}
//2. 命名空间可以嵌套
// test.cpp
namespace N1
{
int a;
int b;
int Add(int left, int right)
{
return left + right;
}
namespace N2
{
int c;
int d;
int Sub(int left, int right)
{
return left - right;
}
}
}
//3. 同一个工程中允许存在多个相同名称的命名空间,编译器最后会合成同一个命名空间中。
// ps:一个工程中的test.h和上面test.cpp中两个N1会被合并成一个
// test.h
namespace N1
{
int Mul(int left, int right)
{
return left * right;
}
}
命名空间使用
命名空间中成员该如何使用呢?比如:
namespace bit
{
// 命名空间中可以定义变量/函数/类型
int a = 0;
int b = 1;
int Add(int left, int right)
{
return left + right;
}
struct Node
{
struct Node* next;
int val;
};
}
int main()
{
// 编译报错:error C2065: “a”: 未声明的标识符
printf("%d\n", a);
return 0;
}
命名空间的使用有三种方式:
1.加命名空间名称及作用域限定符
int main()
{
printf("%d\n", N::a);
return 0;
}
2.使用using将命名空间中某个成员引入
using N::b;
int main()
{
printf("%d\n", N::a);
printf("%d\n", b);
return 0;
}
3.使用using namespace 命名空间名称 引入
using namespce N;
int main()
{
printf("%d\n", N::a);
printf("%d\n", b);
Add(10, 20);
return 0;
}
c++输入输出
新生婴儿会以自己独特的方式向这个崭新的世界打招呼,C++刚出来后,也算是一个新事物,
那C++是否也应该向这个美好的世界来声问候呢?我们来看下C++是如何来实现问候的。
#include<iostream>
// std是C++标准库的命名空间名,C++将标准库的定义实现都放到这个命名空间中
using namespace std;
int main()
{
cout<<"Hello world!!!"<<endl;
return 0;
}
说明:
1. 使用cout标准输出对象(控制台)和cin标准输入对象(键盘)时,必须包含< iostream >头文件
以及按命名空间使用方法使用std。
2. cout和cin是全局的流对象,endl是特殊的C++符号,表示换行输出,他们都包含在包含<
iostream >头文件中。
3. <<是流插入运算符,>>是流提取运算符。
4. 使用C++输入输出更方便,不需要像printf/scanf输入输出时那样,需要手动控制格式。
C++的输入输出可以自动识别变量类型。
5. 实际上cout和cin分别是ostream和istream类型的对象,>>和<<也涉及运算符重载等知识,
这些知识我们我们后续才会学习,所以我们这里只是简单学习他们的使用。后面我们还有有
一个章节更深入的学习IO流用法及原理。
注意:早期标准库将所有功能在全局域中实现,声明在.h后缀的头文件中,使用时只需包含对应
头文件即可,后来将其实现在std命名空间下,为了和C头文件区分,也为了正确使用命名空间,
规定C++头文件不带.h;旧编译器(vc 6.0)中还支持<iostream.h>格式,后续编译器已不支持,因
此推荐使用<iostream>+std的方式。
#include <iostream>
using namespace std;
int main()
{
int a;
double b;
char c;
// 可以自动识别变量的类型
cin>>a;
cin>>b>>c;
cout<<a<<endl;
cout<<b<<" "<<c<<endl;
return 0;
}
// ps:关于cout和cin还有很多更复杂的用法,比如控制浮点数输出精度,控制整形输出进制格式等
等。因为C++兼容C语言的用法
std命名空间的使用惯例:
std是C++标准库的命名空间,如何展开std使用更合理呢?
1. 在日常练习中,建议直接using namespace std即可,这样就很方便。
2. using namespace std展开,标准库就全部暴露出来了,如果我们定义跟库重名的类型/对象/函数,就存在冲突问题。该问题在日常练习中很少出现,但是项目开发中代码较多、规模大,就很容易出现。所以建议在项目开发中使用,像std::cout这样使用时指定命名空间 +using std::cout展开常用的库对象/类型等方式。
缺省参数
缺省参数概念
缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数时,如果没有指定实
参则采用该形参的缺省值,否则使用指定的实参。
void Func(int a = 0)
{
cout<<a<<endl;
}
int main()
{
Func(); // 没有传参时,使用参数的默认值
Func(10); // 传参时,使用指定的实参
return 0;
}
缺省参数分类
全缺省参数
void Func(int a = 10, int b = 20, int c = 30)
{
cout<<"a = "<<a<<endl;
cout<<"b = "<<b<<endl;
cout<<"c = "<<c<<endl;
}
半缺省参数
void Func(int a, int b = 10, int c = 20)
{
cout<<"a = "<<a<<endl;
cout<<"b = "<<b<<endl;
cout<<"c = "<<c<<endl;
}
注意:
1. 半缺省参数必须从右往左依次来给出,不能间隔着给
2. 缺省参数不能在函数声明和定义中同时出现
//a.h
void Func(int a = 10);
// a.cpp
void Func(int a = 20)
{}
// 注意:如果生命与定义位置同时出现,恰巧两个位置提供的值不同,那编译器就无法确定到底该
//用那个缺省值。
3. 缺省值必须是常量或者全局变量
4. C语言不支持(编译器不支持)
函数重载
自然语言中,一个词可以有多重含义,人们可以通过上下文来判断该词真实的含义,即该词被重载了。
比如:以前有一个笑话,国有两个体育项目大家根本不用看,也不用担心。一个是乒乓球,一个是男足。前者是“谁也赢不了!”,后者是“谁也赢不了!“
函数重载概念
函数重载:是函数的一种特殊情况,C++允许在同一作用域中声明几个功能类似的同名函数,这些同名函数的形参列表(参数个数 或 类型 或 类型顺序)不同,常用来处理实现功能类似数据类型不同的问题。
#include<iostream>
using namespace std;
// 1、参数类型不同
int Add(int left, int right)
{
cout << "int Add(int left, int right)" << endl;
return left + right;
}
double Add(double left, double right)
{
cout << "double Add(double left, double right)" << endl;
return left + right;
}
// 2、参数个数不同
void f()
{
cout << "f()" << endl;
}
void f(int a)
{
cout << "f(int a)" << endl;
}
// 3、参数类型顺序不同
void f(int a, char b)
{
cout << "f(int a,char b)" << endl;
}
void f(char b, int a)
{
cout << "f(char b, int a)" << endl;
}
int main()
{
Add(10, 20);
Add(10.1, 20.2);
f();
f(10);
f(10, 'a');
f('a', 10);
return 0;
}
c++支持函数重载原理--名字修饰(name)
为什么C++支持函数重载,而C语言不支持函数重载呢?
在C/C++中,一个程序要运行起来,需要经历以下几个阶段:预处理、编译、汇编、链接。
1. 实际项目通常是由多个头文件和多个源文件构成,而通过C语言阶段学习的编译链接,我们
可以知道,【当前a.cpp中调用了b.cpp中定义的Add函数时】,编译后链接前,a.o的目标文件中没有Add的函数地址,因为Add是在b.cpp中定义的,所以Add的地址在b.o中。那么怎么办呢?
2. 所以链接阶段就是专门处理这种问题,链接器看到a.o调用Add,但是没有Add的地址,就 会到b.o的符号表中找Add的地址,然后链接到一起。(老师要带同学们回顾一下)
3. 那么链接时,面对Add函数,链接接器会使用哪个名字去找呢?这里每个编译器都有自己的函数名修饰规则。
4. 由于Windows下vs的修饰规则过于复杂,而Linux下g++的修饰规则简单易懂,下面我们使用了g++演示了这个修饰后的名字。
5. 通过下面我们可以看出gcc的函数修饰后名字不变。而g++的函数修饰后变成【_Z+函数长度 +函数名+类型首字母】。 采用C语言编译器编译后结果
结论:在linux下,采用gcc编译完成后,函数名字的修饰没有发生改变。
采用C++编译器编译后结果
结论:在linux下,采用g++编译完成后,函数名字的修饰发生改变,编译器将函数参 数类型信息添加到修改后的名字中。
Windows下名字修饰规则
对比Linux会发现,windows下vs编译器对函数名字修饰规则相对复杂难懂,但道理都是类似的
6. 通过这里就理解了C语言没办法支持重载,因为同名函数没办法区分。而C++是通过函数修 饰规则来区分,只要参数不同,修饰出来的名字就不一样,就支持了重载。
7. 如果两个函数函数名和参数是一样的,返回值不同是不构成重载的,因为调用时编译器没办法区分。
引用
引用概念
引用不是新定义一个变量,而是给已存在变量取了一个别名,编译器不会为引用变量开辟内存空间,它和它引用的变量共用同一块内存空间。
比如:李逵,在家称为"铁牛",江湖上人称"黑旋风"。
类型& 引用变量名(对象名) = 引用实体;
void TestRef()
{
int a = 10;
int& ra = a;//<====定义引用类型
printf("%p\n", &a);
printf("%p\n", &ra);
}
注意:引用类型必须和引
引用特性
1. 引用在定义时必须初始化
2. 一个变量可以有多个引用
3. 引用一旦引用一个实体,再不能引用其他实体
void TestRef()
{
int a = 10;
// int& ra; // 该条语句编译时会出错
int& ra = a;
int& rra = a;
printf("%p %p %p\n", &a, &ra, &rra);
}
常引用
void TestConstRef()
{
const int a = 10;
//int& ra = a; // 该语句编译时会出错,a为常量
const int& ra = a;
// int& b = 10; // 该语句编译时会出错,b为常量
const int& b = 10;
double d = 12.34;
//int& rd = d; // 该语句编译时会出错,类型不同
const int& rd = d;
}
使用场景
1. 做参数
void Swap(int& left, int& right)
{
int temp = left;
left = right;
right = temp;
}
2. 做返回值
int& Count()
{
static int n = 0;
n++;
// ...
return n;
}
下面代码输出什么结果?为什么?
int& Add(int a, int b)
{
int c = a + b;
return c;
}
int main()
{
int& ret = Add(1, 2);
Add(3, 4);
cout << "Add(1, 2) is :"<< ret <<endl;
return 0;
}
注意:如果函数返回时,出了函数作用域,如果返回对象还在(还没还给系统),则可以使用 引用返回,如果已经还给系统了,则必须使用传值返回。
传值,传引用效率对比
以值作为参数或者返回值类型,在传参和返回期间,函数不会直接传递实参或者将变量本身直接返回,而是传递实参或者返回变量的一份临时的拷贝,因此用值作为参数或者返回值类型,效率是非常低下的,尤其是当参数或者返回值类型非常大时,效率就更低。
#include <time.h>
struct A{ int a[10000]; };
void TestFunc1(A a){}
void TestFunc2(A& a){}
void TestRefAndValue()
{
A a;
// 以值作为函数参数
size_t begin1 = clock();
for (size_t i = 0; i < 10000; ++i)
TestFunc1(a);
size_t end1 = clock();
// 以引用作为函数参数
size_t begin2 = clock();
for (size_t i = 0; i < 10000; ++i)
TestFunc2(a);
size_t end2 = clock();
// 分别计算两个函数运行结束后的时间
cout << "TestFunc1(A)-time:" << end1 - begin1 << endl;
cout << "TestFunc2(A&)-time:" << end2 - begin2 << endl;
}
值和引用的作为返回值类型的性能比较
#include <time.h>
struct A{ int a[10000]; };
A a;
// 值返回
A TestFunc1() { return a;}
// 引用返回
A& TestFunc2(){ return a;}
void TestReturnByRefOrValue()
{
// 以值作为函数的返回值类型
size_t begin1 = clock();
for (size_t i = 0; i < 100000; ++i)
TestFunc1();
size_t end1 = clock();
// 以引用作为函数的返回值类型
size_t begin2 = clock();
for (size_t i = 0; i < 100000; ++i)
TestFunc2();
size_t end2 = clock();
// 计算两个函数运算完成之后的时间
cout << "TestFunc1 time:" << end1 - begin1 << endl;
cout << "TestFunc2 time:" << end2 - begin2 << endl;
}
通过上述代码的比较,发现传值和指针在作为传参以及返回值类型上效率相差很大。
引用和指针的区别
在语法概念上引用就是一个别名,没有独立空间,和其引用实体共用同一块空间。
int main()
{
int a = 10;
int& ra = a;
cout<<"&a = "<<&a<<endl;
cout<<"&ra = "<<&ra<<endl;
return 0;
}
在底层实现上实际是有空间的,因为引用是按照指针方式来实现的。
int main()
{
int a = 10;
int& ra = a;
ra = 20;
int* pa = &a;
*pa = 20;
return 0;
}
引用和指针的不同点:
1. 引用概念上定义一个变量的别名,指针存储一个变量地址。
2. 引用在定义时必须初始化,指针没有要求
3. 引用在初始化时引用一个实体后,就不能再引用其他实体,而指针可以在任何时候指向任何一个同类型实体
4. 没有NULL引用,但有NULL指针
5. 在sizeof中含义不同:引用结果为引用类型的大小,但指针始终是地址空间所占字节个数(32位平台下占4个字节)
6. 引用自加即引用的实体增加1,指针自加即指针向后偏移一个类型的大小
7. 有多级指针,但是没有多级引用
8. 访问实体方式不同,指针需要显式解引用,引用编译器自己处理
9. 引用比指针使用起来相对更安全
内联函数
概念
以inline修饰的函数叫做内联函数,编译时C++编译器会在调用内联函数的地方展开,没有函数调用建立栈帧的开销,内联函数提升程序运行的效率。
如果在上述函数前增加inline关键字将其改成内联函数,在编译期间编译器会用函数体替换函数的调用。查看方式:
1. 在release模式下,查看编译器生成的汇编代码中是否存在call Add
2. 在debug模式下,需要对编译器进行设置,否则不会展开(因为debug模式下,编译器默认不会对代码进行优化,以下给出vs2013的设置方式)
特性
1. inline是一种以空间换时间的做法,如果编译器将函数当成内联函数处理,在编译阶段,会 用函数体替换函数调用,缺陷:可能会使目标文件变大,优势:少了调用开销,提高程序运行效率。
2. inline对于编译器而言只是一个建议,不同编译器关于inline实现机制可能不同,一般建议:将函数规模较小(即函数不是很长,具体没有准确的说法,取决于编译器内部实现)、不 是递归、且频繁调用的函数采用inline修饰,否则编译器会忽略inline特性。
3. inline不建议声明和定义分离,分离会导致链接错误。因为inline被展开,就没有函数地址了,链接就会找不到
// F.h
#include <iostream>
using namespace std;
inline void f(int i);
// F.cpp
#include "F.h"
void f(int i)
{
cout << i << endl;
}
// main.cpp
#include "F.h"
int main()
{
f(10);
return 0;
}
// 链接错误:main.obj : error LNK2019: 无法解析的外部符号 "void __cdecl
//f(int)" (?f@@YAXH@Z),该符号在函数 _main 中被引用
【面试题】
宏的优缺点?
优点:
1.增强代码的复用性。
2.提高性能。
缺点:
1.不方便调试宏。(因为预编译阶段进行了替换)
2.导致代码可读性差,可维护性差,容易误用。
3.没有类型安全的检查 。
C++有哪些技术替代宏?
1. 常量定义 换用const enum
2. 短小函数定义 换用内联函数
auto关键字(c++11)
类型别名思考
随着程序越来越复杂,程序中用到的类型也越来越复杂,经常体现在:
1. 类型难于拼写
2. 含义不明确导致容易出错
#include <string>
#include <map>
int main()
{
std::map<std::string, std::string> m{ { "apple", "苹果" }, { "orange",
"橙子" },
{"pear","梨"} };
std::map<std::string, std::string>::iterator it = m.begin();
while (it != m.end())
{
//....
}
return 0;
}
std::map<std::string, std::string>::iterator 是一个类型,但是该类型太长了,特别容
易写错。聪明的同学可能已经想到:可以通过typedef给类型取别名,比如:
#include <string>
#include <map>
typedef std::map<std::string, std::string> Map;
int main()
{
Map m{ { "apple", "苹果" },{ "orange", "橙子" }, {"pear","梨"} };
Map::iterator it = m.begin();
while (it != m.end())
{
//....
}
return 0;
}
使用typedef给类型取别名确实可以简化代码,但是typedef有会遇到新的难题:
typedef char* pstring;
int main()
{
const pstring p1; // 编译成功还是失败?
const pstring* p2; // 编译成功还是失败?
return 0;
}
在编程时,常常需要把表达式的值赋值给变量,这就要求在声明变量的时候清楚地知道表达式的
类型。然而有时候要做到这点并非那么容易,因此C++11给auto赋予了新的含义
auto简介
在早期C/C++中auto的含义是:使用auto修饰的变量,是具有自动存储器的局部变量,但遗憾的是一直没有人去使用它,大家可思考下为什么?
C++11中,标准委员会赋予了auto全新的含义即:auto不再是一个存储类型指示符,而是作为一 个新的类型指示符来指示编译器,auto声明的变量必须由编译器在编译时期推导而得
int TestAuto()
{
return 10;
}
int main()
{
int a = 10;
auto b = a;
auto c = 'a';
auto d = TestAuto();
cout << typeid(b).name() << endl;
cout << typeid(c).name() << endl;
cout << typeid(d).name() << endl;
//auto e; 无法通过编译,使用auto定义变量时必须对其进行初始化
return 0;
}
【注意】
使用auto定义变量时必须对其进行初始化,在编译阶段编译器需要根据初始化表达式来推导auto 的实际类型。因此auto并非是一种“类型”的声明,而是一个类型声明时的“占位符”,编译器在编 译期会将auto替换为变量实际
auto使用细则
1. auto与指针和引用结合起来使用
用auto声明指针类型时,用auto和auto*没有任何区别,但用auto声明引用类型时则必须 加&
int main()
{
int x = 10;
auto a = &x;
auto* b = &x;
auto& c = x;
cout << typeid(a).name() << endl;
cout << typeid(b).name() << endl;
cout << typeid(c).name() << endl;
*a = 20;
*b = 30;
c = 40;
return 0;
}
2. 在同一行定义多个变量
当在同一行声明多个变量时,这些变量必须是相同的类型,否则编译器将会报错,因为编译
器实际只对第一个类型进行推导,然后用推导出来的类型定义其他变量。
void TestAuto()
{
auto a = 1, b = 2;
auto c = 3, d = 4.0; // 该行代码会编译失败,因为c和d的初始化表达式类型不同
}
auto不能·推导的场景
1. auto不能作为函数的参数
// 此处代码编译失败,auto不能作为形参类型,因为编译器无法对a的实际类型进行推导
void TestAuto(auto a)
{}
2. auto不能直接用来声明数组
void TestAuto()
{
int a[] = {1,2,3};
auto b[] = {4,5,6};
}
3. 为了避免与C++98中的auto发生混淆,C++11只保留了auto作为类型指示符的用法
4. auto在实际中最常见的优势用法就是跟以后会讲到的C++11提供的新式for循环,还有lambda表达式等进行配合使用、
基于范围for循环(c++11)
范围for语法
在C++98中如果要遍历一个数组,可以按照以下方式进行:
void TestFor()
{
int array[] = { 1, 2, 3, 4, 5 };
for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
array[i] *= 2;
for (int* p = array; p < array + sizeof(array)/ sizeof(array[0]); ++p)
cout << *p << endl;
}
对于一个有范围的集合而言,由程序员来说明循环的范围是多余的,有时候还会容易犯错误。因此C++11中引入了基于范围的for循环。for循环后的括号由冒号“ :”分为两部分:第一部分是范 围内用于迭代的变量,第二部分则表示被迭代的范围。
void TestFor()
{
int array[] = { 1, 2, 3, 4, 5 };
for(auto& e : array)
e *= 2;
for(auto e : array)
cout << e << " ";
//依次取数组中的数据赋值给e(e也可以是其他名字)
//自动判定结束
//自动迭代
return 0;
}
注意:与普通循环类似,可以用continue来结束本次循
范围for使用条件
1. for循环迭代的范围必须是确定的
对于数组而言,就是数组中第一个元素和最后一个元素的范围;对于类而言,应该提供begin和end的方法,begin和end就是for循环迭代的范围。
注意:以下代码就有问题,因为for的范围不确定
void TestFor(int array[])
{
for(auto& e : array)
cout<< e <<endl;
}
2. 迭代的对象要实现++和==的操作
指针空值nullptr(c++11)
c++98中的指针空值
在良好的C/C++编程习惯中,声明一个变量时最好给该变量一个合适的初始值,否则可能会出现不可预料的错误,比如未初始化的指针。如果一个指针没有合法的指向,我们基本都是按照如下方式对其进行初始化:
void TestPtr()
{
int* p1 = NULL;
int* p2 = 0;
// ……
}
NULL实际是一个宏,在传统的C头文件(stddef.h)中,可以看到如下代码:
#ifndef NULL
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif
#endif
可以看到,NULL可能被定义为字面常量0,或者被定义为无类型指针(void*)的常量。不论采取何种定义,在使用空值的指针时,都不可避免的会遇到一些麻烦,比如:
void f(int)
{
cout<<"f(int)"<<endl;
}
void f(int*)
{
cout<<"f(int*)"<<endl;
}
int main()
{
f(0);
f(NULL);
f((int*)NULL);
return 0;
}
程序本意是想通过f(NULL)调用指针版本的f(int*)函数,但是由于NULL被定义成0,因此与程序的初衷相悖。
在C++98中,字面常量0既可以是一个整形数字,也可以是无类型的指针(void*)常量,但是编译器默认情况下将其看成是一个整形常量,如果要将其按照指针方式来使用,必须对其进行强转(void*)0。
注意:
1. 在使用nullptr表示指针空值时,不需要包含头文件,因为nullptr是C++11作为新关键字引入 的。
2. 在C++11中,sizeof(nullptr) 与 sizeof((void*)0)所占的字节数相同。
3. 为了提高代码的健壮性,在后续表示指针空值时建议最好使用nullptr。
类与对象(上篇)
面向过程和面向对象初步介绍
C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。
C++是基于面向对象的,关注的是对象,将一件事情拆分成不同的对象,靠对象之间的交互完成。
类的引入
C语言结构体中只能定义变量,在C++中,结构体内不仅可以定义变量,也可以定义函数。比如:
之前在数据结构初阶中,用C语言方式实现的栈,结构体中只能定义变量;现在以C++方式实现,
会发现struct中也可以定义函数
typedef int DataType;
struct Stack
{
void Init(size_t capacity)
{
_array = (DataType*)malloc(sizeof(DataType) * capacity);
if (nullptr == _array)
{
perror("malloc申请空间失败");
return;
}
_capacity = capacity;
_size = 0;
}
void Push(const DataType& data)
{
// 扩容
_array[_size] = data;
++_size;
}
DataType Top()
{
return _array[_size - 1];
}
void Destroy()
{
if (_array)
{
free(_array);
_array = nullptr;
_capacity = 0;
_size = 0;
}
}
DataType* _array;
size_t _capacity;
size_t _size;
};
int main()
{
Stack s;
s.Init(10);
s.Push(1);
s.Push(2);
s.Push(3);
cout << s.Top() << endl;
s.Destroy();
return 0;
}
上面结构体的定义,在C++中更喜欢用class来代替。
类的定义
class className
{
// 类体:由成员函数和成员变量组成
}; // 一定要注意后面的分号
class为定义类的关键字,ClassName为类的名字,{}中为类的主体,注意类定义结束时后面分 号不能省略。
类体中内容称为类的成员:类中的变量称为类的属性或成员变量; 类中的函数称为类的方法或成员函数。
类的两种定义方式:
1. 声明和定义全部放在类体中,需注意:成员函数如果在类中定义,编译器可能会将其当成内 联函数处理。
2. 类声明放在.h文件中,成员函数定义放在.cpp文件中,注意:成员函数名前需要加类名::
一般情况下,更期望采用第二种方式。注意:上课为了方便演示使用方式一定义类,大家后序工 作中尽量使用第二种。
成员变量命名规则的建议:
// 我们看看这个函数,是不是很僵硬?
class Date
{
public:
void Init(int year)
{
// 这里的year到底是成员变量,还是函数形参?
year = year;
}
private:
int year;
};
// 所以一般都建议这样
class Date
{
public:
void Init(int year)
{
_year = year;
}
private:
int _year;
};
// 或者这样
class Date
{
public:
void Init(int year)
{
mYear = year;
}
private:
int mYear;
};
class Date
{
public:
void Init(int year)
{
_year = year;
}
private:
int _year;
};
// 或者这样
class Date
{
public:
void Init(int year)
{
mYear = year;
}
private:
int mYear;
};
// 其他方式也可以的,主要看公司要求。一般都是加个前缀或者后缀标识区分就行
类的访问限定符及封装
访问限定符
C++实现封装的方式:用类将对象的属性与方法结合在一块,让对象更加完善,通过访问权限选择性的将其接口提供给外部的用户使用
【访问限定符说明】
1. public修饰的成员在类外可以直接被访问
2. protected和private修饰的成员在类外不能直接被访问(此处protected和private是类似的)
3. 访问权限作用域从该访问限定符出现的位置开始直到下一个访问限定符出现时为止
4. 如果后面没有访问限定符,作用域就到 } 即类结束。
5. class的默认访问权限为private,struct为public(因为struct要兼容C)
注意:访问限定符只在编译时有用,当数据映射到内存后,没有任何访问限定符上的区别
【面试题】
问题:C++中struct和class的区别是什么?
解答:C++需要兼容C语言,所以C++中struct可以当成结构体使用。另外C++中struct还可以用来定义类。和class定义类是一样的,区别是struct定义的类默认访问权限是public,class定义的类默认访问权限是private。注意:在继承和模板参数列表位置,struct和class也有区别,后序给大家介绍。
封装
【面试题】
面向对象的三大特性:封装、继承、多态。
在类和对象阶段,主要是研究类的封装特性,那什么是封装呢?
封装:将数据和操作数据的方法进行有机结合,隐藏对象的属性和实现细节,仅对外公开接口来 和对象进行交互。
封装本质上是一种管理,让用户更方便使用类。比如:对于电脑这样一个复杂的设备,提供给用户的就只有开关机键、通过键盘输入,显示器,USB插孔等,让用户和计算机进行交互,完成日常事务。但实际上电脑真正工作的却是CPU、显卡、内存等一些硬件元件。
对于计算机使用者而言,不用关心内部核心部件,比如主板上线路是如何布局的,CPU内部是如何设计的等,用户只需要知道,怎么开机、怎么通过键盘和鼠标与计算机进行交互即可。因此计 算机厂商在出厂时,在外部套上壳子,将内部实现细节隐藏起来,仅仅对外提供开关机、鼠标以 及键盘插孔等,让用户可以与计算机进行交互即可。
在C++语言中实现封装,可以通过类将数据以及操作数据的方法进行有机结合,通过访问权限来 隐藏对象内部实现细节,控制哪些方法可以在类外部直接
类的作用域
类定义了一个新的作用域,类的所有成员都在类的作用域中。在类体外定义成员时,需要使用 ::
作用域操作符指明成员属于哪个类域。
class Person
{
public:
void PrintPersonInfo();
private:
char _name[20];
char _gender[3];
int _age;
};
// 这里需要指定PrintPersonInfo是属于Person这个类域
void Person::PrintPersonInfo()
{
cout << _name << " "<< _gender << " " << _age << endl;
}
类的实例化
用类类型创建对象的过程,称为类的实例化
1. 类是对对象进行描述的,是一个模型一样的东西,限定了类有哪些成员,定义出一个类并没 有分配实际的内存空间来存储它;比如:入学时填写的学生信息表,表格就可以看成是一个类,来描述具体学生信息。
类就像谜语一样,对谜底来进行描述,谜底就是谜语的一个实例。谜语:"年纪不大,胡子一把,主人来了,就喊妈妈" 谜底:山羊
2. 一个类可以实例化出多个对象,实例化出的对象占用实际的物理空间,存储类成员变量
int main()
{
Person._age = 100; // 编译失败:error C2059: 语法错误:“.”
return 0;
}
Person类是没有空间的,只有Person类实例化出的对象才有具体的年龄。
3. 做个比方。类实例化出对象就像现实中使用建筑设计图建造出房子,类就像是设计图,只设计出需要什么东西,但是并没有实体的建筑存在,同样类也只是一个设计,实例化出的对象才能实际存储数据,占用物理空间
类对象模型
如何计算类对象大小
class A
{
public:
void PrintA()
{
cout<<_a<<endl;
}
private:
char _a;
};
问题:类中既可以有成员变量,又可以有成员函数,那么一个类的对象中包含了什么?如何计算一个类的大小?
类对象的存储方式猜测
对象中包含类的各个成员
缺陷:每个对象中成员变量是不同的,但是调用同一份函数,如果按照此种方式存储,当一个类创建多个对象时,每个对象中都会保存一份代码,相同代码保存多次,浪费空间。那么 如何解决呢?
代码只保存一份,在对象中保存存放代码的地址
只保存成员变量,成员函数存放在公共的代码段
问题:对于上述三种存储方式,那计算机到底是按照那种方式来存储的?
我们再通过对下面的不同对象分别获取大小来分析看下
// 类中既有成员变量,又有成员函数
class A1 {
public:
void f1(){}
private:
int _a;
};
// 类中仅有成员函数
class A2 {
public:
void f2() {}
};
// 类中什么都没有---空类
class A3
{};
//分配1byte位,不存储数据,只是占位,表示对象存在过
sizeof(A1) : ___4___ sizeof(A2) : ___1___ sizeof(A3) : ___1___
结论:一个类的大小,实际就是该类中”成员变量”之和,当然要注意内存对齐
注意空类的大小,空类比较特殊,编译器给了空类一个字节来唯一标识这个类的对象。
结构体内存对齐规则
1. 第一个成员在与结构体偏移量为0的地址处。
2. 其他成员变量要对齐到某个数字(对齐数)的整数倍的地址处。注意:对齐数 = 编译器默认的一个对齐数 与 该成员大小的较小值。
VS中默认的对齐数为8
3. 结构体总大小为:最大对齐数(所有变量类型最大者与默认对齐参数取最小)的整数倍。
4. 如果嵌套了结构体的情况,嵌套的结构体对齐到自己的最大对齐数的整数倍处,结构体的整体大小就是所有最大对齐数(含嵌套结构体的对齐数)的整数倍。
【面试题】
1. 结构体怎么对齐? 为什么要进行内存对齐?
结构体的内存对齐是拿空间来换取时间的做法。优点是提高了可移植性和cpu性能
2. 如何让结构体按照指定的对齐参数进行对齐?能否按照3、4、5即任意字节对齐?
3. 什么是大小端?如何测试某台机器是大端还是小端,有没有遇到过要考虑大小端的场景
小端: 数据的低序字节保存在内存的低地址,数据的高序字节保存在内存的高地址。低序低地好记。
大端: 数据的高序字节保存在内存的低地址,数据的低序字节保存在内存的高地址
芯片字节序: 大端,符合阅读习惯;
网元字节序: 小端,ARM大部分是小端;
网络字节序: 大端,规定。
this指针
this指针的引出
我们先来定义一个日期类 Date
this指针的特性
class Date
{
public:
void Init(int year, int month, int day)
{
_year = year;
_month = month;
_day = day;
}
void Print()
{
cout <<_year<< "-" <<_month << "-"<< _day <<endl;
}
private:
int _year; // 年
int _month; // 月
int _day; // 日
};
int main()
{
Date d1, d2;
d1.Init(2022,1,11);
d2.Init(2022, 1, 12);
d1.Print();
d2.Print();
return 0;
}
对于上述类,有这样的一个问题:
Date类中有 Init 与 Print 两个成员函数,函数体中没有关于不同对象的区分,那当d1调用 Init 函数时,该函数是如何知道应该设置d1对象,而不是设置d2对象呢?
C++中通过引入this指针解决该问题,即:C++编译器给每个“非静态的成员函数“增加了一个隐藏的指针参数,让该指针指向当前对象(函数运行时调用该函数的对象),在函数体中所有“成员变量” 的操作,都是通过该指针去访问。只不过所有的操作对用户是透明的,即用户不需要来传递,编 译器自动完成。
this指针的特性
1. this指针的类型:类类型* const,即成员函数中,不能给this指针赋值。
2. 只能在“成员函数”的内部使用
3. this指针本质上是“成员函数”的形参,当对象调用成员函数时,将对象地址作为实参传递给this形参。所以对象中不存储this指针。
4. this指针是“成员函数”第一个隐含的指针形参,一般情况由编译器通过ecx寄存器自动传 递,不需要用户传递
【面试题】
1. this指针存在哪里?
this是一个形参,一般存在栈帧里
2. this指针可以为空吗?
// 1.下面程序编译运行结果是? A、编译报错 B、运行崩溃 C、正常运行
class A
{
public:
void Print()
{
cout << "Print()" << endl;
}
private:
int _a;
};
int main()
{
A* p = nullptr;
p->Print();
return 0;
}
//c
// 1.下面程序编译运行结果是? A、编译报错 B、运行崩溃 C、正常运行
class A
{
public:
void PrintA()
{
cout<<_a<<endl;
}
private:
int _a;
};
int main()
{
A* p = nullptr;
p->PrintA();
return 0;
}
//b
c语言和c++实现stack的对比
1. C语言实现
typedef int DataType;
typedef struct Stack
{
DataType* array;
int capacity;
int size;
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->array = (DataType*)malloc(sizeof(DataType) * 3);
if (NULL == ps->array)
{
assert(0);
return;
}
ps->capacity = 3;
ps->size = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
if (ps->array)
{
free(ps->array);
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
}
void CheckCapacity(Stack* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity * 2;
DataType* temp = (DataType*)realloc(ps->array,
newcapacity*sizeof(DataType));
if (temp == NULL)
{
perror("realloc申请空间失败!!!");
return;
}
ps->array = temp;
ps->capacity = newcapacity;
}
}
void StackPush(Stack* ps, DataType data)
{
assert(ps);
CheckCapacity(ps);
ps->array[ps->size] = data;
ps->size++;
}
int StackEmpty(Stack* ps)
{
assert(ps);
return 0 == ps->size;
}
void StackPop(Stack* ps)
{
if (StackEmpty(ps))
return;
ps->size--;
}
DataType StackTop(Stack* ps)
{
assert(!StackEmpty(ps));
return ps->array[ps->size - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->size;
}
int main()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
printf("%d\n", StackTop(&s));
printf("%d\n", StackSize(&s));
StackPop(&s);
StackPop(&s);
printf("%d\n", StackTop(&s));
printf("%d\n", StackSize(&s));
StackDestroy(&s);
return 0;
}
可以看到,在用C语言实现时,Stack相关操作函数有以下共性:
每个函数的第一个参数都是Stack*
函数中必须要对第一个参数检测,因为该参数可能会为NULL
函数中都是通过Stack*参数操作栈的
调用时必须传递Stack结构体变量的地址
结构体中只能定义存放数据的结构,操作数据的方法不能放在结构体中,即数据和操作数据 的方式是分离开的,而且实现上相当复杂一点,涉及到大量指针操作,稍不注意可能就会出错。
2. C++实现
typedef int DataType;
class Stack
{
public:
void Init()
{
_array = (DataType*)malloc(sizeof(DataType) * 3);
if (NULL == _array)
{
perror("malloc申请空间失败!!!");
return;
}
_capacity = 3;
_size = 0;
}
void Push(DataType data)
{
CheckCapacity();
_array[_size] = data;
_size++;
}
void Pop()
{
if (Empty())
return;
_size--;
}
DataType Top(){ return _array[_size - 1];}
int Empty() { return 0 == _size;}
int Size(){ return _size;}
void Destroy()
{
if (_array)
{
free(_array);
_array = NULL;
_capacity = 0;
_size = 0;
}
}
private:
void CheckCapacity()
{
if (_size == _capacity)
{
int newcapacity = _capacity * 2;
DataType* temp = (DataType*)realloc(_array, newcapacity *
sizeof(DataType));
if (temp == NULL)
{
perror("realloc申请空间失败!!!");
return;
}
_array = temp;
_capacity = newcapacity;
}
}
private:
DataType* _array;
int _capacity;
int _size;
};
int main()
{
Stack s;
s.Init();
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
printf("%d\n", s.Top());
printf("%d\n", s.Size());
s.Pop();
s.Pop();
printf("%d\n", s.Top());
printf("%d\n", s.Size());
s.Destroy();
return 0;
}
C++中通过类可以将数据 以及 操作数据的方法进行完美结合,通过访问权限可以控制那些方法在
类外可以被调用,即封装,在使用时就像使用自己的成员一样,更符合人类对一件事物的认知。
而且每个方法不需要传递Stack*的参数了,编译器编译之后该参数会自动还原,即C++中 Stack *
参数是编译器维护的,C语言中需用用户自己维护。
类与对象(中篇)
类的6个默认成员函数
如果一个类中什么成员都没有,简称为空类。
空类中真的什么都没有吗?并不是,任何类在什么都不写时,编译器会自动生成以下6个默认成员函数。
默认成员函数:用户没有显式实现,编译器会生成的成员函数称为默认成员函数。
class Date {};
构造函数
概念
对于以下Date类:
class Date
{
public:
void Init(int year, int month, int day)
{
_year = year;
_month = month;
_day = day;
}
void Print()
{
cout << _year << "-" << _month << "-" << _day << endl;
}
private:
int _year;
int _month;
int _day;
};
int main()
{
Date d1;
d1.Init(2022, 7, 5);
d1.Print();
Date d2;
d2.Init(2022, 7, 6);
d2.Print();
return 0;
}
对于Date类,可以通过 Init 公有方法给对象设置日期,但如果每次创建对象时都调用该方法设置信息,未免有点麻烦,那能否在对象创建时,就将信息设置进去呢?
构造函数是一个特殊的成员函数,名字与类名相同,创建类类型对象时由编译器自动调用,以保证每个数据成员都有 一个合适的初始值,并且在对象整个生命周期内只调用一次
特性
构造函数是特殊的成员函数,需要注意的是,构造函数虽然名称叫构造,但是构造函数的主要任务并不是开空间创建对象,而是初始化对象。
其特征如下:
1. 函数名与类名相同。
2. 无返回值。
3. 对象实例化时编译器自动调用对应的构造函数。
4. 构造函数可以重载。
class Date
{
public:
// 1.无参构造函数
Date()
{}
// 2.带参构造函数
Date(int year, int month, int day)
{
_year = year;
_month = month;
_day = day;
}
private:
int _year;
int _month;
int _day;
};
void TestDate()
{
Date d1; // 调用无参构造函数
Date d2(2015, 1, 1); // 调用带参的构造函数
// 注意:如果通过无参构造函数创建对象时,对象后面不用跟括号,否则就成了函数声明
// 以下代码的函数:声明了d3函数,该函数无参,返回一个日期类型的对象
// warning C4930: “Date d3(void)”: 未调用原型函数(是否是有意用变量定义的?)
Date d3();
}
5. 如果类中没有显式定义构造函数,则C++编译器会自动生成一个无参的默认构造函数,一旦
用户显式定义编译器将不再生成。
class Date
{
public:
/*
// 如果用户显式定义了构造函数,编译器将不再生成
Date(int year, int month, int day)
{
_year = year;
_month = month;
_day = day;
}
*/
void Print()
{
cout << _year << "-" << _month << "-" << _day << endl;
}
private:
int _year;
int _month;
int _day;
};
int main()
{
// 将Date类中构造函数屏蔽后,代码可以通过编译,因为编译器生成了一个无参的默认构造函
//数
// 将Date类中构造函数放开,代码编译失败,因为一旦显式定义任何构造函数,编译器将不再
//生成
// 无参构造函数,放开后报错:error C2512: “Date”: 没有合适的默认构造函数可用
Date d1;
return 0;
}
6. 关于编译器生成的默认成员函数,很多童鞋会有疑惑:不实现构造函数的情况下,编译器会生成默认的构造函数。但是看起来默认构造函数又没什么用?d对象调用了编译器生成的认构造函数,但是d对象_year/_month/_day,依旧是随机值。也就说在这里编译器生成的 默认构造函数并没有什么用??
解答:C++把类型分成内置类型(基本类型)和自定义类型。内置类型就是语言提供的数据类型,如:int/char...,自定义类型就是我们使用class/struct/union等自己定义的类型,看看下面的程序,就会发现编译器生成默认的构造函数会对自定类型成员_t调用的它的默认成员函数。
注意:C++11 中针对内置类型成员不初始化的缺陷,又打了补丁,即:内置类型成员变量在 类中声明时可以给默认值。
class Time
{
public:
Time()
{
cout << "Time()" << endl;
_hour = 0;
_minute = 0;
_second = 0;
}
private:
int _hour;
int _minute;
int _second;
};
class Date
{
private:
// 基本类型(内置类型)
int _year;
int _month;
int _day;
// 自定义类型
Time _t;
};
int main()
{
Date d;
return 0;
}
7. 无参的构造函数和全缺省的构造函数都称为默认构造函数,并且默认构造函数只能有一个。注意:无参构造函数、全缺省构造函数、我们没写编译器默认生成的构造函数,都可以认为是默认构造函数
class Date
{
public:
Date()
{
_year = 1900;
_month = 1;
_day = 1;
}
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
private:
int _year;
int _month;
int _day;
};
// 以下测试函数能通过编译吗?
void Test()
{
Date d1;
}
析构函数
概念
通过前面构造函数的学习,我们知道一个对象是怎么来的,那一个对象又是怎么没呢的?析构函数:与构造函数功能相反,析构函数不是完成对对象本身的销毁,局部对象销毁工作是由编译器完成的。而对象在销毁时会自动调用析构函数,完成对象中资源的清理工作
特性
析构函数是特殊的成员函数,其特征如下:
1. 析构函数名是在类名前加上字符 ~。
2. 无参数无返回值类型。
3. 一个类只能有一个析构函数。若未显式定义,系统会自动生成默认的析构函数。注意:析构函数不能重载
4. 对象生命周期结束时,C++编译系统系统自动调用析构函数
typedef int DataType;
class Stack
{
public:
Stack(size_t capacity = 3)
{
_array = (DataType*)malloc(sizeof(DataType) * capacity);
if (NULL == _array)
{
perror("malloc申请空间失败!!!");
return;
}
_capacity = capacity;
_size = 0;
}
void Push(DataType data)
{
// CheckCapacity();
_array[_size] = data;
_size++;
}
// 其他方法...
~Stack()
{
if (_array)
{
free(_array);
_array = NULL;
_capacity = 0;
_size = 0;
}
}
private:
DataType* _array;
int _capacity;
int _size;
};
void TestStack()
{
Stack s;
s.Push(1);
s.Push(2);
}
5. 关于编译器自动生成的析构函数,是否会完成一些事情呢?下面的程序我们会看到,编译器生成的默认析构函数,对自定类型成员调用它的析构函数。
class Time
{
public:
~Time()
{
cout << "~Time()" << endl;
}
private:
int _hour;
int _minute;
int _second;
};
class Date
{
private:
// 基本类型(内置类型)
int _year = 1970;
int _month = 1;
int _day = 1;
// 自定义类型
Time _t;
};
int main()
{
Date d;
return 0;
}
// 程序运行结束后输出:~Time()
// 在main方法中根本没有直接创建Time类的对象,为什么最后会调用Time类的析构函数?
// 因为:main方法中创建了Date对象d,而d中包含4个成员变量,其中_year, _month,
//_day三个是
// 内置类型成员,销毁时不需要资源清理,最后系统直接将其内存回收即可;而_t是Time类对
//象,所以在
// d销毁时,要将其内部包含的Time类的_t对象销毁,所以要调用Time类的析构函数。但是:
//main函数
// 中不能直接调用Time类的析构函数,实际要释放的是Date类对象,所以编译器会调用Date
//类的析构函
// 数,而Date没有显式提供,则编译器会给Date类生成一个默认的析构函数,目的是在其内部
//调用Time
// 类的析构函数,即当Date对象销毁时,要保证其内部每个自定义对象都可以正确销毁
// main函数中并没有直接调用Time类析构函数,而是显式调用编译器为Date类生成的默认析
//构函数
// 注意:创建哪个类的对象则调用该类的析构函数,销毁那个类的对象则调用该类的析构函数
6. 如果类中没有申请资源时,析构函数可以不写,直接使用编译器生成的默认析构函数,比如
Date类;有资源申请时,一定要写,否则会造成资源泄漏,比如Stack类
拷贝构造函数
概念
在现实生活中,可能存在一个与你一样的自己,我们称其为双胞胎
那在创建对象时,可否创建一个与已存在对象一某一样的新对象呢?
拷贝构造函数:只有单个形参,该形参是对本类类型对象的引用(一般常用const修饰),在用已存 在的类类型对象创建新对象时由编译器自动调用。
特性
拷贝构造函数也是特殊的成员函数,其特征如下:
1. 拷贝构造函数是构造函数的一个重载形式。
2. 拷贝构造函数的参数只有一个且必须是类类型对象的引用,使用传值方式编译器直接报错,因为会引发无穷递归调用。
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
// Date(const Date d) // 错误写法:编译报错,会引发无穷递归
Date(const Date& d) // 正确写法
{
_year = d._year;
_month = d._month;
_day = d._day;
}
private:
int _year;
int _month;
int _day;
};
int main()
{
Date d1;
Date d2(d1);
return 0;
}
3. 若未显式定义,编译器会生成默认的拷贝构造函数。 默认的拷贝构造函数对象按内存存储按字节序完成拷贝,这种拷贝叫做浅拷贝,或者值拷贝
class Time
{
public:
Time()
{
_hour = 1;
_minute = 1;
_second = 1;
}
Time(const Time& t)
{
_hour = t._hour;
_minute = t._minute;
_second = t._second;
cout << "Time::Time(const Time&)" << endl;
}
private:
int _hour;
int _minute;
int _second;
};
class Date
{
private:
// 基本类型(内置类型)
int _year = 1970;
int _month = 1;
int _day = 1;
// 自定义类型
Time _t;
};
int main()
{
Date d1;
// 用已经存在的d1拷贝构造d2,此处会调用Date类的拷贝构造函数
// 但Date类并没有显式定义拷贝构造函数,则编译器会给Date类生成一个默认的拷贝构
//造函数
Date d2(d1);
return 0;
}
注意:在编译器生成的默认拷贝构造函数中,内置类型是按照字节方式直接拷贝的,而自定
义类型是调用其拷贝构造函数完成拷贝的。
4. 编译器生成的默认拷贝构造函数已经可以完成字节序的值拷贝了,还需要自己显式实现吗?
当然像日期类这样的类是没必要的。那么下面的类呢?验证一下试试?
// 这里会发现下面的程序会崩溃掉?这里就需要我们以后讲的深拷贝去解决。
typedef int DataType;
class Stack
{
public:
Stack(size_t capacity = 10)
{
_array = (DataType*)malloc(capacity * sizeof(DataType));
if (nullptr == _array)
{
perror("malloc申请空间失败");
return;
}
_size = 0;
_capacity = capacity;
}
void Push(const DataType& data)
{
// CheckCapacity();
_array[_size] = data;
_size++;
}
~Stack()
{
if (_array)
{
free(_array);
_array = nullptr;
_capacity = 0;
_size = 0;
}
}
private:
DataType *_array;
size_t _size;
size_t _capacity;
};
int main()
{
Stack s1;
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.Push(4);
Stack s2(s1);
return 0;
}
注意:类中如果没有涉及资源申请时,拷贝构造函数是否写都可以;一旦涉及到资源申请
时,则拷贝构造函数是一定要写的,否则就是浅拷贝。
5. 拷贝构造函数典型调用场景:
使用已存在对象创建新对象
函数参数类型为类类型对象
函数返回值类型为类类型对象
class Date
{
public:
Date(int year, int minute, int day)
{
cout << "Date(int,int,int):" << this << endl;
}
Date(const Date& d)
{
cout << "Date(const Date& d):" << this << endl;
}
~Date()
{
cout << "~Date():" << this << endl;
}
private:
int _year;
int _month;
int _day;
};
Date Test(Date d)
{
Date temp(d);
return temp;
}
int main()
{
Date d1(2022,1,13);
Test(d1);
return 0;
}
为了提高程序效率,一般对象传参时,尽量使用引用类型,返回时根据实际场景,能用引用尽量使用引用。
赋值运算符重载
运算符重载
C++为了增强代码的可读性引入了运算符重载,运算符重载是具有特殊函数名的函数,也具有其返回值类型,函数名字以及参数列表,其返回值类型与参数列表与普通的函数类似。
函数名字为:关键字operator后面接需要重载的运算符符号。
函数原型:返回值类型 operator操作符(参数列表)
注意:
不能通过连接其他符号来创建新的操作符:比如operator@
重载操作符必须有一个类类型参数
用于内置类型的运算符,其含义不能改变,例如:内置的整型+,不 能改变其含义
作为类成员函数重载时,其形参看起来比操作数数目少1,因为成员函数的第一个参数为隐藏的this
.* :: sizeof ?: .
注意以上5个运算符不能重载。这个经常在笔试选择题中出现。
// 全局的operator==
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
//private:
int _year;
int _month;
int _day;
};
// 这里会发现运算符重载成全局的就需要成员变量是公有的,那么问题来了,封装性如何保证?
// 这里其实可以用我们后面学习的友元解决,或者干脆重载成成员函数。
bool operator==(const Date& d1, const Date& d2)
{
return d1._year == d2._year
&& d1._month == d2._month
&& d1._day == d2._day;
}
void Test ()
{
Date d1(2018, 9, 26);
Date d2(2018, 9, 27);
cout<<(d1 == d2)<<endl;
}
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
// bool operator==(Date* this, const Date& d2)
// 这里需要注意的是,左操作数是this,指向调用函数的对象
bool operator==(const Date& d2)
{
return _year == d2._year;
&& _month == d2._month
&& _day == d2._day;
}
private:
int _year;
int _month;
int _day;
};
赋值运算符重载
1.赋值运算符重载格式
参数类型:const T&,传递引用可以提高传参效率
返回值类型:T&,返回引用可以提高返回的效率,有返回值目的是为了支持连续赋值
检测是否自己给自己赋值
返回*this :要复合连续赋值的含义
class Date
{
public :
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
Date (const Date& d)
{
_year = d._year;
_month = d._month;
_day = d._day;
}
Date& operator=(const Date& d)
{
if(this != &d)
{
_year = d._year;
_month = d._month;
_day = d._day;
}
return *this;
}
private:
int _year ;
int _month ;
int _day ;
};
2. 赋值运算符只能重载成类的成员函数不能重载成全局函数
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
int _year;
int _month;
int _day;
};
// 赋值运算符重载成全局函数,注意重载成全局函数时没有this指针了,需要给两个参数
Date& operator=(Date& left, const Date& right)
{
if (&left != &right)
{
left._year = right._year;
left._month = right._month;
left._day = right._day;
}
return left;
}
// 编译失败:
// error C2801: “operator =”必须是非静态成员
原因:赋值运算符如果不显式实现,编译器会生成一个默认的。此时用户再在类外自己实现一个全局的赋值运算符重载,就和编译器在类中生成的默认赋值运算符重载冲突了,故赋值运算符重载只能是类的成员函数。
3. 用户没有显式实现时,编译器会生成一个默认赋值运算符重载,以值的方式逐字节拷贝。注意:内置类型成员变量是直接赋值的,而自定义类型成员变量需要调用对应类的赋值运算符重载完成赋值。
class Time
{
public:
Time()
{
_hour = 1;
_minute = 1;
_second = 1;
}
Time& operator=(const Time& t)
{
if (this != &t)
{
_hour = t._hour;
_minute = t._minute;
_second = t._second;
}
return *this;
}
private:
int _hour;
int _minute;
int _second;
};
class Date
{
private:
// 基本类型(内置类型)
int _year = 1970;
int _month = 1;
int _day = 1;
// 自定义类型
Time _t;
};
int main()
{
Date d1;
Date d2;
d1 = d2;
return 0;
}
既然编译器生成的默认赋值运算符重载函数已经可以完成字节序的值拷贝了,还需要自己实现吗?当然像日期类这样的类是没必要的。那么下面的类呢?验证一下试试?
// 这里会发现下面的程序会崩溃掉?这里就需要我们以后讲的深拷贝去解决。
typedef int DataType;
class Stack
{
public:
Stack(size_t capacity = 10)
{
_array = (DataType*)malloc(capacity * sizeof(DataType));
if (nullptr == _array)
{
perror("malloc申请空间失败");
return;
}
_size = 0;
_capacity = capacity;
}
void Push(const DataType& data)
{
// CheckCapacity();
_array[_size] = data;
_size++;
}
~Stack()
{
if (_array)
{
free(_array);
_array = nullptr;
_capacity = 0;
_size = 0;
}
}
private:
DataType *_array;
size_t _size;
size_t _capacity;
};
int main()
{
Stack s1;
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.Push(4);
Stack s2;
s2 = s1;
return 0;
}
注意:如果类中未涉及到资源管理,赋值运算符是否实现都可以;一旦涉及到资源管理则必
须要实现。
前置++和后置++重载
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
{
_year = year;
_month = month;
_day = day;
}
// 前置++:返回+1之后的结果
// 注意:this指向的对象函数结束后不会销毁,故以引用方式返回提高效率
Date& operator++()
{
_day += 1;
return *this;
}
// 后置++:
// 前置++和后置++都是一元运算符,为了让前置++与后置++形成能正确重载
// C++规定:后置++重载时多增加一个int类型的参数,但调用函数时该参数不用传递,编译器
自动传递
// 注意:后置++是先使用后+1,因此需要返回+1之前的旧值,故需在实现时需要先将this保存
一份,然后给this+1
// 而temp是临时对象,因此只能以值的方式返回,不能返回引用
Date operator++(int)
{
Date temp(*this);
_day += 1;
return temp;
}
private:
int _year;
int _month;
int _day;
};
int main()
{
Date d;
Date d1(2022, 1, 13);
d = d1++; // d: 2022,1,13 d1:2022,1,14
d = ++d1; // d: 2022,1,15 d1:2022,1,15
return 0;
}
日期类的实现
class Date
{
public:
// 获取某年某月的天数
int GetMonthDay(int year, int month)
{
static int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30,
31};
int day = days[month];
if (month == 2
&&((year % 4 == 0 && year % 100 != 0) || (year%400 == 0)))
{
day += 1;
}
return day;
}
// 全缺省的构造函数
Date(int year = 1900, int month = 1, int day = 1);
// 拷贝构造函数
// d2(d1)
Date(const Date& d);
// 赋值运算符重载
// d2 = d3 -> d2.operator=(&d2, d3)
Date& operator=(const Date& d);
// 析构函数
~Date();
// 日期+=天数
Date& operator+=(int day);
// 日期+天数
Date operator+(int day);
// 日期-天数
Date operator-(int day);
// 日期-=天数
Date& operator-=(int day);
// 前置++
Date& operator++();
// 后置++
Date operator++(int);
// 后置--
Date operator--(int);
// 前置--
Date& operator--();
// >运算符重载
bool operator>(const Date& d);
// ==运算符重载
bool operator==(const Date& d);
// >=运算符重载
bool operator >= (const Date& d);
// <运算符重载
bool operator < (const Date& d);
// <=运算符重载
bool operator <= (const Date& d);
// !=运算符重载
bool operator != (const Date& d);
// 日期-日期 返回天数
int operator-(const Date& d);
private:
int _year;
int _month;
int _day;
};
const成员
将const修饰的“成员函数”称之为const成员函数,const修饰类成员函数,实际修饰该成员函数隐含的this指针,表明在该成员函数中不能对类的任何成员进行修改。
class Date
{
public:
Date(int year, int month, int day)
{
_year = year;
_month = month;
_day = day;
}
void Print()
{
cout << "Print()" << endl;
cout << "year:" << _year << endl;
cout << "month:" << _month << endl;
cout << "day:" << _day << endl << endl;
}
void Print() const
{
cout << "Print()const" << endl;
cout << "year:" << _year << endl;
cout << "month:" << _month << endl;
cout << "day:" << _day << endl << endl;
}
private:
int _year; // 年
int _month; // 月
int _day; // 日
};
void Test()
{
Date d1(2022,1,13);
d1.Print();
const Date d2(2022,1,13);
d2.Print();
}
请思考下面的几个问题:
1. const对象可以调用非const成员函数吗?
不行,权限扩大
2. 非const对象可以调用const成员函数吗?
可以,权限放小
3. const成员函数内可以调用其它的非const成员函数吗?
不行,权限扩大
4. 非const成员函数内可以调用其它的const成员函数吗?
可以,权限放小
取地址及const取地址操作符重载
这两个默认成员函数一般不用重新定义,编译器默认会生成。
class Date
{
public :
Date* operator&()
{
return this ;
}
const Date* operator&()const
{
return this ;
}
private :
int _year ; // 年
int _month ; // 月
int _day ; // 日
};
这两个运算符一般不需要重载,使用编译器生成的默认取地址的重载即可,只有特殊情况,才需
要重载,比如想让别人获取到指定的内容!
类与对象(下篇)
再谈构造函数
构造函数体赋值
在创建对象时,编译器通过调用构造函数,给对象中各个成员变量一个合适的初始值
class Date
{
public:
Date(int year, int month, int day)
{
_year = year;
_month = month;
_day = day;
}
private:
int _year;
int _month;
int _day;
};
虽然上述构造函数调用之后,对象中已经有了一个初始值,但是不能将其称为对对象中成员变量的初始化, 构造函数体中的语句只能将其称为赋初值,而不能称作初始化。因为初始化只能初始化一次,而构造函数体 可以多次赋值。
初始化列表
初始化列表:以一个冒号开始,接着是一个以逗号分隔的数据成员列表,每个"成员变量"后面跟一个放在括号中的初始值或表达式。
class Date
{
public:
Date(int year, int month, int day)
: _year(year)
, _month(month)
, _day(day)
{}
private:
int _year;
int _month;
int _day;
};
【注意】
1. 每个成员变量在初始化列表中只能出现一次(初始化只能初始化一次)
2. 类中包含以下成员,必须放在初始化列表位置进行初始化:
引用成员变量
const成员变量
自定义类型成员(且该类没有默认构造函数时)
class A
{
public:
A(int a)
:_a(a)
{}
private:
int _a;
};
class B
{
public:
B(int a, int ref)
:_aobj(a)
,_ref(ref)
,_n(10)
{}
private:
A _aobj; // 没有默认构造函数
int& _ref; // 引用
const int _n; // const
};
3. 尽量使用初始化列表初始化,因为不管你是否使用初始化列表,对于自定义类型成员变量,一定会先使用初始化列表初始化。
class Time
{
public:
Time(int hour = 0)
:_hour(hour)
{
cout << "Time()" << endl;
}
private:
int _hour;
};
class Date
{
public:
Date(int day)
{}
private:
int _day;
Time _t;
};
int main()
{
Date d(1);
}
4. 成员变量在类中声明次序就是其在初始化列表中的初始化顺序,与其在初始化列表中的先后次序无关
class A
{
public:
A(int a)
:_a1(a)
,_a2(_a1)
{}
void Print() {
cout<<_a1<<" "<<_a2<<endl;
}
private:
int _a2;
int _a1;
};
int main() {
A aa(1);
aa.Print();
}
A. 输出1 1
B.程序崩溃
C.编译不通过
D.输出1 随机值
explicit关键字
构造函数不仅可以构造与初始化对象,对于接收单个参数的构造函数,还具有类型转换的作用。接收单个参数的构造函数具体表现:
1. 构造函数只有一个参数
2. 构造函数有多个参数,除第一个参数没有默认值外,其余参数都有默认值
3. 全缺省构造函数
class Date
{
public:
// 1. 单参构造函数,没有使用explicit修饰,具有类型转换作用
// explicit修饰构造函数,禁止类型转换---explicit去掉之后,代码可以通过编译
explicit Date(int year)
:_year(year)
{}
/*
// 2. 虽然有多个参数,但是创建对象时后两个参数可以不传递,没有使用explicit修饰,具有类型转
换作用
// explicit修饰构造函数,禁止类型转换
explicit Date(int year, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
*/
Date& operator=(const Date& d)
{
if (this != &d)
{
_year = d._year;
_month = d._month;
_day = d._day;
}
return *this;
}
private:
int _year;
int _month;
int _day;
};
void Test()
{
Date d1(2022);
// 用一个整形变量给日期类型对象赋值
// 实际编译器背后会用2023构造一个无名对象,最后用无名对象给d1对象进行赋值
d1 = 2023;
// 将1屏蔽掉,2放开时则编译失败,因为explicit修饰构造函数,禁止了单参构造函数类型转换的作
//用
}
上述代码可读性不是很好,用explicit修饰构造函数,将会禁止构造函数的隐式转换。
static成员
概念
声明为static的类成员称为类的静态成员,用static修饰的成员变量,称之为静态成员变量;用static修饰的成员函数,称之为静态成员函数。静态成员变量一定要在类外进行初始化
面试题:实现一个类,计算程序中创建出了多少个类对象。
class A
{
public:
A() { ++_scount; }
A(const A& t) { ++_scount; }
~A() { --_scount; }
static int GetACount() { return _scount; }
private:
static int _scount;
};
int A::_scount = 0;
void TestA()
{
cout << A::GetACount() << endl;
A a1, a2;
A a3(a1);
cout << A::GetACount() << endl;
}
特性
1. 静态成员为所有类对象所共享,不属于某个具体的对象,存放在静态区
2. 静态成员变量必须在类外定义,定义时不添加static关键字,类中只是声明
3. 类静态成员即可用 类名::静态成员 或者 对象.静态成员 来访问
4. 静态成员函数没有隐藏的this指针,不能访问任何非静态成员
5. 静态成员也是类的成员,受public、protected、private 访问限定符的限制
【问题】
1. 静态成员函数可以调用非静态成员函数吗?
不可以
2. 非静态成员函数可以调用类的静态成员函数吗?
可以
友元
友元函数
问题:现在尝试去重载operator<<,然后发现没办法将operator<<重载成成员函数。因为cout的输出流对象和隐含的this指针在抢占第一个参数的位置。this指针默认是第一个参数也就是左操作数了。但是实际使用中cout需要是第一个形参对象,才能正常使用。所以要将operator<<重载成全局函数。但又会导致类外没办法访问成员,此时就需要友元来解决。operator>>同理。
class Date
{
public:
Date(int year, int month, int day)
: _year(year)
, _month(month)
, _day(day)
{}
// d1 << cout; -> d1.operator<<(&d1, cout); 不符合常规调用
// 因为成员函数第一个参数一定是隐藏的this,所以d1必须放在<<的左侧
ostream& operator<<(ostream& _cout)
{
_cout << _year << "-" << _month << "-" << _day << endl;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
友元函数可以直接访问类的私有成员,它是定义在类外部的普通函数,不属于任何类,但需要在类的内部声明,声明时需要加friend关键字。
class Date
{
friend ostream& operator<<(ostream& _cout, const Date& d);
friend istream& operator>>(istream& _cin, Date& d);
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
istream& operator>>(istream& _cin, Date& d)
{
_cin >> d._year;
_cin >> d._month;
_cin >> d._day;
return _cin;
}
int main()
{
Date d;
cin >> d;
cout << d << endl;
return 0;
}
说明:
友元函数可访问类的私有和保护成员,但不是类的成员函数
友元函数不能用const修饰
友元函数可以在类定义的任何地方声明,不受类访问限定符限制
一个函数可以是多个类的友元函数
友元函数的调用与普通函数的调用原理相同
友元类
友元类的所有成员函数都可以是另一个类的友元函数,都可以访问另一个类中的非公有成员。友元关系是单向的,不具有交换性。
比如上述Time类和Date类,在Time类中声明Date类为其友元类,那么可以在Date类中直接访问Time类的私有成员变量,但想在Time类中访问Date类中私有的成员变量则不行。
友元关系不能传递
如果B是A的友元,C是B的友元,则不能说明C时A的友元。
友元关系不能继承,在继承位置再给大家详细介绍。
class Time
{
friend class Date; // 声明日期类为时间类的友元类,则在日期类中就直接访问Time类中的私有成
员变量
public:
Time(int hour = 0, int minute = 0, int second = 0)
: _hour(hour)
, _minute(minute)
, _second(second)
{}
private:
int _hour;
int _minute;
int _second;
};
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
void SetTimeOfDate(int hour, int minute, int second)
{
// 直接访问时间类私有的成员变量
_t._hour = hour;
_t._minute = minute;
_t._second = second;
}
private:
int _year;
int _month;
int _day;
Time _t;
};
内部类
概念:如果一个类定义在另一个类的内部,这个内部类就叫做内部类。内部类是一个独立的类,它不属于外部类,更不能通过外部类的对象去访问内部类的成员。外部类对内部类没有任何优越的访问权限。
注意:内部类就是外部类的友元类,参见友元类的定义,内部类可以通过外部类的对象参数来访问外部类中的所有成员。但是外部类不是内部类的友元。
特性:
1. 内部类可以定义在外部类的public、protected、private都是可以的。
2. 注意内部类可以直接访问外部类中的static成员,不需要外部类的对象/类名。
3. sizeof(外部类)=外部类,和内部类没有任何关系。
class A
{
private:
static int k;
int h;
public:
class B // B天生就是A的友元
{
public:
void foo(const A& a)
{
cout << k << endl;//OK
cout << a.h << endl;//OK
}
};
};
int A::k = 1;
int main()
{
A::B b;
b.foo(A());
return 0;
}
再次理解类和对象
现实生活中的实体计算机并不认识,计算机只认识二进制格式的数据。如果想要让计算机认识现实生活中的实体,用户必须通过某种面向对象的语言,对实体进行描述,然后通过编写程序,创建对象后计算机才可以认识。比如想要让计算机认识洗衣机,就需要:
1. 用户先要对现实中洗衣机实体进行抽象---即在人为思想层面对洗衣机进行认识,洗衣机有什么属性,有那些功能,即对洗衣机进行抽象认知的一个过程
2. 经过1之后,在人的头脑中已经对洗衣机有了一个清醒的认识,只不过此时计算机还不清楚,想要让计算机识别人想象中的洗衣机,就需要人通过某种面相对象的语言(比如:C++、Java、Python等)将洗衣机用类来进行描述,并输入到计算机中
3. 经过2之后,在计算机中就有了一个洗衣机类,但是洗衣机类只是站在计算机的角度对洗衣机对象进行描述的,通过洗衣机类,可以实例化出一个个具体的洗衣机对象,此时计算机才能洗衣机是什么东西。
4. 用户就可以借助计算机中洗衣机对象,来模拟现实中的洗衣机实体了。
在类和对象阶段,大家一定要体会到,类是对某一类实体(对象)来进行描述的,描述该对象具有那些属性,那些方法,描述完成后就形成了一种新的自定义类型,才用该自定义类型就可以实例化具体的对象。
c&c++内存管理
c/c++内存分布
我们先来看下面的一段代码和相关问题
int globalVar = 1;
static int staticGlobalVar = 1;
void Test()
{
static int staticVar = 1;
int localVar = 1;
int num1[10] = { 1, 2, 3, 4 };
char char2[] = "abcd";
const char* pChar3 = "abcd";
int* ptr1 = (int*)malloc(sizeof(int) * 4);
int* ptr2 = (int*)calloc(4, sizeof(int));
int* ptr3 = (int*)realloc(ptr2, sizeof(int) * 4);
free(ptr1);
free(ptr3);
}
1. 选择题:
选项: A.栈 B.堆 C.数据段(静态区) D.代码段(常量区)
globalVar在哪里?____ staticGlobalVar在哪里?____
staticVar在哪里?____ localVar在哪里?____
num1 在哪里?____
char2在哪里?____ *char2在哪里?___
pChar3在哪里?____ *pChar3在哪里?____
ptr1在哪里?____ *ptr1在哪里?____
2. 填空题:
sizeof(num1) = ____;
sizeof(char2) = ____; strlen(char2) = ____;
sizeof(pChar3) = ____; strlen(pChar3) = ____;
sizeof(ptr1) = ____;
3. sizeof 和 strlen 区别?
【说明】
1. 栈又叫堆栈--非静态局部变量/函数参数/返回值等等,栈是向下增长的。
2. 内存映射段是高效的I/O映射方式,用于装载一个共享的动态内存库。用户可使用系统接口创建共享共享内存,做进程间通信。(Linux课程如果没学到这块,现在只需要了解一下)
3. 堆用于程序运行时动态内存分配,堆是可以上增长的。
4. 数据段--存储全局数据和静态数据。
5. 代码段--可执行的代码/只读常量。
c语言中动态内存管理方式malloc/calloc/realloc
void Test ()
{
int* p1 = (int*) malloc(sizeof(int));
free(p1);
// 1.malloc/calloc/realloc的区别是什么?
int* p2 = (int*)calloc(4, sizeof (int));
int* p3 = (int*)realloc(p2, sizeof(int)*10);
// 这里需要free(p2)吗?
free(p3 );
}
【面试题】
1. malloc/calloc/realloc的区别?
calloc==malloc+memset
1,是否会对申请的内存空间进行初始化
函数malloc
不能初始化所分配的内存空间,函数calloc()
会将所分配的内存空间中的每一位都初始化为零
2,功能上的区别
malloc与calloc用来动态分配内存空间,而realloc则是对给定的指针所指向的内存空间进行扩大或者缩小。
2. malloc的实现原理?
c++内存管理方式
new/delete操作内置类型
void Test()
{
// 动态申请一个int类型的空间
int* ptr4 = new int;
// 动态申请一个int类型的空间并初始化为10
int* ptr5 = new int(10);
// 动态申请10个int类型的空间
int* ptr6 = new int[10];
delete ptr4;
delete ptr5;
delete[] ptr6;
}
注意:申请和释放单个元素的空间,使用new和delete操作符,申请和释放连续的空间,使用new[]和 delete[],注意:匹配起来使用。匹配使用!
new/delete操作自定义类型
class A
{
public:
A(int a = 0)
: _a(a)
{
cout << "A():" << this << endl;
}
~A()
{
cout << "~A():" << this << endl;
}
private:
int _a;
};
int main()
{
// new/delete 和 malloc/free最大区别是 new/delete对于【自定义类型】除了开空间还会调用构
//造函数和析构函数
A* p1 = (A*)malloc(sizeof(A));
A* p2 = new A(1);
free(p1);
delete p2;
// 内置类型是几乎是一样的
int* p3 = (int*)malloc(sizeof(int)); // C
int* p4 = new int;
free(p3);
delete p4;
A* p5 = (A*)malloc(sizeof(A)*10);
A* p6 = new A[10];
free(p5);
delete[] p6;
return 0;
}
注意:在申请自定义类型的空间时,new会调用构造函数,delete会调用析构函数,而malloc与free不会。
operator new 与operator delete 函数
operator new与operator delete函数(重点)
new和delete是用户进行动态内存申请和释放的操作符,operator new 和operator delete是系统提供的全局函数,new在底层调用operator new全局函数来申请空间,delete在底层通过operator delete全局函数来释放空间。
/*
operator new:该函数实际通过malloc来申请空间,当malloc申请空间成功时直接返回;申请空间失败,
尝试执行空 间不足应对措施,如果改应对措施用户设置了,则继续申请,否则抛异常。
*/
void *__CRTDECL operator new(size_t size) _THROW1(_STD bad_alloc)
{
// try to allocate size bytes
void *p;
while ((p = malloc(size)) == 0)
if (_callnewh(size) == 0)
{
// report no memory
// 如果申请内存失败了,这里会抛出bad_alloc 类型异常
static const std::bad_alloc nomem;
_RAISE(nomem);
}
return (p);
}
/*
operator delete: 该函数最终是通过free来释放空间的
*/
void operator delete(void *pUserData)
{
_CrtMemBlockHeader * pHead;
RTCCALLBACK(_RTC_Free_hook, (pUserData, 0));
if (pUserData == NULL)
return;
_mlock(_HEAP_LOCK); /* block other threads */
__TRY
/* get a pointer to memory block header */
pHead = pHdr(pUserData);
/* verify block type */
_ASSERTE(_BLOCK_TYPE_IS_VALID(pHead->nBlockUse));
_free_dbg( pUserData, pHead->nBlockUse );
__FINALLY
_munlock(_HEAP_LOCK); /* release other threads */
__END_TRY_FINALLY
return;
}
/*
free的实现
*/
#define free(p) _free_dbg(p, _NORMAL_BLOCK)
通过上述两个全局函数的实现知道,operator new 实际也是通过malloc来申请空间,如果malloc申请空间成功就直接返回,否则执行用户提供的空间不足应对措施,如果用户提供该措施就继续申请,否则就抛异常。operator delete 最终是
new和delete的实现原理
5.1 内置类型
如果申请的是内置类型的空间,new和malloc,delete和free基本类似,不同的地方是:new/delete申请和释放的是单个元素的空间,new[]和delete[]申请的是连续空间,而且new在申请空间失败时会抛异常,
malloc会返回NULL。
5.2 自定义类型
new的原理
1. 调用operator new函数申请空间
2. 在申请的空间上执行构造函数,完成对象的构造
delete的原理
1. 在空间上执行析构函数,完成对象中资源的清理工作
2. 调用operator delete函数释放对象的空间
new T[N]的原理
1. 调用operator new[]函数,在operator new[]中实际调用operator new函数完成N个对象空间的申请
2. 在申请的空间上执行N次构造函数
delete[]的原理
1. 在释放的对象空间上执行N次析构函数,完成N个对象中资源的清理
2. 调用operator delete[]释放空间,实际在operator delete[]中调用operator delete来释放空间
定位new表达式(placement-new)
定位new表达式是在已分配的原始内存空间中调用构造函数初始化一个对象。
使用格式:
new (place_address) type或者new (place_address) type(initializer-list)
place_address必须是一个指针,initializer-list是类型的初始化列表
使用场景:
定位new表达式在实际中一般是配合内存池使用。因为内存池分配出的内存没有初始化,所以如果是自定义类型的对象,需要使用new的定义表达式进行显示调构造函数进行初始化。
class A
{
public:
A(int a = 0)
: _a(a)
{
cout << "A():" << this << endl;
}
~A()
{
cout << "~A():" << this << endl;
}
private:
int _a;
};
// 定位new/replacement new
int main()
{
// p1现在指向的只不过是与A对象相同大小的一段空间,还不能算是一个对象,因为构造函数没有执行
A* p1 = (A*)malloc(sizeof(A));
new(p1)A; // 注意:如果A类的构造函数有参数时,此处需要传参
p1->~A();
free(p1);
A* p2 = (A*)operator new(sizeof(A));
new(p2)A(10);
p2->~A();
operator delete(p2);
return 0;
}
常见面试题
malloc/free和new/delete的区别
malloc/free和new/delete的共同点是:都是从堆上申请空间,并且需要用户手动释放。不同的地方是:
1. malloc和free是函数,new和delete是操作符
2. malloc申请的空间不会初始化,new可以初始化
3. malloc申请空间时,需要手动计算空间大小并传递,new只需在其后跟上空间的类型即可, 如果是多个
对象,[]中指定对象个数即可
4. malloc的返回值为void*, 在使用时必须强转,new不需要,因为new后跟的是空间的类型
5. malloc申请空间失败时,返回的是NULL,因此使用时必须判空,new不需要,但是new需要捕获异常
6. 申请自定义类型对象时,malloc/free只会开辟空间,不会调用构造函数与析构函数,而new在申请空间
后会调用构造函数完成对象的初始化,delete在释放空间前会调用析构函数完成空间中资源的清理
前5条是用法,最后一条是底层操作
内存泄漏
什么是内存泄漏,内存泄漏的危害
什么是内存泄漏:内存泄漏指因为疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏并不是指内存在物理上的消失,而是应用程序分配某段内存后,因为设计错误,失去了对该段内存的控制,因而造成了内存的浪费。
内存泄漏的危害:长期运行的程序出现内存泄漏,影响很大,如操作系统、后台服务等等,出现内存泄漏会导致响应越来越慢,最终卡死。
void MemoryLeaks()
{
// 1.内存申请了忘记释放
int* p1 = (int*)malloc(sizeof(int));
int* p2 = new int;
// 2.异常安全问题
int* p3 = new int[10];
Func(); // 这里Func函数抛异常导致 delete[] p3未执行,p3没被释放.
delete[] p3;
}
内存泄漏的分类(了解)
C/C++程序中一般我们关心两种方面的内存泄漏:
堆内存泄漏(Heap leak)
堆内存指的是程序执行中依据须要分配通过malloc / calloc / realloc / new等从堆中分配的一块内存,用完后必须通过调用相应的 free或者delete 删掉。假设程序的设计错误导致这部分内存没有被释放,那么以后这部分空间将无法再被使用,就会产生Heap Leak。
系统资源泄漏指程序使用系统分配的资源,比方套接字、文件描述符、管道等没有使用对应的函数释放掉,导致系统资源的浪费,严重可导致系统效能减少,系统执行不稳定。
如何检测内存泄漏(了解)
在vs下,可以使用windows操作系统提供的_CrtDumpMemoryLeaks() 函数进行简单检测,该函数只报出了大概泄漏了多少个字节,没有其他更准确的位置信息。
int main()
{
int* p = new int[10];
// 将该函数放在main函数之后,每次程序退出的时候就会检测是否存在内存泄漏
_CrtDumpMemoryLeaks();
return 0;
}
// 程序退出后,在输出窗口中可以检测到泄漏了多少字节,但是没有具体的位置
Detected memory leaks!
Dumping objects ->
{79} normal block at 0x00EC5FB8, 40 bytes long.
Data: < > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD
Object dump complete.
因此写代码时一定要小心,尤其是动态内存操作时,一定要记着释放。但有些情况下总是防不胜防,简单的可以采用上述方式快速定位下。如果工程比较大,内存泄漏位置比较多,不太好查时一般都是借助第三方内存泄漏检测工具处理的。
在linux下内存泄漏检测:Linux下几款C++程序中的内存泄露检查工具_c++内存泄露工具分析-CSDN博客
在windows下使用第三方工具:VS编程内存泄漏:VLD(Visual LeakDetector)内存泄露库_visual leak detector vs2020-CSDN博客
其他工具:内存泄露检测工具比较 - 默默淡然 - 博客园
如何避免内存泄漏
1. 工程前期良好的设计规范,养成良好的编码规范,申请的内存空间记着匹配的去释放。ps:这个理想状态。但是如果碰上异常时,就算注意释放了,还是可能会出问题。需要下一条智能指针来管理才有保证。
2. 采用RAII思想或者智能指针来管理资源。
3. 有些公司内部规范使用内部实现的私有内存管理库。这套库自带内存泄漏检测的功能选项。
4. 出问题了使用内存泄漏工具检测。ps:不过很多工具都不够靠谱,或者收费昂贵。
总结一下:
内存泄漏非常常见,解决方案分为两种:1、事前预防型。如智能指针等。2、事后查错型。如泄漏检测工具。
模版初阶
泛型编程
如何实现一个通用的交换函数呢?
void Swap(int& left, int& right)
{
int temp = left;
left = right;
right = temp;
}
void Swap(double& left, double& right)
{
double temp = left;
left = right;
right = temp;
}
void Swap(char& left, char& right)
{
char temp = left;
left = right;
right = temp;
}
......
使用函数重载虽然可以实现,但是有一下几个不好的地方:
1. 重载的函数仅仅是类型不同,代码复用率比较低,只要有新类型出现时,就需要用户自己增加对应的函数
2. 代码的可维护性比较低,一个出错可能所有的重载均出错
那能否告诉编译器一个模子,让编译器根据不同的类型利用该模子来生成代码呢?
如果在C++中,也能够存在这样一个模具,通过给这个模具中填充不同材料(类型),来获得不同材料的铸件 (即生成具体类型的代码),那将会节省许多头发。巧的是前人早已将树栽好,我们只需在此乘凉。
泛型编程:编写与类型无关的通用代码,是代码复用的一种手段。模板是泛型编程的基础
函数模版
函数模版概念
函数模板代表了一个函数家族,该函数模板与类型无关,在使用时被参数化,根据实参类型产生函数的特定类型版本。
函数模版格式
template<typename T1, typename T2,......,typename Tn>
返回值类型 函数名(参数列表){}
template<typename T>
void Swap( T& left, T& right)
{
T temp = left;
left = right;
right = temp;
}
注意:typename是用来定义模板参数关键字,也可以使用class(切记:不能使用struct代替class)
函数模版原理
那么如何解决上面的问题呢?大家都知道,瓦特改良蒸汽机,人类开始了工业革命,解放了生产力。机器生产淘汰掉了很多手工产品。本质是什么,重复的工作交给了机器去完成。有人给出了论调:懒人创造世界。
函数模板是一个蓝图,它本身并不是函数,是编译器用使用方式产生特定具体类型函数的模具。所以其实模板就是将本来应该我们做的重复的事情交给了编译器
在编译器编译阶段,对于模板函数的使用,编译器需要根据传入的实参类型来推演生成对应类型的函数以供调用。比如:当用double类型使用函数模板时,编译器通过对实参类型的推演,将T确定为double类型,然后产生一份专门处理double类型的代码,对于字符类型也是如此
函数模版实例化
用不同类型的参数使用函数模板时,称为函数模板的实例化。模板参数实例化分为:隐式实例化和显式实例化。
1. 隐式实例化:让编译器根据实参推演模板参数的实际类型
template<class T>
T Add(const T& left, const T& right)
{
return left + right;
}
int main()
{
int a1 = 10, a2 = 20;
double d1 = 10.0, d2 = 20.0;
Add(a1, a2);
Add(d1, d2);
/*
该语句不能通过编译,因为在编译期间,当编译器看到该实例化时,需要推演其实参类型
通过实参a1将T推演为int,通过实参d1将T推演为double类型,但模板参数列表中只有一个T,
编译器无法确定此处到底该将T确定为int 或者 double类型而报错
注意:在模板中,编译器一般不会进行类型转换操作,因为一旦转化出问题,编译器就需要背黑锅
Add(a1, d1);
*/
// 此时有两种处理方式:1. 用户自己来强制转化 2. 使用显式实例化
Add(a, (int)d);
return 0;
}
2. 显式实例化:在函数名后的<>中指定模板参数的实际类型
int main(void)
{
int a = 10;
double b = 20.0;
// 显式实例化
Add<int>(a, b);
return 0;
}
如果类型不匹配,编译器会尝试进行隐式类型转换,如果无法转换成功编译器将会报错
函数模版的匹配原则
1. 一个非模板函数可以和一个同名的函数模板同时存在,而且该函数模板还可以被实例化为这个非模板函数
// 专门处理int的加法函数
int Add(int left, int right)
{
return left + right;
}
// 通用加法函数
template<class T>
T Add(T left, T right)
{
return left + right;
}
void Test()
{
Add(1, 2); // 与非模板函数匹配,编译器不需要特化
Add<int>(1, 2); // 调用编译器特化的Add版本
}
2. 对于非模板函数和同名函数模板,如果其他条件都相同,在调动时会优先调用非模板函数而不会从该模 板产生出一个实例。如果模板可以产生一个具有更好匹配的函数, 那么将选择模板
// 专门处理int的加法函数
int Add(int left, int right)
{
return left + right;
}
// 通用加法函数
template<class T1, class T2>
T1 Add(T1 left, T2 right)
{
return left + right;
}
void Test()
{
Add(1, 2); // 与非函数模板类型完全匹配,不需要函数模板实例化
Add(1, 2.0); // 模板函数可以生成更加匹配的版本,编译器根据实参生成更加匹配的Add函
//数
}
3. 模板函数不允许自动类型转换,但普通函数可以进行自动类型转换
类模版
类模版的定义格式
template<class T1, class T2, ..., class Tn>
class 类模板名
{
// 类内成员定义
};
// 动态顺序表
// 注意:Vector不是具体的类,是编译器根据被实例化的类型生成具体类的模具
template<class T>
class Vector
{
public :
Vector(size_t capacity = 10)
: _pData(new T[capacity])
, _size(0)
, _capacity(capacity)
{}
// 使用析构函数演示:在类中声明,在类外定义。
~Vector();
void PushBack(const T& data);
void PopBack();
// ...
size_t Size() {return _size;}
T& operator[](size_t pos)
{
assert(pos < _size);
return _pData[pos];
}
private:
T* _pData;
size_t _size;
size_t _capacity;
};
// 注意:类模板中函数放在类外进行定义时,需要加模板参数列表
template <class T>
Vector<T>::~Vector()
{
if(_pData)
delete[] _pData;
_size = _capacity = 0;
}
类模版的实例化
类模板实例化与函数模板实例化不同,类模板实例化需要在类模板名字后跟<>,然后将实例化的类型放在<>中即可,类模板名字不是真正的类,而实例化的结果才是真正的类
// Vector类名,Vector<int>才是类型
Vector<int> s1;
Vector<double> s2;
STL简介
什么是STL
STL(standard template libaray-标准模板库):是C++标准库的重要组成部分,不仅是一个可复用的组件库,而且是一个包罗数据结构与算法的软件框架
STL版本
原始版本
Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本,本着开源精神,他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码,无需付费。唯一的条件就是也需要向原始版本一样做开源使用。 HP 版本--所有STL实现版本的始祖。
P. J. 版本
由P. J. Plauger开发,继承自HP版本,被Windows Visual C++采用,不能公开或修改,缺陷:可读性比较低,符号命名比较怪异。
RW版本
由Rouge Wage公司开发,继承自HP版本,被C+ + Builder 采用,不能公开或修改,可读性一般。
SGI版本
由Silicon Graphics Computer Systems,Inc公司开发,继承自HP版 本。被GCC(Linux)采用,可移植性好,可公开、修改甚至贩卖,从命名风格和编程 风格上看,阅读性非常高。我们后面学习STL要阅读部分源代码,主要参考的就是这个版本。
STL六大组件
STL重要性
1. 在笔试中
二叉数层序打印
重建二叉树
两个栈实现一个队列
2. 在面试中
网上有句话说:“不懂STL,不要说你会C++”。STL是C++中的优秀作品,有了它的陪伴,许多底层的数据结构以及算法都不需要自己重新造轮子,站在前人的肩膀上,健步如飞的快速开发。
如何学习STL
简单总结一下:学习STL的三个境界:能用,明理,能扩展
STL缺陷
1. STL库的更新太慢了。这个得严重吐槽,上一版靠谱是C++98,中间的C++03基本一些修订。C++11出来已经相隔了13年,STL才进一步更新。
2. STL现在都没有支持线程安全。并发环境下需要我们自己加锁。且锁的粒度是比较大的。
3. STL极度的追求效率,导致内部比较复杂。比如类型萃取,迭代器萃取。
4. STL的使用会有代码膨胀的问题,比如使用vector/vector/vector这样会生成多份代码,当然这是模板语法本身导致的。
string
为什么学习string类
c语言的字符串
C语言中,字符串是以'\0'结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数,但是这些库函数与字符串是分离开的,不太符合OOP的思想,而且底层空间需要用户自己管理,稍不留神可能还会越界访问
两个面试题
字符串转整形数字
字符串相加
在OJ中,有关字符串的题目基本以string类的形式出现,而且在常规工作中,为了简单、方便、快捷,基本都使用string类,很少有人去使用C库中的字符串操作函数。
标准库中的string类
string类
string类的文档介绍
1. 字符串是表示字符序列的类
2. 标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专门用于操作单字节字符字符串的设计特性。
3. string类是使用char(即作为它的字符类型,使用它的默认char_traits和分配器类型(关于模板的更多信息,请参阅basic_string)。
4. string类是basic_string模板类的一个实例,它使用char来实例化basic_string模板类,并用char_traits和allocator作为basic_string的默认参数(根于更多的模板信息请参考basic_string)。
5. 注意,这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如UTF-8)的序列,这个类的所有成员(如长度或大小)以及它的迭代器,将仍然按照字节(而不是实际编码的字符)来操作。
总结:
1. string是表示字符串的字符串类
2. 该类的接口与常规容器的接口基本相同,再添加了一些专门用来操作string的常规操作
3. string在底层实际是:basic_string模板类的别名,typedef basic_string<char, char_traits, allocator>string;
4. 不能操作多字节或者变长字符的序列。
在使用string类时,必须包含#include头文件以及using namespace std;
string类的常用接口说明
1. string类对象的常见构造
void Teststring()
{
string s1; // 构造空的string类对象s1
string s2("hello bit"); // 用C格式字符串构造string类对象s2
string s3(s2); // 拷贝构造s3
}
2. string类对象的容量操作
string容量相关方法使用代码演示
注意:
1. size()与length()方法底层实现原理完全相同,引入size()的原因是为了与其他容器的接口保持一
致,一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空,不改变底层空间大小。
3. resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个,不同的是当字符个数增多时:resize(n)用0来填充多出的元素空间,resize(size_t n, char c)用字符c来填充多出的元素空间。注意:resize在改变元素个数时,如果是将元素个数增多,可能会改变底层容量的大小,如果是将元素个数减少,底层空间总大小不变。
4. reserve(size_t res_arg=0):为string预留空间,不改变有效元素个数,当reserve的参数小于string的底层空间总大小时,reserver不会改变容量大小。
4. string类对象的修改操作
注意:
1. 在string尾部追加字符时,s.push_back(c) / s.append(1, c) / s += 'c'三种的实现方式差不多,一般情况下string类的+=操作用的比较多,+=操作不仅可以连接单个字符,还可以连接字符串。
2. 对string操作时,如果能够大概预估到放多少字符,可以先通过reserve把空间预留好。
5. string类非成员函数
上面的几个接口大家了解一下,下面的OJ题目中会有一些体现他们的使用。string类中还有一些其他的操作,这里不一一列举,大家在需要用到时不明白了查文档即可。
6. vs和g++下string结构的说明
注意:下述结构是在32位平台下进行验证,32位平台下指针占4个字节。
vs下string的结构
string总共占28个字节,内部结构稍微复杂一点,先是有一个联合体,联合体用来定义string中字
符串的存储空间:
当字符串长度小于16时,使用内部固定的字符数组来存放
当字符串长度大于等于16时,从堆上开辟空间
union _Bxty
{ // storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE];
pointer _Ptr;
char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;
这种设计也是有一定道理的,大多数情况下字符串的长度都小于16,那string对象创建好之后,内
部已经有了16个字符数组的固定空间,不需要通过堆创建,效率高。
其次:还有一个size_t字段保存字符串长度,一个size_t字段保存从堆上开辟空间总的容量
最后:还有一个指针做一些其他事情。
故总共占16+4+4+4=28个字节。
g++下string的结构
G++下,string是通过写时拷贝实现的,string对象总共占4个字节,内部只包含了一个指针,该指
针将来指向一块堆空间,内部包含了如下字段:
空间总大小
字符串有效长度
引用计数
指向堆空间的指针,用来存储字符串。
3. string类对象的访问及遍历操作
string类的模拟实现
经典的string类问题
上面已经对string类进行了简单的介绍,大家只要能够正常使用即可。在面试中,面试官总喜欢让学生自己来模拟实现string类,最主要是实现string类的构造、拷贝构造、赋值运算符重载以及析构函数。大家看下以下string类的实现是否有问题?
// 为了和标准库区分,此处使用String
class String
{
public:
/*String()
:_str(new char[1])
{*_str = '\0';}
*/
//String(const char* str = "\0") 错误示范
//String(const char* str = nullptr) 错误示范
String(const char* str = "")
{
// 构造String类对象时,如果传递nullptr指针,可以认为程序非
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
// 测试
void TestString()
{
String s1("hello bit!!!");
String s2(s1);
}
说明:上述String类没有显式定义其拷贝构造函数与赋值运算符重载,此时编译器会合成默认的,当用s1构造s2时,编译器会调用默认的拷贝构造。最终导致的问题是,s1、s2共用同一块内存空间,在释放时同一块空间被释放多次而引起程序崩溃,这种拷贝方式,称为浅拷贝。
浅拷贝
浅拷贝:也称位拷贝,编译器只是将对象中的值拷贝过来。如果对象中管理资源,最后就会导致多个对象共享同一份资源,当一个对象销毁时就会将该资源释放掉,而此时另一些对象不知道该资源已经被释放,以为还有效,所以当继续对资源进项操作时,就会发生发生了访问违规。
就像一个家庭中有两个孩子,但父母只买了一份玩具,两个孩子愿意一块玩,则万事大吉,万一不想分享就你争我夺,玩具损坏。
可以采用深拷贝解决浅拷贝问题,即:每个对象都有一份独立的资源,不要和其他对象共享。父母给每个孩子都买一份玩具,各自玩各自的就不会有问题了
深拷贝
如果一个类中涉及到资源的管理,其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供。
传统版写法的string类
class String
{
public:
String(const char* str = "")
{
// 构造String类对象时,如果传递nullptr指针,可以认为程序非
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
}
String& operator=(const String& s)
{
if (this != &s)
{
char* pStr = new char[strlen(s._str) + 1];
strcpy(pStr, s._str);
delete[] _str;
_str = pStr;
}
return *this;
}
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
现代版写法的string类
class String
{
public:
String(const char* str = "")
{
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(nullptr)
{
String strTmp(s._str);
swap(_str, strTmp._str);
}
// 对比下和上面的赋值那个实现比较好?
String& operator=(String s)
{
swap(_str, s._str);
return *this;
}
/*
String& operator=(const String& s)
{
if(this != &s)
{
String strTmp(s);
swap(_str, strTmp._str);
}
return *this;
}
*/
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
写时拷贝就是一种拖延症,是在浅拷贝的基础之上增加了引用计数的方式来实现的。
引用计数:用来记录资源使用者的个数。在构造时,将资源的计数给成1,每增加一个对象使用该资源,就给计数增加1,当某个对象被销毁时,先给该计数减1,然后再检查是否需要释放资源,如果计数为1,说明该对象时资源的最后一个使用者,将该资源释放;否则就不能释放,因为还有其他对象在使用该资源。
C++ STL string的Copy-On-Write技术 | 酷 壳 - CoolShell
C++的std::string的“读时也拷贝”技术! | 酷 壳 - CoolShell
string类模拟实现
会另发一篇博客进行详细实现
扩展阅读
C++面试中string类的一种正确写法 | 酷 壳 - CoolShell
STL 的string类怎么啦?_string拥有庞大字符串 c++-CSDN博客
STL 的string类怎么啦?_stl为什么要搞出string-CSDN博客
vector
vector的介绍及使用
vector的介绍
https://cplusplus.com/reference/vector/vector/
1. vector是表示可变大小数组的序列容器。
2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完的。
5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。
使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习
vector的使用
vector的定义
https://cplusplus.com/reference/vector/vector/vector/
vector iterator 的使用
https://cplusplus.com/reference/vector/vector/begin/
https://cplusplus.com/reference/vector/vector/rbegin/
https://cplusplus.com/reference/vector/vector/rend/
vector 空间增长问题
https://cplusplus.com/reference/vector/vector/size/
https://cplusplus.com/reference/vector/vector/capacity/
https://cplusplus.com/reference/vector/vector/empty/
https://cplusplus.com/reference/vector/vector/resize/
https://cplusplus.com/reference/vector/vector/reserve/
capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义 的。vs是PJ版本STL,g++是SGI版本STL。
reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化,影响size
// 测试vector的默认扩容机制
void TestVectorExpand()
{
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g++运行结果:linux下使用的STL基本是按照2倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
// 如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
vector<int> v;
size_t sz = v.capacity();
v.reserve(100); // 提前将容量设置好,可以避免一遍插入一遍扩容
cout << "making bar grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
vector 增删查改
https://cplusplus.com/reference/vector/vector/push_back/
https://cplusplus.com/reference/vector/vector/pop_back/
https://cplusplus.com/reference/algorithm/find/?kw=find
https://cplusplus.com/reference/vector/vector/insert/
https://cplusplus.com/reference/vector/vector/erase/
https://cplusplus.com/reference/vector/vector/swap/
https://cplusplus.com/reference/vector/vector/operator%5B%5D/
vector插入和删除做操作示例
vector 迭代器失效问题。(重点)
迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装,比如:vector的迭代器就是原生态指针T* 。因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有:
1. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
// 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容
// v.resize(100, 8);
// reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变
// v.reserve(100);
// 插入元素期间,可能会引起扩容,而导致原空间被释放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 给vector重新赋值,可能会引起底层容量改变
v.assign(100, 8);
/*
出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉,
而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的
空间,而引起代码运行时崩溃。
解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新
赋值即可。
*/
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout<<endl;
return 0;
}
2. 指定位置元素的删除操作--erase
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 删除pos位置的数据,导致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此处会导致非法访问
return 0;
}
erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了。因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了。
以下代码的功能是删除vector中所有的偶数,请问那个代码是正确的,为什么?
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
return 0;
}
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
return 0;
}
从上述三个例子中可以看到:SGI STL中,迭代器失效后,代码并不一定会崩溃,但是运行结果肯定不对,如果it不在begin和end范围内,肯定会崩溃的。
4. 与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效
vector 在OJ中的使用
1.
只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
int value = 0;
for(auto e : v) {value ^= e; }
return value;
}
};
2.
杨辉三角
// 涉及resize / operator[]
// 核心思想:找出杨辉三角的规律,发现每一行头尾都是1,中间第[j]个数等于上一行[j-1]+[j]
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for(int i = 0; i < numRows; ++i)
{
vv[i].resize(i+1, 1);
}
for(int i = 2; i < numRows; ++i)
{
for(int j = 1; j < i; ++j)
{
vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
}
}
return vv;
}
};
总结:通过上面的练习我们发现vector常用的接口更多是插入和遍历。遍历更喜欢用数组operator[i]的形式访问,因为这样便捷。课下自己实现一遍上面课堂讲解的OJ练习,然后请自行完成下面题目的OJ练习。以此增强学习vector的使用。
3. 删除有序数组中的重复项
vector深度剖析及模拟实现
std::vector的核心框架接口的模拟实现
使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中,使用memcpy进行的拷贝,以下代码会发生什么问题?
int main()
{
bite::vector<bite::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
问题分析:
1. memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是内置类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。
动态二维数组理解
// 以杨慧三角的前n行为例:假设n为5
void test2vector(size_t n)
{
// 使用vector定义二维数组vv,vv中的每个元素都是vector<int>
bit::vector<bit::vector<int>> vv(n);
// 将二维数组每一行中的vecotr<int>中的元素全部设置为1
for (size_t i = 0; i < n; ++i)
vv[i].resize(i + 1, 1);
// 给杨慧三角出第一列和对角线的所有元素赋值
for (int i = 2; i < n; ++i)
{
for (int j = 1; j < i; ++j)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
list
list介绍及使用
list介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list使用
https://cplusplus.com/reference/list/list/list/
list的构造使用代码演示
ist iterator的使用
此处,可暂时将迭代器理解成一个指针,该指针指向list中的某个节点。
https://cplusplus.com/reference/list/list/begin/
https://cplusplus.com/reference/list/list/end/
https://cplusplus.com/reference/list/list/rbegin/
https://cplusplus.com/reference/list/list/rend/
【注意】
1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动
list capacity
https://cplusplus.com/reference/list/list/empty/
https://cplusplus.com/reference/list/list/size/
list element access
https://cplusplus.com/reference/list/list/front/
https://cplusplus.com/reference/list/list/back/
list modifiers
https://cplusplus.com/reference/list/list/push_front/
https://cplusplus.com/reference/list/list/pop_front/
https://cplusplus.com/reference/list/list/push_back/
https://cplusplus.com/reference/list/list/pop_back/
https://cplusplus.com/reference/list/list/insert/
https://cplusplus.com/reference/list/list/erase/
https://cplusplus.com/reference/list/list/swap/
https://cplusplus.com/reference/list/list/clear/
list的迭代器失效
前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给
其赋值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}
list的模拟实现
模拟实现list
要模拟实现list,必须要熟悉list的底层结构以及其接口的含义,通过上面的学习,这些内容已基本掌握,现在我们来模拟实现list。
list反向迭代器
通过前面例子知道,反向迭代器的++就是正向迭代器的--,反向迭代器的--就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可。
template<class Iterator>
class ReverseListIterator
{
// 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的类型,而不是静态成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
//
// 构造
ReverseListIterator(Iterator it): _it(it){}
//
// 具有指针类似行为
Ref operator*(){
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->(){ return &(operator*());}
//
// 迭代器支持移动
Self& operator++(){
--_it;
return *this;
}
Self operator++(int){
Self temp(*this);
--_it;
return temp;
}
Self& operator--(){
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
//
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it != l._it;}
Iterator _it;
};
list与vector的对比
vector与list都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同,其主要不同如下:
stack和queue
stack的介绍和使用
stack的介绍
翻译:
1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
empty:判空操作
back:获取尾部元素操作
push_back:尾部插入元素操作
pop_back:尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。
stack的使用
https://cplusplus.com/reference/stack/stack/stack/
https://cplusplus.com/reference/stack/stack/empty/
https://cplusplus.com/reference/stack/stack/size/
https://cplusplus.com/reference/stack/stack/empty/
https://cplusplus.com/reference/stack/stack/push/
https://cplusplus.com/reference/stack/stack/pop/
stack的模拟实现
从栈的接口中可以看出,栈实际是一种特殊的vector,因此使用vector完全可以模拟实现stack。
#include<vector>
namespace bite
{
template<class T>
class stack
{
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::vector<T> _c;
};
}
queue的介绍和使用
queue的介绍
翻译:
1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty:检测队列是否为空
size:返回队列中有效元素的个数
front:返回队头元素的引用
back:返回队尾元素的引用
push_back:在队列尾部入队列
pop_front:在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。
queue的使用
https://cplusplus.com/reference/queue/queue/queue/
https://cplusplus.com/reference/queue/queue/empty/
https://cplusplus.com/reference/queue/queue/size/
https://cplusplus.com/reference/queue/queue/front/
https://cplusplus.com/reference/queue/queue/back/
https://cplusplus.com/reference/queue/queue/push/
https://cplusplus.com/reference/queue/queue/empty/
queue的模拟实现
因为queue的接口中存在头删和尾插,因此使用vector来封装效率太低,故可以借助list来模拟实现queue,具体如下:
#include <list>
namespace bite
{
template<class T>
class queue
{
public:
queue() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_front();}
T& back() {return _c.back();}
const T& back()const {return _c.back();}
T& front() {return _c.front();}
const T& front()const {return _c.front();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::list<T> _c;
};
}
priorty_queue的介绍和使用
priorty_queue的介绍
翻译:
1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
priorty_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。
https://cplusplus.com/reference/queue/priority_queue/priority_queue/
https://cplusplus.com/reference/queue/priority_queue/empty/
https://cplusplus.com/reference/queue/priority_queue/top/
https://cplusplus.com/reference/queue/priority_queue/push/
https://cplusplus.com/reference/queue/priority_queue/pop/
【注意】
1. 默认情况下,priority_queue是大堆
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
// 默认情况下,创建的是大堆,其底层按照小于号比较
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// 如果要创建小堆,将第三个模板参数换成greater比较方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
2. 如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueue()
{
// 大堆,需要用户在自定义类型中提供<的重载
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout << q1.top() << endl;
// 如果要创建小堆,需要用户提供>的重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout << q2.top() << endl;
}
在oj中的使用
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 将数组中的元素先放入优先级队列中
priority_queue<int> p(nums.begin(), nums.end());
// 将优先级队列中前k-1个元素删除掉
for(int i= 0; i < k-1; ++i)
{
p.pop();
}
return p.top();
}
};
priorty_queue的模拟实现
通过对priority_queue的底层结构就是堆,因此此处只需对对进行通用的封装即可。
容器适配器
什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。
STL标准库中的stack和queue的底层结构
虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,比如:
deque的简单介绍
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组
双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂
为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:
1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。
结合了deque的优点,而完美的避开了其缺陷。
STL标准库中对于stack和queue模拟实现
stack模拟实现
#include<deque>
namespace bite
{
template<class T, class Con = deque<T>>
//template<class T, class Con = vector<T>>
//template<class T, class Con = list<T>>
class stack
{
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
Con _c;
};
}
queue模拟实现
#include<deque>
#include <list>
namespace bite
{
template<class T, class Con = deque<T>>
//template<class T, class Con = list<T>>
class queue
{
public:
queue() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_front();}
T& back() {return _c.back();}
const T& back()const {return _c.back();}
T& front() {return _c.front();}
const T& front()const {return _c.front();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
Con _c;
};
}
模版进阶
非类型模版参数
模板参数分类类型形参与非类型形参。
类型形参即:出现在模板参数列表中,跟在class或者typename之类的参数类型名称。
非类型形参,就是用一个常量作为类(函数)模板的一个参数,在类(函数)模板中可将该参数当成常量来使用
namespace bite
{
// 定义一个模板类型的静态数组
template<class T, size_t N = 10>
class array
{
public:
T& operator[](size_t index){return _array[index];}
const T& operator[](size_t index)const{return _array[index];}
size_t size()const{return _size;}
bool empty()const{return 0 == _size;}
private:
T _array[N];
size_t _size;
};
}
注意:
1. 浮点数、类对象以及字符串是不允许作为非类型模板参数的。
2. 非类型的模板参数必须在编译期就能确认结果。
模版的特化
概念
通常情况下,使用模板可以实现一些与类型无关的代码,但对于一些特殊类型的可能会得到一些错误的结果,需要特殊处理,比如:实现了一个专门用来进行小于比较的函数模板
// 函数模板 -- 参数匹配
template<class T>
bool Less(T left, T right)
{
return left < right;
}
int main()
{
cout << Less(1, 2) << endl; // 可以比较,结果正确
Date d1(2022, 7, 7);
Date d2(2022, 7, 8);
cout << Less(d1, d2) << endl; // 可以比较,结果正确
Date* p1 = &d1;
Date* p2 = &d2;
cout << Less(p1, p2) << endl; // 可以比较,结果错误
return 0;
}
可以看到,Less绝对多数情况下都可以正常比较,但是在特殊场景下就得到错误的结果。上述示例中,p1指向的d1显然小于p2指向的d2对象,但是Less内部并没有比较p1和p2指向的对象内容,而比较的是p1和p2指针的地址,这就无法达到预期而错误。
此时,就需要对模板进行特化。即:在原模板类的基础上,针对特殊类型所进行特殊化的实现方式。模板特化中分为函数模板特化与类模板特化
函数模版特化
函数模板的特化步骤:
1. 必须要先有一个基础的函数模板
2. 关键字template后面接一对空的尖括号<>
3. 函数名后跟一对尖括号,尖括号中指定需要特化的类型
4. 函数形参表: 必须要和模板函数的基础参数类型完全相同,如果不同编译器可能会报一些奇怪的错误。
// 函数模板 -- 参数匹配
template<class T>
bool Less(T left, T right)
{
return left < right;
}
// 对Less函数模板进行特化
template<>
bool Less<Date*>(Date* left, Date* right)
{
return *left < *right;
}
int main()
{
cout << Less(1, 2) << endl;
Date d1(2022, 7, 7);
Date d2(2022, 7, 8);
cout << Less(d1, d2) << endl;
Date* p1 = &d1;
Date* p2 = &d2;
cout << Less(p1, p2) << endl; // 调用特化之后的版本,而不走模板生成了
return 0;
}
注意:一般情况下如果函数模板遇到不能处理或者处理有误的类型,为了实现简单通常都是将该函数直接给出。
bool Less(Date* left, Date* right)
{
return *left < *right;
}
该种实现简单明了,代码的可读性高,容易书写,因为对于一些参数类型复杂的函数模板,特化时特别给出,因此函数模板不建议特化
类模版特化
全特化
全特化即是将模板参数列表中所有的参数都确定化
template<class T1, class T2>
class Data
{
public:
Data() {cout<<"Data<T1, T2>" <<endl;}
private:
T1 _d1;
T2 _d2;
};
template<>
class Data<int, char>
{
public:
Data() {cout<<"Data<int, char>" <<endl;}
private:
int _d1;
char _d2;
};
void TestVector()
{
Data<int, int> d1;
Data<int, char> d2;
}
偏特化
偏特化:任何针对模版参数进一步进行条件限制设计的特化版本。比如对于以下模板类:
template<class T1, class T2>
class Data
{
public:
Data() {cout<<"Data<T1, T2>" <<endl;}
private:
T1 _d1;
T2 _d2;
};
偏特化有以下两种表现方式:
部分特化
将模板参数类表中的一部分参数特化
// 将第二个参数特化为int
template <class T1>
class Data<T1, int>
{
public:
Data() {cout<<"Data<T1, int>" <<endl;}
private:
T1 _d1;
int _d2;
};
参数更进一步的限制
偏特化并不仅仅是指特化部分参数,而是针对模板参数更进一步的条件限制所设计出来的一个特化版本。
//两个参数偏特化为指针类型
template <typename T1, typename T2>
class Data <T1*, T2*>
{
public:
Data() {cout<<"Data<T1*, T2*>" <<endl;}
private:
T1 _d1;
T2 _d2;
};
//两个参数偏特化为引用类型
template <typename T1, typename T2>
class Data <T1&, T2&>
{
public:
Data(const T1& d1, const T2& d2)
: _d1(d1)
, _d2(d2)
{
cout<<"Data<T1&, T2&>" <<endl;
}
private:
const T1 & _d1;
const T2 & _d2;
};
void test2 ()
{
Data<double , int> d1; // 调用特化的int版本
Data<int , double> d2; // 调用基础的模板
Data<int *, int*> d3; // 调用特化的指针版本
Data<int&, int&> d4(1, 2); // 调用特化的指针版本
}
模版分离编译
什么是分离编译
一个程序(项目)由若干个源文件共同实现,而每个源文件单独编译生成目标文件,最后将所有目标文件链接起来形成单一的可执行文件的过程称为分离编译模式。
模版的分离编译
假如有以下场景,模板的声明与定义分离开,在头文件中进行声明,源文件中完成定义:
// a.h
template<class T>
T Add(const T& left, const T& right);
// a.cpp
template<class T>
T Add(const T& left, const T& right)
{
return left + right;
}
// main.cpp
#include"a.h"
int main()
{
Add(1, 2);
Add(1.0, 2.0);
return 0;
}
解决办法
1. 将声明和定义放到一个文件 "xxx.hpp" 里面或者xxx.h其实也是可以的。推荐使用这种。
2. 模板定义的位置显式实例化。这种方法不实用,不推荐使用。
【分离编译扩展阅读】:为什么C++编译器不能支持对模板的分离式编译-CSDN博客
模版总结
【优点】
1. 模板复用了代码,节省资源,更快的迭代开发,C++的标准模板库(STL)因此而产生
2. 增强了代码的灵活性
【缺陷】
1. 模板会导致代码膨胀问题,也会导致编译时间变长
2. 出现模板编译错误时,错误信息非常凌乱,不易定位错误
标签:初阶,return,心得体会,int,c++,year,Date,size,函数 From: https://blog.csdn.net/weixin_73861555/article/details/142221495