資料結構與C++程式設計進階 C++標準樣板庫(STL) 講師：林業峻 CSIE, NTU 7/ 12, 2010.

Presentation on theme: "資料結構與C++程式設計進階 C++標準樣板庫(STL) 講師：林業峻 CSIE, NTU 7/ 12, 2010."— Presentation transcript:

1 資料結構與C++程式設計進階 C++標準樣板庫(STL) 講師：林業峻 CSIE, NTU 7/ 12, 2010

2 大綱 標準樣板庫 (STL) 抽象指標 (Iterator) 容器 (Container) 演算法 (Algorithm)

3 標準樣板庫 (STL) STL(Standard Template Library) 提供多種類別樣板與函式樣板以供使用
由以下三大部分所組成 Iterator: 抽象指標 Container: 容器 (類別樣板): vector, list, stack, queue, map,… Algorithm: 演算法 (函式樣板): find, sort, count,… 要訣: 用某資料結構存放資料 (容器) 用某演算法操作資料結構 (演算法) 用某指標表示某容器中之一個資料 (抽象指標)

4 STL參考網站

5 大綱 標準樣板庫 (STL) 抽象指標 (Iterator) 容器 (Container) 演算法 (Algorithm)

6 抽象指標(Iterator) 抽象指標是一種可以讓使用者逐一存取容器中元 素的工具。
STL中，各種容器均提供抽象指標做為使用者逐一 存取容器中元素管道。 宣告抽象指標語法： 容器::iterator it; 容器均有提供begin( ),end( )成員函數，讓使用者 取得容器的元素開頭與元素結尾的位址。 注意! 元素結尾指的是資料的結束(最後一個元素的下一個)

7 抽象指標(Iterator) 範例： 優點： 下例中list是STL中的一種容器，使用其中的抽象指標把其中 所有內容(元素)印出。
在結構中找前後一筆資料 之程式較為容易實作。 #include<iostream> #include<list> using namespace std; int main() { list<int> L; list<int>::iterator it; L.push_back(10); L.push_back(20); L.push_back(30); for (it = L.begin(); it != L.end(); it++) cout << *it <<" "; cout << endl; return 0; }

8 大綱 標準樣板庫 (STL) 抽象指標 (Iterator) 容器 (Container) 演算法 (Algorithm)

9 容器(Containers) Vector (向量) List (串列) Map (映射表)
動態陣列，此陣列可任意增長其大小，並提供隨機存取 List (串列) 雙向鏈結串列，支援循序雙向存取(無法隨機存取) Map (映射表) 支援查表功能之資料結構，資料均以key/value方式存入 其他容器… (stack, queue, set…)

10 向量 vector vector其特性如同陣列一樣，但又比內建的陣列 多了許多好用的功能
vector可以動態成長，可以將一個vector指定給另一個vector vector知道自己內含元素的個數。 常用函式 [n] 取得第索引值n之資料 size 計算長度 front 取得開頭元素 back 取得結尾元素 pop_back 移除結尾資料 push_back 新增資料於結尾 begin 取得開頭元素之抽象指標 end 取得結尾元素之抽象指標 insert 插入資料 erase 刪除資料

11 vector::vector 範例: 建立一個vector vector<資料型態> 物件名稱;
#include <iostream> #include <vector> using namespace std; int main () { int i; int myints[] = {16,2,77,29}; vector<int> v1 (myints, myints + 4); vector<int> v2; vector<int> v3(2); v2 = v1; //一般陣列無法這麼做 for (i=0; i < v2.size(); i++) //一般陣列無法用.size cout << " " << v2[i]; cout << endl; v3[0] = 100; v3[1] = 200; for (i=0; i < v3.size(); i++) cout << " " << v3[i]; return 0; }

12 vector::pop_back, push_back
範例 : 使用vector實作堆疊 (stack) #include <iostream> #include <vector> using namespace std; int main () { vector<int> v; int sum=0; v.push_back (100); v.push_back (200); v.push_back (300); while (!v.empty()) sum+=v.back(); v.pop_back(); //注意此pop不會回傳值, 只會把資料丟棄 } cout << "sum = " << sum << endl; return 0;

