Try   HackMD
tags: 社團事務

🗝 進階 C++ STL 迭代器

我們在之前的課程中介紹了基本功。
但是在實際上，若想要繼續走程式這條路，基本功實在遠遠不夠，接下來的學習大多是靠著自學方式進行，下的努力越多，收穫就會越多，加油！

STL ( Standard Template Library ) 迭代器 主要由 3 種東西構成：

  1. 迭代器 ( Iterator )
    使用者可以利用其逐一存取、宣告、使用 Container 中元素，常見的有 begin()、end() 等等

    index 0 1 2 3
    interator begin()+0 begin()+1 begin()+2 begin()+size()
    interator end()-size() end()-3 end()-2 end()-1

  2. 容器 ( Container )
    這個講義裡面的超級重點，配合迭代器及演算法讓你搖身一變變電神。

    應該注意：大部分的容器都具有通性( common methods )，需要特別注意喔

  3. 演算法 ( Algorithm )
    在團戰裡面的超強輔助的概念，有很多小功能用得好的話可以省下一堆時間，這裡面的功能有很多都是以前需要思考很久才寫出來的。

學習起來困難重重ㄏ，但是學起來就可以用的得心應手。
覺得英文很難不想看資料？ 覺得學不會想放棄？ 你們已經撐到這裡了，半途而廢絕對不是一個好選擇，認真、努力、勤練才是學習的捷徑喔！

🧬 前置處理器

以下介紹的東西，都是在編譯的預處理階段完成的，這部分的東西不會被編譯成機械語言，通常只會涉及代換的內容。

  • #define

    定義，它可以將之後程式出現之變數全部帶換成某值
    格式為：

    ​​​​#define 識別名稱 字串

    例如：

    ​​​​#define PI 3.14159

  • include

    除了 include 內建的標頭檔外，也可以 include 自己撰寫的標頭檔，例如：

    ​​​​#include "test.h"
​​​​#include <iostream>

    則會在main.cpp下的目錄找到 test.h 並將它 include 進去。

🥏 algorithm 函式庫

參考網站

algorithm 函式庫 是現代化 C++ 的代表之一，這裡扮演一個銜接初階與進階的一個踏板，裡面包含一些很厲害的功能，這裡來舉例一些很好用的函式ㄅ

  • max / min 最大最小值
    在 參數_1 和 參數_2 選最大最小值
    在 參數_1 和 參數_2 前一個位址 之範圍內選最大最小值

    ​​​​max(1,2);        // 回傳 2
​​​​min('a','z');    // 回傳 a

​​​​int num[] = {3,7,2,5,6,4,9};
​​​​*max_element(num,num + 7);    // 回傳 9
​​​​*min_element(num,num + 7);    // 回傳 2

​​​​// 這 2 個函式的參數和回傳值都是位址，所以需要配合指標使用

  • swap 置換 2 數
    置換 參數_1 和 參數_2

    ​int arr[] = { 3,7,2,5,6,4,9 };
​swap(arr[0],arr[1]); // 3,7 -> 7,3
​float a = 0.314;
​float b = 3.14;
​swap(a,b);	// 0.314,3.14 -> 3.14,0.314

  • sort 整理數列
    從 參數_1 到 參數_2前一個位址 作排序

    ​​​​int arr[] = { 3,7,2,5,6,4,9 };
​​​​sort( begin(arr), begin(arr)+3);    
​​​​//  (2 3 7) 5 6 4 9
​​​​sort( begin(arr)+4, end(arr));    
​​​​//  2 3 7 5 (4 6 9)
​​​​sort( arr, arr+7);
​​​​//  2 3 4 5 6 7 9

  • copy 複製數列
    從 參數_1 到 參數_2前一個位址 作複製

    ​​​​int arr[] = { 3,7,2,5,6,4,9 };
