淘先锋技术网

首页 1 2 3 4 5 6 7

目录

C/C++

C 和 C++ 的区别

C和C++动态申请内存的区别?

一个C++源文件从文本到可执行文件经历的过程

C++内存分布都有哪些区/操作系统进程的内存分配?堆栈有什么区别?

new 和 malloc 的区别?使用malloc需要注意什么?new的底层实现?delete底层实现过程?

malloc最大可以申请多大的空间?

对虚函数的理解

C++的继承方式,类对象的内存占用大小的问题

C++的sizeof工作方式,内存对齐原则?

sizeof()来求一个类的大小

C++的野指针和内存泄露,如何避免?shared_ptr工作方式,如何实现智能指针引用计数,使用时可能出现什么问题,如何避免循环引用

#include 的顺序以及尖叫括号和双引号的区别...

C++11有哪些新特性

C++多态,动态绑定如何实现

虚函数使用范围及不同情况

虚函数表是什么?

析构函数可以抛出异常吗?

子类继承父类,如果父类的析构函数不是虚函数,会有什么问题?

if(i==3) 与 if(3==i) 哪个写法更好,为什么?

简述匈牙利命名法。

for 循环中语句中使用++i 与使用 i++哪个更好,为什么(当 i 不是基本类型,而是一个类类型时)

简述静态成员函数与普通成员函数,静态全局变量与普通全局变量,静态局部变量与普通局部变量的区别。

a,b 为 2 个整型变量,设计一个算法,不使用临时变量实现值的交换。

#include "…" 与 #include 有什么区别?内联函数(inline),

指针与引用的区别

const 与 virtual 的作用?

const关键字怎么用?哪些场景用 ?

static 的作用

初始化过的static变量和未初始化过的static变量有什么区别?

volatile关键字(易变的)

常量指针和指针常量,分别怎么声明,怎么用?

用宏实现一个返回两个数最大值的功能?

用宏实现的话有什么不安全的地方?

对函数局部变量生存周期的理解?

静态局部变量在函数初次调用时和调用后的行为?

如何防止头文件被重复引用?

main函数执行前会做些什么工作?

讲一讲对extern的理解

sizeof()与strlen()的区别

堆排序/二分排序

求斐波那契数列?非递归如何实现?

给定一个字符串,求最长的重复子串?

strcpy与memcpy的区别?字符串复制函数strcpy的弊端?

如何查询1000万个数里最小的100个数?最小堆

函数指针了解吗?如何定义和初始化函数指针?函数指针通常用在什么地方?

STL

vector 与 list 的区别

vector查找倒数第二位数字

map容器结构?map 怎么插入数据有几种方式?每种方式的优缺点;

什么是 STL? 列举下 STL 中你常使用的容器,并简单描述。STL 中的迭代器是什么意思?

C++的内存管理方式,STL的allocaotr,最新版本默认使用的分配器

vector增长策略?

vector是如何实现的?

vector在插入新元素时如何申请内存的?

map底层实现?

讲一下AVL树?满二叉树与AVL的区别?

讲一下对红黑树的理解,讲一下红黑树的查找复杂度?为什么查找速度快?

红黑树是怎么实现自平衡的?

hash_map的实现?如何处理冲突?

操作系统

多线程的理解(多线程同步的途径)

多进程(继承什么, 不继承什么)

进程间通信

五种 IO 模型

IO复用之select、poll、epoll区别

C++线程中的锁有那些类型呢

多线程多进程

线程间同步的方式,进程间同步的方式和进程间通信的方式

怎么创建管道 pipe()

操作系统内存管理

进程和线程的区别,切换方式,具体切换过程,涉及到哪些操作,多线程共享哪些资源,哪些是独立的?

服务器多个线程切换如何减少创建的开销,线程池如何实现?

怎么创建共享内存 shmget();

简述一个 windows 窗口程序的创建过程。

Windows 窗口程序在获取消息时,调用 GetMessage()与 PeekMessage()有什么区别?

什么是句柄(HANDLE)? 什么是回调函数(CALLBACK)?

简述 windows 中的消息处理过程。

程序设计模式(单例模式、工厂模式、观察者模式)

生产者、消费者问题

ET 模式与 LT 模式的区别

同步异步概念?什么是非阻塞模式?

为什么在操作系统中引入线程?使用线程池提高并发度,并降低频繁创建线程的开销。怎么提高并发度的,为什么说创建线程的开销大?

怎么给线程分配任务的?(RR策略)有没有什么优化方式?

多线程实现方式

写时复制/拷贝技术,具体的数据是如何在存储之间传递的?

Linux

gdb 的使用, 编译器的使用

常见的 Linux 的命令

如何查询某个文件被哪些进程占用,如何查询当前系统的cpu和内存占用

数据库

数据库索引,B和B+树的区别

数据库存储过程

数据库存储引擎

MySQL 查询前 100 条数据, 以及如何分组

计算机网络

OSI七层模型/TCP/IP四层模型?

TCP 和 UDP 的区别

socket 的流程?服务端的socket过程是什么?

 

三次握手?四次挥手?

TCP 有哪些字段

TCP粘包,拆包及解决方法、丢包的原因及解决办法

了解 HTTP, TCP 吗

HTTP 报文, 一个 HTTP 请求包括

HTTP报文首字段

常见HTTP方法

常见 HTTP 响应码有哪些

什么是HTTP 长连接,什么是短连接, 它们各自的使用场景是什么?

HTTP和HTTPS的区别,HTTPS的具体握手步骤,建立连接完成以后通信过程用什么加密方式

TCP、UDP 的工作流程;客服端服务器端的创建连接啊等等的流程

 TCP是如何保证消息可靠,滑动窗口工作方式,TCP拥塞控制-慢启动、拥塞避免、快重传、快启动

通信过程,哪些情况些会出现返回reset

浏览器搜索淘宝,具体的调用流程,具体用到了什么协议?

如果在三次握手结束后,客户端断电了,服务端可以得知吗?服务端会主动断开连接吗?

malloc如果遇到内存不足以申请的情况怎么办?new呢?


C/C++

C 和 C++ 的区别

C 是面向过程的一门编程语言,C++ 可以很好地进行面向对象的程序设计。C++ 虽然主要是以 C 的基础发展起来的一门新语言,但它不是 C 的替代品,它们是兄弟关系。面向对象和面向过程不是矛盾的,而是各有用途、互为补充的。C++ 对 C 的增强,表现在六个方面:

1、增强了类型检查机制:传统上 C 使用 void* 指针指向不同对象,使用时强制转换回原始类型或兼容类型。这样做的缺陷是绕过了编译器的类型检查,如果错误转换了类型并使用,会造成程序崩溃等严重问题。C++ 通过使用基类指针或引用来代替 void* 的使用,避免了这个问题(其实也是体现了类继承的多态性)。

  1. 增加了面向对象的机制:C面向过程,C++面向对象
  2. 增加了泛型编程的机制(template)
  3. 增加了异常处理
  4. 增加了重载的机制
  5. 增加了标准模板库(STL)

C和C++动态申请内存的区别?

参考:https://blog.csdn.net/u011692048/article/details/78531639

c使用malloc和free,c++则是new和delete。申请释放都差不多,那么它们之间到底是否有差别呢?
C 语言的malloc() 和free() 并不会调用析构函数和构造函数。C++的 new 和 delete 操作符 是 “类意识” ,并且当调用new的时候会调用类的构造函数和当delete 调用的时候会调用析构函数。
注意:混合用malloc 和delete或者混合用new 和free 是不正确的。C++的new和delete是C++用构造器分配内存,用析构函数清除使用过的内存。

new/delete 优点:
1、new/delete调用 constructor/destructor.Malloc/free 不会.
2、new 不需要类型强制转换。.malloc 要对放回的指针强制类型转换.
3、new/delete操作符可以被重载, malloc/free 不会
4、new 并不会强制要求你计算所需要的内存 ( 不像malloc)
注意:
malloc: 用于申请一段新的地址
calloc: 用于申请N段新的地址
realloc: realloc是给一个已经分配了地址的指针重新分配空间
free: 通过指针释放内存c申请返回的是一个指针,而c++返回的是一个副本。
C++中注意:
1、如果删除操作符被应用在基类中,并且其析构函数并不是虚函数,这将会引起内存泄露,因为只有基类的内存被释放掉。
2、基类的析构函数不是纯虚函数,将不能被作为基类而实现。
3、类的析构函数可以不是virtual。
总结如下:
1. C 语言的malloc() 和free() 并不会调用析构函数和构造函数。C++的 new 和 delete 操作符 是 “类意识” ,并且当调用new的时候会调用类的构造函数和当delete 调用的时候会调用析构函数。
2. c函数返回一个指针,c++返回一个副本
3. C++虚析构函数中应当注意的
4. C++自身的保护机制。

一个C++源文件从文本到可执行文件经历的过程

1).预处理,产生.ii文件

2).编译,产生汇编文件(.s文件)

3).汇编,产生目标文件(.o或.obj文件)

4).链接,产生可执行文件(.out或.exe文件)

C++内存分布都有哪些区/操作系统进程的内存分配?堆栈有什么区别?

https://img-blog.csdnimg.cn/2020031618331882.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MjYyNzI3,size_16,color_FFFFFF,t_70

栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等。在一个进程中,位于用户虚拟地址空间顶部的是用户栈,编译器用它来实现函数的调用。和堆一样,用户栈在程序执行期间可以动态地扩展和收缩。

堆,就是那些由 new 分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个 new 就要对应一个 delete。如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收。堆可以动态地扩展和收缩。

自由存储区,就是那些由 malloc 等分配的内存块,他和堆是十分相似的,不过它是用 free 来结束自己的生命的。

全局/静态存储区,全局变量和静态变量被分配到同一块内存中,在以前的 C 语言中,全局变量又分为初始化的和未初始化的(初始化的全局变量和静态变量在一块区域,未初始化的全局变量与静态变量在相邻的另一块区域,同时未被初始化的对象存储区可以通过 void* 来访问和操纵,程序结束后由系统自行释放),在 C++ 里面没有这个区分了,他们共同占用同一块内存区。

常量存储区,这是一块比较特殊的存储区,他们里面存放的是常量,不允许修改(当然,你要通过非正当手段也可以修改,而且方法很多

堆和栈的区别
首先是管理方式不同,堆由程序员负责申请和释放,栈是编译器负责的,然后是结构不同,堆是一种从底部往顶部扩展的结构,栈是从顶部到底部刚好相反的结构,最后是效率有很大的不同,堆的申请和释放都需要经过算法计算,因为要减少内存碎片和提高内存使用率,而栈由编辑器负责,速度非常快,在这点上堆的效率比较低

new 和 malloc 的区别?使用malloc需要注意什么?new的底层实现?delete底层实现过程?

参考:https://blog.csdn.net/ZWE7616175/article/details/80330800

一、new和malloc区别?

1.所属语言
new是C++特性,malloc是C的。C++一般使用的new,但也可以使用malloc,而C用malloc、realloc、calloc。
2.申请释放方式
new和delete,malloc和free配对使用。new的使用比malloc简单,内部已经实现了大小的计算、类型转换等工作,而malloc使用时需要计算大小及进行类型转换。
3.malloc是标准库函数,new是C++的运算符。
new可以被重载,但malloc不可以,malloc需要库函数的支持,new不需要。
4.构造与析构
new和delete会自动调用构造函数和析构函数,但是malloc和free不会。
5.申请内存失败
申请内存失败,默认new抛出异常,malloc返回NULL。
6.重新分配内存
malloc可利用realloc重新分配内存,new不可以。
7.类型安全性
new会检查类型是否对应,如果不对应会保存,但malloc只关注申请内存的多少,不会检查类型。
8.类型转换
malloc返回的类型是void,所以在调用malloc时要进行显式的类型转换,将void转换成所需的指针类型,new不需要。
9.数组分配
new有明确的方式处理数组的分配,即new[],释放也有delete[],malloc没有。
10.设置内存分配器
new可以设置自己的内存分配器,malloc不可以。

二、malloc需要注意什么?

使用malloc申请内存空间需要了解:1)内存分配给谁?2)分配多大的内存?3)是否还有足够内存分配?4)内存将用来存储什么格式的数据?5)分配的内存在哪里?

使用malloc函数申请内存空间注意事项:1)内存是否申请成功? if( NULL !=p )2)使用结束后,一定要释放,要求malloc和free符合一夫一妻制;3)内存释放后(使用free函数之后指针变量p本身保存的地址并没有改变),需要将p的值赋值为NULL(拴住野指针)。

三、new底层实现

1.内存被分配(通过operator new函数)
2.为被分配的内存调用一个或多个构造函数

operator new伪代码:

void *operator new(size_t size)//operator new可能还有其他参数
{
  if(size == 0)
     size = 1;//处理0字节请求时,把它当做1个字节请求进行处理

  while(1){
   分配size字节内存
   if(分配成功)
     return (指向内存的指针);

   //如果分配不成功
   new_handler globalHandler = set_new_handler(0);//卸除new_handler
   set_new_handler(globalHandler);

  if(globalHandler)
    (*globalHandler)();
  else
    thow std::alloc();//指向出错处理的函数指针为空,抛出异常
  }
}

1.调用set_new_handler函数,输入参数为X的出错处理函数。使得X的new_handler函数成为全局new_handler函数。(标准set_new_handler函数存在于std空间)。

2.调用全局的operator new分配内存。如果一次分配失败,全局的operator new会调用X的new_handler(new_handler函数是全局的),如果全局的new_handler最终未能分配到内存, new_handler抛出std::bad_alloc异常,X的operator new会捕捉到它。X的operator new然后会恢复最初被取代的全局new_handler函数,最后以抛出异常返回。

3.假设全局operator new为类型X的对象分配内存成功,X的operator new会再次调用标准set_new_handler函数来恢复最初的全局出错处理函数,最后返回分配成功的内存的指针。

operator new内部包含一个无限循环,跳出循环的办法有4种,分别为:得到了更多的可用内存、安装了一个新的new_handler(出错处理函数)、卸除了new_handler,抛出了一个std::bad_alloc或其派生类型的异常、返回失败。

operator new在无法完成内存分配请求时,会在抛出异常之前调用客户指定的一个出错处理函数new_handler函数。
指定出错处理函数时要用到set_new_handler函数,在头文件大致是:

typedef void (*new_handler());
new_handler set_new_handler(new_handler p)
{
  throw();
}

四、delete底层实现过程

1.为将被释放的内存调用一个或多个析构函数
2.释放内存(通过operator delete函数)

析构函数里对指针成员调用delete,原因是增加一个指针成员会做下边的几项工作:
1.在每个构造函数里对指针进行初始化。对于一些构造函数,如果没有内存要分配给指针的话,指针需要初始化为空指针。
2.删除现有内存,通过赋值操作符分配给指针新的内存。
3.在析构函数里删除指针。

如果在构造函数中忘记初始化某个指针,或者在赋值操作的过程中忘记处理,问题很快就会出现,程序出错。但是要是忘记在析构函数中删除指针,不会立即出错,只能表现为一点的内存泄露,并不断的增长,最后占用所有的内存导致程序挂掉。所以,一定要注意,析构函数对指针必须使用delete。

五、底层做的工作

1.new T类型
(1)调用operator new(sizeof(T)),该函数的函数原型为void* operator new(size_t size)。
(2)调用operator new中的malloc(set_new_handle),如果申请成功,返回;申请失败(可能原因是内存空间不足),采取应对措施set_new_handler,如果应对措施没有,抛出一个异常。
(3)调用一个构造函数。构造函数显示给出,编译器自动合成。

2.delete p
(1)调用一个析构函数。
(2)调用operator delete,释放空间地址。
(3)调用free函数。

3.new T[N]
(1)调用operator new[] (N*sizeof(T)),会在申请的空间的头部多给4个字节的空间,用来存放N。
(2)调用operator new函数
(3)调用malloc函数
(4)调用N次构造函数,构造出来N个对象。
(5)返回第一个对象所在的首地址,不是原空间的地址,而是原空间的地址向后偏移4个位置。

4.delete[] p
(1)取出N(在空间的前四个字节中)。

*((int*)p-1)
*[(int*)((int)p-4)]
1
2
(2)调用N次析构函数。
(3)调用operator delete[] (p)。
(4)调用operator delete。
(5)调用free函数。

malloc最大可以申请多大的空间?

考虑32位linux情况的话,依据版本的话
如果是2.4版本之前的话,因为映射区是在1G地址位置,而且映射区与栈相对生长,malloc申请的空间大于128KB的话,调用的是mmap函数,因此分配的地址起始在1G位置,末端为3G,最大2G左右,所以一次最大申请为2G左右,如果小块小块累计申请的话算上堆区128M到1G区间的话,小块申请 malloc调用brk总和就0.9G,累计能申请到的为2.9G。
2.6到当前版本的话,因为映射区是在顶端靠近栈区,但是生长方向向下,与堆向上相对,一次malloc申请大空间,malloc调用mmap()能最大申请到2.9G左右,算上堆区128M开始向上小块累计的话,(因为2.9G被mmap了)累计就剩下零头,累计申请最大也是2.9G。
现在分配的才是虚拟地址(不是物理内存,即使物理内存才0.5G),只有真正使用的话,才会建立页表开始关联物理内存。

对虚函数的理解

什么是虚函数?什么是纯虚函数?什么是抽象类?构造函数能否为虚函数? 析构函数能否为虚函数?简述虚函数机制。

虚函数概念

虚函数:不代表一定需要子类去实现,而是可以通过基类的指针调用子类的此函数。

纯虚函数:一定需要子类去实现它,它定义的仅仅是一组行为,拥有纯虚函数的类即为抽象类,只能当做基类,无法实例化。

抽象类:包含纯虚函数的类称为抽象类。由于抽象类包含了没有定义的纯虚函数,所以不能定义抽象类的对象。在C++中,我们可以把只能用于被继承而不能直接创建对象的类设置为抽象类(Abstract Class)。

抽象类的规定

(1)抽象类只能用作其他类的基类,不能建立抽象类对象。

(2)抽象类不能用作参数类型、函数返回类型或显式转换的类型。

(3)可以定义指向抽象类的指针和引用,此指针可以指向它的派生类,进而实现多态性。

构造函数不能为虚函数,而析构函数可以且常常是虚函数。

为什么构造函数不能为虚函数?

1)从存储空间角度

虚函数对应一个虚函数表vtable,这个vtable其实是存储在对象的内存空间的。但是,如果构造函数是虚的,就需要通过vtable来调用,可是对象还没有实例化,也就是内存空间还没有,无法找到vtable,所以构造函数不能是虚函数。

即vtable是在构造函数调用后才建立,因而构造函数不可能成为虚函数。

2)从使用角度:虚函数主要用于在信息不全的情况下,能使重载的函数得到对应的调用。构造函数本身就是要初始化实例,那使用虚函数也没有实际意义,所以构造函数没有必要是虚函数。

虚函数机制:MFC

2、为什么叫“虚”函数呢

正是这个函数调用的不可预测性,而这种不可预测性即函数的调用在编译阶段无法确定,待执行时才能确定函数调用的真正地址

3、为什么当做基类的类的析构函数一定要是“虚函数”?

析构函数执行时先调用派生类的析构函数,其次才调用基类的析构函数。如果析构函数不是虚函数,而程序执行时又要通过基类的指针去销毁派生类的动态对象,那么用delete销毁对象时,只调用了基类的析构函数,未调用派生类的析构函数。这样会造成销毁对象不完全、内存泄露。

