小冬找工作

[小冬找工作]-Cpp八股整理

CPP常见面试八股文整理

Posted by Lordon on April 7, 2021

关于

CPP知识点虽然没有JAVA那么多，但是想要学好还是不简单的.这里放上我平时整理的知识点，虽然此index更新不及时，但是跳转后的仓库是会一直更新到 找到满意的工作的~

C++新特性与C的区别

C++11 最常用的新特性如下：

  • auto关键字： 编译器可以根据初始值自动推导出类型。但是不能用于函数传参以及数组类型的推导

  • nullptr关键字： nullptr是一种特殊类型的字面值，它可以被转换成任意其它的指针类型；而NULL一般被宏定义为0，在遇到重载时可能会出现问题。

  • 智能指针： C++11新增了std::shared_ptr、std::weak_ptr等类型的智能指针，用于解决内存管理的问题。

  • 初始化列表： 使用初始化列表来对类对象进行初始化

    1

    AstructFunction(int a,int b):param1(a),param2(b){};

  • 右值引用：[最重要特性之一,包括移动语义+完美转发] 基于右值引用可以实现移动语义和完美转发，消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率.

    表现为 右值引用&&符号只能作用于右值(10、”sdf”等)且具有对右值修改的权限。

    移动语义 std::move(左值) // 将左值转化为右值,因为右值本身没有变量名，只有move之后才是右值
    完美转发 std::forward(10)// 按照原来的类型进行转发，原来的左值也成为右值。而将右值转化为左值这个根本不需要多余的操作。

    右值引用多用在函数形参中，既能够接受右值，又能够接受move转化过的左值，虽然一个引用也能用

1
2
3
4

int a = 1;     // a 是左值
int b = 2;     // b 是左值
int c = a + b; // + 需要右值，所以 a 和 b 被转换成右值
               // + 返回右值

  • atomic原子操作:

    目的是解决在并发程序中不加锁情况下,多线程对共享内存操作事发生错误的情况。在cuda编程中 有广泛使用。

    自旋锁:使用原子操作模拟互斥锁的行为就是自旋锁，自旋锁状态时程序员自己控制的

  • cbegin

新增STL容器array以及tuple

c++ 与 c 的区别

c是面向过程的语言(面向硬件编程)，c++是面向对象的语言(面向编译器)

同时C++对C进行了扩展,同时c是c++的子集，c可以不做修改地拿到c++使用。

参考智能车竞赛：为什么在嵌入式中多用c？

c++中的很多机制都会造成开销，相对于实时性要求高的嵌入式来说难以用到面型对象机制的许多方法，所以不采用.

~问就是兼容性好。

  • 具体体现在使用c写的底层好，兼容性强，并不会因为不同版本编译器而产生问题，这个是不用c++的原因所在，所以为什么c++是面向编译器编程的原因。

GCC与g++

两者什么区别?

首先说明：gcc 和 GCC 是两个不同的东西

GCC:GNU Compiler Collection(GUN 编译器集合)，它可以编译C、C++、JAV、Fortran、Pascal、Object-C、Ada等语言。

gcc是GCC中的GUN C Compiler（C 编译器）

g++是GCC中的GUN C++ Compiler（C++编译器）

另外

一个有趣的事实就是，就本质而言，gcc和g++并不是编译器，也不是编译器的集合，它们只是一种驱动器，根据参数中要编译的文件的类型，调用对应的GUN编译器而已，比如，用gcc编译一个c文件的话，会有以下几个步骤： 所以，更准确的说法是：

gcc调用了C compiler，而g++调用了C++ compiler

gcc和g++的主要区别

  1. 对于 *.c和*.cpp文件，gcc分别当做c和cpp文件编译（c和cpp的语法强度是不一样的）
  2. 对于 *.c和*.cpp文件，g++则统一当做cpp文件编译
  3. 使用g++编译文件时，g++会自动链接标准库STL，而gcc不会自动链接STL
  4. gcc在编译C文件时，可使用的预定义宏是比较少的
  5. gcc在编译cpp文件时/g++在编译c文件和cpp文件时（这时候gcc和g++调用的都是cpp文件的编译器），会加入一些额外的宏

编译过程

  1. 预编译 将所有的文件包含 宏定义与条件编译等带#的进行替换。 .i 文件
  2. 汇编 将预编译文件转化成汇编代码 包含语法词法的分析以及优化操作
  3. 编译 编成二进制文件
  4. 链接 可执行文件 就是将标识名字替换为函数的地址，反汇编可以看到

    STL-sort

  • STL中sort算法为什么选用插入排序+快排 而不用快排+其他呢？

