從零開始的演算法競賽入門教學
0%

0-16 STL簡介

發表於

STL 是什麼？

wiki

STL 簡單來說，就是容器，裝資料的容器。

之前，我們學習過的容器只有array而已，array的缺點有幾個：

  1. 不能改變大小
  2. 不能從前面插入元素(從前面插等於將整個陣列往後，可以想像，這超慢)
  3. 不能自動排序好元素(也就是，插入一個數字後要重新排序很慢)

但STL裡的容器很特別，他有：

  • 可以改變陣列大小的 vector
  • 可以從前方插入或移除元素的 deque、queue
  • 可以邊插入邊移除，一邊很快的排序的 set、map，以及priority_queue
  • 可以對 bool 陣列進行位元運算，大幅加快速度的 bitset

因此，學習使用 STL，能讓你的實力更上一層樓！

宣告

STL 的語法大致相近。

1
2
3
vector<int> v;
vector<string> ss;
vector<vector<int>> v2;

其中，想特別講一下<>。這是 C++ 裡的 template 功能，要用什麼型態就放在裡面，非常自由。想用二維陣列的話，就在 vector 裡面再包一個 vector 吧！

迭代器(iterator)

STL 中，有一個新的概念：迭代器。

寫得很好的教學文

以往，如果要找到一個陣列 arr 開頭的位置，我們可以直接寫 arr，因為 arr 本身其實只是一個指標而已。要找到陣列第 N 項的位置，就是 arr+N，因為記憶體在陣列裡是連續的，所以可以直接加，但這些在 STL 中是做不到的。

假設你宣告了一個 vector 名為 v，那這個 v 在之後的程式中，不是代表記憶體，而是整個容器。

因此若需要得到 v 開頭的位置，要寫： v.begin()。v 結束的位置要寫 v.end()。在 set 與 map 中將會有迭代器的進階應用。

成員函式(member function)

1
2
3
4
5
6
7
struct my_struct{
    int a, b, c;
} s;

int main(){
    s.a = 10;
}

像是之前的 struct，假設我要得到 s 裡的 a 這個值，要寫 s.a。

STL 中也有類似的概念，但是，裡面包的是函式！比如剛剛的 .begin()，呼叫它，得到的回傳值就是這個容器的開始位置。

因為是函式，所以會有()的存在。有些函式需要傳入參數，就像正常使用函式那樣，在()中傳入就可以了。

常見的成員函式有：

  • .begin()：容器的開始位置
  • .end() ：容器的結束位置
  • .size() ：回傳容器大小，型態是 unsigned int，拿來跟 int 比較(.size() > 5)沒有問題，但編譯器會噴警告。拿來進行運算則存在 overflow 風險(<0的時候，unsigned int 就 overflow)。
  • .empty() ：回傳容器是否為空，型態是 bool，盡量多使用 .empty()，而非 .size() == 0。
  • (vector).push_back(x)：在後方加入元素 x
  • (vector).pop_back()：移除最後方元素
  • (set map).insert(x)：加入元素 x

總結

STL 超好用的！

從下一章開始，將會一個一個介紹常用的 STL，請不知道是否存在的長期讀者們稍等一下！