360-c++开发面经(二)
共 4851字,需浏览 10分钟
·
2021-06-12 08:38
点击蓝字关注我们,获取更多面经
![](https://filescdn.proginn.com/46faddb7113fe23832e491f8eac65fe5/bf03d56f0bb82ae7153749099061888f.webp)
![](https://filescdn.proginn.com/893aafaf9d89a5be83d30e0b6583e11a/e6a240800f4c4a12b009f9fe716bc7b5.webp)
关于vector简单的说就是一个动态增长的数组,里面有一个指针指向一片连续的内存空间,当空间装不下要容纳的数据的时候会自动申请一片更大的空间(空间配置器)将原来的数据拷贝到新的空间,然后就会释放旧的空间。当删除的时候空间并不会释放只是清空了里面的数据。
vector的数据安排以及操作方式与数组非常相似,两者唯一区别在于空间运用的灵活性,数组是静态空间一旦配置了就不能再改变大小,如果要增容的话,就要把数据搬到新的数组里面,然后再把原来的空间释放掉还给操作系统。vector是动态的随着元素的增加,它的内部机制会自动的扩充空间来容纳新的元素。因此,vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们不必害怕空间不足而一开始就开辟一块很大的内存。
vector的实现技术,关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧空间满载了,如果客户端每新增加一个元素,vector的内部只是扩充了一个元素空间,其实这样是比较不明智的。因为所谓的扩充空间(无论多大),过程都是配置新空间——数据移动——释放旧空间,成本还是比较高的。vector维护的是一个连续的线性空间,所以vector支持随机访问。
在vector的动态增加大小的时候,并不是在原有的空间上持续增加成新的空间(无法保证原空间的后面还有可供配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将原来的内容拷贝过来,并释放原来的空间。因此,对vector的任何操作一旦引起了空间的重新配置,指向原vector的所有迭代器会都失效了,这是比较容易犯的一个错误。
vector里的函数:
![](https://filescdn.proginn.com/46faddb7113fe23832e491f8eac65fe5/bf03d56f0bb82ae7153749099061888f.webp)
![](https://filescdn.proginn.com/893aafaf9d89a5be83d30e0b6583e11a/e6a240800f4c4a12b009f9fe716bc7b5.webp)
需要引入的头文件不同
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类型来存贮的。其底层实现是完全不同的,上方已经解释了,但是就外部使用来说却是一致的。
![](https://filescdn.proginn.com/46faddb7113fe23832e491f8eac65fe5/bf03d56f0bb82ae7153749099061888f.webp)
![](https://filescdn.proginn.com/893aafaf9d89a5be83d30e0b6583e11a/e6a240800f4c4a12b009f9fe716bc7b5.webp)
在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分配的内存,记住传递给它一个删除器。
更多面经
扫描二维码
获取更多面经
扶摇就业