c/c++问题集四

原创

_咯噔_

修改于 2022-04-18 18:07:04

7350

修改于 2022-04-18 18:07:04

文章被收录于专栏：CS学习笔记CS学习笔记

1、虚函数和虚函数表

虚函数表属于类，类的所有对象共享这个类的虚函数表。虚函数表由编译器在编译时生成，保存在.rdata只读数据段。
虚函数指针在对象里，对象在哪，虚函数指针就在哪。类对象的虚函数指针vptr是在运行阶段确定的

继承关系中，派生类的虚表指针继承自父类

多重继承，放在第一个有虚函数指针基类的地方，如果基类都没有虚函数，就是特属子类的虚函数指针

2、c++泛型编程

泛型在C++中的主要实现为模板函数和模板类。

模板函数

以swap函数为例，都是交换功能，只是数据类型的不同，template是声明一个模板，typename/class是声明一个虚类型T

template <class T>
void swap(T *p1,T *p2){
 T temp=*p1;
 *p1=*p2;
 *p2=temp;
}

调用时，自动类型推导；自己声明数据类型进行调用（那就是没有参数传递的时候必须声明）

	//1、自动类型推导
	swap(a, b);
	//2、显示指定类型
	swap<int>(a, b);

一个函数里面含有不同数据类型

template<class T1,class T2>
void func(T1 a,T2 b){....}

1) 函数模板并不是真正的函数，它只是C++编译生成具体函数的一个模子。

2) 函数模板本身并不生成函数，实际生成的函数是替换函数模板的那个函数，这种替换是编译期就绑定的。

3) 函数模板不是只编译一份满足多重需要，而是为每一种替换它的函数编译一份。

模板类

调用时必须指定数据类型，这点与函数模板不一样

template<class T1,class T2,class T3>
class Student{
public:
 Student(T1 name,T2 age,T3 score){
 ..........
 }
 T1 m_Name;
 T2 m_Age;
 T3 m_Score;
}
Student<string,int,float> s("Tom",18,85.5);

类外定义模板函数

template<class numType>
class Compare{
public:
 Compare(numType a,numType b){
 this->a=a;
 this->b=b;
 }
 //声明模板函数：
 numType max( );
private:
 numType a;
 numTypr b;
}
//类外定义模板函数
template<class numType>
numType Compare::max( ){
 return this->a>this->b?this->a:this->b;
 }

类作为数据类型传入

//定义Person1
class Person1 {
public:
	void showPerson1() {
		cout << "Person1 show" << endl;
	}
};
//定义Person2
class Person2 {
public:
	void showPerson2() {
		cout << "Person2 show" << endl;
	}
};
//定义类模板
template<class T>
class MyClass {
public:
	T obj;
	//类模板中的成员函数
	void func1() {
		obj.showPerson1();
	}
	void func2() {
		obj.showPerson2();
	}
};
//主函数
int main() {
	MyClass<Person1>m;
	m.func1();
	//m.func2();//会报错，因为“showPerson2”: 不是“Person1”的成员
	system("pause");
	return 0;
}

类模板与继承

子类父类都要申明为模板类，子类继承父类的时要指父类的泛型

template<class T>
class Base {
	T m_Name;
};
//class Son :public Base { //错误，必须知道T的内存才能指定空间
class Son1:public Base<int>{ // 不灵活
};
//想要灵活指定父类中T的类型
template<class T1,class T2>
class Son2 :public Base<T2> {
public:
	T1 m_A;
};
int main() {
	//让子类的T为string，子类的T1为int
	Son2<int, string>s2;
	system("pause");
	return 0;
}

类模板与友元

当传入类对象到函数里面，如果这个函数需要用到对象里面的数据，而该数据有被设定为private(私有)就无法直接访问，方法是将该函数申明为类的友元函数，

//先声明类和函数，防止编译器报错
template<class T1,class T2>
class Person;
template<class T1, class T2>
void printPerson(Person<T1, T2> p);

template<class T1,class T2>
class Person {
	//全局函数类外实现的声明
	friend void printPerson<>(Person<T1, T2> p);
public:
	Person(T1 name, T2 age) {
		this->m_Name = name;
		this->m_Age = age;
	}
private:
	T1 m_Name;
	T2 m_Age;
};
//全局函数类外实现
template<class T1,class T2>
void printPerson(Person<T1, T2> p) {
	cout << "Name:" << p.m_Name << endl;
	cout << "Age:" << p.m_Age << endl;
}

当一个类包含一个友元声明时，类与友元各自是否是模板是相互无关的。如果一个类模板包含一个非模板的友元，则友元被授权可以访问所有模板的实例。如果友元自身是模板，类可以授权给所有友元模板的实例，也可以只授权给特定实例。

类模板的static成员

