老虎证券 C++面经

(1)进程与线程的区别?

调度:线程是独立调度的基本单位,进程是拥有资源的基本单位。在同一进程中,线程的切换不会引起进程的切换;在不同的进程中,进行线程切换,则会引起进程的切换。
拥有资源:进程是拥有资源的基本单位,线程不拥有资源,但线程可以共享器隶属进程的系统资源。
并发性:进程可以并发执行,而且同一进程内的多个线程也可以并发执行,大大提高了系统的吞吐量。
系统开销:创建和撤销进程时,系统都要为之分配或回收资源,在进程切换时,涉及当前执行进程CPU环境的保存以及新调度的进程CPU环境的设置;而线程切换时只需保存和设置少量寄存器内容,因此开销很小,另外,由于同一进程内的多个线程共享进程的地址空间,因此这些线程之间的同步与通信比较容易实现,甚至无须操作系统的干预。
通信方面:进程间通信需要借助操作系统,而线程间可以直接读/写进程数据段来进行通信。

(2)进程间的通信方式?

  • 管道( pipe )
  • 有名管道 (named pipe)
  • 信号量( semophore )
  • 消息队列( message queue )
  • 信号 ( signal )
  • 套接字( socket )
  • 共享内存(Shared Memory)

(3)线程间的通信方式?

  • 事件(Event);
  • 信号量(semaphore);
  • 互斥量(mutex);
  • 临界区(Critical section)

(4)栈和堆的区别?

1、在申请方式上

(stack): 现在很多人都称之为堆栈,这个时候实际上还是指的栈。它由编译器自动管理,无需我们手工控制。 例如,声明函数中的一个局部变量 int b 系统自动在栈中为b开辟空间;在调用一个函数时,系统自动的给函数的形参变量在栈中开辟空间。

(heap): 申请和释放由程序员控制,并指明大小。容易产生memory leak。

在C中使用malloc函数。

如:char *p1 = (char *)malloc(10);

在C++中用new运算符。

如:char *p2 = new char(20);

但是注意p1本身在全局区,而p2本身是在栈中的,只是它们指向的空间是在堆中。

2、申请后系统的响应上

(stack):只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。

(heap): 首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序。另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete或 free语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。

3、申请大小的限制

(stack):在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示 overflow。因此,能从栈获得的空间较小。例如,在VC6下面,默认的栈空间大小是1M(好像是,记不清楚了)。当然,我们可以修改:打开工程,依次操作菜单如下:Project->Setting->Link,在Category 中选中Output,然后在Reserve中设定堆栈的最大值和commit。

注意:reserve最小值为4Byte;commit是保留在虚拟内存的页文件里面,它设置的较大会使栈开辟较大的值,可能增加内存的开销和启动时间。

(heap): 堆是向高地址扩展的数据结构,是不连续的内存区域(空闲部分用链表串联起来)。正是由于系统是用链表来存储空闲内存,自然是不连续的,而链表的遍历方向是由低地址向高地址。一般来讲在32位系统下,堆内存可以达到4G的空间,从这个角度来看堆内存几乎是没有什么限制的。由此可见,堆获得的空间比较灵活,也比较大。

4、分配空间的效率上

(stack):栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高。但程序员无法对其进行控制。

(heap):是C/C++函数库提供的,由new或malloc分配的内存,一般速度比较慢,而且容易产生内存碎片。它的机制是很复杂的,例如为了分配一块内存,库函数会按照一定的算法在堆内存中搜索可用的足够大小的空间,如果没有足够大小的空间(可能是由于内存碎片太多),就有可能调用系统功能去增加程序数据段的内存空间,这样就有机会分到足够大小的内存,然后进行返回。这样可能引发用户态和核心态的切换,内存的申请,代价变得更加昂贵。显然,堆的效率比栈要低得多。

5、堆和栈中的存储内容

(stack):在函数调用时,第一个进栈的是主函数中子函数调用后的下一条指令(子函数调用语句的下一条可执行语句)的地址,然后是子函数的各个形参。在大多数的C编译器中,参数是由右往左入栈的,然后是子函数中的局部变量。

注意:静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中子函数调用完成的下一条指令,程序由该点继续运行。

(heap):一般是在堆的头部用一个字节存放堆的大小,堆中的具体内容有程序员安排。

