溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“multimap和priority_queue怎么理解”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
題目簡述：有一個人每天往返于一段道路中，走著走著就覺得無聊了，于是自己給自己找樂子發明了一個扔石頭的游戲：在一次單程行走過程中，假設整段路程中有 n 塊石頭，每塊石頭有兩個重要信息，一個是所處的位置，一個是石頭可以扔出的距離。還有一點值得注意，石頭的塊頭越大扔的距離就越近。此人從第一塊石頭開始，遇到的第奇數個石頭就搬起來往前扔，遇到的第偶數個石頭不作處理。如果在某個位置上有兩個石頭，那么此人會先看到個頭較大的那塊石頭（即扔的距離較近的那塊石頭）。現在要求算出此人走出多遠就沒石頭可扔了。
輸入數據：第一行給出測試數據的組數 t （ 1< = t <= 10 ),接下來給出 t 組測試數據，每組數據第一行 給出測試數據的組數 n （ 0 < n <=10 000） ，接下來的 n 行，每行給出一對測試數據 p 和 d ，（ p( 0 <= p <= 10 000) 表示石頭的位置，d ( 0 <= d <= 1 000) 表示石頭可扔出的距離 ）
輸出數據：給出每組測試數據的結果，每行一個數據。
測試數據如下：
現在對整個題目進行分析，此人從第一塊石頭出發，隨著時間推移接下來遇到的石頭相對于起始位置越來越遠，因此石頭的位置是一個遞增的信息，由此可以斷定，存儲石頭信息的結構應該具備順序結構，但石頭的位置并不連續，如果用 vector 來存儲，勢必會造成空間的大量浪費。此人遇到偶數個石頭丟棄，遇到奇數個石頭要朝著他行走的方向往前扔，也就意味著扔到前面的石頭他還會再遇到。這就需要在處理的時候，刪掉偶數塊的石頭，并將奇數塊石頭重新添加到序列其他的位置，這就要求存儲石頭信息的結構需要有優良的插入、刪除性質，序列型容器 vector 在這一點上更顯的能力不足，這個時候，考慮其他的序列容器 隊列queue 、鏈表 list 。鏈表雖然在隨機插入刪除方面很有優勢，但若要求有序，鏈表操作是相當麻煩的。這個時候就剩 queue 還沒被拋棄，題目要求遇到一個石頭處理一個，即將此石頭出列進行其余操作，這正是隊列具備的特征，處理石頭的時候需要將奇數的石頭根據位置信息插入到相應位置。在有序的序列中，將元素插入到相應位置，priority_queue 就是應此要求誕生的。
選定了存儲結構，現在來討論一下具體的實現：使用計數器對此人遇到過的石頭進行計數，分成奇數和偶數情況來處理，偶數情況將該石頭信息出隊不作處理，奇數情況將石頭出隊，并把位置信息更改為當前位置加可扔距離再次入隊。每次對當前訪問的石頭位置進行存儲，如此處理直至隊列為空，輸出最后一個處理石頭的位置信息即可。
優先隊列需要對隊列的優先標準進行定義：當位置不相同時，位置靠前的優先性高，位置相同時，可扔距離較近的優先性較高。
在這個問題中需要考慮可扔距離為零的特殊情況。
下面對優先隊列使用中需要注意的問題進行闡述
優先隊列包含在 queue 頭文件中
優先隊列的聲明有三種形式，
第一種：
priority_queue< element_type > que；
此時聲明了一個存儲 element_type 類型元素的優先隊列 ，名稱為 que，這句聲明中包含了如下信息：
該優先隊列元素的類型為 element_type，
該優先隊列使用的容器為默認容器 vector ，
該優先隊列使用的優先級關系為優先級由高到低，一般的數字大的數據優先級高，此時隊首的元素為優先級高的元素。確定優先級的比較函數是less（）；請注意，優先隊列中的內置函數只能對基本數據類型進行排序，如果要對特殊類型進行排序，需要自定義比較函數。
第二種：
priority_queue< element_type, name< element_type > > ;
此時聲明了一個存儲 element_type 類型的元素的優先隊列 ，名稱為 que，這句聲明中包含了以下信息：
該優先隊列元素的類型為 element_type ,
該優先隊列使用的容器為 name 容器，（ 此處的 name 為用戶需要使用的容器的名稱，并非真實存在的某容器，假設 此處需要使用 queue容器，那么聲明為
priority_queue< element_type, queue< element_type > >
）
該隊列使用的優先級關系為默認優先級（由高到低），默認比較函數為 less（）。
第三種：
priority_queue< element_type , vector< element_type > , less<element_type > > ;
這種定義用于用戶使用非 less（）函數的其他優先級。
需要注意此時無論容器是不是默認容器 vector 都需要進行傳參，這由優先隊列相關函數內部實現決定。
例如：
現在元素類型為結構體類型，比較函數需要改變，則 處理如下：
struct node
{
element_type x;
element_type y;
};
bool compare( node a, node b )
{
return a . x > a . y ;(此處的優先級關系可任意更改)
}
priority_queue<node , vector<node> , compare<node> > ;
另例如下：
struct node
{
friend bool operator < ( node a , node b )
{
return a . y > b . y ; (同樣，此處的優先級順序也是可以根據需要任意更改的)
}
element_type x;
element_type y;
};
priority_queue< node>
或者下面這種：
priority_queue< node , vector<node> , less<node> > ; // 此時優先級實際上已經更改。
補充說明：
在優先隊列中，內置優先性比較函數有兩個：
less（），由隊首開始優先性逐漸減小
greater（），由隊首開始優先性逐漸增大
但不聲明的情況下，默認使用 less（），需要使用 greater （）的時候，要使用上面介紹的第三種聲明方式。
2. 優先隊列其余函數大多與普通隊列 queue 的使用方法類似。
以上是使用優先隊列的方法，下面我將用 multimap 方法對此題進行講解，在此題中，multimap 方法似乎有些麻煩，但是也不失為一種解題思路，重在介紹 multimap 的相關函數使用方法。
在序列式容器中有自動排序功能的是 priority_queue ，而關聯式容器也有這個特點，而且紅黑樹實現效率非常高。
關聯式容器有 set ／ multiset 和 map ／ multimap 這兩對：
set 的結構相當于集合，除了滿足集合的唯一性、確定性，還滿足有序性（默認由小到大排列）。multiset 與 set 的相關用法大多相同，唯一的區別在于，multiset 允許集合中有相同元素的出現，由此會引起部分函數的差異。
map／multimap 的結構相當于 映射對的集合，同樣，兩者大同小異，區別在于multimap中允許有相同鍵值的元素出現。
由于在某一確定時刻每個石頭的位置和可扔距離是確定的，且一一對應。因此我想到可以用 map 容器，又因為扔石頭過程中，同一位置有可能出現多于一塊石頭，因此可以確定使用 multimap 容器。
思路和上面的思路大同小異，先將初始數據存入 map ，然后設置計數變量和存儲當前位置的變量，map 不空就不斷進行計數變量的奇偶判斷和map 刪除、插入元素的處理。同樣應該考慮可扔距離為零的情況。
在這個過程中有一些需要注意的地方：
一、頭文件
multimap 包含在 map 頭文件中，使用時要在程序打開頭文件編寫時加入#include<map>語句。
二、聲明
分為兩種：
第一種：
multimap<key_type , value_type> mp；
包含以下信息
聲明了一個 鍵值為 key_type 類型 、關聯值為 value_type 類型的 multimap 型變量 mp；
multimap內 的鍵值排序按照默認排序順序由小到大；
第二種：
multimap<key_type , value_type ，compare< key_type> >;
包含以下信息
聲明了一個鍵值為 key_type 類型 ，關聯值為 value_type 類型的 multimap 型變量 mp；
multimap 內鍵值的排序規則由比較函數 compare給出，請注意這里 compare（）函數中的參數只有 鍵值的類型，而沒有關聯值的類型，原因是，multimap 內部的排序只根據鍵值大小進行排序，而對關聯值的順序沒有相應的處理，由此可見， multimap 中同一鍵值元素的相對位置并不是由關聯值的大小決定，而是由添加順序決定。
三、普通map可以用 map［key］來對鍵值為 key 的元素的關聯值進行操作，但 multimap 不包含此性質，因此向multimap中添加元素只能使用 insert（）函數，同樣也不能用mp[ key ]來訪問某一元素。用法如下：
mp . insert( pair< key_type ,value_type>( key ,value ) )
mp . insert( make_pair ( key , value ) ) ;
其中，pair是一種模版類型，含有兩個成員分別為 first 和 second。 兩個成員的類型可以根據需要任意確定，可以是基本數據類型，也可以是用戶自定義類型。pair 可以作為新的類型 進行函數傳參和使用。聲明如下：
pair< element_type , element_type > p = ( element_1 , element_2);
pair< element_type , element_type > p = make_pair ( element_1 , element_2 )
需要使用pair 的兩個成員時如下：
p . first
p . second
巧用 pair，當某函數需要返回兩個類型不同的值時，可以定義 pair 來返回。
四、如何確定鍵值相同而關聯值不同的元素的個數，以及如何對它們進行訪問：
確定個數使用函數
mp . count ( key ) ;
逐個進行訪問
mp . equal_range ( key ) ;
注意，此函數的返回值是兩個迭代器，其中，第一個迭代器返回的是 該鍵值第一個元素的迭代器，第二個迭代器返回的的是 該鍵值最后一個元素訪問結束即將跳轉的下一個元素的迭代器 。因此需要使用模版 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 ++ ;
}
在此應該注意思考一個問題：當multimap中只有一個元素的時候， p . second 此時的值應該與當前 mp . end ( ) 返回值相同，這時候，如果循環寫成這樣：
while( p . first != p . second )
{
cout << p . first << endl ;
mp . insert ( make_pair( elem_1 , elem_ 2 ) ) ;
p . first ++ ;
}
在插入新的元素后， mp . end ( ) 值變了，但 p . second 值還是原來的末尾，既不是現在的尾，也不是新加入的元素的位置，p .first 會一直自增尋找結束條件，但 p . second 目前已經失效了，會陷入死循環，并且這種錯誤一般不容易被發現 。因此在編寫程序的過程中，應該盡量避免這種情況的發生。改進方法需要根據具體的要求來實現，在這里就不舉例了。
五、特殊查找
mp . lower_bound( key ) 查找第一個鍵值不小于 key 的元素，返回其迭代器
mp . upper_bound( key ) 查找第一個鍵值比 key 大的元素，返回其迭代器
由上面注意事項中所提到的，同一鍵值的不同元素在multimap中的順序并不是按照 value 值的大小決定，而是由輸入順序決定，因此，在本題中，需要將相同鍵值的元素摘出來存在vector中，對其進行排序再使用。本題中，multimap 比 priority_queue 復雜的地方就在此了。
“multimap和priority_queue怎么理解”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
