360-c++开发面经（二）

关于vector简单的说就是一个动态增长的数组，里面有一个指针指向一片连续的内存空间，当空间装不下要容纳的数据的时候会自动申请一片更大的空间（空间配置器）将原来的数据拷贝到新的空间，然后就会释放旧的空间。当删除的时候空间并不会释放只是清空了里面的数据。

vector的数据安排以及操作方式与数组非常相似，两者唯一区别在于空间运用的灵活性，数组是静态空间一旦配置了就不能再改变大小，如果要增容的话，就要把数据搬到新的数组里面，然后再把原来的空间释放掉还给操作系统。vector是动态的随着元素的增加，它的内部机制会自动的扩充空间来容纳新的元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们不必害怕空间不足而一开始就开辟一块很大的内存。

vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧空间满载了，如果客户端每新增加一个元素，vector的内部只是扩充了一个元素空间，其实这样是比较不明智的。因为所谓的扩充空间（无论多大），过程都是配置新空间——数据移动——释放旧空间，成本还是比较高的。vector维护的是一个连续的线性空间，所以vector支持随机访问。

在vector的动态增加大小的时候，并不是在原有的空间上持续增加成新的空间（无法保证原空间的后面还有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原来的内容拷贝过来，并释放原来的空间。因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了，这是比较容易犯的一个错误。

vector里的函数：

需要引入的头文件不同

map: #include < map >

unordered_map: #include < unordered_map >

内部实现机理不同

map：map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。哈希表详细介绍

优缺点以及适用处

map：

优点：

有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作

红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高

缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

优点：因为内部实现了哈希表，因此其查找速度非常的快

缺点：哈希表的建立比较耗费时间

适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

总结：

内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。

但是unordered_map执行效率要比map高很多

对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的

map和unordered_map的使用

unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。

在C++中，动态内存的管理是通过一对运算符来完成的：new，在动态内存中为对象分配空间并返回一个指向该对象的指针，可以选择对对象进行初始化；delete，接受一个动态对象的指针，销毁该对象，并释放与之关联的内存。

动态内存的使用很容易出问题，因为确保在正确的时间释放内存是极其困难的。有时会忘记释放内存，在这种情况下会产生内存泄露；有时在尚有指针引用内存的情况下就释放了它，在这种情况下就会产生引用非法内存的指针。

为了更容易(同时也更安全)地使用动态内存，C++11标准库提供了两种智能指针(smart pointer)类型来管理动态对象。智能指针的行为类似常规指针，重要的区别是它负责自动释放所指的对象。C++11标准库提供的这两种智能指针的区别在于管理底层指针的方式：shared_ptr允许多个指针指向同一个对象；unique_ptr则"独占"所指向的对象。C++11标准库还定义了一个名为weak_ptr的辅助类，它是一种弱引用，指向shared_ptr所管理的对象。这三种类型都定义在memory头文件中。智能指针是模板类而不是指针。类似vector，智能指针也是模板，当创建一个智能指针时，必须提供额外的信息即指针可以指向的类型。默认初始化的智能指针中保存着一个空指针。智能指针的使用方式与普通指针类似。解引用一个智能指针返回它指向的对象。如果在一个条件判断中使用智能指针，效果就是检测它是否为空。

智能指针实质就是重载了->和*操作符的类，由类来实现对内存的管理，确保即使有异常产生，也可以通过智能指针类的析构函数完成内存的释放。

shared_ptr的类型转换不能使用一般的static_cast，这种方式进行的转换会导致转换后的指针无法再被shared_ptr对象正确的管理。应该使用专门用于shared_ptr类型转换的 static_pointer_cast<T>() , const_pointer_cast<T>() 和dynamic_pointer_cast<T>()。

使用shared_ptr避免了手动使用delete来释放由new申请的资源，标准库也引入了make_shared函数来创建一个shared_ptr对象，使用shared_ptr和make_shared，你的代码里就可以使new和delete消失，同时又不必担心内存的泄露。shared_ptr是一个模板类。