​vector<int> a(7) ;
​​​​copy(begin(arr)+4, end(arr),a.begin());  
​​​​// n = {6 4 9 0 0 0 0}
​copy(begin(arr), end(arr),a.begin());    
​​​​// n = {3 7 2 5 6 4 9}

  • reverse 翻轉數列
    從 參數_1 到 參數_2前一個位址 作翻轉

    ​​​​int arr[] = { 3,7,2,5,6,4,9 };
​​​​reverse(begin(arr)+4, end(arr));
​​​​// arr[] = {3 7 2 5 9 4 6}
​​​​reverse(begin(arr), end(arr))
​​​​// arr[] = {6 4 9 5 2 7 3}

  • find 尋找某值
    從 參數_1 到 參數_2前一個位址 作尋找

    ​int myints[] = { 10, 20, 30, 40 };
​​​int * p;

​​​p = find (myints, myints+4, 30);
​​​if (p != myints+4)	// 注意這裡的判斷句
​​​​	cout << "Element found in myints: " << *p << '\n';
​​​else
​​​​	cout << "Element not found in myints\n";

​​​vector<int> myvector (myints,myints+4);
​​​vector<int>::iterator it;

​​​it = find (myvector.begin(), myvector.end(), 30);
​​​if (it != myvector.end())
​​​​	cout << "Element found in myvector: " << *it << '\n';
​​​else
​	cout << "Element not found in myvector\n";

  • count 計算次數
    從 參數_1 到 參數_2前一個位址 作計算出現次數

    ​int myints[] = {10,20,30,30,20,10,10,20};   
​​​int mycount = count (myints, myints+8, 10);	// 計算出現次數
​​​cout << "10 appears " << mycount << " times.\n";

🥥 Container 容器

種類

STL容器的類型大致上可以分為這幾類，應用上可以簡略區分彼此

  • 序列式容器 ( Sequence containers )

    • 陣列 Array
    • 向量 Vector
    • 串列 List
    • 雙端佇列 Deque

  • 容器配接器 ( Sequence containers )

    • 堆疊 Stack
    • 佇列 Queue

  • 關聯性容器 ( Associative containers )

    • 集合 Set
    • 可重複集合 Multiset
    • 映射 Map
    • 可重複映射 Multimap

  • 無排序關聯性容器 (Unordered associative containers)

    • 無排序集合 Unordered_set
    • 無排序可重複集合 Unordered_multiset
    • 無排序映射 Unordered_map
    • 無排序可重複映射 Unordered_multimap

通性

在 STL 中容器大多具有下列函式之功能，在這邊先說，後面就不一一贅述ㄌ

  • 迭代器 Iterator

    1. begin()：指向首端之 iterator
    2. end()：指向尾端之 iterator 的下一個位置
    3. 其他
      • 反向迭代器：rbegin、rend
      • 常數迭代器：cbegin、cend
      • 常數反向迭代器：crbegin、crend
        註： rbegin 是 指向尾端元素，rend 是 指向首端元素的前一個位置

  • 大小 Capacity

    1. size()：容器內有多少元素
    2. empty()：是否已經清空所有元素

  • 接口 Access

    1. front()：回傳開口端元素值
    2. back()：回傳最尾端元素值

  • 功能 Modifier

    1. clear()：清空容器
    2. insert()：插入元素到指定位置，其餘位置順延
    3. erase()：消除指定位置的元素

介面

🎠 stack 堆疊

stack 是一種先進後出 ( FILO ) 的容器。
就像將書疊起來，先放下 的書要將 後放下 的書 移走後才能拿。

  • 圖示

函式

  • empty
  • size
  • top
  • push
  • pop
  • swap

🎭 queue 佇列

queue 是一種先進先出 ( FIFO ) 的容器。
就像排隊，先排入 的人可以比 後排入 的人 先離開。

  • 圖示

函式

  • empty
  • size
  • front
  • push
  • pop
  • swap

🎏 vector 向量

vector 是一種可以動態使用的陣列，相較於 C-style Array 更為常用。基本上寫 c++ 很建議使用 vector 取代低階的 array 和 pointer，比較易維護、容易除錯、活動度很高等等

