🥗Container

容器

這裡簡單介紹幾個較常用到的容器，包括 : vector, set, map, list, queue, stack。

vector

Vector 可以看成是一個動態陣列 🎄，宣告時可不指定大小，需要時再追加元素😉，而且可以在中間插入(insert)、刪除(erase)元素。不過要注意在數量很大時，插入和刪除效率會不好的，如果有在最前面增加、刪除元素的需求可以用deque(雙端佇列)，效率會比較高喔。

引用自:https://larry850806.github.io/2016/06/06/STL1/

用起來跟陣列很像，常用功能有 :

• push_back : 把一個值加到尾巴

• pop_back : 把尾巴的值移除掉

• size : 得到目前長度

• [] : 得到某一個位置的值

• insert( vec.begin() + i, a) : 在第i+1個元素前面插入a

• erase( vec.begin() + i , vec.begin() + j ) //刪除區間 i ~ j-1

ex1.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<int> vec;    // 宣告一個裝 int 的 vector
                        // 現在 vec 是空的
    vec.push_back(10);
    vec.push_back(20);  // 經過三次 push_back
    vec.push_back(30);  // vec 是 [10, 20, 30]

    int length = vec.size();        // length = 3
    for(int i=0 ; i<length ; i++){
        cout << vec[i] << endl;     // 輸出 10, 20, 30
    }

    vec.pop_back();     // 移除 30

    for(int i=0 ; i<vec.size() ; i++){  // vec.size() = 3
        cout << vec[i] << endl;         // 輸出 10, 20
    }
}

ex2.cpp

#include<vector>
#include<iostream>
using namespace std;

int main() {
    vector<int> v(3);
    v[0]=2; //v[0]是第1個元素
    v[1]=7;
    v[2]=9;
    v.insert(v.begin(),8);//在最前面插入新元素。
    v.insert(v.begin()+2,1);//在迭代器中第二個元素前插入新元素
    v.insert(v.end(),3);//在向量末尾追加新元素。

    v.insert(v.end(),4,1);//在尾部插入4個1

    int a[] = {1,2,3,4};
    v.insert(v.end(),a[1],a[3]);//在尾部插入a[1]個a[3]，也就是2個4

    vector<int>::iterator it; //使用iterator存取
    for(it=v.begin(); it!=v.end(); it++) {
        cout<<*it<<" ";
    }
    cout<<endl;

    v.erase(v.begin()+2); //刪除第3個元素
    for(auto e : v)
        cout<<e<<" ";
    cout<<endl;

    v.erase(v.begin()+5,v.begin()+9); //刪除區間5~8

    for(auto e : v)
        cout<<e<<" ";
    cout<<endl;
}
/*
output :
    8 2 1 7 9 3 1 1 1 1 4 4
    8 2 7 9 3 1 1 1 1 4 4
    8 2 7 9 3 4 4
*/

set

Set 就是集合內部資料結構為一顆紅黑樹 (red-black tree)，裡面的元素都不會重覆，而且都會由小排到大，不過數量多時效率還是會糟的 !

引用自:http://blog.daum.net/_blog/BlogTypeView.do?blogid=0Nu8o&articleno=82&categoryId=7&regdt=20091210122155

基本功能有:

• insert() : 把一個數字放進集合

• erase() : 把某個數字從集合中移除

• count() : 檢查某個數是否有在集合中

ex3.cpp

#include <iostream>
#include <set>
using namespace std;

int main(){
    set<int> mySet;
    mySet.insert(20);   // mySet = {20}
    mySet.insert(10);   // mySet = {10, 20}
    mySet.insert(30);   // mySet = {10, 20, 30}

    cout << mySet.count(20) << endl;    // 存在 -> 1
    cout << mySet.count(100) << endl;   // 不存在 -> 0

    mySet.erase(20);                    // mySet = {10, 30}
    cout << mySet.count(20) << endl;    // 0
}

map

它提供搜尋和插入友善的資料結構，並具有一對一 mapping 功能：

• 第一個稱為關鍵字 (key)，每個關鍵字只能在 map 中出現一次。

• 第二個稱為該關鍵字的值 (value)。

Map 的 key-value 對應主要用於資料一對一映射 (one-to-one) 的情況，比如一個班級中，每個學生的學號跟他的姓名就存在著一對一映射的關係。

Map 的特色

• map 內部資料結構為一顆紅黑樹 (red-black tree)，因此：

  • 內部是有排序的資料。

  • 對於搜尋和插入操作友善( O(logn) )。

• 可以修改 value 值、不能修改 key 值。

• 以模板（泛型）方式實現，可以儲存任意類型的變數，包括使用者自定義的資料型態 。

引用自 : https://mropengate.blogspot.com/2015/12/cc-map-stl.html

1. 宣告

map<string, string> mapStudent;

2. 插入 insert()

// 用 insert 函數插入 pair
mapStudent.insert(pair<string, string>("r000", "student_zero"));

//用 "array" 方式插入
mapStudent["r123"] = "student_first";
mapStudent["r456"] = "student_second";

3. 尋找 find()

出現時，它返回資料所在位置，如果沒有，返回 iter 與 end() 函數的返回值相同。

iter = mapStudent.find("r123");

if(iter != mapStudent.end())
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Do not Find"<<endl;