类模板可以声明static成员。类模板的每一个实例都有其自己独有的static成员对象，对于给定的类型X，所有class_name<X>类型的对象共享相同的一份static成员实例。

（https://www.jb51.net/article/53746.htm）

类模板中可以指定默认参数类型

template<class NameType, class AgeType = int> //

三、C++四种cast及其使用

static_cast

static_cast <T> content：静态转换，在编译期间处理
主要用于C++中内置的基本数据类型之间的转换，例如int转换为char,把int转换成enum，但是没有运行时类型的检测来保证转换的安全性。
还用于各种隐式转换，比如非const转const，void*转指针等。
多态中：
用于基类和子类之间的指针或引用的转换。把子类的指针或引用转换为基类表示时（向上转换）是安全的；但把基类的指针或引用转换为用子类表示时（向下转换），由于没有进行动态类型检测，所以是不安全的。
需要注意的是，static_cast只转换类型，不改变属性，即content的const、volatile、unaligned的属性是不会改变的

const_cast

const_cast <T*> content：去常转换，编译时执行
常用于去除const类对象的指针或引用的const属性，且强制转换的类型必须是指针或引用。
作用于同一个类型，但不能用作不同类型之间的转换。

dynamic_cast

dynamic_cast <T*> content：动态类型转换，运行时执行
只能用于含有虚函数的类，用于类层次间的向上和向下转换。转换时（特别是向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常）会进行类型安全检查
只能转指针或引用。
通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否相同来判断是否能够进行向下转换。
不能用于内置的基本数据类型及其指针之间的转换

reinterpret_cast

reinterpret_cast <T*> content：重解释类型转换，几乎什么都可以转。
它有着和C语言中强制转换一样的功能，它可以把任何的内置数据类型转换为其他的类型，同时它也可以把任何类型的指针转换为整数。它的机制是对二进制数据进行重新的解释，不会改变原来的格式，而static_cast则会改变原来的格式。

4、虚继承

在菱形继承中，有多重继承的问题，从不同途径继承来的同一基类，会在子类中存在多份拷贝。这将存在两个问题：其一，浪费存储空间；第二，存在二义性问题。

虚继承一般通过虚基类指针和虚基类表实现，每个虚继承的子类都有一个虚基类指针vbptr（占用一个指针的存储空间，4字节）和虚基类表（不占用类对象的存储空间）（多重虚继承还是单一虚继承，指向虚基的指针都只有一个）；当虚继承的子类被当做父类继承时，虚基类指针也会被继承，如果是多重继承那就会有多个虚基指针。

5、B树B+树

一颗m阶的B树（B-tree）定义如下：

（1）每个节点最多有 m-1 个关键字，n个关键字有n+1个子树，每个关键字都指向磁盘中的一条记录；

（2）根节点至少有1个key；

（3）非根节点至少有 Math.ceil(m/2) 个子树，至多有m个子树；

（4）每个节点中的key都按照从小到大的顺序排列，每个key的左子树中的所有key都小于它，而右子树中的所有key都大于它；

（5）所有叶子节点都位于同一层，即根节点到每个叶子节点的长度都相同。

m阶B+树区别在：

（1）n个关键字有n个子树，每个关键字都是其指向的子节点中的最大值；

（2）非叶子节点仅具有索引作用（多级索引），叶子节点才直接指向数据文件。

（3）树的所有叶子节点构成一个有序链表，按递增次序排好序。

•当从B+树根结点开始随机查找时, 检索方法与B-树相似, 但若在分支结点中的关键字与检索关键字相等时, 检索并不停止, 要继续查找到叶结点为止。

B+树的优点（为什么mysql数据库要用B+树）：

B+树的磁盘读写代价更低

由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key，访问外存次数更少。数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。

B+树的查询更加稳定

所有的关键字查询都会走一条从根节点到叶子结点的路径。即s所有关键字查询的长度是一样的，查询效率稳定。

B+树便于遍历和区间查找

B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。

但是B树也有优点，其优点在于：

由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

红黑树也带索引，为啥不用红黑树？

索引是存储在磁盘上的，索引查找过程中就要从磁盘获取数据（I/O操作），所以要想提高效率就要优化索引的结构组织，尽量减少查找过程中磁盘I/O的存取次数。在数据库设计中将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

在B+树中，d(节点的度)很大，h(树的深度)一般很小，每次检索最多访问h个节点，所以I/O次数就会很少，效率就高。

在红黑树中，d(节点的度)很小，h(树的深度)一般很大，每次检索最多访问h个节点，所以I/O次数就会很大，效率就小。

为什么数据库要用B树：

B树在设计上容纳更多的数据，能更加方便得让子节点存放在硬盘，所以B树能减少机械磁盘的磁头跳转的次数，B 树更加适合大量数据动态操作，因此很多数据库使用B+树来实现存储和检索。

6、空闲链表和内存池

空闲链表（free list）

