---
# System prepended metadata

title: STL

---

STL


1. vector

會自動allocate memory的array

example

    vector<int> vec;
    vec.push_back(2);
    cout << vec[0] << endl; //2
    int lastElement = vec.back(); //2
    vec.pop_back(); //vec become empty

可以一開始先allocate好一些空間, 並給予init value
    
    vector<int> initWithOne(10, 1); //size = 10, value = 1

也可以是nested
    
    vector<vector<int>> twoDimVec;
    

應用: 存Graph
例如說有一堆edge存在 vector\<int\> edges, 以及node數量n, 我們可以轉成Adj list

    void SomeGraphProblem(vector<vector<int>> edges, int n)
    {
        vector<vector<int>> Graph(n); //allocate n vectors
        for(auto edge : edges)
        {
            //Assume graph is undirected
            Graph[edge[0]].push_back(edge[1]);
            Graph[edge[1]].push_back(edge[0]);
        }
    }
    

STL的element通常都可以混合使用, 比如說

    vector<unordered_map<int, int>> hashMapVec(n);

應用: DP, 當state不一定都在整數, 或者數字可能過大
https://leetcode.com/problems/target-sum/description/

    class Solution {
    public:
        vector<unordered_map<int, int>> index2Target2Ans;
        int CountWays(vector<int>& nums, int target, int curIndex)
        {
            int n = nums.size();
            if(curIndex == n && target == 0)
            {
                return 1;
            }
            if(curIndex == n)
            {
                return 0;
            }
            if(index2Target2Ans[curIndex].find(target) != index2Target2Ans[curIndex].end())
            {
                return index2Target2Ans[curIndex][target];
            }
            int plus = target - nums[curIndex];
            int minus = target + nums[curIndex];
            return index2Target2Ans[curIndex][target] = (CountWays(nums, plus, curIndex + 1) + CountWays(nums, minus, curIndex + 1));
        }

        int findTargetSumWays(vector<int>& nums, int target) {
            index2Target2Ans.resize(nums.size());
            return CountWays(nums, target, 0);
        }
    };

    
2. queue


宣告, 同樣可塞其他STL/Type
    
    queue<int> intQueue;
    queue<pair<int,int>> pairQueue;
    queue<vector<int>> vecQueue;
    queue<TreeNode*> treeNodeQueue;


Member function
    
    queue<int> intQueue;
    intQueue.push(1);
    intQueue.push(2);
    intQueue.push(3);
    while(!intQueue.empty()) //intQueue.size() > 0
    {
        int cur = intQueue.front();
        intQueue.pop();
        cout << cur ;
    }
    // 1, 2, 3

    
應用: BFS 

example1. BFS on tree
https://leetcode.com/problems/binary-tree-level-order-traversal/

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> leverOrderResult;
            if(!root)
            {
                return leverOrderResult;
            }
            queue<TreeNode*> NodeQueue;
            NodeQueue.push(root);

            while(!NodeQueue.empty())
            {
                queue<TreeNode*> nextRoundQueue;
                vector<int> curLevel;
                while(!NodeQueue.empty())
                {
                    TreeNode* cur = NodeQueue.front();
                    NodeQueue.pop();
                    curLevel.push_back(cur->val);
                    if(cur->left)
                    {
                        nextRoundQueue.push(cur->left);
                    }
                    if(cur->right)
                    {
                        nextRoundQueue.push(cur->right);
                    }
                }
                leverOrderResult.push_back(curLevel);
                NodeQueue = nextRoundQueue;
            }
            return leverOrderResult;
        }
    };

example2. BFS on graph/state
https://leetcode.com/problems/keys-and-rooms/

    class Solution {
    public:
        bool canVisitAllRooms(vector<vector<int>>& rooms) {
            int n = rooms.size();
            vector<vector<int>> graph(n);
            for(int i = 0 ; i < n ; i++)
            {
                vector<int> &keys = rooms[i];
                for(int key : keys)
                {
                    graph[i].push_back(key);
                }
            }

            queue<int> roomQueue;
            roomQueue.push(0);
            vector<bool> visted(n, false);
            visted[0] = true;
            int roomRemain = n;
            while(!roomQueue.empty())
            {
                int curRoom = roomQueue.front();
                roomQueue.pop();
                roomRemain --;
                for(int nextRoom : graph[curRoom])
                {
                    if(!visted[nextRoom])
                    {
                        visted[nextRoom] = true;
                        roomQueue.push(nextRoom);
                    }
                }
            }
            return roomRemain == 0;

        }
    };


