CSTL筆試題

　　STL(Standard Template Library，標準模板庫), STL的代碼從廣義上講分為三類：algorithm(算法)、container(容器)和iterator(迭代器)，并包括一些工具類如auto_ptr。幾乎所有的代碼都采用了模板類和模板函數的方式，這相比于傳統的由函數和類組成的庫來說提供了更好的代碼重用機會。下面就由第一范文網小編為大家介紹一下C++STL筆試題的文章，歡迎閱讀。

　　C++STL筆試題篇1

　　1.C++ STL 之所以得到廣泛的贊譽，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封裝了許多復雜的數據結構算法和大量常用數據結構操作。vector封裝數組，list封裝了鏈表，map和set封裝了二叉樹等

　　2.標準關聯容器set, multiset, map, multimap內部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-BlackTree)。RB樹的統計性能要好于一般的平衡二叉樹

　　3.STL map和set的使用雖不復雜，但也有一些不易理解的地方，如：

　　map: type pair，很多不同的const Key對應的T對象的一個集合，所有的記錄集中只要const Key 不一樣就可以，T無關!

　　set: type const Key. 只存單一的對const Key，沒有map 的T對像!可以看成map的一個特例

　　(1)為何map和set的插入刪除效率比用其他序列容器高?，樹

　　答：因為對于關聯容器來說，不需要做內存拷貝和內存移動。說對了，確實如此。map和set容器內所有元素都是以節點的方式來存儲，其節點結構和鏈表差不多，指向父節點和子節點

　　(2)為何每次insert之后，以前保存的iterator不會失效?

　　答：iterator這里就相當于指向節點的指針，內存沒有變，指向內存的指針怎么會失效呢(當然被刪除的那個元素本身已經失效了)。相對于vector來說，每一次刪除和插入，指針都有可能失效，調用push_back在尾部插入也是如此。因為為了保證內部數據的連續存放，iterator指向的那塊內存在刪除和插入過程中可能已經被其他內存覆蓋或者內存已經被釋放了。即使時push_back的時候，容器內部空間可能不夠，需要一塊新的更大的內存，只有把以前的內存釋放，申請新的更大的內存，復制已有的數據元素到新的內存，最后把需要插入的元素放到最后，那么以前的內存指針自然就不可用了。特別時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。

　　(3)為何map和set不能像vector一樣有個reserve函數來預分配數據?

　　答：我以前也這么問，究其原理來說時，引起它的原因在于在map和set內部存儲的已經不是元素本身了，而是包含元素的節點。也就是說map內部使用的Alloc并不是map聲明的時候從參數中傳入的Alloc。例如：

　　4.set, multiset

　　set和multiset會根據特定的排序準則自動將元素排序，set中元素不允許重復，multiset可以重復。

　　因為是排序的，所以set中的元素不能被修改，只能刪除后再添加。

　　向set中添加的元素類型必須重載<操作符用來排序。排序滿足以下準則：

　　1、非對稱，若A

　　2、可傳遞，若A

　　3、A

　　set中判斷元素是否相等：

