---

前言

前幾天回老家沒事兒在新華書店乘涼，無意翻到《c++信息學奧林匹克競賽入門與提高》，拍了幾張照片，順便學點c++的知識。
現整理如下：
關于STL的知識可以先看看百度百科：STL(模板庫)_百度百科

---

【1】stack操作以及應用

stack的幾個核心接口

向棧中壓入一個元素（push）、
取棧頂元素的值（top）、
彈出棧頂元素（pop）、
清空棧（empty）、
判斷棧是否為空（isEmpty）

利用stack完成進制轉換

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
using namespace std;//stack應用
//輸入：十進制數n,轉換成r進制數輸出（2<=r<=16）
const string t = "0123456789ABCDEF";
int main()
{stack<int>s;int n, r, x;cin >> n >> r;while (n != 0){x = n % r;//求余數s.push(x);//將余數壓入棧頂n = n / r;//縮小r倍}while (!s.empty()){cout << t[s.top()];	//轉換成r進制數位s.pop();	//彈出棧頂元素，即移除元素}
}

結果：

【2】priority_queue操作以及應用

priority_queue的幾個核心接口

push()——根據元素的優先級將元素置入優先隊列（默認降序排列，大值優先）
top()——返回優先隊列頭部最大的元素的引用(不移除
pop()——從優先隊列中移除最大元素
empty()——優先隊列是否為空

priority_queue 的模板聲明帶有三個參數:
priority_queue<Type, Container, Functional>
其中Type 為數據類型， Container 為保存數據的容器，Functional 為元素比較方式。
Container 必須是用數組實現的容器，比如 vector, deque 但不能用 list.
STL里面默認用的是 vector. 比較方式默認用 operator< , 所以如果你把后面倆個參數缺省的話，
優先隊列就是大頂堆，隊頭元素最大。

利用priority_queue完成合并果子問題

問題描述以及分析：
在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把
所有的果子合成一堆。每一次合并,多多可以把兩堆果子合并到一起,消耗的體力等于兩堆果子的重力之和。
算法分析:
如有3種果子,數目依次為1,9，2。可以先將1,2堆合并,新堆數目為3,耗費體力為3。接著﹐將新堆
與數量為9的堆合并，又得到新的堆，數目為12,耗費體力為12。
所以多多總共耗費體力=3＋12=15。可以證明15為最小的體力耗費值。
類似于堆操作（完全二叉樹），優先級高的優先處理
代碼實現：

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
using namespace std;
//最小值優先（升序處理）使用動態數組vector遞增參數排序，相當于最小值優先
priority_queue<int, vector<int>, greater<int> > q;
//從小到大的優先級隊列，可將greater改為less，即為從大到小,
int main()
{int i, n, ans = 0, t1 = 0, t2 = 0, t3 = 0, x;cin >> n;for (i=0;i<n;i++){cin >> x;	q.push(x);	//進隊，把一個元素壓入隊尾}//所有元素壓入隊列中之后自動排序for (i = n;i > 1;i--)	//合并次數共計n-1次{t1 = q.top();		//取最小的元素q.pop();			//此元素出隊列t2 = q.top();		//取第二小的元素q.pop();			//此元素出隊列t3 = t1 + t2;		//合并果子數（合并較小的2個）ans +=t3;			//求果子數目之和q.push(t3);			//入隊列//每一次循環，都會自動排序}cout << ans << endl;return 0;
}

結果：

【3】vector操作以及應用

vector的幾個核心接口

常用操作	效果
vectorc	產生一個空的vetcor
c.size()	返回元素個數
front()	返回第一個元素的引用，不檢查元素是否存在
back()	返回最后一個元素的引用，不檢查元素是否存在
begin()	返回一個迭代器，指向第一個元素
end()	返回一個迭代器，指向最后一個元素之后
c.insert(pos,e)	在pos位置插入元素e的副本，并返回新元素的位置
c.push_back(e)	在尾部添加一個元素e的副本
c.pop_back(e)	移除最后一個元素但不返回最后一個元素
c.erase(pos)	刪除pos位置的元素，返回下一個元素的位置
c.clear()	移除所有元素，清空容器

利用vector完成隨機排序

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
#include <time.h>
using namespace std;
void Swap(int& a, int& b)
{int c = a;a = b;b = c;
}
void random_arrange(int a[], int len)
{int i;srand(time(NULL));for (i = 0; i < len; i++){Swap(a[i], a[rand() % (i + 1)]);}
}void print(int a[], int len)
{for (int i = 0; i < len; i++)cout << a[i] << "  ";cout << endl;
}int main(void)
{int a[] = { 1,2,3,4,5,6,7,8,9 };int len = sizeof(a) / sizeof(int);int i = 0;cout << "before arrange" << endl;print(a, len);//random_arrange(a, len);vector<int> se;			//這里的vector要是換成set會報錯while (se.size() < len)se.push_back(a[i++]);random_shuffle(se.begin(), se.end());cout << "after arrange" << endl;for (i = 0; i < len; i++)cout << se[i] << "  ";cout << endl;return 0;
}

效果：

【4】deuqe(雙向隊列)操作以及應用

deque(雙向隊列)和vector非常相似，操作接口功能模塊基本一致。它采用動態數組來管理元素，提供隨機存取，可以在頭尾兩段快速插入和刪除元素。

deuqe的特點以及核心接口

deque支持隨機存取，可以使用迭代器或[ ]符號
deque支持在頭部和尾部存儲數據

操作	效果
c,push_back(e)	在尾部添加一個元素e的副本
c.push_front(e)	在頭部添加一個元素e的副本
c.pop_back()	移除最后一個元素但不返回最后一個元素
c.pop_front()	移除第一個元素但不返回第一個元素

利用deuqe處理數據

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
#include <time.h>using namespace std;int main()
{//deque(int nSize,const T& t):創建一個deque,元素個數為nSize,且值均為tdeque< int>d(10, 1);deque< int>::iterator it;int x, y;cin >> x >> y;d.push_front(y);d.push_back(x);cout << "d[0]=" << d[0] << endl;cout << "d[11]=" << d[11] << endl;cout << "d.front()=" << d.front() << endl;cout << "d.back()=" << d.back() << endl;for (it = d.begin();it != d.end();it++){cout << *it << " ";}cout << endl;return 0;
}

【5】list(雙向鏈表)操作以及應用

list的特點

雙向鏈表將元素按順序存儲在鏈表中。與動態數組vector相比，它允許快速地插入與刪除，但是隨機訪問卻比較慢。
特點：

使用雙向鏈表管理元素，數據元素可以使任意類型T
list只能通過迭代器遍歷數據（不支持隨機存取，不能使用[ ]）
在任何位置上執行元素的插入和移除都非常快

雙向鏈表實現數據的輸入與求和

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <string> 
#include <cstring> 
#include <list> 
#include<numeric>using namespace std;
list<int>list1;
int main()
{list<int>::iterator iter;//從雙向鏈表list1前面向容器中添加數據list1.push_front(5);list1.push_front(8);//從雙向鏈表list1后面向容器中添加數據list1.push_back(7);list1.push_back(9);//從前向后顯示list1中的數據cout << "list1 data" << endl;for (iter = list1.begin();iter != list1.end();iter++){cout << *iter << " ";}cout << endl;//求和int result = accumulate(list1.begin(),list1.end(),0);cout << "Sum" << result << endl;return 0;
}

【6】map/multimap操作以及應用

map是STL關聯式容器，它提供映射關系（第一個關鍵字，第二個關鍵值）的數據處理能力，通常用它來快速處理映射相關的數據集，map數據結構內部是一棵紅黑樹（平衡二叉樹），它具有對數據自動排序的功能，我們可以快速高效處理容器中的數據，時間復雜度為logN。對于訪問的迭代器來說，僅能修改關鍵值，不能修改key。

map/multimap的幾個特點以及功能接口

元素包含兩部分(key,value),key和value可以是任意類型
根據元素的key自動對元素排序，因此根據元素的key可以進行很快定位
不能直接改變元素的key,可以通過[ ]直接存取元素值
map中不允許key相同的元素，multimap允許key相同的元素

操作	效果
map.c	產生空的map
c.size()	返回元素個數
count(key)	返回鍵值==key的元素個數
find(key)	返回鍵值==key 的第一個元素，找不到的話返回end
lower_bound(key)	返回鍵值>=key的第一個元素
upper_bound(key)	返回鍵值>key的第一個元素
equal_range(key)	返回鍵值==key的元素區間
c.insert(pos,e)	在pos位置為起點插入e的副本，并返回新元素的位置
c.erase(val)	移除所有值為val的元素，返回移除元素個數

map/multimap應用：優惠購物

問題描述：
某購物網站平臺進行優惠活動，每件商品當天第一個訂單可以打75折。這天網站先后依次接受到了(N<100 000)個訂單，訂單的數據形式是:商品名價格(單價*數量)，商品名是長度不超過20請按商品名字典序輸出當天的每種商品名和其售出的總價。

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
#include <iomanip> //要用到格式控制符
using namespace std;
//聲明映射變量m，由m[string]映射double類型的數值
map<string, double>m;
int main()
{string name;double val;int n;cin >> n;for (int i = 1;i <= n;i++){cin >> name >> val;//輸入訂單-商品名和價格if (m.count(name) == 0)	//如果是第一次出現m[name] = val * 0.75;		//打折，m[name]映射了商品價格的數值elsem[name] = val;	//不打折}//構建了map類型迭代器指針map<string, double>::iterator it;cout << "映射結果（統計）" << endl;for (it = m.begin();it != m.end();it++){//輸出商品名和價格							2位浮點數cout << it->first << " " << fixed << setprecision(2) << it->second << endl;}return 0;
}

【7】set/multiset(集合/多重集合)操作以及應用

set(集合)是將容器內所有元素都能更具其鍵值自動排序，set元素的鍵值就是實值。set不允許兩個元素有相同的鍵值，multiset可以有相同的鍵值。

set/multiset的幾個特點

set使用平衡二叉樹管理元素（紅黑樹）
set的每個元素值必須唯一，系統會自動將數據排序。他支持插入、刪除、查找等操作，所有的操作都在logN時間之內完成，效率比較高。
set和multiset的區別是：set插入的元素不能相同，而multiset可以相同
操作指令同map

利用set完成隨機數的產生以及排序

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
using namespace std;
//生成n個指定范圍a~b中的不重復隨機數（a<=b<=10000）
int main()
{set<int>s;int n, a, b,x;cin >> n >> a >>b;while (s.size() < n){x = rand() % (b - a + 2) + a;	//產生的隨機數s.insert(x);	//在集合中插入元素（自動去重處理）	}cout << "輸出（默認升序+去重）：" << endl;set<int>::iterator it1;	//正向迭代器for (it1 = s.begin();it1 != s.end();it1++)cout << *it1 << " ";cout << endl;return 0;
}

---

總結

無