5 STL“容器”的使用與練習

"容器" 為什麼要加引號呢～請往下看

課程內容#

模板 <類型> 名；// 自定義類型也可以，如 struct

隊列與棧#

queue#

queue que;
名。方法 ()
- que.push (5); // 入隊
- que.pop (); // 出隊
- que.front (); // 隊首元素
- que.size (); // 元素個數
- que.empty (); // 是否為空

stack#

stack sta;
名。方法 ()
- sta.push(5);
- sta.pop();
- sta.top(); // 棧頂元素，唯獨與 queue 不一樣的
- sta.size();
- sta.empty();

本質#

它們的底層是由deque實現的
- double-ended queue，雙端隊列
- 參考deque-cppreference
它們是對 deque 的封裝，實際是適配器
- deque 才是正兒八經的容器

向量與優先隊列#

vector#

【插：在 C 語言中，不能定義變長數組，❌不可這樣定義：int n; scanf ("% d", &n); int num [n]】

vector v;
名。方法 ()
- v.push_back (5); // 在尾部添加一個元素O(1)
- v.size (); // 元素數量
- v.insert (1, 6); // 插入元素O(N)，用 push_back 更高效
vector<vector > v2; // 動態二維數組
- C++11 標準之前 "> >" 之間要有空格，否則易被誤認為是右移操作
初始化，參考vector 的幾種初始化及賦值方式-CSDN
cin 到 vector 需要先將 vector 初始化出空間大小

priority_queue#

priority_queue que;
- int 後可以添加排序的對象
- 參考C++ priority_queue (STL priority_queue) 用法詳解-C 語言中文網
名。方法 ()
- que.push(5);
- que.pop();
- que.top(); // 堆頂元素，默認是大數在上
- que.size();
- que.empty();
自定義結構型優先隊列需要重載小於號
- bool operator <(const struct 名 & 變量) {}
- 注：重載小於號，對於這個容器，在裡面實現的若是
  - a) <，則從大到小排列，對應最大堆
  - b) >，則從小到大排列，對應最小堆
  - 有點繞，詳細見代碼演示 - priority_queue
- 注：所有需要排序的容器結構，都是重載小於號

本質#

vector 底層是用數組實現的
priority_queue 底層是用堆實現的

字符串 string#

類

string str;
名。方法 ()
- str.size () // 等同於 str.length ()
- str.find (s2, pos = 0); // 在 str 中查找 s2，默認從頭 (pos = 0) 開始查找，找到返回下標
  - 底層方法實現取決於編譯器
  - 判斷是否找到（no position）

if (str,find(s2) != string::npos) {
  // static const size_t npos = -1;
  // 找到了
} else {
  // 未找到
}

- str.insert (x, s2); // 在下標 x 處插入 s2
- str.substr (2); // 從下標 2 截取到最後
- str.substr (2, len); // 注意第二個參數是長度
- str.replace (index, len, s2); // 同樣注意第二個參數是長度
重載了很多運算符
- +
  - string a = string("123") + string("a");
  - += 慎用
    - a += string ("123") + string ("456"); // "+=" 優先級僅高於 ","
    - ❓ 想像一下定義了多少臨時變量，值拷貝了多少次
- ==、>=、<=、>、<
  - 根據字典序判斷
- =
  - str = "123a"
  - 可以直接賦值，不像 C 語言需要使用 strcpy

鍵值對 map#

映射

map<string, int> m; // "123" → 456
方法
- []
  - 賦值、訪問
  - 如果訪問的 key 不存在，就會自動創建一個，按類型的默認值賦值
  - 有隱式開銷，因為底層是紅黑樹，查找效率為 O (logN)
- insert、find、erase
- count
  - 返回某個 key 多少個
  - 但 map 裡沒有重複的，所以只返回 0、1
  - 可用來判斷 key 是否存在
底層實現是紅黑樹【RBTree】
- 有序的結構，map 默認升序排
- 如果 key 對應的是自定義結構體，需重載 < 號
擴展
- multimap
  - 可以有多個重複的鍵存在