STL中使用的sort为introsort,结合了快排/堆排序+插入排序的方法，其中快排与堆排序通过函数计算快排可拆分数的阈值， 当拆分段长度>16时采用递归。_RandomAccessIterator 类型数据是三点取中值的value取值方法重要体现

结合快排思想,当数据量大时采用Quick Sort，分段递归排序，一旦分段后的数据量小于某个门槛， 为避免QuickSort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。

总而言之：是快排+插入+堆排的组合方法 即【Introspective Sorting(内省式排序)】

其他部分比较

时间复杂度：最好最坏情况下平均时间复杂度

稳定性： 如果有相同数字，那么两个数字还会保持原来的位置，先后顺序不变

具体实现：sort.h

排序类型 时间复杂度 稳定性
冒泡 n2 稳定
选择 n2 不稳定
插入 n2 稳定
希尔 n1.3 不稳定
快排 nlogn 不稳定
归并 nlogn 稳定
堆排 nlogn 不稳定
基数排 n+k 稳定

选择排序(Selection sort)，插入排序(Insertion Sort)，冒泡排序(Bubble Sort)。 这三个排序是初学者必须知道的三个基本排序方式，且他们速度都不快 – O(n2)。

为什么STL中sort算法是快排+归并+插入的组合？

选择排序就不说了，最好情况复杂度也得O(N^2)，因为是完全遍历，且还是个不稳定的排序算法，直接淘汰。

那冒泡排序和插入排序相比较呢？

首先，他们都是稳定的排序算法，且最好情况下都是O(N^2)。然而Bubble Sort在“几近排序但尚未完成”的情况下是没多少改进作用的，所以选择了插入排序与快排的组合。 因为几近排好的情况下插入排序能够提前终止，如果比前面的数值大就可以跳过。

  • STL-sort部分源码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 阈值判断选择执行方式
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void __introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit,
_Compare __comp)
{
while (__last - __first > int(_S_threshold)) // 排序长度>16
{
if (__depth_limit == 0) // 不适用快排 可分割0层时改用堆排序
{
// 这里堆排序可以跳出循环  所以插入排序还要再判断一下长度
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
// 快排 找到下一轮递归中值的位置
_RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp);
// 对右侧部分[cut,last]进行递归排序  退出来之后对左侧继续排序
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
// 本循环中对左侧部分[first,cut]继续进行判断 长度小于16即采用插入排序
__last = __cut;
}
}

// sort source code 入口
template<typename _RandomAccessIterator, typename _Compare>
inline void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
if (__first != __last)
{
// 包含快排与 恶劣情况下的堆排序
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2, //对排序分割恶化情况进行判断 __lg(__last - __first) * 2 最大快排拆分数
__comp);
// 插入排序 几近完成 的情况下使用  长度小于16的时候
std::__final_insertion_sort(__first, __last, __comp);
}
}

STL-vector

reserve 与 resize区别：最大的在reserve只管扩充原vector，不管缩小，resize小了会擦除，大了会扩充。

shrink_to_fit:根据size()决定是否进行移动构造

push_back:没超容量在*end加，超范围则复制拷贝

pop_back:end不=begin 则前移

size：返回end-begin

emplace：原地插入迭代器位置

erase：将后面位置的内容拷贝过来

swap：创建临时变量，使用std::move进行交换

erase:将当前位置到最后的内容向前移一位 注意这里迭代器会失效 ite = nums.erase(ite);可有效避免

1
2
3
4
5

if(*ite == numsTarget){
    ite = nums.erase(ite);
else
    ite ++;
}

vector扩容问题

STL 的 vector 底层实现是动态数组，大致原理就是：

vector 为空的时候没有预分配空间，每次添加一个元素时， 会判断当前(size)(resize 直接进行扩容 短截长补0)是否还有剩余可用空间， 如果没有则进行试探性扩容变为之前的2倍(capacity)(reserve 改变扩容策略)， 并且把内存拷贝到 新申请的内存空间上，并且释放原先的内存；

vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。 vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。 因此，vector的运用对内存的合理利用与运用的灵活性有很大的帮助。

譬如

push_back insert resize pop erase等均可以对vector进行扩容操作。以二倍方式扩容

详情见

win + linux 内存泄漏检测方法

virtual