13 vector::begin, end 範例 : 使用抽象指標控制vector #include <iostream>
#include <vector> using namespace std; int main () { vector<int> v; vector<int>::iterator it; for (int i=1; i<=5; i++) v.push_back(i); for ( it=v.begin() ; it < v.end(); it++ ) cout << " " << *it; cout << endl; return 0; }

14 vector::insert 範例 : 插入資料 insert(向量插入位置, 資料);
// inserting into a vector #include <iostream> #include <vector> using namespace std; int main () { int i; vector<int> v; int a[] = { 10,20,30 }; v.insert (v.begin(), a, a+3); //插入一段資料於開頭 v.insert (v.begin()+1,15); //插入一筆資料於第二個位子 v.insert (v.end(),100); //插入一筆資料於最後 for (i=0; i<v.size(); i++) cout << " " << v[i]; cout << endl; return 0; }

15 vector::erase 範例 : 移除資料 erase(向量移除位置); erase(向量移除開始位置,向量移除結束位置);
#include <iostream> #include <vector> using namespace std; int main () { int i; vector<int> v; for (i=1; i<=10; i++) v.push_back(i); v.erase (v.begin()+5); //指定一筆資料 v.erase (v.begin(),v.begin()+3); //刪除一段資料 for (i=0; i<v.size(); i++) cout << " " << v[i]; cout << endl; return 0; }

16 串列 list list其特性主要為實作串列資料結構。 常用函式 size 計算長度 front 取得開頭元素 back 取得結尾元素
begin 取得開頭元素之抽象指標 end 取得結尾元素之抽象指標 pop_back, (pop_front) 移除結尾(開頭)資料 push_back, (push_front) 新增資料於結尾(開頭) insert 插入資料 erase 刪除資料 remove 指定一個資料內容,並刪除 reverse 資料反置 sort 資料排序

17 list::list 範例: 建立一個list list<資料型態> 物件名稱;
#include <iostream> #include <list> using namespace std; int main () { list<int>::iterator it; int a[] = {16,2,77,29}; list<int> L1 (a, a + 4); list<int> L2; L2 = L1; //跟vector一樣可以這麼做 for (it=L2.begin(); it!=L2.end(); it++) cout << " " << *it; //無法使用[], 使用抽象指標!! cout << endl; return 0; }

18 list::insert 範例: 插入節點 insert(向量插入位置, 資料);
#include <iostream> #include <list> using namespace std; int main () { list<int>::iterator it; list<int> L; int a[] = { 10,20,30 }; L.insert (L.begin(), a, a+3); //插入一段資料於開頭 // L.insert (L.begin()+1,15); //串列無法這麼做!! (資料不是連續的!) L.insert (L.end(),100); //插入一筆資料於最後 for (it=L.begin(); it!=L.end(); it++) cout << " " << *it; cout << endl; return 0; }

19 list::remove 範例: 刪除節點 remove(資料內容); #include <iostream>
#include <list> using namespace std; int main () { int a[]= {17,89,7,14}; list<int> L (a,a+4); list<int>::iterator it; L.remove(89); for (it=L.begin(); it!=L.end(); it++) cout << " " << *it; cout << endl; return 0; }

20 list::reverse 範例: 反轉串列 reverse(); #include <iostream>
#include <list> using namespace std; int main () { list<int> L; list<int>::iterator it; for (int i=1; i<10; i++) L.push_back(i); for (it=L.begin(); it!=L.end(); ++it) cout << " " << *it; cout << endl; L.reverse(); //反轉串列 return 0; }

21 list::sort 範例: 資料排序 sort(); #include <iostream>
#include <list> using namespace std; int main () { int a[]= {17,89,7,14}; list<int> L (a,a+4); list<int>::iterator it; for (it=L.begin(); it!=L.end(); ++it) cout << " " << *it; cout << endl; L.sort(); //排序 return 0; }

22 映射表 map map是一種關聯容器，支援查表功能之資料結構 ，資料均以key/value方式存入 key: 使用者自訂之索引值
常用函式 [n] 取得key值為n之value size 計算長度 erase 刪除資料 find 尋找資料之位置 insert 插入資料 count 判斷資料是否存在 lower_bound, (upper_bound) 取得接近下限(上限)之資料