3. stack


宣告
    
    stack<int> intStack;
    stack<pair<int,int>> pairStack;
    
Member function

    stack<int> intStack;
    intStack.push(1);
    intStack.push(2);
    intStack.push(3);
    while(!intStack.empty())
    {
        int cur = intStack.top();
        intStack.pop();
        cout << cur;
    }
    //3 2 1
    
    
應用:monotonic stack
在一個array中, 往左/右找第一個比自己大/小的

以Next Greater Element I為例, 題目要求:
對於每個nums1的數, 找到他在nums2裡面, 第一個往右找比他大的數
我們可以用一個hash map: unordered_map<int, int> num2NextGreater來存在nums2中
每個數, 第一個往右比較更大的數字為何

比如說nums2 = [1,3,4,2]
1往右比第一個比他大的是3
3往右比第一個比他大的是4
4往右比找不到比他大的數字, 依照題目要求, 答案為-1
2有右比找不到更大, 答案為-1

我們可以maintain一個stack, 從array的右邊開始掃, 如果目前stack最上方的數字
比目前看到的數字小, 則我們從stack pop該數字, 最後再push目前的數字
跑一下上面的範例
i = 3, original stack = [] , updated stack = [2]
i = 2, original stack = [2], stack = [4]
i = 1, original stack = [4], 此時在我們發現3無法讓4 pop出去, 這代表從右掃過來, 4是第一個比3大的數字, stack = [4,3]
i = 0, original stack = [4,3], 此時我們發現1無法讓3 pop出去, 這代表從右邊掃過來, 3是第一個比1大的數字
stack = [4,3,1]

我們發現最後stack的內容是單調的


https://leetcode.com/problems/next-greater-element-i/

    class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            unordered_map<int, int> num2NextGreater;
            stack<int> monoStack;
            int n = nums2.size();
            for(int i = n - 1 ; i >= 0 ; i --)
            {
                while(!monoStack.empty() && nums2[i] > monoStack.top() )
                {
                    monoStack.pop();
                }
                if(!monoStack.empty())
                {
                    num2NextGreater[nums2[i]] = monoStack.top();
                }
                else
                {
                    num2NextGreater[nums2[i]] = -1;
                }
                monoStack.push(nums2[i]);
            }
            vector<int> ret(nums1.size());
            for(int i = 0; i  < nums1.size() ; i++)
            {
                ret[i] = num2NextGreater[nums1[i]];
            }
            return ret;
        }
    };


4. unordered_map/map

unordered_map: implementation為hash, average O(1), key必須能算hash
map: implementation為red-black tree, O(logn), key必須能比大小

map的用法會跟vector/array類似, 都是用operator [] , 但vector/array的[]代表offset, 
map的[]代表access/update某個key

宣告

    unordered_map<int, int> num2num;
    unordered_map<char, int> char2num;
    unordered_map<string, int> string2num;
    unordered_map<int, string> num2string;
    
    
Member function

    num2string[5] = "abcdefg";
    num2num[0] = 5;
    if(num2num.find(2) == num2num.end())
    {
        cout << "Key 2 not exist\n";
    }
    
    if(num2num.find(5) == num2num.end())
    {
        cout << "Key 5 not exist\n";
    } //Will NOT output this line, find based on key
    
    num2num.erase(2)  // Remove key 2 from map
    
    
    


應用: DP存state (參考vector)

應用: 用string當成key
https://leetcode.com/problems/group-anagrams/
    
    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            unordered_map<string, vector<string>> ana2Group;
            for(string &str : strs)
            {
                string tmp = str;
                sort(tmp.begin(), tmp.end());
                ana2Group[tmp].push_back(str);
            }
            vector<vector<string>> ret;
            for(auto it : ana2Group)
            {
                ret.push_back(it.second);
            }
            return ret;
        }
    };

應用: 用char當成key
https://leetcode.com/problems/longest-substring-without-repeating-characters/

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            unordered_map<char, int> word2Count;
            int n = s.size();
            int left = 0;
            int ans = 0;
            for(int i = 0 ; i < n ; i++)
            {
                if(word2Count.find(s[i]) == word2Count.end())
                {
                    word2Count[s[i]] = 1;
                }
                else
                {
                    word2Count[s[i]] ++;
                }
                while(word2Count[s[i]] > 1)
                {
                    word2Count[s[left]] --;
                    left ++;
                }
                ans = max(ans, i - left + 1);
            }
            return ans;
        }
    };

