本篇內(nèi)容介紹了“multimap和priority_queue怎么理解”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

在茅箭等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作定制網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),網(wǎng)絡(luò)營銷推廣,成都外貿(mào)網(wǎng)站制作,茅箭網(wǎng)站建設(shè)費(fèi)用合理。

題目簡述：有一個(gè)人每天往返于一段道路中，走著走著就覺得無聊了，于是自己給自己找樂子發(fā)明了一個(gè)扔石頭的游戲：在一次單程行走過程中，假設(shè)整段路程中有 n 塊石頭，每塊石頭有兩個(gè)重要信息，一個(gè)是所處的位置，一個(gè)是石頭可以扔出的距離。還有一點(diǎn)值得注意，石頭的塊頭越大扔的距離就越近。此人從第一塊石頭開始，遇到的第奇數(shù)個(gè)石頭就搬起來往前扔，遇到的第偶數(shù)個(gè)石頭不作處理。如果在某個(gè)位置上有兩個(gè)石頭，那么此人會(huì)先看到個(gè)頭較大的那塊石頭（即扔的距離較近的那塊石頭）?，F(xiàn)在要求算出此人走出多遠(yuǎn)就沒石頭可扔了。

輸入數(shù)據(jù)：第一行給出測試數(shù)據(jù)的組數(shù) t （ 1< = t <= 10 ),接下來給出 t 組測試數(shù)據(jù)，每組數(shù)據(jù)第一行 給出測試數(shù)據(jù)的組數(shù) n （ 0 < n <=10 000） ，接下來的 n 行，每行給出一對測試數(shù)據(jù) p 和 d ，（ p( 0 <= p <= 10 000) 表示石頭的位置，d ( 0 <= d <= 1 000) 表示石頭可扔出的距離 ）

輸出數(shù)據(jù)：給出每組測試數(shù)據(jù)的結(jié)果，每行一個(gè)數(shù)據(jù)。

測試數(shù)據(jù)如下：

現(xiàn)在對整個(gè)題目進(jìn)行分析，此人從第一塊石頭出發(fā)，隨著時(shí)間推移接下來遇到的石頭相對于起始位置越來越遠(yuǎn)，因此石頭的位置是一個(gè)遞增的信息，由此可以斷定，存儲(chǔ)石頭信息的結(jié)構(gòu)應(yīng)該具備順序結(jié)構(gòu)，但石頭的位置并不連續(xù)，如果用 vector 來存儲(chǔ)，勢必會(huì)造成空間的大量浪費(fèi)。此人遇到偶數(shù)個(gè)石頭丟棄，遇到奇數(shù)個(gè)石頭要朝著他行走的方向往前扔，也就意味著扔到前面的石頭他還會(huì)再遇到。這就需要在處理的時(shí)候，刪掉偶數(shù)塊的石頭，并將奇數(shù)塊石頭重新添加到序列其他的位置，這就要求存儲(chǔ)石頭信息的結(jié)構(gòu)需要有優(yōu)良的插入、刪除性質(zhì)，序列型容器 vector 在這一點(diǎn)上更顯的能力不足，這個(gè)時(shí)候，考慮其他的序列容器 隊(duì)列queue 、鏈表 list 。鏈表雖然在隨機(jī)插入刪除方面很有優(yōu)勢，但若要求有序，鏈表操作是相當(dāng)麻煩的。這個(gè)時(shí)候就剩 queue 還沒被拋棄，題目要求遇到一個(gè)石頭處理一個(gè)，即將此石頭出列進(jìn)行其余操作，這正是隊(duì)列具備的特征，處理石頭的時(shí)候需要將奇數(shù)的石頭根據(jù)位置信息插入到相應(yīng)位置。在有序的序列中，將元素插入到相應(yīng)位置，priority_queue 就是應(yīng)此要求誕生的。