23 map::map 範例: 建立一個map map<key值型態, value型態> 物件名稱;
#include <iostream> #include <map> #include <string> using namespace std; int main () { map<char,string> m; m['a']="Andy Lee"; //將"Andy Lee"放在'a'位置 m['b']="Joe Wang"; //將"Joe Wang"放在'b'位置 m['c']="Mary Lin"; //將"Mary Lin"放在'c'位置 cout << "m['a'] is " << m['a'] << endl; cout << "m['b'] is " << m['b'] << endl; cout << "m['c'] is " << m['c'] << endl; cout << "m now contains " << (int) m.size() << " elements." << endl; return 0; }

24 map::find, erase 範例: 尋找與刪除 find(key值); erase(key值); erase(位置);
// erasing from map #include <iostream> #include <map> using namespace std; int main () { map<char,int> m; map<char,int>::iterator it; // insert some values: m['a']=10; m['b']=20; m['c']=30; m['d']=40; m['e']=50; m['f']=60; it=m.find('b'); m.erase (it); // 刪除it位置之資料 m.erase ('c'); // 刪除key為'c'之資料 it=m.find ('e'); m.erase ( it, m.end() ); // 刪除一段資料 for ( it=m.begin() ; it != m.end(); it++ ) cout << (*it).first << " => " << (*it).second << endl; return 0; }

25 map::count 範例: 判斷資料是否存在 count(key值); #include <iostream>
#include <map> using namespace std; int main () { map<char,int> m; char c; m ['a']=101; m ['c']=202; m ['f']=303; for (c='a'; c<='h'; c++) cout << c; if (m.count(c)>0) cout << " yes.\n"; else cout << " no.\n"; } return 0;

