c/c++面试总结(3),面试总结

7.vector和list的区别(这个也算是经常问的)

vector和数组类似,拥有一段连续的内存空间,并且起始地址不变,这样对随机的读取很有效率(就是我们所有的[]运算符了),因为内存是连续的如果我们想要插入或者删除元素的时候就需要对当前的元素进行复制和移动,如果vector存储的对象较大,或者构造函数较复杂,那么对现有对象进行拷贝的开销就会很大(拷贝对象需要调用拷贝构造函数),vector每次扩张容量的时候将容量扩张2倍(由于vector中的元素是连续存放,所以不能随便找个地方存放,于是vector会重新分配一块大的内存,将原来的数据拷贝过来再将原来的空间释放掉,而这部分内存一般情况下比需要存储的数据所需要的内存大,这样当再有元素需要存储时就不需要在开辟内存了)。

list的对象是离散存储的(就是内存不是连续的),想要随机访问某个元素就需要遍历list,但是在插入元素的效率很高(只需要改变元素的指针,头尾插入效率最高—具体参考链表的一些操作)。

vector适用:对象数量变化少,简单对象,随机访问元素频繁

list适用:对象数量变化大,对象复杂,插入和删除频繁

8.vector的resize和rserver操作的区别(虽然以前用过,但都不知道为什么)
reserve增加了vector的容量,但是它的size没有改变!
resize改变了vector的容量同时也增加了它的size!
想要更加深入的了解可以自行百度!!

9.unordered_map和map的实现机制,性能差异(c++面试STL的时候有可能会问到)
运行效率方面:unordered_map最高,hash_map其次,而map效率最低单提供了有序的序列。
占用内存方面:hash_map内存占用最低,unordered_map其次(数量少时优于hash_map),而map占用最高
unordered_map,它与
stl::map的区别就是,stl::map是按照operator<比较判断元素是否相同,以及比较元素的大小,然后选择合适的位置插入到树中。所以,如果对map进行遍历(中序遍历)的话,输出的结果是有序的。顺序就是按照operator<
定义的大小排序。
而unordered_map是计算元素的Hash值,根据Hash值判断元素是否相同。所以,对unordered_map进行遍历,结果是无序的。
用法的区别就是,stl::map 的key需要定义operator< 。
而unordered_map需要定义hash_value函数并且重载operator==(必须要自定义operator==和hash_value。
重载operator==是因为,如果两个元素的hash_value的值相同,并不能断定这两个元素就相同,必须再调用operator==。
当然,如果hash_value的值不同,就不需要调用operator==)。
对于内置类型,如string,这些都不用操心。
对于自定义的类型做key,就需要自己重载operator<
或者hash_value()了。
当不需要结果排好序时,最好用unordered_map。
实现机制:
map的内部实现是二叉平衡树(红黑树自行查找相关概念,我也不懂,还需努力)
unordered_map的实现是hash_table;
hash_map在unordered_map实现之前先实现,但是unordered_map作为STL的标准被加入;hash_map和c++
stl的api不兼容,c++ tr1(C++ Technical Report1)作为标准的扩展,实现了hash
map,提供了和stl兼容一致的api,称为unorder_map.在头文件
<tr1/unordered_map>中。
使用unordered_map,尽量不使用hash_map。

7.vector和list的区别(这个也算是经常问的)
vector和数组类似,拥有一段连续的内存空间,并且起始地址不变…

相关文章