這些是使用 vector 的特點：

  1. 支援隨機存取
  2. 尾端增刪元素很快 : O(1)
  3. 中間增刪元素比較費時 : O(n)

宣告

  • 一般宣告

    ​#include <vector> ;
​
​// vector<資料型態> <陣列名稱>;
​vector<int> a;

​// vector<float> <陣列名稱> = {初始值_1, 初始值_2, ...};
​vector<float> b = {1.14, 2.14, 3.14};
​
​vector<int> c(5);
​// 建立大小為 5 的 vector，且預設值為 0 
​
​vector<int> c(5,1);
​// 建立大小為 5 的 vector，且預設值為 1

    註：vector<int> a[10] 是指宣告出 10 個 int 型態的 vector

  • 引數型宣告

    ​#include <vector> ;
​
​vector<int> a = {1,2,3,4,5,6};

​// 完全複製 a 之內容到 b
​vector<int> b = a;
​vector<int> b(a);
​
​// 特定範圍
​vector<int> vec( v1.begin(), v1.end() ) // vec = {1,2,3,4,5,6}
​vector<int> vec( v1.begin()+1, v1.end()-1 ) // vec = {2,3,4,5}

    註：vec 中特定範圍宣告之第二參數為該參數前一位置

  • 二維宣告：

    ​vector<vector<int>> a;
​// 建立空的二維 vector ： a
​vector<vector<int>> b(10,vector<int>(10));  
​// 建立 10 * 10 之二維 vector ： b
​
​a.resize(10, vector<int>(10));
​// 將 a 變成 10*10 方陣，且原本的值不會被取代，但超過範圍的值會被抹去

  • 鏈結型二維宣告

    ​vector<int> ivec[10];

    這行就會像這張圖顯示的一樣宣告，因為 vector 的 templete 特性，所以可以當作一個動態鏈結串列使用。

    若是在之後加上這幾行：

    ​vector<int> ivec[10];
​ivec[0].push_back(10);
​ivec[0].push_back(20);
​.
​.
​.

    就會像這張圖顯示的一樣，可以變成一組長短不一的二維鏈結串列

    這裡附上參考資料，可以試著理解看看，這實在非常好用。

遍歷

遍歷( travel )，聽起來很難的名詞，其實就是全部順一次的意思，這邊介紹幾種方法以供選擇。

  • 索引遍歷 
    ​vector<int> v = {0, 1, 2, 3, 4};
​  
​for (int i = 0; i < v.size(); i++)
​  	cout << v[i] << '\n';
  • 迭代器遍歷 
    ​vector<int> v = {0, 1, 2, 3, 4};
​  
​// auto == vector<int>::iterator;
​for (auto itr = v.begin(); itr < v.end(); itr++)  
​​​​	cout << *itr << '\n';
  • auto + Range-based loop 遍歷
    詳情可以參閱這裡
    總之這裡的用法是真的很重要，大家要特別注意 
    ​vector<int> v = {0, 1, 2, 3, 4};
​	
​// int 不推薦
​for(int  i : v)
​	cout << i << ' ';
​	  
​// auto 不受歡迎，無法改變 i 值
​for (auto i : v)
​​​​	cout << i << ' ';
​	
​// auto& 較推薦
​for (auto &i : v)   // 非萬能像是遇到 bool 會掛掉
​​​​	cout << i << ' ';
​for (auto &&i : v)  // 這樣就可以解決了
​​​​	cout << i << ' ';
​	  
​// const auto&，只能讀值，同樣不能改值
​for (const auto &i : v)  
​​​​	cout << i << ' ';

函式

  • 增加元素
    我不知道怎麼形容這裡的重要，總之這邊絕對要會，這邊學會後學其他的就會很得心應手

    • push_back() 
      ​​vector<int> a ;
​​
​​a.push_back(1);  // a = {1}
​​a.push_back(2);  // a = {1,2}
​​a.push_back(3);  // a = {1,2,3}
​​
​​int i = 0;
​​a.push_back(i);  // a = {1,2,3,0}
​​int b[]={1,2,3};
​​a.push_back(b[0]);  // a= {1,2,3,0,1}
    • insert() 
      ​​vector<int> a={0,2,4,6};	
