# 🥗Container

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

## vector

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

![引用自:https://larry850806.github.io/2016/06/06/STL1/](/files/-LwqEf8KcVQVHZrtvA4p)

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

* push\_back : 把一個值加到尾巴
* pop\_back : 把尾巴的值移除掉
* size : 得到目前長度
* \[] : 得到某一個位置的值
* insert( vec.begin() + i, a) : 在第i+1個元素前面插入a
* erase( vec.begin() + i , vec.begin() + j )  //刪除區間 i \~ j-1

{% code title="ex1.cpp" %}

```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
    }
}

```

{% endcode %}

{% code title="ex2.cpp" %}

```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
*/
```

{% endcode %}

## set

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

![引用自:http://blog.daum.net/\_blog/BlogTypeView.do?blogid=0Nu8o\&articleno=82\&categoryId=7\&regdt=20091210122155](/files/-Lwr9fjEEkHuanU3Pkpw)

#### 基本功能有: <a href="#ji-ben-gong-neng-you-2" id="ji-ben-gong-neng-you-2"></a>

* insert() : 把一個數字放進集合
* erase() : 把某個數字從集合中移除
* count() : 檢查某個數是否有在集合中

{% code title="ex3.cpp" %}

```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
}
```

{% endcode %}

## map

&#x20;它提供搜尋和插入友善的資料結構，並具有一對一 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](/files/-LwqIHJB5b_q1jGYLhCb)

**1. 宣告**

```cpp
map<string, string> mapStudent;
```

**2. 插入 insert()**

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

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

**3. 尋找 find()**

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

```cpp
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](https://3.bp.blogspot.com/-p2D7ql_iuFE/VmU7pe7zQrI/AAAAAAAA_Ks/WC3G3ADrKBE/s1600/27.7.png)

**4. 刪除與清空**

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

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

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

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

#### 完整範例 :

{% code title="ex4.cpp" %}

```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;
}
```

{% endcode %}

## **list**

&#x20;**list** 是[C++標準程式庫](https://zh.wikipedia.org/wiki/C%2B%2B%E6%A8%99%E6%BA%96%E7%A8%8B%E5%BC%8F%E5%BA%AB)中的一個[類](https://zh.wikipedia.org/wiki/%E9%A1%9E)，可以簡單視之為雙向[連結串列](https://zh.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E4%B8%B2%E5%88%97)，以線性列的方式管理物件集合。list 的特色是在集合的任何位置增加或刪除元素都很快，但是不支持隨機存取。

#### 用法有 :

| <p></p><p>list.size()</p>        | <p></p><p>計算長度 </p>                 |
| -------------------------------- | ----------------------------------- |
| <p></p><p>list.front() </p>      | <p></p><p>取得開頭元素 </p>               |
| <p></p><p>list.back() </p>       | <p></p><p>取得結尾元素 </p>               |
| <p></p><p>list.begin() </p>      | <p></p><p>取得開頭元素之抽象指標</p>           |
| <p></p><p>list.end() </p>        | <p></p><p>取得結尾元素之抽象指標</p>           |
| <p></p><p>list.push\_front()</p> | <p></p><p>增加一個新的元素在 list 的前端</p>    |
| <p></p><p>list.pop\_front()</p>  | <p></p><p>刪除 list 的第一個元素</p>        |
| <p></p><p>list.push\_back() </p> | <p></p><p>增加一個新的元素在 list 的尾端</p>    |
| <p></p><p>list.pop\_back() </p>  | <p></p><p>刪除 list 的最末個元素</p>        |
| <p></p><p>list.insert()</p>      | <p></p><p>插入一個或多個元素至 list內的任意位置</p> |
| <p></p><p>list.erase() </p>      | <p></p><p>刪除 list中一個或多個元素</p>       |
| <p></p><p>list.reverse()</p>     | <p></p><p>資料反置</p>                  |

{% code title="ex5.cpp" %}

```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; 
} 
```

{% endcode %}

## queue

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

![引用自 : https://pixabay.com/vectors/bank-queue-person-standing-atm-3527570/](/files/-LwrT2vbmo2C6OeqBDEM)

#### 基本功能有: <a href="#ji-ben-gong-neng-you" id="ji-ben-gong-neng-you"></a>

* push() : 把一個值加到尾巴
* pop() : 把第一個值移除掉
* back() : 得到尾巴的值
* front() : 得到頭的值

{% code title="ex7.cpp" %}

```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
}
```

{% endcode %}

## &#x20;stack

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

<div align="left"><img src="/files/-LwrTkUeACCf0bsnJYVQ" alt="引用自 : https://www.flickr.com/photos/eraphernalia_vintage/3033502393"></div>

#### 基本功能有: <a href="#ji-ben-gong-neng-you-1" id="ji-ben-gong-neng-you-1"></a>

* top() : 得到最上面的值
* push() : 再拿一個盤子往上疊
* pop() : 拿掉最上面的盤子

{% code title="ex8.cpp" %}

```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
}
```

{% endcode %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ncchen99.gitbook.io/ncc/container.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.