26 map::lower_bound, upper_bound
範例: 取得接近下限(上限)之資料 lower_bound(key值); upper_bound( (key值); // map::lower_bound/upper_bound #include <iostream> #include <map> using namespace std; int main () { map<char,int> m; map<char,int>::iterator it,itlow,itup; m['a']=20; m['b']=40; m['c']=60; m['d']=80; m['e']=100; itlow=m.lower_bound ('b'); // 設定下限 itup=m.upper_bound ('d'); // 設定上限 m.erase(itlow,itup); // 刪除下限到上限所有資料 // print content: for ( it=m.begin() ; it != m.end(); it++ ) cout << (*it).first << " => " << (*it).second << endl; return 0; }

27 範例: STL鏈結串列應用 使用STL寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。
輸入d，接著輸入一個整數，將鏈結串列中刪除一筆該整數資 料。 輸入q後程式結束。 (LinkedList_STL.cpp)

28 大綱 標準樣板庫 (STL) 抽象指標 (Iterator) 容器 (Container) 演算法 (Algorithm)

29 演算法(Algorithm) STL中的演算法 在STL中除了提供容器(類別樣板), 尚提供演算法( 函式樣板)以供操作之資料
#include <algorithm> 常用演算法 find count search sort for_each transform

30 find: 尋找資料 find(first, last, val)
[回傳值]: 找到資料之位置 針對某個容器做搜尋，區間由first及last這兩個位 置，目標值為val，找到後回傳其所在元素位置 函數模板原型 template<class InIt, class T> InIt find(InIt first, InIt last, const T& val);

31 find 範例 使用容器 一般陣列 #include<iostream> #include<iostream>
#include<list> #include<algorithm> using namespace std; int main( ) { list<int> L; list<int>::iterator it; L.push_back(10) ; L.push_back(20); L.push_back(30); it = find(L.begin( ), L.end( ), 30); if ( it == L.end( )) //找不到 cout << "data not found\n"; else cout << *it << endl; return 0; } #include<iostream> #include<algorithm> using namespace std; int main( ) { int l[7] = { 1, 3, 2, 5, 1, 2, 1 }; int *it ; it = find(&l[0], &l[7], 5); if ( it == l+7) //找不到 cout << "data not found\n" ; else cout << *it << endl; return 0; }

32 count: 計算資料個數 count(first, last, val)
[回傳值]: 找到資料之個數 針對某個容器做搜尋，區間由first及last這兩個位 置，目標值為val，回傳容器中元素值為val的個數 函數模板原型 template<class InIt, class T> int count(InIt first, InIt last, const T& val);

33 count 範例 #include<iostream> #include<vector>
#include<algorithm> using namespace std; int main() { int a[7] = { 1, 3, 2, 4, 1, 2, 1}; vector<int> v(a,a+7); int count_of_1; count_of_1 = count(v.begin(), v.end(), 1); //計算1出現幾次 cout << "count of 1 = " <<count_of_1<<endl; return 0; }

34 search: 搜尋一段連續資料 search(s_first, s_last, t_first, t_last)
[回傳值]: 找到資料之位置 找尋某一資料序列是否出現在另一個容器中 函數模板原型 template<class FwdIt1, class FwdIt2> FwdIt1 search(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);

35 search 範例:在一般陣列中做搜尋 #include<iostream> #include<list>
#include<vector> #include<algorithm> using namespace std; int main( ) { int a[7] = { 1, 3, 2, 5, 1, 2, 1}; int b[7] = { 5, 1, 2}; int *it; it = search(a, a+7, b, b+3); if (it != a+7) //有找到 cout << *it << " " << *(it+1) << " " << *(it+2) << endl ; return 0; }

36 search 範例:在STL的vector與list容器中做搜尋 #include<iostream>
#include<list> #include<vector> #include<algorithm> using namespace std; int main( ) { int a[7] = { 1, 3, 2, 5, 1, 2, 1}; vector<int> v(a,a+7) ; vector<int>::iterator it ; list<int> L ; L.push_back(5); L.push_back(1); L.push_back(2) ; it = search(v.begin( ), v.end( ), L.begin( ), L.end( )); if (it != v.end( )) //有找到 cout << *it << " " << *(it+1) << " " << *(it+2) << endl ; return 0; }

37 sort: 資料排序 sort(first, last) sort(first, last, f) 資料排序 (預設由小到大) 函數模板原型
template<class RanIt> void sort(RanIt first, RanIt last); template<class RanIt, class Pred> void sort(RanIt first, RanIt last, Pred pr);

38 sort 範例: #include<iostream> #include<vector>
#include<algorithm> using namespace std; int greater(int x, int y) { return x>y; } int main() int a[7] = { 8, 1, 3, 2, 5, 1, 4}; vector<int> v(a,a+7); vector<int>::iterator it ; sort(v.begin( ), v.end( )) ; //由小排到大 for ( it = v.begin( ); it != v.end( ) ; it++) cout << *it <<" "; cout << endl; sort(v.begin( ), v.end( ), greater) ; //greater 由大排到小 return 0; 範例:

39 for_each: 對每個資料做同樣動作 for_each(first, last, f)
函數模板原型 template<class InIt, class Fun> void for_each(InIt first, InIt last, Fun f) ;

40 for_each 範例: #include<iostream> #include<list>
#include<algorithm> using namespace std; void print(int x) { cout << x << " "; } void add(int &x) x = x+5; int main( ) list<int> L ; L.push_back(10); L.push_back(20) ; L.push_back(30) ; for_each(L.begin( ), L.end( ), print) ; cout << endl; for_each(L.begin( ), L.end( ), add) ; return 0; 範例:

41 transform: 對每個資料做同樣動作並放到容器
transform(first, last, output, f) [first]: 資料開始位置 [last]: 資料結束位置 [output]: 輸出容器 [f]: 功能函式 [回傳值]: void 同for_each，但會把結果放在output容器中 函數模板原型 template<class InIt, class OutIt, class Unop> void transform(InIt first, InIt last, OutIt x, Unop uop);

42 transform 範例: #include<iostream> #include<list>
#include<vector> #include<algorithm> using namespace std; void print(int x) { cout << x << " "; } int add(int x) return x+5; //注意這行不是x=x+5 int main( ) list<int> L ; vector<int> v(3) ; L.push_back(10); L.push_back(20) ; L.push_back(30) ; transform(L.begin( ), L.end( ), v.begin(), add) ; for_each(L.begin( ), L.end( ), print) ; cout << endl; for_each(v.begin( ), v.end( ), print) ; return 0; transform 範例:

43 範例: STL鏈結串列應用 使用STL寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。
輸入f，接著輸入一個整數，印出該整數是否存在鏈結串列中 輸入d，接著輸入一個整數，將鏈結串列中刪除一筆該整數資 料。 輸入l，印出鏈結串列中所有內容。 輸入q後程式結束。 (LinkedList_STL.cpp)