- unordered_map ❗c++11 裡出現
  - 無序
  - 底層實現是哈希表，查找、插入效率均為 O (1)
  - 自定義結構需要手動實現哈希函數
    - 參考C++ STL 無序容器自定義哈希函數和比較規則-C 語言中文網

集合 set#

可用來去重、排序
底層和 map 一樣，紅黑樹，必要時也需重載 “<”
擴展
- multiset
- unordered_set ❗c++11

對 pair#

對兒
pair<int, int>
- pair.first 前一元素
- pair.second 後一元素
make_pair可快速創建一個臨時的 pair

代碼演示#

queue#

兩種數據類型的隊列
que.empty () 和 que.size () 都是 O (1) 的，底層有一個數據域存儲
默認生成構造函數

輸出

stack#

與 queue 的區別：名字、頭文件、top () 方法

輸出

vector#

比數組更高級，在 leetcode 裡常用
3 種插入方式

輸出

priority_queue#

自定義結構型隊列要記得重載小於號
❗重載的是小於號，但完成的是從大到小輸出！

輸出

第二部分裡，實現了從大到小排列，但重載的是小於號，實現的也是小於號

map#

對於自定義結構，map 需重載 <，unordered_map 需定義 hash 函數
對於不存在的 key，訪問時會自動創建，並賦值類型的默認值

輸出

練習題#

HZOJ-383：週末舞會#

樣例輸入

3 5 6

樣例輸出

思路
- 隊列
- 出隊、放隊尾
代碼
- 隊列的基本操作

HZOJ-378：字符串括號匹配 2#

樣例輸入

a(cc[])bbb()@

樣例輸出

YES