C++的继承方式,类对象的内存占用大小的问题

1、C++继承方式?

三种继承方式:public,protected,private。如上图所示:

1)当public继承的时候,父类中public类型的成员会被继承到子类的public中去,而父类的protected成员也会被继承到子类的protected中去

当protected继承的时候,父类中无论是public的还是protected的成员都会被继承到子类的protected中去

当private继承的时候,父类中 public 和 protected 的成员都会被继承到子类的private中去

注意:父类的private成员是无论如何都不能被继承的。

C++sizeof工作方式,内存对齐原则?

sizeof是运算符,而非函数。关于sizeof的两个精巧的宏实现。一切的根源就是指针步长
非数组的sizeof:
#defne _sizeof(T) ( (size_t)((T*)0 + 1))
数组的sizeof:
#define array_sizeof(T)   ( (size_t)(&T+1)  - (size_t)(&T)  )
原理就是c/c++中的指针运算。

内存对齐原则:

1).数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小(只要该成员有子成员,比如说是数组,结构体等)的整数倍开始(比如int在32位机为4字节, 则要从4的整数倍地址开始存储),基本类型不包括struct/class/uinon。

2).结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部"最宽基本类型成员"的整数倍地址开始存储.(struct a里存有struct b,b里有char,int ,double等元素,那b应该从8的整数倍开始存储.)。

3).收尾工作:结构体的总大小,也就是sizeof的结果,.必须是其内部最大成员的"最宽基本类型成员"的整数倍.不足的要补齐.(基本类型不包括struct/class/uinon)。

4).sizeof(union),以结构里面size最大元素为union的size,因为在某一时刻,union只有一个成员真正存储于该地址。

sizeof()来求一个类的大小

参考:https://blog.csdn.net/starstar1992/article/details/61619422

先,类的大小是什么?确切的说,类只是一个类型定义,它是没有大小可言的。 用sizeof运算符对一个类型名操作,得到的是具有该类型实体的大小。

如果 Class A; A obj; 那么sizeof(A)==sizeof(obj) 那么sizeof(A)的大小和成员的大小总和是什么关系呢,很简单,一个对象的大小大于等于所有非静态成员大小的总和。
sizeof一个空类,带有构造函数的,以及虚函数的:

#include<iostream>
using namespace std;
class A
{
};
class B
{
public:
    B() {}
    ~B() {}
};
class C
{
public:
    C() {}
    virtual ~C() {}
};
int main()
{
    cout <<"sizeof一个空类的大小为  "<< sizeof(A) << endl;//1
    cout << "sizeof一个带有构造函数和析构函数的类的大小为  " << sizeof(B) << endl;//1
    cout << "sizeof一个带有虚函数的类的大小为  " << sizeof(C) << endl;//4
    return 0;

}

上述结果分别是:1,1,4

class A是一个空类型,它的实例不包含任何信息,本来求sizeof应该是0。但当我们声明该类型的实例的时候,它必须在内存中占有一定的空间,否则无法使用这些实例。至于占用多少内存,由编译器决定。Visual Studio 2008中每个空类型的实例占用一个byte的空间。

class B在class A的基础上添加了构造函数和析构函数。由于构造函数和析构函数的调用与类型的实例无关(调用它们只需要知道函数地址即可),在它的实例中不需要增加任何信息。所以sizeof(B)和sizeof(A)一样,在Visual Studio 2008中都是1。

class C在class B的基础上把析构函数标注为虚拟函数。C++的编译器一旦发现一个类型中有虚拟函数,就会为该类型生成虚函数表,并在该类型的每一个实例中添加一个指向虚函数表的指针。在32位的机器上,一个指针占4个字节的空间,因此sizeof(C)是4。

C++标准规定类的大小不为0,空类的大小为1,当类不包含虚函数和非静态数据成员时,其对象大小也为1。 如果在类中声明了虚函数(不管是1个还是多个),那么在实例化对象时,编译器会自动在对象里安插一个指针指向虚函数表VTable,在32位机器上,一个对象会增加4个字节来存储此指针,它是实现面向对象中多态的关键。而虚函数本身和其他成员函数一样,是不占用对象的空间的。
sizeof类中带有成员变量的

class D {

    char ch;

    void func() { }

};

class E {

    char ch1; //占用1字节

    char ch2; //占用1字节

    virtual void func() { }

};
class F {

    int in;

    virtual void func() { }

};

    cout << "D的大小"<< sizeof(D) << endl;//1
    cout << "E的大小" << sizeof(E) << endl;//8
    cout << "F的大小" << sizeof(E) << endl;//8

注意内存对齐!

sizeof求继承类的大小

等于基类的和,但是要注意字节对齐。不过这个和一般的字节对齐还不一样,比如I,按理说应该是4(1)+4+4(1),但是实际应该是4(1+1)+4。

C++的野指针和内存泄露,如何避免?shared_ptr工作方式,如何实现智能指针引用计数,使用时可能出现什么问题,如何避免循环引用

1、C++的野指针和内存泄漏,如何避免?

内存泄漏概念:用动态存储分配函数动态开辟的空间,在使用完毕后未释放,结果导致一直占据该内存单元。直到程序结束。即所谓内存泄漏。注意:内存泄漏是指堆内存的泄漏。简单的说就是申请了一块内存空间,使用完毕后没有释放掉。它的一般表现方式是程序运行时间越长,占用内存越多,最终用尽全部内存,整个系统崩溃。由程序申请的一块内存,且没有任何一个指针指向它,那么这块内存就泄露了。

野指针概念:“野指针”不是NULL指针,是指向“垃圾”内存的指针。人们一般不会错用NULL指针,因为用if语句很容易判断。但是“野指针”是很危险的,if语句对它不起作用。野指针的成因主要有两种:1)指针变量没有被初始化。任何指针变量刚被创建时不会自动成为NULL指针,它的缺省值是随机的,它会乱指一气。所以,指针变量在创建的同时应当被初始化,要么将指针设置为NULL,要么让它指向合法的内存。2)指针p被free或者delete之后,没有置为NULL,让人误以为p是个合法的指针。别看free和delete的名字恶狠狠的(尤其是delete),它们只是把指针所指的内存给释放掉,但并没有把指针本身干掉。通常会用语句if (p != NULL)进行防错处理。很遗憾,此时if语句起不到防错作用,因为即便p不是NULL指针,它也不指向合法的内存块。

避免方法:free()释放的是指针指向的内存!注意!释放的是内存,不是指针!这点非常非常重要!指针是一个变量,只有程序结束时才被销毁。释放了内存空间后,原来指向这块空间的指针还是存在!只不过现在指针指向的内容的垃圾,是未定义的,所以说是垃圾。因此,前面我已经说过了,释放内存后把指针指向NULL,防止指针在后面不小心又被解引用了。非常重要啊这一点!在使用指针的时候还要注意的问题:1)不要返回指向栈内存的指针或引用,因为栈内存在函数结束时会被释放.2) 在使用指针进行内存操作前记得要先给指针分配一个动态内存。

智能指针概念:由于 C++ 语言没有自动内存回收机制,程序员每次 new 出来的内存都要手动 delete,比如流程太复杂,最终导致没有 delete,异常导致程序过早退出,没有执行 delete 的情况并不罕见,并造成内存泄露。如此c++引入智能指针 ,智能指针即是C++ RAII的一种应用,可用于动态资源管理,资源即对象的管理策略。 智能指针在 <memory> 标头文件的 std 命名空间中定义。 它们对 RAII 或获取资源即初始化编程惯用法至关重要。RAII 的主要原则是为所有堆分配资源提供所有权,例如动态分配内存或系统对象句柄、析构函数包含要删除或释放资源的代码的堆栈分配对象,以及任何相关清理代码

c++ 智能指针主要包括:unique_ptr,shared_ptr, weak_ptr, 这三种,其中auto_ptr 已被遗弃。

参考:https://blog.csdn.net/daniel_ustc/article/details/23096229

unique_ptr
只允许基础指针的一个所有者。 可以移到新所有者(具有移动语义),但不会复制或共享(即我们无法得到指向同一个对象的两个unique_ptr)。 替换已弃用的 auto_ptr。 相较于 boost::scoped_ptr。 unique_ptr 小巧高效;大小等同于一个指针,支持 rvalue 引用,从而可实现快速插入和对 STL 集合的检索。 头文件:<memory>。

使用unique_ptr,可以实现以下功能:1、为动态申请的内存提供异常安全。2、将动态申请内存的所有权传递给某个函数。3、从某个函数返回动态申请内存的所有权。4、在容器中保存指针。5、所有auto_ptr应该具有的(但无法在C++ 03中实现的)功能。

shared_ptr
采用引用计数的智能指针。 shared_ptr基于“引用计数”模型实现,多个shared_ptr可指向同一个动态对象,并维护了一个共享的引用计数器,记录了引用同一对象的shared_ptr实例的数量。当最后一个指向动态对象的shared_ptr销毁时,会自动销毁其所指对象(通过delete操作符)。shared_ptr的默认能力是管理动态内存,但支持自定义的Deleter以实现个性化的资源释放动作。头文件:<memory>。
基本操作:shared_ptr的创建、拷贝、绑定对象的变更(reset)、shared_ptr的销毁(手动赋值为nullptr或离开作用域)、指定deleter等操作。shared_ptr的创建,有两种方式,一,使用函数make_shared(会根据传递的参数调用动态对象的构造函数);二,使用构造函数(可从原生指针、unique_ptr、另一个shared_ptr创建)

 weak_ptr
结合 shared_ptr 使用的特例智能指针。 weak_ptr 提供对一个或多个 shared_ptr 实例所属对象的访问,但是,不参与引用计数。 如果您想要观察对象但不需要其保持活动状态,请使用该实例。 在某些情况下需要断开 shared_ptr 实例间的循环引用。 头文件:<memory>。

weak_ptr的用法:weak_ptr用于配合shared_ptr使用,并不影响动态对象的生命周期,即其存在与否并不影响对象的引用计数器。weak_ptr并没有重载operator->和operator *操作符,因此不可直接通过weak_ptr使用对象。提供了expired()与lock()成员函数,前者用于判断weak_ptr指向的对象是否已被销毁,后者返回其所指对象的shared_ptr智能指针(对象销毁时返回”空“shared_ptr)。循环引用的场景:如二叉树中父节点与子节点的循环引用,容器与元素之间的循环引用等。

智能指针的循环引用

循环引用问题可以参考这个链接上的问题理解,“循环引用”简单来说就是:两个对象互相使用一个shared_ptr成员变量指向对方的会造成循环引用。导致引用计数失效。

解除这种循环引用有下面有三种可行的方法(参考):
1. 当只剩下最后一个引用的时候需要手动打破循环引用释放对象。
2. 当A的生存期超过B的生存期的时候,B改为使用一个普通指针指向A。
3. 使用弱引用的智能指针打破这种循环引用。
虽然这三种方法都可行,但方法1和方法2都需要程序员手动控制,麻烦且容易出错。我们一般使用第三种方法:弱引用的智能指针weak_ptr。

强引用和弱引用
一个强引用当被引用的对象活着的话,这个引用也存在(就是说,当至少有一个强引用,那么这个对象就不能被释放)。share_ptr就是强引用。相对而言,弱引用当引用的对象活着的时候不一定存在。仅仅是当它存在的时候的一个引用。弱引用并不修改该对象的引用计数,这意味这弱引用它并不对对象的内存进行管理,在功能上类似于普通指针,然而一个比较大的区别是,弱引用能检测到所管理的对象是否已经被释放,从而避免访问非法内存。

#include 的顺序以及尖叫括号和双引号的区别...

我们知道C++已经有一些编写好的头文件(比如标准函数库等等),它们存放在VC++的Include文件夹里。当我们使用#include <文件名>命令时,编译器就到这个文件夹里去找对应的文件。显然,用这种写法去包含一个我们自己编写的头文件(不在那个Include文件夹里)就会出错了。所以包含C++提供的头文件时,应该使用尖括号。
3、进程和线程,为什么要有线程

C++11有哪些新特性

1、新增基于范围的for循环:类似Java中foreach语句,为遍历数组提供了很大方便。

int nArr[5] = {1,2,3,4,5};for(int &x : nArr){x *=2;   //数组中每个元素倍乘}

2、自动类型推断 auto:它的作用就是当编译器在一个变量声明的时候,能够根据变量赋的值推断该变量的数据类型。这样就有些逼近Python中定义变量的功能,无需提前声明定义的变量的数据类型。

3、匿名函数 Lambda:如果代码里面存在大量的小函数,而这些函数一般只被一两处调用,那么不妨将它们重构成Lambda表达式,也就是匿名函数。作用就是当你想用一个函数,但是又不想费神去命名一个函数。

4、后置返回类型(tailng-return-type)

template Ret adding_func(const Lhs &lhs, const Rhs &rhs) {return lhs + rhs;}

这不是合法的C++,因为lhs和rhs还没定义;解析器解析完函数原型的剩余部分之前,它们还不是有效的标识符。为此, C++11引入了一种新的函数声明语法,叫做后置返回类型(trailing-return-type)。
5、为什么可变参数模板至关重要,右值引用,完美转发,lambda

C++11的新特性--可变模版参数(variadic templates)是C++11新增的最强大的特性之一,它对参数进行了高度泛化,它能表示0到任意个数、任意类型的参数。相比C++98/03,类模版和函数模版中只能含固定数量的模版参数,可变模版参数无疑是一个巨大的改进。然而由于可变模版参数比较抽象,使用起来需要一定的技巧,所以它也是C++11中最难理解和掌握的特性之一。虽然掌握可变模版参数有一定难度,但是它却是C++11中最有意思的一个特性,本文希望带领读者由浅入深的认识和掌握这一特性。声明可变参数模板时需要在typename或class后面带上省略号“...”。比如我们常常这样声明一个可变模版参数:template<typename...>或者template<class...>

C++多态,动态绑定如何实现

动态绑定与静态绑定
静态绑定:编译时绑定,通过对象调用
动态绑定:运行时绑定,通过地址实现

只有采用“指针->函数()”或“引用变量.函数()”的方式调用C++类中的虚函数才会执行动态绑定。对于C++中的非虚函数,因为其不具备动态绑定的特征,所以不管采用什么样的方式调用,都不会执行动态绑定。
即所谓动态绑定,就是基类的指针或引用有可能指向不同的派生类对象,对于非虚函数,执行时实际调用该函数的对象类型即为该指针或引用的静态类型(基类类型);而对于虚函数,执行时实际调用该函数的对象类型为该指针或引用所指对象的实际类型

虚函数使用范围及不同情况

C++中的虚函数实现了多态的机制,也就是用父类型指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数,这种技术可以让父类的指针有“多种形态”,这也是一种泛型技术,也就是使用不变的代码来实现可变的算法

1、什么是虚函数
C++书中介绍为了指明某个成员函数具有多态性,用关键字virtual来标志其为虚函数。传统的多态实际上就是由虚函数(Virtual Function)利用虚表(Virtual Table)实现的也就是说,虚函数应为多态而生。

2、什么时候用到虚函数
既然虚函数虚函数应为多态而生,那么简单的说当我们在C++和C#中要想实现多态的方法之一就是使用到虚函数。复杂点说,那就是因为OOP的核心思想就是用程序语言描述客观世界的对象,从而抽象出一个高内聚、低偶合,易于维护和扩展的模型。

但是在抽象过程中我们会发现很多事物的特征不清楚,或者很容易发生变动,怎么办呢?比如飞禽都有飞这个动作,但是对于不同的鸟类它的飞的动作方式是 不同的,有的是滑行,有的要颤抖翅膀,虽然都是飞的行为,但具体实现却是千差万别,在我们抽象的模型中不可能把一个个飞的动作都考虑到,那么怎样为以后留 下好的扩展,怎样来处理各个具体飞禽类千差万别的飞行动作呢?比如我现在又要实现一个类“鹤”,它也有飞禽的特征(比如飞这个行为),如何使我可以只用简 单地继承“飞禽”,而不去修改“飞禽”这个抽象模型现有的代码,从而达到方便地扩展系统呢?

因此面向对象的概念中引入了虚函数来解决这类问题。

使用虚函数就是在父类中把子类中共有的但却易于变化或者不清楚的特征抽取出来,作为子类需要去重新实现的操作(override)。而虚函数也是OOP中实现多态的关键之一。

3、虚函数/接口/抽象函数
虚函数:可由子类继承并重写的函数,后期绑定
抽像函数:规定其非虚子类必须实现的函数,必须被重写。
接口:必须重写

多态种类和区别
C++ 中的多态性具体体现在编译和运行两个阶段。编译时多态是静态多态,在编译时就可以确定使用的接口。运行时多态是动态多态,具体引用的接口在运行时才能确定。

静态多态和动态多态的区别其实只是在什么时候将函数实现和函数调用关联起来,是在编译时期还是运行时期,即函数地址是早绑定还是晚绑定的。静态多态是指在编译期间就可以确定函数的调用地址,并生产代码,这就是静态的,也就是说地址是早绑定。静态多态往往也被叫做静态联编。 动态多态则是指函数调用的地址不能在编译器期间确定,需要在运行时确定,属于晚绑定,动态多态往往也被叫做动态联编。
多态的作用:为了接口重用。静态多态,将同一个接口进行不同的实现,根据传入不同的参数(个数或类型不同)调用不同的实现。动态多态,则不论传递过来的哪个类的对象,函数都能够通过同一个接口调用到各自对象实现的方法。

静态多态和动态多态的区别
静态多态往往通过函数重载和模版(泛型编程)来实现。

动态多态最常见的用法就是声明基类的指针,利用该指针指向任意一个子类对象,调用相应的虚函数,可以根据指向的子类的不同而调用不同的方法。如果没有使用虚函数,即没有利用 C++ 多态性,则利用基类指针调用相应函数的时候,将总被限制在基类函数本身,而无法调用到子类中被重写的函数。因为没有多态性,函数调用的地址将是一定的,而固定的地址将始终调用同一个函数,这就无法达到“一个接口,多种实现”的目的了。

虚函数表是什么?

参考:https://www.cnblogs.com/zhxmdefj/p/11594459.html

C++中的虚函数实现了多态的机制,也就是用父类型指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数,这种技术可以让父类的指针有“多种形态”,这也是一种泛型技术,也就是使用不变的代码来实现可变的算法

C++通过继承和虚函数来实现多态性,虚函数是通过一张虚函数表实现的,虚函数表解决了继承、覆盖、添加虚函数的问题,保证其真实反应实际的函数。

C++实现虚函数的方法是:为每个类对象添加一个隐藏成员,隐藏成员保存了一个指针,这个指针叫虚表指针(vptr),它指向一个虚函数表(virtual function table, vtbl)虚函数表就像一个数组,表中有许多的槽(slot),每个槽中存放的是一个虚函数的地址(可以理解为数组里存放着指向每个虚函数的指针)即:每个类使用一个虚函数表,每个类对象用一个虚表指针

在有虚函数的类的实例对象中,这个表被分配在了这个实例对象的内存中(就和上面说的一样),当我们用父类的指针来操作一个子类的时候,这张表就像一个地图一样,指明了实际所应该调用的函数,结构如下

 

析构函数可以抛出异常吗?

抛出异常(也称为抛弃异常)即检测是否产生异常,在C++中,其采用throw语句来实现,如果检测到产生异常,则抛出异常。

C++标准指明析构函数不能、也不应该抛出异常。如果对象在运行期间出现了异常,C++异常处理模型有责任清除那些由于出现异常所导致的已经失效了的对象(也即对象超出了它原来的作用域),并释放对象原来所分配的资源, 这就是调用这些对象的析构函数来完成释放资源的任务,所以从这个意义上说,析构函数已经变成了异常处理的一部分

子类继承父类,如果父类的析构函数不是虚函数,会有什么问题?

C++类有继承时,析构函数必须为虚函数。如果不是虚函数,则使用时可能存在内在泄漏的问题。

  • 若析构函数是虚函数(即加上virtual关键词),delete时基类和子类都会被释放;
  • 若析构函数不是虚函数(即不加virtual关键词),delete时只释放基类,不释放子类;

if(i==3) 与 if(3==i) 哪个写法更好,为什么?

效率上没有区别,第2种的主要目的是防止写成if(n=10)而导致错误,但现在的编译器一般会给出警告信息所以现在不常用了.第1种更符合习惯,只要把相应的编译选项打开,一般不会出问题.第二种会省掉很多  debug  的时间的。

简述匈牙利命名法。

匈牙利命名:开头字母用变量类型的缩写,其余部分用变量的英文或英文的缩写,要求单词第一个字母大写。example:

int iMyAge; “i”是int类型的缩写;

char cMyName[10]; “c”是char类型的缩写;

float fManHeight; “f”是float类型的缩写;

驼峰式命名法:又叫小驼峰式命名法。第一个单词首字母小写,后面其他单词首字母大写。example:
int myAge;
char myName[10];
float manHeight;

帕斯卡命名法:又叫大驼峰式命名法。
每个单词的第一个字母都大写。ex:
int MyAge;
char MyName[10];
float ManHeight;

for 循环中语句中使用++i 与使用 i++哪个更好,为什么(当 i 不是基本类型,而是一个类类型时)

i++由于是在使用当前值之后再+1,所以会需要一个临时变量来转储,而++则直接+1。在没有编译器优化的情况下,++i更好。优化过后两者都一样,看起来似乎喜欢怎样写都无所谓了。但是如果这里的i不是int而是迭代器,那么++在前和在后就会有所不同,使用++i将会有切实的更高的效率。虽然int情况下没多少区别,但为了语法上的统一,最好一律改用++i这种形式。

简述静态成员函数与普通成员函数,静态全局变量与普通全局变量,静态局部变量与普通局部变量的区别。

static全局变量与普通的全局变量

全局变量(外部变量)的说明之前再冠以static就构成了静态的全局变量.全局变量本身就是静态存储方式,静态全局变量当然也是静态存储方式。 这两者在存储方式上并无不同。这两者的区别在于非静态全局变量的作用域是整个源程序,当一个源程序由多个源文件组成时,非静态的全局变量在各个源文件中都是有效的。而静态全局变量则限制了其作用域,即只在定义该变量的源文件内有效,在同一源程序的其它源文件中不能使用它。由于静态全局变量的作用域局限于一个源文件内,只能为该源文件内的函数公用,因此可以避免在其它源文件中引起错误。

static局部变量和普通局部变量

把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期。把全局变量改变为静态变量后是改变了它的作用域,限制了它的使用范围。

static函数与普通函数

static函数与普通函数作用域不同,仅在本文件。只在当前源文件中使用的函数应该说明为内部函数(static),内部函数应该在当前源文件中说明和定义。对于可在当前源文件以外使用的函数,应该在一个头文件中说明,要使用这些函数的源文件要包含这个头文件。

总结

1.static全局变量与普通的全局变量有什么区别:

static全局变量只初使化一次,防止在其他文件单元中被引用。

2.static局部变量和普通局部变量有什么区别:

static局部变量只被初始化一次,下一次依据上一次结果值。

3.static函数与普通函数有什么区别:

static函数在内存中只有一份,普通函数在每个被调用中维持一份拷贝。

a,b 为 2 个整型变量,设计一个算法,不使用临时变量实现值的交换。

1) 算术运算