将内存中所有的空闲内存块通过链表的形式组织起来，就形成了最基础的free list。内存分配时，扫描free list的各个空闲内存块，从中找到一个大小满足要求的内存块，并将该内存块从free list中移除。内存释放时，释放的内存块被重新插入到free list中。

First fit（最先适配），就是从free list头部开始扫描，直到遇到第一个满足大小的空闲内存块，这里第一个48字节的内存块就可以满足要求。这种方法的优点是相对快一些，尤其是满足要求的空闲内存块位于链表前部的时候，但是在控制碎片数量上不是最优的。

Best fit（最佳适配），就是遍历free list的所有空闲内存块，从中找到和所申请的内存大小最接近的空闲内存块，这里第二个16字节的内存块是最接近12字节的。

Worst fit（最差适配），也是遍历free list的所有空闲内存块，如果找不到大小刚好匹配的，就从最大的空闲内存块中分配。初看起来很反直觉是不是？但假设接下来的内存申请是64个字节，那只有worst fit的这种方法才能满足需求，所以其价值体现在：分配之后剩下的空闲内存块很可能仍然足够大。

内存池（memory pool）

空闲链表的分配方式简单，但分配效率不高，运行一段时间后容易产生大量的内存碎片，从而恶化了内存利用率。

如果能将一大块内存分成多个小内存（称为内存池），不同的内存池又按照不同的「尺寸」分成大小相同的内存块（比如分别按照32, 64, 128……字节），同一内存池中的空闲内存块按照free list的方式连接。

每次分配的时候，选择和申请的的内存在「尺寸」上最接近的内存池，比如申请60字节的内存，就直接从单个内存块大小为64字节的内存池的free list上分配。

但要想取得好的效果，需要结合系统实际的内存分配需求，对内存池的大小进行合理的划分。比如一个系统常用的是256字节以下的内存申请，那设置过多的256字节以上的内存池，就会造成内存资源的闲置和浪费。

（https://zhuanlan.zhihu.com/p/73468738）

7、tcp粘包和拆包问题

粘包拆包发生场景

因为TCP是面向流，没有边界，而操作系统在发送TCP数据时，会通过缓冲区来进行优化，例如缓冲区为1024个字节大小。

如果一次请求发送的数据量比较小，没达到缓冲区大小，TCP则会将多个请求合并为同一个请求进行发送，这就形成了粘包问题。

如果一次请求发送的数据量比较大，超过了缓冲区大小，TCP就会将其拆分为多次发送，这就是拆包。

常见的解决方案

对于粘包和拆包问题，常见的解决方案有四种：

发送端将每个包都封装成固定的长度，比如100字节大小。如果不足100字节可通过补0或空等进行填充到指定长度；
发送端在每个包的末尾使用固定的分隔符，例如\r\n。如果发生拆包需等待多个包发送过来之后再找到其中的\r\n进行合并；例如，FTP协议；
将消息分为头部和消息体，头部中保存整个消息的长度，只有读取到足够长度的消息之后才算是读到了一个完整的消息；
通过自定义协议进行粘包和拆包的处理。

8、TCP拥塞控制

reno算法

在新环境下不能充分利用网络带宽，主要是因为在进入拥塞避免阶段后，它们的拥塞窗口每经过一个RTT才加1，拥塞窗口的增长速度太慢，当碰上高带宽环境时，可能需要经历很多个RTT，拥塞窗口才能接近于一个BDP。如果是短流，可能拥塞窗口还没增长到一个BDP，数据流就已经结束了，致使网络带宽浪费和降低用户体验。

BIC-TCP采用二分搜索的方式来决定拥塞窗口的增长尺度，探测一个合适的窗口大小，，BIC-TCP的增长函数在小链路带宽时延短的情况下比起标准的TCP来抢占性强

cubic算法：

拥塞控制窗口增长函数是一个三次函数(即一个立方函数)，在三次函数曲线中同样存在一个凹和凸的部分，该曲线形状和BIC-TCP的曲线图十分相似，于是该部分取代BIC-TCP的增长曲线。另外，CUBIC中最关键的点在于它的窗口增长函数仅仅取决于连续的两次拥塞事件的时间间隔值，从而窗口增长完全独立于网络的时延RTT，解决有些算法存在严重的RTT不公平性问题，更好的保证流与流之间的公平性。

当某次拥塞事件发生时，Wmax设置为此时发生拥塞时的窗口值，然后把窗口进行乘法减小，乘法减小因子设为β，当从快速恢复阶段退出然后进入到拥塞避免阶段，此时CUBIC的窗口增长开始按照“凹”式增长曲线进行增长，该过程一直持续直到窗口再次增长到Wmax，紧接着，该函数转入“凸”式增长阶段。该方式的增长可以使得窗口一直维持在Wmax附近，从而可以达到网络带宽的高利用率和协议本身的稳定性。