​​a.insert(a.begin()+1,1);  // 0,1,2,4,6
​​a.insert(a.begin()+3,3);  // 0,1,2,3,4,6
​​a.insert(a.begin()+5,5);  // 0,1,2,3,4,5,6
​​
​​// 特定範圍
​​// insert(目的地,複製地首位址,複製地尾位址後一格)
​​int num[]={7,8,9};
​​a.insert(a.end(),num.begin(),num.end());  // 0,1,2,3,4,5,6,7,8,9

    特別注意：另外有 emplace() 和 emplace_back() 的用法，有興趣可以了解一下。

  • 刪除元素
    有增加就有刪除，兩個同等重要，加油 o(〃＾▽＾〃)o

    • pop_back() 
      ​​vector<int> a = {1,2,3};
​​
​​a.pop_back();  // a = {1,2} 
​​a.pop_back();  // a = {1}
    • erase() 
      ​​vector<int> a = {1,2,3,4,5,6,7,8,9};
​​
​​a.erase(a.begin()+1);  // a = {1,3,4,5,6,7,8,9} 
​​a.erase(a.begin()+2);  // a = {1,3,5,6,7,8,9} 
​​a.erase(a.begin()+3);  // a = {1,3,5,7,8,9} 
​​
​​// 特定範圍
​​a.erase( a.end()-3 , a.end() );  // a = {1,3,5}

  • 其他

    • assign()

      ​​vector<int> a = { 0,2,4,6 };
​​int num[] = { 7,8,9 };
​​	
​​a.assign(begin(num), end(num));  // a = 7,8,9

      註：使用 assign() 將會取代原有元素，需特別注意

    • swap()

      ​​vector<int> a(3,100);
​​vector<int> b(5,200);
​​
​​swap(a,b);	
​​// a = 200 200 200 200 200
​​// b = 100 100 100

函式間傳遞

其實很多人即使對 vector 有初步的認知，卻會不知道 vector 在自己寫的函式中傳遞應該怎麼寫，這邊來為各位解惑。
大致分成這幾種：

  1. 傳值型
    這麼做會讓整個 vec 的構造重新拷貝一次，不符合效益，完全不建議使用。

    宣告：void 函式名( vector< int> a )
    呼叫：deal( vec )

  2. 傳遞引用型
    老實說，傳引用的函式不僅不會重新拷貝，函式寫的方式跟上面一模一樣。
    因此，絕對推薦大家使用引用傳遞

    void 函式名( vector< int>& a )
    deal( vec )
    void 函式名( const vector< int>& a )
    deal( vec )

  3. 傳遞指標型
    其實這個講起來挺複雜，應用起來不會那麼直觀，可以看完 map 之後再來了解

    void 函式名( vector< int>* a )
    void 函式名( const vector< int>* a )
    deal( &vec )
    deal( &vec )

範例：























#include <iostream>
#include <vector>
using namespace std; 
   
void func(vector<int> &vect) 
{ 
   vect.push_back(30); 
} 
   
int main() 
{ 
    vector<int> vect; 
    vect.push_back(10); 
    vect.push_back(20); 
   
    func(vect); 
  
    for (int i=0; i<vect.size(); i++) 
       cout << vect[i] << " "; 
   
    return 0; 
}

🛒 set 集合

set 是數學意義上的集合，你可以按照數學邏輯與程式相互搭配。
而 set 分成下列幾種，這些的應用各不相同，在上方 容器 那篇已經介紹過了，這邊就大概簡略使用與搭配：

  1. set：有排序、不含重複元素之集合
  2. multiset ：有排序、含重複元素之集合
  3. unordered set：無排序、不含重複元素之集合
  4. unordered multiset：無排序、含重複元素之集合

可是 set 的使用上需注意效率問題，一般會搭配演算法使用。

宣告

  • 一般宣告
    set 系列

    ​#include <set>

