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。