云虚拟主机 多个网站,wordpress code editor,wordpress模板学校,电子网址怎么创建总结了语法、数据结构、常见排序算法、操作系统、网络五大块常见校招面试题。欢迎补充与修正。 ★★语法知识★★
一、C与C的区别
面向对象与面向过程的区别
面向过程
面向过程编程是就分析出解决问题题的步骤#xff0c;然后把这些步骤一步一步的实现#xff0c;使用的时… 总结了语法、数据结构、常见排序算法、操作系统、网络五大块常见校招面试题。欢迎补充与修正。 ★★语法知识★★
一、C与C的区别
面向对象与面向过程的区别
面向过程
面向过程编程是就分析出解决问题题的步骤然后把这些步骤一步一步的实现使用的时候一个一个的一次调用就可以了。
面向对象
面向对象编程就是把问题分解成各个对象建立对象的目的不是为了完成一个步骤而是为了描述某个市委在整个解决问题的步骤中的行为。 举个例子玩五子棋 使用面向过程的思想来考虑就是开始游戏白棋先走、绘制画面、轮到黑子、绘制画面、判断输赢、重复之前的过程输出最终结果。 使用面向对象的思想来考虑就是玩家系统、棋盘系统、判定系统、输出系统。 面向对象就是高度的将实物抽象化也就是功能的划分面向过程就是自顶向下编程也就是步骤的划分 具体语言的区别
1、关键字不同
C99有32个关键字
C98有63个关键字
一些关键字细微的区别
1、struct在C语言猴子那个struct定义的变量中不能由函数在C中可以有函数
2、mallocmalloc的返回值是void*在C语言中可以赋值给任意类型的指针在C中必须要进行强制类型转换否则会报错。
3、class和structclass是对struct的扩展struct的默认访问权限是public而class的默认访问全显示private
2、后缀名不同
C源文件的后缀是.cC源文件的后缀是.cpp在VS中如果在创建源文件的时候什么都不给默认的就是.cpp
3、返回值不同
在C语言中如果一个函数没有指定返回值得类型默认的返回值为int类型并且会返回一个随机数一般为0xCCCCCCCCC中如果一个函数没有返回值则必须要指定为void否则编译不会通过。
4、参数列表不同
在C语言中函数没有指定参数列表的时候默认可以接受多个参数但是不支持无名参数在C中因为严格的参数类型检测没有参数列表的函数默认为void不接受任何参数但是他支持无名参数。
5、缺省参数
缺省参数的声明或定制函数时的参数指定一个默认值。在调用该函数时如果没有指定实参则可以采用该默认值则使用指定的参数。但是这在C语言中是不支持的。
6、函数重载
函数重载是函数的一种特殊情况指的是在同一作用域中声明几个功能类似的同名函数这些同名函数的形参列表必须不同或者是在类中使用const修饰的函数和没有使用const修饰的函数常用来处理实现功能类似但是数据类型不同的问题。在C语言中没有函数重载是因为C语言对函数名的修饰只是在函数名前添加一个下划线但是C对函数名的修饰会添加上该函数的返回值和参数列表。
7、标准输入输出
在C语言中使用的是scanf()和printf()来实现的但是C中是使用类来实现的。cin、cout对象他们本身并不是C语言的组成部分在C中不提供内在的输入输出运算符这时与其他语言不相同的地方他的输入和输出是通过C中的类来实现的cin和cout都是这些类的实例是在C语言的外部实现的。
8、动态内存管理
C语言使用的是malloc/free函数C在此基础上还添加了new/delete两个关键字。
9、const修饰的变量
C语言中const修饰的变量不可以用在定义数组时的大小并且在定义的时候可以不设定初始值但是在C中修饰的变量在定义的时候必须要设定初始值并且可以用在定义数组的大小如果不进行取地址或解引用的话是存放在符号表中的不开辟内存。
二、C面向对象
面向对象的特点
维护性、复用性、扩展性。
封装体现了维护性按照信息屏蔽的原则把对象的属性和操作结合在一起构成一个独立的对象。通过限制对属性和操作的访问权限可以将属性隐藏在对象内部对外提供一定的接口在对象之外只能通过接口对对象进行操作这样增加了对象的独立性外部的对象不能直接操作对象的属性只能使用对象提供的服务从而保证了数据的可靠性。
继承体现了复用性当定义了一个类后又需要定义一个新类但是这个类与原来的类相比只是增加或修改了部分属性和操作这时可以引用原来的类派生出新的类新类中只需要描述自己特有的属性和操作这样就大大的简化了对问题的描述提高了程序的复用性。
多态体现了扩展性多态就是一个接口多种实现当需要添加新的模块功能的时候不需要改变原来的功能只需要添加新的即可这样就实现了扩展性。
面向对象的优点
易于维护可读性比较高如果有改变的需求由于继承的存在维护也只是局部模块所以说维护起来是非常方便和较低成本的。
质量高可重用现有的在以前的项目的领域中一杯测试过的类使系统满足业务需求并具有较高的质量。
效率高在软件开发时根据设计的需要对现实事件的事务进行抽象产生类。这样结局问题的方法接近于日常生活和自然的思考方式必定会提高软件开发的效率和质量。
1、c语言是面向过程的结构化 语言易于调试和维护。
2、表现能力和处理能力极强可以直接访问内存的物理地址。
3、C语言实现了对硬件的编程操作也适合于引用软件的开发。
概述
封装可以使得代码模块化继承可以扩展已经存在的代码他们的目的是为了代码重用。而多态的目的是为了接口重用。
封装
封装是设计类的一个基本原理是将抽象得到的数据和行为相结合形成一个有机的整体也就是将数据与对数据进行的操作进行有机的结合从而形成类其中的数据和函数都是类的成员。
继承
如果B是继承了A那么就把这个B称为是A的子类把A称为B的父类。继承可以使子类具有父类的各种属性和方法和方法就不用再次编写相同的代码。子类继承父类的同时可以重新定义某些属性并重定义其中的一些方法也就是隐藏父类中原有的属性和方法使其获得于父类不同的功能。
单继承
单继承就是一个派生类继承一个基类。单继承的继承规则为所有继承下来的基类成员变量存放在派生类添加的成员变量之前也就是基类的成员变量的内存地址低于派生类的内存地址可以看做是将基类的内存空间进行了一次拷贝并且在拷贝的内存空间后面加上派生类自己的成员。
多继承
菱形继承
菱形继承存在的问题就是数据二义性相应的解决方案就是虚拟继承。多继承的继承规则是以单继承的方式按照父类声明的顺序继承每个父类可以看做是按照声明的顺序将每个父类的内存空间拷贝到一起并且在后面添加上派生类自己的成员。
虚拟继承
虚拟继承是解决C中多重继承问题的一种手段从不同途径继承来的同一基类会在子类中存在多份拷贝。这样会存在两个问题一个是对于存储空间的浪费还有就是数据的二义性。虚拟继承就是针对这两个问题出现的虚拟继承的底层实现原理与编译器相关一般通过虚基类和虚基表实现每个虚继承的子类都有一个虚基类指针和虚基表当虚拟继承的子类被当做父类继承时虚基类指针也会被继承。实际上vbptr指的是虚基类表指针这个指针指向虚基类表在虚基类表中记录了虚基类与本类的偏移地址通过偏移地址可以找到虚基类的成员虚拟继承和虚函数有着相同之处都是利用了虚指针和虚表虚基类表中存储的是虚基类相对于直接继承类的便宜而虚函数表中存储的时候虚函数的地址。
继承中的访问权限
父类的私有成员在子类中无论以什么方式继承都是不可见的这个的不可见指的是private成员仍然被继承到了子类中但是在语法上限制子类对象不管实在类内还是在类外都是无法访问它的。
子类以公有方式继承父类时父类的成员在子类中保持原有的属性。
子类以保护方式继承父类时父类中的公有成员在子类中成了保护成员。
子类以私有方式继承父类时父类中所有成员在子类中都是私有的。
使用class时默认的继承方式时私有的使用struct时则默认的继承方式是共有的。
还有一点就是友元是类级别的不存在继承的问题也就是子类不能继承父类的友元关系。
多态
多态可以简单的概括为“一个接口多种方法”字面意思是多种形态。多态分为静态多态和动态多态。
静态多态
静态多态也称作静态绑定或者是早绑定。地址的绑定是编译器在编译的时候完成的编译器根据函数实参的类型可以推断出要调用那个函数这里可能会进行隐式的类型转换如果有对应的函数就调用了否则编译报错。静态多态又分为函数重载和泛型编程。
函数重载
函数重载是在相同的作用域中只有函数的名称相同参数个数或参数类型不同。编译器根据函数不同的参数表对同名函数的名称修饰然后这些同名函数就成了不同的函数。这个在C语言中是不支持的因为c语言中对函数的名称修饰较为简单在VS2013编译器中c语言对函数名称修饰的处理只关注到了函数名对函数名的修饰只是简单的在函数名前添加_而c语言除了函数名还关注了函数的参数对函数名的修饰时候要加上参数通过对函数名称的修饰不同编译器调用函数时所找的符号就不同。
泛型编程
泛型编程指的是编写独立于特定类型的代码泛型编程在C中的主要是实现为函数模板和类模板。泛型编程的特性有如下几点
1、函数模板并不是真正的函数他只是C编译器生成具体的函数的一个模子。
2、函数模板本身并不生成函数实际生成的函数是替换函数模板的那个函数这种替换在编译期就绑定了。
3、函数模板不是只编译一份满足多重需要而是为每一种替换他的函数编译一份。
4、函数模板不允许自动类型转换。
5、函数模板不可以设置默认模板参数。
动态多态
C中的动态多态是基于虚函数的。对于相关的对象类型确定他们之间的一个共同的功能集然后在父类中把这些共同的功能声明为多个公共的虚函数接口。各个子类重写这些虚函数完成具体的功能。操作函数通过指向基类的引用或指针来操作这些对象对虚函数的调用会自动绑定到实际提供的子类对象上去。
虚函数
虚函数之所以叫做虚函数是因为他的推迟联编和动态联编一个类的虚函数的调用并不是在编译的时候确定的而是在运行的时候确定的虚函数通过基类的指针或者引用指向派生类对象实现多态。
纯虚函数
纯虚函数指的是在基类中声明的虚函数但是没有在基类中定义要求在任何派生类中都要定义自己实现方法。如果一个类中有纯虚函数则这个类被称为抽象类由于这个类的构建并不完成所以不能生成一个对象。继承了抽象类的派生类必须要将纯虚函数实现否则同样是抽象类不能生成对象。
虚函数表
在C中虚函数通话四通过虚函数表来实现的这个表中存放的是虚函数的地址他是属于类的不属于某个具体的对象在一个类中只有一个虚表所有对象共享同一份虚表。为了指定对象的虚表在对象构造的时候就在对象的内部包含了虚表指针_vfptr一般是放在头部。
关于虚函数表有两种情况是要分清楚的多继承和多重继承中的虚表是不一样的。
多继承指的是有一个子类继承了两个基类比如说有ABC三个类在A和B类中都有虚函数C类依次继承了A类和B类这时候C类中的虚表就有了A类和B类两个虚表并且C类中的虚表指针是以A类虚表地址为基础的如果想要获取到B类虚表的地址可以让指针向后偏移A类的大小或者给出一个B类的指针指向C类对象发生一个天然的转换需要注意的是在C类中的重写的虚函数会覆盖A类和B类中的同名虚函数如果C类中的虚函数在A类和B类中没有就添加到A类的虚函数表中但是A类指针不可以调用如果是只在A类或者B类中有的虚函数在C类中没有那么只能是拥有虚函数的父类和C类可以调用。
多重继承就是B类继承了A类C类继承了B类在B类中的重写的虚函数会在虚函数表中覆盖A类的同名虚函数并将B类新添加的虚函数放在B类虚函数表的末尾C类也是如此C类的虚表是从B类中继承的在C类中的重写的虚函数会在虚函数表中覆盖B类的同名虚函数并将C类新添加的虚函数放在C类虚函数表的末尾。
静态多态多态的比较
静态多态
优点
1、静态多态通过模板编程为C带来了泛型设计的概念,比如STL。
2、静态多态是在编译期完成的所以效率很高编译器可以对其进行优化。
缺点
由于模板是实现静态多态,所以模板的不足也是静态多态的劣势,比如调试困难、编译耗时、代码膨胀。
动态多态
优点
1、实现与接口分离可复用。
缺点
1、运行时绑定导致一定程度上的运行时开销。
2、编译器无法对虚函数进行优化。
3、笨重的类继承体系对接口的修改影响整个类层次。
不同点
本质不同
早晚绑定静态多态是在编译期决定的由模板实现完成而动态多态是在运行期间决定的由继承、虚函数实现。
接口方式不同
动态多态的接口是显式的以函数名为中心通过虚函数在运行期间实现静态多态的接口是隐式的以有效表达为中心通过模板在编译期间完成。
应用形式上
静多态是发散式的让相同的实现代码应用于不同的场合。
动多态是收敛式的让不同的实现代码应用于相同的场合。
思维方式上
静多态是泛型式编程风格它看重的是算法的普适性。
动多态是对象式编程风格它看重的是接口和实现的分离度。
相同点
够可以实现多态性静态多态/编译期多态动态多态/运行期多态。
都可以是使接口和实现分离一个是模板定义接口类型参数定义实现一个是基类定义接口继承类负责实现。
虚函数面试题
inliine函数可以实虚函数码
不可以因为inline函数没有地址无法将他存放到虚函数表中。
静态成员可以是虚函数吗
不能因为静态成员函数中没有this指针使用成员函数的嗲用用方式无法访问虚函数表所以静态成员函数无法放进虚函数表。
构造函数可以是虚函数吗
不可以因为对象中的虚函数指针是在对象构造的时候初始化的。
析构函数可以是虚函数吗什么场景下析构函数是虚函数
可以最好将析构函数设置为虚函数因为这样可以避免内存泄漏的问题如果一个父类的指针指向了子类的的对象如果子类对象中的虚函数没有写成多态的他只会调用父类的析构函数不会调用自己的析构函数但是他创建对象的时候调用了构造函数所以说就用子类的构造函数就应该该取调用他的析构函数这样才能保证所有的必须释放的资源都是放了才可以保证不会有内存泄漏。如果是多态的就会先去调用子类的析构函数然后再取调用父类的析构函数这样子类和父类的资源就都可以释放。
对象访问普通函数快还是虚函数快
如果是普通对象是一样快的如果是指针对象或者是引用对象调用普通函数更快一些因为构成了多态运行时调用虚函数要先到虚函数表中去查找。这样然后才拿到韩式的地址这样就不如直接可以拿到函数地址的普通函数快。
虚函数表时再什么阶段生成的他存放在哪里
虚函数时再编译阶段生成的他一般存放再代码段也就是常量区。
是否可以将类中的所有成员函数都声明称为虚函数为什么
虚函数是在程序运行的时候通过寻址操作才能确定真正要调用的的函数而普通的成员函数在编译的时候就已经确定了要调用的函数。这个两者的区别从效率上来说虚函数的效率要低于普通成员函数因为虚函数要先通过对象中的虚标指针拿到虚函数表的地址然后再从虚函数表中找到对应的函数地址最后根据函数地址去调用而普通成员函数直接就可以拿到地址进行调用所以没必要将所有的成员函数声明成虚函数。
虚函数表指针被编译器初始化的过程怎么理解的
当类中声明了虚函数是编译器会在类中生成一个虚函数表VS中存放在代码段虚函数表实际上就是一个存放虚函数指针的指针数组是由编译器自动生成并维护的。虚表是属于类的不属于某个具体的对象一个类中只需要有一个虚表即可。同一个类中的所有对象使用同一个虚表为了让每个包含虚表的类的对象都拥有一个虚表指针编译器在每个对象的头添加了一个指针用来指向虚表并且这个指针的值会自动被设置成指向类的虚表每一个virtaul函数的函数指针存放在虚表中如果是单继承先将父类的虚表添加到子类的虚表中然后子类再添加自己新增的虚函数指针但是在VS编译器中我们通常看不到新添加的虚函数指针是编译器故意将他们隐藏起来如果是多继承在子类中新添加的虚函数指针会存放在第一个继承父类的虚函数表中。
多态的分类
静态绑定的多态的是通过函数的重载来实现的。动态绑定的多态是通过虚函数实现的。
为什么要引入抽象类和纯虚函数
为了方便使用多态特性在很多情况下由基类生成对象是很不合理的纯虚函数在基类中是没有定义的要求在子类必须加以实现这种包含了纯虚函数的基类被称为抽象类不能被实例化如果子类没有实现纯虚函数那么它他也是一个抽象类。
虚函数和纯虚函数有什么区别
从基类的角度出发如果一个类中声明了虚函数这个函数是要在类中实现的它的作用是为了能让这个函数在他的子类中能被重写实现动态多态。纯虚函数只是一个接口一个函数声明并没有在声明他的类中实现。对于子类来说它可以不重写基类中的虚函数但是他必须要将基类中的纯虚函数实现。虚函数既继承接口的同时也继承了基类的实现纯虚函数关注的是接口的统一性实现完全由子类来完成。
什么是多态他有什么作用
多态就是一个接口多种实现多态是面向对象的三大特性之一。多态分为静态多态和动态多态。静态多态包含函数重载和泛型编程进程多态是程序调用函数编译器决定使用哪个可执行的代码块。静态多态是由继承机制以及虚函实现的通过指向派生类的基类指针或者引用访问派生类中同名重写成员函数。堕胎的作用就是把不同子类对象都当作父类来看可以屏蔽不同子类之间的差异从而写出通用的代码做出通用的编程以适应需求的不断变化。
三、虚函数和纯虚函数
概述
虚函数它虚就虚在所谓的“推迟联编”和“动态联编”上一个类虚函数的调用并不是在编译时刻确定的而是在运行的时候被确定。由于编写代码的时候并不能确定被调用的是基类函数还是那个派生类的函数所以被称为虚函数。
虚函数只能借助指针或引用来达到多态的效果。常用的方式是基类指针或引用指向子类的对象。当有多个子类的继承时可以统一用父类指针来表示各子类对象但事实上所指的对象具体是哪一个或者调用的函数是哪个子类中的函数要在运行的时候才知道这就实现了多态。
class parent
{public:vritual void fun(){cout parent::fun endl;}
};class child : public parent
{public:void fun(){cout child :: fun endl;}
};int main()
{parent *a new child;a-fun(); //这里的指针虽然是parent类型但是指向的是child的fun函数。构成了多态。return 0;
}语法
virtual void fun()0; //纯虚函数
virtual void fun(); //虚函数纯虚函数
纯虚函数是指在基类中声明的虚函数并没有在基类中定义要求在任何派生类中都要定义自己的实现方法。在类中有纯虚函数的类被称为抽象类由于他的构建并不完整所以不能用抽象类来生成对象。继承了抽象类的派生类必须要将纯虚函数实现否则同样是抽象类不能生成对象。
虚函数表
在C中虚汗是是通过虚函数表来实现的以下称为虚表在这张表中存放的是虚函数的地址它是属于类的不属于某个具体的对象一个类中只有一个虚表在同一个类中的所有对象都是用类中唯一这个虚表。为了指定对象的虚表在对象构造的时候就在对象内部包含了虚表指针。为此编译器在类中添加了一个*_vptr来指向虚表并且这个指针的值会自动被设置为指向该类的虚表。在C编译器中虚表指针在存放在每个对象的头四个字节并且虚函数表的末尾是以空指针结束。
关于虚函数表有两种情况是要分清楚的多继承和多重继承这两种继承中的虚表是不一样的。
多继承指的是有一个子类继承了两个基类比如说有ABC三个类在A和B类中都有虚函数C类依次继承了A类和B类这时候C类中的虚表就有了A类和B类两个虚表并且C类中的虚表指针是以A类虚表地址为基础的如果想要获取到B类虚表的地址可以让指针向后偏移A类的大小或者给出一个B类的指针指向C类对象发生一个天然的转换需要注意的是在C类中的重写的虚函数会覆盖A类和B类中的同名虚函数如果C类中的虚函数在A类和B类中没有就添加到A类的虚函数表中但是A类指针不可以调用如果是只在A类或者B类中有的虚函数在C类中没有那么只能是拥有虚函数的父类和C类可以调用。
多重继承就是B类继承了A类C类继承了B类在B类中的重写的虚函数会在虚函数表中覆盖A类的同名虚函数并将B类新添加的虚函数放在B类虚函数表的末尾C类也是如此C类的虚表是从B类中继承的在C类中的重写的虚函数会在虚函数表中覆盖B类的同名虚函数并将C类新添加的虚函数放在C类虚函数表的末尾。
虚函数面试题
inliine函数可以实虚函数码
不可以因为inline函数没有地址无法将他存放到虚函数表中。
静态成员可以是虚函数吗
不能因为静态成员函数中没有this指针使用成员函数的嗲用用方式无法访问虚函数表所以静态成员函数无法放进虚函数表。
构造函数可以是虚函数吗
不可以因为对象中的虚函数指针是在对象构造的时候初始化的。
析构函数可以是虚函数吗什么场景下析构函数是虚函数
可以最好将析构函数设置为虚函数因为这样可以避免内存泄漏的问题如果一个父类的指针指向了子类的的对象如果子类对象中的虚函数没有写成多态的他只会调用父类的析构函数不会调用自己的析构函数但是他创建对象的时候调用了构造函数所以说就用子类的构造函数就应该该取调用他的析构函数这样才能保证所有的必须释放的资源都是放了才可以保证不会有内存泄漏。如果是多态的就会先去调用子类的析构函数然后再取调用父类的析构函数这样子类和父类的资源就都可以释放。
对象访问普通函数快还是虚函数快
如果是普通对象是一样快的如果是指针对象或者是引用对象调用普通函数更快一些因为构成了多态运行时调用虚函数要先到虚函数表中去查找。这样然后才拿到韩式的地址这样就不如直接可以拿到函数地址的普通函数快。
虚函数表时再什么阶段生成的他存放在哪里
虚函数时再编译阶段生成的他一般存放再代码段也就是常量区。
是否可以将类中的所有成员函数都声明称为虚函数为什么
虚函数是在程序运行的时候通过寻址操作才能确定真正要调用的的函数而普通的成员函数在编译的时候就已经确定了要调用的函数。这个两者的区别从效率上来说虚函数的效率要低于普通成员函数因为虚函数要先通过对象中的虚标指针拿到虚函数表的地址然后再从虚函数表中找到对应的函数地址最后根据函数地址去调用而普通成员函数直接就可以拿到地址进行调用所以没必要将所有的成员函数声明成虚函数。
虚函数表指针被编译器初始化的过程怎么理解的
当类中声明了虚函数是编译器会在类中生成一个虚函数表VS中存放在代码段虚函数表实际上就是一个存放虚函数指针的指针数组是由编译器自动生成并维护的。虚表是属于类的不属于某个具体的对象一个类中只需要有一个虚表即可。同一个类中的所有对象使用同一个虚表为了让每个包含虚表的类的对象都拥有一个虚表指针编译器在每个对象的头添加了一个指针用来指向虚表并且这个指针的值会自动被设置成指向类的虚表每一个virtaul函数的函数指针存放在虚表中如果是单继承先将父类的虚表添加到子类的虚表中然后子类再添加自己新增的虚函数指针但是在VS编译器中我们通常看不到新添加的虚函数指针是编译器故意将他们隐藏起来如果是多继承在子类中新添加的虚函数指针会存放在第一个继承父类的虚函数表中。
多态的分类
静态绑定的多态的是通过函数的重载来实现的。动态绑定的多态是通过虚函数实现的。
为什么要引入抽象类和纯虚函数
为了方便使用多态特性在很多情况下由基类生成对象是很不合理的纯虚函数在基类中是没有定义的要求在子类必须加以实现这种包含了纯虚函数的基类被称为抽象类不能被实例化如果子类没有实现纯虚函数那么它他也是一个抽象类。
虚函数和纯虚函数有什么区别
从基类的角度出发如果一个类中声明了虚函数这个函数是要在类中实现的它的作用是为了能让这个函数在他的子类中能被重写实现动态多态。纯虚函数只是一个接口一个函数声明并没有在声明他的类中实现。对于子类来说它可以不重写基类中的虚函数但是他必须要将基类中的纯虚函数实现。虚函数既继承接口的同时也继承了基类的实现纯虚函数关注的是接口的统一性实现完全由子类来完成。
什么是多态他有什么作用
多态就是一个接口多种实现多态是面向对象的三大特性之一。多态分为静态多态和动态多态。静态多态包含函数重载和泛型编程进程多态是程序调用函数编译器决定使用哪个可执行的代码块。静态多态是由继承机制以及虚函实现的通过指向派生类的基类指针或者引用访问派生类中同名重写成员函数。堕胎的作用就是把不同子类对象都当作父类来看可以屏蔽不同子类之间的差异从而写出通用的代码做出通用的编程以适应需求的不断变化。
四、引用和指针的区别
指针
对于一个类型TT* 就是一个指向T的指针类型也就是一个T*类型的变量能够保存一个T对象的地址而类型T可以添加一些限定词如const、volatile等等。 volatile提醒编译器它后面所定义的变量随时有可能改变。精确地说就是遇到这个关键字声明的变量编译器对访问该变量的代码就不再优化从而可以提供对特殊地址的稳定访问如果不使用volatile则编译器对所声明的语句进行优化。 1中断服务程序中修改的供其他程序检测的变量需要加volatile 2多任务环境下各任务间共享的标志应该加volatile 3多存储器映射的硬件寄存器通常也要加volatile因为每次对它的读写都可能有不同意义。 需要注意的是频繁地使用volatile很可能会增加代码尺寸和降低代码性能因此要合理地使用volatile。 引用
引用就是一个对象的别名主要用于函数参数和返回值类型类型变量名 被引用的对象。
不同点
1、引用是某块内存的别名而指针指向的是一块内存他的内容是所指内存的地址。
2、引用在创建时必须被初始化但是指针可以为空在C语言中NULL在C中是nullptr。所以指针在使用的时候必须要判空引用就没有必要。
3、引用不可以改变指向一旦初始化了就不能改变。指针可以改变自己的指向可以指向其他对象。
4、对于引用来说const int a 和 int const a没有区别因为都表示指向的对象是常量。对于指针来说const int *p 说明p是指向常量的指针 int * const p 说明p本身就是一个常量。
5、引用的大小是指向对象的大小而指针在32位机上是四字节在64位机上是8字节是指针本身的大小。
6、对引用操作就是对引用指向的对象进行操作但是对指针操作表示的是地址的变化向后移动一个指针的大小。
7、指针传递和引用传递
指针传递传递的是地址在函数中定义了一个局部的指针变量存放的是实参的地址消耗了内存可以对地址进行加减操作指向另一个变量由于传递的是地址所以不需要返回值因为实际修改的就是实参的值。
引用传递同样是地址但是不会在函数中消耗内存直接对地址进行使用对函数中的引用变量的加减操作直接影响外部的实参并且不能指向另一个变量。在实际使用中传递引用的时候如果不希望实参被改变通常要用const将其修饰。
五、深拷贝和浅拷贝
浅拷贝指的是将原始对象中的数据型字段拷贝到新对象中将引用型对象的引用赋值到新对象中去不把引用的对象复制进去所以原始对象和新对象引用同一对象新对象中的引用型字段发生变化会导致原始对象中对应的字段发生变化。
深拷贝是在引用方面不同深拷贝就是重新创建一个新的和原始字段内容相同的字段所以两者的引用是不同的。其中一个对象发生变化并不会影响另一个对象。
编译系统会在我们自己没有定义拷贝构造的时候调用默认的拷贝构造函数进行浅拷贝也就是两个对象使用同一份资源。当两个对象调用析构函数的时候就会析构两次导致内存泄漏。所以对含有指针成员的对象或类中存在资源的对象进行拷贝的时候必须要自己定义拷贝构造函数实现深拷贝避免内存泄漏。
六、常见关键字的作用
static
static有静态局部变量、静态全局变量和静态方法三种使用方法他们的共同点就是在本文件中声明的静态变量和静态方法是不能被其他文件所使用的和对应的extern关键字extern关键字声明的全局变量和函数在整个工程中都是可以被使用的。
全局变量
有static声明的全局变量只能在函数体外部被定义并且只能在本文件中有效这点就是区别于普通的全局变量普通的全局变量在其他的文件中也是可见的。在函数体重可以定义同名的局部变量这时会隐藏这个静态的如果要使用静态的全局变量需要在变量名前添加::作用域运算符。
局部变量
static局部变量同样只能在本文件中使用静态局部变量的生命周期不随着函数的结束而结束只能在第一调用函数的时候回他进行初始化之后调用就会跳过初始化他会在函数结束之后在内存中保存当前的结果而不会像普通的局部变量在清栈的时候销毁在内存中他区别与局部变量的是局部变量每次调用函数时分配的内存空间可能是不一样的但是静态局部变量具有全局唯一性的特点每次调用使用的时候用的都是同一块内存空间但是这也造成了一个不可重入的问题。现在有两个进程A、B都要去调用这个函数fun()如果是A先调用函数fun在运行函数的时候突然失去了运行权但是已经将局部变量修改成了自己要试用的值由于使用的是同一块内存空间进程B调用函数的时候也将局部变量修改成了自己要使用的值当进程A需要继续执行的时候由于这块内存空间中的值已经被修改了所有进程A就得不到自己想要的结果。
方法
static数据成员和成员函数
在C中继承了C语言中的static这个关键字并且在类中给了第三种定义方法表示只属于一类而不是属于类的某个对象的变量和函数。这个和普通的成员最大的区别就是在类中是唯一的并且在内存中只有一份普通成员函数调用的时候需要传入this指针但是静态成员函数调用的时候是没有this指针的只能在调用的时候使用类名加作用域来调用。在设计多线程操作的时候有POSIX库下的线程函数要求是全局的所以普通的成员函数是无法直接作为线程函数的但是静态的成员函数是可以做线程函数的。
static函数和普通函数
普通函数的定义和声明默认是extern的在同一个工程中的其他文件中是可见的如果在另一个文件中定义了相同的函数就会穿线重定义错误当然这个重定义和继承中的 重定义是不一样的这里的重定义指定的命名冲突。静态函数在内存中只有一份但是普通的函数在每个被调用中都会维护一份拷贝。
extern
extern置于变量或函数前用于标示变量或函数的定制在别的文件中提示编译器遇到这个变量或函数要在其他的模块中查找。
extern “C”
如果是extern“C” void fun(int a, int b)这样是高数编译器在编译fun这个函数的时候要按照C的规则去编译而不是按照C的这一点主要是与C支持重载C语言不支持重载和函数被C编译器编译后在苦衷的名字与C语言的不同有关。
当extern不与“C”在一起修饰变量或者函数时比如extern int a他的作用就是声明函数或者全局变量的作用范围和关键字其生命的函数和变量可以在本工程中的所有文件中使用。需要注意的是他只是一个声明并不是定义。
const
使用const修饰类的成员变量的时候必须要在初始化列表进行初始化并且引用类型的成员变量和没有默认默认构造函数的对象成员也必须要在初始化列表进行初始化如果有继承的关系如果父类没有默认的构造函数也必须要在初始化列表进行初始化初始化列表对数据成员的初始化顺序时按照数据成员的声明顺序严格执行的。
const修饰成员函数的时候一般是放在成员函数的最后面修饰的类的成员函数中隐藏的this指针代表不可以通过this指针修改类的数据成员这个使用方法也可以与普通的相同的成员函数构成重载。
关于const还有一个问题就是传参和赋值的问题一般来说使用const修饰的变量是安全的没有使用const修饰的变量是不安全的在传参的时候可以让非const修饰的变量传给const修饰的但是const修饰的变量不可以传给非const修饰的形参这就相当于将安全的变量交给了不安全的变量。
volatile
volatile一般用来修饰变量他的存在是因为我们的程序在进行编译的时候编译器会进行一系列的优化比如说某个变量被修饰为const编译器就会认为这个值是只读的就会在寄存器中保存这个变量的值每次需要的时候直接从寄存器中读取但是有的时候会在不经意间修改了这个变量的值那么编译器是并不知道的还是从寄存器中进行读取这样就会造成结果不匹配。但是如果使用volatile声明后就是相当与告诉编译器这个变量随时会给变需要每次都要从内存中读取不需要优化从而避免了这个问题volatile的应用场景最多的是多线程对
define、const、inline区别
define作用域程序的预处理节点而预处理主要的工作是宏替换、去注释以及条件编译而define起作用的地方就在宏替换阶段只是单纯的将宏替换为代码。但是define只是单纯的代码替换不会进行类型的检查很容易出错。在C中建议使用const、枚举定义常量这样就会有类型检查。于是C中有提供了一个inline关键字可以实现和define相同的功能并且支持类型检查和调试一般生命在函数的定义前面但是inline只是对编译器的一种建议一般建议代码为3-5航左右并且没有复杂的逻辑结构例如循环、递归之类的。
七、malloc/free和new/delete的区别
1、malloc是从堆上开辟空间而new是从自由存储区开辟空间。自由存储区是C抽象出来的概念不仅可以是堆还可以是静态存储区。
2、malloc是函数而new是关键字。
3、malloc对开辟的空间大小需要严格的指定而new只需要对象名。
4、malloc开辟的空间既可以给单个对象使用也可以给数组使用释放的方式都是free()而new开辟对象数组需要使用new[size]释放是使用delete[]。
5、malloc成功的返回值是void*需要用户进行强转申请空间失败会返回NULL所以在使用的时候需要进行判空处理new成功返回的是对象指针不需要强转失败抛出异常但是为了最大程度的兼容CC的new也支持失败返回NULL但是一般不使用。
6、new不仅负责开辟空间还会去调用对象的构造函数和析构函数。
7、new申请空间的效率要低于malloc因为new的底层是通过malloc实现的。
八、类中的成员函数占空间吗怎么调用
类中的普通成员函数和静态成员函数是不占用类的内存的只有在类中函数有虚函数的时候才会在类中添加一个虚函数指针增加一个指针的大小。类中的成员函数实际上与普通的全局函数一眼只不过是在编译的时候在成员函数中国添加了一个指向当前对象的this指针成员函数的地址是全局已知的所以对象的内存空间中是没有必要去保存成员函数的地址的。在编译的时候就已经绑定了类的属性值得是类中的数据成员他们是实例化一个对象的时候就为数据成员分配了内存但是成员函数是所有对象多公有的。
但是空类的大小是1个字节这是为了保证两个不同对象的地址不同。类的实例化是在内存中分配一块地址每个势力在内存中欧拥有独一无二的地址。同样的空类也会实例化所以编译器会给类隐含的添加一个字节这样空类实例化后就有了独一无二的地址了。在一个空类中在第一次实例化对象的时候就创建了默认的成员函数并且这个成员函数是public和inline的。
九、NULL和nullptr的区别
传统意义上来说c把NULL、0视为同一种东西有些编译器将NULL定义为 void*0有些将其定义为0
c不允许直接将void隐式的转化为其他类型但是如果NULL被定义为 void*0当编译char *p NULL,NULL只好被定义为0。
还有void funcintvoid funcchar*
如果NULL被定义为0funcNULL会去调用void funcint这是不合理的
所以引入nullptr专门用来区分0、NULL。nullptr的类型为nullptr_t能够隐式的转换为任何指针。所以用空指针就尽可能的使用nullptr。十、智能指针
什么是智能指针
智能指针最主要的作用就是管理一个指针因为有可能申请的空间在函数结束的时候没有及时的释放从而造成的了内存泄漏。使用智能指针是要是针对这个问题因为只能指针是一个类在他生命周期结束的时候回去调用析构函数进行资源的释放不需要进行手动的释放资源。智能指针一共有auto_ptr、unique_ptr、shard_ptr、week_ptr四种。
auto_ptr
是C98提出来的智能指针它采用的是所有权模式。就是将智能指针A赋值给智能指针B就是将A的所有权交给了B如果再想访问A就会出错auto_ptr的缺点就是存在潜在的内存崩溃问题。
unique_ptr
他解决了auto_ptr的问题从名字可以知道他是独有的智能指针也就是说他不能进行赋值和拷贝操作在unique_ptr中将拷贝构造函数和赋值运算符重载私有并且将其删除。
shared_ptr
shared_ptr实现了共享的概念多个智能指针可以指向同一份资源。他的原理是多个智能指针共同维护一份引用计数当有第二个进行赋值和拷贝构造的时候回将引用计数1每当一个智能指针使用完需要调用析构函数的时候就会检查是不是最后一个使用资源的如果不是不进行释放否则要进行资源释放。但是在使用的时候会出现这么一个情况就是相互引用产生的死锁问题那么这两个智能指针的引用计数将永远不会下降为0也就是资源不会得到释放。这时就需要week_ptr了。
week_ptr
week_ptr是一种不控制对象生命周期的智能指针他指向一个sheard_ptr管理的对象进行该对象的内存管理的是那个强引用的shared_ptr。week_ptr只是提供了对管理对象的一各访问的手段他只能从一个shared_ptr或另一个weak_ptr对象构造他的构造函数和析构函数是不会引起引用计数的改变。weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用不会增加对象的引用计数和shared_ptr之间可以相互转化shared_ptr可以直接赋值给它它可以通过调用lock函数来获得shared_ptr。week_ptr只能是协助shared_ptr他不能直接指向对象。
十一、默认构造函数
默认构造函数我认为是在调用时不需要显式地传入实参的构造函数。如果定义一个对象时没有使用初始化式编译器就会使用默认的构造函数。编译器生成默认构造函数的情况用一句话可以进行概括就是唯有默认构造函数被编译器需要的时候编译器才会生成默认的构造函数。关于这个被编译器需要分为几种情况当该类的类对象数据成员有默认构造函数时当类的基类有默认的构造函数时、当该类的基类为虚基类时、当该类有虚函数时这四种情况。
默认构造函数中有这么几点需要注意
1、不能让无参的默认构造函数和带缺省的默认构造函数同时存在这样就会让编译器产生二义性从而生成编译错误。
2、在使用无参默认构造函数的时候不能再对象名后面加括号否则会产生警告让编译器误认为是要声明一个函数但是又没有找到该函数的定义所以就产生了警告。
十二、前置和后置区别
1、从使用的角度来说c是先使用后自增c是先自增后使用
2、从系统的角度来说c表示取c的地址把他放入寄存器中然后增加内存中的c使用寄存器中的值对于c表示取c的地址自增后把他放入寄存器中使用很显然c的效率要比c高因为c会生成一个临时变量。
3、如果不需要返回自增后之前的值那么c和c的效果是一样的但是要优先使用c效率高。
十三、lambda表达式
[函数对象参数](操作符重载函数参数)mutable或exception声明 -返回值类型{函数体}函数对象参数
空没有使用任何的函数对象参数。函数体内可以使用lambda所在作用域范围内所有可见的局部变量并且是值传递。函数体内可以使用lambda所在作用域范围内所有可见的局部变量并且是引用传递。
a 将a按值传递但是a的默认是const的可以添加mutable修饰后变为普通的。
a将a按引用传递。
ab将a按值传递b按引用传递。
ab除了a和b其他参数均按值传递。
ab除了a和b其他参数均按引用传递。
this函数体重可以使用lambda所在类中的所有成员变量操作符重载函数参数
表示重载的()操作符的参数没有参数的时候这个可以省略。
mutable或exception声明
按值传递函数对象参数时加上mutable修饰可以修改值传递进来的拷贝。exception声明用于指定函数抛出的异常如抛出整形的异常可以使用throw进行捕获。
-返回值类型
标识函数返回值的类型当返回值为void或者函数同种只有一处return的地方这部分可以省略。
{函数体}
表示函数的实现这部分不可以省略但是函数体可以为空。
十四、什么是右值
左值和右值是编译器和程序中经常出现的词汇在C中被广泛认同的说法就是可以取地址的、有名字的就是左值没有地址的不能取取名字的就是右值。
在C11中右值由纯右值和将亡值组成。
纯右值用于辨识临时变量和一个不跟对象有关联的值比如说非引用返回的函数返回值运算表达式、不跟对象关联的字面量值true、false、常量等、类型转换函数的返回值lambda表达式。
将亡值是C11新增的跟右值引用相关的表达式这样表达式通常是将要被移动的对象比如说返回右值引用T的函数的返回值move库函数的返回值转换为T的类型转换函数的返回值。
除了纯右值和将亡值剩余的所有值都是左值。
十五、右值引用
右值引用:
C中左值通常指可以取地址有名字的值就是左值而不能取地址没有名字的就是右值。而在指C11中右值是由两个概念构成将亡值和纯右值。纯右值是用于识别临时变量和一些不跟对象关联的值比如13产生的临时变量值2、true等而将亡值通常是指具有转移语义的对象比如返回右值引用T的函数返回值等。
C11中右值引用就是对一个右值进行引用的类型。由于右值通常不具有名字所以我们一般只能通过右值表达式获得其引用比如T aReturnRvale();
假设ReturnRvalue()函数返回一个右值那么上述语句声明了一个名为a的右值引用其值等于ReturnRvalue函数返回的临时变量的值。基于右值引用可以实现转移语义和完美转发新特性。
十六、 说一说c中四种cast转换
C中四种类型转换是static_cast, dynamic_cast, const_cast, reinterpret_cast
1、const_cast
用于将const变量转为非const
2、static_cast
用于各种隐式转换比如非const转constvoid*转指针等, static_cast能用于多态向上转化如果向下转能成功但是不安全结果未知
3、dynamic_cast
用于动态类型转换。只能用于含有虚函数的类用于类层次间的向上和向下转化。只能转指针或引用。向下转化时如果是非法的对于指针返回NULL对于引用抛异常。要深入了解内部转换的原理。
向上转换指的是子类向基类的转换
向下转换指的是基类向子类的转换
它通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否相同来判断是否能够进行向下转换。
4、reinterpret_cast
几乎什么都可以转比如将int转指针可能会出问题尽量少用
5、为什么不使用C的强制转换
C的强制转换表面上看起来功能强大什么都能转但是转化不够明确不能进行错误检查容易出错。
十七、数组和指针的区别
1、指针中保存的是数据的地址而数组中保存的是数据。
2、指针是间接访问数据要访问一个数据要先获得指针的内容然后通过这个地址提取出数据而数组是直接访问数据。
3、指针通常用于动态的数据结构链表、链式二叉树等数组通常用语固定数目并且数据类型相同的数据结构顺序表等。
4、指针通过malloc或new申请内存并且使用完要进行释放数组则是隐式的分配和删除。
十八、函数指针与指针函数
十九、请你来说一下一个C源文件从文本到可执行文件经历的过程
对于C源文件从文本到可执行文件一般需要四个过程
预处理阶段对源代码文件中文件包含关系头文件、预编译语句宏定义进行分析和替换生成预编译文件。
编译阶段将经过预处理后的预编译文件转换成特定汇编代码生成汇编文件后缀为.s
汇编阶段将编译阶段生成的汇编文件转化成机器码生成可重定位目标文件.o
链接阶段将多个目标文件及所需要的库连接成最终的可执行目标文件.exe
二十、内存泄漏
内存泄漏(memory leak)是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。内存泄漏并非指内存在物理上的消失而是应用程序分配某段内存后由于设计错误失去了对该段内存的控制因而造成了内存的浪费。
内存泄漏的分类
1、堆内存泄漏 Heap leak。对内存指的是程序运行中根据需要分配通过malloc,realloc new等从堆中分配的一块内存再是完成后必须通过调用对应的 free或者delete 删掉。如果程序的设计的错误导致这部分内存没有被释放那么此后这块内存将不会被使用就会产生Heap Leak.
2、系统资源泄露Resource Leak。主要指程序使用系统分配的资源比如 Bitmap,handle ,SOCKET等没有使用相应的函数释放掉导致系统资源的浪费严重可导致系统效能降低系统运行不稳定。
3、没有将基类的析构函数定义为虚函数。当基类指针指向子类对象时如果基类的析构函数不是virtual那么子类的析构函数将不会被调用子类的资源没有正确是释放因此造成内存泄露。
二十一、C对象模型
★★数据结构★★
一、STL总结
什么是STL
STL是一套高效的C程序库采用泛型编程的思想对常见的数据结构和算法进程封装里面处处体现着泛型编程的设计思想以及设计模式现在已经被集成到了C标准库中。STL里面包含了容器、适配器、空间配置器、迭代器、仿函数和算法。
六大组件
容器就是各种数据结构根据底层的实现由分为序列式容器和关联式容器。
适配器是一种用来修饰容器或者仿函数或迭代器接口的东西。比如queue和stack。
空间配置器负责空间配置与管理。从实现角度看配置器是一个实现了动态空间配置、空间管理、空间释放额class template。
迭代器扮演容器与算法之间的胶合剂是所谓的“泛型指针”。
算法各种常见算法如sortsearchcopyerase等。
仿函数行为类函数可作为算法的某种策略从实现角度看仿函数是一种重载了operator()的class或class template。一般函数指针可视为狭义的仿函数。
他们之间的关系空间配置器给容器分配存储空间算法通过迭代器获取容器中的内容仿函数可以协助算法完成各种操作配接器用来套接适配仿函数
容器
其中容器分为序列容器和关联式容器两大类序列容器包括静态数组array、动态数组vector、动态二维数组deque、带头结点的循环单链表forward_list、带头结点的双向循环链表list、字符串string。关联式容器根据地层的实现红黑树实现和哈希表实现两大类关联式容器中的两大类主要区别于底层的实现红黑树和哈希表
红黑树是一种二叉搜索树在每个节点上都增加了一个存储位表示结点的颜色可以红色或者是黑色通过对任何一条从根到叶子结点的路径上各个节点的颜色限制确保没有一条路径会比其他路径长出2倍所以是接近平衡的是比较稳定的二叉搜索树由于二叉搜索树的任意根节点总是大于它左子树的所有节点小于他的右子树的所有节点所以在查找的时候可以采用类似于二分查找的思想快速找到某个节点红黑树是一个平衡二叉树他的查找时间复杂度也是logN。
哈希表是根据关键码值直接进行访问的数据结构。通过关键码值可以直接映射到哈希表中的一个位置来访问对应的值以加快查找的速度查找的时间复杂度是O(1)。哈希表主要解决的是哈希函数和哈希冲突哈希函数也叫散列函数要根据不同的输入值得到一个固定长度的消息摘要。理想的哈希函数要对不同的输入产生不同的不同的输出结果同时还要满足同一性和雪崩效应。哈希冲突就是不同的关键码值通过哈希函数计算出相同的哈希地址。
解决哈希冲突的常见方法有闭散列和开散列两种闭散列采用的是线性探测法当发生哈希冲突时如果哈希表没有被装满就说明还可以将关键码值存放到下一个空位置然后从冲突位置一次向后探测直到空位置为止闭散列可以缓解哈希冲突但是不能彻底解决。开散列使用的是拉链法先将关键码通过哈希函数计算得到相应的哈希地址然后将相同的哈希地址的关键码放在同一个子集合中这个子集合通常称之为桶每个桶中的元素通过单链表的方式连接起来然后将各个链表的头结点存放在哈希表中。
但是对于哈希表来说通的个数是固定如果某个桶中的元素超过了8个就要将这个桶中的单链表转换为红黑树如果桶中的元素小于6个的时候要将红黑树结构再次转换为单链表。这个转换是由于桶中的元素是由链表保存的链表的查找时间复杂度是O(N)而红黑树的查找时间复杂度是logN但是当链表中的长度很小的时候查找也是很快的当链表不断变长了他的查找性能就会降低需要转换成红黑树。一开始不将桶的结构初始化为树是因为一个红黑树的节点占用的空间是单链表节点的二倍为了时间和空间的权衡只有当链表长度到8才进行单链表向红黑树的转换。但一个哈希表的离散性很好的情况下将单链表转换为红黑树的概率很小因为数据均匀分布在每个哈希桶中几乎不会有哈希桶中的链表长度达到8理想情况下哈希表中的所有哈希桶中节点分布频率会遵循泊松分布长度为8的概率是6*10^-8几乎是不可能的。
hash和红黑都是性能非常高的两个数据结构但是他们还是有区别的hash的查找速度比红黑树快并且查找速度基本上是和数据量无关的属于常数级别但是红黑树的查找速度是logN的但是hash还有hash函数并且它的构造速度也是比较慢的并且还需要实现分配足够的内存存储散列表并且hash是无序的。红黑树所需要的内存较小只需要为节点分配内存并且红黑树中的节点是有序它的查找时间复杂度是LogN但是不能说就比常数大。基于这两个数据结构各自的特点和性能STL将关联式容器分成了基于红黑树的map、set、multimap、multiset和基于hash的unordered_map、unordered_map、unordered_set、unordered_multimap、unordered_multiset。
vector
vector是线性容器他的元素严格按照线性序列排序和动态数组很相识他和数组一样所有的元素存储在一块连续的存储空间中这也意味着我们不仅可以使用迭代器访问元素还可以使用指针偏移的方式访问和常规数组不一样的是vector能够自动存储元素可以自动增长和缩小存储空间。和数组相比虽然vector在在自动处理容量的大小时会消耗更多的内存但是容器可以提供和数组一样的性能而且可以很好的调整存储空间的大小。相比其他的序列容器能更有效地访问容器中的元素和在末尾添加和删除元素在其他位置添加和删除元素就不如其他序列容器了并且在迭代器当面也不如list支持的好。
vector的迭代器无论在迭代器位置进行增加元素还是删除元素都会导致所有的迭代器失效因为vector中删除和添加元素后可能会改变容器的大小所以要更新所有的迭代器关于vector的空间这里需要注意的是size和capacity这两个成员函数的区别size指的是当前容器中拥有元素的个数而capacity指的是当前容器可以存放的元素个数。vector在分配空间这块他会分配一些额外的空间来适应可能的增长。不同的库采用的不同的策略权衡空间的使用和重新分配在vs中PJ版本的STL是以1.5倍的方式进行扩容的在gcc中的SGI版本的STL是按2倍的方式进行扩容的。
list
list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以向前向后双向迭代。list的地层是一个双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。他与forward_list非常相似最主要的区别就是forward_list是单链表只能向后迭代而list是双向链表可以向前迭代也可以向后迭代。与其他容器相比较list和forward_list最大的缺陷就是不支持在任意位置的随机访问比如要访问list的第6个元素必须从头部或者尾部迭代到该位置这段位置上的迭代需要线性的时间开销list还需要开辟一些额外的空间以保存每个节点相关联的信息。
list中也存在迭代器失效的问题因为list的底层结构是双向循环链表所以在list中插入时不会导致list的迭代器失效只有在删除的时候才会导致迭代器失效但是失效的仅是被删除节点的迭代器其他的迭代器并不会受到影响。
vector和list的区别
底层结构
vector是动态的顺序表在内存中是一段连续的空间list使用的是带头结点的双向循环链表。
随机访问
vector支持随机访问访问某个元素的时间复杂度是O(1),list不支持随机访问访问某个元素的时间复杂度是O(n)
插入和删除
vector在任意位置的插入和删除的效率较低需要搬移元素时间复杂度为O(N)插入的时候还有可能会增容增容操作中有开辟新空间、拷贝元素、释放旧空间导致效率更低。list在任意位置插入和删除效率比较高不需要搬移元素只需要更改上下两个节点的指针指向时间复杂度是O(1)。
空间利用率
vector的底层为一段连续的空间不容易造成内存碎片空间利用率高缓存利用率高。list底层节点动态开辟容易造成内存碎片空间利用率低缓存利用率低。
迭代器
vector使用的是原生态的指针list是将原生态的指针进行了封装。vector在插入元素是要给所有的迭代器重新赋值因为插入元素有可能会导致扩容致使原来的迭代器会失效并且删除元素的时候也会对迭代器进行重新赋值同样也会使原来的迭代器失效。对弈list来说他的底层是双向循环链表插入元素时并不会导致迭代器失效删除元素是只会导致当前的迭代器失效其他的迭代器并不受影响。
使用场景
vector适用于需要高效存储需要随机访问并且不关心插入和删除的效率。list适用于大量的插入和删除操作不需要随机访问也不关心存储的场景。
set
set是按照一定次序进行存储的容器。set中元素只有一个value并且每个value必须是唯一的set中的元素不能再容器中进行修改元素总是const的但是可以容容器中对他们进行删除或者插入。并且元素总是按照其内部的比较对象所指是的特定的严格弱排序标准进行排序的set访问元素的速度要比unordered_set慢但是它允许直接迭代并且是有序的set的底层实现是红黑树。他与map/multimap不同的是set中只存放的value但是他的底层存放的是由构成的键值对由于set中不允许有重复的元素所以可以使用set去重
map
map是关联式容器他按照特定的次序来存储由建值key和值value组合而成的元素。在map中建值key通常用于排序和唯一标识元素而值value中存储的是与建值key相关联的内容。建值key和值value的类型可能不同并且在map中key与value通过成员类型value_type绑定在一起。在map中元素总是按照建值key进行比较排序并且他访问某个元素时通常要比unordered_map慢但是map中的元素直接进行迭代是有序的。他的底层实现是红黑树结构。map与multimap唯一的不同就是map中的key值是唯一的但是multimap中的key是可以重复的。set于multiset的区别就是multiset中的元素是可以重复的。
list、set、map的区别
从结构上来说
list和set是存储的单列数据的集合map中存储的是键值对这样的双列数据的集合。list的底层结构是双向循环列表set和map的底层结构是红黑树。
从数据上来说
list中存储的数据是有顺序的并且是允许有重复的查找的时间复杂度是O(N)每个节点只有一个值valuemap中的存储的数据是无序的他的键值是不允许重复的但是他的值是允许重复的并且他的键值是有序的查找时间复杂度是logN每个节点是由键值key值value构成的键值对set中存储的数据是有序的不允许重复查找时间复杂度是logN每个节点是值value但是他的底层节点是value,value的键值对。
STL面试题
一、STL常用的容器有哪些以及各自的特点是什么?
1.vector:底层数据结构为数组 支持快速随机访问。
2.list:底层数据结构为双向链表支持快速增删。
3.stack:底层一般用顺序表和链表实现封闭头部即可不用vector的原因应该是容量大小有限制扩容耗时
4.queue:底层一般用顺序表和链表实现封闭头部即可不用vector的原因应该是容量大小有限制扩容耗时stack和queue其实是适配器,而不叫容器因为是对容器的再封装
5.set:底层数据结构为红黑树有序不重复。
6.multiset:底层数据结构为红黑树有序可重复。
7.map:底层数据结构为红黑树有序不重复。
8.multimap:底层数据结构为红黑树有序可重复。
9.hash_set:底层数据结构为hash表无序不重复。
10.hash_multiset:底层数据结构为hash表无序可重复 。
11.hash_map :底层数据结构为hash表无序不重复。
12.hash_multimap:底层数据结构为hash表无序可重复。
二、什么情况下用vector什么情况下用list。
vector可以随机存储元素即可以通过公式直接计算出元素地址而不需要挨个查找但在非尾部插入删除数据时效率很低适合对象简单对象数量变化不大随机访问频繁。
list不支持随机存储适用于对象大对象数量变化频繁插入和删除频繁。
三、什么时候需要用hash_map什么时候需要用map?
总体来说hash_map 查找速度会比map快而且查找速度基本和数据数据量大小属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小hash还有hash函数的耗时明白了吧如果你考虑效率特别是在元素达到一定数量级时考虑考虑hash_map。但若你对内存使用特别严格希望程序尽可能少消耗内存那么一定要小心hash_map可能会让你陷入尴尬特别是当你的hash_map对象特别多时你就更无法控制了而且hash_map的构造速度较慢。
四、请你来说一说STL迭代器删除元素
这个主要考察的是迭代器失效的问题。1.对于序列容器vector,deque来说使用erase(itertor)后后边的每个元素的迭代器都会失效但是后边每个元素都会往前移动一个位置但是erase会返回下一个有效的迭代器2.对于关联容器map set来说使用了erase(iterator)后当前元素的迭代器失效但是其结构是红黑树删除当前元素的不会影响到下一个元素的迭代器所以在调用erase之前记录下一个元素的迭代器即可。3.对于list来说它使用了不连续分配的内存并且它的erase方法也会返回下一个有效的iterator因此上面两种正确的方法都可以使用。
五、请你来说一下STL中迭代器的作用有指针为何还要迭代器
1、迭代器
Iterator迭代器模式又称Cursor游标模式用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解Iterator模式是运用于聚合对象的一种模式通过运用该模式使得我们可以在不知道对象内部表示的情况下按照一定顺序由iterator提供的方法访问聚合对象中的各个元素。
由于Iterator模式的以上特性与聚合对象耦合在一定程度上限制了它的广泛运用一般仅用于底层聚合支持类如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。
2、迭代器和指针的区别
迭代器不是指针是类模板表现的像指针。他只是模拟了指针的一些功能通过重载了指针的一些操作符-、*、、–等。迭代器封装了指针是一个“可遍历STL Standard Template Library容器内全部或部分元素”的对象 本质是封装了原生指针是指针概念的一种提升lift提供了比指针更高级的行为相当于一种智能指针他可以根据不同类型的数据结构来实现不同的–等操作。
迭代器返回的是对象引用而不是对象的值所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。
3、迭代器产生原因
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来使得不用暴露集合内部的结构而达到循环遍历集合的效果。
说说你所知道的容器都有哪些map与set的区别使用map有哪些优势map的底层实现说下红黑树map的迭代器会失效吗什么情况下回失效AVLTree和RBTree的对比为什么map和set使用了红黑树红黑树的优势是什么AVLTree和RBTree所达到的平衡有什么区别RBTree节点的颜色是红或者黑色其他颜色行不行RBTree是如何插入如何旋转的
二、哈希
哈希表是根据关键码值而直接进行访问的数据结构。通过关键码值映射到表中的一个位置来访问记录以加快查找的速度。哈希表主要是解决两个问题哈希函数和哈希冲突。
哈希函数
哈希函数也叫散列函数他对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对不同的输入要产生不同的结构同时散列结果也应当具有同一性和雪崩效应微小的输入值发生的变化使得输出值发生巨大的变化。
哈希冲突
哈希冲突就是不同的关键字通过相同的哈希函数计算出了相同的哈希地址。解决哈希冲突最常见的方法是闭散列和开散列闭散列使用的是线性探测法当发生哈希冲突时如果哈希表没有被装满说明可以将key值保存到下一个空位置中从冲突发生的位置开始依次向后探测直到找到下一个空位置为止。开散列使用的是拉链法先对关键码使用哈希函数计算哈希地址具有相同的哈希地址的关键码归于同一个子集称子集合为一个桶每个桶中的元素通过一个单链表连接起来然后将各个链表的头结点存放在哈希表中。由于哈希表中桶的个数是固定的如果某个桶中的元素非常多这样会影响真个哈希表的性能。一般来说如果桶中的元素过多会将单链表的存储方式换成红黑树或者是对哈希表进行增容。
十、二叉树的先序遍历、中序遍历和后序遍历
//二叉树的递归遍历
void PreOrde(BTree* root) { if(root) { cout root-data ; PreOrde(root-left); PreOrde(root-right); } }
void InOrde(BTree* root) { if(root) { PreOrde(root-left); cout root-data ; PreOrde(root-right); } }
void PostOrde(BTree* root) { if(root) { PreOrde(root-left); PreOrde(root-right); cout root-data ; } }
void PreOrde1(BTree* root) { stackBTree* s; BTree* cur root;
while(!s.empty() || cur)
{while(cur){cout cur-data ;s.push(cur);cur cur-left;}if(!s.empty()){BTree* tmp s.top();s.pop();cur tmp-right;}
}}
void InOrde1(BTree* root) { stackBTree* s; BTree* cur root;
while(!s.empty() || cur)
{while(cur){s.push(cur);cur cur-left;}if(!s.empty()){BTree* tmp s.top();cout tmp-data ;s.pop();cur tmp-right;}
}}
void PasrOrde1(BTree* root) { stackBTree* s; stack flag; BTree* cur root;
while(!s.empty() || cur)
{while(cur){s.push(cur);flag.push(false);cur cur-left;}if(!s.empty()){if(flag.top()){cout s.top()-data ;s.pop();flag.pop();}else{cur s.top()-right;flag.top() true;}}
} }
三、链表环
判断是否有环
定义一个快指针和一个慢指针快指针一次走两步慢指针一次走两步会出现两种情况情况一指针走到了空的位置那就说明这个链表不带环。情况二两个指针相遇说明这个链表带环。
获得入环节点
如果不考虑空间复杂度可以使用一个map来记录走过的节点这个指针一直向后遍历如果遇到空说明这个链表不带环也就没有入环节点如果没有遇到空如果遇到第一个在map中存在的节点就说明回到了出发点这个节点就是环的入口节点。
如果不建立额外的空间先使用快慢指针判断这个链表是否有环如果有环将相遇节点记录然后一个指针从链表的起始位置开始一次走一步另一个指针从记录的节点开始一次走一步当两个节点再次相遇这个相遇节点就是环的入口节点。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7uf3JqSR-1637763958108)(C:\Users\LENOVO\AppData\Roaming\Typora\typora-user-images\1565675547490.png)]
四、栈和队列
两个栈模拟实现队列
队列的特性就是只能在队尾进行插入操作在队头进行删除操作两个栈实现一个队列一个栈s1负责入队列另一个栈s2负责出队列当删除队列的时候如果s2中有元素直接取栈顶元素如果s2是空栈将s1中的所有元素搬移到s2中然后再取栈顶元素。
两个队列模拟实现栈
栈的特性就是只能在一端进行插入和删除操作用两个队列一个用来进行入栈操作另一个进行删除的时候才会用到将有元素的栈的size-1个元素全部搬移到另一个空队列中然后将最后一个元素删除就完成了删除操作。
五、hashmap和map的区别
map是STL中的一个关联式容器它提供一对一的K-V的数据处理能力由于这个特性在我们需要完成Key-Value数据处理的时候可以很方便的调用。map的底层结构是红黑树这棵树对数据有自动排序的功能所以map中的数据都是有序的并且查找的时间复杂度基本是LogN。他的特点是增加和删除节点对迭代器的影响很小只对操作的节点有影响但是对于迭代器来说可以修改节点对应的V值不能修改K值。
HashMap是基于哈希表的Map它具有着map的特性。当我们将K值传递给put()方法时它调用对象的hashCode()方法来计算hashcode然后找到对应的位置来存放value。hashmap使用开散列的方法来解决哈希冲突。他是线程不安全的hashmap中的初始容量和装填因子会影响他的性能。
1、他们的底层实现不同map使用的是红黑树来实现Hashmap使用的哈希表来实现。
2、他们的查找时间复杂度不同map的时间复杂度是log(n)hashmap的时间复杂度O(1)。
3、map不允许有NULL值但是hashmap允许有NULL。
★★排序算法★★ 一、冒泡排序 冒泡排序时通过无序区中相邻记录的关键字间的比较和位置的交换使关键字最小的元素如气泡似的逐步上浮直水面。有序区逐渐扩大无序区逐渐缩小。 冒泡排序算法的原理如下
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较
动画演示 冒泡排序是一种非常容易理解的排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 普通冒泡
void bubble0(vectorint arr){ int size arr.size(); for(int i 0; i size; i) { for(int j 0; j size-i-1; j) { if(arr[j] arr[j1]) { swap(arr[j1], arr[j]); } } }}优化一 第一种优化就是在交换的地方加一个标记如果某一趟排序没有交换元素说明这组数据已经有序不用再继续下去。这样对部分连续有序而整体无序的数据大大提升了效率。
void bubble1(vectorint arr){ int size arr.size(); for(int i 0; i size; i) { bool flag true; for(int j 0; j size-i-1; j) { if(arr[j] arr[j1]) { flag false; swap(arr[j1], arr[j]); } } if(flag) return; }}优化二 对于优化一来说仅仅对部分连续有序而整体无序的数据效率高一些如果这组数据时前面无序但是后面的部分有序效率就不是那么高了。因此可以在优化一的基础上记下最后一次交换的位置这个位置后没有交换必然是有序的然后下一次排序从第一个比较到上次记录的位置结束即可。
void bubble2(vectorint arr){ int size arr.size() -1; int pos size; for(int i 0; i size; i) { bool flag true; int k 0; for(int j 0; j pos; j) { if(arr[j1] arr[j]) { flag false; swap(arr[j1], arr[j]); k j; } } if(flag) return; pos k; }}优化三 冒泡算法经过优化二后效率有很大的提升但是效率还可以继续优化就是在一趟排序中确定两个最值也就是一个正向查找最大值另一个反向查找最小值
void bubble3(vectorint arr){ int size arr.size() -1; int pos size; int pos1 0; for(int i 0; i size; i) { bool flag true; int k 0; //正向冒最大值 for(int j 0; j pos; j) { if(arr[j1] arr[j]) { flag false; swap(arr[j1], arr[j]); k j; } } if(flag) return; pos k; //反向冒最小值 int n pos1; for(int j k; j pos1; --j) { if(arr[j-1] arr[j]) { swap(arr[j-1], arr[j]); n j-1; flag false; } } if(flag) return; pos1 n; }}二、选择排序 选择排序是一种简单直观的排序算法。 选择排序原理
初始时设第一个元素为最大值并记录其下标为maxpos从剩余未排序元素中继续寻找最大元素如果当前元素比下标为maxpos的元素大将maxpos更新到当前位置一次遍历后将下标为maxpos的元素与最后一个元素交换位置以此类推直到整个数组有序。 注意选择排序与冒泡排序是区别的冒泡排序通过依次交换相邻两个顺序不合法的元素位置从而将当前最大元素放到合适的位置而选择排序每遍历一次都记住了当前最大元素的位置最后仅需一次交换操作即可将其放到合适的位置。 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定 void slectSort(vectorint arr){ int size arr.size(); for (int i 0; i size - 1; i) { int maxPos 0; for (int j 1; j size - i; j) { if (arr[j] arr[maxPos]) maxPos j; } if (maxPos ! size-i-1) swap(arr[maxPos], arr[size - i-1]); }}优化 选择排序的优化就是在原来的一次只标记一个最值优化为一个标记两个最值这样效率可以提升原来的一半。
void SlectSort(vectorint arr){ int size arr.size(); int begin 0; int end size - 1; while (begin end) { int minPos begin; int maxPos begin; int index begin 1; while (index end) { if (arr[minPos] arr[index]) minPos index; if (arr[maxPos] arr[index]) maxPos index; index; } if (maxPos ! end) swap(arr[maxPos], arr[end]); //这段小代码在在下面介绍其作用 if (minPos end) minPos maxPos; if (minPos ! begin) swap(arr[begin], arr[minPos]); begin; --end; }}上面代码标记的一小段代码是为了防止minpos在最大值要插入的位置。比如序列21541这时候的maxpos为1minpos为3调整过最大值后序列就成了21415这时候的minpos还是3如果直接进行最小值交换就恢复到之前的位置了所以要加上这段判断代码。这样如果最小值在最大值要交换的位置最大值交换后要将最小值的位置更新到maxpos的位置。
三、插入排序 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想 当插入第i(i1)个元素时前面的arr[0],arr[1],…,arr[i-1]已经排好 序此时用arr[i]与arr[i-1],arr[i-2]进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。 元素集合越接近有序直接插入排序算法的时间效率越高其时间效率在O(n)与O(n^2)之间。直接插入排序的空间复杂度为O(1)它是一种稳定的排序算法。 元素集合越接近有序直接插入排序算法的时间效率越高 时间复杂度O(N^2) 空间复杂度O(1)它是一种稳定的排序算法 稳定性稳定 void InsertSort(vectorint arr){ int size arr.size(); for (int i 1; i size; i) { //待插入元素 int key arr[i]; //找插入位置 int end i - 1; while (end 0 arr[end] key) { //向后搬移数据 arr[end 1] arr[end]; end--; } //开始插入 arr[end 1] key; }}优化 普通的插入排序就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列这样我们不用按顺序依次寻找插入点可以采用折半查找的方法来加快寻找插入点的速度。 折半插入排序算法是一种稳定的排序算法比普通插入算法明显减少了关键字之间比较的次数因此速度比直接插入排序算法快但记录移动的次数没有变所以折半插入排序算法的时间复杂度仍然为O(n^2)与直接插入排序算法相同。
void InsertSort1(vectorint arr){ int size arr.size(); for (int i 1; i size; i) { //待插入元素 int key arr[i]; //找插入位置 int right i - 1; int left 0; if(arr[right] key) { while (left right ) { int mid left((right-left)1); if(arr[mid] key) left mid1; else right mid-1; } } //开始搬移数据 int end i -1; while(end left) { arr[end1] arr[end]; --end; } //开始插入数据 arr[end 1] key; }}四、希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 希尔排序是对直接插入排序的优化。 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 希尔排序的时间复杂度不好计算需要进行推导推导出来平均时间复杂度 O(N^1.3 - N^2 稳定性不稳定 void ShellSort(vectorint arr){ int size arr.size(); int gap size; while (gap 0) { gap gap / 3 1; for (int i gap; i size; i) { //待插入元素 int key arr[i]; //找插入位置 int end i - gap; while (end 0 arr[end] key) { arr[end gap] arr[end]; end - gap; } //开始插入 arr[end gap] key; } if(gap 1) break; }}五、快速排序 快速排序快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度平均O(N*logN) 最坏O(n^2)【每次的关键值都是最大值或者最小值】 空间复杂度O(logN) 稳定性不稳定 普通快排 普通快排就是将当前序列的最后一个值作为标志然后开始分割序列。 int Partion(vectorint arr, int left, int right){ int key arr[right-1]; int begin 0; int end right-1; while (begin end) { while (begin end arr[begin] key) begin; while (begin end arr[end] key) end--; if (begin ! end) swap(arr[begin], arr[end]); } if (begin ! right - 1) swap(arr[begin], arr[right - 1]); return begin;}优化一挖坑法 挖坑法的原理就是在左边找到不符合条件的元素时将这个元素放在end处这时候begin位置就成了一个“坑”在右边找到不符合条件的元素时将这个元素放到begin位置将之前的“坑”填好以此类推最后将标志key保存的值放在begin位置将最后一个“坑”填满。
int Partion1(vectorint arr, int left, int right){ int end right - 1; int begin left; int key arr[right - 1]; while (begin end) { while (begin end arr[begin] key) begin; if (begin end) { arr[end] arr[begin]; end--; } while (begin end arr[end] key) end--; if (begin end) { arr[begin] arr[end]; begin; } } arr[begin] key; return begin;}//齐头并进法int Partion2(vectorint arr, int left, int right){ int key arr[right - 1]; int cur left; int pre cur - 1; while (cur right) { if (arr[cur] key pre ! cur) { swap(arr[pre], arr[cur]); } cur; } if (pre ! right-1) swap(arr[pre], arr[right - 1]); return pre;}//三数取中法int MidNum(vectorint arr,int left, int right){ int mid left ((right - left) 1); if (arr[left] arr[right]) { if (arr[mid] arr[left]) mid left; if (arr[mid] arr[right]) mid right; } else { if (arr[mid] arr[left]) mid left; if (arr[mid] arr[right]) mid right; } return mid;}int Partion3(vectorint arr, int left, int right){ int end right - 1; int begin left; int mid MidNum(arr, left, end); swap(arr[mid], arr[right - 1]); int key arr[right - 1]; while (begin end) { while (begin end arr[begin] key) begin; if (begin end) { arr[end] arr[begin]; end--; } while (begin end arr[end] key) end--; if (begin end) { arr[begin] arr[end]; begin; } } arr[begin] key; return begin;}void QuickSort(vectorint arr, int left, int right){ if (right - left 1) { int key Partion3(arr, left, right); QuickSort(arr, left, key); QuickSort(arr, key 1, right); }}//非递归快排void QuickSortNor(vectorint arr){ int right arr.size(); int left 0; stackint s; s.push(right); s.push(left); while (!s.empty()) { left s.top(); s.pop(); right s.top(); s.pop(); if (right - left 1) { int key Partion3(arr, left, right); //保存右值 s.push(right); s.push(key 1); //保存左值 s.push(key); s.push(left); } }}六、堆排序 堆排序就是利用堆堆的详细介绍这种数据结构进行排序的算法堆排序属于选择排序 时间复杂度O(nlogn) 空间复杂度O(1) 稳定性不稳定 堆排序的步骤为 1、基于所给元素创建一个大堆 2、使用堆删除的思想从最后一个结点向前调整 typedef struct Heap{ HPData* _array; int _size; int _capacity;}Heap;void HeapAdjust(HPData* array, int size, int root){ int child root * 2 1; while (child size) { if (child 1 size array[child] array[child 1]) child 1; if (array[child] array[root]) { swap(array[child], array[root]); root child; child root * 2 1; } else return; }}void HeapSort(HPData* array, int size){ //建大堆 //找倒数第一个非叶子节点 int root (size - 2) 1; for (; root 0; --root) HeapAdjust(array, size, root); //开始排序使用删除节点的思想 int end size - 1; while (end) { swap(array[0], array[end]); HeapAdjust(array, end, 0); end--; }}七、归并排序 归并排序是简历在归并操作上的一中有效的排序算法该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列。显示每个子序列有序再使子序列段间有序。若两个有序列表合并成一个有序列表陈伟二路归并。 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定 void _MergeData(vectorint arr, int left, int mid, int right, vectorint temp){ int begin1 left; int end1 mid; int begin2 mid; int end2 right; int index left; while (begin1 end1 begin2 end2) { if (arr[begin1] arr[begin2]) temp[index] arr[begin1]; else temp[index] arr[begin2]; } while (begin1 end1) temp[index] arr[begin1]; while (begin2 end2) temp[index] arr[begin2];}void _MergeSort(vectorint arr, int left, int right, vectorint temp){ if ((right - left) 1) { int mid left ((right - left) 1); _MergeSort(arr, left, mid, temp); _MergeSort(arr, mid, right, temp); _MergeData(arr, left, mid, right, temp); copy(temp.begin() left, temp.begin() right, arr.begin() left); }}★★系统知识★★
一、进程
进程间通信
为什么要为用户提供程间通信方式
因为进程的独立性每个进程操作的都是自己虚拟地址空间中的虚拟地址无法访问别人的地址所以无法直接通信。
管道半双工
本质内核中的一块缓冲区
原理人多个进程访问到相同的缓冲区来实现通信管道通信使用的系统调用的IO接口遵循一切皆文件的思想。
匿名管道
一个进程创建匿名管道操作系统再内核中重建一块缓冲区并返回两个人文件描述符作为管道的操作句柄一个用于读一个用于写方向的选择权交给用户但是这个缓冲区在内核中没有标识。
操作接口
创建管道
int pipe(int pipefd[2]);pipefd:至少有两个int型元素的数组创建一个管道通过pipefd获取系统返回的管道操作句柄其中pipefd[0]: 用于从管道中读取数据pipefd[1]: 用于向管道中写入数据返回值成功返回 0 失败返回-1ipc进程间通信方式
管道必须创建于子进程之前子进程这样才能复制到管道的操作句柄
管道的读写特性
1、若管道中没有数据则read会阻塞等待直到数据被写入
2、若管道中数据满了则write会阻塞等待直到数据被读取
3、若管道中的所有读端被关闭则wirte会触发异常进程退出
4、若管道的所有写端被关闭则read会返回0
5、管道的read返回0不仅仅指的是没有读到数据还有可能是写端被关闭
grep make从标准输入循环读取数据对读到的数据进行过滤匹配
匿名管道的实现就是创建两个进程一个运行ls另一个运行grep
让ls这个进程标准输出重定向到管道写入端
命名管道
在命名管道中同一主机上的任意进程之间通信命名管道在内核中这块缓冲区是由标识的一维着所有的进程都可以通过这个标识找到这块缓冲区来实现通信。命名管道的标识符实际上是一个文件可见于文件系统意味着所有进程都可以通过打开文件来访问到内核中的缓冲区。
命名管道的打开特性
若文件当前没有被已读的方式打开则以O_WRONLY打开时会阻塞
若文件当前没有被已读的方式打开则以O_RDONLY打开时会阻塞
命名管道的读写特性类同于匿名管道
命名管道和匿名管道
匿名管道只能用于具有亲缘关系的进程间通信
命名管道可以作用于同一主机上任意进程间通信
管道特性
1、管道是半双工通信
2、管道的读写特性命名管道的打开特性
3、管道的生命周期随进程所有管道的操作句柄被关闭
4、管道自带同步与互斥管道的读写大小不超过PIPE_BUF时是安全的
5、管道提供字节流服务但是存在粘包问题
管道通信
管道通信的本质是通过内核中的缓冲区来实现通信
进程1将数据从用户态缓冲区拷贝到内核态缓冲区然后进程2将数据冲内核态缓冲区拷贝到用户态缓冲区涉及两次用户态与内核态之间的数据拷贝。
共享内存
最快的进程间通信方式
共享内存原理
1、在物理内存中开辟一块内存空间
2、将这块空间通过页表映射到进程的虚拟地址空间中
3、进程可以直接通过进程虚拟地址空间访问这块物理内存进行操作若多个进程映射同一块物理内存就可以实现相互通信这样就可以通过虚拟地址改变内存中的数据其他进程也会随之改变。
4、相较于其他进程间通信方式少了两步内核态和用户态之间的数据拷贝
5、释放映射关系
6、删除共享内存
1、创建共享内存int shmget(key_t key, size_t size, int shmflg); key: 共性内存在操作系统中的标识符 size: 共享内存大小 shmflag: IPC_CREAT 共享内若存在则打开否则创建 IPC_EXCL 与IPC_CREAT同时使用若共享内存村在则报错返回 mode 贡献内存的操作权限 返回值: 正整数--共享内存的操作句柄 2、将共享内存映射到虚拟地址空间void *shmat(int shmid, const void *shmaddr, int shmflg); shmid 创建共享内存返回的操作句柄 shmaddr 共享内存在虚拟地址空间中的首地址--通常置空NULL,有操作系统来指定 shmflg SHM_RDONLY--映射之后共享内存只读通常置0可读可写 返回值 映射首地址 失败(void*) -13、通过虚拟地址进行操作
mencpy
4、解除映射关系
int shmdt(const void *shmaddr); shmaddr shmat建立映射关系是返回的映射首地址5、删除共享内存
int shmctl(int shmid, int cmd, struct shmid_ds *buf); shmid 共享内存操作句柄 cmd 共享内存操作即将进行的操作 IPC_RMID buf 用于获取/设置共享内存信息共享内存的删除流程共向内存在删除的时候首先会判断当前映射链接数是否为0若为0直接删除否则表示现在还有其他进程在使用则共享内存不能立即被删除但是会拒绝后续进程的映射链接等待映射链接数为0时删除这块共享内存。
消息队列
操作系统在内核中为用户闯将一个队列其他进程通过访问相同的队列进行通信消息队列传输的是有类型的数据块共享内存、消息队列的生命周期随内核
用于多个进程间有类型的数据块传输
ipcs 查看 -m 共享内存 -s 信号量 -q 消息队列ipcrm -m shmid 删除对应的共享内存 -m 共享内存 -s 信号量 -q 消息队列信号量
实现进程间的同步与互斥
本质:在内核中是一个计数器唤醒等待.
同步保证多个进程之间对临界资源访问的时序合理性-—-等待与唤醒
互斥保存多个进程之间同一时间对临界资源的唯一访问型性
原理:
进程对资源进行访问操作之前先进行临界资源计数判断 若计数0,则阻塞等待创建资源 --计数-1 等待在等待队列中 若计数 0,则直接返回,按照程序流程就可以直接擦做资源了,计数-1 有进程创建了资源,计数1, 并唤醒等待队列上的那些进程
二、线程
线程是在Linux中使用PCB模拟实现的轻量级进程进程从表面来说是一个运行起来的程序但是从操作系统角度来说进程就是操作系统堆为一个正在执行的程序而创建的描述符操作系统通过对这个描述来对程序进行控制这个描述信息就是PCB所以说线程就是一个轻量级的进程是一个进程等的子任务线程共享进程中部分资源包括数据段、代码段和扩展段每个线程拥有自己的线程描述符、数据栈、用于存放上下文数据的寄存器、错误码、信号屏蔽字。线程是进程中的一个执行流是操作系统调度和执行的最小单位。
线程间通信(同步)的方式
临界区通过多线程的串行化来访问公共资源或一段代码速度快适合控制数据访问
互斥量采用互斥对象机制只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个所以可以保证公共资源不会被多个线程同时访问
信号量为控制具有有限数量的用户资源而设计的它允许多个线程在同一时刻去访问同一个资源但一般需要限制同一时刻访问此资源的最大线程数目。
事件(信号通过通知操作的方式来保持多线程同步还可以方便的实现多线程优先级的比较操作
三、进程与线程
什么是线程
线程是在Linux中使用PCB模拟实现的轻量级进程进程从表面来说是一个运行起来的程序但是从操作系统角度来说进程就是操作系统堆为一个正在执行的程序而创建的描述符操作系统通过对这个描述来对程序进行控制这个描述信息就是PCB所以说线程就是一个轻量级的进程是一个进程等的子任务线程共享进程中部分资源包括数据段、代码段和扩展段每个线程拥有自己的线程描述符、数据栈、用于存放上下文数据的寄存器、错误码、信号屏蔽字。线程是进程中的一个执行流是操作系统调度和执行的最小单位。
线程和进程的区别
1、一个线程只能属于一个进程而一个进程可以有一个或多个线程线程是依赖于进程存在的。
2、进程在执行过程中拥有一个独立的内存单元而多个线程共享同一个进程的内存。也就是说资源分配给进程在这个进程中的所有线程共享其中的所有资源同一个进程中所有线程共享代码段、数据段、扩展段。但是每个线程拥有自己的栈段栈段又叫运行时段用来存放所有局部变量和临时变量。栈寄存器上下文数据信号屏蔽字errno(错误码)线程标识符
3、进程是资源分配的最小单元线程是CPU调度的最小单元
4、系统的开销由于创建或撤销进程时系统都要为他分配或回收如内存空间、I/O设备等。因为操作系统所付出的开销将显著的大于在创建线程或撤销线程时的开销。类似地在进行进程切换时涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只需要保存和设置少量的寄存器的内容并不涉及存储器管理方面的操作。所以进程切换的开销要远远大于线程切换的开销。
5、通信由于同一个进程中的多个线程具有相同的地址空间所以他们之间的同步和通信的实现也变得比较简单。进程间通信IPC有管道、共享内存、消息队列、信号量进行通信。线程间可以直接读写进程数据段来进行通信。在有的系统中线程的切换、同步和通信都无需操作系统内核干预。
6、进程编程调试简单可靠性高但是创建和销毁的开销较大相对于线程来说正好相反开销小、切换速度快但是编程调试相对复杂。
7、进程之间不会相互影响但是同一个进程中只有一个线程挂掉了将导致整个进程挂掉。
8、多线程适合于I/O密集的工作场景、多进程适合于CPU密集型的工作场景。
怎么实现线程池
1、设置一个生产者消费者队列作为临界资源。
2、初始化n个线程并让其运行起来以加解锁的方式去队列取任务运行。
3、当任务队列为空的时候所有的线程阻塞。
4、当生产者队列来了一个任务后先对队列加锁把任务挂在队列上然后使用条件变量去通知阻塞中的一个线程。
四、线程安全
什么是线程安全
多线程对临界资源进程操作二不会产生二义性。
保证线程安全的机制
使用同步与互斥保证线程安全。
线程同步
同步就是协同步调按预定的先后次序进行运行。线程同步是指多线程通过特定的设置如互斥量事件对象临界区来控制线程之间的执行顺序即所谓的同步也可以说是在线程之间通过同步建立起执行顺序的关系如果没有同步那线程之间是各自运行各自的
线程互斥是指对于共享的进程系统资源在各单个线程访问时的排它性。当有若干个线程都要使用某一共享资源时任何时刻最多只允许一个线程去使用其它要使用该资源的线程必须等待直到占用资源者释放该资源。线程互斥可以看成是一种特殊的线程同步。
线程同步有四种方式临界区、互斥对象、信号量、事件对象。
临界区、互斥对象主要用于互斥控制都具有拥有权的控制方法只有拥有互斥对象的线程才能执行任务所以拥有互斥对象的线程执行完任务后一定要释放该对象。
信号量、事件对象事件对象是以通知的方式进行控制主要用于同步控制。
临界区
通过对多线程的串行化来访问公共资源或一段代码速度快适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问如果有多个线程试图访问公共资源那么在有一个线程进入后其他试图访问公共资源的线程将被挂起并一直等到进入临界区的线程离开临界区在被释放后其他线程才可以抢占。它并不是核心对象不是属于操作系统维护的而是属于进程维护的。
互斥对象
互斥对象和临界区很像采用互斥对象机制只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个所以能保证公共资源不会同时被多个线程同时访问。当前拥有互斥对象的线程处理完任务后必须将线程交出以便其他线程访问该资源。
信号量
信号量也是内核对象。它允许多个线程在同一时刻访问同一资源但是需要限制在同一时刻访问此资源的最大线程数目。
条件变量
条件变量是一种同步机制允许线程挂起直到共享数据上的某些条件得到满足。条件变量要和互斥锁相结合避免出现条件竞争就是一个线程预备等待一个条件变量当它在真正等待之前另一个线程恰好触发了该条件。
互斥锁
互斥从表面上理解就是相互排斥。所以互斥锁从字面上理解就是一个进程拥有了这个锁他将排斥其他所有的进程访问被锁住的东西其他的进程如果需要锁只能阻塞等待等拥有锁的进程解锁后才能继续运行。在使用互斥锁的时候要注意一点就是解铃还须系铃人如果拥有锁的进程不解锁那么其他进程将永远不能得到互斥锁。
读写锁
互斥锁是排它锁条件变量出现后和互斥锁配合能够有效地节省系统资源并提高线程之间的协同工作效率。互斥锁的目的是为了独占条件变量的目的是为了等待和通知。对于文件来说最常见的操作就是读和写读文件不会修改文件的内容所以多个进程同时读也是可以的但是当写进程需要写数据的时候为了保证数据的一致性所有读的进程都不能读数据否则读到的数据可能是一半是旧的一半是新的这样就乱了。所以为了防止读数据的时候写入新的数据在读数据的时候就必须对文件加锁但是如果有两个进程要同时读另一个进程就只能等待从性能上讲是浪费时间。所以这是要用到读写锁读写锁的出现有效地解决了多进程并行读的问题这样每个进程在读的时候需要申请读锁进程之间相互不干扰。如果有进程要写数据需要申请写锁如果有读锁或者写锁存在那么只能等待所有的锁都解锁了才可以进行写操作。有一点值得注意的是读锁是所有进程共享的但是写锁是互斥的。
记录锁
为了增加同步的性能可以在读写锁的基础上进一步细分被锁对象的粒度。比如说写操作是针对文件的前1k字节但是读操作是针对文件的后1k字节这样就可以对文件的前1k上写锁后1k上读锁这样读和写就可以并发进行了文件锁是记录锁的一个特例记录锁针对的是文件中的某一部分内容如果记录锁将整个文件上锁这时候的记录锁就是一个文件锁。
线程互斥
五、死锁的条件以及解决的办法
什么死锁
死锁的条件
必须要满足以下的四个条件才可以发生死锁。
1、互斥条件
指的是某个资源同时只能让一个进程占有比如说打印机。必须要在占有该资源的进程主动释放资源后其他进程才可以占有。这时有资源本身属性决定的。
2、不可抢占资源
进程获得的资源在没有使用完的情况下这份资源不能被资源申请者强行占有只能等该资源释放候才可以申请。
3、占有且申请条件
一个进程至少占有了一个资源他又要申请新的资源但是申请的资源被另一个进程所占有这时进程阻塞在他阻塞的时候仍然占有已有的资源。
4、循环等待条件
可以说是一个进程等待队列p1等待p2所占有的资源同时p1不对自己的资源进行释放p2在等待p1所占有的资源同样的p2也不对自己所占有的资源进行释放这样就形成了一个进程的循环等待。
死锁的预防
死锁的预防就是保证系统不进入死锁的状态的一种策略。
1、破坏互斥条件
但是有些资源确实不能被共享这是由资源的属性决定的。
2、破坏不可抢占条件
将资源的申请设置为可抢占式也就是要求申请失败的进程要释放自己占有的资源给其他进程使用但是会降低系统性能。
3、破坏占有且申请条件
直接一次性将自己所需要的资源申请完。当时这样有两个问题一个是有时候不可预知需要什么资源另一个是资源的利用率低进程可能会长期占有自己可能用不到的资源。
4、破坏循环等待条件
将资源进行分类、编号让进程按照排好的序号进行申请。存在的问题是对资源的编号可能是困难的维护相应的序列也可能是困难的。
死锁的避免
死锁的避免是指不限制进程有关申请资源的命令而是对进程所发出的每一个申请资源命令甲乙动态的检查并且根据检查结果来判断是否进行资源分配。
银行家算法我们可以把操作系统看作是银行家操作系统管理的资源相当于银行家管理的资金进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全
银行家规定
当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客 顾客可以分期贷款但贷款的总数不能超过最大需求量 当银行家现有的资金不能满足顾客尚需的贷款数额时对顾客的贷款可推迟支付但总能使顾客在有限的时间里得到贷款 当顾客得到所需的全部资金后一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源当进程首次申请资源时要测试该进程对资源的最大需求量如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源否则就推迟分配。当进程在执行中继续申请资源时先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源若能满足则按当前的申请量分配资源否则也要推迟分配。
六、IO多路转接
select
对大量的IO事件是否就绪进行监控并且可以告诉进程哪一个IO就绪了然后就可以对就绪的IO进行具体的操作。事件是否就绪指的是文件描述符可读/可写/异常。他的流程是这样的用户将需要监控的文件描述符添加到一个描述符集合中然后select将描述符集合拷贝到内核中对集合中的描述符进行轮询判断如果有描述符事件就绪了select调用返回并且返回描述符的个数。否则隔一会再进行轮询判断。在调用返回之前会将集合中没有就绪的时间描述符移除在集合中只剩下就绪的文件描述符。返回之后进程判断有哪个文件描述符在集合中然后对其进行操作。
select的缺点
select所能监控的文件描述符最多只有1024个他每次都需要将文件描述符集合拷贝到内核中进行监控在用户态和内核态之间进行数据的拷贝在内核中要对所有的文件描述符进行轮询遍历判断性能会随着描述符的增加而降低每次返回的时候都需要将文件描述符集合中非就绪的描述符进行移除再次监控的时候需要添加新的描述符编码复杂select虽然返回给用户文件描述符集合但并不会告诉用户哪些文件描述符是就绪的需要用户自己去遍历判断性能同样会随着描述符的增多而降低。
select的优点
select遵循posix标准可以跨平台使用并且他监控超时的等待时间可以精细到微秒。
poll
poll的功能也是对大量的文件描述符事件进行监控用户为每一个关心的文件描述符定义一个事件结构内容为文件描述符所关心的事件poll将描述符事件结构数组拷贝到内核中进行监控同样是轮询遍历数组中的描述符判断事件是否就绪如果就绪了就将事件放到事件结构revents中调用返回否则会隔一段时候后继续遍历判断当调用返回后用户遍历事件结构数组判断结构中的revents事件中是否包含了所关心的事件。
poll缺点
每次监控需要将所有的事件结构信息拷贝到内核中在内核中进行轮询判断描述符事件是否就绪会随着描述符的增多而降低性能poll的返回同样不会直接告诉用户哪些描述符就绪了需要用户轮询去遍历事件结构数组判断哪个是用户所关心的并且对其进行操作poll相对于select来说没有大的改变性能并没有提升多少并且poll没有遵循POSIX标准所以不能跨平台。
poll优点
poll采用事件结构的方式对描述符进行监控简化了多个描述符集合的监控编码流程poll监控的文件描述符的数量没有上限。
epoll
epoll可以说是Linux中最优秀的多路转接他的性能是最高的他在内核中创建eventpoll结构体这个结构体是由红黑树存放事件节点和双向链表存放就绪的文件描述符实现。在linux2.6.8之前需要对epoll监控的文件描述符数量上限进行设置但是在Linux2.6.8之后就忽略了这一参数只要大于0就可以。epoll是一个异步操作epoll开始监控后告诉操作系统开始进程监控eventpoll结构体中红黑树中的所有事件节点操作系统为每一个文件描述符就定义了 一个事件回溯当文件描述符指定的事件就绪后就将这个描述符指定的事件接收信息节点添加到eventpoll中的双向链表中。相当于直接告诉了用户哪些文件描述符就绪了。
epoll触发方式
水平触发
对于可读事件来说文件描述符接收缓冲区数据大小只要大于低水位标记就会触发对于可写事件来说只要是文件描述符的发送缓冲区空间大小只要大于低水位标记就会触发。水平触发是epoll的默认触发方式EPOLLLT宏
边缘触发
对于可读事件来说描述符缓冲区中每当有新数据到来时才会触发一次对于可写事件来说描述符发送缓冲区从没有剩余空间到有剩余空间时才会触发一次。边缘触发需要手动设置EPOLLET。边缘触发每条数据值触发一次这就意味着这次触发的过程中需要用户将所有的数据存取完毕因为这条数据不会触发第二次只有等到下一条数据到来才会触发下一次。由于边缘触发需要一次性将所有的数据都处理完但是用户有可能也不知道数据有多长所以要使用循环才可以将所有的数据处理完但是循环会出现一个就是读到没有数据的时候就会阻塞。相应的解决方案是将IO操作设置为非阻塞的。
将描述符设置为非阻塞int flag fcntl(fd, F_GETFD,0) ----获取描述符属性fcntl(fd, F_GETFD, flag | O_NONBLOCK)---设置描述符属性为增加一个非阻塞属性epoll优点
监控的文件描述符没有上限采用事件结构对描述符进行监控简化了多个描述符集合的监控流程每条epoll的事件信息只向内核中拷贝一次是一个异步阻塞操作操作系统仅对描述符事件进行监控并且使用的是事件回调方式描述符就绪后直接拷贝到对应的位置不需要轮询遍历判断所以描述符的增加不会影响性能在回调的过程中是将就绪的描述符添加到双向链表中epoll_wait只需要判断双向链表就知道当前是否有描述符事件就绪当epoll_wait返回时是直接将就绪信息拷贝到之前给予的事件结构数组中这就相当于直接将就绪的描述符告诉给了用户。
epoll缺点
epoll没有遵循POSIX标准所以不能跨平台他监控超时只能精确到毫秒。
同步异步和阻塞非阻塞的区别
阻塞是为了完成一个功能发起调用如果当前不满足条件要等待满足条件了才调用返回。非阻塞恰恰相反如果不满足条件直接报错返回阻塞和非阻塞强调的是发起一个调用后是否立即返回。同步指的是如果不满足条件需要进程进行等待知道条件满足了才会调用返回对于异步来说他为了完成某个功能只发起一个调用进程自身并不去完成功能由操作系统完成后调用进程所以说同步和异步强调的是发起调用后功能是否有进程自己完成。同步功能是由进程自身完成的通常是阻塞的异步功能是由系统完成的有阻塞也有非阻塞。在多路转接中select和poll是同步的需要进程自己来实现轮询的遍历监控epoll是异步阻塞的因为功能的完成是操作系统完成的而进程是调用epoll_wait阻塞等待操作系统完成监控。
场景
多路转接模型实现高并发模型相较于多线程/多进程消耗资源较少但并不是说所有的场景都使用多路转接模型它只是用于有大量的文件描述符需要监控但是同一时间只有少量活跃并且每个描述符的处理过程时间不能太长。
七、用户态和内核态
在inter x86结构的cpu中一共有四个级别0-3级0级特权最高3级特权最低这样做是为了让最关键的工作交给特权级最高的进程去执行可以做到集中管理减少有限资源的访问和使用冲突。
当一个进程在执行用户自己的代码时处于用户态此时特权级最低为3级是普通用户进程运行的特权级大部分用户直接面对的程序都是运行在用户态并且Ring3状态不能访问Ring0状态的地址空间包括代码和数据当一个进程因为系统调用陷入内核代码中执行时处于内核运行态此时特权级最高为0级。执行的内核代码会使用当前进程的内核栈每个进程都有自己的内核栈。内核态的进程执行完又会切换到Ring3回到用户态。这样用户态的程序就不能随意操作内核地址空间具有一定的安全保护作用。用户态切换到内核态通常有三种方式系统调用、异常、外围设备的断。
系统电泳是用户态进程主动要求切换内核态的一种方式。用户态进程通过系统调用申请使用操作系统的服务程序完成工作。比如说fork()就是执行了一个创建新进程的系统调用。
异常是当cpu在执行运行在用户态的程序时发生了一些没有预知的异常这时会触发由当前运行进程切换到处理词异常的内核相关进程中也就是切换到了内核态。
外围设备的中断指的是当外围设备完成用户请求的操作后会向CPU发出相应的中断信号这时CPU会暂停执行下一条即将要执行的指令而转到与中断信号对应的处理程序去执行如果当前执行的执行时用户态下的程序那么转换的过程自然就是由用户态转换到内核态。
这三种方式是系统在运行时有用户态切换到内核态的主要方式其中系统调用可以认为是用户进程主动发起的异常和外围设备中断是被动的。
八、什么是POSIX标准
posix表示可移植操作系统接口它定义了操作系统应该为应用程序提供的接口这一标准带来的好处就是在一个POSIX兼容的操作系统中编写的符合其标准的应用程序可以直接在其他的POSIX支持的操作系统中无需修改而能够直接编译运行。
九、协程★★☆☆☆
协程可以认为是比线程更小的执行单元它自带CPU上下文只要在合适的时机就可以把一个协程切换到另一个协程只要在这个过程中保存或恢复CPU上下文那么程序还是可以运行的。 线程与协程的区别就是系统为了程序运行的高效性每个线程都有自己缓存Cacge等数据操作系统还会帮助做这些数据的恢复操作可以说线程的切换时非常耗性能但是协程的切换只是单程的操作CPU的上下文所以一秒钟切换上百万次系统都扛得住。但是协程有一个问题就是系统并不感知所以操作系统不会对其做切换。在设计的时候可以是一个线程作为容器然后再里面放置多个协程构成一个协程池在协程池中有一个被动的调度器当有协程执行不了的时候就要去通知协程调度器通过算法找到当前最需要CPU的协程然后去执行。
十、Linux程序典型内存布局
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YdIAz6xP-1637763958109)(C:\Users\LENOVO\AppData\Roaming\Typora\typora-user-images\1566374936321.png)]
十一、内存管理
虚拟内存
什么是虚拟内存
内存是一个程序运行的物质基础由于内存空间总是有限的所以让有限的空间运行较大的程序这个问题就出现了Linux中就使用了虚拟内存技术解决了这个问题。虚拟内存是计算机系统管理的一种技术可以让应用程序认为自己有拥有连续的可用内存让系统看上去具有比实际物理内存大得多的内存空间而实际上是被分隔成多个物理内存的碎片还有部分暂时存储在外部磁盘存储器上在需要时进行数据交换。由于程序是逐段被运行的虚拟内存技术是先将一段程序导入内存中执行完后导入下一段程序给我们的感觉是内存变大了实际上物理内存并没有发生变化。
每个进程都有自己独立的4G内存空间各个进程的内存空间具有类似的结构这个空间知识虚拟内存空间每次访问内存空间的某个地址都需要吧地址翻译成实际的物理内存地址。每一个进程都会建立自己的内存空间用来存放这个进程的数据、代码等这些内存空间都与对应的磁盘空间映射。所有进程都共享同一物理内存每个进程只把自己目前需要的虚拟内存并保存到物理内存中。进程通过页表来记录哪些数据在物理内存上哪些不在如果在是在物理内存的哪里。页表一般分为两个部分一部分记录此页是否在物理内存中另一部分用来记录在物理内存中的地址当一个进程需要访问某个虚拟地址的时候要先去看页表如果发丝昂对象的数据不在物理内存中就会缺页异常然后通过解决缺页异常处理后访问对应的物理内存。
虚拟内存的优点
1、每个进程的内存空间都是一致并且是固定的所以链接器在链接可执行文件的时候可以设定内存地址就可以不用去管这些数据最终实际的内存地址这是独立内存空间的好处。当不同的进程使用的同样的代码的时候比如说库文件中的代码物理内存中可以只存储一份这样的代码不同的进程只需要将自己的虚拟内存映射到对应的位置就可以这样节省了内存。在程序需要分配连续的内存空间的时候只需要在虚拟内存空间中分配连续的空间而不需要实际的物理内存空间连续这样可以利用物理内存中的内存碎片提高了内存的利用率。
2、虚拟内存保证了读写内存的安全性。物理内存本身是不限制访问的任何地址都可以读写而操作系统要求不同的页面要具有不同的访问权限这是利用CPU模式和MMU的内存保护机制实现的。
3、如果一个操作系统同时运行着很多进程并且为各个进程分配的内存之和大于实际可用的物理内存虚拟内存管理就可以使这种情况各个进程仍然可以正常运行。因为各个进程分配的只不过是虚拟内存的页面这些页面的数据可以映射到物理页面也可以临时保存到磁盘上而不占用物理页面在磁盘上临时保存的虚拟内存页面可能是一个磁盘分区也可能是一个磁盘文件被称为交换设备。当物理内存不够用的时候可以将一些不常用的物理页面中的数据临时保存到交换设备中然后这个物理页面就可以被认为是空闲的可以重新分配给进程使用这个过程称为换出。如果进程要用到被换出的页面就从交换设备再加载回物理内存这个过程称为换入。换出和换入在操作系统中统称为换页所以系统中可分配的内存总量为物理内存的大小交换设备的大小。
4、虚拟内存作为内存管理工具大大的简化了内存管理并且为每个进程提供了一个独立的虚拟地址空间多个虚拟页面可以映射到同一个共享的物理页面上。按照需要进行页面的调度和独立的虚拟地址空间的结合让虚拟内存简化了连接和加载代码和数据共享以及应用程序的内存分配。
简化链接说的是独立的地址空间允许每个进程的内存映射使用相同的基本格式不用考虑代码和数据在物理内存的地址。当不用的进程使用相同的代码的时候比如说库文件中的代码在物理内存中只存放了一份这样的代码不同的进程只需要将自己的虚拟内存映射到对应的位置就可以。
简化加载指的是虚拟内存让向内存中中加载可执行文件和共享对象文件变得容易。将一组连续的虚拟页面映射到任意一个文件中的任意位置的表示法称为内存映射。
简化共享指的是独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的机制。一般情况下每个进程都有自己独立的内存空间里面存放着该进程的代码、数据、堆栈这些内容都是不与其他进程所共享的。在操作系统中为了多个进程之间通讯的考虑预留出了一块内存区多个进程如果要实现共享由操作系统创建页表将相应的虚拟页映射到不连续的物理页面然后将这个页表映射到进程的这块内存中这样多个进程就可以对同一块物理内存进行读写实现数据的共享。
简化内存分配指的是虚拟内存向用户进程提供一个简单的分配额外空间的机制。当一个用户程序要求额外空间的时候操作系统分配K个适当的连续的虚拟内存页面并且将他们映射到物理内存中的K个任意页面操作系统没有必要分配K个连续的物理内存页面。
鉴于《深入理解计算机系统》龚奕利·译
缺页异常解决办法
什么是缺页异常
在分页系统中可以通过查询页表的状态为来确定要访问的页面时候存在内存中每当所有访问的页面不在内存时或者访问的页面在内存中但是时不可写的会产生一次缺页中断。缺页本身就是一种中断它与一般的中断一样需要经过4个处理步骤 1、保护CPU现场。 2、分析中断的原因 3、转入缺页中断处理程序中进行处理 4、恢复CPU现场继续执行 但是缺页中断时可能由于要访问的页面不在内存中这时就会由硬件产生一种特殊的中断缺页中断与一般的中断区别在于在指令执行期间产生和处理缺页中断信号、一条指令在执行期间可能会产生多次缺页中断、缺页中断返回时执行的是产生中断的那一条指令而不是像一般中断去执行下一条指令。
页面置换算法
进程运行过程中如果发生缺页中断但是内存中没有空间的物理块为了能够把所缺的页面装入内存系统必须要从内存中选择一页调出到磁盘的对换区。但此时应该吧那个页面换出则需要根据一定的页面置换算法来确定。通常有最佳置换、先进先出置换、最近最久未使用置换、时钟置换算法。
最佳置换算法OPT
从主存中移除永远不需要的页面如果没有这样的页面存在则选择最长时间不需要的访问的页面。由于所选择的被淘汰的页面是以后永不使用的或者是在长时间内不再被访问的页面这样就可以保证获得最低的缺页率。
先进先出算法FIFO
是最简单的页面置换算法。这种算法的思想是当需要淘汰一个页面的时候总是选择驻留主存事件最长的页面进行淘汰也就是先进入主存的页面会被先淘汰。这是因为最早调入主存的页面的不再被使用的可能性最大。
FIFO算法还会产生当所分配的物理块树增大而页故障数不减少反而增加的异常现象这是由Belady于1969年发现所以称为Belady异常只有FIFO算法会出现Belady异常而LRU和OPT算法永远不会出现Belady异常。
需要注意的是内存的页面中最先进入队列的页面会被来的页面直接覆盖而不是先出队然后再从大队尾入队。
最近最久未使用算法LRU
这种算法的思想是利用局部性原理根据一个作业在执行中过去的页面访问历史来推测未来的行为。他认为过去一段时间里不曾被访问的页面在最近的将来也不会再被访问。所以这种算法的实质就是当需要淘汰一个页面的时候总是选择在最近一段时间内最久没有使用的页面淘汰。
时钟置换算法CLOCK
由于LRU算法的性能接近于OPT但是实现起来比较困难并且开销大FIFO算法实现简单但是性能差。所以师徒用比较小的开销接近LRU的性能这类算法都是CLOCK算法的变体。
简单的CLOCK算法是给每一帧关联一个附加位称为使用位。当某一页首次装入主存时该帧的使用位设置为1当给爷虽有在被访问到时它的使用位也置为1。对于也替换算法来说用于替换的候选帧集合看做一个循环缓冲区并且有一个指针与之关联。当某一页被替换时给指针被设置成指向缓冲区中的下一帧。当需要替换一页时操作系统扫描缓冲区以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时操作系统就会将该位重新置为0如果在这个过程开始时缓冲区中所有的使用位均为0则选择遇到的第一个帧替换如果所有的帧使用位均为1则指针在缓冲区中完整的循环一周把所有的使用位都置为0并且停留在最初始的位置上替换该帧中的页。由于这个算法循环地检测各页面的情况所以被称为CLOCK算法又称为最近未使用算法。
MMU
内存管理单元简称MMU他杜泽虚拟地址到物理地址的映射并提供硬件机制的访问权限检查。MMU使得每个用户进程拥有自己独立的地址空间并通过内存访问权限的检查保护每个进程所用的内存不被其他的进程破坏。
物理内存
在内核态申请内存比在用户态申请内存更为直接他没有采用用户态的延迟分配内存技术。内核认为一旦有内核函数申请内存就必须立即满足该申请的请求并且这个请求一定是合理的。相反对于用户态申请内存的请求内核总是尽量延后分配内存用户进程总是先获得一个虚拟内存区的使用权最终通过缺页异常获得一块真正的物理内存。
十二、动态库和静态库
什么是库
平时在写代码的时候会经常添加一些头文件添加这些头文件其实是让编译器从一个目录下去寻找这个文件这个目录就是我们常说的库。在Linux中库一般存放在user/lib目录。库就是将一些常用的函数的目标文件打包在一起提供相应的函数接口以便于使用。
什么是静态库
静态库就是在编译连接的时候将库中的代码连接直接复制到可执行文件中这样程序在运行的时候就不用去连接动态库了。静态库的这个连接过程就是静态链接。
什么是动态库
动态库就是程序在运行的时候才去连接动态库的代码可以多个程序共享动态库中的代码这个动态库的连接过程就是动态链接也就是在执行文件开始之前将外部函数的机器码有系统从磁盘上对应的动态库中向内存复制一份。
静态库和动态库的区别
1、动态库是在运行时有系统调用库函数实现链接代码较小巧。而静态库是在链接是复制到代码中代码量比较庞大冗余度高。 2、由于静态库是通过复制的方式所以他在编译连接之后就不再需要静态库代码的可以执行强但是动态库由于是利用本地的库函数如果将代码移植到其他电脑会出现运行bug等可移植性差。 3、动态库必须放在指定的目录下完成连接但是静态库只需要给出链接文件的路径就可以。 4、他们的相同点就是在库文件中不能出现main函数库都是用来提供函数接口的不暴露源代码所有的库的目的都是为了增加代码的复用可共享性减小冗余。 5、在windows中静态库是后缀是.lib动态库是.dll在Linux中静态库是.a,动态库是so。 6、使用ar创建静态库
生成动态和静态库
gcc -fPIC -c child.c -o child.o 生成目标文件
gcc --share child.o -o lid库名称.so 动态库
gcc -ar rcd lib库名称.a 静态库
windows下的动态库 .dll 静态库 .lib
先生成二进制的.o文件gcc -fPIC -c child.c -o child.o生成静态库ar -rc libchild.a child.o生成动态库gcc --shared -fpic libchild.so child.o链库-l 库名但是库必须保存在lib、usr/lib、usr/local/lib目录下否则要用-L 文件路径 -l 库名十三、软连接和硬链接
十四、线程的切换
★★网络知识★★
一、TCP和UDP的区别及应用场景
区别
1、面向连接和无连接角度
tcp建立一个链接需要三次握手断开的时候需要进行四次挥手。TCP在断开是主动方要进入一个TIME_WAIT状态要等待2MSL才会对连接端口释放这个时间要根据系统来定Windows一般为120秒。
但是UDP不需要建立连接直接发起。
2、可靠和不可靠角度
TCP利用三次握手、四次挥手、ACK确认应答、重传机制等来保证可靠性UDP没有。
TCP中保证可靠性的机制有
校验和用来校验数据是否损坏
定时器用来确认分组是否丢失丢失需要重传
序列号用来检测丢失的分组和重传的分组。
确认应答ACK用来让接收方通知发送方已经正确接受以及期望的下一个分组。
否定确认用来让接收方通知发送方没有被正确接受的分组。
窗口和流水线用于增加信道的吞吐量。
3、有序性
TCP利用seq序列号来对包进行排序UDP没有
4、面向字节流和面向报文
面向报文
面向报文的传输方式是应用层交给UDP多少报文UDP就按原样发送也就是一个发送一个报文。所以应用层就要选择合适的大小的报文交给UDP如果报文太长在IP层就会进行分片。
面向字节流
面向字节流的传输方式是虽然应用层交给TCP的是一次一个数据块但是TCP会将这个数据块看成一连串无结构的字节流。在TCP的发送端有一个发送缓冲区当数据块太大TCP就将它划分的小一些在发送如果数据块太小了TCP就会等待累计够足够多的字节后再发送。
5、TCP有流量控制机制UDP没有
6、TCP头部为20字节UDP头部为8字节
应用场景
TCP的应用场景
对效率要求较低但是对准确要求很高的场景。因为在使用TCP传输的时候需要对数据进行确认、重发、排序等操作相对UDP来说效率降低了许多。这些场景都有文件传输、远程登录。
UDP应用场景
对效率要求较高对准确要求较低的场景因为在使用UDP传输的时候没有对数据进行任何的检验操作相对于TCP效率提升了很多。这些应用场景有QQ聊天、在线视频、广播通信等。
二、TCP连接的建立和断开
TCP建立连接
tcp采用三次握手建立连接
1、客户端向服务端发起SYN连接请求这条连接请求中还包含了客户端的窗口大小
2、服务端收到连接、请求后为客户端申请资源同时向客户端回复一个SYNACK还有自己的窗口大小。
3、如果这条消息丢失客户端没有收到这条消息那么客户端不会做任何响应也就不会向服务端发送ACK确认由于服务端迟迟没有发送确认的ACK服务器就会将之前申请的资源释放。如果客户端收到了这条消息开始申请资源同时回复服务端一个ACK确认开始进行收发数据。
4、如果最后这条ACK消息丢失导致服务端没有收到服务端就认为连接失败将之前的资源释放但是客户端认为连接已经建立好了就会向服务端发送数据。服务端由于没有收到最后一条ACK消息就会以RST包对客户端进行响应重新建立连接。
TCP断开连接
TCP采用四次挥手断开连接
1、主动关闭方向被动方发送FIN请求进入FIN_WAIT_1状态等待被动方的ACK确认。
2、被动接收到FIN请求后回复一个ACK确认这时被动方进入CLOSE_WAIT状态进入这个状态是为了将自己的所有要发送的数据都发送完将自己申请的空间都释放完。这时候主动方接受到ACK请求没有直接断开连接而是进入FIN_WAIT_2状态在这个状态下主动方只能接受数据不能进行发送。
3、等被动方将自己的事情都处理完向主动方发送FIN请求进入LAST_ACK状态等待主动方的ACK确认。
4、主动方接收到被动方的FIN请求后进入TIME_WAIT状态向被动方发送ACK等待2MSL后进入CLOSED的状态。这里的MSL是一个报文在网络中的最大生命周期进入TIME_WAIT状态并且等待2MSL是为了防止由于网络原因最后一个ACK没有到达被动方如果被动方一直没有收到ACK确认会再次向主动方发送FIN请求这时主动方重新进入TIMR_WAIT状态。将等待时间设置为2MSL还有一个原因就是要将网络中所有残留的数据消失防止由于网络原因某些数据阻塞在网络中如果没有等待2MSL而是立即重新建立连接很有可能之前的滞留在网络中的数据到达了这时就会造成数混乱。如果在2MSL之内主动方没有接收到被动方FIN请求则认为对方已经接收到ACK主动方进入CLOSED状态也就是断开连接。对于被动方来说一旦接收到了来自主动方的ACK确认就会进入CLOSED状态关闭连接。
三、socket编程过程
基于TCP的socket
服务端程序
创建一个socket调用socket函数返回绑定IP地址、等信息到socket上调用函数bind设置允许的最大连接数,调用函数listen()通常设置为5接受来自客户端的连接调用accept(),使用send和recv开始收发数据 返回值 成功返回实际接收字节数错误返回的-1对端已经关闭了连接返回0关闭网络连接客户端程序
创建一个socket调用socket()函数设置要连接的对方的IP地址和端口等属性连接服务器调用函数connect()使用send和recv开始收发数据关闭网络连接[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nzGXRIl7-1637763958110)(C:\Users\LENOVO\AppData\Roaming\Typora\typora-user-images\1566711302816.png)]
/************************************************************************* - 文件名: tcp_socket.hpp - 作者: bean - 邮箱: 17331372728163.com - 创建时间: Fri 24 May 2019 06:05:41 AM PDT - 备注: 封装一个TcpSocket类向外提供轻便的socket接口 1.创建套接字 2.为套接字绑定地址 3.客户端向服务端发起连接请求 4.服务端开始监听 4.服务端获取一个已经连接成功的客户端的新建socket 5.客户端与服务端开始收发数据 6.关闭套接字 *************************************************************************/#includeiostream#includestring#includestdlib.h#includestdio.h#includeunistd.h#include sys/types.h#includesys/socket.h#includenetinet/in.h#includearpa/inet.h#includestring.husing namespace std;#define CHECK_RET(q) if((q) false){return -1;}class TcpSocket{ public: TcpSocket():_sockfd(-1) {} ~TcpSocket(){} bool Socket() { _sockfd socket(AF_INET,SOCK_STREAM,IPPROTO_TCP); if(_sockfd 0) { cout socket error endl; return false; } return true; } bool Bind(string ip, uint16_t port) { struct sockaddr_in addr; addr.sin_family AF_INET; addr.sin_port htons(port); addr.sin_addr.s_addr inet_addr(ip.c_str()); socklen_t len sizeof(struct sockaddr_in); int ret bind(_sockfd, (struct sockaddr*)addr, len); if(ret 0) { cout bind error endl; return false; } return true; } //开始监听并且设置服务端的同一时间最大并发连接数 bool Listen(int baklog 5) { //int listen(int sockfd, int backlog); //sockfd: 套接字描述符 //backlog: 同一时间最大连接数设置内核中已完成连接的最大节点数 int ret listen(_sockfd, baklog); if(ret 0) { cout Listen error endl; return false; } return true; } //获取连接成功客户端socket并且返回客户端的地址信息 bool Accept(TcpSocket sock, struct sockaddr_in *addr NULL) { //int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen); //sockfd: 套接字描述符 //addr: 用于存储客户端地址信息 //addrlen: 用于设置想要的地址长度和保存实际的地址长度 //返回值 为客户端连接新建的socket描述符 //接下来与客户端的通信都是通过这个新的描述符实现的 struct sockaddr_in _addr; socklen_t len sizeof(struct sockaddr_in); int newfd accept(_sockfd, (struct sockaddr*)_addr, len); if(newfd 0) { cout Accept error endl; return false; } sock.SetFd(newfd); if(addr ! NULL) { memcpy(addr, _addr, len); } return true; } //客户端向服务端发起连接请求 bool Connect(string ip, uint16_t port) { //int connect(int sockfd, const struct sockaddr *addr,socklen_t addrlen); //sockfd: 套接字描述符 //addr: 服务端监听地址信息 //addrlen: 地址信息长度 struct sockaddr_in addr; addr.sin_family AF_INET; addr.sin_port htons(port); addr.sin_addr.s_addr inet_addr(ip.c_str()); socklen_t len sizeof(struct sockaddr_in); int ret connect(_sockfd,(struct sockaddr*)addr, len); //cout ip port ret 1 endl; if(ret 0) { cout connect error endl; return false; } cout 来了老弟 endl; return true; } //通信接口tcp服务端也可以直接发送数据因为连接已经发送成功 bool Recv(string buff) { //ssize_t recv(int sockfd, void *buf, size_t len, int flags); //sockfd: 套接字描述符 //buf: 接收的数据存储 //len: 想要接收的数据长度 //flags: 0 默认是阻塞接收 // MSG_PEEK 接收数据但是数据不从接收缓冲区中移除 探测性接收 //返回值 成功返回实际接收字节数错误返回的-1对端已经关闭了连接返回0 char tmp[1024] {0}; int ret recv(_sockfd, tmp, 1024, 0); if(ret 0) { cout peer shutdown endl; return false; } else if(ret 0) { cout recv error endl; return false; } buff.assign(tmp,ret); return true; } ssize_t Send(string buff) { //ssize_t send(int sockfd, const void *buf, size_t len, int flags); //返回值 成功就是实际发送的字节数 失败 -1 //如果连接已经断开发送就会触发异常导致进程退出 int ret send(_sockfd, buff.c_str(), buff.size(), 0); if(ret 0) { cout send error endl; return false; } return true; } bool Close() { close(_sockfd); _sockfd -1; return true; } void SetFd(int sockfd) { _sockfd sockfd; } private: int _sockfd;};/************************************************************************* *文件名: tcp_ser.cpp *作者: bean *邮箱: 17331372728163.com * 创建时间: Fri 24 May 2019 07:27:34 AM PDT * 备注:通过封装的TcpSocket类实现服务端程序 * 1、创建套接字 * 2、绑定地址信息 * 3、开始监听 * 4、获取连接成功的客户端新建socket * 5、通过新建的socket与客户端进行通信 * 6、关闭套接字 *************************************************************************/#includetcpsocket.hppint main(int argc, char* argv[]){ if(argc ! 3) { cout ./tcp_ser ip port endl; return -1; } string ip argv[1]; uint16_t port atoi(argv[2]); TcpSocket sock; CHECK_RET(sock.Socket()); CHECK_RET(sock.Bind(ip, port)); CHECK_RET(sock.Listen()); while(1) { //程序会卡在accept是应为用户无法获知客户端的新连接什么时候到来 //如果能知道什么时候盗垒就不会阻塞只需要在来的时候调用一次就行 TcpSocket client; if(sock.Accept(client) false) { continue; } while(1) { string buff; client.Recv(buff); cout Tcp-Client say: buff endl; buff.clear(); cout Tcp-Server say:; fflush(stdout); getline(cin,buff); client.Send(buff); } } sock.Close(); return 0;}/**************************************************************************文件名: tcp_ser.cpp*作者: bean*邮箱: 17331372728163.com* 创建时间: Fri 24 May 2019 07:27:34 AM PDT* 备注:通过封装的TcpSocket类实现服务端程序* 1、创建套接字* 2、绑定地址信息* 3、开始监听* 4、获取连接成功的客户端新建socket* 5、通过新建的socket与客户端进行通信* 6、关闭套接字*************************************************************************/#includetcpsocket.hpp#includesignal.h#includesys/wait.hvoid sigcb(int no){ while(waitpid(-1, NULL, WNOHANG) 0);}int main(int argc, char* argv[]) if(argc ! 3) { cout ./tcp_ser ip port endl; return -1; } //如果多个进程同时退出了要等他处理完了再退出 signal(SIGCHLD, sigcb); string ip argv[1]; uint16_t port atoi(argv[2]); TcpSocket sock; CHECK_RET(sock.Socket()); CHECK_RET(sock.Bind(ip, port)); CHECK_RET(sock.Listen()); while(1) { //程序会卡在accept是应为用户无法获知客户端的新连接什么时候到来 //如果能知道什么时候盗垒就不会阻塞只需要在来的时候调用一次就行 TcpSocket client; if(sock.Accept(client) false) { continue; } //创建一个子进程负责聊天 int pid fork(); if(pid 0) { while(1) { string buff; client.Recv(buff); cout Client say: buff endl; cout Server asy:; fflush(stdout); cin buff; client.Send(buff); } } client.Close(); } sock.Close(); return 0;}基于UDP的socket
服务端流程
创建套接字文件描述符调用socket();设置服务器地址和监听关口初始化要绑定的网络地址结构。绑定监听端口调用bind()函数接收客户端数据调用recvfrom()函数向客户端发送数据调用sendto()函数向客户端发送数据关闭套接字调用close()函数释放资源。客户端流程
创建套接字文件描述符调用socket()设置服务器地址和端口struct sockaddr()向服务端发送数据调用sendto()接受服务端的数据调用recvfrom()关闭套接字调用close()函数释放资源。/*************************************************************************- 文件名: udp_socket.hpp- 作者: bean- 邮箱: 17331372728163.com- 创建时间: Thu 23 May 2019 04:20:18 AM PDT- 备注:分装一个udp的套接字接口类 实现 套接字创建、绑定地址、接收数据、发送数据、关闭套接字*************************************************************************/#includeiostream#includestring#includesys/socket.h#includeerrno.h#includenetinet/in.h#includearpa/inet.h#includestdio.h#includestdlib.h#includesys/types.h#includestring.h#includeunistd.h#define CHECK_RET(q) if((q) false){return -1;}using namespace std;class UdpSocket{ public: UdpSocket() { } ~UdpSocket() { } bool Socket() //创建套接字 { //int socket(int domain, int type, int protocol); //domain: 地址域确定通信范围 // AF_INET 表示使用IPV4网络协议 //type 套接字类型 // SOCK_STREAM 流式套接字----默认使用TCP // SOCK_DGRSM 数据包套接字--默认使用UDP //protocol: // 0 使用默认协议 // IPPROTO_TCP 6 TCP协议 // IPPROTO_UDP 17 UDP协议 //返回值套接字操作句柄---文件描述符 失败-1 _sock socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP); if(_sock 0) { perror(socket error); return false; } return true; } bool Bind(string ip, uint16_t port) //为套接字绑定地址信息 { struct sockaddr_in addr; addr.sin_family AF_INET; //因为网络通信使用大端字节序因此端口和IP地址信息都要转换成网络字节序 //uint16_t htons(uint16_t hostshort); // 将一个16为数据从主机字节序转换为网络字节序 //uint32_t htonl(uint32_t hostlong); //将一个32为数据从主机字节序转换为网络字节序 //不能使用htonl因为端口只有2的字节由于htonl是两个字节来转换的所以经htonl后还是原来的 addr.sin_port htons(port); //in_addr_t inet_addr(const char *cp); //将字符串点分十进制IP地址转换为网络字节序的整数IP地址 addr.sin_addr.s_addr inet_addr(ip.c_str()); //int bind(int sockfd, const struct sockaddr *addr,socklen_t addrlen); //sockfd: 创建套接字返回套接字描述符 //addr: 要绑定的地址信息 //addrlen: 地址信息长度 //返回值 成功0 失败-1 socklen_t len sizeof(struct sockaddr_in); int ret bind(_sock, (struct sockaddr*)addr, len); if(ret 0) { perror(Bind error); return -1; } return true; } bool Recv(string buf, sockaddr_in *_addr NULL) //接收数据 { //recvfrom(int sockfd, void *buf, size_t len, int flags, struct sockaddr *src_addr, socklen_t *addrlen); //sockfd: 套接字描述符 //buf: 用于保存接收的数据 //len: 要接受的数据长度 //flags: 默认0表示阻塞接收没有数据就阻塞 //src_addr: 发送端的地址信息 //addelen: 用于获取地址信息长度输入输出型参数 //返回值 实际接收数据长度错误返回-1 char tmp[1024] {0}; struct sockaddr_in addr; socklen_t len sizeof(struct sockaddr_in); int ret recvfrom(_sock, tmp, 1024, 0,(struct sockaddr*)addr, len); if(ret 0) { perror(recvfrom error); return false; } buf.assign(tmp, ret); //从tmp中拷贝获取的实际长度到buf中 if(_addr ! NULL)//如果用户想要获取发送端的地址这是_addr就不为空这时就将获取到的地址拷贝到_addr中 memcpy(_addr,addr,len); return true; } bool Send(string buf, struct sockaddr_in addr) //发送数据 { //sendto(int sockfd, void *buf, size_t len, int flags,struct sockaddr *dest_addr, socklen_t addrlen); //dest_addr: 目的端地址信息 //addrlen: 发送地址信息长度 socklen_t len sizeof(struct sockaddr_in); int ret sendto(_sock, buf.c_str(), buf.size(), 0,(struct sockaddr*)addr, len); if(ret 0) { perror(sendto error); return false; } return true; } bool Close() //关闭套接字 { close(_sock); _sock -1; return true; } private: int _sock;};/*************************************************************************- 文件名: udp_ser.cpp- 作者: bean- 邮箱: 17331372728163.com- 创建时间: Thu 23 May 2019 04:08:16 AM PDT- 备注:使用UdpSock类完胜UDP服务端程序*************************************************************************/#includeudp_socket.hppint main(int argc, char *argv[]){ if(argc ! 3) { cout ./dup_srv ip port endl; return -1; } string ip argv[1]; uint16_t port atoi(argv[2]); UdpSocket sock; //创建套接字 CHECK_RET(sock.Socket()); CHECK_RET(sock.Bind(ip, port)); while(1) { string buff; struct sockaddr_in c_addr; sock.Recv(buff, c_addr); cout client asy: buff.c_str() endl; cout server say:; fflush(stdout); getline(cin, buff); sock.Send(buff, c_addr); } sock.Close(); return 0;}/*************************************************************************- 文件名: udp_cli.cpp- 作者: bean- 邮箱: 17331372728163.com- 创建时间: Fri 24 May 2019 05:06:34 AM PDT- 备注: 通过udpsocket实现客户端程序*************************************************************************/#include udp_socket.hppint main(int argc, char* argv[]){ if(argc ! 3) { cout ./dup_cli ip port endl; return -1; } string ip argv[1]; uint16_t port atoi(argv[2]); UdpSocket sock; CHECK_RET(sock.Socket()); struct sockaddr_in s_addr; s_addr.sin_family AF_INET; s_addr.sin_port htons(port); s_addr.sin_addr.s_addr inet_addr(ip.c_str()); while(1) { string buff; cout client say:; getline(cin, buff); sock.Send(buff, s_addr); buff.clear(); sock.Recv(buff); cout server say: buff endl; } sock.Close(); return 0;}四、应用层的协议
基于TCP的有FTP、Telnet、SMTP、HTTP、POP3与DNS 基于UDP的有TFTP、SNMP与DNS 其中DNS既可以基于TCP也可以基于UDP。 FTP(File Transfer Protocol)文本传输协议 端口号 20 和21一个端口用于控制一个端口用于传输数据 Telnet端口号为23功能远程管理而在Linux中为SSH 端口号为22 SMTP: 发送邮件 TCP25 POP3接收邮件TCP:110 HTTP:超文本传输协议 TCP:80 HTTPS相对于HTTP安全 对数据包进行加密 TCP43 DNS域名解析服务 网络下标如果出现谈好很可能是DNS配置不对 TCP UDP:53 TFTP简单文件传输协议 早先FTP服务器代码太大了相对于服务器的容量来说所以主要传输一些小文件的时候就是用TFTP对于网络设备的维护一直使用 端口号为69 五、HTTP协议
HTTP协议超文本传输协议是互联网上引用最广泛的一种网络协议所有的www文件都要必须遵守这个标准。HTTP和TCp是不冲突的HTTP定义在应用层、TCP是在传输层解决的是传输层的逻辑。HTTP使用TCP不使用UDP是因为打开一个网页需要传送很多的数据而TCP提供传输控制按顺序数字数据和错误纠正并且保证数据的可靠传输。
URL、URI、URN的区别
URI用来唯一标识一个资源。由URL和URN组成。
URL统一资源定位通过描述资源的位置来标识资源
URN通过名字来标识资源与其位置没有关系及时资源的位置发生了变化URN也不会变化
请求报文格式请求行、请求头部、请求正文
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TPGBDTCi-1637763958112)(D:/%E6%9C%89%E9%81%93%E7%AC%94%E8%AE%B0/%E6%9C%89%E9%81%93%E6%96%87%E4%BB%B6/qqFD408D4C0254F01133B894C843A4BA78/3bcc5219fdc64197a7027c676ad4a85f/clipboard.png)]
请求行
请求方法GET、HEAD、PUT、POST、TRACE、OPTIONS、DELETE
URL通过描述资源的位置来标识资源。
协议版本常见有1.0和1.1
常见的请求头
请求头部
请求头部为请求报文添加了一些附加信息由“名/值”组成每行一对名和值之间使用冒号分割
常见的请求头
请求头说明Host接受请求的服务器地址可以是IP:端口号也可以是域名User-Agent发送请求的应用程序名称Connection指定与连接相关的属性如Connection:Keep-AliveAccept-Charset通知服务端可以发送的编码格式Accept-Encoding通知服务端可以发送的数据压缩格式Accept-Language通知服务端可以发送的语言
请求头部的最后会有一个空行表示请求头部结束接下来为请求报文这一行必不可少
请求正文
响应报文格式
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ppe4AVAq-1637763958113)(D:/%E6%9C%89%E9%81%93%E7%AC%94%E8%AE%B0/%E6%9C%89%E9%81%93%E6%96%87%E4%BB%B6/qqFD408D4C0254F01133B894C843A4BA78/e011fb9e44af4a808701792c293fb77c/clipboard.png)]
状态行
协议版本
状态码100 ~ 199信息状态码1.1200~299表示成功300 ~ 399资源重定向 400 ~ 499 表示客户端请求出错 500 ~ 599表示服务端出错。
常见状态码
状态码状态说明200响应成功301永久重定向搜索引擎将删除原地址保留重定向地址302暂时重定向重定向地址由响应投中的Locaition属性指定由于搜索引擎的判定问题较为复杂的URL容易被其他的网站使用更为精简的URL及302重定向劫持304缓冲文件并未过期还可以继续使用无需再次从服务端获取400客户端请求语法错误不能被服务器识别403服务器收到了请求但是拒绝提供服务404请求的资源不存在500服务器的内部错误
响应头部
与请求头部类似为响应报文添加了一些附加信息
响应头说明Server服务器应用程序软件的名称和版本Content-Type响应正文的类型是图片还是二进制字符串Content-Length响应正文长度Content-Charset响应正文使用的编码Content-Encoding响应正文使用的数据压缩格式Content-Language响应正文使用的语言
六、请求方法
HTTP1.0中定义了三种请求方法GET,POST,HEAD方法。
HTTP1.1中新加了五种请求方法OPTIONS,PUT,DELETE,TRACE,CONNECT
常见的请求方法
序号方法描述1GET请求指定的页面信息并返回实体主体2HEAD类似于GET请求只不过返回的响应中没有具体的内容用于获取报头3POST向指定的资源提交数据进行处理请求。数据被包含在请求体中POST请求可能会导致新资源的建立或已有资源的修改。4PUT从客户端向服务器传送的数据取代指定的文档内容。5DELETE请求服务器删除指定的页面。6CONNECTHTTP/1.1协议中预留该能够将连接改为管道方式的代理服务器7OPTIONS允许客户端查看服务器的性能8TRACE回显服务器收到的请求主要用于测试或诊断
七、GET与POST比较
本质区别
get是从指定资源中获取数据
post是向指定资源中提交将要被处理的数据
1、生成方式
get可以直接在URL地址栏中输入URL还可以网页中的超链接生成
post只知道一种就是将html中的form标签的method属性改为post
2、数据的传输方式
GET和POST只是HTTP协议中的两种请求方式而HTTP是基于TCP/IP的应用层协议所以用的都是同一个传输层的协议所以在传输上没有区别。
在报文格式上不带参数时最大的区别就是第一行方法名不同POST方法请求报文第一行是这样的POST/url HTTP/1.1 GET方法请求报文第一行是这样的 GET/url HTTP/1.1
带参数的区别是GET请求的数据会附加在URL之后以****分割URL多个参数使用连接URL的编码格式采用的是ASCII编码也就是说所有的非ASCII字符都要编码之后才可以传输POST请求POST请求会把请求的数据放置在HTTP请求包的包体中。所以说GET请求的数据会暴露在地址栏中但是POST请求不会所以POST相对于GET来说相对安全但是如果是使用HTTP那么他们都是不安全的因为HTTP是明文传输没有对数据进行加密也就是说POST请求的数据也是可见的但是使用HTTPSPOST的数据就是安全的。
3、传输数据的大小
在HTTP规范中没有对URL的长度和传输的数据进行限制但是在实际的开发中特定的浏览器和服务器对URL的长度是有限制的所以在使用GET请求的时候传输的数据就会受URL的长度限制一般是不超过2KB但是对于POST来说理论上来说并不会受到URL的限制但是实际上各个服务器都会规定对POST提交的数据大小进行限制。
在实际开发中对URL的长度进行限制是因为对于服务器来说URL长了是一种负担如果一个没有多少数据的会话但是被人恶意的构造了一个几M大小的URL并且不停的访问服务器那么服务器的并发数显然就会下降。还有一种攻击就是将Content-Length设置为一个很大的数然后只给服务器发送很短的数据这时候服务器就会进行等待只有等待超时了服务器才可以继续做其他的这样也会降低服务器的效率所以要给URL的长度进行限制。
GET在浏览器回退时是无害的POST会再次提交请求。。
GET请求只能进行url编码而POST支持多种编码方式。
GET请求参数会被完整保留在浏览器历史记录里而POST中的参数不会被保留。
GET只接受ASCII字符的参数的数据类型而POST没有限制
八、HTTP1.0和HTTP1.1的区别
主要有五个方面的区别长连接、HOST域、宽带优化、消息传递、缓存
1、长连接
长连接指的是传输完成了保持TCP连接不断开等待在同域名下继续用这个通道传输数据反之就是短连接。
HTTP1.1支持长连接和请求的流水线处理并且默认使用长连接只有介入“connectionclose”才断开连接。
HTTP1.0默认使用短连接规定客户端和服务器只能保持短暂的连接客户端的每次请求都需要与到服务端建立一个TCP连接服务器完成请求处理后立即断开TCP连接服务器不跟踪客户端也不记录之前的请求。
如果HTTP1.0想要建立长连接可以在请求消息中包含ConnectionKeep-Alive头域如果服务器想要维持这条连接在相应的消息中也会包含一个ConnectionKeep-Alive的头域。
2、HOST域
HTTP1.1在Request消息头里多了一个Host域并且是必须传的HTTP1.0中没有这个域。
在HTTP1.0中认为每个服务器都绑定唯一一个IP地址所以在请求消息中的URL并没有传递主机名。但随着虚拟主机技术的发展在一台物理服务器上可以存在多个虚拟主机并且他们共享一个IP地址。
HTTP1.1的请求小和响应消息都应支持Host头域且请求消息中如果没有Host头域汇报稿一个错误状态码400并且服务器应该接受一绝对路径标记的资源请求。
3、带宽优化
HTTP1.0中存在一些浪费宽带的现象 比如说客户端只是需要某个对象的一部分资源但是服务器将整个对象都传送过来了。又比如下载大文件时不支持断点续传功能所以在发生断链后不得不重新下载完整的包。
HTTP1.1中在请求消息中引入了range头域它支持之请求资源的某个部分。他在响应消息中Content-Range头域声明了返回的这部分对象的偏移值和长度。如果服务器相应地反悔了对象所请求范围的内容则响应状态码为206它可以防止Cache将响应误以为是完整的一个对象。
HTTP支持只发送header信息如果服务器认为客户端有权限请求服务器则返回100否则返回401只有客户端接收到了100才开始把请求body发送到服务器。如果接收到401客户端就可以不用发送请求body了这样可以节约带宽。
4、消息传递
HTTP消息中可以包含任意长度的尸体通常他们使用Content-Length来给出消息结束的标志。但是对于很多动态产生的响应只能通过缓冲完整的消息来判断消息的大小但这样会加大延迟。如果不适用长连接还可以通过连接关闭的信号来判定一个消息的结束。
HTTP1.1zongoing引入了Chunke来解决上面的这个问题发送方将消息分割成若干个任意大小的数据块每个数据块在发送时都会附上块的长度最右用一个零长度的块作为消息的结束标志。这种方法允许发送方只缓冲消息的一个片段还可以避免缓冲整个消息带来的过载。
在HTTP1.0中有一个Content-MD5的头域要计算这个头域需要发送方缓冲完整个消息后才能进行这在HTTP1.1中采用chunked分块传递的消息在最后一个块结束后会再传递一个拖尾它包含一个或多个头域这些头域是发送方在传递完所有块之后在计算出的值。
5、缓存
HTTP1.0中使用Expire头域来判断资源是否是新资源并使用条件请求来判断资源是否仍然有效。
HTTP1.1在1.0的基础上加入了一些新特性当缓存对象的生命超过了周期编程stale的时候不需要直接抛弃stale对象而是与源服务器进行重新激活。
九、HTTP流水线技术
HTTP流水线技术指的是在一个TCP链接内多个HTTP请求可以并行客户端不用等待上一次请求的结果返回就可以发出下一次的请求但是服务器必须要按照接收到客户端的请求的顺序依次会送响应的结果以保证客户端可以区分出每次请求响应的内容。使用HTTP流水线技术必须要求客户端和服务端都要支持目前有部分浏览器完全支持而服务端的支持仅需要按照HTTP请求顺序正确返回也就是先来先服务模式只要服务器能够正确处理使用流水线技术的客户端的请求那么服务器就算是支持了HTTP流水线技术。
GET 用于获取信息是无副作用的是幂等的且可缓存 POST 用于修改服务器上的数据有副作用非幂等不可缓存
十、HTTP无状态问题
http是无状态协议无状态也就是对于十五处理没有记忆能力。缺少状态意味着如果后续处理需要之前的信息。使用cookie和session来解决无状态问题。
十一、cookie和session的区别
cookie
是客户端技术程序把每个用户的数据以cookie的形式写给用户各自的浏览器。当用户使用浏览器再去访问服务器的时候就会带着各自的数据过去这样就服务器就知道当前是哪个用户并处理对应的数据。会话cookie保存在浏览器的内存中浏览器关闭后cookie就消失了持久化cookie是保存在本地的磁盘上一般会有一定的过期时间。
session
是服务器技术利用这个技术服务器可以为每个用户的浏览器创建一个独立的session对象并且每个session都有自己唯一对应的ID可以把各自的数据保存在自己的session中这样当用户再去访问服务器的时候服务器就可以用当前用户的session中取出数据为之服务。session都有过期时间如果一段时间没有更新数据库就会消失。
区别
1、cookie和session都是会话技术cookie数据存放在客户端session的数据存放在服务器。
2、cookie不是很安全可以对本地存放的cookie进行cookie欺骗考虑到安全应该使用session。
3、session会在一定的时间内保存在服务器中当访问增多会比较占用服务器性能所有考虑到减轻服务器的负载应该使用cookie
4、登陆注册等重要信息要存放在session中其他的信息可以保存在cookie中
5、Cookie 只能保存ASCII字符串如果是Unicode字符或者二进制数据需要先进行编码。Session能够存取很多类型的数据包括String、Integer、List、Map等。
十九、怎么让客户端和服务端一直保持连接
通情况下tcp的连接是一直保持很长时间但是有可能这个链接会一直空闲着这样会造成资源浪费所以TCP就提供了保活机制和心跳报文
保活机制
也就是keepalive在客户端和服务端都可以设置通常是服务端设置的。保活时长一般是2小时如果这个tcp连接空闲了两个小时这个保活计时器超时服务端会向客户端发送一个探测报文这时客户端通常处于这么几个状态。
1、客户端处于正常状态收到探测报文后发送了响应报文服务端知道客户端是正常的将保活计时器复位。
2、客户端已经崩溃正在关机或者重启没有响应服务端的探测报文 服务端由于没有收到回复会每个75秒发送一个探测报文如果连续发送10探测报文都没有响应就会认为客户端挂了会关闭TCP连接。
3、客户端已经重启并且正常运行了但是在重启之前关闭了tcp这个客户端收到探测报文回应一个RST服务端收到这个报文将TCP连接关闭。
4、客户端正常运行但是接收不到服务端的报文可以说是和情况2是一样的服务端并不能去放是网络问题还是客户端的问题所以同样会将连接关闭。
心跳报文
每隔一段时间向对端发送一个较小的数据包通知对方自己在线并传送一些可能必要的数据包并且定时检测对端返回的数据如果连续几次没有在规定的时间中收到回复则判断对端已经掉线然后做进一步处理这个方法适合客户端在应用层开一个线程发送心跳包检测对端情况。