選定了存儲(chǔ)結(jié)構(gòu)，現(xiàn)在來討論一下具體的實(shí)現(xiàn)：使用計(jì)數(shù)器對此人遇到過的石頭進(jìn)行計(jì)數(shù)，分成奇數(shù)和偶數(shù)情況來處理，偶數(shù)情況將該石頭信息出隊(duì)不作處理，奇數(shù)情況將石頭出隊(duì)，并把位置信息更改為當(dāng)前位置加可扔距離再次入隊(duì)。每次對當(dāng)前訪問的石頭位置進(jìn)行存儲(chǔ)，如此處理直至隊(duì)列為空，輸出最后一個(gè)處理石頭的位置信息即可。

優(yōu)先隊(duì)列需要對隊(duì)列的優(yōu)先標(biāo)準(zhǔn)進(jìn)行定義：當(dāng)位置不相同時(shí)，位置靠前的優(yōu)先性高，位置相同時(shí)，可扔距離較近的優(yōu)先性較高。

在這個(gè)問題中需要考慮可扔距離為零的特殊情況。

下面對優(yōu)先隊(duì)列使用中需要注意的問題進(jìn)行闡述

優(yōu)先隊(duì)列包含在 queue 頭文件中

優(yōu)先隊(duì)列的聲明有三種形式，

第一種：

priority_queue< element_type >  que；

此時(shí)聲明了一個(gè)存儲(chǔ) element_type 類型元素的優(yōu)先隊(duì)列 ，名稱為 que，這句聲明中包含了如下信息：

1. 該優(yōu)先隊(duì)列元素的類型為 element_type，

2. 該優(yōu)先隊(duì)列使用的容器為默認(rèn)容器 vector ，

3. 該優(yōu)先隊(duì)列使用的優(yōu)先級關(guān)系為優(yōu)先級由高到低，一般的數(shù)字大的數(shù)據(jù)優(yōu)先級高，此時(shí)隊(duì)首的元素為優(yōu)先級高的元素。確定優(yōu)先級的比較函數(shù)是less（）；請注意，優(yōu)先隊(duì)列中的內(nèi)置函數(shù)只能對基本數(shù)據(jù)類型進(jìn)行排序，如果要對特殊類型進(jìn)行排序，需要自定義比較函數(shù)。

第二種： 

priority_queue< element_type, name< element_type > > ;

此時(shí)聲明了一個(gè)存儲(chǔ) element_type 類型的元素的優(yōu)先隊(duì)列 ，名稱為 que，這句聲明中包含了以下信息：

1. 該優(yōu)先隊(duì)列元素的類型為 element_type ,

2. 該優(yōu)先隊(duì)列使用的容器為 name 容器，（ 此處的 name 為用戶需要使用的容器的名稱，并非真實(shí)存在的某容器，假設(shè) 此處需要使用 queue容器，那么聲明為

   priority_queue< element_type, queue< element_type > >

   ）

3. 該隊(duì)列使用的優(yōu)先級關(guān)系為默認(rèn)優(yōu)先級（由高到低），默認(rèn)比較函數(shù)為 less（）。

第三種：

priority_queue< element_type , vector< element_type > , less > ;

這種定義用于用戶使用非 less（）函數(shù)的其他優(yōu)先級。

需要注意此時(shí)無論容器是不是默認(rèn)容器 vector 都需要進(jìn)行傳參，這由優(yōu)先隊(duì)列相關(guān)函數(shù)內(nèi)部實(shí)現(xiàn)決定。

例如：

現(xiàn)在元素類型為結(jié)構(gòu)體類型，比較函數(shù)需要改變，則 處理如下：

struct node

{

     element_type x;

     element_type y;

};

bool compare( node a, node b )

{

      return a . x   >  a . y   ;(此處的優(yōu)先級關(guān)系可任意更改)

}

priority_queue , compare > ;

另例如下：

struct node

{

     friend  bool operator < ( node a , node b )

     {

           return a . y  >  b . y ; (同樣，此處的優(yōu)先級順序也是可以根據(jù)需要任意更改的)

     }