C++开发处理内存泄漏最有效的办法就是使用智能指针，使用智能指针就不会担心内存泄露的问题了，因为智能指针可以自动删除分配的内存。

智能指针是指向动态分配(堆)对象指针，用于生存期控制，能够确保自动正确的销毁动态分配的对象，防止内存泄露。它的一种通用实现技术是使用引用计数。每次使用它，内部的引用计数加1，每次析构一次，内部引用计数减1，减为0时，删除所指向的堆内存。

每一个shared_ptr的拷贝都指向相同的内存。在最后一个shared_ptr析构的时候, 内存才会被释放。

可以通过构造函数、赋值函数或者make_shared函数初始化智能指针。

shared_ptr基于”引用计数”模型实现，多个shared_ptr可指向同一个动态对象，并维护一个共享的引用计数器，记录了引用同一对象的shared_ptr实例的数量。当最后一个指向动态对象的shared_ptr销毁时，会自动销毁其所指对象(通过delete操作符)。

shared_ptr的默认能力是管理动态内存，但支持自定义的Deleter以实现个性化的资源释放动作。

最安全的分配和使用动态内存的方法是调用一个名为make_shared的标准库函数。此函数在动态内存中分配一个对象并初始化它，返回指向此对象的shared_ptr。当要用make_shared时，必须指定想要创建的对象的类型，定义方式与模板类相同。在函数名之后跟一个尖括号，在其中给出类型。例如，调用make_shared<string>时传递的参数必须与string的某个构造函数相匹配。如果不传递任何参数，对象就会进行值初始化。

通常用auto定义一个对象来保存make_shared的结果。

当进行拷贝或赋值操作时，每个shared_ptr都会记录有多少个其它shared_ptr指向相同的对象。

可以认为每个shared_ptr都有一个关联的计数器，通常称其为引用计数(reference count)。无论何时拷贝一个shared_ptr，计数器都会递增。例如，当用一个shared_ptr初始化另一个shared_ptr，或将它作为参数传递给一个函数以及作为函数的返回值时，它所关联的计数器就会递增。当给shared_ptr赋予一个新值或是shared_ptr被销毁(例如一个局部的shared_ptr离开其作用域)时，计数器就会递减。一旦一个shared_ptr的计数器变为0，它就会自动释放自己所管理的对象。

当指向一个对象的最后一个shared_ptr被销毁时，shared_ptr类会自动销毁此对象。它是通过另一个特殊的成员函数析构函数(destructor)来完成销毁工作的。类似于构造函数，每个类都有一个析构函数。就像构造函数控制初始化一样，析构函数控制此类型的对象销毁时做什么操作。shared_ptr的析构函数会递减它所指向的对象的引用计数。如果引用计数变为0，shared_ptr的析构函数就会销毁对象，并释放它占用的内存。

如果将shared_ptr存放于一个容器中，而后不再需要全部元素，而只使用其中一部分，要记得用erase删除不再需要的那些元素。

使用shared_ptr注意事项：

(1)、不要把一个原生指针给多个shared_ptr管理；

(2)、不要把this指针给shared_ptr；

(3)、不要在函数实参里创建shared_ptr；

(4)、不要不加思考地把指针替换为shared_ptr来防止内存泄漏，shared_ptr并不是万能的，而且使用它们的话也是需要一定的开销的；

(5)、环状的链式结构shared_ptr将会导致内存泄漏(可以结合weak_ptr来解决)；

(6)、共享拥有权的对象一般比限定作用域的对象生存更久，从而将导致更高的平均资源使用时间；

(7)、在多线程环境中使用共享指针的代价非常大，这是因为你需要避免关于引用计数的数据竞争；

(8)、共享对象的析构器不会在预期的时间执行；

(9)、不使用相同的内置指针值初始化(或reset)多个智能指针；

(10)、不delete get()返回的指针；

(11)、不使用get()初始化或reset另一个智能指针；

(12)、如果使用get()返回的指针，记住当最后一个对应的智能指针销毁后，你的指针就变为无效了；

(13)、如果你使用智能指针管理的资源不是new分配的内存，记住传递给它一个删除器。