int  a,b;

a=10;b=12;

a=b-a;//a=2;b=12

b=b-a;//a=2;b=10

a=b+a;//a=12;b=10

2) 指针地址操作

因为对地址的操作实际上进行的是整数运算,比如:两个地址相减得到一个整数,表示两个变量在内存中的储存位置隔了多少个字节;地址和一个整数相加即“a+10”表示以a为基地址的在a后10个a类数据单元的地址。所以理论上可以通过和算术算法类似的运算来完成地址的交换,从而达到交换变量的目的。即:

int*a,*b;//假设*a=newint(10);*b=newint(20);//&a=0x00001000h,&b=0x00001200h

a=(int*)(b-a);//&a=0x00000200h,&b=0x00001200h

b=(int*)(b-a);//&a=0x00000200h,&b=0x00001000h

a=(int*)(b+int(a));//&a=0x00001200h,&b=0x00001000h

3) 位运算

int a=10,b=12;//a=1010^b=1100;

a=a^b;//a=0110^b=1100;

b=a^b;//a=0110^b=1010;

a=a^b;//a=1100=12;

b=1010;

^ 按位异或 若参加运算的两个二进制位值相同则为0,否则为1

此算法能够实现是由异或运算的特点决定的,通过异或运算能够使数据中的某些位翻转,其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次,值不变,(理论上重载“^”运算符,也可以实现任意结构的交换)。

4)栈实现。

#include "…" 与 #include 有什么区别?内联函数(inline),

其实#include后接<>或""包含的文件都是以实现定义(或者说implementation-defined)的方式去搜索的,以""形式包含的文件在无法以这个形式定义的方式搜索时转为使用<>形式包含的方法去搜索,而绝大多数实现里<>表示搜索系统+附加包含路径中的文件,""表示搜索当前源文件所处路径下的文件,这意味着在这些实现下以""形式包含的文件当无法在当前源文件所处路径下搜索到文件时会转而去搜索系统+附加包含路径,

内联函数是C++的增强特性之一,用来降低程序的运行时间。当内联函数收到编译器的指示时,即可发生内联:编译器将使用函数的定义体来替代函数调用语句,这种替代行为发生在编译阶段而非程序运行阶段。值得注意的是,内联函数仅仅是对编译器的内联建议,编译器是否觉得采取你的建议取决于函数是否符合内联的有利条件。如何函数体非常大,那么编译器将忽略函数的内联声明,而将内联函数作为普通函数处理。

指针与引用的区别

对象是指一块能存储数据并具有某种类型的内存空间,一个对象a,它有值和地址&a,运行程序时,计算机会为该对象分配存储空间,来存储该对象的值,我们通过该对象的地址,来访问存储空间中的值

指针p也是对象,它同样有地址&p和存储的值p,只不过,p存储的数据类型是数据的地址。如果我们要以p中存储的数据为地址,来访问对象的值,则要在p前加解引用操作符"*",即*p。

对象有常量(const)和变量之分,既然指针本身是对象,那么指针所存储的地址也有常量和变量之分,指针常量是指,指针这个对象所存储的地址是不可以改变的,而指向常量的指针的意思是,不能通过该指针来改变这个指针所指向的对象。

引用可以理解成变量的别名。定义一个引用的时候,程序把该引用和它的初始值绑定在一起,而不是拷贝它。计算机必须在声明r的同时就要对它初始化,并且,r一经声明,就不可以再和其它对象绑定在一起了。引用的一个优点是它一定不为空,因此相对于指针,它不用检查它所指对象是否为空,这增加了效率。

const 与 virtual 的作用?

虚函数:https://blog.csdn.net/shuzfan/article/details/77165474

const: 在编译器的角度下,const其实给出了地址,而define给出了立即数,然后const是有类型的,表达式运算的时候会进行类型安全检查,而define没有,最后const只在第一次使用的时候访问内存,往后的使用都是访问符号表,define则是普通的字符串替换,具有多个副本。

const一般用于函数的参数保护,以免函数内部不小心修改了只读变量,define其实比较自由,按照Linux的风格,define是有崇高的地位,很多短小精悍的功能都由define完成,如果就定义常量而言,const和define都可以,不过我个人认为const定义的常量比define要高效.

const关键字怎么用?哪些场景用 ?

const一般用于函数的参数保护,以免函数内部不小心修改了只读变量。

使用方法

常变量:   const 类型说明符 变量名

常引用:   const 类型说明符 &引用名

常对象:  类名 const 对象名

常成员函数:  类名::fun(形参) const

常数组:  类型说明符 const 数组名[大小]    

常指针:   const 类型说明符* 指针名 ,类型说明符* const 指针名

都是保护const对象不被修改

example:

const int a;
int const a;
const int *a;
int *const a;
int const *a const;
前两个的作用是一样,a是一个常整型数。第三个意味着a是一个指向常整型数的指针(也就是,整型数是不可修改的,但指针可以)。第四个意思a是一个指向整型数的常指针(也就是说,指针指向的整型数是可以修改的,但指针是不可修改的)。最后一个意味着a是一个指向常整型数的常指针(也就是说,指针指向的整型数是不可修改的,同时指针也是不可修改的)。如果应试者能正确回答这些问题,那么他就给我留下了一个好印象。顺带提一句,也许你可能会问,即使不用关键字 const,也还是能很容易写出功能正确的程序,那么我为什么还要如此看重关键字const呢?我也如下的几下理由:
1). 关键字const的作用是为给读你代码的人传达非常有用的信息,实际上,声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时间清理其它人留下的垃圾,你就会很快学会感谢这点多余的信息。(当然,懂得用const的程序员很少会留下的垃圾让别人来清理的。)
2). 通过给优化器一些附加的信息,使用关键字const也许能产生更紧凑的代码。
3). 合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数,防止其被无意的代码修改。简而言之,这样可以减少bug的出现。

static 的作用

静态局部变量使用static修饰符定义,即使在声明时未赋初值,编译器也会把它初始化为0。且静态局部变量存储于进程的全局数据区,即使函数返回,它的值也会保持不变。

全局变量定义在函数体外部,在全局数据区分配存储空间,且编译器会自动对其初始化。普通全局变量对整个工程可见,其他文件可以使用extern外部声明后直接使用。也就是说其他文件不能再定义一个与其相同名字的变量了(否则编译器会认为它们是同一个变量)。静态全局变量仅对当前文件可见,其他文件不可访问,其他文件可以定义与其同名的变量,两者互不影响。在定义不需要与其他文件共享的全局变量时,加上static关键字能够有效地降低程序模块之间的耦合,避免不同文件同名变量的冲突,且不会误使用。

函数的使用方式与全局变量类似,在函数的返回类型前加上static,就是静态函数。其特性有:静态函数只能在声明它的文件中可见,其他文件不能引用该函数不同的文件可以使用相同名字的静态函数,互不影响。非静态函数可以在另一个文件中直接引用,甚至不必使用extern声明.

初始化过的static变量和未初始化过的static变量有什么区别?

未初始化的全局变量,static变量,编译器会自动初始化为0. 这样可以减少可执行文件的大小。

局部变量的值是不确定的。因为使用的时候会先赋值在使用。

volatile关键字(易变的)

volatile关键字是一种类型修饰符,用它声明的类型变量表示可以被某些编译器未知的因素更改。

用volatile关键字声明的变量i每一次被访问时,执行部件都会从i相应的内存单元中取出i的值。

没有用volatile关键字声明的变量i在被访问的时候可能直接从cpu的寄存器中取值(因为之前i被访问过,也就是说之前就从内存中取出i的值保存到某个寄存器中),之所以直接从寄存器中取值,而不去内存中取值,是因为编译器优化代码的结果(访问cpu寄存器比访问ram快的多)。

以上两种情况的区别在于被编译成汇编代码之后,两者是不一样的。之所以这样做是因为变量i可能会经常变化,保证对特殊地址的稳定访问。

volatile关键字是一种类型修饰符,用它声明的类型变量表示可以被某些编译器未知的因素更改,比如:操作系统、硬件或者其它线程等。遇到这个关键字声明的变量,编译器对访问该变量的代码就不再进行优化,从而可以提供对特殊地址的稳定访问。使用该关键字的例子如下:

volatile int nVint; 

当要求使用volatile 声明的变量的值的时候,系统总是重新从它所在的内存读取数据,即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存。

常量指针和指针常量,分别怎么声明,怎么用?

本质上是,1)“被指向的对象是常量”;2)“指针本身是常量”。

const int p;      // p  为常量,初始化后不可更改
const int* p;     // *p 为常量,不能通过*p改变它指向的内容 
int const* p;     // *p 为常量,同上
int* const p;     // p  为常量,初始化后不能再指向其它内容

用宏实现一个返回两个数最大值的功能?

#define MAX(x, y) \
        ((x) > (y) ? (x) : (y))

//防止参数副作用的实现方法
#define MAX_2(x, y) ({\
        int _x = (x); \
        int _y = (y); \
        _x > _y ? _x : _y; \
})

用宏实现的话有什么不安全的地方?

首先,预处理宏是“全局”的。所以,在 C++ 这样如此强调命名空间、类这样的东西的语言中,全局的东西真是越少越好。但是其实预处理宏的全局并不是语义上的全局,之所以叫预处理宏,是因为预处理宏会在编译器编译代码之前被简单地替换成代码。

然后,正因为预处理宏会被简单替换,所以替换的结果是不可预料的。

对函数局部变量生存周期的理解?

局部变量的作用域一般认为在函数体内有效,其内存分配管理和销毁由编译器来实现。当函数执行完成返回时,局部变量将全部销毁,则其生命周期也随之结束。

全局变量的生命周期等于程序执行时间,程序开始执行时,全局变量将被初始化。

静态局部变量在函数初次调用时和调用后的行为?

参考:https://zhuanlan.zhihu.com/p/93934910

局部变量i的解析:

在连续三次调用func1中,每次调用时,在进入函数func1后都会创造一个新的变量i,

并且给它赋初值1,然后i++时加到2,

然后printf输出时输出2.然后func1本次调用结束,

结束时同时杀死本次创造的这个i。这就是局部变量i的整个生命周期。

下次再调用该函数func1时,又会重新创造一个i,经历整个程序运算,

最终在函数运行完退出时再次被杀死。

静态局部变量(static) 静态局部变量定义时前面加static关键字。

1、静态局部变量和普通局部变量不同。静态局部变量也是定义在函数内部的,静态局部变量定义时前面要加static关键字来标识,静态局部变量所在的函数在多调用多次时,只有第一次才经历变量定义和初始化,以后多次在调用时不再定义和初始化,而是维持之前上一次调用时执行后这个变量的值。本次接着来使用。

2、静态局部变量在第一次函数被调用时创造并初始化,但在函数退出时它不死亡,而是保持其值等待函数下一次被调用。下次调用时不再重新创造和初始化该变量,而是直接用上一次留下的值为基础来进行操作。

3、静态局部变量的这种特性,和全局变量非常类似。它们的相同点是都创造和初始化一次,以后调用时值保持上次的不变。不同点在于作用域不同

如何防止头文件被重复引用?

使用条件编译#ifndef #define #endif 可以防止头文件被重复引用

main函数执行前会做些什么工作?

main函数执行之前主要是初始化系统资源

1、设置栈指针。

2、初始化static静态和global全局变量,即data段内容。

3、将未初始化部分的赋初值:数值型short,int,long等为0,bool为FALSE,指针为NULL,等等,即.bss段的内容。

4、运行全局构造器,估计是C++中构造函数之类的吧

5、将main函数的参数,argc,argv等传递给main函数,然后才真正运行main函数

一般的程序运行过程如下:
1.操作系统创建进程后,把控制权交给程序的入口函数(gcc –e (_startEntryPoint)),   这个函数往往是运行时库的某个入口函数。 glibc 的入口函数是_start,
          msvc(vc6.0)是mainCRTStartup
2. 入口函数对运行库和程序运行环境进行初始化,包括堆,I/O,线程,全局变量构造(constructor)等。
3. 调用MAIN函数,正式开始执行程序主体。
4. 执行MAIN完毕,返回入口函数,进行清理工作,包括全局变量析构,堆销毁,关闭I/O等,然后进行系统调用介绍进程

讲一讲对extern的理解

概念:声明extern关键字的全局变量和函数可以使得它们能够跨文件被访问。全局函数的声明语句中,关键字extern可以省略,因为全局函数默认是extern类型的。如果在一个文件里定义了char g_str[] = "123456";在另外一个文件中必须使用extern char g_str[ ];来声明。不能使用extern char* g_str;来声明。extern是严格的声明。且extern char* g_str只是声明的一个全局字符指针。声明可以拷贝n次,但是定义只能定义一次。

extern “C”

概念:包含双重含义,从字面上即可得到:首先,被它修饰的目标是“extern”的;其次,被它修饰的目标是“C”的。

用法

1、被extern "C"限定的函数或变量是extern类型的:extern是C/C++语言中表明函数和全局变量作用范围(可见性)的关键字,该关键字告诉编译器,其声明的函数和变量可以在本模块或其它模块中使用。

2、实现C++与C及其它语言的混合编程:被extern"C"修饰的变量和函数是按照C语言方式编译和连接的,未加extern “C”则按照声明时的编译方式。

extern 和static

(1)extern表明该变量在别的地方已经定义过了,在这里要使用那个变量。

(2)static 表示静态的变量,分配内存的时候,存储在静态区,不存储在栈上面。

static作用范围是内部连接的关系这和extern有点相反。它和对象本身是分开存储的,extern也是分开存储的,但是extern可以被其他的对象用extern引用,而static不可以,只允许对象本身用它。具体差别首先,static与extern是一对“水火不容”的家伙,也就是说extern和static不能同时修饰一个变量;其次,static修饰的全局变量声明与定义同时进行,也就是说当你在头文件中使用static声明了全局变量后,它也同时被定义了;最后,static修饰全局变量的作用域只能是本身的编译单元,也就是说它的“全局”只对本编译单元有效,

extern和const
C++中const修饰的全局常量具有跟static相同的特性,即它们只能作用于本编译模块中,且static修饰的是全局变量,但是const可以与extern连用来声明该常量可以作用于其他编译模块中,如externconst char g_str[];然后在原文件中别忘了定义:const char g_str[] = "123456";

sizeof()与strlen()的区别

一、sizeof
    sizeof(...)是运算符,在头文件中typedef为unsigned int,其值在编译时即计算好了,参数可以是数组、指针、类型、对象、函数等。
    它的功能是:获得保证能容纳实现所建立的最大对象的字节大小。
    由于在编译时计算,因此sizeof不能用来返回动态分配的内存空间的大小。实际上,用sizeof来返回类型以及静态分配的对象、结构或数组所占的空间,返回值跟对象、结构、数组所存储的内容没有关系。
    具体而言,当参数分别如下时,sizeof返回的值表示的含义如下:
    数组——编译时分配的数组空间大小;
    指针——存储该指针所用的空间大小(存储该指针的地址的长度,是长整型,应该为4);
    类型——该类型所占的空间大小;
    对象——对象的实际占用空间大小;
    函数——函数的返回类型所占的空间大小。函数的返回类型不能是void。

二、strlen
    strlen(...)是函数,要在运行时才能计算。参数必须是字符型指针(char*)。当数组名作为参数传入时,实际上数组就退化成指针了。
    它的功能是:返回字符串的长度。该字符串可能是自己定义的,也可能是内存中随机的,该函数实际完成的功能是从代表该字符串的第一个地址开始遍历,直到遇到结束符NULL。返回的长度大小不包括NULL。

Sizeof与Strlen的区别与联系(转)