     element_type x;

     element_type y;

};

 priority_queue< node>

或者下面這種：

priority_queue< node , vector , less > ; // 此時(shí)優(yōu)先級實(shí)際上已經(jīng)更改。

補(bǔ)充說明：

1. 在優(yōu)先隊(duì)列中，內(nèi)置優(yōu)先性比較函數(shù)有兩個(gè)：

   less（），由隊(duì)首開始優(yōu)先性逐漸減小

   greater（），由隊(duì)首開始優(yōu)先性逐漸增大

   但不聲明的情況下，默認(rèn)使用 less（），需要使用 greater （）的時(shí)候，要使用上面介紹的第三種聲明方式。

2. 優(yōu)先隊(duì)列其余函數(shù)大多與普通隊(duì)列 queue 的使用方法類似。

以上是使用優(yōu)先隊(duì)列的方法，下面我將用 multimap 方法對此題進(jìn)行講解，在此題中，multimap  方法似乎有些麻煩，但是也不失為一種解題思路，重在介紹 multimap 的相關(guān)函數(shù)使用方法。

在序列式容器中有自動(dòng)排序功能的是 priority_queue ，而關(guān)聯(lián)式容器也有這個(gè)特點(diǎn)，而且紅黑樹實(shí)現(xiàn)效率非常高。

關(guān)聯(lián)式容器有 set ／ multiset  和 map ／ multimap 這兩對：

set 的結(jié)構(gòu)相當(dāng)于集合，除了滿足集合的唯一性、確定性，還滿足有序性（默認(rèn)由小到大排列）。multiset 與 set 的相關(guān)用法大多相同，唯一的區(qū)別在于，multiset 允許集合中有相同元素的出現(xiàn)，由此會(huì)引起部分函數(shù)的差異。

map／multimap 的結(jié)構(gòu)相當(dāng)于 映射對的集合，同樣，兩者大同小異，區(qū)別在于multimap中允許有相同鍵值的元素出現(xiàn)。

由于在某一確定時(shí)刻每個(gè)石頭的位置和可扔距離是確定的，且一一對應(yīng)。因此我想到可以用 map 容器，又因?yàn)槿邮^過程中，同一位置有可能出現(xiàn)多于一塊石頭，因此可以確定使用 multimap 容器。

思路和上面的思路大同小異，先將初始數(shù)據(jù)存入 map ，然后設(shè)置計(jì)數(shù)變量和存儲(chǔ)當(dāng)前位置的變量，map 不空就不斷進(jìn)行計(jì)數(shù)變量的奇偶判斷和map 刪除、插入元素的處理。同樣應(yīng)該考慮可扔距離為零的情況。

在這個(gè)過程中有一些需要注意的地方：

一、頭文件

multimap 包含在 map 頭文件中，使用時(shí)要在程序打開頭文件編寫時(shí)加入#include

二、聲明

分為兩種：

第一種：

multimap mp；

包含以下信息

1. 聲明了一個(gè) 鍵值為 key_type 類型 、關(guān)聯(lián)值為 value_type 類型的 multimap  型變量 mp；

2. multimap內(nèi) 的鍵值排序按照默認(rèn)排序順序由小到大；

第二種：

multimap >;

包含以下信息

1. 聲明了一個(gè)鍵值為 key_type 類型 ，關(guān)聯(lián)值為 value_type 類型的 multimap  型變量 mp；

2. multimap 內(nèi)鍵值的排序規(guī)則由比較函數(shù) compare給出，請注意這里 compare（）函數(shù)中的參數(shù)只有 鍵值的類型，而沒有關(guān)聯(lián)值的類型，原因是，multimap 內(nèi)部的排序只根據(jù)鍵值大小進(jìn)行排序，而對關(guān)聯(lián)值的順序沒有相應(yīng)的處理，由此可見， multimap 中同一鍵值元素的相對位置并不是由關(guān)聯(lián)值的大小決定，而是由添加順序決定。