引用自:https://mropengate.blogspot.com/2015/12/cc-map-stl.html

4. 刪除與清空

清空 map 中的資料可以用 clear() 函數，判定 map 中是否有資料用 empty() 函數，如果回傳 true 則 map 為空，而資料的刪除用 erase() 函數，它有三種 overload 的用法：

//迭代器刪除
iter = mapStudent.find("r123");
mapStudent.erase(iter);

//用關鍵字刪除
int n = mapStudent.erase("r123");//如果刪除了會返回1，否則返回0

//用迭代器範圍刪除 : 把整個map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同於mapStudent.clear()

完整範例 :

ex4.cpp

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){

    //declaration container and iterator
    map<string, string> mapStudent;
    map<string, string>::iterator iter;
    map<string, string>::reverse_iterator iter_r;

    //insert element
    mapStudent.insert(pair<string, string>("r000", "student_zero"));

    mapStudent["r123"] = "student_first";
    mapStudent["r456"] = "student_second";

    //traversal
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
                cout<<iter->first<<" "<<iter->second<<endl;
    for(iter_r = mapStudent.rbegin(); iter_r != mapStudent.rend(); iter_r++)
                cout<<iter_r->first<<" "<<iter_r->second<<endl;

    //find and erase the element
    iter = mapStudent.find("r123");
    mapStudent.erase(iter);

    iter = mapStudent.find("r123");

    if(iter != mapStudent.end())
       cout<<"Find, the value is "<<iter->second<<endl;
    else
       cout<<"Do not Find"<<endl;

    return 0;
}

list

list 是C++標準程式庫中的一個類，可以簡單視之為雙向連結串列，以線性列的方式管理物件集合。list 的特色是在集合的任何位置增加或刪除元素都很快，但是不支持隨機存取。

用法有 :

list.size()	計算長度
list.front()	取得開頭元素
list.back()	取得結尾元素
list.begin()	取得開頭元素之抽象指標
list.end()	取得結尾元素之抽象指標
list.push_front()	增加一個新的元素在 list 的前端
list.pop_front()	刪除 list 的第一個元素
list.push_back()	增加一個新的元素在 list 的尾端
list.pop_back()	刪除 list 的最末個元素
list.insert()	插入一個或多個元素至 list內的任意位置
list.erase()	刪除 list中一個或多個元素
list.reverse()	資料反置

ex5.cpp

#include <iostream> 
#include <list> 
#include <iterator> 
using namespace std; 

//function for printing the elements in a list 
void showlist(list <int> g) 
{ 
	list <int> :: iterator it; 
	for(it = g.begin(); it != g.end(); ++it) 
		cout << '\t' << *it; 
	cout << '\n'; 
} 

int main() 
{ 

	list <int> gqlist1, gqlist2; 


	for (int i = 0; i < 10; ++i) 
	{ 
		gqlist1.push_back(i * 2); 
		gqlist2.push_front(i * 3); 
	} 
	cout << "\nList 1 (gqlist1) is : "; 
	showlist(gqlist1); 

	cout << "\nList 2 (gqlist2) is : "; 
	showlist(gqlist2); 

	cout << "\ngqlist1.front() : " << gqlist1.front(); 
	cout << "\ngqlist1.back() : " << gqlist1.back(); 

	cout << "\ngqlist1.pop_front() : "; 
	gqlist1.pop_front(); 
	showlist(gqlist1); 

	cout << "\ngqlist2.pop_back() : "; 
	gqlist2.pop_back(); 
	showlist(gqlist2); 

	cout << "\ngqlist1.reverse() : "; 
	gqlist1.reverse(); 
	showlist(gqlist1); 

	cout << "\ngqlist2.sort(): "; 
	gqlist2.sort(); 
	showlist(gqlist2); 

	return 0; 
} 

queue

Queue 就像是排隊買東西 只能往尾巴排，然後從頭出來，但是需注意只能操作頭尾。

引用自 : https://pixabay.com/vectors/bank-queue-person-standing-atm-3527570/

基本功能有:

• push() : 把一個值加到尾巴

• pop() : 把第一個值移除掉

• back() : 得到尾巴的值

• front() : 得到頭的值

ex7.cpp

#include <iostream>
#include <queue>
using namespace std;
int main(){
    queue<int> q;       // 一個空的 queue
    for(int i=0 ; i<5 ; i++){
        q.push(i * 10);
    }                   // [0, 10, 20, 30, 40]

    while(q.size() != 0){
        cout << q.front() << endl;
        q.pop();
    }                   // 依序輸出 0 10 20 30 40
}

stack

Stack 就是一疊盤子，只能拿走最上面的，或是繼續往上疊。

引用自 : https://www.flickr.com/photos/eraphernalia_vintage/3033502393

基本功能有:

• top() : 得到最上面的值

• push() : 再拿一個盤子往上疊

• pop() : 拿掉最上面的盤子

ex8.cpp

#include <iostream>
#include <stack>
using namespace std;
int main(){
    stack<int> s;
    
    s.push(10);     //  | 30 |
    s.push(20);     //  | 20 |   疊三個盤子
    s.push(30);     //  |_10_|   10 在最下面

    for(int i=0 ; i<s.size() ; i++){    // s.size() = 3
        cout << s.top() << endl;
        s.pop();
    }                                   // 輸出 30, 20, 10
}