1.sizeof操作符的结果类型是size_t,它在头文件中typedef为unsigned int类型。
该类型保证能容纳实现所建立的最大对象的字节大小。

2.sizeof是算符,strlen是函数。

3.sizeof可以用类型做参数,strlen只能用char*做参数,且必须是以''\0''结尾的。
sizeof还可以用函数做参数,比如:
short f();
printf("%d\n", sizeof(f()));
输出的结果是sizeof(short),即2。

4.数组做sizeof的参数不退化,传递给strlen就退化为指针了。

5.大部分编译程序 在编译的时候就把sizeof计算过了 是类型或是变量的长度这就是sizeof(x)可以用来定义数组维数的原因
char str[20]="0123456789";
int a=strlen(str); //a=10;
int b=sizeof(str); //而b=20;

6.strlen的结果要在运行的时候才能计算出来,时用来计算字符串的长度,不是类型占内存的大小。

7.sizeof后如果是类型必须加括弧,如果是变量名可以不加括弧。这是因为sizeof是个操作符不是个函数。

8.当适用了于一个结构类型时或变量, sizeof 返回实际的大小,
当适用一静态地空间数组, sizeof 归还全部数组的尺寸。
sizeof 操作符不能返回动态地被分派了的数组或外部的数组的尺寸

9.数组作为参数传给函数时传的是指针而不是数组,传递的是数组的首地址,
如:
fun(char [8])
fun(char [])
都等价于 fun(char *)
在C++里参数传递数组永远都是传递指向数组首元素的指针,编译器不知道数组的大小
如果想在函数内知道数组的大小, 需要这样做:
进入函数后用memcpy拷贝出来,长度由另一个形参传进去
fun(unsiged char *p1, int len)
{
unsigned char* buf = new unsigned char[len+1]
memcpy(buf, p1, len);
}
我们能常在用到 sizeof 和 strlen 的时候,通常是计算字符串数组的长度
看了上面的详细解释,发现两者的使用还是有区别的,从这个例子可以看得很清楚:
char str[20]="0123456789";
int a=strlen(str); //a=10; >>>> strlen 计算字符串的长度,以结束符 0x00 为字符串结束。
int b=sizeof(str); //而b=20; >>>> sizeof 计算的则是分配的数组 str[20] 所占的内存空间的大小,不受里面存储的内容改变。
上面是对静态数组处理的结果,如果是对指针,结果就不一样了
char* ss = "0123456789";
sizeof(ss) 结果 4 ===》ss是指向字符串常量的字符指针,sizeof 获得的是一个指针的之所占的空间,应该是长整型的,所以是4
sizeof(*ss) 结果 1 ===》*ss是第一个字符 其实就是获得了字符串的第一位'0' 所占的内存空间,是char类型的,占了 1 位,strlen(ss)= 10 >>>> 如果要获得这个字符串的长度,则一定要使用 strlen

堆排序/二分排序

1、堆排序

概念:堆排序是利用这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

堆排序具体看我写的博客:https://blog.csdn.net/qq_27262727/article/details/104372455

2、二分排序

参考:https://blog.csdn.net/qq1641530151/article/details/80631201

概念:在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上。

/**
 * 二分法排序<br>
 * 根据排序原则,每次我们都是在一个有序序列中插入一个新的数字<br>
 * 那么我们可以将这个有序序列进行二分。<br>
 * 左游标left为0,右游标right为i-1(i是这个数字在原数组中的位置)<br>
 * middle初始为。<br>
 * 当left<=right时<br>
 * middle是left和right的中值。<br>
 * 我们作如下操作。如果array[i]的值比array[middle]值大。<br>
 * 那么我们就移动左游标令值为middle+1<br>
 * 负责就移动右游标为middle-1<br>
 * 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入
 * <p style="color:red">时间复杂度n</p>
 */
public int[] binaryInsertSort(int[] array){
	for(int i = 0;i<array.length;i++){
		int temp = array[i];//待插入到前面有序序列的值
		int left = 0;//有序序列的左侧
		int right = i-1;//有序序列的右侧
		int middle = 0;//有序序列的中间
		while(left <= right){
			middle = (left + right)/2;//赋值
			if(temp<array[middle]){
				right = middle-1;
			}else{
				left = middle + 1;
			}
		}
		for(int j = i-1;j>=left;j--){
			//从i-1到left依次向后移动一位,等待temp值插入
			array[j+1] = array[j];
		}
		if(left != i ){
			array[left] = temp;
		}
	}
	return array;
}

求斐波那契数列?非递归如何实现?

参考:https://www.jianshu.com/p/26e0ba026176

//递归版本 
long long Fibonacci(long long num)  
{  
     assert(num >= 0);  

         //递归  
         if ((num == 1) || (num == 0))  
         {  
              return num;  
         }  
             return Fibonacci(num-1)+Fib1(num-2);  
 }  
//非递归
long long Fibonacci(long long num)  
{  
    assert(num >= 0);  
    long long first = 0;  
    long long second = 1;  
    long long third = 0;  
    for(int i=2; i<=num; i++)  
    {  
        third = first + second;  
        first = second;  
        second = third;  
    }  
    return third;  
}  

给定一个字符串,求最长的重复子串?

参考:https://blog.csdn.net/Hackbuteer1/article/details/7968623

直观的解法是,首先检测长度为 n - 1 的字符串情况,如果不存在重复则检测 n - 2, 一直递减下去,直到 1 。
这种方法的时间复杂度是 O(N * N * N),其中包括三部分,长度纬度、根据长度检测的字符串数目、字符串检测。

改进的方法是利用后缀数组

后缀数组:

把s的每个后缀按照字典序排序,

后缀数组sa[i]就表示排名为i的后缀的起始位置的下标

而它的映射数组rk[i]就表示起始位置的下标为i的后缀的排名

简单来说,sa表示排名为i的是啥,rk表示第i个的排名是啥。

后缀数组是一种数据结构,对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分。
这样的时间复杂度为:生成后缀数组 O(N),排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)
依次检测相邻的两个字符串 O(N * N),总的时间复杂度是 O(N^2*logN),优于第一种方法的 O(N^3)

#include <iostream>
using namespace std;
 
#define MAXCHAR 5000 //最长处理5000个字符
 
char c[MAXCHAR], *a[MAXCHAR];
 
int comlen( char *p, char *q )
{
    int i = 0;
    while( *p && (*p++ == *q++) )
        ++i;
    return i;
}
 
int pstrcmp( const void *p1, const void *p2 )
{
    return strcmp( *(char* const *)p1, *(char* const*)p2 );
}
 
 
int main(void)
{
    char ch;
    int  n=0;
    int  i, temp;
    int  maxlen=0, maxi=0;
    printf("Please input your string:\n");
 
	n = 0;
    while( (ch=getchar())!='\n' )
	{
        a[n] = &c[n];
        c[n++] = ch;
    }
    c[n]='\0';     // 将数组c中的最后一个元素设为空字符,以终止所有字符串
 
    qsort( a, n, sizeof(char*), pstrcmp );
    for(i = 0 ; i < n-1 ; ++i )
	{
        temp=comlen( a[i], a[i+1] );
        if( temp>maxlen )
		{
            maxlen=temp;
            maxi=i;
        }
    }
    printf("%.*s\n",maxlen, a[maxi]);
    
    return 0;
}

strcpy与memcpy的区别?字符串复制函数strcpy的弊端?

strcpy和memcpy都是标准C库函数,它们有下面的特点。
strcpy提供了字符串的复制。即strcpy只用于字符串复制,并且它不仅复制字符串内容之外,还会复制字符串的结束符。

已知strcpy函数的原型是:char* strcpy(char* dest, const char* src);
memcpy提供了一般内存的复制。即memcpy对于需要复制的内容没有限制,因此用途更广。

strcpy和memcpy主要有以下3方面的区别。
1、复制的内容不同。strcpy只能复制字符串,而memcpy可以复制任意内容,例如字符数组、整型、结构体、类等。
2、复制的方法不同。strcpy不需要指定长度,它遇到被复制字符的串结束符"\0"才结束,所以容易溢出。memcpy则是根据其第3个参数决定复制的长度。
3、用途不同。通常在复制字符串时用strcpy,而需要复制其他类型数据时则一般用memcpy

void *memcpy( void *dest, const void *src, size_t count );

char * strcpy(char * dest, const char * src) // 实现src到dest的复制
{
  if ((src == NULL) || (dest == NULL)) //判断参数src和dest的有效性
  {
 
      return NULL;
  }
  char *strdest = dest;        //保存目标字符串的首地址
  while ((*strDest++ = *strSrc++)!='\0'); //把src字符串的内容复制到dest下
  return strdest;
}
void *memcpy(void *memTo, const void *memFrom, size_t size)
{
  if((memTo == NULL) || (memFrom == NULL)) //memTo和memFrom必须有效
         return NULL;
  char *tempFrom = (char *)memFrom;             //保存memFrom首地址
  char *tempTo = (char *)memTo;                  //保存memTo首地址      
  while(size -- > 0)                //循环size次,复制memFrom的值到memTo中
         *tempTo++ = *tempFrom++ ;  
  return memTo;
}

弊端

strcpy容易造成缓冲区溢出漏洞,这是系统漏洞中比较常见的一种。

strcpy()函数的原型为:char *strcpy(char *str1, const char *str2);
strcpy(str2, str1)函数调用中,strcpy()无法检查,str1指向的字符串的大小是否适合str2指向的数组。
如果str2指向的字符串长度为n,如果str1中有不超过n-1个字符,那么复制操作可以顺利完成。但是如果str1指向了一个更长的字符串,操作结果就得另当别论了。strcpy(str2, str1)会一直复制到str1的第一个字符'\0'为止,所以它会越过str2的数组边界继续复制。无论后面内存中的是什么,都将被覆盖。

想用更安全的复制字符串的函数,请用strncpy()函数。

如何查询1000万个数里最小的100个数?最小堆

采用小顶堆算法,我们知道完全二叉树有几个非常重要的特性,就是假如该二叉树中总共有N个节点,那么该二叉树的深度就是log2N,对于小顶堆来说移动根元素到 底部或者移动底部元素到根部只需要log2N,相比N来说时间复杂度优化太多了(1亿的logN值是26-27的一个浮点数)。基本的思路就是先从文件中取出1000个元素构建一个小顶堆数组k,然后依次对剩下的100亿-1000个数字进行遍历m,如果m大于小顶堆的根元素,即k[0],那么用m取代k[0],对新的数组进行重新构建组成一个新的小顶堆。这个算法的时间复杂度是O((100亿-1000)log(1000)),即O((N-M)logM),空间复杂度是M。这个算法优点是性能尚可,空间复杂度低,IO读取比较频繁,对系统压力大。

// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

void heap_swap(int u,int v)
{   
     swap(h[u],h[v]); 
     swap(hp[u],hp[v]);     
     swap(ph[hp[u]],ph[hp[v]]);            
}
void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u*2;//判断左子树是否小于h[t],是就交换小的
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//同理判断右子树,哪个小就换哪个
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);//递归往下走
    }

}
void up(int u)
{
    if(u/2>0&&h[u]<h[u/2]) 
    {
        heap_swap(u,u/2);
        up(u>>1);
    }
}

//步骤:
//定义h[],size,h是heap,size是存在h[]数组上有多少个元素
//down:判断左右子树是否小于h[t],是就交换小的,然后交换,递归down
//从小到大输出比m小的数:h[1]最小,删除最小值h[1] = h[size1];size--;然后down(1);
 
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N], size1;//p是heap,size是存在h[]数组上有多少个元素
void down(int u){
    int t = u;
    if (u *2 <= size1 && p[u * 2] <= p[t]) t = u * 2;//这里不是p[t * 2],而是p[u * 2],下面一样的,因为t是变的
    if (u *2 + 1 <= size1 && p[u * 2 + 1] <= p[t]) t = u * 2 + 1;
    if (t != u){
        swap(p[u], p[t]);
        down(t);//忘了,应该是t,因为t变了
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >>p[i];
    size1 = n;
    //建堆
    for (int i = n / 2; i ; i --) down(i);//这里是i = n / 2,因为是树的形式,所以得除2,而且是down(i)
    while (m --){
        cout << p[1] << ' ';//h[1]最小
        p[1] = p[size1];//删除最小值
        size1 --;
        down(1);
    }
}

函数指针了解吗?如何定义和初始化函数指针?函数指针通常用在什么地方?

参考:https://blog.csdn.net/ZongYinHu/article/details/48790555

概念:函数指针是指向函数的指针变量。 因此“函数指针”本身首先应是指针变量,只不过该指针变量指向函数。这正如用指针变量可指向整型变量、字符型、数组一样,这里是指向函数。如前所述,C在编译时,每一个函数都有一个入口地址,该入口地址就是函数指针所指向的地址。有了指向函数的指针变量后,可用该指针变量调用函数,就如同用指针变量可引用其他类型变量一样,在这些概念上是大体一致的。函数指针有两个用途:调用函数和做函数的参数

定义初始化函数指针:

#include<cstdlib>
using namespace std;
 
int func()
{
	cout << "my name is zyh_helen" << endl;
	return 0;
}
 
int main()
{
	int(*p)() = func;   //函数指针初始化方式1
	int(*p1)() = &func; //函数指针初始化方式2
 
	func();//函数调用方式1
	(*p)();//函数调用方式2
	p();   //函数调用方式3
 
	system("pause");
	return 0;
}

1:函数指针初始化方式有两种:

方式2中的&操作符是可选的,因为函数名被使用时总是由编译器把它转化为函数指针,&操作符只是显示的说明了编译器将隐式执行的任务

2:函数调用方式有三种:

函数调用方式1:使用函数名调用函数,执行过程可能和你想象的不一样,函数名首先被转化为一个函数指针,该指针指定函数在内存中的位置,然后,函数调用操作符()调用该函数,执行开始于这个地址的代码。
函数调用方式2:首先对p执行间接访问操作,它把函数指针转化为一个函数名,这个转换并不是真正需要的,因为编译器在执行函数调用操作符之前又会把它转换回去。
函数调用方式3:省去了编译器的隐式转化
因此,通过函数指针调用函数时,最好选择方式3

3:函数指针的用途:

1:回调函数:用户把一个函数指针作为参数传递给其他函数,后者将“回调”用户的函数
2:转移表  :本质:一个函数指针数组

STL

STL包括几个部分:容器,算法(泛型算法),迭代器三个主要部分(当然还包含仿函数,适配器等其他部分)

具体可以看我写的STL博客: https://blog.csdn.net/qq_27262727/category_9843205.html

vector 与 list 的区别

vector特点是:其容量在需要时可以自动分配,本质上是数组形式的存储方式。即在索引可以在常数时间内完成。缺点是在插入或者删除一项时,需要线性时间。但是在尾部插入或者删除,是常数时间的。

list 是双向链表:如果知道位置,在其中进行插入和删除操作时,是常数时间的。索引则需要线性时间(和单链表一样)。

vector 和 list 都支持在常量的时间内在容器的末尾添加或者删除项,vector和list都支持在常量的时间内访问表的前端的项.

vector会一次分配多个元素内存,那么下次增加时,只是改写内存而已,就不会再分配内存了,但是list每次只分配一个元素的内存,每次增加一个元素时,都会执行一次内存分配行为。如果是大量数据追加,建议使用list,因为vector 在有大量元素,并且内存已满,再pushback元素时,需要分配大块内存并把已经有的数据move到新分配的内存中去(vector不能加入不可复制元素)然后再释放原来的内存块,这些操作很耗时。而list的性能而会始终于一的,不会出现vector的性能变化情况,所以对于容器构件,需要用什么类型最好,取决于业务逻辑。

vector查找倒数第二位数字

*(kk.end() - 2)

map容器结构?map 怎么插入数据有几种方式?每种方式的优缺点;

概念:Map也是一种关联容器,它是 键—值对的集合,即它的存储都是以一对键和值进行存储的,Map通常也可以理解为关联数组(associative array),就是每一个值都有一个键与之一一对应,因此,map也是不允许重复元素出现的。

底层数据结构是红黑树。具体理解参考:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

插入数据几种方式

方法一:pair

例:

map<int, string> mp;

mp.insert(pair<int,string>(1,"aaaaa"));

方法二:make_pair

例:

map<int, string> mp;

mp.insert(make_pair<int,string>(2,"bbbbb"));

方法三:value_type

例:

map<int, string> mp;

mp.insert(map<int, string>::value_type(3,"ccccc"));

方法四:[]

例:

map<int, string> mp;

mp[4] = "ddddd";

四种方法异同:前三种方法当出现重复键时,编译器会报错,而第四种方法,当键重复时,会覆盖掉之前的键值对。

什么是 STL? 列举下 STL 中你常使用的容器,并简单描述。STL 中的迭代器是什么意思?

STL是C++标准库,常使用vector、map、string等

迭代器(iterator)是一种抽象的设计理念,通过迭代器可以在不了解容器内部原理的情况下遍历容器。除此之外,STL中迭代器一个最重要的作用就是作为容器(vector,list等)与STL算法的粘结剂,只要容器提供迭代器的接口,同一套算法代码可以利用在完全不同的容器中,这是抽象思想的经典应用。

STL中有以下几类iterator(迭代器): 

输入iterator(迭代器),在容器的连续区内向前移动,可以读取容器内任意值; 

输出iterator(迭代器),把值写进它所指向的容器中; 

前向iterator(迭代器),读取队列中的值,并可以向前移动到下一个位置(++p, p++); 

双向iterator(迭代器),读取队列中的值,并可以向前后遍历容器;随机访问向iterator(迭代器),可以直接以下标方式对容器进行访问,vector的iterator(迭代器)就是这种iterator(迭代器); 

流iterator(迭代器),可以直接输入、输出流中的值;

C++的内存管理方式,STL的allocaotr,最新版本默认使用的分配器

内存池,STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中,其内存配置和释放如下:

new运算分两个阶段:(1)调用::operator new配置内存;(2)调用对象构造函数构造对象内容

vector增长策略?delete运算分两个阶段:(1)调用对象希构函数;(2)掉员工::operator delete释放内存

为了精密分工,STL allocator将两个阶段操作区分开来:内存配置有alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造由::construct()负责,对象析构由::destroy()负责。

同时为了提升内存管理的效率,减少申请小内存造成的内存碎片问题,SGI STL采用了两级配置器,当分配的空间大小超过128B时,会使用第一级空间配置器;当分配的空间大小小于128B时,将使用第二级空间配置器。第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放,而第二级空间配置器采用了内存池技术,通过空闲链表来管理内存。

vector增长策略?

为了支持快速的访问,vector/string将元素连续存储--每个元素都是紧挨着前一个元素存储。如果我们向vector/string中添加新的元素,会发生什么:由于连续存放的缘故,当没有多余的空间来容纳新的元素的时候,容器必须分配新的空间来保存已有的元素和新元素,将已有元素从旧位置移动到新空间中,然后添加新的元素,释放旧的空间。vector不会对新添加的每一个元素都做上述操作,效率太慢。所以vector会预留一些空间。就是因为这些预留的空间,容器的元素个数和实际容量不一定是相等的。
首先介绍两个概念:
capacity,可以告诉我们容器在不扩张内存的情况下可以容纳多少各元素
reserve,可以让我们通知容器它应该准备保存多少个元素的空间
容器大小管理操作:
shrink_to_fit只能用于vector,string,deque
capacity,reserve只能用于vector,string
c.shrink_to_fit(),将capacity()减少为size()相同的大小
c.capacity() 不重新分配内存空间的话,c可以保存多少元素个数
c.reserve(n) 分配至少能容纳n个元素的内存空间,n如果《=capacity(),那么reserve什么也不做;n大于当前容量时,才会分配空间。
c.size() 容器中元素的个数,与capacity是不一样的;
分配策略:大部分vector采用的分配策略:就是在每次需要分配内存空间时,将当前的容量capacity翻倍;
这也是不确定的,应该具体问题具体分析。
分配原则:通过在一个初始为空的vector上调用push_back来创建一个n个元素的vector,所花费的时间不能超过n的常熟倍

vector是如何实现的?

vector是动态空间,随着元素的加入,它的内部机制会自行扩充空间以容纳新元素。因此,vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们再也不必因为害怕空间不足而一开始要求一个大块头的array了,我们可以安心使用array,吃多少用多少。
      vector的实现技术,关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧有空间满载,如果客户端每新增一个元素,vector的内部只是扩充一个元素的空间,实为不智。因为所谓扩充空间(不论多大),一如稍早所说,是”  配置新空间/数据移动/释还旧空间  “的大工程,时间成本很高,应该加入某种未雨绸缪的考虑。稍后我们便可看到SGI vector的空间配置策略了。
      另外,由于  vector维护的是一个连续线性空间,所以vector支持随机存取  。
      注意:vector动态增加大小时,并不是在原空间之后持续新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此,  对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了  。这是程序员易犯的一个错误,务需小心。

template<class _Ty,
    class _Ax>
    class vector
        : public _Vector_val<_Ty, _Ax>
    {   // varying size array of values
public:
    /********/
protected:
    pointer _Myfirst;   // pointer to beginning of array
    pointer _Mylast;    // pointer to current end of sequence
    pointer _Myend; // pointer to end of array
    };

简单理解,就是vector是利用上述三个指针来表示的,基本示意图如下

两个关键大小:
大小:size=_Mylast - _Myfirst;
容量:capacity=_Myend - _Myfirst;
分别对应于resize()、reserve()两个函数。
size表示vector中已有元素的个数,容量表示vector最多可存储的元素的个数;为了降低二次分配时的成本,vector实际配置的大小可能比客户需求的更大一些,以备将来扩充,这就是容量的概念。即capacity>=size,当等于时,容器此时已满,若再要加入新的元素时,就要重新进行内存分配,整个vector的数据都要移动到新内存。二次分配成本较高,在实际操作时,应尽量预留一定空间,避免二次分配。

vector在插入新元素时如何申请内存的?

插入操作:push_back()就是往vector之后插入元素,这也是vector跟array最大的区别,array只能是固定大小,而有了vector之后,就可以动态扩大其容量了。

1.    Vec.push_back(a);
            申请1个内存空间, 存放a.                 copy 1 次
2.  Vec.push_back(b);
            a> 发现内存空间不够,于是扩大为原来的2倍.
            b> 然后将a,b copy到新的内存空间        这里copy 2 次
            c> 然后释放原来空间上的a                destruction 1 次

map底层实现?

概念:map是经过排序了的二元组的集合,map中的每个元素都是由两个值组成,其中的key(键值,一个map中的键值必须是唯一的)是在排序或搜索时使用,它的值可以在容器中重新获取;而另一个值是该元素关联的数值。比如,除了可以ar[43] = "overripe"这样找到一个数据,map还可以通过ar["banana"] = "overripe"这样的方法找到一个数据。如果你想获得其中的元素信息,通过输入元素的全名就可以轻松实现。Map也是一种关联容器,它是 键—值对的集合,即它的存储都是以一对键和值进行存储的,Map通常也可以理解为关联数组(associative array),就是每一个值都有一个键与之一一对应,因此,map也是不允许重复元素出现的。

底层是红黑树。

讲一下AVL树?满二叉树与AVL的区别?

参考:https://blog.csdn.net/yuwushuang11/article/details/78628071

度:指的是一个节点拥有子节点的个数。如二叉树的节点的最大度为2。

深度:数的层数,根节点为第一层,依次类推。

叶子节点:度为0的节点,即没有子节点的节点。

树:树中的每一个节点,可以有n(后续节点)个子节点,但是每个节点只有一个前驱节点。

二叉树:除了叶子节点外,每个节点只有两个分支,左子树和右子树,每个节点的最大度数为2.

满二叉树:除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,

完全二叉树:只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。也就是说,在满叉树的基础上,我在最底层从右往左删去若干节点,得到的都是完全二叉树。所以说,满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树。

平衡二叉树:树的左右子树的高度差不超过1的数,空树也是平衡二叉树的一种。平衡二叉树,又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1.。

平衡二叉树的调整方法

平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

哈夫曼树:带权路径长度达到最小的二叉树,也叫做最优二叉树。

不关心树的结构,只要求带权值的路径达到最小值,哈夫曼树可能是完全二叉树也可能是满二叉树。

二叉树的性质:

(1) 在二叉树中,第i层的结点总数不超过2^(i-1);

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点;

(3) 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,

则N0=N2+1;

(4) 具有n个结点的完全二叉树的深度为int(log2n)+1

(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:

若I为结点编号则 如果I<>1,则其父结点的编号为I/2;

如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;

如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

(6)给定N个节点,能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

讲一下对红黑树的理解,讲一下红黑树的查找复杂度?为什么查找速度快?

参考:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

https://github.com/Moosphan/Android-Daily-Interview/issues/147

由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。

二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 任意结点的左、右子树也分别为二叉查找树。
  • 没有键值相等的结点(no duplicate nodes)。

因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,一般操作的执行时间为O(lgn).(至于n个结点的二叉树高度为lgn的证明,可参考算法导论 第12章 二叉查找树 第12.4节)。

但二叉树若退化成了一棵具有n个结点的线性链后,则此些操作最坏情况运行时间为O(n)。后面我们会看到一种基于二叉查找树-红黑树,它通过一些性质使得树相对平衡,使得最终查找、插入、删除的时间复杂度最坏情况下依然为O(lgn)。

1)每个结点要么是红的,要么是黑的。  
2)根结点是黑的。  
3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。  
4)如果一个结点是红的,那么它的俩个儿子都是黑的。  
5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