三、普通map可以用 map［key］來對鍵值為 key 的元素的關(guān)聯(lián)值進(jìn)行操作，但 multimap 不包含此性質(zhì)，因此向multimap中添加元素只能使用 insert（）函數(shù)，同樣也不能用mp[ key ]來訪問某一元素。用法如下：

1. mp . insert( pair< key_type ,value_type>( key ,value ) )

2. mp . insert( make_pair ( key , value ) ) ;

其中，pair是一種模版類型，含有兩個(gè)成員分別為 first 和 second。 兩個(gè)成員的類型可以根據(jù)需要任意確定，可以是基本數(shù)據(jù)類型，也可以是用戶自定義類型。pair 可以作為新的類型 進(jìn)行函數(shù)傳參和使用。聲明如下：

pair< element_type , element_type >  p = ( element_1 , element_2);

pair< element_type , element_type >  p = make_pair ( element_1 , element_2 )

需要使用pair 的兩個(gè)成員時(shí)如下：

p . first

p . second

巧用 pair，當(dāng)某函數(shù)需要返回兩個(gè)類型不同的值時(shí)，可以定義 pair 來返回。

四、如何確定鍵值相同而關(guān)聯(lián)值不同的元素的個(gè)數(shù)，以及如何對它們進(jìn)行訪問：

1. 確定個(gè)數(shù)使用函數(shù)

   mp . count ( key ) ;

2. 逐個(gè)進(jìn)行訪問

   mp . equal_range ( key ) ;

   注意，此函數(shù)的返回值是兩個(gè)迭代器，其中，第一個(gè)迭代器返回的是 該鍵值第一個(gè)元素的迭代器，第二個(gè)迭代器返回的的是 該鍵值最后一個(gè)元素訪問結(jié)束即將跳轉(zhuǎn)的下一個(gè)元素的迭代器 。因此需要使用模版 pair ，如下：

   typedef   multimap< key_type , value_type >:: iterator  iter;

   pair< iter , iter > p ;

   p = mp . equal_range ( key ) ;

   while( p . first  !=  p . second )

   {

         cout << p . first << endl ;

         p . first ++ ;

3. }

       在此應(yīng)該注意思考一個(gè)問題：當(dāng)multimap中只有一個(gè)元素的時(shí)候， p . second 此時(shí)的值應(yīng)該與當(dāng)前 mp . end ( ) 返回值相同，這時(shí)候，如果循環(huán)寫成這樣：

while( p . first  !=  p . second )

{

      cout << p . first << endl ;

      mp . insert ( make_pair( elem_1 , elem_ 2 )  ) ;

      p . first ++ ;

}

在插入新的元素后，   mp . end ( ) 值變了，但 p . second 值還是原來的末尾，既不是現(xiàn)在的尾，也不是新加入的元素的位置，p .first 會(huì)一直自增尋找結(jié)束條件，但 p . second 目前已經(jīng)失效了，會(huì)陷入死循環(huán)，并且這種錯(cuò)誤一般不容易被發(fā)現(xiàn) 。因此在編寫程序的過程中，應(yīng)該盡量避免這種情況的發(fā)生。改進(jìn)方法需要根據(jù)具體的要求來實(shí)現(xiàn)，在這里就不舉例了。

五、特殊查找

mp . lower_bound( key ) 查找第一個(gè)鍵值不小于 key 的元素，返回其迭代器

mp . upper_bound( key ) 查找第一個(gè)鍵值比 key 大的元素，返回其迭代器

由上面注意事項(xiàng)中所提到的，同一鍵值的不同元素在multimap中的順序并不是按照 value 值的大小決定，而是由輸入順序決定，因此，在本題中，需要將相同鍵值的元素摘出來存在vector中，對其進(jìn)行排序再使用。本題中，multimap 比 priority_queue 復(fù)雜的地方就在此了。

“multimap和priority_queue怎么理解”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！