STL容器及其简单应用(stack、priority_queue、vector、deuqe、list、map/multimap、set/multiset)
目錄
- 前言
- 【1】stack操作以及應用
- stack的幾個核心接口
- 利用stack完成進制轉換
- 【2】priority_queue操作以及應用
- priority_queue的幾個核心接口
- 利用priority_queue完成合并果子問題
- 【3】vector操作以及應用
- vector的幾個核心接口
- 利用vector完成隨機排序
- 【4】deuqe(雙向隊列)操作以及應用
- deuqe的特點以及核心接口
- 利用deuqe處理數據
- 【5】list(雙向鏈表)操作以及應用
- list的特點
- 雙向鏈表實現數據的輸入與求和
- 【6】map/multimap操作以及應用
- map/multimap的幾個特點以及功能接口
- map/multimap應用：優惠購物
- 【7】set/multiset(集合/多重集合)操作以及應用
- set/multiset的幾個特點
- 利用set完成隨機數的產生以及排序
- 總結
前言
前幾天回老家沒事兒在新華書店乘涼，無意翻到《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為最小的體力耗費值。
類似于堆操作（完全二叉樹），優先級高的優先處理
代碼實現：
結果：
【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請按商品名字典序輸出當天的每種商品名和其售出的總價。
【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; }總結
無
總結
以上是生活随笔為你收集整理的STL容器及其简单应用(stack、priority_queue、vector、deuqe、list、map/multimap、set/multiset)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 面包蟹多少钱一斤啊？
- 下一篇： 微信最多转账多少钱啊？