堆和栈的区别可以用如下的比喻来看出: 使用栈就象我们去饭馆里吃饭,只管点菜(声明变量)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。

使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。

(5)C++和C的区别?

C是一个结构化语言,它的重点在于算法和数据结构。对于语言本身而言,C是C++的子集。C程序的设计首要考虑的是如何通过一个过程,对输入进行运算处理,得到输出。对于C++,首要考虑的是如何构造一个对象模型,让这个模型能够配合对应的问题,这样就可以通过获取对象的状态信息得到输出或实现过程控制。

因此,C与C++的最大区别在于,它们用于解决问题的思想方法不一样。

C实现了C++中过程化控制及其他相关功能。而在C++中的C,相对于原来的C还有所加强,引入了重载、内联函数、异常处理等。C++更是拓展了面向对象设计的内容,如类、继承、虚函数、模板和包容器类等。

在C++中,不仅需要考虑数据封装,还需要考虑对象的粒度的选择、对象接口的设计和继承、组合与继承的使用等问题。

相对于C,C++包含了更丰富的设计概念。

(6)BST,AVL树,红黑树的区别?

二叉查找树(BST)

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:

  • 任意节点左子树不为空,则左子树的值均小于根节点的值.
  • 任意节点右子树不为空,则右子树的值均大于于根节点的值.
  • 任意节点的左右子树也分别是二叉查找树.
  • 没有键值相等的节点.

AVL树

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少,但查找多的情况。

