C++ 容器
===
[糞Game製作大師](https://www.facebook.com/kauhiant/)
[前篇:C++記憶體](https://hackmd.io/s/HJZKTyVtM#)
---
> [color=#5ff555]
> * 容器就是用來儲存東西的，它儲存的東西是**特定類別**，所以不能把不同類別的東西存在同一個容器。
> * 通常每一種容器都會有**迭代器**來依序訪問容器內的每個元素。
> * 通常每一種容器都會有類似的幾種功能，這方便我們記憶，但是這些功能會依照容器的類型而有不同的處理速度，所以要**依據我們想做的事來選擇使用的容器**。
---
## template
> 不同容器內可儲存的型態不一樣
> 但不需要為此而另外寫一個class
> 可以利用template做出一個共同的模板
> *在這裡，我們只需要知道怎麼使用就好*
// define
```cpp=1
// 定義一個模板
template<class T>
class test{
public:
T val;
test(T val):val(val){}
};
```
// main()
```cpp=10
// 利用Test<T>來生成物件
// t1,t2分別屬於兩個不一樣的class
test<int> t1(12);
test<string> t2("123");
```
---
## 迭代器的概念
> 是一種容器專用的**指標**，指向容器內的元素
> 他的概念就像下面的 `i`一樣，
> 可以說`i`是`arr`陣列的迭代器
```cpp=
// 定義一個 大小為10的int陣列
int arr[10];
// 依序訪問這個陣列裡的每個元素
// i=0 :從第0個元素開始
// i!=10:arr的大小為10，所以不會訪問到arr[10]
// ++i :往下一個元素
for(int i=0; i!=10; ++i){
arr[i];// arr內的某個元素
}
```
---
## 迭代器的用法
> 迭代器的用法跟指標很像
> 可以把它當作一個**指向容器內某元素**的指標
```cpp=
// 一個<儲存型態為int>的vector
vector<int> test;
// 一個可指向 vector<int>內的元素 的迭代器
vector<int>::iterator it;
// 訪問test的每個元素
for(it=test.begin(); it!=test.size(); ++it){
*it;// test內的某個元素
}
// 有迭代器就能使用foreach
for(auto e : test){
e;// test內的某個元素的副本
}
```
---
## 共同介面
> 所有的容器都可使用以下兩種方法
```cpp=
size_t size (); // 容器內有幾個元素
bool empty(); // 此容器是不是空的
```
---
---
# 序列容器
> [color=#ff5555]
>
> container<Type>
> 序列容器內的元素會有先後順序。
> 可以把它想像成一整排的資料
> 所有序列容器都可使用以下幾類方法
---
> 迭代器、反向迭代器
```cpp=
iterator begin(); // 傳回指向第一個元素的迭代器
iterator end(); // 傳回指向最後一個元素!!之後!!的迭代器
reverse_iterator rbegin(); // 傳回指向!!倒數!!第一個元素的迭代器
reverse_iterator rend(); // 傳回指向第一個元素!!之前!!的迭代器
```
---
> 內容修改 swap, clear, insert, erase
swap, clear
```cpp=
// 和另一個同類型的容器交換內容
void swap (container& x);
// 清空容器
void clear();
```
---
insert
```cpp=
// 在$position之前插入一個值為$value的元素
// 回傳指向新插入元素的迭代器
iterator insert (iterator position, Type value);
// 在$position之前插入$n個值為$value的元素
void insert (iterator position, size_t n, Type value);
// 在$position之前插入一排內容
// 範圍是 [ $first , $last )
// InputIterator可以是跟此容器相同或不同類別的迭代器，
// 但兩個容器儲存的類型要一樣
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
```
---
erase
```cpp=
// 刪除$position所指向的元素
// 回傳指向下一個元素的迭代器
iterator erase (iterator position);
// 刪除範圍是 [ $first , $last )的元素
// 回傳指向下一個元素的迭代器 (就是$last)
iterator erase (iterator first, iterator last);
```
---
> 首尾元素
```cpp=
Type& front(); // 回傳第一個元素的參考
Type& back (); // 回傳最後一個元素的參考
```
---
## [vector<Type>](http://www.cplusplus.com/reference/vector/vector/)
> [color=#5555ff]
>
> 雖然叫向量，但我認為跟向量沒什麼關係。
> vector是一個**動態陣列**，
> 它的陣列大小會自動增加，所以容量大小我們不用去管它。
> 因為是陣列，元素在記憶體中是連續的，所以支援隨機存取，速度也是容器中**最快**的。
---
> 隨機存取
```cpp=
// 傳回容器內第$index個元素的參考
Type& at (size_t index);
Type& operator[](size_t index);
```
---
> 單向push,pop
> *push:如過vector的容量已滿，會自動新增一個更大的陣列，
> 並將原本的所有內容全部複製到新的陣列。*
```cpp=
// 在容器最後端新增一個值為$value的元素
void push_back(Type value);
// 將容器最後端的元素移除
void pop_back ();
```
---
## [list<Type>](http://www.cplusplus.com/reference/list/list/)
> [color=#5555ff]
>
> 就是雙向linked-list。
> 因為是linked-list，在容器任一節點做插入刪除或是改變順序都很方便，不會因元素數量而改變。
> 因為每個節點是靠指標連起來的，所以不像陣列一樣可以隨機存取，必須依順序一個個迭代。
---
> 雙向push,pop
```cpp=
// 在容器最後端新增一個值為$value的元素
void push_back (Type value);
// 將容器最後端的元素移除
void pop_back ();
// 在容器最前端新增一個值為$value的元素
void push_front(Type value);
// 將容器最前端的元素移除
void pop_front ();
```
---
> 其他功能
> 因為做插入刪除或是改變順序都很方便，所以功能也比其他容器多
```cpp=
// 排序，由小到大
void sort();
// 合併排序，由小到大，$x的所有元素會被移至此list
void merge (list& x);
// 把$x的所有元素合併到此list的$position之前
void splice (iterator position, list& x);
// 把$x內$index所指向的元素合併到此list的$position之前
void splice (iterator position, list& x, iterator index);
// 把$x的範圍[first,last)內的所有元素合併到此list的$position之前
void splice (iterator position, list& x, iterator first, iterator last);
// 將容器中每個連續的相同元素中除了第一個元素之外的所有元素刪除
void unique();
// 把容器中所有值為$value的元素刪掉
void remove (Type value);
// 把容器中元素的順序反轉
void reverse();
```
---
## [deque<Type>](http://www.cplusplus.com/reference/deque/deque/)
> [color=#5555ff]
>
> 雙向queue，用起來像雙向vector，可以在前後兩端增加刪除，也可以隨機存取。
> 看起來像是兩個vector，後面的vector就和原本的vector一樣，~~但前面的vector我看不懂他是怎麼實作出來的。~~
---
> 隨機存取
```cpp=
// 傳回容器內第$index個元素的參考
Type& at (size_t index);
Type& operator[](size_t index);
```
---
> 雙向push,pop
```cpp=
// 在容器最後端新增一個值為$value的元素
void push_back (Type value);
// 將容器最後端的元素移除
void pop_back ();
// 在容器最前端新增一個值為$value的元素
void push_front(Type value);
// 將容器最前端的元素移除
void pop_front ();
```
---
---
# 特定小功能容器
> [color=#ff5555]
>
> 和其他類型的容器的差別是:
> 沒有迭代器，所以不能用foreach
> 沒有內容修改器，只能以push,pop來修改內容
> 因為只是要使用一些小功能，所以能使用的方法很少，但卻簡單好上手
---
## [stack<Type>](http://www.cplusplus.com/reference/stack/stack/)
> [color=#5555ff]
>
> 資料結構的**stack**，可用來反轉
```cpp=
// 存取頂端元素
Type& top();
// 在容器頂端放入或丟出元素
void push(Type value);
void pop();
```
---
## [queue<Type>](http://www.cplusplus.com/reference/queue/queue/)
> [color=#5555ff]
>
> 資料結構的**queue**，可用來緩衝
```cpp=
// 傳回首尾元素的參考
Type& front();
Type& back ();
// 在容器尾端加入元素
void push(Type value);
// 在容器首端丟出元素
void pop();
```
---
## [priority_queue<Type>](http://www.cplusplus.com/reference/queue/priority_queue/)
> [color=#5555ff]
>
> 資料結構的**max heap**，可用來排序
```cpp=
// 傳回頂端元素的參考
Type& top();
// 在容器內加入或丟出元素
void push(Type value);
void pop();
```
---
---
# 關聯性容器
> [color=#ff5555]
>
> 不知道怎麼解釋...
> *用二元搜尋樹實作出來的*，算是以set為主的類型
> 能用的功能有迭代器、內容修改，但並非和序列容器一樣
---
> 迭代器、反向迭代器
```cpp=
iterator begin(); // 傳回指向第一個元素的迭代器
iterator end(); // 傳回指向最後一個元素!!之後!!的迭代器
reverse_iterator rbegin(); // 傳回指向!!倒數!!第一個元素的迭代器
reverse_iterator rend(); // 傳回指向第一個元素!!之前!!的迭代器
```
---
> 內容修改 swap, clear, insert, erase
swap, clear
```cpp=
// 和另一個同類型的容器交換內容
void swap (container& x);
// 清空容器
void clear();
```
---
insert
```cpp=
// 在$position前插入值為$value的元素，但不一定會真的插在那個位置
// 回傳插入的位置，不一定是$position
// 如果位置選好的話，插入速度為常數
iterator insert (iterator position, Type value);
// 在容器內插入一排內容
// 範圍是 [ $first , $last )
// InputIterator可以是跟此容器相同或不同類別的迭代器，
// 但兩個容器儲存的類型要一樣
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
```
---
erase
```cpp=
// 刪除$position所指向的元素
// (C++11)回傳指向下一個元素的迭代器
void erase (iterator position);
// 刪除範圍是 [ $first , $last )的元素
// (C++11)回傳指向下一個元素的迭代器 (就是$last)
void erase (iterator first, iterator last);
```
---
## [set<Type>](http://www.cplusplus.com/reference/set/set/)
> [color=#5555ff]
>
> 離散數學教的集合，可以用來過濾重複元素，還會自動排序(大到小)。
> 為了符合集合的定義，它會自動將內部元素**轉為const**型態，以防止使用者亂修改。
```cpp=
// 在容器內找出指向 值為$value的元素 的迭代器，
// 若找不到回傳this.end()
iterator find (Type value);
// 在容器內找出 值為$value的元素 的數量。(1 or 0)
// 在set中沒什麼明顯作用
size_t count(Type value);
```
```cpp=
// 在容器內插入一個值為$value的元素
// 若此元素插入前已存在，傳回 <該元素的位置 ,false>
// 若此元素插入前不存在，傳回 <插入後該元素的位置,true>
pair<iterator,bool> insert (Type value);
// 刪除與value相等的元素
// 回傳刪除的數量(1 or 0)
// 在set中沒什麼明顯作用
size_t erase (Type value);
```
---
## [map<Key, Value>](http://www.cplusplus.com/reference/map/map/)
> [color=#5555ff]
>
> Type == <Key, Value>
> 離散數學教的函數，一對一、一對多
> 跟C#的dictionary差不多
> 它和set很像。 map<K,V> 大概等於 set<pair<K,V>>
> 內容元素 pair<K,V>，一對key-value
```cpp=
// 傳回 key==$k的元素的 value的參考
// 若無此元素，插入 pair($k,default) 到容器中
Value& operator[] (Key k);
// 傳回 指向key==$k的元素 的迭代器
// 若找不到回傳this.end()
iterator find (Key k);
// 在容器內的key找出此元素的數量。
size_t count(K key);
```
```cpp=
// 在容器內插入一個值為$p的元素
// 若此元素插入前已存在，傳回 <該元素的位置 ,false>
// 若此元素插入前不存在，傳回 <插入後該元素的位置,true>
pair<iterator,bool> insert (pair<K,V> p);
// 刪除key為$k的元素
// 回傳刪除的數量(1 or 0)
size_t erase (Key k);
```
---
## [multiset<Type>](http://www.cplusplus.com/reference/set/multiset/)
> [color=#5555ff]
>
> 跟set很像，差別在裡面的元素可以重複。
> 但它還是會自動將內部元素**轉為const**型態，以防止使用者亂修改。
```cpp=
// 在容器內找出指向 值為$value的元素 的第一個迭代器，
// 若找不到回傳this.end()
iterator find (Type value);
// 傳回所有 值為$value的元素 的迭代器
// 範圍 [pair.first , pair.second)
// 若找不到回傳this.end()
pair<iterator,iterator> equal_range (Type value);
// 在容器內找出 值為$value的元素 的數量。
size_t count(Type value);
```
```cpp=
// 在容器內插入一個值為$value的元素
// 若已存在，在那個元素後面插入
iterator insert (Type value);
// 刪除與value相等的元素
// 回傳刪除的數量
size_t erase (Type value);
```
---
## [multimap<Key, Value>](http://www.cplusplus.com/reference/map/multimap/)
> [color=#5555ff]
>
> 跟map很像，差別在裡面的Key可以重複。
> 但它還是會自動將內部元素的Key**轉為const**型態，以防止使用者亂修改。
```cpp=
// 傳回 指向key==$k的元素 的第一個迭代器
// 若找不到回傳this.end()
iterator find (Key k);
// 傳回所有 指向key==$k的元素
// 範圍 [pair.first , pair.second)
// 若找不到回傳this.end()
pair<iterator,iterator> equal_range (Key k);
// 在容器內的key找出此元素的數量。
size_t count(K key);
```
```cpp=
// 在容器內插入一個值為$p的元素
// 若已存在，在那個元素後面插入
iterator insert (pair<K,V> p);
// 刪除key為$k的元素
// 回傳刪除的數量
size_t erase (Key k);
```
---
## [留言區](https://hackmd.io/IYIxAYEYoUwWgByQEzjgFmAgrHE6B2AZjgDMEBOC9GANhCOWwqA=#)
> 有什麼話要講，請用編輯模式在上面留言
> [color=#555555][name=kauhiant]
###### tags: `cpp`
Sign in with Wallet
Connect another wallet