多态是什么？ wiki : 相同的信息发送给不同的对象能够引发不同的动作.

多态有哪几种？ 具体表现为四种： 子类多态(运行时多态 类向上转化后给父类指针 调用子类方法 指针引用,否则就算是虚函数也只会调用父类方法)、 参数多态(模板类的使用)、 重载多态、(重载运算符) 强制多态.(强制数据类型转化)

也可以分为静态多态与动态多态两部分

虚函数是什么 在某基类中声明为virtual，在一个或多个派生类中被重写的函数。目的是为了实现子类多态属性, 因为派生类中重定义后的方法向上转化后调用只能表现出当前类的方法。

虚函数如何实现的？

  • 虚函数的实现与虚函数表及其中存储的虚函数指针有关 类的存储地址中除了定义的函数成员，还有一个成员是虚函数表指针（占四个基本内存单元） 【所以不论定义了多少虚函数，类中都只有一个虚函数表指针来对方法的使用进行索引。】

    这个指针指向一个虚函数表的起始位置，这个表会与类的定义同时出现， 这个表存放着该类的虚函数指针，调用的时候可以找到该类的虚函数表指针， 通过虚函数表指针找到虚函数表，通过虚函数表的偏移找到函数的入口地址，从而找到要使用的虚函数。

  • 当实例化一个该类的子类对象的时候，（如果）该类的子类并没有定义虚函数， 但是却从父类中继承了虚函数，那么在实例化该类子类对象的时候也会产生一个虚函数表，这个虚函数表是子类的虚函数表， 在没有重载的情况下记录的子类的虚函数地址却是与父类的是一样的。 所以通过子类对象的虚函数表指针找到自己的虚函数表， 在自己的虚函数表找到的要执行的函数指针也是父类的相应函数入口的地址。

-（有关覆盖）如果我们在子类中重载了从父类继承来的虚函数，然而对于父类来说本身是没有被改变的. 对于子类来说它的虚函数表与之前的虚函数表是一样的，但是如果此时子类中重写了（从父类那继承来的） 相应虚函数，那么它的虚函数表当中关于这个函数的指针就会覆盖掉原有的指向父类函数的指针的值， 换句话说就是指向了自己定义的相应函数，（父类指向子类？？） 这样如果用父类的指针指向子类的对象，就会通过子类对象当中的虚函数表指针找到子类的虚函数表， 从而通过子类的虚函数表找到子类的相应虚函数地址，而此时的地址已经是该函数自己定义的虚函数入口地址， 而不是父类的相应虚函数入口地址，所以执行的将会是子类当中的虚函数。这就是多态的原理。若子函数中 重载了虚函数那么就会调用之，若没定义则会调用父类的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

CMan m_man;

CChild m_child;

//这才是使用的精髓，如果不定义基类的指针去使用，没有太大的意义

CMan *p ;

p = &m_man ;

p->Eat(); //始终调用CMan的Eat成员函数，不会调用 CChild 的

p = &m_child; // 父类指向子类，如果子类没有实现该函数，则调用CMan的Eat函数

p->Eat(); //如果子类实现(覆盖)了该方法，则始终调用CChild的Eat函数

const

1
2
3
4

const Stock & Stock::topval(const Stock& s)const
{
    return  *s;
}

这样一个函数中

1 函数返回值不会被修改。

2 保证传入的变量不会被修改.