插入、删除、查找的最坏时间复杂度都为O(logn) 。

为什么查找速度快?

参考:https://www.zhihu.com/question/19856999

红黑树是怎么实现自平衡的?

参考:https://blog.csdn.net/Jop_qq/article/details/104527085/

红黑树(Red-Black Tree),又称“R-B树”,属于“二叉查找树”的一种,但它比较特殊,能够实现树结点的“自平衡”特性,但这种平衡只是近似的,不是绝对平衡。而这一特性使得红黑树能够保证在最坏情况下,基本动态集合的操作时间复杂度为O(lgn)。树中每个结点包含5个属性:key、color、left、right 和 p。

根据《算法导论》中,红黑树的描述定义为:

每个结点或是红色的,或是黑色的;
根结点是黑色的;
每个叶结点(NIL / NULL)是黑色的;
如果一个结点是红色的,则它的两个子结点都是黑色的;
对每个结点,从该结点到其后代叶结点的简单路径上,均包含相同数目的黑色结点。(概念:根据性质5,所得到的黑色结点数,又称为“黑高(black-height)",记作 bh(x),注意不包含当前结点,“NIL / NULL”的黑高为0)。

hash_map的实现?如何处理冲突?

参考:https://blog.csdn.net/qq_30546099/article/details/89531651

数组和链表的结合体,hashmap是由数组和链表组成的。数组是HashMap的本体,而链表则是为了解决hash冲突而存在的,如果定位到数组位置不存在链表(当前Entry的next指向为null),那么对于查找插入等操作很快,仅仅需要一次寻址即可;如果定位到数组有链表,对于添加操作其时间复杂度为O(n),首先遍历链表,存在既覆盖,否则新增。对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。
冲突处理方法:

原理是如果两个不相等的对象返回不同的 hashcode 的话,那么碰撞的几率就会小些。这就意味着存链表结构减小,这样取值的话就不会频繁调用 equal 方法,从而提高 HashMap 的性能(扰动即 Hash 方法内部的算法实现,目的是让不同对象返回不同hashcode)。
使用不可变的、声明作 final 对象,并且采用合适的 equals() 和 hashCode() 方法,将会减少碰撞的发生不可变性使得能够缓存不同键的 hashcode,这将提高整个获取对象的速度,使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。

1.开放定址法

开放定址法处理冲突的基本思想是当冲突发生时,形成一个地址序列,沿着这个序列逐个探测,直到找到一个“空”的开放地址,将发生冲突的关键字值存入到该地址中。

 Hi = (H(key)+di)%m    (i=1,2,...k(k<=m-1)

H(key)是关键字key的哈希函数,m为哈希表长,di为每次再探测时的地址增量。地址增量的取法主要有线性探测法、二次探测法和双哈希函数探测法。

2.链地址法

3.公共溢出区法

4.再哈希法

为什么 String、Integer 这样的 wrapper 类适合作为键?

因为 String 是 final,而且已经重写了 equals() 和 hashCode() 方法了。不可变性是必要的,因为为了要计算 hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的 hashcode 的话,那么就不能从 HashMap 中找到你想要的对象。

操作系统

多线程的理解(多线程同步的途径)

参考:https://blog.csdn.net/sinat_22336563/article/details/71588703

概念:进程是系统进行资源分配和调用的独立单位,每一个进程,都由它自己的内存空间和系统资源线程是进程的执行单元,执行路径,线程也是程序使用CPU的最基本单位。

理解:将CPU比作是是一个工厂,那么进程可以看做是一个可以独立进行工作的车间,车间内有生产必须的资源以及工人(线程),同时工厂内同一时刻只有一个车间在开工,但是工厂内是可以有多个车间的。线程,程序执行的最小单元;线程则是车间内的工人,工人的数量可以有多个,某些工具或者空间只有一个,需要多人分享(共享资源),如果有一个人正在使用,那么其他工人则必须等待此人使用完毕。进程拥有独立的执行环境,每个进程都有自己的内存空间。进程间的通信可以使用管道或者socket等。在一个进程中,线程共享该进程的资源,比如内存或者打开的文件。由于进程之间是隔离的,而线程之间共享资源,所以线程之间存在竞争。

线程状态:就绪(等待处理)、运行(占用CPU资源)、阻塞(等待一个事件或者信号量,此时线程无法执行)

并发与并行:并发是同一时间应对多件事情的能力;而并行则是同一时间做多件事情的能力。并行就是在相同的时间,多个工作执行单位同时执行;在单核CPU上,多线程本质上是单个 CPU 的时间分片,一个时间片运行一个线程的代码,它可以支持并发处理,但是不能说是真正的并行计算。而在多核的CPU上,则实现了真正意义上的并行。

多线程安全

线程间相互干扰:使用互斥锁来解决,当一个线程对某个数据进行排他性访问的时候,会得到了其内部锁之后才能访问,而在该线程没有释放此锁的情况下,其他的线程是无法访问的。另外一种方式则是阻塞block,当一个线程在运行时,另一个线程处于休眠的状态。总而言之,就是将并行转换为串行来避开竞争的问题。

线程活跃度:当一个线程锁定了另一个线程需要的资源的时候,而第二个线程又锁定了第一个线程需要的资源,这个时候就会发生死锁,双方都在等待对方先释放所需资源。其次,当一个线程长时间地占用某个资源,而其他的线程只能被迫长时间地等待。然后,线程1可以使用资源,但是他让线程2先使用,同样地,线程2也在谦让,致使双方还是无法进行。另外,如果对同样一个资源,多次调用非递归锁,会造成多重锁死;

C++11新特性

C++11将Boost库中的thread类引进——std::thread,同时提供了std::atomic, st d::mutex,std::conditonal_variable,std::future,配上智能指针,使得c++11中的多线程并发变得安全容易。C++11 所定义的线程是和操作系的线程是一一对应的,也就是说我们生成的线程最终还是直接接受操作系统的调度的。

多进程(继承什么, 不继承什么)

子进程继承父进程:

用户号UIDs和用户组号GIDs、环境Environment、堆栈、共享内存、打开文件的描述符

执行时关闭(Close-on-exec)标志、信号(Signal)控制设定、进程组号、当前工作目录、根目录、文件方式创建屏蔽字、资源限制、控制终端

子进程独有:进程号PID不同的父进程号、自己的文件描述符和目录流的拷贝子进程不继承父进程的进程正文(text),数据和其他锁定内存(memory locks)不继承异步输入和输出。

父进程和子进程拥有独立的地址空间和PID参数。

进程间通信

1. 管道pipe:管道是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
2. 命名管道FIFO:有名管道也是半双工的通信方式,但是它允许无亲缘关系进程间的通信。
4. 消息队列MessageQueue:消息队列是由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
5. 共享存储SharedMemory:共享内存就是映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问。共享内存是最快的 IPC 方式,它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制,如信号两,配合使用,来实现进程间的同步和通信。
6. 信号量Semaphore:信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其他进程也访问该资源。因此,主要作为进程间以及同一进程内不同线程之间的同步手段。
7. 套接字Socket:套解口也是一种进程间通信机制,与其他通信机制不同的是,它可用于不同及其间的进程通信。
8. 信号 ( sinal ) : 信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生。

五种 IO 模型

参考:https://juejin.im/post/5c725dbe51882575e37ef9ed

阻塞I/O(blocking IO) :进程会一直阻塞,直到数据拷贝完成 应用程序调用一个IO函数,导致应用程序阻塞,等待数据准备好。数据准备好后,从内核拷贝到用户空间,IO函数返回成功指示。

非阻塞I/O (nonblocking I/O) :通过进程反复调用IO函数,在数据拷贝过程中,进程是阻塞的。

I/O 复用 (I/O multiplexing) :主要是select和epoll。一个线程可以对多个IO端口进行监听,当socket有读写事件时分发到具体的线程进行处理。

信号驱动I/O (signal driven I/O (SIGIO)) :首先我们允许Socket进行信号驱动IO,并安装一个信号处理函数,进程继续运行并不阻塞。当数据准备好时,进程会收到一个SIGIO信号,可以在信号处理函数中调用I/O操作函数处理数据。

异步I/O (asynchronous I/O):异步IO不是顺序执行。用户进程进行aio_read系统调用之后,无论内核数据是否准备好,都会直接返回给用户进程,然后用户态进程可以去做别的事情。等到socket数据准备好了,内核直接复制数据给进程,然后从内核向进程发送通知。IO两个阶段,进程都是非阻塞的。

阻塞IO和非阻塞IO的区别 调用阻塞IO后进程会一直等待对应的进程完成,而非阻塞IO不会等待对应的进程完成,在kernel还在准备数据的情况下直接返回。 

IO复用之select、poll、epoll区别

epoll是linux所特有,而select是POSIX所规定,一般操作系统均有实现。

select

select本质是通过设置或检查存放fd标志位的数据结构来进行下一步处理。缺点是:

  1. 单个进程可监视的fd数量被限制,即能监听端口的大小有限。一般来说和系统内存有关,具体数目可以cat /proc/sys/fs/file-max察看。32位默认是1024个,64位默认为2048个
  2. 对socket进行扫描时是线性扫描,即采用轮询方法,效率低。当套接字比较多的时候,每次select()都要遍历FD_SETSIZE个socket来完成调度,不管socket是否活跃都遍历一遍。会浪费很多CPU时间。如果能给套接字注册某个回调函数,当他们活跃时,自动完成相关操作,就避免了轮询,这正是epoll与kqueue做的
  3. 需要维护一个用来存放大量fd的数据结构,会使得用户空间和内核空间在传递该结构时复制开销大

poll

poll本质和select相同,将用户传入的数据拷贝到内核空间,然后查询每个fd对应的设备状态,如果设备就绪则在设备等待队列中加入一项并继续遍历,如果遍历所有fd后没有发现就绪设备,则挂起当前进程,直到设备就绪或主动超时,被唤醒后又要再次遍历fd。它没有最大连接数的限制,原因是它是基于链表来存储的,但缺点是:

  1. 大量的fd的数组被整体复制到用户态和内核空间之间,不管有无意义。
  2. poll还有一个特点“水平触发”,如果报告了fd后,没有被处理,那么下次poll时再次报告该ffd。

epoll

epoll支持水平触发和边缘触发,最大特点在于边缘触发,只告诉哪些fd刚刚变为就绪态,并且只通知一次。还有一特点是,epoll使用“事件”的就绪通知方式,通过epoll_ctl注册fd,一量该fd就绪,内核就会采用类似callback的回调机制来激活该fd,epoll_wait便可以收到通知。epoll的优点:

  1. 没有最大并发连接的限制。
  2. 效率提升,只有活跃可用的FD才会调用callback函数。
  3. 内存拷贝,利用mmap()文件映射内存加速与内核空间的消息传递。

C++线程中的锁有那些类型呢

一般的锁的功能越强大,性能就会越低,主要有以下几个:

互斥锁:控制多个线程对他们之间共享资源互斥访问的一个信号量。也就是说是为了避免多个线程在某一时刻同时操作一个共享资源。例如线程池中的有多个空闲线程和一个任务队列。任何是一个线程都要使用互斥锁互斥访问任务队列,以避免多个线程同时访问任务队列以发生错乱。

条件锁:条件锁就是所谓的条件变量,某一个线程因为某个条件为满足时可以使用条件变量使改程序处于阻塞状态。一旦条件满足以“信号量”的方式唤醒一个因为该条件而被阻塞的线程。最为常见就是在线程池中,起初没有任务时任务队列为空,此时线程池中的线程因为“任务队列为空”这个条件处于阻塞状态。一旦有任务进来,就会以信号量的方式唤醒一个线程来处理这个任务。这个过程中就使用到了条件变量

自旋锁:假设我们有一个两个处理器core1和core2计算机,现在在这台计算机上运行的程序中有两个线程:T1和T2分别在处理器core1和core2上运行,两个线程之间共享着一个资源。首先我们说明互斥锁的工作原理,互斥锁是是一种sleep-waiting的锁。假设线程T1获取互斥锁并且正在core1上运行时,此时线程T2也想要获取互斥锁(pthread_mutex_lock),但是由于T1正在使用互斥锁使得T2被阻塞。当T2处于阻塞状态时,T2被放入到等待队列中去,处理器core2会去处理其他任务而不必一直等待(忙等)。也就是说处理器不会因为线程阻塞而空闲着,它去处理其他事务去了。而自旋锁就不同了,自旋锁是一种busy-waiting的锁。也就是说,如果T1正在使用自旋锁,而T2也去申请这个自旋锁,此时T2肯定得不到这个自旋锁。与互斥锁相反的是,此时运行T2的处理器core2会一直不断地循环检查锁是否可用(自旋锁请求),直到获取到这个自旋锁为止。从“自旋锁”的名字也可以看出来,如果一个线程想要获取一个被使用的自旋锁,那么它会一致占用CPU请求这个自旋锁使得CPU不能去做其他的事情,直到获取这个锁为止,这就是“自旋”的含义。当发生阻塞时,互斥锁可以让CPU去处理其他的任务;而自旋锁让CPU一直不断循环请求获取这个锁。通过两个含义的对比可以我们知道“自旋锁”是比较耗费CPU的。

读写锁:计算机中某些数据被多个进程共享,对数据库的操作有两种:一种是读操作,就是从数据库中读取数据不会修改数据库中内容;另一种就是写操作,写操作会修改数据库中存放的数据。因此可以得到我们允许在数据库上同时执行多个“读”操作,但是某一时刻只能在数据库上有一个“写”操作来更新数据。这就是一个简单的读者-写者模型。

递归锁

多线程多进程

参考:https://blog.csdn.net/linraise/article/details/12979473

https://img-blog.csdnimg.cn/2018122721302863

线程间同步的方式,进程间同步的方式和进程间通信的方式

一、进程/线程间同步机制。

临界区(Critical Section)、互斥量(Mutex)、信号量(Semaphore)、事件(Event)四种方式。
1、临界区:通过对多线程的串行化来访问公共资源或一段代码,速度快,适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问,如果有多个线程试图访问公共资源,那么在有一个线程进入后,其他试图访问公共资源的线程将被挂起,并一直等到进入临界区的线程离开,临界区在被释放后,其他线程才可以抢占。
2、互斥量:采用互斥对象机制。 只有拥有互斥对象的线程才有访问公共资源的权限,因为互斥对象只有一个,所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享,还能实现不同应用程序的公共资源安全共享 .互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享,而且可以在不同应用程序的线程之间实现对资源的安全共享。
3、信号量:它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目 .信号量对象对线程的同步方式与前面几种方法不同,信号允许多个线程同时使用共享资源,这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。

PV操作及信号量的概念
P操作申请资源:(1)S减1;(2)若S减1后仍大于等于零,则进程继续执行;(3)若S减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转入进程调度。
V操作释放资源:(1)S加1;(2)若相加结果大于零,则进程继续执行;(3)若相加结果小于等于零,则从该信号的等待队列中唤醒一个等待进程,然后再返回原进程继续执行或转入进程调度。
4、事 件: 通过通知操作的方式来保持线程的同步,还可以方便实现对多个线程的优先级比较的操作 .

总结:
1. 互斥量与临界区的作用非常相似,但互斥量是可以命名的,也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多,所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建,就可以通过名字打开它。
2. 互斥量(Mutex),信号灯(Semaphore),事件(Event)都可以被跨越进程使用来进行同步数据操作,而其他的对象与数据同步操作无关,但对于进程和线程来讲,如果进程和线程在运行状态则为无信号状态,在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和线程退出。
3. 通过互斥量可以指定资源被独占的方式使用,但如果有下面一种情况通过互斥量就无法处理,比如现在一位用户购买了一份三个并发访问许可的数据库系统,可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作,这时候如果利用互斥量就没有办法完成这个要求,信号灯对象可以说是一种资源计数器。

二、进程间通信方式

进程间通信主要包括管道, 系统IPC(包括消息队列,信号量,共享存储), SOCKET.

管道分为有名管道和无名管道,无名管道只能用于亲属进程之间的通信,而有名管道则可用于无亲属关系的进程之间。消息队列用于运行于同一台机器上的进程间通信,与管道相似;共享内存通常由一个进程创建,其余进程对这块内存区进行读写。得到共享内存有两种方式:映射/dev/mem设备和内存映像文件。前一种方式不给系统带来额外的开销,但在现实中并不常用,因为它控制存取的是实际的物理内存;本质上,信号量是一个计数器,它用来记录对某个资源(如共享内存)的存取状况。一般说来,为了获得共享资源,进程需要执行下列操作:

(1)测试控制该资源的信号量;

(2)若此信号量的值为正,则允许进行使用该资源,进程将进号量减1;

(3)若此信号量为0,则该资源目前不可用,进程进入睡眠状态,直至信号量值大于0,进程被唤醒,转入步骤(1);

(4)当进程不再使用一个信号量控制的资源时,信号量值加1,如果此时有进程正在睡眠等待此信号量,则唤醒此进程。套接字通信并不为Linux所专有,在所有提供了TCP/IP协议栈的操作系统中几乎都提供了socket,而所有这样操作系统,对套接字的编程方法几乎是完全一样的

三、进程/线程同步机制与进程间通信机制比较

很明显2者有类似,但是差别很大

同步主要是临界区、互斥、信号量、事件

进程间通信是管道、内存共享、消息队列、信号量、socket

共通之处是,信号量和消息(事件)

怎么创建管道 pipe()

我们将用pipe()函数建立管道。每当我们打开数据流时,它都会加入描述符表。pipe()函数也是如此,它创建两条相连的数据流,并把它们加到描述符表中,然后只要我们往其中一条数据流中写数据,就可以从另一条数据流中读取。pipe()在描述符表中创建这两项时,会把它们的文件描述符存放在一个包含两个元素的数组中。

int fd[2];  //文件描述符将保存在fd数组中。

if(pipe(fd) == -1){

        fprintf(stderr,"Can't create the pipe!");

        exit(2);

}

pipe()函数创建了管道,并返回了两个描述符:fd[0]用来从管道读数据,fd[1]用来向管道写数据。我们将在父、子进程中使用这两个描述符。

操作系统内存管理

内存管理包括内存管理和虚拟内存管理
内存管理包括内存管理概念、交换与覆盖、连续分配管理方式和非连续分配管理方式(分页管理方式、分段管理方式、段页式管理方式)。
虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。

内存管理的功能有:

  • 内存空间的分配与回收:由操作系统完成主存储器空间的分配和管理,使程序员摆脱存储分配的麻烦,提高编程效率。
  • 地址转换:在多道程序环境下,程序中的逻辑地址与内存中的物理地址不可能一致,因此存储管理必须提供地址变换功能,把逻辑地址转换成相应的物理地址。
  • 内存空间的扩充:利用虚拟存储技术或自动覆盖技术,从逻辑上扩充内存。
  • 存储保护:保证各道作业在各自的存储空间内运行,.互不干扰。

进程和线程的区别,切换方式,具体切换过程,涉及到哪些操作,多线程共享哪些资源,哪些是独立的?

进程线程区别

a.地址空间和其它资源:进程间相互独立,同一进程的各线程间共享。某进程内的线程在其它进程不可见。

b.通信:进程间通信IPC,线程间可以直接读写进程数据段(如全局变量)来进行通信——需要进程同步和互斥手段的辅助,以保证数据的一致性。

c.调度和切换:线程上下文切换比进程上下文切换要快得多。

d.在多线程OS中,进程不是一个可执行的实体。

优缺点:线程和进程在使用上各有优缺点:线程执行开销小,但不利于资源的管理和保护;而进程正相反。同时,线程适合于在SMP机器上运行,而进程则可以跨机器迁移。

线程共享独享资源如下:

服务器多个线程切换如何减少创建的开销,线程池如何实现?

概念:多线程技术主要解决处理器单元内多个线程执行的问题,它可以显著减少处理器单元的闲置时间,增加处理器单元的吞吐能力。

    假设一个服务器完成一项任务所需时间为:T1 创建线程时间,T2 在线程中执行任务的时间,T3 销毁线程时间。

    如果:T1 + T3 远大于 T2,则可以采用线程池,以提高服务器性能。

一个线程池包括以下四个基本组成部分:

1、线程池管理器(ThreadPool):用于创建并管理线程池,包括 创建线程池,销毁线程池,添加新任务;

2、工作线程(PoolWorker):线程池中线程,在没有任务时处于等待状态,可以循环的执行任务;

3、任务接口(Task):每个任务必须实现的接口,以供工作线程调度任务的执行,它主要规定了任务的入口,任务执行完后的收尾工作,任务的执行状态等;

4、任务队列(taskQueue):用于存放没有处理的任务。提供一种缓冲机制。

  线程池技术正是关注如何缩短或调整T1,T3时间的技术,从而提高服务器程序性能的。它把T1,T3分别安排在服务器程序的启动和结束的时间段或者一些空闲的时间段,这样在服务器程序处理客户请求时,不会有T1,T3的开销了。

  线程池不仅调整T1,T3产生的时间段,而且它还显著减少了创建线程的数目,看一个例子:假设一个服务器一天要处理50000个请求,并且每个请求需要一个单独的线程完成。在线程池中,线程数一般是固定的,所以产生线程总数不会超过线程池中线程的数目,而如果服务器不利用线程池来处理这些请求则线程总数为50000。一般线程池大小是远小于50000。所以利用线程池的服务器程序不会为了创建50000而在处理请求时浪费时间,从而提高效率。

为什么要用线程池?诸如 Web 服务器、数据库服务器、文件服务器或邮件服务器之类的许多服务器应用程序都面向处理来自某些远程来源的大量短小的任务。请求以某种方式到达服务器,这种方式可能是通过网络协议(例如 HTTP、FTP 或 POP)、通过 JMS 队列或者可能通过轮询数据库。不管请求如何到达,服务器应用程序中经常出现的情况是:单个任务处理的时间很短而请求的数目却是巨大的。

构建服务器应用程序的一个过于简单的模型应该是:每当一个请求到达就创建一个新线程,然后在新线程中为请求服务。实际上,对于原型开发这种方法工作得很好,但如果试图部署以这种方式运行的服务器应用程序,那么这种方法的严重不足就很明显。每个请求对应一个线程(thread-per-request)方法的不足之一是:为每个请求创建一个新线程的开销很大;为每个请求创建新线程的服务器在创建和销毁线程上花费的时间和消耗的系统资源要比花在处理实际的用户请求的时间和资源更多。

除了创建和销毁线程的开销之外,活动的线程也消耗系统资源。在一个 JVM 里创建太多的线程可能会导致系统由于过度消耗内存而用完内存或“切换过度”。为了防止资源不足,服务器应用程序需要一些办法来限制任何给定时刻处理的请求数目。

线程池为线程生命周期开销问题和资源不足问题提供了解决方案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。其好处是,因为在请求到达时线程已经存在,所以无意中也消除了线程创建所带来的延迟。这样,就可以立即为请求服务,使应用程序响应更快。而且,通过适当地调整线程池中的线程数目,也就是当请求的数目超过某个阈值时,就强制其它任何新到的请求一直等待,直到获得一个线程来处理为止,从而可以防止资源不足。

怎么创建共享内存 shmget();

可以说,共享内存是一种最为高效的进程间通信方式,因为进程可以直接读写内存,不需要任何数据的复制。为了在多个进程间交换信息,内核专门留出了一块内存区,这段内存区可以由需要访问的进程将其映射到自己的私有地址空间。因此,进程就可以直接读写这一段内存区而不需要进行数据的复制,从而大大提高了效率。当然,由于多个进程共享一段内存,因此也需要依靠某种同步机制,如互斥锁和信号量等。共享内存的原理图如下图1所示。共享内存使用步骤

1、创建共享内存。也就是从内存中获得一段共享内存区域,这里用到的函数是shmget();

2、映射共享内存。也就是把这段创建的共享内存映射到具体的进程空间中,这里使用的函数是shmat()。到这一步就可以使用这段共享内存了,也就是可以使用不带缓冲的I/O读写命令对其进行操作。

3、撤销映射。使用完共享内存就需要撤销,用到的函数是shmdt()。

https://img-blog.csdn.net/20130626172641875?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbXliZWxpZWYzMjE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

https://img-blog.csdn.net/20130626172806187?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbXliZWxpZWYzMjE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

https://img-blog.csdn.net/20130626172820843?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbXliZWxpZWYzMjE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

简述一个 windows 窗口程序的创建过程。

1.创建一个窗口首先要注册一个窗口类,初始化wndclass中的各个域,设置窗口过程函数。

2.调用RigisterClass来注册这个窗口类。

3.创建窗口。CreateWindow

4.显示窗口。ShowWindow

5.刷新窗口。UpdateWindow

5.消息循环。

一般情况下,点击一下所在的windows窗口,系统就会把该事件放入该程序所拥有的消息队列中。然后通过上面的循环代码取出msg消息并且投给系统。系统调用该程序所属窗口类的窗口函数,并且把消息传给该函数,最后在该函数中判断是哪种信息,并根据信息执行相应的反馈。

Windows 窗口程序在获取消息时,调用 GetMessage()与 PeekMessage()有什么区别?

GetMessage从消息队列里取得消息,填写好MSG结构并返回,如果取得的消息是WM_QUIT,则返回值是0,否则返回非零值。Windows是一个抢占式的多任务操作系统,使用GetMessage时,轮到应用程序的时间片的时候,如果消息队列里没有消息,则程序主动将控制权返还给Windows。使用PeekMessage时,如果消息队列里没有消息,PeekMessage返回0,否则返回非零值。

PeekMessage的前4个参数和GetMessage相同,最后一个参数是PM_REMOVE时,消息被取回的同时也被从消息队列中删除,而PM_NOREMOVE则不会删除。

什么是句柄(HANDLE)? 什么是回调函数(CALLBACK)?

Windows系统中有许多内核对象(这里的对象不完全等价于"面向对象程序设计"一词中的"对象",虽然实质上还真差不多),比如打开的文件,创建的线程,程序的窗口,等等。这些重要的对象肯定不是4个字节或者8个字节足以完全描述的,他们拥有大量的属性。为了保存这样一个"对象"的状态,往往需要上百甚至上千字节的内存空间,那么怎么在程序间或程序内部的子过程(函数)之间传递这些数据呢?拖着这成百上千的字节拷贝来拷贝去吗?显然会浪费效率。那么怎么办?当然传递这些对象的首地址是一个办法,但这至少有两个缺点:

  1. 暴露了内核对象本身,使得程序(而不是操作系统内核)也可以任意地修改对象地内部状态(首地址都知道了,还有什么不能改的?),这显然是操作系统内核所不允许的;
  2. 操作系统有定期整理内存的责任,如果一些内存整理过一次后,对象被搬走了怎么办?

所以,Windows操作系统就采用进一步的间接:在进程的地址空间中设一张表,表里头专门保存一些编号和由这个编号对应一个地址,而由那个地址去引用实际的对象,这个编号跟那个地址在数值上没有任何规律性的联系,纯粹是个映射而已。

在Windows系统中,这个编号就叫做"句柄"。

回调函数:当一个程序调用windows API时的过程称为Call,当windows API调用程序里面的函数时这称之为Callback。callback 是一种特殊的函数,这个函数被作为参数传给另一个函数去调用。这样的函数就是回调函数。callback 拆开,就是 call back,在英语里面就是「回拨电话」的意思。

那我们就用打电话为例子来说明一下 callback:

  1. 「我打电话给某某」(I call somebody),那么「打电话」的人就是「我」。
  2. 「我」在电话里说:你办完某事后,回拨电话给「我」。
  3. 某某做完事后,就会「回拨电话给我」(calls back to me),那么「打电话」的人就是「某某」。

用编程来解释的话,是这样的:

  1. 「我调用一个函数 f」(I call a function),那么「调用函数」的人是「我」。代码是 f(c)。
  2. 「我」让这个函数 f 在执行完后,调用我传给它的另一个函数 c。
  3. f 执行完的时候,就会「调用 c」,也叫做「回调 c」(call c back),调用 c 的人是 f。

好了,解释完了:callback 就是(传给另一个函数调用的)函数。

把括号里面的内容去掉,简化成:callback 就是一种函数。

简述 windows 中的消息处理过程。

参考:https://blog.csdn.net/wlanye/article/details/44917305

1)消息的组成:一个消息由一个消息名称(UINT),和两个参数(WPARAM,LPARAM)。当用户进行了输入或是窗口的状态发生改变时系统都会发送消息到某一个窗口。例如当菜单转中之后会有WM_COMMAND消息发送,WPARAM的高字中(HIWORD(wParam))是命令的ID号,对菜单来讲就是菜单ID。当然用户也可以定义自己的消息名称,也可以利用自定义消息来发送通知和传送数据。
2)谁将收到消息:一个消息必须由一个窗口接收。在窗口的过程(WNDPROC)中可以对消息进行分析,对自己感兴趣的消息进行处理。例如你希望对菜单选择进行处理那么你可以定义对WM_COMMAND进行处理的代码,如果希望在窗口中进行图形输出就必须对WM_PAINT进行处理。
 3)未处理的消息到那里去了:M$为窗口编写了默认的窗口过程,这个窗口过程将负责处理那些你不处理消息。正因为有了这个默认窗口过程我们才可以利用Windows的窗口进行开发而不必过多关注窗口各种消息的处理。例如窗口在被拖动时会有很多消息发送,而我们都可以不予理睬让系统自己去处理。
