江苏龙网

  1. 主页 > 生活百科 > >

STL总结与常见面试题( 九 )

STL


当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据 。
因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了

STL总结与常见面试题

文章插图
 
  1. vector中的reserve和resize的区别
  • reserve是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化push_back），就可以提高效率，其次还可以减少多次要拷贝数据的问题 。reserve只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n 。reserve()只有一个参数 。
  • resize()可以改变有效空间的大小，也有改变默认值的功能 。capacity的大小也会随着改变 。resize()可以有多个参数 。
  1. vector中的size和capacity的区别
  • size表示当前vector中有多少个元素（finish - start）;
  • capacity函数则表示它已经分配的内存中可以容纳多少元素（end_of_storage - start）;
  1. vector中erase方法与algorithn中的remove方法区别
  • vector中erase方法真正删除了元素，迭代器不能访问了
  • remove只是简单地将元素移到了容器的最后面，迭代器还是可以访问到 。因为algorithm通过迭代器进行操作，不知道容器的内部结构，所以无法进行真正的删除 。
  1. vector迭代器失效的情况
  • 当插入一个元素到vector中，由于引起了内存重新分配，所以指向原内存的迭代器全部失效 。
  • 当删除容器中一个元素后,该迭代器所指向的元素已经被删除，那么也造成迭代器失效 。erase方法会返回下一个有效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it); 。
  1. 正确释放vector的内存(clear(), swap(), shrink_to_fit())
  • vec.clear()：清空内容，但是不释放内存 。
  • vector<int>().swap(vec)：清空内容，且释放内存，想得到一个全新的vector 。
  • vec.shrink_to_fit()：请求容器降低其capacity和size匹配 。
  • vec.clear();vec.shrink_to_fit();：清空内容，且释放内存 。
  1. list的底层原理

STL总结与常见面试题

文章插图
 
  • ist的底层是一个双向链表，使用链表存储数据，并不会将它们存储到一整块连续的内存空间中 。恰恰相反，各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针来维持,每次插入或删除一个元素，就配置或释放一个元素空间 。
  • list不支持随机存取，如果需要大量的插入和删除，而不关心随即存取
  1. 什么情况下用vector，什么情况下用list，什么情况下用deque
  • vector可以随机存储元素（即可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入删除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁 。除非必要，我们尽可能选择使用vector而非deque，因为deque的迭代器比vector迭代器复杂很多 。
  • list不支持随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁，比如写多读少的场景 。
  • 需要从首尾两端进行插入或删除操作的时候需要选择deque 。
  1. priority_queue的底层原理
  • priority_queue：优先队列，其底层是用堆来实现的 。在优先队列中，队首元素一定是当前队列中优先级最高的那一个 。
  1. map 、set、multiset、multimap的底层原理
map 、set、multiset、multimap的底层实现都是红黑树，epoll模型的底层数据结构也是红黑树，linux系统中CFS进程调度算法，也用到红黑树 。
STL总结与常见面试题

文章插图
 
红黑树的特性：
  • 每个结点或是红色或是黑色；
  • 根结点是黑色；
  • 每个叶结点是黑的；
  • 如果一个结点是红的，则它的两个儿子均是黑色；
  • 每个结点到其子孙结点的所有路径上包含相同数目的黑色结点 。
  1. 为何map和set的插入删除效率比其他序列容器高
  • 因为不需要内存拷贝和内存移动
  1. 为何map和set每次Insert之后，以前保存的iterator不会失效？

上一篇：教你如何沏白茶,百合山药茶的做法

下一篇：喝茶是不是可以解酒,喝什么能解酒