Stack

後進先出(LIFO, Last-in-First-out)
先進後出(FILO, First-in-Last-out)

ex. 疊盤子

<stack>

std::stack<T> mystack // 宣告
mystack.push(val); // 加入元素（把書放在最上面，只能放在尾）
mystack.pop(); // 刪除元素（拿走最上面的一本書，只能刪除尾）

T t = mystack.top(); // 看看最後一個元素

bool emp = mystack.empty(); // 是空的嗎？
int size = mystack.size(); // 有幾個元素？

Queue

先進先出(FIFO, First-in-First-out)

ex. 排隊、等公車

<queue>

std::queue<T> myqueue // 宣告
myqueue.push(val); // 加入元素（不能插隊，只能放在尾端）
myqueue.pop(); // 刪除元素（讓排頭離開隊伍，只能刪除頭）

T f = myqueue.front(); // 看看第一個元素
T b = myqueue.back(); // 看看最後一個元素

bool emp = myqueue.empty(); // 是空的嗎？
int size = myqueue.size(); // 有幾個元素？

stack + queue

<deque>

std::deque<T> mydeque; // 宣告

mydeque.push_back(val); // 把資料放在最後面
mydeque.push_front(val); // 把資料放在最前面
mydeque.pop_back(); // 刪除最後面的資料
mydeque.pop_front(); // 刪除最前面的資料

T f = mydeque.front(); // 查看最前面的資料
T b = mydeque.back(); // 查看最後面的資料
bool emp = mydeque.empty(); // 是空的嗎？
int size = mydeque.size(); // 有幾個元素

Dynamic Array

capacity

query : size_t capacity()
modify : void reserve(size_t)

size

query : size_t size()
modify : void resize(size_t)

<vector>

std::vector<T> mv;
std::vector<T> mv2(n);     // 放n個東西
std::vector<T> mv3(n,val); // 放n個val

mv.push_back(val); // 把資料放在最後面
mv.pop_back();     // 刪除最後面的資料
bool emp = mv.empty(); // 是空的嗎
int size = mv.size();  // 有幾個元素

Declaration

Pointer

int arr[10];
int* ptr = arr;    // 指標指向陣列的頭

Container Pointer

vector<int> vec;
vector<int>::iterator it;
it = vec.begin();    // 迭代器指向vec的頭 
it = vec.end();      // 迭代器指向vec的尾

Loop & Search

Pointer

int arr[10];
for(ptr = arr ; ptr-arr<10 ; ptr++)
    cout<<(*ptr);

Container Pointer

vector<int> vec;
for(vector<int>::iterator it = vec.begin() ; it!=vec.end() ; it++)
    cout<<(*it);

Red Black Tree (R-B Tree)

<map> <set>
<multimap> <multiset>

Hash Table

<unordered_map> <unordered_set>
<unordered_multimap> <unordered_multiset>

<map>

std::map<T1, T2> m;        // 空的map
std::map<string, int> id;

id["Sally"] = 1;
id.insert(make_pair("Hsia",2));
id.insert(std::pair<string, int>("Wan",3));

cout<<id["Hsia"];            // 查詢

id.erase("Wan");             // 消除一個特定key
id.erase(id.find("Hsia"));   // 消除一個特定的位置

id.size();                   // 有幾個元素
id.empty();                  // 是空的嗎

// 遍歷所有的(key,value)
std::map<string, int>::iterator it;
for(it = id.begin() ; it != id.end() ; it++)        
    cout<<'('<<it->first<<','<<it->second<<")\n";

<set>

std::set<T> m;        // 空的set
std::set<char> alpha;

char arr[] = {'b','c','d','e'};
alpha.insert('a');           // 放一個
alpha.insert(arr,arr+4);     // 放好多個

if(alpha.find('b') != alpha.end());         // 有沒有元素
if(alpha.count('b');         // 有沒有元素

alpha.erase('a');            // 消除一個特定key
alpha.erase(alpha.find('b'));   // 消除一個特定的位置

alpha.size();                   // 有幾個元素
alpha.empty();                  // 是空的嗎

// 遍歷所有的元素
std::set<char>::iterator it;
for(it = alpha.begin() ; it != alpha.end() ; it++)        
    cout<<*it<<' ';

<list>

std::list<T> m;        // 空的list
std::list<int> ls;

int arr[] = {1,2,3,4};
ls.insert('a');           // 放一個
ls.insert(arr,arr+4);     // 放好多個
ls.insert(4,100);         // 放4個100

if(ls.find('b') != ls.end());         // 有沒有元素
if(ls.count('b');         // 有沒有元素

ls.erase('a');            // 消除一個特定key
ls.erase(ls.find('b'));   // 消除一個特定的位置

ls.size();                   // 有幾個元素
ls.empty();                  // 是空的嗎

// 遍歷所有的元素
std::list<int>::iterator it;
for(it = ls.begin() ; it != ls.end() ; it++)        
    cout<<*it<<' ';