红黑树

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black. 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍.它是一种弱平衡二叉树(由于是弱平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,我们就用红黑树.

性质

  • 每个节点非红即黑.
  • 根节点是黑的。
  • 每个叶节点(叶节点即树尾端NUL指针或NULL节点)都是黑的.
  • 如果一个节点是红的,那么它的两儿子都是黑的.
  • 对于任意节点而言,其到叶子点树NIL指针的每条路径都包含相同数目的黑节点.
  • 查找、插入和删除的时间复杂度都是O(logn)

(7)产生死锁的必要条件?已经如何预防死锁?

一、计算机系统中的死锁

竞争不可抢占性资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁
二、产生死锁的必要条件

互斥条件(资源独占)
请求和保持条件
不可抢占条件(不可剥夺)
循环等待条件
三、处理死锁的方法

预防死锁
避免死锁
检测死锁
解除死锁
四、预防死锁

破坏‘请求和保持’条件
破坏‘不可抢占条件’条件
破坏‘循环等待’条件
(主要是破坏产生死锁的后三个条件)

五、解决死锁

最简单的办法是终止各锁住进程,或按一定的顺序中止进程序列,直到已释放到有足够的资源来完成剩下的进程时为止。
也可以从被锁住进程强迫剥夺资源以解除死锁

(8)TCP和UDP的区别?

TCP和UDP的区别:

传输控制协议TCP的特点:

(1) TCP是面向连接的运输层协议

(2) 每一条TCP连接只能有两个端口,即:点对点

(3) TCP提供可靠交付的服务

(4) TCP提供全双工通信

(5) 面向字节流,TCP中的“流”指流入到进程或从进程流出的字节序列

用户数据报协议UDP的特点:

(1) UDP是无连接的

(2) UDP使用尽最大努力交付

(3) UDP是面向报文

(4) UDP没有拥塞控制

(5) UDP支持一对一、一对多、多对一和多对的的交互通信

(6) UDP的首部开销小,只有8个字节,比TCP的20个字节的首部要短

(9)TCP状态中 time_wait 的作用?

TCP状态中 time_wait 的作用:

客户端接收到服务器端的 FIN 报文后进入此状态,此时并不是直接进入 CLOSED 状态,还需要等待一个时间计时器设置的时间。这么做有两个理由:

确保最后一个确认报文段能够到达。如果 B 没收到 A 发送来的确认报文段,那么就会重新发送连接释放请求报文段,A 等待一段时间就是为了处理这种情况的发生。
可能存在“已失效的连接请求报文段”,为了防止这种报文段出现在本次连接之外,需要等待一段时间。

(10)HTTP 2.0与HTTP 1.0的区别 ?

  1. HTTP/2采用二进制格式而非文本格式
  2. HTTP/2是完全多路复用的,而非有序并阻塞的——只需一个连接即可实现并行
  3. 使用报头压缩,HTTP/2降低了开销
  4. HTTP/2让服务器可以将响应主动“推送”到客户端缓存中

(11)HTTP与HTTPS的区别?

HTTP协议传输的数据都是未加密的,也就是明文的,因此使用HTTP协议传输隐私信息非常不安全,为了保证这些隐私数据能加密传输,于是网景公司设计了SSL(Secure Sockets Layer)协议用于对HTTP协议传输的数据进行加密,从而就诞生了HTTPS。简单来说,HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议,要比http协议安全。

HTTPS和HTTP的区别主要如下:

1、https协议需要到ca(证书授权机构:Certificate Authority )申请证书,一般免费证书较少,因而需要一定费用。

2、http是超文本传输协议,信息是明文传输,https则是具有安全性的ssl加密传输协议。

3、http和https使用的是完全不同的连接方式,用的端口也不一样,前者是80,后者是443。

4、http的连接很简单,是无状态的;HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议,比http协议安全。

(12)TCP的三次握手和四次挥手的过程?

在这里插入图片描述

在这里插入图片描述

(13)事务具有四个特性?

  • 原子性(Atomicity)
  • 一致性(Consistency)
  • 隔离性(Isolation)
  • 持续性(Durability)

(14)树的先序、中序和后序的递归和非递归实现?

树的先序递归:

void PreOrder(Tree* root)
{
	if (root != nullptr)
	{
		cout << root->date << " ";
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

树的先序非递归:

void PreOrder(Tree* root)
{
	stack<Tree* > Stack;
	if (root == nullptr)
		return;
	while (root != nullptr || !Stack.empty())
	{
		while (root != nullptr)
		{
			Stack.push(root);
			cout << root->date << " ";
			root = root->lchild;
		}
		root = Stack.top();
		Stack.pop();
		root = root->rchild;
	}
}

树的中序递归:

void InOrder(Tree* root)
{
	if (root != nullptr)
	{
		InOrder(root->lchild);
		cout << root->date << " ";
		InOrder(root->rchild);
	}
}

树的中序非递归:

void InOrder(Tree* root)
{
	stack<Tree*> s;
	while (root != nullptr || !s.empty())
	{
		if (root != nullptr)
		{
			s.push(root);
			root = root->lchild;
		}
		else
		{
			root = s.top();s.pop();
			cout << root->date << " ";
			root = root->rchild;
		}
	}
}

树的后序递归:

void PostOrder(Tree* root)
{
	if (root != nullptr)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		cout << root->date << " ";
	}
}

树的后序非递归:

void PostOrder(Tree* root)
{
	stack<Tree*> s;
	Tree* r = nullptr;//使用辅助指针,指向最近访问过的节点
	while (root != nullptr || !s.empty())
	{
		if (root != nullptr)
		{
			s.push(root);
			root = root->lchild;
		}
		else
		{
			root = s.top();
			if (root->rchild != nullptr && root->rchild != r)
				root = root->rchild;
			else
			{
				s.pop();
				cout << root->date << " ";
				r = root;
				root = nullptr;
			}
		}
	}
}

(15)树的层次遍历?

void LevelOrder(Tree* root)
{
	if (root == nullptr)
		return;
	queue<Tree*> que;
	que.push(root);
	while (!que.empty())
	{
		root = que.front();
		cout << root->date << " ";
		que.pop();
		if (root->lchild != nullptr)
			que.push(root->lchild);
		if (root->rchild != nullptr)
			que.push(root->rchild);
	}
}

(16)static关键字的作用?

static关键字的作用:

(1)函数体内static变量的作用范围为该函数体,不同于auto变量,该变量的内存只被分配一次,因此其值在下次调用时仍维持上次的值;

(2)在模块内的static全局变量可以被模块内所用函数访问,但不能被模块外其它函数访问;

(3)在模块内的static函数只可被这一模块内的其它函数调用,这个函数的使用范围被限制在声明它的模块内;

(4)在类中的static成员变量属于整个类所拥有,对类的所有对象只有一份拷贝;

(5)在类中的static成员函数属于整个类所拥有,这个函数不接收this指针,因而只能访问类的static成员变量。

(17)const关键字的作用?

const关键字的作用:

(1)欲阻止一个变量被改变,可以使用const关键字。在定义该const变量时,通常需要对它进行初始化,因为以后就没有机会再去改变它了;

(2)对指针来说,可以指定指针本身为const,也可以指定指针所指的数据为const,或二者同时指定为const;

(3)在一个函数声明中,const可以修饰形参,表明它是一个输入参数,在函数内部不能改变其值;

(4)对于类的成员函数,若指定其为const类型,则表明其是一个常函数,不能修改类的 成员变量;

(5)对于类的成员函数,有时候必须指定其返回值为const类型,以使得其返回值不为“左值”。

(18)指针和引用的区别?

  1. 指针:指针是一个变量,只不过这个变量存储的是一个地址,指向内存的一个存储单元;引用的底层是const指针,引用同样占据一块内存。
  2. 引用不可以为空,当被创建的时候,必须初始化,而指针可以是空值,可以在任何时候被初始化。

(19)哈希表处理冲突的方法?

(1) 链地址法

链地址法是指把所有的冲突关键字存储在一个线性链表中,这个链表由其散列地址唯一标识。

(2) 开放定址法

开放定址法是指可存放新表项的空闲地址,既向它的同义词表项开放,又向它的非同义词表项开放。其数学递推公式为(Hi表示冲突发生后第i次探测的散列地址)

Hi = (H(key) + di) % m

式中,i = 1,2,…,k,m为散列表表长,di为增量序列。di通常有以下几种取法:

当di = 1,2,…,m – 1时,称为线性探测法。其特点是,冲突发生时顺序查看表中下一个单元,直到找出一个空单元或查遍全表。

当di = 12,-12,22,-22,…,k2,-k2时,又称为二次探测法。

当di = 伪随机数序列时,称为伪随机探测法。

(3) 再散列法

当发生冲突时,利用另一个哈希函数再次计算一个地址。直到冲突不再发生。

(4) 建立一个公共溢出区

一旦由哈希函数得到的地址冲突,就都填入溢出表。

(20)面向对象的三大特性?

继承、封装、多态

(21)多态的实现?

(1)编译时的多态性。编译时的多态性是通过重载来实现的。对于非虚的成员来说。系统在编译时,根据传递的参数、返回的类型等信息决定实现何种操作。

(2)运行时的多态性。运行时的多态性就是直到系统运行时,才根据实际情况决定实现何种操作。C++中,运行时的多态性通过虚函数实现。

(22)深拷贝和浅拷贝的区别?

浅拷贝

对一个已知对象进行拷贝,编译系统会自动调用一种构造函数——拷贝构造函数,如果用户未定义拷贝构造函数,则会调用默认拷贝构造函数,调用一次构造函数,调用两次析构函数,两个对象的指针成员所指内存相同,但是程序结束时该内存却被释放了两次,会造成内存泄漏问题。

深拷贝

在对含有指针成员的对象进行拷贝时,必须要自己定义拷贝构造函数,使拷贝后的对象指针成员有自己的内存空间,即进行深拷贝,这样就避免了内存泄漏发生,调用一次构造函数,一次自定义拷贝构造函数,两次析构函数。两个对象的指针成员所指内存不同。

总结:浅拷贝只是对指针的拷贝,拷贝后两个指针指向同一个内存空间,深拷贝不但对指针进行拷贝,而且对指针指向的内容进行拷贝,经深拷贝后的指针是指向两个不同地址的指针。

(23)vector的实现原理

vector的数据安排以及操作方式,与array非常相似。两者的唯一区别在于空间的运用的灵活性。array是静态空间,一旦配置了就不能改变;要换个大(或小)一点的房子,可以,一切琐细都得由客户端自己来:首先配置一块新空间,然后将元素从旧址一一搬往新址,再把原来的空间释还给系统。vector是动态空间,随着元素的加入,它的内部机制会自行扩充空间以容纳新元素。因此,vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们再也不必因为害怕空间不足而一开始要求一个大块头的array了,我们可以安心使用array,吃多少用多少。

vector的实现技术,关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧有空间满载,如果客户端每新增一个元素,vector的内部只是扩充一个元素的空间,实为不智。因为所谓扩充空间(不论多大),一如稍早所说,是” 配置新空间/数据移动/释还旧空间 “的大工程,时间成本很高,应该加入某种未雨绸缪的考虑。稍后我们便可看到SGI vector的空间配置策略了。

另外,由于 vector维护的是一个连续线性空间,所以vector支持随机存取 。

注意:vector动态增加大小时,并不是在原空间之后持续新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此, 对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了 。这是程序员易犯的一个错误,务需小心。

(24)C++ 源代码到可执行代码的详细过程 ?

https://maplefan.com/index.php/2018/12/06/编译预处理/

(25)memcpy和strcpy的区别 ?

memcpy和strcpy的区别?

strcpy和memcpy主要有以下3方面的区别。

复制的内容不同。strcpy只能复制字符串,而memcpy可以复制任意内容,例如字符数组、整型、结构体、类等。
复制的方法不同。strcpy不需要指定长度,它遇到被复制字符的串结束符”\0″才结束,如果空间不够,就会引起内存溢出。memcpy则是根据其第3个参数决定复制的长度。
用途不同。通常在复制字符串时用strcpy,而需要复制其他类型数据时则一般用memcpy,由于字符串是以“\0”结尾的,所以对于在数据中包含“\0”的数据只能用memcpy。
从s1复制字符串到s2

strncpy和memcpy很相似,只不过它在一个终止的空字符处停止。当n>strlen(s1)时,给s2不够数的空间里填充“\0”(n为s2的空间大小);当n<=strlen(s1)时,s2是没有结束符“\0”的,所以使用strncpy时,确保s2的最后一个字符是“\0”。

(26)vector删除数据时有什么需要注意的吗 ?

先用迭代器指向vector的起始位置,然后用while循环,找到符合的元素,删除迭代器所指向的元素,返回一个指向被删元素之后元素的迭代器,这时不能在自增了,因为迭代器指针已经指向下一个元素了,如果在自增,就将被删除的元素的后面一个元素就跳过去了,如果在被删除的元素在末尾,那么迭代器指针就会变成野指针。

(27)虚函数和纯虚函数的区别?

虚函数

引入原因:为了方便使用多态特性,我们常常需要在基类中定义虚函数。

纯虚函数在基类中是没有定义的,必须在子类中加以实现。

纯虚函数

引入原因:在很多情况下,基类本身生成对象是不合情理的。

纯虚函数就是基类只定义了函数体,没有实现过程,定义方法如下;

virtual void Eat() = 0; 直接=0 不要 在cpp中定义就可以了。

纯虚函数相当于接口,不能直接实例话,需要派生类来实现函数定义。

虚函数在子类里面也可以不重载的;但纯虚必须在子类去实现,

普通成员函数是静态编译的,没有运行时多态,只会根据指针或引用的“字面值”类对象,调用自己的普通函数;虚函数为了重载和多态的需要,在基类中定义的,即便定义为空;纯虚函数是在基类中声明的虚函数,它可以再基类中有定义,且派生类必须定义自己的实现方法。

一旦父类的成员函数声明virtual,其子类的函数不管有没有声明为virtual,都是虚函数。

普通函数如果不被使用,可以只有声明没有定义,虚函数必须要有定义,即使是一个空实现,因为编译器无法确定会使用哪个函数。

(28)C++中overload,override,overwrite的区别?

Overload(重载):在C++程序中,可以将语义、功能相似的几个函数用同一个名字表示,但参数或返回值不同(包括类型、顺序不同),即函数重载。
(1)相同的范围(在同一个类中);
(2)函数名字相同;
(3)参数不同;
(4)virtual 关键字可有可无。

Override(覆盖):是指派生类函数覆盖基类函数,特征是:
(1)不同的范围(分别位于派生类与基类);
(2)函数名字相同;
(3)参数相同;
(4)基类函数必须有virtual 关键字。

Overwrite(重写):是指派生类的函数屏蔽了与其同名的基类函数,规则如下:
(1)如果派生类的函数与基类的函数同名,但是参数不同。此时,不论有无virtual关键字,基类的函数将被隐藏(注意别与重载混淆)。

(2)如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有virtual关键字。此时,基类的函数被隐藏(注意别与覆盖混淆)。

(29)C++中四种强制类型转换 ?

去const属性用const_cast。

基本类型转换用static_cast。

多态类之间的类型转换用daynamic_cast。

不同类型的指针类型转换用reinterpret_cast。

(30)有了malloc/free,为什么还要new/delete?

malloc与free是C/C++的标准库函数,new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。

对于非内部数据类型的对象而言,光用malloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数,对象的消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符,不在编译器控制权限之内,不能够把执行构造函数和析构函数的任务强加于malloc/free。

因此,C++需要一个能完成动态内存分配和初始化工作的运算符new,以及一个能完成清理与释放内存工作的运算符delete。注意:new/delete不是库函数。

(31)map可以用结构体作为键值吗,注意事项?

在使用map时,有时候我们需要自定义键值,才能符合程序的需要。

比如我们需要使用自定义的结构体来作为map的键值。

键值无法比较。因为map的键值是自动比较后进插入的,键值是递增的。

现在我们自定义的键值,编译器无法进行比较,找不到类似的模板,所以报错。

既然是没有‘<’,那我们自己重载小于操作符应该就可以了。

(32)Volatile的作用?

voliate变量是随时变化的,用voliate修饰的运算,编译器不进行优化,以免出错。

对于一个普通变量,为提高存取速率,编译器会先将变量的值存储在一个寄存器中,以后再取变量值时,就存寄存器中取出。

但是用voliate修饰的变量,就说明这个变量会发生意向不到的改变。也就是说,优化器每次在读取该值时,不会假设这个值了,每次都会小心的在读取这个变量的值,而不是在寄存器中取保留的备份。

那么,一个参数可以同时被const和voliate修饰吗?
答案是可以的,如:只读的状态寄存器。它是voliate,是因为它可能会发生意想不到的改变;它是voliate,表示程序不应该试图去改变它。

(33)了解哪些C++11特性?

https://blog.csdn.net/chen134225/article/details/80976666

(34)右值引用和move语义?

不知道

(35)STL里resize和reserve的区别?

  • size():返回vector中的元素个数
  • capacity():返回vector能存储元素的总数
  • resize()操作:创建指定数量的的元素并指定vector的存储空间
  • reserve()操作:指定vector的元素总数

resize():改变当前容器内含有元素的数量(size()),eg: vector<int>v; v.resize(len);v的size变为len,如果原来v的size小于len,那么容器新增(len-size)个元素,元素的值为默认为0.当v.push_back(3);之后,则是3是放在了v的末尾,即下标为len,此时容器是size为len+1;

reserve():改变当前容器的最大容量(capacity),它不会生成元素,只是确定这个容器允许放入多少对象,如果reserve(len)的值大于当前的capacity(),那么会重新分配一块能存len个对象的空间,然后把之前v.size()个对象通过copy construtor复制过来,销毁之前的内存;

只有当容器内元素数(size)大于capcity时,容器才会改变地址。

(36)vector和deque的区别?

vector是单向开口的连续线性空间, deque是一种双向开口的连续线性定 ;

deque允许于常数时间内对起头端进行元素的插入或移除操作 ;
deque没有所谓容量(capacity)观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。

(37)不同排序算法的比较?

在这里插入图片描述

(38)大端和小端的区别,以及如何判断一台机器是大端还是小端?

大端模式,是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中,这样的存储模式有点儿类似于把数据当作字符串顺序处理:地址由小向大增加,而数据从高位往低位放;这和我们的阅读习惯一致。
小端模式,是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中,这种存储模式将地址的高低和数据位权有效地结合起来,高地址部分权值高,低地址部分权值低。
int checkCPU()
{
    union w
    {
        int a;
        char b;
    }c;
    c.a = 1;
    return (c.b == 1);//小端返回1,大端返回0
}

(39)malloc分配内存的原理?

步骤分为放置、分割和合并

在堆中,堆块由一个字的头部、有效载荷、填充以及一个字的脚部组成,空闲块是通过头部中的大小字段隐含地连接在一起形成一个隐式空闲链表,分配器可以通过遍历堆中所有的块,从而间接遍历整个空闲块的集合。

1、放置已分配的块

当一个应用请求一个k字节的块时,分配器搜索空闲链表,查找一个足够大可以放置所请求块的空闲块,分配器执行这种搜索的方式是放置策略确定的。常见的策略是首次适配、下一次适配和最佳适配。

首次适配:从头开始搜索空闲链表,选择第一个适合的空闲块。

下一次适配:从上一次查询结束的地方开始搜索空闲链表,选择第一个适合的空闲块。

最佳适配:检查每个空闲块,选择适合所需请求大小的最小空闲块。

2、分割空闲块

一旦分配器找到一个匹配的空闲块,它就必须做另一个策略决定,那就是分配这个空块中多少空间。一个选择是用整个空闲块,另一个选择是将这个空闲块分割成两部分。

如果分配器不能为请求块找到合适的空闲块将发生什么呢?一个选择是通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块。然而,如果这样还是不能生成一个足够大的块,或者如果空闲块已经最大程度地合并了,那么分配器就会通过调用sbrk函数,向内核请求额外的堆内存,分配器将额外的内存转化成一个大的空闲块,将这个块插入到空闲链表中,然后将被请求的块放置在这个新的空闲块中。

3、合并空闲块

Knuth提出了一种聪明而通用的技术,叫做边界标记,允许在常数时间内进行对前面的块合并。这种思想是,在每个块的结尾处添加一个脚部,其中脚部就是头部的一个副本,如果每个块包括这样一个脚部,那么分配器就可以通过检查它的脚部,判断前面一个块的起始位置和状态,这个脚部总是在当前块开始位置一个字的距离。

(40)为什么构造函数不能声明为虚函数,析构函数可以,构造函数中为什么不能调用虚函数?

1 构造一个对象的时候,必须知道对象的实际类型,而虚函数行为是在运行期间确定实际类型的。而在构造一个对象时,由于对象还未构造成功。编译器无法知道对象 的实际类型,是该类本身,还是该类的一个派生类,或是更深层次的派生类。无法确定。。。

2 虚函数的执行依赖于虚函数表。而虚函数表在构造函数中进行初始化工作,即初始化vptr,让他指向正确的虚函数表。而在构造对象期间,虚函数表还没有被初 始化,将无法进行。

(41)STL中unordered_map 和 map的区别 ?

一、hash_map与unordered_map

这两个的内部结构都是采用哈希表来实现。区别在哪里?unordered_map在C++11的时候被引入标准库了,而hash_map没有,所以建议还是使用unordered_map比较好。

哈希表的好处是什么?查询平均时间是O(1)。顾名思义,unordered,就是无序了,数据是按散列函数插入到槽里面去的,数据之间无顺序可言,但是有些时候我只要访问而不需要顺序,因此可以选择哈希表。举个最好的例子,就是我的LeetCode的博文里——Longest Consecutive Sequence这一题,我的方法二就是用的unordered_map来实现“空间弥补时间”这样的做法。

二、unordered_map与map

虽然都是map,但是内部结构大大的不同哎,map的内部结构是R-B-tree来实现的,所以保证了一个稳定的动态操作时间,查询、插入、删除都是O(logn),最坏和平均都是。而unordered_map如前所述,是哈希表。顺便提一下,哈希表的查询时间虽然是O(1),但是并不是unordered_map查询时间一定比map短,因为实际情况中还要考虑到数据量,而且unordered_map的hash函数的构造速度也没那么快,所以不能一概而论,应该具体情况具体分析。

三、unordered_map与unordered_set

后者就是在哈希表插入value,而这个value就是它自己的key,而不是像之前的unordered_map那样有键-值对,这里单纯就是为了方便查询这些值。我在Longest Consecutive Sequence这一题,我的方法一就是用了unordered_set,同样是一个将空间弥补时间的方法。再举个大家好懂的例子,给你A,B两组数,由整数组成,然后把B中在A中出现的数字取出来,要求用线性时间完成。很明显,这道题应该将A的数放到一个表格,然后线性扫描B,发现存在的就取出。可是A的范围太大,你不可能做一个包含所有整数的表,因为这个域太大了,所以我们就用unordered_set来存放A的数,具体实现库函数已经帮你搞定了,如果对于具体怎么去散列的同学又兴趣可以查看《算法导论》的第11章或者《数据结构与算法分析》的第五章,如果要看《算法导论》的同学我给个建议,完全散列你第一遍的时候可以暂时跳过不看,确实有点复杂。

(42)C/C++中extern的用法 ?

在C语言中,修饰符extern用在变量或者函数的声明前,用来说明“此变量/函数是在别处定义的,要在此处引用”。

1:extern修饰变量的声明。举例来说,如果文件a.c需要引用b.c中变量int v,就可以在a.c中声明extern int v,然后就可以引用变量v。这里需要注意的是,被引用的变量v的链接属性必须是外链接(external)的,也就是说a.c要引用到v,不只是取决于在a.c中声明extern int v,还取决于变量v本身是能够被引用到的。这涉及到c语言的另外一个话题--变量的作用域。能够被其他模块以extern修饰符引用到的变量通常是全局变量。还有很重要的一点是,extern int v可以放在a.c中的任何地方,比如你可以在a.c中的函数fun定义的开头处声明extern int v,然后就可以引用到变量v了,只不过这样只能在函数fun作用域中引用v罢了,这还是变量作用域的问题。对于这一点来说,很多人使用的时候都心存顾虑。好像extern声明只能用于文件作用域似的。

2:extern修饰函数声明。从本质上来讲,变量和函数没有区别。函数名是指向函数二进制块开头处的指针。如果文件a.c需要引用b.c中的函数,比如在b.c中原型是int fun(int mu),那么就可以在a.c中声明extern int fun(int mu),然后就能使用fun来做任何事情。就像变量的声明一样,extern int fun(int mu)可以放在a.c中任何地方,而不一定非要放在a.c的文件作用域的范围中。对其他模块中函数的引用,最常用的方法是包含这些函数声明的头文件。

使用extern和包含头文件来引用函数有什么区别呢?
extern的引用方式比包含头文件要简洁得多!extern的使用方法是直接了当的,想引用哪个函数就用extern声明哪个函数。这大概是KISS原则的一种体现吧!这样做的一个明显的好处是,会加速程序的编译(确切的说是预处理)的过程,节省时间。在大型C程序编译过程中,这种差异是非常明显的。

3:此外,extern修饰符可用于指示C或者C++函数的调用规范。比如在C++中调用C库函数,就需要在C++程序中用extern “C”声明要引用的函数。这是给链接器用的,告诉链接器在链接的时候用C函数规范来链接。主要原因是C++和C程序编译完成后在目标代码中命名规则不同。

(43)I/O模型

https://blog.csdn.net/chen134225/article/details/81749980
(44)TCP和UDP的应用场景,从生活中使用的APP的一些例子来讲。

当对网络通信质量有要求时,比如:整个数据要准确无误的传递给对方,这往往对于一些要求可靠的应用,比如HTTP,HTTPS,FTP等传输文件的协议,POP,SMTP等邮件的传输协议。常见使用TCP协议的应用:
1.浏览器使用的:HTTP
2.FlashFXP:FTP
3.Outlook:POP,SMTP
4.QQ文件传输

对当前网络通讯质量要求不高的时候,要求网络通讯速度尽量的快,这时就使用UDP
日常生活中常见使用UDP协议:
1.QQ语音
2.QQ视频
(45)判断两个链表是否相交。

1.判断两个链表最后一个结点是否相同。

2.将第二个链表的头结点接在第一个链表的尾结点后,判断合成的链表是否形成了环。
(46)二叉树的广度优先遍历和深度优先遍历。

//深度优先搜索
//利用栈,现将右子树压栈再将左子树压栈
void DepthFirstSearch(BitNode *root)
{
    stack<BitNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty())
    {
        BitNode *node = nodeStack.top();
        cout << node->data << ' ';
        nodeStack.pop();
        if (node->right)
        {
            nodeStack.push(node->right);
        }
        if (node->left)
        {
            nodeStack.push(node->left);
        }
    }
}

//广度优先搜索
void BreadthFirstSearch(BitNode *root)
{
    queue<BitNode*> nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty())
    {
        BitNode *node = nodeQueue.front();
        cout << node->data << ' ';
        nodeQueue.pop();
        if (node->left)
        {
            nodeQueue.push(node->left);
        }
        if (node->right)
        {
            nodeQueue.push(node->right);
        }
    }
}

(47)快排,堆排,归并哪些是稳定的,假如我要用C++封装一个sort我要用那种比较好。

只有归并是稳定的,封装的话看需求。
(48)现在有一百万个数不重复我要使用那种排序最快最好。

内存足够,快速排序。

内存不够,多路归并排序。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注