1 什麼是STL?
STL(Standard Template Library),即標準模板庫,是一個具有工業強度的,高效的C++程式庫。它被容納於C++標準程式庫(C++ Standard Library)中,是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域裡所常用的基本資料結構和基本演算法。為廣大C++程式設計師們提供了一個可擴充套件的應用框架,高度體現了軟體的可複用性。
STL的一個重要特點是資料結構和演算法的分離。儘管這是個簡單的概念,但這種分離確實使得STL變得非常通用。例如,由於STL的sort()函式是完全通用的,你可以用它來操作幾乎任何資料集合,包括連結串列,容器和陣列;
STL另一個重要特性是它不是面向物件的。為了具有足夠通用性,STL主要依賴於模板而不是封裝,繼承和虛擬函式(多型性)——OOP的三個要素。你在STL中找不到任何明顯的類繼承關係。這好像是一種倒退,但這正好是使得STL的元件具有廣泛通用性的底層特徵。另外,由於STL是基於模板,行內函數的使用使得生成的程式碼短小高效;
從邏輯層次來看,在STL中體現了泛型化程式設計的思想,引入了諸多新的名詞,比如像需求(requirements),概念(concept),模型(model),容器(container),演算法(algorithmn),迭代子(iterator)等。與OOP(object-oriented programming)中的多型(polymorphism)一樣,泛型也是一種軟體的複用技術;
從實現層次看,整個STL是以一種型別引數化的方式實現的,這種方式基於一個在早先C++標準中沒有出現的語言特性——模板(template)。
2 STL內容介紹
STL中六大元件:
容器(Container),是一種資料結構,如list,vector,和deques ,以模板類的方法提供。為了訪問容器中的資料,可以使用由容器類輸出的迭代器;
迭代器(Iterator),提供了訪問容器中物件的方法。例如,可以使用一對迭代器指定list或vector中的一定範圍的物件。迭代器就如同一個指標。事實上,C++的指標也是一種迭代器。但是,迭代器也可以是那些定義了operator*()以及其他類似於指標的運算子地方法的類物件;
演算法(Algorithm),是用來操作容器中的資料的模板函式。例如,STL用sort()來對一個vector中的資料進行排序,用find()來搜尋一個list中的物件,函式本身與他們操作的資料的結構和型別無關,因此他們可以在從簡單陣列到高度複雜容器的任何資料結構上使用;
仿函式(Functor)
介面卡(Adaptor)
分配器(allocator)
2。1 容器
STL中的容器有佇列容器和關聯容器,容器介面卡(congtainer adapters:stack,queue,priority queue),位集(bit_set),串包(string_package)等等。
(1)序列式容器(Sequence containers),每個元素都有固定位置--取決於插入時機和地點,和元素值無關,vector、deque、list;
Vector:將元素置於一個動態陣列中加以管理,可以隨機存取元素(用索引直接存取),陣列尾部新增或移除元素非常快速。但是在中部或頭部安插元素比較費時;
Deque:是“double-ended queue”的縮寫,可以隨機存取元素(用索引直接存取),陣列頭部和尾部新增或移除元素都非常快速。但是在中部或頭部安插元素比較費時;
List:雙向連結串列,不提供隨機存取(按順序走到需存取的元素,O(n)),在任何位置上執行插入或刪除動作都非常迅速,內部只需調整一下指標;
(2)關聯式容器(Associated containers),元素位置取決於特定的排序準則,和插入順序無關,set、multiset、map、multimap等。
Set/Multiset:內部的元素依據其值自動排序,Set內的相同數值的元素只能出現一次,Multisets內可包含多個數值相同的元素,內部由二叉樹實現,便於查詢;
Map/Multimap:Map的元素是成對的鍵值/實值,內部的元素依據其值自動排序,Map內的相同數值的元素只能出現一次,Multimaps內可包含多個數值相同的元素,內部由二叉樹實現,便於查詢;
容器類自動申請和釋放記憶體,無需new和delete操作。
2。2 STL迭代器
Iterator(迭代器)模式又稱Cursor(遊標)模式,用於提供一種方法順序訪問一個聚合物件中各個元素, 而又不需暴露該物件的內部表示。或者這樣說可能更容易理解:Iterator模式是運用於聚合物件的一種模式,透過運用該模式,使得我們可以在不知道物件內部表示的情況下,按照一定順序(由iterator提供的方法)訪問聚合物件中的各個元素。
迭代器的作用:能夠讓迭代器與演算法不干擾的相互發展,最後又能無間隙的粘合起來,過載了*,++,==,!=,=運算子。用以操作複雜的資料結構,容器提供迭代器,演算法使用迭代器;常見的一些迭代器型別:iterator、const_iterator、reverse_iterator和const_reverse_iterator。
相關影片推薦
紅黑樹,在Linux核心的那些故事
【C++後端開發】c++11, 80行程式碼實現高效靈活的定時器
學習地址:C/C++Linux鏈嶅姟鍣ㄥ紑鍙�/鍚庡彴鏋舵瀯甯堛€愰浂澹版暀鑲層€�-瀛︿範瑙嗛鏁欑▼-鑵捐璇懼爞
需要C/C++ Linux伺服器架構師學習資料加qun
812855908
獲取(資料包括
C/C++,Linux,golang技術,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒體,CDN,P2P,K8S,Docker,TCP/IP,協程,DPDK,ffmpeg
等),免費分享
2。3 演算法
函式庫對資料型別的選擇對其可重用性起著至關重要的作用。舉例來說,一個求方根的函式,在使用浮點數作為其引數型別的情況下的可重用性肯定比使用整型作為它的引數類性要高。而C++透過模板的機制允許推遲對某些型別的選擇,直到真正想使用模板或者說對模板進行特化的時候,STL就利用了這一點提供了相當多的有用演算法。它是在一個有效的框架中完成這些演算法的——你可以將所有的型別劃分為少數的幾類,然後就可以在模版的引數中使用一種型別替換掉同一種類中的其他型別。
STL提供了大約100個實現演算法的模版函式,比如演算法for_each將為指定序列中的每一個元素呼叫指定的函式,stable_sort以你所指定的規則對序列進行穩定性排序等等。只要我們熟悉了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: 利用底層元素的等於運算子,對指定範圍內的元素與輸入值進行比較。當匹配時,結束搜尋,返回該元素的 一個InputIterator。
find_end: 在指定範圍內查詢“由輸入的另外一對iterator標誌的第二個序列”的最後一次出現。找到則返回最後一對的第一 個ForwardIterator,否則返回輸入的“另外一對”的第一個ForwardIterator。過載版本使用使用者輸入的運算子代 替等於操作。
find_first_of: 在指定範圍內查詢“由輸入的另外一對iterator標誌的第二個序列”中任意一個元素的第一次出現。過載版本中使 用了使用者自定義運算子。
find_if: 使用輸入的函式代替等於運算子執行find。
lower_bound: 返回一個ForwardIterator,指向在有序序列範圍內的可以插入指定值而不破壞容器順序的第一個位置。過載函 數使用自定義比較操作。
upper_bound: 返回一個ForwardIterator,指向在有序序列範圍內插入value而不破壞容器順序的最後一個位置,該位置標誌 一個大於value的值。過載函式使用自定義比較操作。
search: 給出兩個範圍,返回一個ForwardIterator,查詢成功指向第一個範圍內第一次出現子序列(第二個範圍)的位 置,查詢失敗指向last1。過載版本使用自定義的比較操作。
search_n: 在指定範圍內查詢val出現n次的子序列。過載版本使用自定義的比較操作。
<二>排序和通用演算法(14個):提供元素排序策略
inplace_merge: 合併兩個有序序列,結果序列覆蓋兩端範圍。過載版本使用輸入的操作進行排序。
merge: 合併兩個有序序列,存放到另一個序列。過載版本使用自定義的比較。
nth_element: 將範圍內的序列重新排序,使所有小於第n個元素的元素都出現在它前面,而大於它的都出現在後面。重 載版本使用自定義的比較操作。
partial_sort: 對序列做部分排序,被排序元素個數正好可以被放到範圍內。過載版本使用自定義的比較操作。
partial_sort_copy: 與partial_sort類似,不過將經過排序的序列複製到另一個容器。
partition: 對指定範圍內元素重新排序,使用輸入的函式,把結果為true的元素放在結果為false的元素之前。
random_shuffle: 對指定範圍內的元素隨機調整次序。過載版本輸入一個隨機數產生操作。
reverse: 將指定範圍內元素重新反序排序。
reverse_copy: 與reverse類似,不過將結果寫入另一個容器。
rotate: 將指定範圍內元素移到容器末尾,由middle指向的元素成為容器第一個元素。
rotate_copy: 與rotate類似,不過將結果寫入另一個容器。
sort: 以升序重新排列指定範圍內的元素。過載版本使用自定義的比較操作。
stable_sort: 與sort類似,不過保留相等元素之間的順序關係。
stable_partition: 與partition類似,不過不保證保留容器中的相對順序。
<三>刪除和替換演算法(15個)
copy: 複製序列
copy_backward: 與copy相同,不過元素是以相反順序被複製。
iter_swap: 交換兩個ForwardIterator的值。
remove: 刪除指定範圍內所有等於指定元素的元素。注意,該函式不是真正刪除函式。內建函式不適合使用remove和 remove_if函式。
remove_copy: 將所有不匹配元素複製到一個制定容器,返回OutputIterator指向被複製的末元素的下一個位置。
remove_if: 刪除指定範圍內輸入操作結果為true的所有元素。
remove_copy_if: 將所有不匹配元素複製到一個指定容器。
replace: 將指定範圍內所有等於vold的元素都用vnew代替。
replace_copy: 與replace類似,不過將結果寫入另一個容器。
replace_if: 將指定範圍內所有操作結果為true的元素用新值代替。
replace_copy_if: 與replace_if,不過將結果寫入另一個容器。
swap: 交換儲存在兩個物件中的值。
swap_range: 將指定範圍內的元素與另一個序列元素值進行交換。
unique: 清除序列中重複元素,和remove類似,它也不能真正刪除元素。過載版本使用自定義比較操作。
unique_copy: 與unique類似,不過把結果輸出到另一個容器。
<四>排列組合演算法(2個):提供計算給定集合按一定順序的所有可能排列組合
next_permutation: 取出當前範圍內的排列,並重新排序為下一個排列。過載版本使用自定義的比較操作。
prev_permutation: 取出指定範圍內的序列並將它重新排序為上一個序列。如果不存在上一個序列則返回false。過載版本使用 自定義的比較操作。
<五>算術演算法(4個)
accumulate: iterator對標識的序列段元素之和,加到一個由val指定的初始值上。過載版本不再做加法,而是傳進來的 二元運算子被應用到元素上。
partial_sum: 建立一個新序列,其中每個元素值代表指定範圍內該位置前所有元素之和。過載版本使用自定義操作代 替加法。
inner_product: 對兩個序列做內積(對應元素相乘,再求和)並將內積加到一個輸入的初始值上。過載版本使用使用者定義 的操作。
adjacent_difference: 建立一個新序列,新序列中每個新值代表當前元素與上一個元素的差。過載版本用指定二元操作計算相 鄰元素的差。
<六>生成和異變演算法(6個)
fill: 將輸入值賦給標誌範圍內的所有元素。
fill_n: 將輸入值賦給first到first+n範圍內的所有元素。
for_each: 用指定函式依次對指定範圍內所有元素進行迭代訪問,返回所指定的函式型別。該函式不得修改序列中的元素。
generate: 連續呼叫輸入的函式來填充指定的範圍。
generate_n: 與generate函式類似,填充從指定iterator開始的n個元素。
transform: 將輸入的操作作用與指定範圍內的每個元素,併產生一個新的序列。過載版本將操作作用在一對元素上,另外一 個元素來自輸入的另外一個序列。結果輸出到指定容器。
<七>關係演算法(8個)
equal: 如果兩個序列在標誌範圍內元素都相等,返回true。過載版本使用輸入的運算子代替預設的等於操 作符。
includes: 判斷第一個指定範圍內的所有元素是否都被第二個範圍包含,使用底層元素的<運算子,成功返回 true。過載版本使用使用者輸入的函式。
lexicographical_compare: 比較兩個序列。過載版本使用使用者自定義比較操作。
max: 返回兩個元素中較大一個。過載版本使用自定義比較操作。
max_element: 返回一個ForwardIterator,指出序列中最大的元素。過載版本使用自定義比較操作。
min: 返回兩個元素中較小一個。過載版本使用自定義比較操作。
min_element: 返回一個ForwardIterator,指出序列中最小的元素。過載版本使用自定義比較操作。
mismatch: 並行比較兩個序列,指出第一個不匹配的位置,返回一對iterator,標誌第一個不匹配元素位置。 如果都匹配,返回每個容器的last。過載版本使用自定義的比較操作。
<八>集合演算法(4個)
set_union: 構造一個有序序列,包含兩個序列中所有的不重複元素。過載版本使用自定義的比較操作。
set_intersection: 構造一個有序序列,其中元素在兩個序列中都存在。過載版本使用自定義的比較操作。
set_difference: 構造一個有序序列,該序列僅保留第一個序列中存在的而第二個中不存在的元素。過載版本使用 自定義的比較操作。
set_symmetric_difference: 構造一個有序序列,該序列取兩個序列的對稱差集(並集-交集)。
<九>堆演算法(4個)
make_heap: 把指定範圍內的元素生成一個堆。過載版本使用自定義比較操作。
pop_heap: 並不真正把最大元素從堆中彈出,而是重新排序堆。它把first和last-1交換,然後重新生成一個堆。可使用容器的 back來訪問被“彈出”的元素或者使用pop_back進行真正的刪除。過載版本使用自定義的比較操作。
push_heap: 假設first到last-1是一個有效堆,要被加入到堆的元素存放在位置last-1,重新生成堆。在指向該函式前,必須先把 元素插入容器後。過載版本使用指定的比較操作。
sort_heap: 對指定範圍內的序列重新排序,它假設該序列是個有序堆。過載版本使用自定義比較操作。
2。4 仿函式
2.4.1 概述
仿函式(functor),就是使一個類的使用看上去象一個函式。其實現就是類中實現一個operator(),這個類就有了類似函式的行為,就是一個仿函式類了。
有些功能的的程式碼,會在不同的成員函式中用到,想複用這些程式碼。
1)公共的函式,可以,這是一個解決方法,不過函式用到的一些變數,就可能成為公共的全域性變數,再說為了複用這麼一片程式碼,就要單立出一個函式,也不是很好維護。
2)仿函式,寫一個簡單類,除了那些維護一個類的成員函式外,就只是實現一個operator(),在類例項化時,就將要用的,非引數的元素傳入類中。
2.4.2 仿函式(functor)在程式語言中的應用
1)C語言使用函式指標和回撥函式來實現仿函式,例如一個用來排序的函式可以這樣使用仿函式
#include #include //int sort_function( const void *a, const void *b);int sort_function( const void *a, const void *b){ return *(int*)a-*(int*)b;} int main(){ int list[5] = { 54, 21, 11, 67, 22 }; qsort((void *)list, 5, sizeof(list[0]), sort_function);//起始地址,個數,元素大小,回撥函式 int x; for (x = 0; x < 5; x++) printf(“%i\n”, list[x]); return 0;}
2)在C++裡,我們透過在一個類中過載括號運算子的方法使用一個函式物件而不是一個普通函式。
#include #include using namespace std;templateclass display{public: void operator()(const T &x) { cout << x << “ ”; }};int main(){ int ia[] = { 1,2,3,4,5 }; for_each(ia, ia + 5, display()); system(“pause”); return 0;}
2.4.3 仿函式在STL中的定義
要使用STL內建的仿函式,必須包含標頭檔案。而標頭檔案中包含的仿函式分類包括
1)算術類仿函式
加:plus
減:minus
乘:multiplies
除:divides
模取:modulus
否定:negate
例子:
#include #include #include #include using namespace std; int main(){ int ia[] = { 1,2,3,4,5 }; vector iv(ia, ia + 5); //120 cout << accumulate(iv。begin(), iv。end(), 1, multiplies()) << endl; //15 cout << multiplies()(3, 5) << endl; modulus modulusObj; cout << modulusObj(3, 5) << endl; // 3 system(“pause”); return 0;}
2)關係運算類仿函式
等於:equal_to
不等於:not_equal_to
大於:greater
大於等於:greater_equal
小於:less
小於等於:less_equal
從大到小排序:
#include #include #include#include using namespace std; template class display{public: void operator()(const T &x) { cout << x << “ ”; }};int main(){ int ia[] = { 1,5,4,3,2 }; vector iv(ia, ia + 5); sort(iv。begin(), iv。end(), greater()); for_each(iv。begin(), iv。end(), display()); system(“pause”); return 0;}
3)邏輯運算仿函式
邏輯與:logical_and
邏輯或:logical_or
邏輯否:logical_no
除了使用STL內建的仿函式,還可使用自定義的仿函式,具體例項見文章3。4。7。2小結
2。5 容器介面卡
標準庫提供了三種順序容器介面卡:queue(FIFO佇列)、priority_queue(優先順序佇列)、stack(棧)
什麼是容器介面卡
介面卡是使一種事物的行為類似於另外一種事物行為的一種機制”,介面卡對容器進行包裝,使其表現出另外一種行為。例 如,stack >實現了棧的功能,但其內部使用順序容器vector來儲存資料。(相當於是vector表現出 了棧的行為)。
容器介面卡
要使用介面卡,需要加入一下標頭檔案:
#include //stack
#include //queue、priority_queue
定義介面卡
1、初始化
stack stk(dep);
2、覆蓋預設容器型別
stack > stk;
使用介面卡
2。5。1 stack
stack s;stack< int, vector > stk; //覆蓋基礎容器型別,使用vector實現stks。empty(); //判斷stack是否為空,為空返回true,否則返回falses。size(); //返回stack中元素的個數s。pop(); //刪除棧頂元素,但不返回其值s。top(); //返回棧頂元素的值,但不刪除此元素s。push(item); //在棧頂壓入新元素item
例項:括號匹配
#include#include#include#includeusing namespace std;int main(){ string s; stack ss; while (cin >> s) { bool flag = true; for (char c : s) //C++11新標準,即遍歷一次字串s { if (c == ‘(’ || c == ‘{’ || c == ‘[’) { ss。push(c); continue; } if (c == ‘}’) { if (!ss。empty() && ss。top() == ‘{’) { ss。pop(); continue; } else { flag = false; break; } } if (!ss。empty() && c == ‘]’) { if (ss。top() == ‘[’) { ss。pop(); continue; } else { flag = false; break; } } if (!ss。empty() && c == ‘)’) { if (ss。top() == ‘(’) { ss。pop(); continue; } else { flag = false; break; } } } if (flag) cout << “Match!” << endl; else cout << “Not Match!” << endl; }}
2.5.2 queue & priority_queue
queue q; //priority_queue q;q。empty(); //判斷佇列是否為空q。size(); //返回佇列長度q。push(item); //對於queue,在隊尾壓入一個新元素 //對於priority_queue,在基於優先順序的適當位置插入新元素 //queue only:q。front(); //返回隊首元素的值,但不刪除該元素q。back(); //返回隊尾元素的值,但不刪除該元素 //priority_queue only:q。top(); //返回具有最高優先順序的元素值,但不刪除該元素
3 常用容器用法介紹
3。1 vector
3。1。1 基本函式實現
1.建構函式
vector():建立一個空vector
vector(int nSize):建立一個vector,元素個數為nSize
vector(int nSize,const t& t):建立一個vector,元素個數為nSize,且值均為t
vector(const vector&):複製建構函式
vector(begin,end):複製[begin,end)區間內另一個數組的元素到vector中
2.增加函式
void push_back(const T& x):向量尾部增加一個元素X
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一個元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n個相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一個相同型別向量的[first,last)間的資料
3.刪除函式
iterator erase(iterator it):刪除向量中迭代器指向元素
iterator erase(iterator first,iterator last):刪除向量中[first,last)中元素
void pop_back():刪除向量中最後一個元素
void clear():清空向量中所有元素
4.遍歷函式
reference at(int pos):返回pos位置元素的引用
reference front():返回首元素的引用
reference back():返回尾元素的引用
iterator begin():返回向量頭指標,指向第一個元素
iterator end():返回向量尾指標,指向向量最後一個元素的下一個位置
reverse_iterator rbegin():反向迭代器,指向最後一個元素
reverse_iterator rend():反向迭代器,指向第一個元素之前的位置
5.判斷函式
bool empty() const:判斷向量是否為空,若為空,則向量中無元素
6.大小函式
int size() const:返回向量中元素的個數
int capacity() const:返回當前向量張紅所能容納的最大元素值
int max_size() const:返回最大可允許的vector元素數量值
7.其他函式
void swap(vector&):交換兩個同類型向量的資料
void assign(int n,const T& x):設定向量中第n個元素的值為x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素設定成當前向量元素
8.看著清楚
1。push_back 在陣列的最後新增一個數據
2。pop_back 去掉陣列的最後一個數據
。at-Domain Parked 得到編號位置的資料
4。begin 得到陣列頭的指標
5。end 得到陣列的最後一個單元+1的指標
6.front 得到陣列頭的引用
7。back 得到陣列的最後一個單元的引用
8。max_size 得到vector最大可以是多大
9。capacity 當前vector分配的大小
10。size 當前使用資料的大小
11。resize 改變當前使用資料的大小,如果它比當前使用的大,者填充預設值
12。reserve 改變當前vecotr所分配空間的大小
13。erase 刪除指標指向的資料項
14。clear 清空當前的vector
15。rbegin 將vector反轉後的開始指標返回(其實就是原來的end-1)
16。rend 將vector反轉構的結束指標返回(其實就是原來的begin-1)
17。empty 判斷vector是否為空
18。swap 與另一個vector交換資料
3.1.2 基本用法
#include < vector> using namespace std;
3.1.3 簡單介紹
Vector<型別>識別符號
Vector<型別>識別符號(最大容量)
Vector<型別>識別符號(最大容量,初始所有值)
Int i[5]={1,2,3,4,5}
Vector<型別>vi(I,i+2);//得到i索引值為3以後的值
Vector< vector< int> >v; 二維向量//這裡最外的<>要有空格。否則在比較舊的編譯器下無法透過
3.1.4 例項
3.1.4.1 pop_back()&push_back(elem)例項在容器最後移除和插入資料
#include #include #include using namespace std; int main(){ vectorobj;//建立一個向量儲存容器 int for(int i=0;i<10;i++) // push_back(elem)在陣列最後新增資料 { obj。push_back(i); cout<輸出結果為:
0,1,2,3,4,5,6,7,8,9, 0,1,2,3,4,
3.1.4.2 clear()清除容器中所有資料
#include #include #include using namespace std; int main(){ vectorobj; for(int i=0;i<10;i++)//push_back(elem)在陣列最後新增資料 { obj。push_back(i); cout<輸出結果為:
0,1,2,3,4,5,6,7,8,9,
3.1.4.3 排序
#include #include #include #include using namespace std; int main(){ vectorobj; obj。push_back(1); obj。push_back(3); obj。push_back(0); sort(obj。begin(),obj。end());//從小到大 cout<<“從小到大:”<輸出結果為:
從小到大:0,1,3, 從大到小:3,1,0,
1。注意 sort 需要標頭檔案
#include <algorithm>
2。如果想 sort 來降序,可重寫 sort
bool compare(int a,int b) { return a< b; //升序排列,如果改為return a>b,則為降序 } int a[20]={2,4,1,23,5,76,0,43,24,65},i; for(i=0;i<20;i++) cout<< a[i]<< endl; sort(a,a+20,compare);
3.1.4.4 訪問(直接陣列訪問&迭代器訪問)
#include #include #include #include using namespace std; int main(){ //順序訪問 vectorobj; for(int i=0;i<10;i++) { obj。push_back(i); } cout<<“直接利用陣列:”; for(int i=0;i<10;i++)//方法一 { cout<::iterator it;//宣告一個迭代器,來訪問vector容器,作用:遍歷或者指向vector容器的元素 for(it=obj。begin();it!=obj。end();it++) { cout<<*it<<“ ”; } return 0;}
輸出結果為:
直接利用陣列:0 1 2 3 4 5 6 7 8 9 利用迭代器:0 1 2 3 4 5 6 7 8 9
3.1.4.5 二維陣列兩種定義方法(結果一樣)
方法一
#include #include #include #include using namespace std; int main(){ int N=5, M=6; vector > obj(N); //定義二維動態陣列大小5行 for(int i =0; i< obj。size(); i++)//動態二維陣列為5行6列,值全為0 { obj[i]。resize(M); } for(int i=0; i< obj。size(); i++)//輸出二維動態陣列 { for(int j=0;j方法二
#include #include #include #include using namespace std; int main(){ int N=5, M=6; vector > obj(N, vector(M)); //定義二維動態陣列5行6列 for(int i=0; i< obj。size(); i++)//輸出二維動態陣列 { for(int j=0;j輸出結果為:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3。2 deque
所謂的deque是”double ended queue”的縮寫,雙端佇列不論在尾部或頭部插入元素,都十分迅速。而在中間插入元素則會比較費時,因為必須移動中間其他的元素。雙端佇列是一種隨機訪問的資料型別,提供了在序列兩端快速插入和刪除操作的功能,它可以在需要的時候改變自身大小,完成了標準的C++資料結構中佇列的所有功能。
Vector是單向開口的連續線性空間,deque則是一種雙向開口的連續線性空間。deque物件在佇列的兩端放置元素和刪除元素是高效的,而向量vector只是在插入序列的末尾時操作才是高效的。deque和vector的最大差異,一在於deque允許於常數時間內對頭端進行元素的插入或移除操作,二在於deque沒有所謂的capacity觀念,因為它是動態地以分段連續空間組合而成,隨時可以增加一段新的空間並連結起來。換句話說,像vector那樣“因舊空間不足而重新配置一塊更大空間,然後複製元素,再釋放舊空間”這樣的事情在deque中是不會發生的。也因此,deque沒有必要提供所謂的空間預留(reserved)功能。
雖然deque也提供Random Access Iterator,但它的迭代器並不是普通指標,其複雜度和vector不可同日而語,這當然涉及到各個運算層面。因此,除非必要,我們應儘可能選擇使用vector而非deque。對deque進行的排序操作,為了最高效率,可將deque先完整複製到一個vector身上,將vector排序後(利用STL的sort演算法),再複製回deque。
deque是一種優化了的對序列兩端元素進行新增和刪除操作的基本序列容器。通常由一些獨立的區塊組成,第一區塊朝某方向擴充套件,最後一個區塊朝另一方向擴充套件。它允許較為快速地隨機訪問但它不像vector一樣把所有物件儲存在一個連續的記憶體塊,而是多個連續的記憶體塊。並且在一個對映結構中儲存對這些塊以及順序的跟蹤。
3.2.1 宣告deque容器
#include // 標頭檔案deque deq; // 宣告一個元素型別為type的雙端佇列quedeque deq(size); // 宣告一個型別為type、含有size個預設值初始化元素的的雙端佇列quedeque deq(size, value); // 宣告一個元素型別為type、含有size個value元素的雙端佇列quedeque deq(mydeque); // deq是mydeque的一個副本deque deq(first, last); // 使用迭代器first、last範圍內的元素初始化deq
3.2.2 deque的常用成員函式
deque deq;
deq[ ]:用來訪問雙向佇列中單個的元素。
deq。front():返回第一個元素的引用。
deq。back():返回最後一個元素的引用。
deq。push_front(x):把元素x插入到雙向佇列的頭部。
deq。pop_front():彈出雙向佇列的第一個元素。
deq。push_back(x):把元素x插入到雙向佇列的尾部。
deq。pop_back():彈出雙向佇列的最後一個元素。
3.2.3 deque的一些特點
支援隨機訪問,即支援[ ]以及at(),但是效能沒有vector好。
可以在內部進行插入和刪除操作,但效能不及list。
deque兩端都能夠快速插入和刪除元素,而vector只能在尾端進行。
deque的元素存取和迭代器操作會稍微慢一些,因為deque的內部結構會多一個間接過程。
deque迭代器是特殊的智慧指標,而不是一般指標,它需要在不同的區塊之間跳轉。
deque可以包含更多的元素,其max_size可能更大,因為不止使用一塊記憶體。
deque不支援對容量和記憶體分配時機的控制。
在除了首尾兩端的其他地方插入和刪除元素,都將會導致指向deque元素的任何pointers、references、iterators失效。不過,deque的記憶體重分配優於vector,因為其內部結構顯示不需要複製所有元素。
deque的記憶體區塊不再被使用時,會被釋放,deque的記憶體大小是可縮減的。不過,是不是這麼做以及怎麼做由實際操作版本定義。
deque不提供容量操作:capacity()和reverse(),但是vector可以。
3.2.4 例項
#include#include#includeusing namespace std;int main(void){ int i; int a[10] = { 0,1,2,3,4,5,6,7,8,9 }; deque q; for (i = 0; i <= 9; i++) { if (i % 2 == 0) q。push_front(a[i]); else q。push_back(a[i]); } /*此時佇列裡的內容是: {8,6,4,2,0,1,3,5,7,9}*/ q。pop_front(); printf(“%d\n”, q。front()); /*清除第一個元素後輸出第一個(6)*/ q。pop_back(); printf(“%d\n”, q。back()); /*清除最後一個元素後輸出最後一個(7)*/ deque::iterator it; for (it = q。begin(); it != q。end(); it++) { cout << *it << ‘\t’; } cout << endl; system(“pause”); return 0;}
輸出結果:
3。3 list
3。3。1 list定義
List是stl實現的雙向連結串列,與向量(vectors)相比, 它允許快速的插入和刪除,但是隨機訪問卻比較慢。使用時需要新增標頭檔案
#include
3。3。2 list定義和初始化
listlst1; //建立空list
list lst2(5); //建立含有5個元素的list
listlst3(3,2); //建立含有3個元素的list
listlst4(lst2); //使用lst2初始化lst4
listlst5(lst2。begin(),lst2。end()); //同lst4
3.3.3 list常用操作函式
Lst1。assign() 給list賦值
Lst1。back() 返回最後一個元素
Lst1。begin() 返回指向第一個元素的迭代器
Lst1。clear() 刪除所有元素
Lst1。empty() 如果list是空的則返回true
Lst1。end() 返回末尾的迭代器
Lst1。erase() 刪除一個元素
Lst1。front() 返回第一個元素
Lst1。get_allocator() 返回list的配置器
Lst1。insert() 插入一個元素到list中
Lst1。max_size() 返回list能容納的最大元素數量
Lst1。merge() 合併兩個list
Lst1。pop_back() 刪除最後一個元素
Lst1。pop_front() 刪除第一個元素
Lst1。push_back() 在list的末尾新增一個元素
Lst1。push_front() 在list的頭部新增一個元素
Lst1。rbegin() 返回指向第一個元素的逆向迭代器
Lst1。remove() 從list刪除元素
Lst1。remove_if() 按指定條件刪除元素
Lst1。rend() 指向list末尾的逆向迭代器
Lst1。resize() 改變list的大小
Lst1。reverse() 把list的元素倒轉
Lst1。size() 返回list中的元素個數
Lst1。sort() 給list排序
Lst1。splice() 合併兩個list
Lst1。swap() 交換兩個list
Lst1。unique() 刪除list中相鄰重複的元素
3。3。4 List使用例項
3.3.4.1 迭代器遍歷list
for(list::const_iteratoriter = lst1。begin();iter != lst1。end();iter++) { cout<<*iter; } cout<3.3.4.2 綜合例項1
#include #include #include #include using namespace std; typedef list LISTINT;typedef list LISTCHAR; void main(){ //用LISTINT建立一個list物件 LISTINT listOne; //宣告i為迭代器 LISTINT::iterator i; listOne。push_front(3); listOne。push_front(2); listOne。push_front(1); listOne。push_back(4); listOne。push_back(5); listOne。push_back(6); cout << “listOne。begin()——- listOne。end():” << endl; for (i = listOne。begin(); i != listOne。end(); ++i) cout << *i << “ ”; cout << endl; LISTINT::reverse_iterator ir; cout << “listOne。rbegin()——-listOne。rend():” << endl; for (ir = listOne。rbegin(); ir != listOne。rend(); ir++) { cout << *ir << “ ”; } cout << endl; int result = accumulate(listOne。begin(), listOne。end(), 0); cout << “Sum=” << result << endl; cout << “——————————” << endl; //用LISTCHAR建立一個list物件 LISTCHAR listTwo; //宣告i為迭代器 LISTCHAR::iterator j; listTwo。push_front(‘C’); listTwo。push_front(‘B’); listTwo。push_front(‘A’); listTwo。push_back(‘D’); listTwo。push_back(‘E’); listTwo。push_back(‘F’); cout << “listTwo。begin()——-listTwo。end():” << endl; for (j = listTwo。begin(); j != listTwo。end(); ++j) cout << char(*j) << “ ”; cout << endl; j = max_element(listTwo。begin(), listTwo。end()); cout << “The maximum element in listTwo is: ” << char(*j) << endl; system(“pause”);}
輸出結果
3.3.4.3 綜合例項2
#include #include using namespace std;typedef list INTLIST; //從前向後顯示list佇列的全部元素 void put_list(INTLIST list, char *name){ INTLIST::iterator plist; cout << “The contents of ” << name << “ : ”; for (plist = list。begin(); plist != list。end(); plist++) cout << *plist << “ ”; cout << endl;} //測試list容器的功能 void main(void){ //list1物件初始為空 INTLIST list1; INTLIST list2(5, 1); INTLIST list3(list2。begin(), ——list2。end()); //宣告一個名為i的雙向迭代器 INTLIST::iterator i; put_list(list1, “list1”); put_list(list2, “list2”); put_list(list3, “list3”); list1。push_back(7); list1。push_back(8); cout << “list1。push_back(7) and list1。push_back(8):” << endl; put_list(list1, “list1”); list1。push_front(6); list1。push_front(5); cout << “list1。push_front(6) and list1。push_front(5):” << endl; put_list(list1, “list1”); list1。insert(++list1。begin(), 3, 9); cout << “list1。insert(list1。begin()+1,3,9):” << endl; put_list(list1, “list1”); //測試引用類函式 cout << “list1。front()=” << list1。front() << endl; cout << “list1。back()=” << list1。back() << endl; list1。pop_front(); list1。pop_back(); cout << “list1。pop_front() and list1。pop_back():” << endl; put_list(list1, “list1”); list1。erase(++list1。begin()); cout << “list1。erase(++list1。begin()):” << endl; put_list(list1, “list1”); list2。assign(8, 1); cout << “list2。assign(8,1):” << endl; put_list(list2, “list2”); cout << “list1。max_size(): ” << list1。max_size() << endl; cout << “list1。size(): ” << list1。size() << endl; cout << “list1。empty(): ” << list1。empty() << endl; put_list(list1, “list1”); put_list(list3, “list3”); cout << “list1>list3: ” << (list1 > list3) << endl; cout << “list1輸出結果:
3。4 map/multimap
map和multimap都需要#include
C++中map提供的是一種鍵值對容器,裡面的資料都是成對出現的,如下圖:每一對中的第一個值稱之為關鍵字(key),每個關鍵字只能在map中出現一次;第二個稱之為該關鍵字的對應值。
Map是STL的一個關聯容器,它提供一對一(其中第一個可以稱為關鍵字,每個關鍵字只能在map中出現一次,第二個可能稱為該關鍵字的值)的資料 處理能力,由於這個特性,它完成有可能在我們處理一對一資料的時候,在程式設計上提供快速通道。這裡說下map內部資料的組織,map內部自建一顆紅黑樹(一 種非嚴格意義上的平衡二叉樹),這顆樹具有對資料自動排序的功能,所以在map內部所有的資料都是有序的。
3.4.1 基本操作函式
begin() 返回指向map頭部的迭代器
clear() 刪除所有元素
count() 返回指定元素出現的次數
empty() 如果map為空則返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊條目的迭代器對
erase() 刪除一個元素
find() 查詢一個元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比較元素key的函式
lower_bound() 返回鍵值>=給定元素的第一個位置
max_size() 返回可以容納的最大元素個數
rbegin() 返回一個指向map尾部的逆向迭代器
rend() 返回一個指向map頭部的逆向迭代器
size() 返回map中元素的個數
swap() 交換兩個map
upper_bound() 返回鍵值>給定元素的第一個位置
value_comp() 返回比較元素value的函式
3.4.2 宣告
//標頭檔案#include
3.4.3 迭代器
共有八個獲取迭代器的函式:* begin, end, rbegin,rend* 以及對應的 * cbegin, cend, crbegin,crend*。
二者的區別在於,後者一定返回 const_iterator,而前者則根據map的型別返回iterator 或者 const_iterator。const情況下,不允許對值進行修改。如下面程式碼所示:
map::iterator it;map mmap;const map const_mmap; it = mmap。begin(); //iteratormmap。cbegin(); //const_iterator const_mmap。begin(); //const_iteratorconst_mmap。cbegin(); //const_iterator
返回的迭代器可以進行加減操作,此外,如果map為空,則 begin = end。
3.4.4 插入操作
3.4.4.1 用insert插入pair資料
//資料的插入——第一種:用insert函式插入pair資料 #include