​set<int> a;		
​multiset<int> b;  
​// multiset 包括在 set 函式庫中

    unordered_set 系列

    ​#include <unordered_set>

​unordered_set<int> c;
​unordered_multiset<int> d;  
​// unordered_multiset 包括在 unordered_set 函式庫中

  • 引數宣告

    ​​​​int myints[] = {75,23,65,42,13};
​​​​
​​​​// 特定範圍
​​​​set<int> myset (myints,myints+5);

    註：set 中特定範圍為宣告之第二參數為該參數前一位置

遍歷

遍歷在 set 之中非常重要，畢竟身為一個集合，應用上就會需要去遍歷過所有元素。
而且與 vector 相比，較為不直觀，總之大家加油！

  • 迭代器遍歷
    大眾上比較常使用的版本，因為判斷條件較明顯 
    ​​for (auto it=myset.begin(); it != myset.end(); ++it)
​​​​	cout << ' ' << *it;
​// std::set<int>::iterator it = auto it
  • auto + Range-based loop 遍歷 
    ​for(auto i : a)
​  cout<< i << ' ';
​for(auto& i : a)
​  cout<< i << ' ';
​  
​ // set 裡都是不允許改值的，必竟性質不同
​// 所以這 2 種基本上在 set 的遍歷上代表意義一樣，只要遍歷即可

函式

  • 增加、刪除元素

    • insert() 插入元素

      ​​set<int> myset;
​​
​​// 定值插入
​​myset.insert(10);	// 10
​​int num = 10;
​​myset.insert(num*10);	// 10 100
​​
​​// 範圍插入
​​int a[]={5269,64,1978};
​​myset.insert(myints, myints + 3); // 10 64 100 1978 5269
​​
​​// 引數插入
​​pair< set<int>::iterator, bool> ret;
​​// pair(迭代器 ,是否存在 )
​​ret = myset.insert(20);   // no new element inserted
​​if (ret.second == false) 
​​  it = ret.first;  // "it" now points to element 20

​​myset.insert(it, 25);   // max efficiency inserting
​​myset.insert(it, 24);   // max efficiency inserting
​​myset.insert(it, 26);   // no max efficiency inserting

      註：其中 特定範圍 之範圍為 第一參數 到 插入的第二個該參數前一位置
      註：引數插入 為最高效率之方法，會使用到 pair 的觀念，mpa 那邊會有介紹

      特別注意：另外有 emplace() 和 emplace_hint() 的用法，有興趣可以了解一下。

    • erase() 刪除元素

      ​​set<int> myset;
​​for (int i=1; i<10; i++) 
​​  myset.insert(i*10);    // 10 20 30 40 50 60 70 80 90
​​// 定值刪除
​​​​myset.erase (40);
​​
​​// 引數刪除
​​it = myset.begin();
​​​​++it;    // "it" points now to 20
​​myset.erase (it);
​​
​​// 範圍刪除
​​​​it = myset.find (60);
​​​​myset.erase (it, myset.end());

      註：其中 特定範圍 之範圍為 第一參數 到 插入的第二個該參數前一位置

  • 查找、計算元素

    • count() 計算元素出現次數

      ​​int a[]={10,73,12,22,73,73,12};
​​​​multiset<int> num (a, a+7);
​​
​​cout << a.count(73);	// 輸出：3，因為 73 出現 3 次

      值得注意：在 set 中使用 count() 不是 1 就是 0，可以利用此性質檢查是否含有某元素

    • find() 尋找某值

      ​​int a[]={10,20,30,40,50,60,70,80,90};
​​set<int> num(begin(a), end(a));
​​
​​auot it = find(20);	// 回傳 20 之所在迭代器
​​// it 之後也可以應用
​​num.erase(it);

      值得注意：假如是 multi系列的只會回傳第一個找到的位址喔

  • 其他

    • swap 交換元素
      寫法是 a.swap(b) 而不是 swap(a,b) 喔

      ​​int num_1[] = { 1,2,3,4 };