應用: 把pointer to list node當key
https://leetcode.com/problems/copy-list-with-random-pointer/description/


    class Solution {
    public:
        Node* copyRandomList(Node* head) {
            unordered_map<Node*, Node*> old2New;
            Node* oldCur = head;
            Node* newHead = nullptr;
            while(oldCur != nullptr)
            {
                Node* curRandom = oldCur->random;
                Node* curNext = oldCur->next;
                Node* newCur = nullptr;
                Node* newRand = nullptr;
                Node* newNext = nullptr;
                if(old2New.find(oldCur) == old2New.end())
                {
                    newCur = new Node(oldCur->val);
                    old2New[oldCur] = newCur;
                }
                if(curRandom && old2New.find(curRandom) == old2New.end() )
                {
                    newRand = new Node(curRandom->val);
                    old2New[curRandom] = newRand;
                }
                if(curNext && old2New.find(curNext) == old2New.end())
                {
                    newNext = new Node(curNext->val);
                    old2New[curNext] = newNext;
                }
                newCur = old2New[oldCur];
                newRand = old2New[curRandom];
                newNext = old2New[curNext];
                newCur->next = newNext;
                newCur->random = newRand;
                if(!newHead)
                {
                    newHead = newCur;
                }
                oldCur = oldCur->next;
            }
            return newHead;
        }
    };


5. set/unordered_set


與map/unordered_map類似, 只是只有key, 沒有value

宣告

    unordered_set<int> intSet;
    unordered_set<char> charSet;
    unordered_set<string> strSet;
    

Member function

    intSet.insert(0);
    if(intSet.find(0) != intSet.end())
    {
        cout <<Key 0 found\n";
    }//Will output
    
    intSet.erase(0);
    if(intSet.find(0) == intSet.end())
    {
        cout <<Key 0 not exist\n";
    }//Will output
    


應用: Contain duplicated: 檢查一個array是否有重複數字

https://leetcode.com/problems/contains-duplicate/description/

    class Solution {
    public:
        bool containsDuplicate(vector<int>& nums) {
            unordered_set<int> existedNums;
            for(auto num : nums)
            {
                if(existedNums.find(num) != existedNums.end())
                {
                    return true;
                }
                existedNums.insert(num);
            }
            return false;
        }
    };


6. priority_queue

Heap, O(logn) insert, delete, O(1) check top element.

宣告

    priority_queue<int> MaxPQ; //Max heap
    
    參數: 
    1. 要存的data type (int)
    2. 底層的資料結構 vector<type>
    3. comparetor, default: less, 要把它變成min heap要用greater<int>
    priority_queue<int, vector<int>, greater<int> > MinPQ; //Min Heap
    
    如果要存類似 (value, index) 這樣的pair
    可以用pair<int, int>, 並且將value放在pair的第一個
    priority_queue<pair<int, int>> MaxPQ;
    priority_queue<pair<int, int>, vector<pair<int,int>, greater<pair<int,int>> > MinPQ;
    
    
Member function

    MaxPQ.push(1);
    MaxPQ.push(8);
    MaxPQ.push(5);
    while(!MaxPQ.empty())
    {
        int curMax = MaxPQ.top();
        cout << curMax << " ";
        MaxPQ.pop();
    } //8, 5, 1
    
    

應用: TOP-k相關問題

https://leetcode.com/problems/top-k-frequent-elements/
1. 用一個hash map存所有element出現次數
2. apporoach 1: 用出現次數sort -> nlogn
3. apporoach 2: maintain一個min heap, 只保留前K個最大的.

當目前heap size >= k, 比較下一個number跟目前heap的top(目前最小值),

決定是否把heap的top刪除並加下一個number -> nlogk


    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> number2Count;
            for(int num : nums)
            {
                number2Count[num] ++;
            }
            vector<int> uniqueNums;
            for(auto it : number2Count)
            {
                uniqueNums.push_back(it.first);
            }
            priority_queue<pair<int,int>, vector<pair<int,int>>,     greater<pair<int,int>> > PQ;
            int n = uniqueNums.size();
            for(int i = 0 ; i < n; i++)
            {
                int curNum = uniqueNums[i];
                int curFreq = number2Count[curNum];
                if(PQ.size() >= k)
                {
                    if(PQ.top().first < curFreq)
                    {
                        PQ.pop();
                        PQ.push({curFreq, curNum});
                    }
                }
                else
                {
                    PQ.push({curFreq, curNum});
                }   
            }
            vector<int> ret;
            while(!PQ.empty())
            {
                ret.push_back(PQ.top().second);
                PQ.pop();
            }
            return ret;
        }
    };



