C/C++

容器和算法

map和set有什么区别？分别又是怎么实现的？

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。

由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。

map和set的区别在于：

map中的元素是key-value（键值对）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。

其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

map支持下标操作，set不支持下标操作。

map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

STL的allocator有什么作用？

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

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

delete运算分两个阶段：(1)调用对象希构函数；(2)掉员工::operator delete释放内存

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

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

STL迭代器如何删除元素？

对于序列容器vector,deque来说，使用erase(itertor)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器；

对于关联容器map set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。

STL中MAP数据如何存放的？

红黑树。unordered map底层结构是哈希表

STL中map与unordered_map有什么区别？

map在底层使用了红黑树来实现，unordered_map是C++11标准中新加入的容器，它的底层是使用hash表的形式来完成映射的功能，map是按照operator<比较判断元素是否相同，以及比较元素的大小，然后选择合适的位置插入到树中。所以，如果对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。

而unordered_map是计算元素的Hash值，根据Hash值判断元素是否相同。所以，对unordered_map进行遍历，结果是无序的。

使用map时，需要为key定义operator< 。 而unordered_map的使用需要定义hash_value函数并且重载operator==。对于内置类型，如string，这些都不用操心，可以使用默认的。对于自定义的类型做key，就需要自己重载operator< 或者hash_value()了。

所以说，当不需要结果排好序时，最好用unordered_map，插入删除和查询的效率要高于map。

vector和list的区别是什么？

  1. vector底层实现是数组；list是双向 链表。

  2. vector支持随机访问，list不支持。

  3. vector是顺序内存，list不是。

  4. vector在中间节点进行插入删除会导致内存拷贝，list不会。

  5. vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。

  6. vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

STL中迭代器有什么作用？有指针为何还要迭代器？

1、迭代器

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。

2、迭代器和指针的区别

迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、--等。迭代器封装了指针，是一个“可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象， 本质是封装了原生指针，是指针概念的一种提升（lift），提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，--等操作。

迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。

3、迭代器产生原因

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

epoll的原理是什么？

调用顺序：

int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);

首先创建一个epoll对象，然后使用epoll_ctl对这个对象进行操作，把需要监控的描述添加进去，这些描述如将会以epoll_event结构体的形式组成一颗红黑树，接着阻塞在epoll_wait，进入大循环，当某个fd上有事件发生时，内核将会把其对应的结构体放入到一个链表中，返回有事件发生的链表。

STL里resize和reserve的区别是什么？

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

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

类和数据抽象

C++中类成员的访问权限？

C++通过 public、protected、private 三个关键字来控制成员变量和成员函数的访问权限，它们分别表示公有的、受保护的、私有的，被称为成员访问限定符。在类的内部（定义类的代码内部），无论成员被声明为 public、protected 还是 private，都是可以互相访问的，没有访问权限的限制。在类的外部（定义类的代码之外），只能通过对象访问成员，并且通过对象只能访问 public 属性的成员，不能访问 private、protected 属性的成员

C++中struct和class的区别是什么?

在C++中，可以用struct和class定义类，都可以继承。区别在于：structural的默认继承权限和默认访问权限是public，而class的默认继承权限和默认访问权限是private。另外，class还可以定义模板类形参，比如template。

C++类内可以定义引用数据成员吗？

可以，必须通过成员函数初始化列表初始化。

面向对象与泛型编程是什么？

  1. 面向对象编程简称OOP,是一种程序设计思想。OOP把对象作为程序的基本单元,一个对象包含了数据和操作数据的函数。
  2. 面向过程的程序设计把计算机程序视为一系列的命令集合，即一组函数的顺序执行。为了简化程序设计，面向过程把函数继续切分为子函数，即把大块函数通过切割成小块函数来降低系统的复杂度。
  3. 泛型编程: 让类型参数化,方便程序员编码。
    类型参数化: 使的程序(算法)可以从逻辑功能上抽象,把被处理对象(数据)的类型作为参数传递。

什么是右值引用，跟左值又有什么区别？

左值和右值的概念：

左值：能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。

右值：不能对表达式取地址，或匿名对象。一般指表达式结束就不再存在的临时对象。

右值引用和左值引用的区别：

  1. 左值可以寻址，而右值不可以。
  2. 左值可以被赋值，右值不可以被赋值，可以用来给左值赋值。
  3. 左值可变,右值不可变（仅对基础类型适用，用户自定义类型右值引用可以通过成员函数改变）。

析构函数可以为 virtual 型，构造函数则不能，为什么？

构造函数不能声明为虚函数，析构函数可以声明为虚函数，而且有时是必须声明为虚函数。不建议在构造函数和析构函数里面调用虚函数。

构造函数不能声明为虚函数的原因是:

虚函数的主要意义在于被派生类继承从而产生多态。派生类的构造函数中，编译器会加入构造基类的代码，如果基类的构造函数用到参数，则派生类在其构造函
数的初始化列表中必须为基类给出参数，就是这个原因。虚函数的意思就是开启动态绑定，程序会根据对象的动态类型来选择要调用的方法。然而在构造函数运行的时候，这个对象的动态类型还不完整，没有办法确定它到底是什么类型，故构造函数不能动态绑定。（动态绑定是根据对象的动态类型而不是函数名，在调用构造函数之前，这个对象根本就不存在，它怎么动态绑定？）

C++中空类默认产生哪些类成员函数？

C++中空类默认会产生以下6个函数：默认构造函数、复制构造函数、析构函数、赋值运算符重载函数、取址运算法重载函数、const取址运算符重载函数等。

class Empty
{
  public:
  Empty(); // 缺省构造函数
  Empty( const Empty& ); // 拷贝构造函数
  ~Empty(); // 析构函数
  Empty& operator=( const Empty& ); // 赋值运算符
  Empty* operator&(); // 取址运算符
  const Empty* operator&() const; // 取址运算符 const
};

联系作者

关于作者

作者在准备秋招的过程中，凭借这份资料，最后顺利拿到了oppo，小米，兆易创新，全志科技，海康威视等十余家家公司的offer。现将这部分资料分享出来，希望能对大家有帮助！

关于嵌入式软件工程师笔试面试指南

嵌入式软件工程师笔试面试指南，详细分成了简历书写，面试技巧，面经总结，笔试面试八股文总结等四个部分。

其中，八股文又分成了C/C++，数据结构与算法分析，Arm体系与架构，Linux驱动开发，操作系统，网络编程，名企笔试真题等七个部分。

无论是做嵌入式应用层还是嵌入式底层，一定会对你有帮助的（没有帮助来找我领红包）。这些内容均会同步更新到github仓库中（内含PDF版本的获取方式）。

因个人能力有限，可能会有一些错误。大家发现错误，可以在github提交issues，勘误我也会整理出来，第一时间通知大家。

这些内容都是我熬夜整理的，创作不易，大家不要忘了点击「赞」支持下，也算没有白白熬夜，对得起我掉的一根根头发。

github：https://github.com/ZhongYi-LinuxDriverDev/EmbeddedSoftwareEngineerInterview