STL Container

電腦中儲存、組織資料的方式，就成為資料結構

等等…那 STL 又是甚麼

• Standard Template Library
• 包含資料結構與演算法的模板
  -> 不用慢慢刻啦

函式庫

使用前記得 #includle <queue>

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

T 可以是任何資料型態
（int、char、自己寫的 struct、STL container）
注意：對空的 queue pop 會噴錯

函式庫

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(); // 有幾個元素？

這些都是O(1)操作

Example

想想看會輸出甚麼

#include <iostream>
#include <queue>
int main() {
    std::queue<int> myqueue;
    myqueue.push(0);
    myqueue.push(1);
    myqueue.push(2);
    myqueue.pop();
    myqueue.push(3);
    myqueue.pop();
 
    std::cout << "first element = " << myqueue.front() << "\n";
    std::cout << "last element = " << myqueue.back() << "\n";
    std::cout << "#element = " << myqueue.size() << "\n";
}

Example Answer

myqueue.push(0); // 0
myqueue.push(1); // 0 1
myqueue.push(2); // 0 1 2
myqueue.pop();   // 1 2
myqueue.push(3); // 1 2 3
myqueue.pop();   // 2 3

first element = 2
last element = 3
#element = 2

課堂練習

Neoj 37 Queue 練習

函式庫

使用前記得 #includle <stack>

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

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

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

T 可以是任何資料型態
這些都是O(1)操作

Example

想想看會輸出甚麼

#include <iostream>
#include <stack>
int main() {
    std::stack<int> mystack;
    mystack.push(0);
    mystack.push(1);
    mystack.push(2);
    mystack.pop();
    mystack.push(3);
    mystack.pop();
 
    std::cout << "last element = " << mystack.top() << "\n";
    std::cout << "#element = " << mystack.size() << "\n";
}

Example Answer

mystack.push(0); // 0
mystack.push(1); // 0 1
mystack.push(2); // 0 1 2
mystack.pop();   // 0 1
mystack.push(3); // 0 1 3
mystack.pop();   // 0 1

last element = 1
#element = 2

課堂練習

Neoj 36 Stack 練習

函式庫

使用前記得 #includle <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(); // 有幾個元素

T 可以是任何資料型態
這些都是O(1)操作

Example

想想看會輸出甚麼

#include <iostream>
#include <string>
#include <deque>

using namespace std;
struct student {
    int id;
    string name;
    student(int _id, string _name) {
        id = _id;
        name = _name;
    }
};

int main() {
    deque<student> s;
    s.push_back(student(15, "Alice"));
    s.push_front(student(23, "Bob"));
    s.push_front(student(32, "Carol"));
    std::cout << s.back().name << "\n";
    s.pop_back();
    std::cout << s.front().name << "\n";
    s.pop_front();
    std::cout << s.back().name << "\n";
}

Example Answer

s.push_back(student(15, "Alice"));  // {15, Alice}
s.push_front(student(23, "Bob"));   // {23, Bob} {15, Alice}
s.push_front(student(32, "Carol")); // {32, Carol} {23, Bob} {15, Alice}
std::cout << s.back().name << "\n"; 
s.pop_back();                       // {32, Carol} {23, Bob}
std::cout << s.front().name << "\n";
s.pop_front();                      // {23, Bob}
std::cout << s.back().name << "\n"; 

Dynamic Array

空間滿了再擴充到兩倍

Vector

• 就是一種 Dynamic Array
• 宣告

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

函式庫

使用前記得 #includle <vector>

std::vector<T> mv

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

Example

想想看會輸出甚麼

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> mv;
    for(int i = 0; i<5; ++i)
        mv.push_back(i);
    mv[3] = 100; // 就像陣列
    mv.pop_back();
    for(int i = 0; i<mv.size(); ++i)
        cout << mv[i] << " ";
}

Example Answer

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> mv;
    for(int i = 0; i<5; ++i)
        mv.push_back(i); // 0 1 2 3 4
    mv[3] = 100;         // 0 1 2 100 4
    mv.pop_back();       // 0 1 2 100
    for(int i = 0; i<mv.size(); ++i)
        cout << mv[i] << " ";  
}

0 1 2 100

如果要對 Vector 中間的元素做操作呢？
例如 刪除中間的元素、在中間插入元素

Recall

• 宣告一個指標 ptr
  • int *ptr;
  • double *ptr;
• int arr[10]
  • 開頭指標：arr / 結尾指標：arr + 10
• 看看指標指向甚麼
  • *ptr
• 變成下一個 pointer
  • ptr++

Vector & Iterator

• 宣告
  • vector<int>::iterator iter
• vector<int> mv
  • 開頭指標：mv.begin()
  • 結尾指標：mv.end()
• 看看 iterator 指向甚麼
  • *iter
• 變成下一個 iterator
  • iter++

Vector & Iterator

遍歷所有元素

vector<int>::iterator iter;
for(iter = mv.begin(); iter!=mv.end(); iter++)
    cout << *iter << " ";

插入 & 刪除

mv.insert(mv.begin()+2, 3);
mv.erase(mv.begin()+1);

auto

vector<int>::iterator iter = mv.begin();

auto iter = mv.begin();

• 一般的變數不會使用
• 有正確的型別概念才可以使用

auto

for(auto iter = mv.begin(); iter != mv.end(); iter++)
    cout << *iter << " ";

Range-based For

for(auto i : mv)
    cout << i << " ";

注意！

會輸出幾個'#'

vector<int> v(10);
for(auto i = v.size() ; i>=0 ; i--){
    cout << '#';
}

函式庫

使用前記得 #includle <list>

std::list<T> mylist     // 宣告
mylist.push_front(val); // 把資料放在最前面
mylist.push_back(val);  // 把資料放在最後面
mylist.pop_front();     // 刪除最前面的資料
mylist.pop_back();      // 刪除最後面的資料
std::list<T>::iterator it1 = mylist.begin();
std::list<T>::iterator it2 = mylist.end();
mylist.insert(it, val);
mylist.erase(it);

注意：list 的 iterator 可以 ++、– 但不能 +=k

Example

std::list<int> mylist;
for(int i = 0; i<5; ++i)
    mylist.push_back(i);

for(auto i : mylist)
    cout << i << " ";
cout << "\n";

erase

// 刪除 3
auto to_delete = mylist.begin();
for(int i = 0; i<3; ++i)
    to_delete++;
mylist.erase(to_delete);

for(auto i : mylist)
    cout << i << " ";
cout << "\n";

insert

// 把 5 插入在 2 之前
auto to_insert = mylist.begin();
for(int i = 0; i<2; ++i) 
    to_insert++;
mylist.insert(to_insert, 5);

for(auto i : mylist)
    cout << i << " ";
cout << "\n";

感覺 list 可以取代
stack, queue, deque和vector？？？

雖然 list 包含了很多好用的函式庫
但代價是速度很慢