3 保证该方法不会修改调用它的类对象。(所以一般用于内联return value函数）

友元

友元函数 、 友元类 、 友元成员函数

  • 为何需要友元： 因为重载的符号运算符只是对左右值为同种type来说的，不能应用于不同type之间。 用于解决例如 ClassA = ClassB * 3.5;这种奇怪的运算，或者想直接获取类中私有变量信息的时候 , 这时候就需要定义友元函数.

  • 使用友元类时注意： (1) 友元关系不能被继承。

(2) 友元关系是单向的，不具有交换性。若类B是类A的友元，类A不一定是类B的友元，要看在类中是否有相应的声明。

(3) 友元关系不具有传递性。若类B是类A的友元，类C是B的友元，类C不一定是类A的友元，同样要看类中是否有相应的申明

友元函数

  1. 可以放在类的任意位置。
  2. 虽然在类内部，但是并不属于该类。
  3. 能够访问类内的私有变量，打破了类的封装性。
1
2
3
4
5
6
7
8
9
10
11
12

class A{
public:
    A(int n){a_ = n;};
    A():a_(0){};
    ~A(){};
    void getNumber()const{cout<<a_<<endl;};
private:
    int a_;
    friend void function(A a);// 全局function为A的友元
};
void function(A a){cout<<a.a_<<endl;};
int main(){ A  a; function(a);}

需要注意的是这个函数并不是类函数，但是他要有能操作类变量的能力，与成员函数权限相同。 本质上是类方法的一种接口，并不是违反了面向对象原则。

友元成员函数

1
2
3
4
5
6
7
8
9
10

class A{
public:
    A(int n){a_ = n;};
    A():a_(0){};
    ~A(){};
    void getNumber()const{cout<<a_<<endl;};
private:
    int a_;
    friend void B::function();// 类B的function方法为A的友元
};

友元类

可以通过友元函数直接调用参数 不用通过方法接口进行调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class A{
public:
    A(int n){a_ = n;};
    A():a_(0){};
    ~A(){};
    void getNumber()const{cout<<a_<<endl;};
private:
    int a_;
    friend class B;
};

class B{
public:
    B(){};
    ~B(){};
    void changeA(A& a){a.a_ = 10;};// 友元类可以直接对A私有变量进行操作
};

int main()
{
    A a;
    a.getNumber();
    B b;
    b.changeA(a);
    a.getNumber();
    return 0;
}

多继承

继承 (公有继承、私有继承、保护继承 –> 正好是类中的三种类型)

公有继承(普通、多态、抽象) 继承通过使用已有的基类定义新的派生类，是的能够根据需要来对派生类进行修改。 公有继承意味着派生类对象也应该是某种基类对象.

多继承问题

  • 问题出现：菱形继承的情况，派生类包含了多个基类组件。

  • 解决办法： 1 使用过程中可以通过指定类型父类方法指针强制转换调用方法

    1

    Worker *w_1 = (Teacher*) &TeacherSinger;

2 在派生类TeacherSinger中对具体方法进行指定

1
2

void TeacherSinger::show()
{Teacher::show();}

3 直接使用作用域解析运算符直接调用。

1

w_1.Teacher::show();

4 虚继承

牛客题

L1 可以编译通过 L2不可以编译通过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct A1{
    virtual ~A1(){}
};
struct A2{
    virtual ~A2(){}
};
struct B1 : A1, A2{};

int main()
{
 B1 d;// 子类 可转向A1 A2
 A1* pb1 = &d;// 父类指针指向子类
 A2* pb2 = dynamic_cast<A2*>(pb1);  //L1
 A2* pb22 = static_cast<A2*>(pb1);  //L2
 return 0;
}

static

类外部：

静态全局变量 只能够在当前源文件cpp中使用，且只有在程序结束时才会被释放。

静态局部变量 定义在函数内部，在调用该函数的时候能够继续之前的值，只有在程序结束时才会被释放。

静态函数 只能够在当前源文件cpp中使用，且只有在程序结束时才会被释放。

类内部：

静态成员(静态变量、静态函数)

静态类中的成员加入static修饰符,即是静态成员.可以直接使用类名+静态成员名访问此静态成员,

不需要实例化即可直接调用，独立于对象存在，没有this指针。

因为静态成员存在于内存,非静态成员需要实例化才会分配内存,所以静态成员不能访问非静态的成员. 因为静态成员存在于内存,所以非静态成员可以直接访问类中静态的成员.

问题++i & i++：

++i与i++

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// ++i 实现自增后返回该值 已经发生了改变
int & operator++()
{
    *this += 1;
    return this;
};

const int operator++(int) // 返回改变之前的值，实际结果已经发生了改变
{
    int res = *this;
    *this += 1;
    return res;
}

1 i++是由前者实现的 2 前者返回引用 后者返回const对象 且不能i++++操作 3 具体实现上区别为operator++() operator++(int) 用int作

问题 B树：

B树

问题 继承封装多态：

三大特性

问题 智能指针：

智能指针

问题 四大转化：

四大转换

问题 红黑树：

红黑树

….不想浪费时间在这里了 跳转过去看吧… XD

CATALOG
    FEATURED TAGS
    Memory 小冬搞开发 小冬传经验 Quadcopter 小冬找工作 小冬爱总结 ROS SLAM C++11 Deep learning Deeplearning Homework Jekyll Blog Object detection TEST Tensorflow 小冬学英语 Algorithm Blender Cross Entropy Error Func Github Kalman_filter Paper RL Raspberry Pi Ubuntu Wiki windows
    FRIENDS
    SHOWCASE