　　if(!(A

　　C++STL筆試題篇2

　　1.map，multimap

　　map和multimap將key和value組成的pair作為元素，根據key的排序準則自動將元素排序，map中元素的key不允許重復，multimap可以重復。

　　map

　　因為是排序的，所以map中元素的key不能被修改，只能刪除后再添加。key對應的value可以修改。

　　向map中添加的元素的key類型必須重載<操作符用來排序。排序與set規則一致。

　　2. List的功能方法

　　實際上有兩種List: 一種是基本的ArrayList,其優點在于隨機訪問元素，另一種是更強大的LinkedList,它并不是為快速隨機訪問設計的，而是具有一套更通用的方法。

　　List : 次序是List最重要的特點：它保證維護元素特定的順序。List為Collection添加了許多方法，使得能夠向List中間插入與移除元素(這只推薦LinkedList使用。)一個List可以生成ListIterator,使用它可以從兩個方向遍歷List,也可以從List中間插入和移除元素。

　　ArrayList : 由數組實現的List。允許對元素進行快速隨機訪問，但是向List中間插入與移除元素的速度很慢。ListIterator只應該用來由后向前遍歷ArrayList,而不是用來插入和移除元素。因為那比LinkedList開銷要大很多。

　　LinkedList : 對順序訪問進行了優化，向List中間插入與刪除的開銷并不大。隨機訪問則相對較慢。(使用ArrayList代替。)還具有下列方法：addFirst, addLast, getFirst,getLast, removeFirst 和 removeLast, 這些方法 (沒有在任何接口或基類中定義過)使得LinkedList可以當作堆棧、隊列和雙向隊列使用

　　3..1 hash_map和map的區別在哪里?

　　構造函數。hash_map需要hash函數，等于函數;map只需要比較函數(小于函數).

　　存儲結構。hash_map采用hash表存儲，map一般采用紅黑樹(RB Tree)實現。因此其memory數據結構是不一樣的。

　　3.2 什么時候需要用hash_map，什么時候需要用map?

　　總體來說，hash_map 查找速度會比map快，而且查找速度基本和數據數據量大小，屬于常數級別;而map的查找速度是log(n)級別。并不一定常數就比log(n)小，hash還有hash函數的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數量級時，考慮考慮hash_map。但若你對內存使用特別嚴格，希望程序盡可能少消耗內存，那么一定要小心，hash_map可能會讓你陷入尷尬，特別是當你的hash_map對象特別多時，你就更無法控制了，而且hash_map的構造速度較慢。

　　現在知道如何選擇了嗎?權衡三個因素: 查找速度, 數據量, 內存使用。

　　C++STL筆試題篇3

　　1.一些使用上的建議：

　　Level 1 - 僅僅作為Map使用：采用靜態數組

　　Level 2 - 保存定長數據，使用時也是全部遍歷：采用動態數組(長度一開始就固定的話靜態數組也行)

　　Level 3 - 保存不定長數組，需要動態增加的能力，側重于尋找數據的速度：采用vector

　　Level 3 - 保存不定長數組，需要動態增加的能力，側重于增加刪除數據的速度：采用list

　　Level 4 - 對數據有復雜操作，即需要前后增刪數據的能力，又要良好的數據訪問速度：采用deque

　　Level 5 - 對數據中間的增刪操作比較多：采用list，建議在排序的基礎上，批量進行增刪可以對運行效率提供最大的保證

　　Level 6 - 上述中找不到適合的：組合STL容器或者自己建立特殊的數據結構來實現

　　2.

　　(1).vector - 會自動增長的數組

　　vectorvec(10) //一個有10個int元素的容器

　　vector vec(10, 0.5)//一個有10個float元素的容器，并且他們得值都是0.5

　　vector::iterator iter;

　　for(iter = vec.begin; iter != vec.end; iter++)

　　{

　　//. . . . . . .

　　}

　　vector由于數組的增長只能向前，所以也只提供了后端插入和后端刪除，

　　也就是push_back和pop_back。當然在前端和中間要操作數據也是可以的，

　　用insert和erase，但是前端和中間對數據進行操作必然會引起數據塊的移動，

　　這對性能影響是非常大的。

　　最大的優勢就是隨機訪問的能力。

　　vector::iterator相關的方法有：

　　begin：用來獲得一個指向vector第一個元素的指針

　　end：用來獲得一個指向vector最后一個元素之后的那個位置的指針，注意不是指向最后一個元素。

　　erase(vector::iterator)：用來刪除作為參數所傳入的那個iterator所指向的那個元素。

　　(2).list - 擅長插入刪除的鏈表

　　listMilkshakes; list Scores;

　　push_back, pop_backpush_front. pop_front

　　list是一個雙向鏈表的實現。

　　為了提供雙向遍歷的能力，list要比一般的數據單元多出兩個指向前后的指針

　　一個使用iterator來刪除元素的例子

　　list stringList;

　　list::iterator iter;

　　advance(iter, 5); //將iterator指向stringList的第五個元素

　　stringList.erase(iterator);//刪除

　　那么刪除操作進行以后，傳入erase方法的iterator指向哪里了呢?它指向了刪除操作前所指向的那個元素的后一個元素。

　　(3).deque - 擁有vector和list兩者優點的雙端隊列

　　(4).這三個模板的總結 比較和一般使用準則

　　這三個模板都屬于序列類模板，可以看到他們有一些通用方法

　　size:得到容器大小

　　begin:得到指向容器內第一個元素的指針(這個指針的類型依容器的不同而不同)

　　end:得到指向容器內最后一個元素之后一個位置的指針

　　erase:刪除傳入指針指向的那個元素

　　clear:清除所有的元素

　　==運算符：判斷兩個容器是否相等

　　=運算符：用來給容器賦值

　　上面的三個模板有各自的特點

　　vector模板的數據在內存中連續的排列，所以隨機存取元素(即通過運算符存取)的速度最快，這一點和數組是一致的。同樣由于它的連續排列，所以它在除尾部以外的位置刪除或添加元素的速度很慢，在使用vector時，要避免這種操作。

　　list模板的數據是鏈式存儲，所以不能隨機存取元素。它的優勢在于任意位置添加 刪除元素的速度。

　　deque模板是通過鏈接若干片連續的數據實現的，所以均衡了以上兩個容器的特點