全排列函數next_permutation
STL 中專門用于排列的函數（可以處理存在重複資料集的排列問題）
頭檔案：#include <algorithm>
using namespace std;
調用： next_permutation(start, end);
注意：函數要求輸入的是一個升序排列的序列的頭指針和尾指針.
用法：
// 數組
int a[N];
sort(a, a+N);
next_permutation(a, a+N);
// 向量
vector<int> ivec;
sort(ivec.begin(), ivec.end());
next_permutation(ivec.begin(), ivec.end());
例子：
vector<int> myVec;
// 初始化代碼
sort(myVec.begin(),myVec.end());
do{
for (i = 0 ;i < size;i ++ ) cout << myVec[i] << " \t " ;
cout << endl;
}while (next_permutation(myVec.begin(), myVec.end())); ACM/ICPC 競賽之STL--pair
STL 的<utility>頭檔案中描述了一個看上去非常簡單的模闆類pair，用來表示一個二進制組或元素對，并提供了按照字典序對元素對進行大小比較的比較運算符模闆函數。
例如，想要定義一個對象表示一個平面坐标點，則可以：
pair<double, double> p1;cin >> p1.first >> p1.second;pair 模闆類需要兩個參數：首元素的資料類型和尾元素的資料類型。pair 模闆類對象有兩個成員：first 和second，分别表示首元素和尾元素。
在<utility>中已經定義了pair 上的六個比較運算符：<、>、<=、>=、==、!=，其規則是先比較first，first 相等時再比較second，這符合大多數應用的邏輯。當然，也可以通過重載這幾個運算符來重新指定自己的比較邏輯。除了直接定義一個pair 對象外，如果需要即時生成一個pair 對象，也可以調用在<utility>中定義的一個模闆函數：make_pair。make_pair 需要兩個參數，分别為元素對的首元素和尾元素。
在題1067--Ugly Numbers 中，就可以用pair 來表示推演樹上的結點，用first 表示結點的值，用second 表示結點是由父結點乘以哪一個因子得到的。
#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long, int> node_type;
int main()
{
unsigned long result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 2) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top(); Q.pop();
switch(node.second)
{
case 2: Q.push( make_pair(node.first*2, 2) );
case 3: Q.push( make_pair(node.first*3, 3) );
case 5: Q.push( make_pair(node.first*5, 5) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0)
{
cout << result[n-1] << endl;
cin >> n;
}
return 0;
} ACM/ICPC 競賽之STL--vector
在STL 的<vector>頭檔案中定義了vector（向量容器模闆類），vector容器以連續數組的方式存儲元素序列，可以将vector 看作是以順序結構實作的線性表。當我們在程式中需要使用動态數組時，vector 将會是理想的選擇，vector 可以在使用過程中動态地增長存儲空間。
vector 模闆類需要兩個模闆參數，第一個參數是存儲元素的資料類型，第二個參數是存儲配置設定器的類型，其中第二個參數是可選的，如果不給出第二個參數，将使用預設的配置設定器。
下面給出幾個常用的定義vector 向量對象的方法示例：38
vector<int> s;
定義一個空的vector 對象，存儲的是int 類型的元素。
vector<int> s(n);定義一個含有n 個int 元素的vector 對象。
vector<int> s(first, last);定義一個vector 對象，并從由疊代器first 和last 定義的序列[first,last)中複制初值。
vector 的基本操作有：
s[i]直接以下标方式通路容器中的元素。
s.front() 傳回首元素。
s.back() 傳回尾元素。
s.push_back(x)向表尾插入元素x。
s.size() 傳回表長。
s.empty() 當表空時，傳回真，否則傳回假。
s.pop_back() 删除表尾元素。
s.begin() 傳回指向首元素的随機存取疊代器。
s.end() 傳回指向尾元素的下一個位置的随機存取疊代器。
s.insert(it, x) 向疊代器it 指向的元素前插入新元素val。
s.insert(it, n, x)向疊代器it 指向的元素前插入n 個x。
s.insert(it, first, last)将由疊代器first 和last 所指定的序列[first, last)插入到疊代器it
指向的元素前面。
s.erase(it)删除由疊代器it 所指向的元素。
s.erase(first, last)删除由疊代器first 和last 所指定的序列[first, last)。
s.reserve(n)預配置設定緩沖空間，使存儲空間至少可容納n 個元素。
s.resize(n)改變序列的長度，超出的元素将會被删除，如果序列需要擴充（原空間小于n），元素預設值将填滿擴充出的空間。
s.resize(n, val)改變序列的長度，超出的元素将會被删除，如果序列需要擴充（原空間小于n），将用val 填滿擴充出的空間。
s.clear()删除容器中的所有的元素。
s.swap(v)将s 與另一個vector 對象v 進行交換。
s.assign(first, last)将序列替換成由疊代器first 和last 所指定的序列[first, last)。[first, last)不能是原序列中的一部分。要注意的是，resize 操作和clear 操作都是對表的有效元素進行的操作，但并不一定會改變緩沖空間的大小。另外，vector 還有其他一些操作如反轉、取反等，不再一下列舉。vector 上還定義了序列之間的比較操作運算符(>, <, >=, <=, ==, !=)，
可以按照字典序比較兩個序列。還是來看一些示例代碼。輸入個數不定的一組整數，再将這組整數按倒序輸出，
如下所示：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L;
int x;
while (cin>>x) L.push_back(x);
for (int i=L.size()-1; i>=0; i--)
cout << L[i] << " ";
cout << endl;
return 0;
} ACM/ICPC 競賽之STL--iterator 簡介
iterator(疊代器)是用于通路容器中元素的訓示器，從這個意義上說，iterator(疊代器)相當于資料結構中所說的“周遊指針”，也可以把iterator(疊代器)看作是一種泛化的指針。STL 中關于iterator(疊代器)的實作是相當複雜的，這裡我們暫時不去詳細讨論關于iterator(疊代器)的實作和使用，而隻對iterator(疊代器)做一點簡單的介紹。
簡單地說，STL 中有以下幾類iterator(疊代器)：
輸入iterator(疊代器)，在容器的連續區間内向前移動，可以讀取容器内任意值；輸出iterator(疊代器)，把值寫進它所指向的容器中；前向iterator(疊代器)，讀取隊列中的值，并可以向前移動到下一位置(++p,p++)；雙向iterator(疊代器)，讀取隊列中的值，并可以向前向後周遊容器；随機通路iterator(疊代器), 可以直接以下标方式對容器進行通路，vector 的iterator(疊代器)就是這種iterator(疊代器)；流iterator(疊代器)，可以直接輸出、輸入流中的值；每種STL 容器都有自己的iterator(疊代器)子類，下面先來看一段簡單的示例代碼：
#include <iostream>
#include <vector>
using namespace std;
main()
{
vector<int> s;
for (int i=0; i<10; i++)
s.push_back(i);
for (vector<int>::iterator it=s.begin(); it!=s.end();it++)
cout << *it << " ";
cout << endl;
return 1;
} vector 的begin()和end()方法都會傳回一個vector::iterator 對象，分别指向vector 的首元素位置和尾元素的下一個位置（我們可以稱之為結束标志位置）。對一個iterator(疊代器)對象的使用與一個指針變量的使用極為相似，或者可以這樣說，指針就是一個非常标準的iterator(疊代器)。再來看一段稍微特别一點的代碼：
#include <iostream>
#include <vector>
using namespace std;
main()
{
vector<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
copy(s.begin(), s.end(), ostream_iterator<int>(cout, ""));
cout <<endl;
return 1;
} 這段代碼中的copy 就是STL 中定義的一個模闆函數，copy(s.begin(),s.end(), ostream_iterator<int>(cout, " "));的意思是将由s.begin()至s.end()(不含s.end())所指定的序列複制到标準輸出流cout 中，用" "作為每個元素的間隔。也就是說，這句話的作用其實就是将表中的所有内容依次輸出。iterator(疊代器)是STL 容器和算法之間的“膠合劑”，幾乎所有的STL 算法都是通過容器的iterator(疊代器)來通路容器内容的。隻有通過有效地運用iterator(疊代器)，才能夠有效地運用STL 強大的算法功能。
ACM/ICPC 競賽之STL--string
字元串是程式中經常要表達和處理的資料，我們通常是采用字元數組或字元指針來表示字元串。STL 為我們提供了另一種使用起來更為便捷的字元串的表達方式：string。string 類的定義在頭檔案<string>中。string 類其實可以看作是一個字元的vector，vector 上的各種操作都可以适用于string，另外，string 類對象還支援字元串的拼合、轉換等操作。下面先來看一個簡單的例子：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s = "Hello! ", name;
cin >> name;
s += name;
s += '!';
cout << s << endl;
return 0;
} 再以題1064--Parencoding 為例，看一段用string 作為容器，實作由P
代碼還原括号字元串的示例代碼片段：
int m;
cin >> m; // P 編碼的長度
string str; // 用來存放還原出來的括号字元串
int leftpa = 0; // 記錄已出現的左括号的總數
for (int j=0; j<m; j++){
int p;
cin >> p;
for (int k=0; k<p-leftpa; k++) str += '(';
str += ')';
leftpa = p;
}
ACM/ICPC 競賽之STL--stack/queue
stack(棧)和queue(隊列)也是在程式設計中經常會用到的資料容器，STL為我們提供了友善的stack(棧)的queue(隊列)的實作。39準确地說，STL 中的stack 和queue 不同于vector、list 等容器，而是對這些容器的重新包裝。這裡我們不去深入讨論STL 的stack 和queue 的實作細節，而是來了解一些他們的基本使用。
1、stack
stack 模闆類的定義在<stack>頭檔案中。
stack 模闆類需要兩個模闆參數，一個是元素類型，一個容器類型，但隻有元
素類型是必要的，在不指定容器類型時，預設的容器類型為deque。
定義stack 對象的示例代碼如下：
stack<int> s1;
stack<string> s2;
stack 的基本操作有：
入棧，如例：s.push(x);
出棧，如例：s.pop();注意，出棧操作隻是删除棧頂元素，并不傳回該元素。
通路棧頂，如例：s.top()
判斷棧空，如例：s.empty()，當棧空時，傳回true。
通路棧中的元素個數，如例：s.size()
下面是用string 和stack 寫的解題1064--Parencoding 的程式。
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i=0; i<n; i++)
{
int m;
cin >> m;
string str;
int leftpa = 0;
for (int j=0; j<m; j++) // 讀入P 編碼，構造括号字元串
{
int p;
cin >> p;
for (int k=0; k<p-leftpa; k++)
str += '(';
str += ')';
leftpa = p;
}
stack<int> s;
for (string::iterator it=str.begin();it!=str.end(); it++)
{ // 構造M 編碼
if (*it=='(') s.push(1);
else
{
int p = s.top(); s.pop();
cout << p << " ";
if (!s.empty()) s.top() += p;
}
}
cout << endl;
}
return 0;
} 2、queue
queue 模闆類的定義在<queue>頭檔案中。stack 模闆類很相似，queue 模闆類也需要兩個模闆參數，一個是元素類型，一個容器類型，元素類型是必要的，容器類型是可選的，預設為deque 類型。
定義queue 對象的示例代碼如下：
queue<int> q1;
queue<double> q2;
queue 的基本操作有：
入隊，如例：q.push(x); 将x 接到隊列的末端。
出隊，如例：q.pop(); 彈出隊列的第一個元素，注意，并不會傳回被彈出元素的值。
通路隊首元素，如例：q.front()，即最早被壓入隊列的元素。
通路隊尾元素，如例：q.back()，即最後被壓入隊列的元素。
判斷隊列空，如例：q.empty()，當隊列空時，傳回true。
通路隊列中的元素個數，如例：q.size()
3、priority_queue
在<queue>頭檔案中，還定義了另一個非常有用的模闆類priority_queue(優先隊列）。優先隊列與隊列的差别在于優先隊列不是按照入隊的順序出隊，而是按照隊列中元素的優先權順序出隊（預設為大者優先，也可以通過指定算子來指定自己的優先順序）。priority_queue 模闆類有三個模闆參數，第一個是元素類型，第二個容器類型，第三個是比較算子。其中後兩個都可以省略，預設容器為vector，預設算子為less，即小的往前排，大的往後排（出隊時序列尾的元素出隊）。
定義priority_queue 對象的示例代碼如下：
priority_queue<int> q1;
priority_queue< pair<int, int> > q2; // 注意在兩個尖括号之間一定要留白格。
priority_queue<int, vector<int>, greater<int> > q3; // 定義小的先出隊
priority_queue 的基本操作與queue 相同。
初學者在使用priority_queue 時，最困難的可能就是如何定義比較算子了。如果是基本資料類型，或已定義了比較運算符的類，可以直接用STL 的less算子和greater 算子——預設為使用less 算子，即小的往前排，大的先出隊。如果要定義自己的比較算子，方法有多種，這裡介紹其中的一種：重載比較運算符。優先隊列試圖将兩個元素x 和y 代入比較運算符(對less 算子，調用x<y，對greater 算子，調用x>y)，若結果為真，則x 排在y 前面，y 将先于x 出隊，反之，則将y 排在x 前面，x 将先出隊。
看下面這個簡單的示例：
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c){}
};
bool operator < (const T &t1, const T &t2)
{
return t1.z < t2.z; // 按照z 的順序來決定t1 和t2 的順序
}
int main()
{
priority_queue<T> q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
}
/*輸出結果為(注意是按照z 的順序從大到小出隊的)：
3 3 6
2 2 5
1 5 4
4 4 3*/
//再看一個按照z 的順序從小到大出隊的例子：
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator > (const T &t1, const T &t2)
{
return t1.z > t2.z;
}
int main()
{
priority_queue<T, vector<T>, greater<T> > q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
} 輸出結果為：
4 4 3
1 5 4
2 2 5
3 3 6
如果我們把第一個例子中的比較運算符重載為：
bool operator < (const T &t1, const T &t2){
return t1.z > t2.z; // 按照z 的順序來決定t1 和t2 的順序
}
則第一個例子的程式會得到和第二個例子的程式相同的輸出結果。
再回顧一下用優先隊列實作的題1067--Ugly Numbers 的代碼：
#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long int, int> node_type;
int main( int argc, char *argv[] )
{
unsigned long int result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 3) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top();
Q.pop();
switch(node.second)
{
case 3: Q.push( make_pair(node.first*2, 3) );
case 2: Q.push( make_pair(node.first*3, 2) );
case 1: Q.push( make_pair(node.first*5, 1) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0)
{
cout << result[n-1] << endl;
cin >> n;
}
return 1;
} ACM/ICPC 競賽之STL--map
在STL 的頭檔案<map>中定義了模闆類map 和multimap，用有序二叉樹來存貯類型為pair<const Key, T>的元素對序列。序列中的元素以const Key部分作為辨別，map 中所有元素的Key 值都必須是唯一的，multimap 則允許有重複的Key 值。可以将map 看作是由Key 辨別元素的元素集合，這類容器也被稱為“關聯容器”，可以通過一個Key 值來快速确定一個元素，是以非常适合于需要按照Key值查找元素的容器。map 模闆類需要四個模闆參數，第一個是鍵值類型，第二個是元素類型，第三個是比較算子，第四個是配置設定器類型。其中鍵值類型和元素類型是必要的。map 的基本操作有：
1、定義map 對象，例如：
map<string, int> m;
2、向map 中插入元素對，有多種方法，例如：
m[key] = value;
[key]操作是map 很有特色的操作，如果在map 中存在鍵值為key 的元素對，
則傳回該元素對的值域部分，否則将會建立一個鍵值為key 的元素對，值域為預設值。是以可以用該操作向map 中插入元素對或修改已經存在的元素對的值域部分。
m.insert( make_pair(key, value) );
也可以直接調用insert 方法插入元素對，insert 操作會傳回一個pair，當map 中沒有與key 相比對的鍵值時，其first 是指向插入元素對的疊代器，其second 為true；若map 中已經存在與key 相等的鍵值時，其first 是指向該元素對的疊代器，second 為false。
3、查找元素對，例如：
int i = m[key];
要注意的是，當與該鍵值相比對的元素對不存在時，會建立鍵值為key 的元素對。map<string, int>::iterator it = m.find(key);如果map 中存在與key 相比對的鍵值時，find 操作将傳回指向該元素對的疊代器，否則，傳回的疊代器等于map 的end()（參見vector 中提到的begin
和end 操作）。
4、删除元素對，例如：
m.erase(key);删除與指定key 鍵值相比對的元素對，并傳回被删除的元素的個數。
m.erase(it);删除由疊代器it 所指定的元素對，并傳回指向下一個元素對的疊代器。
#include<map>
#include<iostream>
using namespace std;
typedef map<int, string, less<int> > M_TYPE;
typedef M_TYPE::iterator M_IT;
typedef M_TYPE::const_iterator M_CIT;
int main()
{
M_TYPE MyTestMap;
MyTestMap[3] = "No.3";
MyTestMap[5] = "No.5";
MyTestMap[1] = "No.1";
MyTestMap[2] = "No.2";
MyTestMap[4] = "No.4";
M_IT it_stop = MyTestMap.find(2);
cout << "MyTestMap[2] = " << it_stop->second << endl;
it_stop->second = "No.2 After modification";
cout << "MyTestMap[2] = " << it_stop->second << endl;
cout << "Map contents : " << endl;
for(M_CIT it = MyTestMap.begin(); it != MyTestMap.end();it++)
{
cout << it->second << endl;
}
return 0;
}
/*程式執行的輸出結果為：
MyTestMap[2] = No.2
MyTestMap[2] = No.2 After modification
Map contents :
No.1
No.2 After modification
No.3
No.4
No.5*/ #include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> m;
m["one"] = 1;
m["two"] = 2;
// 幾種不同的insert 調用方法
m.insert(make_pair("three", 3));
m.insert(map<string, int>::value_type("four", 4));
m.insert(pair<string, int>("five", 5));
string key;
while (cin>>key)
{
map<string, int>::iterator it = m.find(key);
if (it==m.end())
{
cout << "No such key!" << endl;
}
else
{
cout << key << " is " << it->second << endl;
cout << "Erased " << m.erase(key) << endl;
}
}
return 0;
}