STL容器詳解

2022-08-05 14:14:15 字數 2889 閱讀 1259

3.1. stl容器

(1)序列式容器(sequencecontainers),每個元素都有固定位置--取決於插入時機和地點,和元素值無關,vector、deque、list;

vectors:將元素置於一個動態陣列中加以管理,可以隨機存取元素(用索引直接存取),陣列尾部新增或移除元素非常快速。但是在中部或頭部安插元素比較費時;

deques:是“double-endedqueue”的縮寫,可以隨機存取元素(用索引直接存取),陣列頭部和尾部新增或移除元素都非常快速。但是在中部或頭部安插元素比較費時;

lists:雙向連結串列,不提供隨機存取(按順序走到需存取的元素,o(n)),在任何位置上執行插入或刪除動作都非常迅速,內部只需調整一下指標;

(2)關聯式容器(associatedcontainers),元素位置取決於特定的排序準則,和插入順序無關,set、multiset、map、multimap;

sets/multisets:內部的元素依據其值自動排序,set內的相同數值的元素只能出現一次,multisets內可包含多個數值相同的元素,內部由二叉樹實現,便於查詢;

maps/multimaps:map的元素是成對的鍵值/實值,內部的元素依據其值自動排序,map內的相同數值的元素只能出現一次,multimaps內可包含多個數值相同的元素,內部由二叉樹實現,便於查詢;

容器的比較:

vectordequelistsetmultisetmapmultimap

內部結構dynamic arrayarray of arraysdouble linked listbinary treebinary treebinary treebinary tree

隨機存取yesyesnononoyes(key)no

搜尋速度慢慢很慢快快快快

快速插入移除尾部首尾任何位置--------

迭代器的作用:能夠讓迭代器與演算法不干擾的相互發展,最後又能無間隙的粘合起來,過載了*,++,==,!=,=運算子。用以操作複雜的資料結構,容器提供迭代器,演算法使用迭代器;

3.2 stl迭代器

迭代器作用:

(1)能夠讓迭代器與演算法不干擾的相互發展,最後又能無間隙的粘合起來;

(2)過載了*,++,==,!=,=運算子。用以操作複雜的資料結構;

(3)容器提供迭代器,演算法使用迭代器;

簡單例子:

迭代器的分類:

input iterator, output iterator, forward iterator, bidirectionaliterator, random access iterator等;

不同容器提供自己的迭代器,所以不同迭代器具有不同的能力;

不同的演算法需要不同的迭代器的能力;相同的演算法需要根據迭代器的能力不同而做相應的優化;

3.3 stl演算法

stl演算法部分主要由標頭檔案,,組成;要使用stl中的演算法函式必須包含標頭檔案,對於數值演算法須包含,中則定義了一些模板類,用來宣告函式物件;

stl中演算法大致分為四類:

非可變序列演算法:指不直接修改其所操作的容器內容的演算法。

可變序列演算法:指可以修改它們所操作的容器內容的演算法。

排序演算法:包括對序列進行排序和合並的演算法、搜尋演算法以及有序序列上的集合操作。

數值演算法:對容器內容進行數值計算。

查詢演算法(13個):判斷容器中是否包含某個值;

adjacent_find:在iterator對標識元素範圍內,查詢一對相鄰重複元素,找到則返回指向這對元素的第一個元素的forwarditerator;否則返回last;

binary_search:在有序序列中查詢value,找到返回true。過載的版本實用指定的比較函式物件或函式指標來判斷相等;

count:利用等於操作符,把標誌範圍內的元素與輸入值比較,返回相等元素個數;

count_if:利用輸入的操作符,對標誌範圍內的元素進行操作,返回結果為true的個數;

equal_range:功能類似equal,返回一對iterator,第一個表示lower_bound,第二個表示upper_bound;

其他:find,find_end,find_first_of,find_if,lower_bound,upper_bound,search,search_n;

排序和通用演算法(14個):提供元素排序策略;

inplace_merge:合併兩個有序序列,結果序列覆蓋兩端範圍。過載版本使用輸入的操作進行排序;

merge:合併兩個有序序列,存放到另一個序列。過載版本使用自定義的比較;

nth_element:將範圍內的序列重新排序,使所有小於第n個元素的元素都出現在它前面,而大於它的都出現在後面。過載版本使用自定義的比較操作;

partial_sort:對序列做部分排序,被排序元素個數正好可以被放到範圍內。過載版本使用自定義的比較操作;

partial_sort_copy:與partial_sort類似,不過將經過排序的序列複製到另一個容器;

其他:partition,random_shuffle,reverse,reverse_copy,rotate,rotate_copy,sort,stable_sort,stable_partition;

刪除和替換演算法(15個);

排列組合演算法(2個):提供計算給定集合按一定順序的所有可能排列組合;

算術演算法(4個);

生成和異變演算法(6個);

關係演算法(8個);

集合演算法(4個);

堆演算法(4個);

4. stl使用示例

待續…5. 參考文件

(1)c++ stl 快速入門

(2)三十分鐘掌握stl

C STL學習之三 容器deque深入學習

c stl學習之三 容器deque深入學習 2012 04 10 09 23 41 我來說兩句 收藏 我要投稿 字型 小 大 c stl容器deque和vector很類似,也是採用動態陣列來管理元素。 使用deque之前需包含標頭檔案 include 它是定義在名稱空間std內的一個class tem...

C STL之algorithm

我們在之前介紹過,stl可分為容器 containers 迭代器 iterators 空間配置器 allocator 配接器 adapters 演算法 algorithms 仿函式 functors 六個部分。 在前幾篇文章裡主要向大家介紹了幾種常用的容器,它們有vector 不定長陣列 stack ...

STL模型Magics修復教程

magics rp是比利時materialise公司開發的 完全針對3d 列印工序特徵的軟體,最新版本19 01。magics為處理stl檔...