​​int num_2[] = { 5,6,7,8 };
​​set<int> a(num_1, num_1+size(num_1));
​​set<int> b(begin(num_2),end(num_2));
​
​​a.swap(b);
​​// a = 5 6 7 8
​​// b = 1 2 3 4

    • upper_bound、lower_bound 值的上下限
      lower_bound 會回傳第一個 不小於 某值之迭代器，
      upper_bound 則會回傳第一個 大於 某值之迭代器

      ​​int num[]={1,2,5,8,11};
​​set<int> a(num, num + 5);
​​
​​auto itlow = a.lower_bound(6);  // itlow 指向 8 
​​itlow = a.lower_bound(5)  // itlow 指向 5
​​
​​auto itup = a.upper_bound(9);  // itup 指向 11
​​itup = a.upper_bound(8)  // itup 指向 11

    • equal_range 值的範圍
      可以把他想成是 lower_bound 跟 upper_bound 的組合
      而回傳值為 pair 型態，
      pair.first = lower_bound 回傳值
      pair.second = upper_bound 回傳值

      ​​int num[] = { 10,20,30,30,30,40,50,60 };
​​multiset<int> a(num, end(num));

​​auto itrange = a.equal_range(30);
​​cout << *itrange.first << ' ' << *itrange.second << endl;
​​// 輸出 30 40
​​
​​a.erase(itrange.first, itrange.second);
​​for (auto i : a)
​​	cout << i<<' ';
​​// 輸出 10 20 40 50 60

  • 數學上集合應用( algorithm )
    這邊是集合在數學上的主要功能，但是是寫在 algotithm 函式庫裡，參數也有點多，又會用到 iterator 函式庫的 inserter 函式。所以記得加上標頭檔喲。
    總之也點麻煩 o(TヘTo)

    set_集合運算(a.a.begin(),a.end(), b.begin(),b.end(), inserter(c,c.begin()))
    也就相當於 c = a 集合運算 b

    • set_union 聯集

      ​​#include <algorithm>
​​#include <iterator>
​​set<int> a;
​​set<int> b;
​​.
​​// a = 5 10 15 20 25
​​// b = 10 20 30 40 50
​​set<int> result;
​​
​​set_union(a.begin(),a.end(),
​​	   b.begin(),b.end(),
​​	   inserter(result,rusult.begin()))
​​// result =  5 10 15 20 25 30 40 50

    • set_intersection 交集

      ​​#include <algorithm>
​​#include <iterator>
​​set<int> a;
​​set<int> b;
​​.
​​// a = 5 10 15 20 25
​​// b = 10 20 30 40 50
​​set<int> result;
​​
​​set_intersection(a.begin(),a.end(),
​​	  	  b.begin(),b.end(),
​​	  	  inserter(result,rusult.begin()))
​​// result =  10 20

    • set_difference() 差集

      ​​#include <algorithm>
​​#include <iterator>
​​set<int> a;
​​set<int> b;
​​.
​​// a = 5 10 15 20 25
​​// b = 10 20 30 40 50
​​set<int> result;
​​
​​set_difference(a.begin(),a.end(),
​​	  	b.begin(),b.end(),
​​	  	inserter(result,rusult.begin()))
​​// result =  5 15 25

    • set_symmetric_difference 聯集 - 差集

      ​​#include <algorithm>
​​#include <iterator>
​​set<int> a;
​​set<int> b;
​​.
​​// a = 5 10 15 20 25
​​// b = 10 20 30 40 50
​​set<int> result;
​​
​​set_symmetric_difference(a.begin(),a.end(),
​​	  		  b.begin(),b.end(),
​​	  		  inserter(result,rusult.begin()))
​​// result =  5 15 25 30 40 50

    註：其實以上介紹之功能也能運用在 vector 或 tree 上，但是要先 sort 喔

    iterator函式庫
    這裡面也是充滿了怪物函示呢 (笑
    其中 prev、next、 inserer 都是較常使用的函式喔，詳請參考這邊

函式間傳遞

💥 map 映射

Last changed by 
 
itch w
0
20
9590
Published on HackMD