4)窗口句柄:说到消息就不能不说窗口句柄,系统通过窗口句柄来在整个系统中唯一标识一个窗口,发送一个消息时必须指定一个窗口句柄表明该消息由那个窗口接收。而每个窗口都会有自己的窗口过程,所以用户的输入就会被正确的处理。例如有两个窗口共用一个窗口过程代码,你在窗口一上按下鼠标时消息就会通过窗口一的句柄被发送到窗口一而不是窗口二。

消息产生到被窗口响应的步骤:系统发生了或用户发出某个事件。Windows把这个事件翻译为消息,然后把他放到消息队列中。应用程序从消息队列中接受到这个消息,把他存放到TMsg记录中。应用程序把消息传递给一个适当的窗体过程。窗体过程响应这个消息并进行处理。把消息传递给了这个窗体的窗体函数。
MFC消息机制:在Windows应用程序的主函数中,首先要注册窗口类,然后创建并显示窗口。创建窗口后程序就进入消息循环,在消息循环中,程序不断地获得消息并将消息派送给对应的窗口函数进行处理

程序设计模式(单例模式、工厂模式、观察者模式)

单例模式

作用:保证一个类只有一个实例,并提供一个访问它的全局访问点,使得系统中只有唯一的一个对象实例。

应用:常用于管理资源,如日志、线程池

主要角色:单例类:包含一个实例且能自行创建这个实例的类。访问类:使用单例的类。

单例模式的结构图

工厂模式

工厂模式包括三种:简单工厂模式、工厂方法模式、抽象工厂模式。

工厂模式的主要作用是封装对象的创建,分离对象的创建和操作过程,用于批量管理对象的创建过程,便于程序的维护和扩展。

观察者模式也是一种非常常用的设计模式,而且也不复杂。下面我们就来看看这种模式。

定义:策略模式定义了一系列的算法,并将每一个算法封装起来,而且使它们还可以相互替换。策略模式让算法独立于使用它的客户而独立变化。

图 6-11 观察者模式的结构图

在观察者模式中有如下角色:

Subject:抽象主题(抽象被观察者),抽象主题角色把所有观察者对象保存在一个集合里,每个主题都可以有任意数量的观察者,抽象主题提供一个接口,可以增加和删除观察者对象。
ConcreteSubject:具体主题(具体被观察者),该角色将有关状态存入具体观察者对象,在具体主题的内部状态发生改变时,给所有注册过的观察者发送通知。
Observer:抽象观察者,是观察者者的抽象类,它定义了一个更新接口,使得在得到主题更改通知时更新自己。
ConcrereObserver:具体观察者,实现抽象观察者定义的更新接口,以便在得到主题更改通知时更新自身的状态。

单例模式的多线程安全问题:

在单例模式的实现中,如果不采取任何措施,在多线程下是不安全的,可能会同时创建多个实例。因此,为了保证单例模式在多线程下的线程安全,一般采用下面几种方式实现单例模式:1)饿汉式:基于class loader机制避免多线程的同步问题,不过,instance在类装载时就实例化,可能会产生垃圾对象。2)懒汉式:通过双重锁机制实现线程安全。
 

生产者、消费者问题

对于有界缓冲区的生产者—消费者问题,两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者,将信息放入缓冲区;另一个是消费者,从缓冲区中取出信息(也可以把这个问题一般化为m个生产者和n个消费者问题,但是我们只讨论一个生产者和一个消费者的情况,这样可以简化解决方案)。

https://img-blog.csdn.net/20170119150635987

