***************************************************

更多精彩，歡迎進入：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的相关用法及扩展的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。