一些c++需要掌握的知识点
虚函数与纯虚函数的比较
- 虚函数为了重载和多态的需要,在基类中是有定义的,即便定义是空,所以子类中可以重写也可以不写基类中的此函数。
- 纯虚函数在基类中是没有定义的,必须在子类中加以实现。
- 虚拟函数就是为了对“如果你以一个基础类指针指向一个衍生类对象,那么通过该指针,你只能访问基础类定义的成员函数”这条规则反其道而行之的设计。
- 多态的真正体现就是基类指针访问子类对象。
- 虚函数动态联编,虚函数表。
在函数编译过程中,父类子类中的成员函数的名字是不一样的,可以区分,然后函数如果调用成员变量,函数会默认传进去一个该类的指针,进行调用。
重载、覆盖(重写)、隐藏区别
重载, 参数不同的同名函数,不关心返回值。并不是两个函数的名字相同就能构成重载。全局函数和类的成员函数同名不算重载,因为函数的作用域不同。对于函数重载,out(float a)和out( int a) 当调用 out(1)时,是正确的, 当调用out(0.5)时,编译错误,因为编译器无法确定应该如何进行类型转换。
隐藏, 是指派生类的函数屏蔽了与其同名的基类函数,注意只要同名函数,不管参数列表是否相同,基类函数都会被隐藏。
覆盖, 重写的基类中被重写的函数必须有virtual修饰。
函数重载只是动态的多态性,在编译阶段,给不同的函数不同的函数名,而虚函数实现运行时多态。
重载、覆盖、隐藏补充
重载
成员函数被重载的特征:
(1)相同的范围(在同一个类中);
(2)函数名字相同;
(3)参数不同;
(4)virtual关键字可有可无。覆盖
覆盖是指派生类函数覆盖基类函数,特征是:
(1)不同的范围(分别位于派生类与基类);
(2)函数名字相同;
(3)参数相同;
(4)基类函数必须有virtual关键字。令人迷惑的隐藏规则
本来仅仅区别重载与覆盖并不算困难,但是C++的隐藏规则使问题复杂性陡然增加。这里“隐藏”是指派生类的函数屏蔽了与其同名的基类函数,规则如下:
(1)如果派生类的函数与基类的函数同名,但是参数不同。此时,不论有无virtual关键字,基类的函数将被隐藏(注意别与重载混淆)。
(2)如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有virtual关键字。此时,基类的函数被隐藏(注意别与覆盖混淆)。
总结起来就是,如果同一个类中,是重载,父类和子类,函数名字相同参数相同,有virtual是覆盖,没有就是隐藏。
内联函数
- 在函数前面加上inline进行声明。
- 内联函数在函数调用位置处直接展开。
- 内联函数可以避免函数调用时的开销,保存寄存器恢复寄存器之类的。适合于规模较小的函数。
- 关键字inline必须与函数定义体放在一起才能使函数成为内联,仅将inline放在函数声明前面不起任何作用。inline是一种“用于实现的关键字”,而不是一种“用于声明的关键字”。
内联函数相比较于 #define定义函数 aa() 有什么优点?
- 代码放到符号表中,用到的时候直接进行替换。
- 编译器可以对它进行参数检查。
- inline可以是类的成员函数,对类内成员进行访问。
函数指针(c++ primer第五版,p221)
const 成员函数
- const 放在函数的后面,只能用在类中,代表该函数不可修改类中变量。
- const aa(类) 只能调用const函数。
父类指针指向子类对象问题
- 到底调用那个函数要根据指针的原型来确定,而不是根据指针实际指向的对象类型确定,即指针是什么类型,就调用什么类型的函数。
- 虚函数除外,虚函数调用最根源的函数,对象是什么类型,就调用相应的函数。
c++各个存储区
在C++中,内存分成5个区,他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
链接:http://www.cnblogs.com/hanyonglu/archive/2011/04/12/2014212.html
接7,对static的讨论
- static 放在静态存储区,并不随着退出函数释放空间。
- 规定作用域。
如下,输出 10 12 131
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void fun()
{
static int a = 10;
cout << "fun " << a << endl;
}
void fun2()
{
static int b = 12;
cout << "fun2 " << b++ << endl;
}
int main()
{
fun();
fun2();
fun2();
getchar();
return 0;
} - char st[10] = “abcde”,在内存中存在两份拷贝,一份在常量存储区上,一份在栈上,函数退出之后,栈上内存释放,如果想让栈上的存储区不释放,可以将其声明为static 放在静态存储区上。
如何去掉const变量的const特性。
利用const_cast去除掉const的特性。
static_cast是强制类型转换的关键字,类似于c语言中的(int)a,static_cast a 等价于 (int)a
程序错误处理
对输入输出,用断言,用异常处理机制。
c++ 构造函数,拷贝构造函数
问题引入:
1 | class A; |
解答:
A b = a 与 A b(a) 代表着相同的意义,这里调用拷贝构造函数,拷贝构造函数如果没有重载的话,默认为浅拷贝。
构造函数调用的次序,先父类,子类,析构函数的顺序,先子类后父类。
c++中 private protected public
- private成员只能被本类成员(类内)和友元访问,不能被派生类访问。
- protected成员可以被派生类访问。
- public继承:基类public成员,protected成员,private成员的访问属性在派生类中分别变成:public, protected, private
- protected继承:基类public成员,protected成员,private成员的访问属性在派生类中分别变成:protected, protected, private
- private继承:基类public成员,protected成员,private成员的访问属性在派生类中分别变成:private, private, private
当数组作为函数参数输入时,数组自动转化为指针,sizeof = 4 。
const char * p1等 容易混淆的概念
- const char * p1 = “hello”;
- char *const p2 = “hello”;
- *翻译成point to ,从右往左读,便可以知道这个是什么。
- 指针常量,是指向常量的指针。
- 常量指针,是指针就是个常量。
哪些运算符不能被重载
- ::
- .*
- .
- ? :
类方法,指的是类的静态方法,即static关键字修饰的方法。
静态方法只能使用该静态方法所在类的静态数据成员和静态方法。这是因为使用静态方法时,该静态方法所在类可能还没有对象。静态方法中没有this指针。
总结:
- 出现在类体外的函数不能指定关键字static;
- 静态成员之间可以互相访问,包括静态成员函数访问静态数据成员和访问静态成员函数;
- 非静态成员函数可以任意地访问静态成员函数和静态数据成员;
- 静态成员函数不能访问非静态成员函数和非静态数据成员;
- 由于没有this指针的额外开销,因此静态成员函数与类的全局函数相比,速度上会有少许的增长;静态成员函数里面不允许使用this指针。
- 调用静态成员函数,可以用成员访问操作符(.)和(->)为一个类的对象或指向类对象的指调用静态成员函数。
- 静态成员函数,如果是private,在类外面是不允许调用的。
hash桶
- hash表关键点2个: 1 hash函数,2冲突处理。
- hash函数可以有很多,取余数等。
- hash冲突处理,1次探测,2次探测,链表(hash桶)法。
reinterpret_cast (expression)
reinterpret_cast运算符是用来处理无关类型之间的转换;它会产生一个新的值,这个值会有与原始参数(expressoin)有完全相同的比特位。
运算符重载
- c++重载运算符的时候,返回的是引用还是值,这个取决于返回运算符本身,如果需要返回运算符本身的值就是引用(即左值)【比如,=系列,+=,-=,*=,/= 】,如果不能返回值本身就需要返回值(如:= - * /等)。
- 在类外部时候,重载运算符如下,声明为友元函数。这个如果不声明为友元,放在类内,codeblocks会报错,类内只接受一个参数或者0个参数
如:类外 friend classType operator+(classType& left, classType& right);
类内 classType operator+(classType& right );
递归栈问题,可以采用尾递归解决
new一个内存然后free会产生什么问题
- delete会调用析构函数,free不会调用,会出现内存溢出问题。
- 如果用free释放“new创建的动态对象”,那么该对象因无法执行析构函数而可能导致程序出错。如果用delete释放“malloc申请的动态内存”,理论上讲程序不会出错,但是该程序的可读性很差。所以new/delete必须配对使用,malloc/free也一样。
new,malloc最大分配多大空间。
理论上是内存的大小,如果32位,最大就是4G,但是实际中,会小一些,因为运行时的限制。
运行时,栈空间多大?
跟os有关。比如windows,在链接时确定栈的大小(可以由连接器的选项指定,如果未指定则用默认值1MB) VS2013开辟的默认栈空间是1M。
static全局变量与普通全局变量的一个区别
这两者的区别在于非静态全局变量的作用域是整个源程序,当一个源程序由多个源文件组成时,非静态的全局变量在各个源文件中都是有效的。而静态全局变量则限制了其作用域, 即只在定义该变量的源文件内有效, 在同一源程序的其它源文件中不能使用它。
全局变量,静态全局变量,默认初值为0 或者 null
全局变量和static变量就是这种方式分配内存的。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。
编译原理理解记录
- 程序编写到运行需要经历 预编译,编译,链接,生成exe等阶段。.cpp与.h的的作用在于.h中进行声明,cpp在编译的时候,遇到声明会做一个标记,然后在链接的时候会找到相应的函数。
每个cpp是单独编译的。不然编译顺序不同,结果不同了。 - .h中不要包含变量的定义,因为定义后,如果多个cpp引用这个变量,在链接阶段会出现重复定义
一个工程中,是不会出现一模一样的函数定义的。那样在链接的时候会报错。
string find()返回类型
- string::size_type 为find返回的类型,如果只是使用int,容易出错,对于跨机器效果不好。
- size_type为string和vector的find的返回类型,需要注意。
- npos为find的失败的返回值。
const修饰类中变量问题
非常重要的一点,也是常犯的错误,有时我们希望某些常量只在类中有效,所以想当然地觉得应该用const修饰数据成员来实现。但是const数据成员只在某个对象生存期内是常量,而对于整个类而言却是可变的,因为类可以创建多个对象,不同的对象const 数据成员的值可以不同。
所以:不能在类声明中初始化const数据成员。因为类的对象未被创建时,编译器不知道SIZE的值是什么。const数据成员的初始化只能在类构造函数的初始化表中进行。
如果想建立在整个类中都恒定的常量。const数据成员是完成不了滴,应该用类中的枚举常量来实现。
1 | class A |
枚举常量不会占用对象的存储空间,它们在编译时被全部求值。枚举常量的缺点是:它的隐含数据类型是整数,其最大值有限,且不能表示浮点数(如PI=3.14159)。
如果想定义非int型变量怎么办呢?可以使用静态常量:static const int size.
关于引用有一些非常重要的规则
- 引用被创建的同时必须被初始化(指针则可以在任何时候被初始化)。
- 不能有NULL引用,引用必须与合法的存储单元关联(指针则可以是NULL)。
- 一旦引用被初始化,就不能改变引用的关系(指针则可以随时改变所指的对象)。
- 引用没有const。
- 引用是受限了的指针,只允许取内容,不能改变所指向。
编程规范
编程时候要注意,分配内存的时候检查是否分配成功,并且初始化,释放的时候,要对其指向null,避免产生野指针。
常量存储区的数据不能更改
数组名是指针常量,不能更改指向
指针与内存
- 指针消亡了,并不表示它所指的内存会被自动释放。
- 内存被释放了,并不表示指针会消亡或者成了NULL指针。
new A 与 new A()区别
new A 与 new A() 都是调用默认构造函数,但是当类型只有 int 等pod类型时候,初始化不同版本可能会不同。
multable修饰变量一直可变, 用在类中被const修饰的函数中。
函数的参数缺省值只能出现在函数的声明中,而不能出现在定义体中。
define和内联函数容易产生的错误
1 |
|
构造函数
- 如果类存在继承关系,派生类必须在其初始化表里调用基类的构造函数。
- 初始化表中调用构造函数,如下例:
1
2
3
4B::B(int x, int y): A(x) // 在初始化表里调用A的构造函数
{
…
} - 成员对象初始化的次序完全不受它们在初始化表中次序的影响,只由成员对象在类中声明的次序决定。这是因为类的声明是唯一的,而类的构造函数可以有多个,因此会有多个不同次序的初始化表。如果成员对象按照初始化表的次序进行构造,这将导致析构函数无法得到唯一的逆序。
拷贝构造函数与赋值函数
1 | String a(“hello”); |
以string类为例,拷贝构造函数与赋值函数的步骤, string类要掌握
1 | String::String(const char *str) // String的普通构造函数 |
基类与派生类构造函数
- 基类的构造函数、析构函数、赋值函数都不能被派生类继承。如果类之间存在继承关系,在编写上述基本函数时应注意以下事项:
- 派生类的构造函数应在其初始化表里调用基类的构造函数。
- 基类与派生类的析构函数应该为虚(即加virtual关键字)。
说说拷贝构造函数和赋值运算符
拷贝构造函数和赋值运算符有以下两个不同之处:
- 拷贝构造函数生成新的类对象,而赋值运算符不能。
- 由于拷贝构造函数是直接构造一个新的类对象,所以在初始化这个对象之前不用检验源对象是否和新建对象相同。而赋值运算符则需要这个操作,另外赋值运算中如果原来的对象中有内存分配要先把内存释放掉。
1 | 8、递归与非递归将链表反转 |
数组名和指针的区别
指针是一个变量,有自己对应的存储空间,而数组名仅仅是一个符号,不是变量,因而没有自己对应的存储空间。
构造函数能否为虚函数,为什么?
- 构造函数不能是虚函数。而且不能在构造函数中调用虚函数,因为那样实际执行的是父类的对应函数,因为自己还没有构造好。析构函数可以是虚函数,而且,在一个复杂类结构中,这往往是必须的。析构函数也可以是纯虚函数,但纯虚析构函数必须有定义体,因为析构函数的调用是在子类中隐含的。
- 虚函数的动态绑定特性是实现重载的关键技术,动态绑定根据实际的调用情况查询相应类的虚函数表,调用相应的虚函数。
- 析构函数如果不定义成虚函数,在用父类指针操作子类对象的时候,在析构的时候容易忘记调用析构函数。
成员函数通过什么来区分不同对象的成员数据?为什么它能够区分?
通过this指针来区分的, 因为它指向的是对象的首地址。
拷贝构造函数在哪几种情况下会被调用?
- 当类的一个对象去初始化该类的另一个对象时;
- 如果函数的形参是类的对象,调用函数进行形参和实参结合时;
- 如果函数的返回值是类对象,函数调用完成返回时。
流运算符为什么不能通过类的成员函数重载?一般怎么解决?
因为通过类的成员函数重载必须是运算符的第一个是自己,而对流运算的重载要求第一个参数是流对象。一般通过友元来解决。
虚拟函数与普通成员函数的区别?内联函数和构造函数能否为虚拟函数?
区别:
- 虚拟函数有virtual关键字,有虚拟指针和虚函数表,虚拟指针就是虚拟函数的接口,而普通成员函数没有。
- 内联函数和构造函数不能为虚拟函数。
全局变量可不可以定义在可被多个.C文件包含的头文件中?为什么?
答:可以,在不同的C文件中以static形式来声明同名全局变量。
可以在不同的C文件中声明同名的全局变量,前提是其中只能有一个C文件中对此变量赋初值,此时连接不会出错.
局部变量能否和全局变量重名?
答:能,局部会屏蔽全局。要用全局变量,需要使用”::” ;局部变量可以与全局变量同名,在函数内引用这个变量时,会用到同名的局部变量,而不会用到全局变量。对于有些编译器而言,在同一个函数内可以定义多个同名的局部变量,比如在两个循环体内都定义一个同名的局部变量,而那个局部变量的作用域就在那个循环体内。
海量处理(海量数据查找可以用hash表进行)
44.1:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
答:可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
分而治之/hash映射:
遍历文件a,对每个url求取映射,然后根据所取得的值将url分别存储到1000个小文件(a1)中。这样每个小文件的大约为300M。遍历文件b,采取和a相同的方式将url分别存储到1000小文件(b1)中。这样处理后,所有可能相同的url都在对应的小文件中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
hash_set统计:
求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。
卡特兰数问http://blog.csdn.net/han_xiaoyang/article/details/11938973
统计出现次数最多的数据
首先用hashmap统计出现的次数,然后用堆排序找出前n个高频对于大数统计,可以采用并发的方式进行。
10亿个整数,1G的内存,统计只出现一次的数
hash桶,先进1000个桶,然后再每个桶内判断。
海量数据排序,
利用位操作
电梯调度算法
问题:
电梯大家对于大家已经是很熟悉了,现在存在这样的问题,那就是在繁忙的上下班时间,在每层楼电梯都要停。这显然让很多办公室在高层的同志有点受不了。现在要求是这样:由于这个电梯楼层并不高,所以电梯只在一个楼层停,这样做电梯的每个人都在这个楼层走到自己想去的楼层。那么怎么知道电梯每次在哪个楼层停下来呢?在一楼的时候每个乘客选择自己的目的层,电梯可以快速的自动计算出应停的楼层。这个应停的楼层应该保证这次乘坐电梯的所有乘客的爬楼梯层数之和最少(包括上下楼)。
解法:
现在我们来更仔细的分析一下这个问题,看看怎么样优化一下。假设电梯停在第 i 层楼,我们计算出所有乘客总共爬楼梯的层数是Y。如果有N1个乘客想去的楼层在第 i 层之下,有N2个乘客正好想去的楼层是第 i 层,有N3个乘客想去的楼层在第 i 层之上。这个时候,重点来了:如果电梯改停在i-1层,所有目的地在第i - 1层以下的乘客可以少爬1层,总共少爬N1层,所有在i层及以上的乘客要多爬一层,总共多爬N2+N3层,这时总共需要爬Y-N1+N2+N3。
反之,如果电梯在i+1层停所有目的地在第 i 层以上的乘客可以少爬1层,总共少爬N3层,所有在 i 层及以下的乘客要多爬一层,总共多爬N1+N2层,这时总共需要爬Y+N1+N2-N3层。
可见,当N1 > N2+N3 时,电梯在第i-1层楼停更好;当N1+N2 < N3 时,电梯在i+1层停更好。其他情况在第i层更好。
如此一来,问题的解法就出来了,从第一层开始考察,计算各位乘客走的楼层的数目,然后根据N1,N2,N3之间的关系进行调整,知道找到最佳楼层,这样算法时间复杂度优化到了O(N)。
一个父类子类虚函数问题
1 | class A |
输出结果:F g F g f g
- (1)没啥说的,正常.
- (2)没啥说的,跟(1)一样,
- (3)类似于用B去初始化A,所有类型已经发生了变换,初始化结束之后,oA的类型就是A,也就不会调用B的虚函数了。