ET 模式与 LT 模式的区别

参考:https://blog.csdn.net/feitianxuxue/article/details/17078179

在使用epoll时,在函数 epoll_ctl中如果不设定,epoll_event 的event默认为LT(水平触发)模式。使用LT模式意味着只要fd处于可读或者可写状态,每次epoll_wait都会返回该fd,这样的话会带来很大的系统开销,且处理时候每次都需要把这些fd轮询一遍,如果fd的数量巨大,不管有没有事件发生,epoll_wait都会触发这些fd的轮询判断。

         在ET模式下,当有事件发生时,系统只会通知你一次,即在调用epoll_wait返回fd后,不管这个事件你处理还是没处理,处理完没有处理完,当再次调用epoll_wait时,都不会再返回该fd,这样的话程序员要自己保证在事件发生时要及时有效的处理完该事件。例如:fd发生了IN事件,在调用epoll_wait后发现了该时间,程序员要保证在本次轮询中对该fd做了读操作,且还要循环调用recv操作,直到读到的recv的返回值小于请求值,或者遇到EAGAIN错误,否则,在下次轮询时,如果该fd没有再次触发事件,你就没有机会知道这个fd需要处理。这样就会增加程序员的负担和出错的机会(可能有些数据没有来得及处理,丢失数据)。

         在LT模式下,无论fd是否有事件发生,或者还有一些事件没有处理完,每次调用epoll_wait时,总会得到该fd让你处理(只要有没事件没有处理,会一直通知你处理,直到你处理完为止,这样就保证了数据的不丢失)。

         操作系统在LT模式下维护的就绪队列大小相对于ET模式肯定大,且LT轮询所有的fd总比ET轮询的fd大。自然在性能上LT不如ET,但是在使用ET模式的时,需要循环调用recv,send等处理函数,得保证其事件处理完毕,这样也会带来开销且容易出错。

从 kernel 代码来看,ET/LT模式的处理逻辑几乎完全相同,差别仅在于 LT模式在 event 发生时不会将其从 ready list 中移除,略为增大了event 处理过程中 kernel space 中记录数据的大小。

 总结:

1. epoll 的 ET和 LT 模式处理逻辑差异极小,性能测试结果表明常规应用场景中二者性能差异可以忽略。
2. 使用 ET 的程序比使用LT 的逻辑复杂,出错概率更高。
3. ET 和LT 的性能差异主要在于 epoll_wait 系统调用的处理速度,是否是程序的性能瓶颈需要视应用场景而定,不可一概而论。

个人建议使用LT模式
 

同步异步概念?什么是非阻塞模式?

    所谓同步,就是在发出一个功能调用时,在没有得到结果之前,该调用就不返回。按照这个定义,其实绝大多数函数都是同步调用(例如sin, isdigit等)。但是一般而言,我们在说同步、异步的时候,特指那些需要其他部件协作或者需要一定时间完成的任务。最常见的例子就是 SendMessage。该函数发送一个消息给某个窗口,在对方处理完消息之前,这个函数不返回。当对方处理完毕以后,该函数才把消息处理函数所返回的 LRESULT值返回给调用者。
    异步的概念和同步相对。当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者。以 CAsycSocket类为例(注意,CSocket从CAsyncSocket派生,但是起功能已经由异步转化为同步),当一个客户端通过调用 Connect函数发出一个连接请求后,调用者线程立刻可以朝下运行。当连接真正建立起来以后,socket底层会发送一个消息通知该对象。这里提到执行部件和调用者通过三种途径返回结果:状态、通知和回调。可以使用哪一种依赖于执行部件的实现,除非执行部件提供多种选择,否则不受调用者控制。如果执行部件用状态来通知,那么调用者就需要每隔一定时间检查一次,效率就很低(有些初学多线程编程的人,总喜欢用一个循环去检查某个变量的值,这其实是一种很严重的错误)。如果是使用通知的方式,效率则很高,因为执行部件几乎不需要做额外的操作。至于回调函数,其实和通知没太多区别。
阻塞
     阻塞调用是指调用结果返回之前,当前线程会被挂起。函数只有在得到结果之后才会返回。有人也许会把阻塞调用和同步调用等同起来,实际上他是不同的。对于同步调用来说,很多时候当前线程还是激活的,只是从逻辑上当前函数没有返回而已。例如,我们在CSocket中调用Receive函数,如果缓冲区中没有数据,这个函数就会一直等待,直到有数据才返回。而此时,当前线程还会继续处理各种各样的消息。如果主窗口和调用函数在同一个线程中,除非你在特殊的界面操作函数中调用,其实主界面还是应该可以刷新。socket接收数据的另外一个函数recv则是一个阻塞调用的例子。当socket工作在阻塞模式的时候,如果没有数据的情况下调用该函数,则当前线程就会被挂起,直到有数据为止。 

为什么在操作系统中引入线程?使用线程池提高并发度,并降低频繁创建线程的开销。怎么提高并发度的,为什么说创建线程的开销大?

1、为什么要在操作系统中引入线程?
答:由于进程是资源的拥有者,所以在创建、撤销、切换操作中需要较大的时空开销,限制了并发程度的进一步提高。为减少进程切换的开销,把进程作为资源分配单位和调度单位这两个属性分开处理,即进程还是作为资源分配的基本单位,但是不作为调度的基本单位(很少调度或切换),把调度执行与切换的责任交给“线程”。这样做的好处不但可以提高系统的并发度,还能适应新的对称多处理机(SMP)环境的运行,充分发挥其性能。
2、怎么提高并发度?

答:采用多线程

3、为么说创建线程开销大?

多线程中两个必要的开销:线程的创建、上下文切换

上下文切换概念:当前任务执行一个时间片后会切换到下一个任务。在切换之前,上一个任务的状态会被保存下来,下次切换回这个任务时,可以再加载这个任务的状态,任务从保存到再加载的过程就是一次上下文切换。

注意:1)时间片是CPU分配给各个线程的时间,时间片一般是几十毫秒。2)CPU通过给每个线程分配CPU时间片,并且不停地切换线程来实现多线程。因为时间片非常短,所以感觉多个线程是在同时执行。

减少上下文切换的方法:1)无锁并发编程:多线程竞争锁时,会引起上下文切换,所以在使用多线程处理数据时,可以采用一些策略来避免使用锁。常见的策略:将数据按照id的哈希值进行切分,不同的线程处理不同段的数据。2)锁分离技术:举例:ConcurrentHashMap。3)CAS算法:ava的Atomic包使用CAS算法来更新数据,而不需要加锁。4)使用最少的线程:避免创建不需要的线程,比如任务很少,但是创建了很多线程来处理,这样会造成大量线程都处于等待状态。

怎么给线程分配任务的?(RR策略)有没有什么优化方式?

参考:https://blog.csdn.net/u012007928/article/details/40144425

调度方法

1,SCHED_OTHER 分时调度策略,

2,SCHED_FIFO实时调度策略,先到先服务

3,SCHED_RR实时调度策略,时间片轮转

实时进程将得到优先调用,实时进程根据实时优先级决定调度权值,分时进程则通过nice和counter值决定权值,nice越小,counter越大,被调度的概率越大,也就是曾经使用了cpu最少的进程将会得到优先调度。

SHCED_RR和SCHED_FIFO的不同:

当采用SHCED_RR策略的进程的时间片用完,系统将重新分配时间片,并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。

SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。

如果有相同优先级的实时进程(根据优先级计算的调度权值是一样的)已经准备好,FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。

相同点:

RR和FIFO都只用于实时任务。

创建时优先级大于0(1-99)。

按照可抢占优先级调度算法进行。

就绪态的实时任务立即抢占非实时任务。

多线程实现方式

三种创建线程的方法分别为:CreateThread,AfxBeginThread,_beginthread/beginthreadex(thread runnable callable

写时复制/拷贝技术,具体的数据是如何在存储之间传递的?

Linux的fork()使用写时拷贝(copy-on-write)页实现。写时拷贝是一种可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间,而是让父进程和子进程共享同一个拷贝。只有在需要写入的时候,数据才会被复制,从而使各个进程拥有各自的拷贝。也就是说,资源的复制只有在需要写入的时候才进行,在此之前,只是以只读方式共享。这种技术使地址空间上的页的拷贝被推迟到实际发生写入的时候。在页根本不会被写入的情况下—举例来说,fork()后立即调用exec()—它们就无需复制了。fork()的实际开销就是复制父进程的页表以及给子进程创建惟一的进程描述符。在一般情况下,进程创建后都会马上运行一个可执行的文件,这种优化可以避免拷贝大量根本就不会被使用的数据(地址空间里常常包含数十兆的数据)。由于Unix强调进程快速执行的能力,所以这个优化是很重要的。

Linux

gdb 的使用, 编译器的使用

gcc生成一个可执行文件简单命令:gcc test.c

两个文件:gcc testmain.c testsub.c -lm -o test其中,-lm表示连接系统的数学库libm.a。

gdb编译器

1、启动你的程序,可以按照你的自定义的要求随心所欲的运行程序。
2、可让被调试的程序在你所指定的调置的断点处停住。(断点可以是条件表达式)
3、当程序被停住时,可以检查此时你的程序中所发生的事。
4、动态的改变你程序的执行环境

常见的 Linux 的命令

拷贝文件 、查看 ip、vim 的基本操作(查找字符串、替换字符串)

查看硬盘大小等等操作

cp, ifconfig - a, 

a)vi查找:  当你用vi打开一个文件后,因为文件太长,如何才能找到你所要查找的关键字呢?在vi里可没有菜单-〉查找,不过没关系,你在命令模式下敲斜杆(/)这时在状态栏(也就是屏幕左下脚)就出现了 “/”然后输入你要查找的关键字敲回车就可以了。如果你要继续查找此关键字,敲字符n就可以继续查找了。值得注意的是“/”是向下查找,而“?”是向上查找,而在键盘定义上“?”刚好是“/”的上档符。

