C++语言中multiset的相关用法及扩展
***************************************************
更多精彩,歡迎進入:http://shop115376623.taobao.com
***************************************************
cpp語言中,multiset是<set>庫中一個非常有用的類型,它可以看成一個序列,插入一個數,刪除一個數都能夠在O(logn)的時間內完成,而且他能時刻保證序列中的數是有序的,而且序列中可以存在重復的數。
???? 我們通過一個程序來看如何使用multiset。
#include <string>
#include <iostream>
#include <set>
using?namespace?std;
void?main()
{
??? ?int?x;
???? scanf("%ld",&x);
???? multiset<int>?h;//建立一個multiset類型,變量名是h,h序列里面存的是int類型,初始h為空
???? while(x!=0)
? ? {
???? h.insert(x);//將x插入h中
? ? scanf("%ld",&x);
? ?}????
??? while(!h.empty())
? {
//?序列非空 h.empty()==true時 表示h已經空了
???????? __typeof(h.begin())?c=h.begin();//c指向h序列中第一個元素的地址,第一個元素是最小的元素
???????? printf("%ld ",*c);//將地址c存的數據輸出
???????? h.erase(c);//從h序列中將c指向的元素刪除
???? }
}
對于輸入數據32 61 12 2 12 0,該程序的輸出是2 12 12 32 61。
我們可以看到,當一個變量h被定義為multiset類型時。所有關于它的操作可以寫成如下格式:
h.函數名(形參);
當要在h中插入一個數x時,語法為h.insert(x);當在h中刪除指針c指向的元素*c時,語法為h.erase(c)。
注意,如果我們把h.erase(c)寫成h.erase(*c),那么該語句就會把h中所有和*c相等的元素都刪掉,大家要注意
如果要查找最大的元素并賦值給k,語法是int k=*(h.end()--),注意multiset類型的尾地址存的內容是空的。
如果要想知道當前序列中比k大的元素最小的是多少,那么可以這樣 int p=*(h.upper_bound(k)),其中h.upper_bound(k)表示比k大的最小的數的地址。
不光是int類型,multiset還可以存儲其他的類型諸如 string類型,結構(struct或class)類型。而我們一般在編程當中遇到的問題經常用到多關鍵字的類型,即struct或class。例如下面的例子:
struct?rec
{
????int?x,y;
};
multiset<rec>h;
以上的代碼是沒有任何用處的,因為multiset并不知道如何去比較一個自定義的多關鍵字類型。怎么辦呢?我們可以定義multiset里面rec類型變量之間的小于關系的含義(這里以x為第一關鍵字為例),具體過程如下:
我們定義一個比較類cmp,cmp內部的operator函數的作用是比較rec類型a和b的大小(以x為第一關鍵字,y為第二關鍵字):
struct?cmp
{
????bool?operator()(const?rec&a,const?rec&b)
? ? {
????????return?a.x<b.x||a.x==b.x&&a.y<b.y;
????}
};
?然后我們將語句"multiset<rec>h;” 改成"multiset<rec,cmp>h;"這樣以后,我們就告訴了序列h如何去比較里面的元素(這種方法屬于重載運算符,在編程當中經常用到,這里就不詳細介紹了)
此時rec以及multiset的定義部分完整代碼可參考如下:
struct?rec{
????int?x,y;
};
struct?cmp{
????bool?operator()(const?rec&a,const?rec&b){
????????return?a.x<b.x||a.x==b.x&&a.y<b.y;
????}
};
multiset<rec,cmp>h;
通過以上代碼,我們就能建立一個集合h使得該集合能夠存儲和排序多關鍵字類型
我們來看一個小應用:求從一個點到另一個點的最短路長度,邊都是正權。
正權邊的最短路問題可以用dijkstra算法來解決,而優化dijkstra算法可以用heap。這里我們來看如何用multiset實現dijkstra+heap。
以下代碼省去了輸入輸出和圖的建立。我們光看求最短路的部分。注意,這里的多關鍵字類型名稱還是rec,multiset集合的名稱還是h;多關鍵字類型rec中,x是第一關鍵字,y是第二關鍵字,y代表圖中點的編號,而x則代表當前點y與源點的最短距離。
d[0]=0;//源點是0
reca;
a.x=0;//第一關鍵字x表示距離
a.y=0;//第二關鍵字y表示點的編號
h.insert(a);//將a插入序列中
while(!h.empty()){//h集合中的元素是否為空
??????__typeof(h.begin())?c=h.begin();
????rect=(*c);//取最小值
????h.erase(c);//將最小值刪去
????for(inti=tail[t.y];i;i=next[i]){
????????intj=p[i];//枚舉和t.y相鄰的點
????????reca;//建立一個結構類變量a
????????if(d[j]==-1){//d[j]==-1表示j還沒有被訪問
????????????d[j]=t.x+w[i];//w[i]表示邊i的邊權
????????????a.x=d[j];
????????????a.y=j;//將j的相關信息保存在rec類型a中
????????????h.insert(a);
????????}elseif(d[j]>t.x+w[i]){//最短路算法的松弛操作
????????????a.x=d[j];
????????????a.y=j;//將j在序列中的信息存儲到a中
????????????c=h.upper_bound(a);//找到序列h中a之后的元素的地址
????????????c--;//地址減一就是a所在的地址
????????????h.erase(c);//刪掉a
????????????a.x=t.x+w[i];
????????????d[j]=a.x;//更新最短路的值
????????????h.insert(a);//插入
????????}
????}
}
有了multiset類型,我們就不用再去寫平衡樹一類的東西了,從而大大降低了編程復雜度
總結
以上是生活随笔為你收集整理的C++语言中multiset的相关用法及扩展的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 基于Chrome内核(WebKit内核)
- 下一篇: 三大运营商布局金融的套路不同,还能否搭上