思路
- 字符棧
- 匹配：YES，如 ([] )
- 不匹配：NO
  - 括號錯開了，如 ([) ]
  - 碰見右括號時，棧為空，如 ())
  - 字符串結束了，棧還不為空，如 (( {} )
- 注意：不能使用三個變量單純記錄個數，因為括號有順序問題，比如 ([)]
代碼
- 注意三種不匹配情況
- 匹配時將左括號出棧

HZOJ-376：機器翻譯#

樣例輸入

3 7
1 2 1 5 4 4 1

樣例輸出

思路
- 隊列
- 用標記數組記錄單詞
  - mark[x] = 1、0
  - 數據不大（文章長度不超過 1000），沒必要用 map、set 之類的
代碼
- 關鍵在存單詞的隊列和標記單詞的數組
- 注意內存已滿的情況

HZOJ-379：倉庫日誌#

樣例輸入

13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2

樣例輸出

思路
- 0、1、2：入庫、出庫、查詢
- 先進後出：需要一個貨物棧
- 查詢功能（輸出最大值）：還需要一個記錄最大值的棧 **【關鍵】**
- 注意：每次的貨物均不同，所以題目被簡化了
代碼
- 共兩個棧！
  - 對於本題，貨物棧可以不用，只是助於理解
  - 因為本題不需要管出棧的貨物是什麼，而最大棧每次入庫都記錄最大值，會重複記！

HZOJ-382：報數#

樣例輸入

7 3

樣例輸出

思路
- 約瑟夫環問題
- 【精髓】隊列：安全的人扔隊尾，不安全的人彈出去
- 結束條件：當隊列的 size 為 1 時
代碼
- push 的 i 是編號
- pop 沒有返回值嗎？
  - 這裡提到的容器裡，pop、push 都沒有返回值
  - 詳見pop-cppreference

HZOJ-384：敲七#

樣例輸入

4 3 6

樣例輸出

思路
- 與上題如出一轍，注意細節
- 區別在於
  - 輸入：第 x 個人從 t 開始報
  - 判斷條件：含 7 或者 7 的倍數
  - 報數不重置，一直 + 1
代碼

HZOJ-385：海港#

樣例輸入

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

樣例輸出

思路
- 輸入：到達時間、人数、每個人的國籍
- 隊列 +【標記數組 /map】+ 國家數量的變量
  - 隊列存船或人都可以
    - 因為船裡的人不固定，存人更方便
  - 先根據時間減人，再加人
  - 國家數量：如果新來一個，+1；如果走了最後一個，-1
代碼
- 關鍵在用到的隊列、標記數組和統計國家數量的變量
- 有點像滑動窗口？略像，但一般滑動窗口，其數據是早就固定好的
- 直接複製數據輸入，輸出格式有點奇怪？應該是換行符的問題
- 33 行快速定義構造體：(struct 名){..., ...}
  - 不加圓括號 () 也沒問題，但是加括號可能更清晰

HZOJ-569：溶液模擬器#

樣例輸入

樣例輸出

200 50.00000
100 100.00000

思路
- 撤銷操作：用棧！存每一次操作後的質量和濃度 [或者] 鹽的質量和總質量
- 化學知識回顧
  - 溶液組成：鹽 + 水
  - 濃度：鹽 / (鹽 + 水)
  - 質量：鹽 + 水
代碼
- 存鹽的質量和總質量便於理解計算
  - 都存為 double 類型，輸出時注意轉換
- 撤銷操作：先減再彈

LC-232：用棧實現隊列#

思路
- 兩個棧實現隊列
- 心中有這樣一個過程👇
代碼

class MyQueue {
public:
    // 在此處聲明棧，否則不好調用
    stack<int> s1, s2;
    /** Initialize your data structure here. */
    MyQueue() {
        // 不用管
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 先把s1棧的元素全倒到s2棧
        while (!s1.empty()) {
            // 先push再pop，順序不能反
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // 此時取出要pop的值
        s2.pop();          // 出棧
        // 倒回來
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        // 折騰到s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // 臨時變量t存值，還得放回來再return
        // 折騰回來
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();  // 直接判斷s1即可
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

- 每次操作完，值一直是存放在 s1 裡
- 棧的聲明位置：放在類的全局裡，才能被其他函數訪問
  - 放在初始化函數 MyQueue () 裡是否可以用 this 調用到？
  - ❌不行，this 指的是整個大類，之後學習類的時候注意
- 【進階】你能否實現每個操作均攤時間複雜度為 O (1) 的隊列？換句話說，執行 n 個操作的總時間複雜度為 O (n) ，即使其中一個操作可能花費較長時間。
  - 關鍵在於：pop 把元素從 s1 倒騰到 s2 的時候，不倒騰回來
  - 這樣 s2 的順序就是隊列出隊的順序
  - 每次 pop 只有 s2 為空時，才把 s1 的元素倒騰過來，否則直接 pop s2 即可
  - 參考用棧實現隊列 - 官方解答- 方法二

LC-225：用隊列實現棧#

思路
- 其實只需要一個隊列
  - 轉移元素時，放隊尾即可
    - ①可以在 push 的時候調整順序
    - ②也可以在 pop 的時候操作
  - 通過 queue.size () 控制轉移的邊界
代碼

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
        // 將前面的所有元素依次放到後面
        for (int i = 1; i < que.size(); i++) {
            que.push(que.front());
            que.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int t = que.front();
        que.pop();
        return t;
    }
    
    /** Get the top element. */
    int top() {
        return que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

Bo2SS

5 STL“容器”的使用與練習

課程內容#

隊列與棧#

queue#

stack#

本質#

向量與優先隊列#

vector#

priority_queue#

本質#

字符串 string#

鍵值對 map#

集合 set#

對 pair#

代碼演示#

queue#

stack#

vector#

priority_queue#

map#

練習題#

HZOJ-383：週末舞會#

HZOJ-378：字符串括號匹配 2#

HZOJ-376：機器翻譯#

HZOJ-379：倉庫日誌#

HZOJ-382：報數#

HZOJ-384：敲七#

HZOJ-385：海港#

HZOJ-569：溶液模擬器#

LC-232：用棧實現隊列#

LC-225：用隊列實現棧#

附加知識點#

思考點#

Tips#

課程速記#