b)vi替换:vi/vim 中可以使用 :s 命令来替换字符串以前只会使用一种格式来全文替换,今天发现该命令有很多种写法(vi 真是强大啊飕还有很多需要学习),记录几种在此,方便以后查询。
:s/vivian/sky/ 替换当前行第一个 vivian 为 sky
:s/vivian/sky/g 替换当前行所有 vivian 为 sky
:n,$s/vivian/sky/ 替换第 n 行开始到最后一行中每一行的第一个 vivian 为 sky
:n,$s/vivian/sky/g 替换第 n 行开始到最后一行中每一行所有 vivian 为 sky
n 为数字,若 n 为 .,表示从当前行开始到最后一行
:%s/vivian/sky/(等同于:g/vivian/s//sky/)替换每一行的第一个 vivian 为 sky
:%s/vivian/sky/g(等同于:g/vivian/s//sky/g)替换每一行中所有 vivian 为 sky

可以使用 # 作为分隔符,此时中间出现的 / 不会作为分隔符
:s#vivian/#sky/# 替换当前行第一个 vivian/ 为 sky/
:%s+/oradata/apras/+/user01/apras1+ (使用+ 来 替换 /):/oradata/apras/替换成/user01/apras1/

查看硬盘大小:

  • du -sh [目录名]:返回该目录的大小
  • du -sm [文件夹]:返回该文件夹总M数
  • du -h [目录名]:查看指定文件夹下的所有文件大小(包含子文件夹)

如何查询某个文件被哪些进程占用,如何查询当前系统的cpu和内存占用

查看进程:

1:使用 ps -ef|grep xxx 命令查找需要查看的进程,xxx是进程名字

2:top -p pid 查看程序的情况 

3:ps -aux | grep process_name

4:cat /proc/pid/status 

查看文件被哪些进程占用:

1、lsof | grep test.sh  2、fuser -v test.sh

查询当前系统的cpu和内存占用:top/free

数据库

具体参考:https://blog.csdn.net/qq_27262727/article/details/104875370

数据库索引,BB+树的区别

索引的目的就是便于快速查找。一本书的索引就是目录,可以让我们快速定位到要查找的内容;数据库的数据是以记录的方式存在的,所以索引的目的就是便于查找某一些记录。

索引类型(常见的数据库书籍中的关于索引类别的一些称呼):

①唯一索引:不允许其中任何两行具有相同值的索引

②.主键索引:可以认为是特殊的唯一索引,仅利用主键建立的索引

③.单一索引:任何一个单一数据项建立的索引,假如有下表【country,city,personNumber】,如果我们想查询某个国家的人数,我们就应当以国家建立索引,这样单一数据项建立的索引就是单一索引。
④.复合索引:多个数据项建立的索引,假如有下表【country,city,personNumber】,如果我们想查询某个城市的人数,我们就应当以【country,city】建立索引,多个数据项建立索引的时候,我们应当指定其排序的先后顺序,此处国家应优先排序,城市次之。

⑤.聚簇索引:利用主键建立的索引,其物理存放顺序与主键顺序一致。因为数据只有一个物理存放顺序,所以一个表只有一个聚簇索引。在MySQL中,选定主键之后将会自动为主键创建索引。该索引可以维护主键的唯一性。非叶子节点包含了主键值,而叶子节点则指向了一条完整的记录

⑥.非聚簇索引(二级索引,辅助索引):除了聚簇索引之外,其余所有的索引都是非聚簇索引。非聚簇索引为什么是二级索引呢?重点在于一个二字。可以料想如果WHERE条件不是根据主键进行索引,那么我们就需要基于该非主键建立的索引进行检索,这样建立的索引叶子节点中包含了记录的主键,再使用主键在聚簇索引中找寻到完整的记录。可以说进行了两次B+ Tree查找而不是一次

⑦.覆盖索引:一个索引包含(覆盖)所要查询的字段的值,注意覆盖索引与具体的查询有关。假如有下表【country,city,personNumber】,如果我们想查询某个城市的人数,覆盖索引指的是可以将你想要查询的列建立在一个索引中,如(国家,城市,人数)作为一个复合索引,此时查找某一个国家的所有城市利用索引就可以完成,实际上这也相当于完成了聚簇索引的功能


b树(balance tree)和b+树应用在数据库索引,可以认为是m叉的多路平衡查找树

如图所示,区别有以下两点:

1. B+树中只有叶子节点会带有指向记录的指针(ROWID),而B树则所有节点都带有,在内部节点出现的索引项不会再出现在叶子节点中。

2. B+树中所有叶子节点都是通过指针连接在一起,而B树不会。

B+树的优点:

1. 非叶子节点不会带上ROWID,这样,一个块中可以容纳更多的索引项,一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。

2. 叶子节点之间通过指针来连接,范围扫描将十分简单,而对于B树来说,则需要在叶子节点和内部节点不停的往返移动。

B树的优点:

对于在内部节点的数据,可直接得到,不必根据叶子节点来定位。

数据库存储过程

存储过程

数据库存储引擎

存储引擎对比

1、InnoDB存储引擎(推荐)

InnoDB是事务型数据库的首选引擎,支持事务安全表(ACID),支持行锁定和外键,上图也看到了,InnoDB是默认的MySQL引擎。

InnoDB主要特性
  • 为MySQL提供了具有提交、回滚和崩溃恢复能力的事物安全(ACID兼容)存储引擎。InnoDB锁定在行级并且也在SELECT语句中提供一个类似Oracle的非锁定读。这些功能增加了多用户部署和性能。在SQL查询中,可以自由地将InnoDB类型的表和其他MySQL的表类型混合起来,甚至在同一个查询中也可以混合
  • InnoDB存储引擎为在主内存中缓存数据和索引而维持它自己的缓冲池。InnoDB将它的表和索引在一个逻辑表空间中,表空间可以包含数个文件(或原始磁盘文件)。这与MyISAM表不同,比如在MyISAM表中每个表被存放在分离的文件中。InnoDB表可以是任何尺寸,即使在文件尺寸被限制为2GB的操作系统上
  • InnoDB支持外键完整性约束,存储表中的数据时,每张表的存储都按主键顺序存放,如果没有显示在表定义时指定主键,InnoDB会为每一行生成一个6字节的ROWID,并以此作为主键

使用 InnoDB存储引擎 MySQL将在数据目录下创建一个名为 ibdata1 的10MB大小的自动扩展数据文件,以及两个名为ib_logfile0ib_logfile1的5MB大小的日志文件

2、MyISAM存储引擎

MyISAM基于ISAM存储引擎,并对其进行扩展。它是在Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM拥有较高的插入、查询速度,但不支持事物。

MyISAM主要特性:
  • 被大文件系统和操作系统支持
  • 当把删除和更新及插入操作混合使用的时候,动态尺寸的行产生更少碎片。这要通过合并相邻被删除的块,若下一个块被删除,就扩展到下一块自动完成
  • 每个MyISAM表最大索引数是64,这可以通过重新编译来改变。每个索引最大的列数是16
  • 最大的键长度是1000字节,这也可以通过编译来改变,对于键长度超过250字节的情况,一个超过1024字节的键将被用上
  • BLOB和TEXT列可以被索引
  • NULL被允许在索引的列中,这个值占每个键的0~1个字节
  • 所有数字键值以高字节优先被存储以允许一个更高的索引压缩
  • 每个MyISAM类型的表都有一个AUTO_INCREMENT的内部列,当INSERT和UPDATE操作的时候该列被更新,同时AUTO_INCREMENT列将被刷新。所以说,MyISAM类型表的AUTO_INCREMENT列更新比InnoDB类型的AUTO_INCREMENT更快
  • 可以把数据文件和索引文件放在不同目录
  • 每个字符列可以有不同的字符集
  • 有VARCHAR的表可以固定或动态记录长度
  • VARCHAR和CHAR列可以多达64KB

使用MyISAM引擎创建数据库,将产生3个文件。文件的名字以表名字开始,扩展名之处文件类型:frm文件存储表定义、数据文件的扩展名为.MYD(MYData)、索引文件的扩展名时.MYI(MYIndex)

3、MEMORY存储引擎

MEMORY存储引擎将表中的数据存储到内存中,未查询和引用其他表数据提供快速访问。

MEMORY主要特性:
  • MEMORY表的每个表可以有多达32个索引,每个索引16列,以及500字节的最大键长度
  • MEMORY存储引擎执行HASH和BTREE缩影
  • 可以在一个MEMORY表中有非唯一键值
  • MEMORY表使用一个固定的记录长度格式
  • MEMORY不支持BLOB或TEXT列
  • MEMORY支持AUTO_INCREMENT列和对可包含NULL值的列的索引
  • MEMORY表在所由客户端之间共享(就像其他任何非TEMPORARY表)
  • MEMORY表内存被存储在内存中,内存是MEMORY表和服务器在查询处理时的空闲中,创建的内部表共享
  • 当不再需要MEMORY表的内容时,要释放被MEMORY表使用的内存,应该执行DELETE FROMTRUNCATE TABLE,或者删除整个表(使用DROP TABLE)

MySQL 查询前 100 条数据, 以及如何分组

SELECT orderid, MAX(datachange_lasttime) AS max_time, eventpolicyid FROM o_policy_orderrelation GROUP BY orderid;

select * from test a left join test b

on a.type=b.type and a.data<=b.data

group by a.type,a.data

– having count(a.data)<=2

计算机网络

OSI七层模型/TCP/IP四层模型?

webp每层有哪些协议

五层体系结构包括:应用层、运输层、网络层、数据链路层和物理层。 
五层协议只是OSI和TCP/IP的综合,实际应用还是TCP/IP的四层结构。为了方便可以把下两层称为网络接口层

这里写图片描述

TCP 和 UDP 的区别

1. TCP协议在传送数据段的时候要给段标号;UDP协议不

2. TCP协议可靠;UDP协议不可靠

3. TCP协议是面向连接;UDP协议采用无连接

4. TCP协议负载较高,采用虚电路;UDP采用无连接

5. TCP协议的发送方要确认接收方是否收到数据段(3次握手协议)

6. TCP协议采用窗口技术和流控制

socket 的流程?服务端的socket过程是什么?

参考:https://zhuanlan.zhihu.com/p/63226104

网络通信的标准流程是,服务端新建一个socket,然后在该socket中绑定一个地址,再设置该socket为监听socket,然后阻塞在accept等待连接。客户端新建一个socket,然后connect到一个服务端的地址。下面分析一下这个过程。看多个客户端或者多个连接是如何在一个监听的socket中完成通信的。

什么是socket?socket翻译为套接字,socket是在应用层和传输层之间的一个抽象层,它把TCP/IP层复杂的操作抽象为几个简单的接口供应用层调用已实现进程在网络中通信。

Socket通信流程

1、服务器收到一个syn包的时候,在tcp_rcv中进行处理。该函数根据tcp数据包中的目的端口和ip,源端口和ip找到一个最匹配的socket。

2、监听socket中有本机的ip和监听的端口。所以根据tcp数据包,可以找到对应的socket。接着判断找到的socket的状态。

3、tcp_conn_request函数很长,下面只列出关键代码。sock结构体是tcp层的表示,socket结构体是更上层的抽象,比如unix域套接字,也是使用socket结构体,然后在unix域实现的时候,使用unix_proto_data结构体。socket和sock结构体是互相指向的。tcp维护了一个哈希链表,以监听的端口号为因子进行哈希。

4、至此完成了tcp的两次握手。等收到客户端的ack的时候,在tcp_ack中完成第三次握手。

https://images2017.cnblogs.com/blog/1199740/201709/1199740-20170915104804953-3885330.png

 

三次握手?四次挥手?

第一次握手:客户端发送 syn 包(syn=j)到服务器,并进入 SYN_SEND 状态,等 待服务器确认;
第二次握手:服务器收到 syn 包,必须确认客户的 SYN(ack=j+1),同时自己也 发送一个 SYN 包(syn=k),即 SYN+ACK 包,此时服务器进入 SYN_RECV 状态; 第三次握手:客户端收到服务器的 SYN+ACK 包,向服务器发送确认包 ACK(ack=k+1),此包发送完毕,客户端和服务器进入 ESTABLISHED 状态,完成 三次握手。 握手过程中传送的包里不包含数据,三次握手完毕后,客户端与服务器才正式 开始传送数据。
理想状态下,TCP 连接一旦建立,在通信双方中的任何一方主动关闭连接之 前,TCP 连接都将被一直保持下去。四次挥手:
第一次: 当主机 A 完成数据传输后,将控制位 FIN 置 1,􏰅出停止 TCP 连接的 请求 ;
第二次: 主机 B 收到 FIN 后对其作出响应,确认这一方向上的 TCP 连接将关 闭,将ACK置1;
第三次: 由 B 端再􏰅出反方向的关闭请求,将 FIN 置 1 ;
第四次: 主机 A 对主机 B 的请求进行确认,将 ACK 置 1,双方向的关闭结束.。

TCP 有哪些字段

1、ACK 是 TCP 报头的控制位之一,对数据进行确认。确认由目的端发出, 用 它来告诉发送端这个序列号之前的数据段都收到了。 比如确认号为 X,则表示 前 X-1 个数据段都收到了,只有当 ACK=1 时,确认号才有效,当 ACK=0 时,确认 号无效,这时会要求重传数据,保证数据的完整性。
2、SYN 同步序列号,TCP 建立连接时将这个位置 1。
3、FIN 发送端完成发送任务位,当 TCP 完成数据传输需要断开时,,􏰅出断开 连接的一方将这位置 1。
Socket 建立网络连接的步骤:服务器监听、客户端请求、连接确认

TCP粘包,拆包及解决方法、丢包的原因及解决办法

粘包、拆包发生原因
发生TCP粘包或拆包有很多原因,现列出常见的几点,可能不全面,欢迎补充,
1、要发送的数据大于TCP发送缓冲区剩余空间大小,将会发生拆包。
2、待发送数据大于MSS(最大报文长度),TCP在传输前将进行拆包。
3、要发送的数据小于TCP发送缓冲区的大小,TCP将多次写入缓冲区的数据一次发送出去,将会发生粘包。
4、接收数据端的应用层没有及时读取接收缓冲区中的数据,将发生粘包。
等等。

粘包、拆包解决办法
通过以上分析,我们清楚了粘包或拆包发生的原因,那么如何解决这个问题呢?解决问题的关键在于如何给每个数据包添加边界信息,常用的方法有如下几个:

1、发送端给每个数据包添加包首部,首部中应该至少包含数据包的长度,这样接收端在接收到数据后,通过读取包首部的长度字段,便知道每一个数据包的实际长度了。
2、发送端将每个数据包封装为固定长度(不够的可以通过补0填充),这样接收端每次从接收缓冲区中读取固定长度的数据就自然而然的把每个数据包拆分开来。
3、可以在数据包之间设置边界,如添加特殊符号,这样,接收端通过这个边界就可以将不同的数据包拆分开。
等等。

测试的时候采用的是一台机器连续发送数据来模拟高并发的场景,所以在测试的时候会发现服务器端收到的数据包的个数经常会小于包的序号,好像发生了丢包。但经过仔细分析可以发现,这种情况是因为TCP发送缓存溢出导致的丢包,也就是这个数据包根本没有发出来。也就是说,发送端发送数据过快,导致接收端缓存很快被填满,这个时候接收端会把通知窗口设置为0从而控制发送端的流量,这样新到的数据只能暂存在发送端的发送缓存中,当发送缓存溢出后,就出现了我上面提到的丢包,这个问题可以通过增大发送端缓存来缓解这个问题,

了解 HTTP, TCP 吗

参考:https://www.jianshu.com/p/947a2673102a

HTTP的主要特点

1、简单快速:客户向服务器请求服务时,只需传送请求方法和路径。请求方法常用的有GET、HEAD、POST。每种方法规定了客户与服务器联系的类型不同。由于HTTP协议简单,使得HTTP服务器的程序规模小,因而通信速度很快。

2、灵活:HTTP允许传输任意类型的数据对象。正在传输的类型由Content-Type加以标记。

3.无连接:无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求,并收到客户的应答后,即断开连接。采用这种方式可以节省传输时间。

4.无状态:HTTP协议是无状态协议。无状态是指协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息,则它必须重传,这样可能导致每次连接传送的数据量增大。另一方面,在服务器不需要先前信息时它的应答就较快。

具体概念:TCP协议对应于传输层,而HTTP协议对应于应用层从本质上来说,二者没有可比性。Http协议是建立在TCP协议基础之上的,当浏览器需要从服务器获取网页数据的时候,会发出一次Http请求。Http会通过TCP建立起一个到服务器的连接通道,当本次请求的数据完毕后,Http会立即将TCP连接断开,这个过程是很短的。所以Http连接是一种短连接,是一种无状态的连接。所谓的无状态,是指浏览器每次向服务器发起请求的时候,不是通过一个连接,而是每次都建立一个新的连接。如果是一个连接的话,服务器进程中就能保持住这个连接并且在内存中记住一些信息状态。而每次请求结束后,连接就关闭,相关的内容就释放了,所以记不住任何状态,成为无状态连接。

TCP协议

TCP协议主要是在传输层,三次握手四次挥手

HTTP 报文, 一个 HTTP 请求包括

一个HTTP请求报文由请求行(request line)、请求头部(header)、空行和请求数据4个部分组成。

HTTP响应也由三个部分组成,分别是:状态行、消息报头、响应正文。

HTTP报文首字段

参考:https://www.cnblogs.com/klguang/p/4618526.html

概念: HTTP 报文是在HTTP 应用程序之间发送的数据块。这些数据块以一些文本形式的元信息(meta-information)开头,这些信息描述了报文的内容及含义,后面跟着可选的数据部分。这些报文在客户端、服务器和代理之间流动。

HTTP报文三个部分:

1、起始行报文的第一行就是起始行,在请求报文中用来说明要做些什么,在响应报文中说明出现了什么情况。

2、首部字段起始行后面有零个或多个首部字段。每个首部字段都包含一个名字和一个值,为了便于解析,两者之间用冒号(:)来分隔。首部以一个空行结束。添加一个首部字段和添加新行一样简单。

3、主体空行之后就是可选的报文主体了,其中包含了所有类型的数据。请求主体中包括了要发送给Web 服务器的数据;响应主体中装载了要返回给客户端的数据。起始行和首部都是文本形式且都是结构化的,而主体则不同,主体中可以包含任意的二进制数据(比如图片、视频、音轨、软件程序)。当然,主体中也可以包含文本。

常见HTTP方法

常见 HTTP 响应码有哪些

 

100~199——信息性状态码

200~299——成功状态码

300~399——重定向状态码     

400~499——客户端错误状态码

500~599——服务器错误状态码

什么是HTTP 长连接,什么是短连接, 它们各自的使用场景是什么?

短连接在HTTP/1.0中,默认使用的是短连接。也就是说,浏览器和服务器每进行一次HTTP操作,就建立一次连接,但任务结束就中断连接。如果客户端浏览器访问的某个HTML或其他类型的 Web页中包含有其他的Web资源,如JavaScript文件、图像文件、CSS文件等;当浏览器每遇到这样一个Web资源,就会建立一个HTTP会话。

操作步骤:建立连接——数据传输——关闭连接...建立连接——数据传输——关闭连接

短连接的优点是:管理起来比较简单,存在的连接都是有用的连接,不需要额外的控制手段

长连接:在使用长连接的情况下,当一个网页打开完成后,客户端和服务器之间用于传输HTTP数据的 TCP连接不会关闭,如果客户端再次访问这个服务器上的网页,会继续使用这一条已经建立的连接。Keep-Alive不会永久保持连接,它有一个保持时间,可以在不同的服务器软件(如Apache)中设定这个时间。实现长连接要客户端和服务端都支持长连接。

操作步骤:建立连接——数据传输...(保持连接)...数据传输——关闭连接

长连接和短连接的优点和缺点:长连接可以省去较多的TCP建立和关闭的操作,减少浪费,节约时间。对于频繁请求资源的客户来说,较适用长连接。不过这里存在一个问题存活功能的探测周期太长,还有就是它只是探测TCP连接的存活,属于比较斯文的做法,遇到恶意的连接时,保活功能就不够使了。短连接对于服务器来说管理较为简单,存在的连接都是有用的连接,不需要额外的控制手段。但如果客户请求频繁,将在TCP的建立和关闭操作上浪费时间和带宽。长连接和短连接的产生在于client和server采取的关闭策略,具体的应用场景采用具体的策略,没有十全十美的选择,只有合适的选择。

各自使用场景?

长连接多用于操作频繁,点对点的通讯,而且连接数不能太多情况。比如数据库连接

短连接多用于像WEB网站的http服务,因为长连接对于服务端来说会耗费一定的资源,而像WEB网站这么频繁的成千上万甚至上亿客户端的连接用短连接会更省一些资源。

HTTPHTTPS的区别,HTTPS的具体握手步骤,建立连接完成以后通信过程用什么加密方式

HTTP:是互联网上应用最为广泛的一种网络协议,是一个客户端和服务器端请求和应答的标准(TCP),用于从WWW服务器传输超文本到本地浏览器的传输协议,它可以使浏览器更加高效,使网络传输减少。

HTTPS:是以安全为目标的HTTP通道,简单讲是HTTP的安全版,即HTTP下加入SSL层,HTTPS的安全基础是SSL,因此加密的详细内容就需要SSL。

这里写图片描述

HTTPS协议的主要作用可以分为两种:一种是建立一个信息安全通道,来保证数据传输的安全;另一种就是确认网站的真实性。

HTTPS和HTTP的区别主要如下:

  1. https协议需要到ca申请证书,一般免费证书较少,因而需要一定费用。

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

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

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

SSL四次握手过程:

  1. 客户端请求建立SSL链接,并向服务端发送一个随机数–Client random和客户端支持的加密方法,比如RSA公钥加密,此时是明文传输。
  2. 服务端回复一种客户端支持的加密方法、一个随机数–Server random、授信的服务器证书和非对称加密的公钥。
  3. 客户端收到服务端的回复后利用服务端的公钥,加上新的随机数–Premaster secret 通过服务端下发的公钥及加密方法进行加密,发送给服务器。
  4. 服务端收到客户端的回复,利用已知的加解密方式进行解密,同时利用Client random、Server random和Premaster secret通过一定的算法生成HTTP链接数据传输的对称加密key – session key。

此后的HTTP链接数据传输即通过对称加密方式进行加密传输。

TCP、UDP 的工作流程;客服端服务器端的创建连接啊等等的流程

TCP:传输控制协议,一种面向连接的协议,给用户进程提供可靠的全双工的字节流,TCP套接口是字节流套接口(stream socket)的一种。

UDP:用户数据报协议。UDP是一种无连接协议。UDP套接口是数据报套接口(datagram socket)的一种。

1、创建一个socket,用函数socket();
2、设置socket属性,用函数setsockopt(); * 可选
3、绑定IP地址、端口等信息到socket上,用函数bind();
4、开启监听,用函数listen();
5、接收客户端上来的连接,用函数accept();
6、收发数据,用函数send()和recv(),或者read()和write();
7、关闭网络连接;
8、关闭监听;

 TCP是如何保证消息可靠,滑动窗口工作方式,TCP拥塞控制-慢启动、拥塞避免、快重传、快启动

一般原理:发生拥塞控制的原因:资源(带宽、交换节点的缓存、处理机)的需求>可用资源。

作用:拥塞控制就是为了防止过多的数据注入到网络中,这样可以使网络中的路由器或者链路不至于过载。拥塞控制要做的都有一个前提:就是网络能够承受现有的网络负荷。

对比流量控制:拥塞控制是一个全局的过程,涉及到所有的主机、路由器、以及降低网络相关的所有因素。流量控制往往指点对点通信量的控制。是端对端的问题。

拥塞窗口:发送方为一个动态变化的窗口叫做拥塞窗口,拥塞窗口的大小取决于网络的拥塞程度。发送方让自己的发送窗口=拥塞窗口,但是发送窗口不是一直等于拥塞窗口的,在网络情况好的时候,拥塞窗口不断的增加,发送方的窗口自然也随着增加,但是接受方的接受能力有限,在发送方的窗口达到某个大小时就不在发生变化了。

    发送方如果知道网络拥塞了呢?发送方发送一些报文段时,如果发送方没有在时间间隔内收到接收方的确认报文段,则就可以认为网络出现了拥塞。

    慢启动算法的思路:主机开发发送数据报时,如果立即将大量的数据注入到网络中,可能会出现网络的拥塞。慢启动算法就是在主机刚开始发送数据报的时候先探测一下网络的状况,如果网络状况良好,发送方每发送一次文段都能正确的接受确认报文段。那么就从小到大的增加拥塞窗口的大小,即增加发送窗口的大小。

    例子:开始发送方先设置cwnd(拥塞窗口)=1,发送第一个报文段M1,接收方接收到M1后,发送方接收到接收方的确认后,把cwnd增加到2,接着发送方发送M2、M3,发送方接收到接收方发送的确认后cwnd增加到4,慢启动算法每经过一个传输轮次(认为发送方都成功接收接收方的确认),拥塞窗口cwnd就加倍。

通信过程,哪些情况些会出现返回reset

RST 是 TCP 发生错误时发送的一种 TCP 分节( segment:传输层的 PDU ),可用来异常的关闭一个连接,此时客户端会返回一个 ECONNREFUSED 错误。
它会在以下三种情况下产生:

目的地为某个端口的 SYN 到达服务器,但并没有服务器在该端口监听。
TCP 想取消一个已有连接,即异常地关闭连接。
TCP 接收到一个根本不存在的连接上的分节。
第一种情况可能有如下原因:
客户端连接的端口不正确或者端口未打开(即服务器未运行)。

第二种情况可以查看第二个参考链接

第三种情况的原因:
服务端在接收到客户端部分数据后,主动关闭了连接(此时服务端处于 TIME_WAIT 状态,可以接收数据),但是客户端仍然继续在发送剩余数据。此时服务端会给客户端发送 RST。

浏览器搜索淘宝,具体的调用流程,具体用到了什么协议?

参考:https://blog.csdn.net/m_buddy/article/details/77800998

1.DNS域名解析:浏览器缓存、系统缓存、路由器、ISP的DNS服务器、根域名服务器。把域名转化成IP地址。

2.与IP地址对应的服务器建立TCP连接,经历三次握手:SYN,ACK、SYN,ACK

3.以get,post方式发送HTTP请求,get方式发送主机,用户***,connection属性,cookie等

4.获得服务器的响应,显示页面

  (1)浏览器本身是一个客户端,当你输入URL的时候,首先浏览器会去请求DNS服务器,通过DNS获取相应的域名对应的IP
(2)然后通过IP地址找到IP对应的服务器后,要求建立TCP连接
(3)浏览器发送完HTTP Request(请求)包后,服务器接收到请求包之后才开始处理请求包
(4)在服务器收到请求之后,服务器调用自身服务,返回HTTP Response(响应)包
(5)客户端收到来自服务器的响应后开始渲染这个Response包里的主体(body),等收到全部的内容随后断开与该服务器之间的TCP连接。

如果在三次握手结束后,客户端断电了,服务端可以得知吗?服务端会主动断开连接吗?

参考:https://blog.csdn.net/stpeace/article/details/44162349

心跳机制tcp keepalive的讨论、应用及“断网”、"断电"检测的C代码实现(Windows环境下),想一下, 当tcp连接被破坏后, 如果是死连接了, 服务端和客户端怎样才能知道信息能不能到达对方呢? 很自然的想法是, 不断地给对方发探测信号, 看有没有回应, 这就是心跳机制的直白原理。 所谓的心跳即是数据包, 发心跳就是一方向另一方发送的数据包, 不断地发送, 如果收不到回应, 那么就有理由认为是tcp连接出了问题。 那为什么要叫心跳呢? 你摸一下你的心, 你看它是不是均匀在跳? 理解了吧, 均匀发出去的数据包就类似于均匀的心跳信号。 所以, 我要说: 心跳就是(探测性的)数据包。

malloc如果遇到内存不足以申请的情况怎么办?new呢?

malloc分配内存失败的原因:

1. 内存不足。
2. 在前面的程序中出现了内存的越界访问,导致malloc()分配函数所涉及的一些信息被破坏。下次再使用malloc()函数申请内存就会失败,返回空指针NULL(0)

解决办法:

设置内存申请失败异常函数,

c++ 内存申请失败的时候会抛出bad_alloc。但是总不能每次new的时候都 try catch吧!

c++ 提供 出错处理函数 set_new_handler

typedef void (*new_handler)();
new_handler set_new_handler(new_handler p) throw();

看定义得出,只要声明一个 没有 参数 没有返回值的函数 new_handler ,然后传给 set_new_handler 就可以了,如下代码:

void nomorememory()
{
    cerr << "无法申请内存\n";
    abort();
}


int main()
{
    set_new_handler(nomorememory);          //直接传函数指针就可以了。
    int *pbigdataarray = new int[100000000];//申请这么多,呵呵...测试测试

    ...
    
}