算法課上完了，估量著以後應該也不會怎麼使用C++了，整理一下C++的一些使用上的經驗技巧，該總結主要參考了一下文章/網站，首先對他們的工作成果表示感謝！ 1、 @mannhello的文章：c++容器簡介與比較 2、 原作者未知的文章：C++中幾個容器的比較 3、 神一般的C++庫函數資料網站：www.cplusplus.com，總結超級全面的，很值得一看 再次對他們的工作成果表示感謝！ 如果發現任何錯漏之處還請告知，感激不盡！ 轉載請注明出處，謝謝！ 1 概述 首先是一些有關C++的使用技巧： （1） 做算法題的時候切記換行與空格，避免低級錯誤； （2） 一旦某道題出現超時，如果你是用的是cin/cout，首先在main()函數第一行添加std::ios::sync_with_stdio(false);取消同步，如果還不能解決則把所有的cin/cout轉換成C風格的scanf/printf； （3） 做算法題的時候但凡排序都可以使用庫函數：#include<algorithm> sort(); 對於結構體的大小關系你可以為其編寫專門的cmp方法傳入即可； （4） 數組初始化可以這樣： #include <memory.h> int a[100]; memset(a, 0, sizeof(int)*100); //把數組a的每個字節都賦值為“0” memset(a, 1, sizeof(int)*100); //這樣是不行的，會把一個int的每個字節都賦值為“1”，最後數組裡存儲的是16843009(1 00000001 00000001 00000001)； （5） 對於浮點數比較，需要用一點技巧： a > b：a > b + (1e-6) a >=b：a > b – (1e-6) a < b：a < b – (1e-6) a <= b：a < b + (1e-6) a == b：a > b – (1e-6) && a < b + (1e-6) （6） 對精度要求比較高的時候，你可以這樣獲得 ：#include <math.h> pi=acos(-1, 0); （7） 如果需要自定義輸入輸出測試數據，可以重定向數據流到文件： freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); 之後使用的cin/cout都會從文件讀取了； （8） 對於大數的模，為了避免溢出可以用這個公式：(X*X % M) = (X%M * X%M) % M； （9） 字符串轉換數字： #include <stdlib.h> char c[5]; string s; int n = atoi(c); int n =atoi(s.c_str()); //atoi()會掃描參數nptr字符串，如果第一個字符不是數字也不是正負號返回零，否則開始做類型轉換，之後檢測到非數字或結束符 /0 時停止轉換，返回整型數。 long n = atol(c); long n =atol(s.c_str); //atol()會掃描參數nptr字符串，跳過前面的空格字符，直到遇上數字或正負符號才開始做轉換，而再遇到非數字或字符串結束時('/0')才結束轉換，並將結果返回。 double n = atof(c); double n = atof(s.c_str); //atof()會掃描參數nptr字符串，跳過前面的空格字符，直到遇上數字或正負符號才開始做轉換，而再遇到非數字或字符串結束時 ('/0')才結束轉換，並將結果返回。參數nptr字符串可包含正負號、小數點或E(e)來表示指數部分，如123.456或123e-2。 （10） 對於一個字符集合，你可以這樣獲得他的全排列： #include<algorithm> string str; do{ …..//取得當前str在全排列中的下一個字符串，直接使用str即可 }while(next_permutation(str.begin(), str.begin() + str.length())); （11） 對於兩個案例之間換行或空格的要求，可以這樣子： bool ok = false; while(case){ if(ok) cout << endl; ok = true; …… } （12） 當題目出現一些類似“N個點，N-1條邊，無環”“N個點，N-1條邊，任意兩點聯通”“N個點，任意兩點簡單連通”，說明題目中的N就是一棵樹； （13） 如果一道題的復雜度在10^8以內，用暴力枚舉也沒關系； （14） 對於搜索，如果已知最多步數，則可以使用DFS獲得所有路徑（遞歸）；如果要求最少步數，則可以使用BFS（隊列）； 2 容器 2.1 所有容器共有函數及屬性 2.1.1 容器中常用typedef 以下這些typedef常用於聲明變量、參數和函數返回值： （1） value_type 容器中存放元素的類型 （2） reference 容器中存放元素類型的引用 （3） const_reference 容器中存放元素類型的常量引用，這種引用只能讀取容器中的元素和進行const操作 （4） pointer 容器中存放元素類型的指針 （5） iterator 指向容器中存放元素類型的迭代器 （6） const_iterator 指向容器中存放元素類型的常量迭代器，只能讀取容器中的元素 （7） reverse_iterator 指向容器中存放元素類型的逆向迭代器，這種迭代器在容器中逆向迭代 （8） const_reverse_iterator 指向容器中存放元素類型的逆向迭代器，只能讀取容器中的元素 （9） difference_type 引用相同容器的兩個迭代器相減結果的類型（list和關聯容器沒有定義operator-） （10） size_type 用於計算容器中項目數和檢索順序容器的類型（不能對list檢索） 2.1.2 所有標准庫共有函數（除適配器外）： （1） 構造器及析構器 a) C<T> a; //默認構造函數，初始化為空 b) C<T> a(a0); //復制構造函數，初始化微現有同類容器副本 c) C<T> a(iter1,iter2); //復制構造函數，初始化為現有同類容器的一部分 d) ~C<T>(); //析構函數 （2） 迭代器 a) iterator begin() noexcept; const_iterator begin() const noexcept; //返回C<T>::iterator或者C<T>::const_iterator，引用容器第一個元素 b) iterator end() noexcept; const_iterator end() const noexcept; //返回C<T>::iterator或者C<T>::const_iterator，引用容器最後一個元素後面一位 c) reverse_iterator rbegin()nothrow; const_reverse_iterator rbegin() const nothrow; //返回C<T>::reverse_iterator或者C<T>::const_reverse_iterator，引用容器最後一個元素 d) reverse_iterator rend() nothrow; const_reverse_iterator rend() const nothrow; //返回C<T>:: reverse_iterator或者C<T>::const_reverse_iterator，引用容器第一個元素前面一位 e) const_iterator cbegin() constnoexcept; //僅用於C++11，返回C<T>::const_iterator，引用容器第一個元素 f) const_iterator cend() constnoexcept; //僅用於C++11，返回C<T>::const_iterator，引用容器最後一個元素後面一位 g) const_reverse_iteratorcrbegin() const noexcept; //僅用於C++11，返回C<T>:: const_reverse_iterator，引用容器最後一個元素 h) const_reverse_iterator crend()const noexcept; //僅用於C++11，返回C<T>:: const_reverse_iterator，引用容器第一個元素前面一位 （3） 功能函數 a) bool empty() const noexcept; //如果容器為空，則返回true，否則返回false b) size_type max_size() const; //返回容器中最大元素個數 c) size_type size() const; //返回容器當前元素個數 （4） 容器操作函數 a) iterator insert (const_iteratorposition, const value_type& val); //插入數據到指定位置，返回新插入的數據中的第一個的迭代器，除這個插入函數外還有其他很多重載函數 b) iterator erase (const_iterator position); iterator erase (const_iterator first, const_iterator last); //刪除容器中指定的某個值或者一個范圍，注意：范圍的概念是[first,last) c) void swap (C<T>& x); //將當前容器與傳入的容器x交換數據 d) void clear() noexcept; //刪除當前容器中的所有元素，也即將size清為0 2.2 順序容器 2.2.1 所有順序容器共有函數 以下是所有順序容器所共有的函數： （1） 元素訪問函數 a) reference front(); const_reference front() const; //返回容器中第一個元素的引用，注意：和begin()方法返回迭代器不同，他返回的是元素的直接引用 b) reference back(); const_reference back() const; //返回容器中最後一個元素的引用，注意：和end()方法返回迭代器不同，它返回的是元素的直接引用 （2） 容器操作函數 a) void push_back (constvalue_type& val); void push_back (value_type&& val); //插入元素到容器末尾 b) void pop_back(); //將容器最後一個元素刪除 2.2.2 vector （1） 使用比較 就是動態數組，它也是在堆中分配內存，元素連續存放，有保留內存，如果減少大小後內存也不會釋放。如果需要的容量大於當前大小時才會再分配內存，對最後元素操作最快(在後面添加刪除最快 )。訪問方面，對任何元素的訪問都是O(1)，也就是是常數的。所以vector常用來保存需要經常進行隨機訪問的內容，並且不需要經常對中間元素進行添加刪除操作。 vector的迭代器在內存重新分配時將失效（它所指向的元素在該操作的前後不再相同）。當把超過capacity()-size()個元素插入 vector中時，內存會重新分配，所有的迭代器都將失效；否則，指向當前元素以後的任何元素的迭代器都將失效。當刪除元素時，指向被刪除元素以後的任何 元素的迭代器都將失效。 （2） 功能函數 a) void resize (size_type n); void resize (size_type n, value_type val); //將容器的size變化成新的大小，如果n比當前size要小，則從容器後部開始刪除元素；否則擴充size，可以指定填充的元素的初始值 b) size_type capacity() constnoexcept; //返回分配給當前容器的存儲空間大小，並不一定和size相等 c) void reserve (size_type n); //為當前容器重新指定capacity的大小，如果n比當前capacity要大，則增加容量；否則什麼事情都不做 d) void shrink_to_fit(); //僅用於C++11，硬性將容器的capacity調整為size的大小 （3） 元素訪問函數 a) reference operator[] (size_typen); const_reference operator[] (size_type n) const; //相當於數組下標 b) reference at (size_type n); const_reference at (size_type n) const; //作用和數組下標一樣，但是超出容量時會拋出out_of_range異常 c) value_type* data() noexcept; const value_type* data() const noexcept; //僅用於C++11，返回容器第一個元素的指針，類似於數組的頭指針，用法也和數組頭指針一樣 2.2.3 deque （1） 使用比較 雙端隊列，也是在堆中保存內容的。它的保存形式如下： [堆1] [堆2] [堆3]…… 每個堆保存好幾個元素，然後堆和堆之間有指針指向，看起來像是list和vector的結合品。deque可以讓在前面或是在後面快速地添加刪除元素，然後還可以有比較高的隨機訪問速度，但是隨機訪問速度比不上vector快，因為它要內部處理堆跳轉。deque也有保留空間，由於deque不要求連續空間，所以可以保存的元素比vector更大，還有就是在前面和後面添加元素時都不需要移動其它塊的元素，所以性能也很高。 增加任何元素都將使deque的迭代器失效。在deque的中間刪除元素將使迭代器失效。在deque的頭或尾刪除元素時，只有指向該元素的迭代器失效。 （2） 功能函數 a) void resize (size_type n); void resize (size_type n, value_type val); //將容器的size變化成新的大小，如果n比當前size要小，則從容器後部開始刪除元素；否則擴充size，可以指定填充的元素的初始值 b) void shrink_to_fit(); //僅用於C++11，deque的size一般來說可以比實際存放的元素數量要多，該方法強制調整內存使用量為已經存放元素的大小 （3） 元素訪問函數 a) reference operator[] (size_typen); const_reference operator[] (size_type n) const; //相當於數組下標 b) reference at (size_type n); const_reference at (size_type n) const; //作用和數組下標一樣，但是超出容量時會拋出out_of_range異常 （4） 容器操作函數 a) void push_front (constvalue_type& val); void push_front (value_type&& val); //插入元素到容器第一位 b) void pop_front(); //刪除容器第一位的元素 2.2.4 list （1） 使用比較 雙向環狀鏈表，元素也是在堆中存放，每個元素都是放在一塊內存中，但list沒有空間預留，所以每分配一個元素都會從內存中分配，每刪除一個元素都會釋放它占用的內存。由於數據結構是鏈表，所以不能隨機訪問一個元素，但是在開頭、末尾和中間任何地方增加或刪除元素所需時間都為常量。 增加任何元素都不會使迭代器失效。刪除元素時，除了指向當前被刪除元素的迭代器外，其它迭代器都不會失效。 （2） 容器操作函數 a) void push_front (constvalue_type& val); void push_front (value_type&& val); //插入元素到容器第一位 b) void pop_front(); //刪除容器第一位的元素 c) void resize (size_type n); void resize (size_type n, value_type val); //將容器的size變化成新的大小，如果n比當前size要小，則從容器後部開始刪除元素；否則擴充size，可以指定填充的元素的初始值 2.3 關聯容器 2.3.1 所有關聯容器共有函數 （1） 訪問函數 a) const_iterator find (constvalue_type& val) const; iterator find (const value_type& val); //查找對應的值/key值，如果找到則返回其迭代器，如果找不到則返回end() b) size_type count (constvalue_type& val) const; //查找指定值/key值的數量，返回0或者1 c) iterator lower_bound (constvalue_type& val); const_iterator lower_bound (const value_type& val) const; 或者 iterator lower_bound (const key_type& k); const_iterator lower_bound (const key_type& k) const; //返回容器中第一個值/key值大於或等於val的迭代器 d) iterator upper_bound (constvalue_type& val); const_iterator upper_bound (const value_type& val) const; 或者 iterator upper_bound (const key_type& k); const_iterator upper_bound (const key_type& k) const; //返回容器中第一個值/key值大於val的迭代器 e) pair<const_iterator,const_iterator>equal_range (const value_type& val) const; pair<iterator,iterator> equal_range (const value_type&val); 或者 pair<const_iterator,const_iterator> equal_range (constkey_type& k) const; pair<iterator,iterator> equal_range (const key_type& k); //返回容器中與傳入值/key值相等的元素的范圍，返回的是一個pair值，它的first值就是lower_bound，second值就是upper_bound 2.3.2 set （1） 使用比較 內部數據結構為紅黑樹的平衡二叉檢索樹，按照鍵進行排序存儲， 值必須可以進行比較， 可以理解為set就是鍵和值相等的map，不允許鍵值重復，元素默認按升序排列。此外，它所有的操作都可以在O(log n)時間復雜度內完成，效率非常高。 如果迭代器所指向的元素被刪除，則該迭代器失效。其它任何增加、刪除元素的操作都不會使迭代器失效。 2.3.3 multiset （1） 使用比較 除了可以存儲重復鍵值以外，其他情況和set相同。 2.3.4 map （1） 使用比較 內部元素以<鍵，值>對的形式存儲，鍵值不能重復，元素默認按鍵的升序排列。可以這樣賦值一個對：m.insert(map<string, int>::value_type(“count”, 100));，或者使用更為簡單的數組下表符號“[]”。讀取的時候，對於一個迭代器iter，可以這樣指定：iter->first; iter->second，或者這樣：*iter.first;*iter.second;。 如果迭代器所指向的元素被刪除，則該迭代器失效。其它任何增加、刪除元素的操作都不會使迭代器失效。 （2） 訪問函數 a) mapped_type& operator[](const key_type& k); mapped_type& operator[] (key_type&& k); //就當他是數組這樣用，但要注意，一旦使用了“[]”，如果此時沒有對應的key值，將會產生一次插入操作 2.3.5 multimap （1） 使用比較 除了可以使用重復鍵值，其他情況和map一樣。 2.4 容器適配器 2.4.1 所有容器適配器共有函數 （1） 功能函數 a) boolempty ( ) const; //如果適配器為空，則返回true，否則返回false b) size_type size ( ) const; //返回適配器中已有的元素數量 2.4.2 stack （1） 使用比較 棧適配器，它可以將任意類型的序列容器轉換為一個堆棧，一般使用deque作為支持的序列容器。元素只能後進先出（LIFO），不能遍歷整個stack。 （2） 功能函數 a) value_type& top ( ); const value_type& top ( ) const; //獲取棧頂元素，並不彈出 b) void push ( const T& x ); //將元素壓入棧 c) void pop ( ); //將棧頂元素彈出，並不返回 2.4.3 queue （1） 使用比較 隊列適配器，它可以將任意類型的序列容器轉換為一個隊列，一般使用deque作為支持的序列容器。元素只能先進先出（FIFO），不能遍歷整個queue。 （2） 功能函數 a) value_type& front ( ); const value_type& front ( ) const; //獲取隊列首部元素，並不彈出 b) value_type& back ( ); const value_type& back ( ) const; //獲取隊列尾部元素，並不彈出 c) void push ( const T& x ); //添加新元素到隊列中 d) void pop ( ); //將隊首元素彈出，並不返回 2.4.4 priority_queue （1） 使用比較 優先隊列適配器，它可以將任意類型的序列容器轉換為一個優先級隊列，一般使用vector作為底層存儲方式。只能訪問第一個元素，不能遍歷整個priority_queue，第一個元素始終是優先級最高的一個元素。 其內部數據結構是堆，具體使用上來說，對於一個結構體，如果想要做一個堆，可以在結構體內部或者外部重載符號“<”即可： typedef struct Node{ …… bool operator<(const Node& in) const{ return data < in.data; //大根堆（如果應用於sort則是從小到大排序） return data > in.data; //小根堆（如果應用於sort則是從大到小排序） } }; bool operator<(const Node& a, const Node& b){ return a.data < b.data; //大根堆（如果應用於sort則是從小到大排序） return a.data >b.data; //小根堆（如果應用於sort則是從大到小排序） } 但是如果想要同時構建最大堆以及最小堆，就需要傳入定制的cmp結構： typedef struct Job{ int prio;int age}; struct cmpBigHeap{ //建立大根堆（優先值高的隊首） bool operator()(const Job& a, const Job& b){ return a.prio< b.prio;} }; struct cmpSmallHeap{ //建立小根堆（優先值低的在隊首） bool operator()(const Job& a, const Job& b){ return a.prio >b.prio;} }; priority_queue<Job, vector<Job>, cmpBigHeap> bigHeap; priority_queue<Job, vector<Job>, cmpSmallHeap > smallHeap; （2） 功能函數 a) const value_type& top ( )const; //獲取優先級隊列中優先級最高的元素 b) void push ( const T& x ); //將新元素放入優先隊列中 c) void pop ( ); //將優先級最高的元素彈出隊列 3 輸入輸出流