應用: Sliding window maximum
https://leetcode.com/problems/sliding-window-maximum/description/

給一個window size, window一直向右, 求每個時間點的最大值

* maintain一個max heap
* 先加入前k個number
* 在window滑行中, 檢查目前最大的是否已經不在window內 -> index <= i - k
* 加入下一個number
* 檢查目前heap最大值
* 

    
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            priority_queue<pair<int,int>> PQ;
            int n = nums.size();
            for(int i = 0 ; i < k ; i++)
            {
                PQ.push({nums[i] , i});
            }
            vector<int> ret;
            ret.push_back(PQ.top().first);
            for(int i = k ; i < n; i++)
            {
                while(!PQ.empty() && PQ.top().second <= (i - k))
                {
                    PQ.pop();
                }
                PQ.push({nums[i], i });
                ret.push_back(PQ.top().first);
            }
            return ret;
        }
    };


應用:最短路徑Dijkstra/ 最小生成樹Prim's algorithm
    
    

    
7. deque
    
Dobule-end queue, 可以從前後push/pop


    
Member function
        
    deque<int> dq;
    dq.push_back(0); //0
    dq.push_front(1); //1 0
    dq.push_back(2); // 1 0 2
    dq.push_front(3); // 3 1 0 2
    dq.pop_front(); // 1 0 2
    dq.pop_back(); // 1 0
    
應用: sliding window maximum, 題目敘述與priority_queue提到的相同, 但這次我們加入monotonic stack的做法.
https://leetcode.com/problems/sliding-window-maximum/description/
    
1 先加入前k個element, 當目前DQ後面有比要加入的element小的, pop back, 這樣DQ的擺放順序就會由大到小, front為目前window最大的
2 每次window滑動時, 檢查最前面的element是否已經不在window內
3 每次加入新element前, pop back掉所有比他小的
4 檢查DQ最前面的element, 就是目前window的最大值
    
    
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            int n = nums.size();
            deque<int> DQ;
            vector<int> ret;
            for(int i = 0 ; i < k ; i++)
            {
                while(!DQ.empty() && nums[DQ.back()] < nums[i] )
                {
                    DQ.pop_back();
                }
                DQ.push_back(i);
            }
            ret.push_back(nums[DQ.front()]);
            for(int i = k ; i < n; i++)
            {
                while(!DQ.empty() && DQ.front() <= i - k)
                {
                    DQ.pop_front();
                }
                while(!DQ.empty() && nums[DQ.back()] < nums[i] )
                {
                    DQ.pop_back();
                }
                DQ.push_back(i);
                ret.push_back(nums[DQ.front()]);
            }
            return ret;
        }
    };

                                                              
                                                              
8. string
                                                              
宣告
                                                              
    string emptyStr = "";
    string someValueStr = "abcdefg";                     

                                                              
Member function (usage)
    
    string curStr = "";
    for(char c = 'a' ; c <= 'd' ; c++)
    {
        curStr += c;
    } //abcd
    
    /*
    s.substr(pos, len)
    pos: starting index to get substring
    len: length of substring
    */
    
    string sub = curStr.substr(0, 2); //ab
    
    curStr.push_back('e'); //abcde
    curStr.pop_back(); //abcd
    
    int num1 = stoi("123456"); //stoi: string to integer
    string num1_str = to_string(num1); //number to string

    
應用: 字串處理相關問題
    

    

    
9. Iterator
    
Iterator是一種object, 可以先理解為一種比較特別的指標(運算類似)
    
在C++一些對於container內建的algorithm, return value常常是iterator.


    vector<int> vec;
    for(int i = 0 ; i < 5 ; i++)
    {
        vec.push_back(i);
    } //0 1 2 3 4
    
    //Traverse container using iterator
    for(auto it = vec.begin() ; it != vec.end() ; it ++)
    {
        cout << *it << " ";
    }// 0 1 2 3 4
    
    //Find specific element
    //If element not existed, vec.end() will be the return value
    auto it = find(vec.begin(), vec.end(), 2);
    if(it != vec.end())
    {
        cout << *it << endl; //2
    }
                           
    //Use iterator as member function argument           
    vec.erase(it); //0 1 3 4
                           
                           
    