<b>3.4.2 map的查增删</b>
<b></b>
<b>1.?map的插入</b>
先講下map的插入，map的插入有3種方式：用insert函數插入pair資料、用insert函數插入value_type資料和用數組方式插入資料。
【例3.18】 用insert函數插入pair資料。
#include
<map>
<string>
<iostream>
using namespace
std;
int main()
{
map<int, string> mapstudent;
mapstudent.insert(pair<int,
string>(1, "student_one"));
string>(2, "student_two"));
string>(3, "student_three"));
map<int, string>::iterator iter;
for(iter = mapstudent.begin(); iter !=
mapstudent.end(); iter++){
cout<<iter->first<<"
"<<iter->second<<endl;
}
return 0;
}
程式的執行結果是：
1 student_one
2 student_two
3 student_three
例3.18中，聲明了一個key為int類型，value為string類型的map，用insert函數插入pair資料，且需要在insert的參數中将(1, "student_one")轉換為pair資料再進行插入。
【例3.19】 用insert函數插入value_type資料。
mapstudent.insert(map<int,
string>::value_type (1,"student_one"));
mapstudent.insert(map<int, string>::value_type
(2,"student_two"));
string>::value_type (3,"student_three"));
map<int, string>::iterator iter;
例3.19中，聲明了一個key為int類型，value為string類型的map，用insert函數插入value_type資料，且需要在insert的參數中将(1, "student_one")轉換為map<int, string>::value_type資料再進行插入。
【例3.20】 map中用數組方式插入資料。
#include <map>
#include <string>
int main(){
mapstudent[1] = "student_one";
mapstudent[2] = "student_two";
mapstudent[3] = "student_three";
cout<<iter->first<<"
1 student_one
2 student_two
3 student_three
例3.20中展示了用數組方式在map中插入資料，和數組通路一樣，有下标、直接指派。以上3種用法，雖然都可以實作資料的插入，但是它們是有差別的，當然了第一種和第二種在效果上是完成一樣的，用insert函數插入資料，在資料的插入上涉及集合的唯一性這個概念，即當map中有這個關鍵字時，insert操作是插入資料不了的，但是用數組方式就不同了，它可以覆寫以前該關鍵字對應的值。
mapstudent.insert(map<int,
string>::value_type (1, "student_one"));
string>::value_type (1, "student_two"));
上面這兩條語句執行後，map中1這個關鍵字對應的值是student_one，第二條語句并沒有生效，那麼這就涉及如何知道insert語句是否插入成功的問題了，可以用pair來獲得是否插入成功，程式如下：
pair<map<int,
string>::iterator, bool> insert_pair;
insert_pair =
mapstudent.insert(map<int, string>::value_type (1,
"student_one"));
可以通過pair的第二個變量來知道是否插入成功，它的第一個變量傳回的是一個map的疊代器，如果插入成功的話insert_pair.second應該是true的，否則為false。
【例3.21】 用pair判斷insert到map的資料是否插入成功。
pair<map<int, string>::iterator,
bool> insert_pair;
insert_pair =
mapstudent.insert(pair<int,string>(1,"student_one"));
if(insert_pair.second == true){
cout<<"insert
successfully"<<endl;
else{
failure"<<endl;
insert_pair =
mapstudent.insert(pair<int, string>(1, "student_two"));
cout<<"insert
}else{
map<int, string>::iterator iter;
for(iter = mapstudent.begin(); iter !=
}
return 0;
insert
successfully
insert failure
例3.21中，用pair判斷insert到map的資料是否插入成功。pair變量insert_pair中的第一個元素的類型是map<int, string>::iterator，是和即将要判斷的map中的key、value類型一緻的一個map的疊代器。如果insert成功了，則insert_pair.second的結果為true，否則則為false。同一個key已經有資料之後，再insert就會失敗。而數組插入的方式，則是直接覆寫。
【例3.22】 資料方式插入map覆寫原有的資料。
map<int,string> mapstudent;
mapstudent[1] = "student_one";
mapstudent[1] = "student_two";
mapstudent[2] = "student_three";
1 student_two
2 student_three
例3.22中展示了mapstudent[1]上已經有資料"student_one"了，再用語句：
mapstudent[1]
= "student_two";
就可以直接覆寫成功。
2.?map的周遊
map資料的周遊，這裡也提供3種方法，來對map進行周遊：應用前向疊代器方式、應用反向疊代器方式和數組方式。應用前向疊代器，上面舉例程式中已經講解過了，這裡着重講解應用反向疊代器的方式，下面舉例說明。
【例3.23】 map反向疊代器的使用舉例。
mapstudent[2] = "student_two";
mapstudent[3] = "student_three";
map<int,
string>::reverse_iterator iter;
for(iter = mapstudent.rbegin(); iter !=
mapstudent.rend(); iter++){
例3.23中，iter就是一個反向疊代器reverse_iterator，它需要使用rbegin()和rend()方法指出反向周遊的起始位置和終止位置。注意，前向周遊的一般是從begin()到end()周遊，而反向周遊則是從rbegin()到rend()。
【例3.24】 用數組方式周遊map。
#include<map>
#include<string>
#include<iostream>
int isize = mapstudent.size();
for(int i = 1; i <= isize; i++){
cout<<i<<"
"<<mapstudent[i]<<endl;
例3.24中，用size()方法确定目前map中有多少元素。用數組通路vector時，下标是從0～（size-1），而用數組通路map，卻是從1~size，這是有所不同的，請使用者多加注意。
3.?map的查找
在這裡可以充分體會到map在資料插入時保證有序的好處。要判定一個資料（關鍵字）是否在map中出現的方法比較多，這裡給出2種常用的資料查找方法。
第一種：用count函數來判定關鍵字是否出現，其缺點是無法定位資料出現位置，由于map的一對一的映射特性，就決定了count函數的傳回值隻有兩個，要麼是0，要麼是1，當要判定的關鍵字出現時傳回1。
第二種：用f?ind函數來定位資料出現位置，它傳回的一個疊代器，當資料出現時，它傳回資料所在位置的疊代器；如果map中沒有要查找的資料，它傳回的疊代器等于end函數傳回的疊代器。
【例3.25】 用f?ind方法查找map中的資料。
map<int, string>::iterator
iter=mapstudent.find(1);
if(iter != mapstudent.end()){
cout<<"found, the value is
cout<<"do not
found"<<endl;
find, the value
is student_one
f?ind函數傳回的是一個疊代器；找不到對應資料的時候，則會傳回mapstudent.end()。
4.?map的删除
用erase方法可删除map中的元素。erase的函數原型是：
map.erase(k)
删除map中鍵為k的元素，并傳回size_type類型的值以表示删除的元素個數，代碼如下：
map.erase(p)
從map中删除疊代器p所指向的元素。p必須指向map中确實存在的元素，而且不能等于map.end()，傳回void類型，代碼如下：
map.erase(b,e)
從map中删除一段範圍内的元素，該範圍由疊代器對b和e标記。b和e必須标記map中的一段有效範圍：即b和e都必須指向map中的元素或最後一個元素的下一個位置。而且，b和e要麼相等（此時删除的範圍為空），要麼b所指向的元素必須出現在e所指向的元素之前，傳回void類型。常用的是第二種，并且是在周遊的過程中删除元素。
【例3.26】 用erase方法删除map中的元素。
mapstudent[1]="student_one";
mapstudent[2]="student_two";
mapstudent[3]="student_three";
mapstudent[4]="student_four";
map<int, string>::iterator
iter=mapstudent.begin();
for(;iter!=mapstudent.end();){
if((*iter).second=="student_one"){
mapstudent.erase(iter++);
}
else{
++iter;
for(iter=mapstudent.begin();iter!=mapstudent.end();iter++){
4 student_four
mapstudent.erase(iter++);中的iter++，不是erase(iter)，然後iter++。因為iter指針被erase之後就失效了，不能再用iter++；也不是erase(++iter)，這樣就不是删iter原來指向的元素了。
5.?map的排序
map的排序預設按照key從小到大排序，但有以下幾點需要注意：①按照key從大到小排序；②key（第一個元素）是一個結構體；③想按value（第二個元素）排序。
map是stl裡面的一個模闆類，現在來看下map的定義：
template <
class key, class t, class compare = less<key>,
class allocator =
allocator<pair<const key,t> > > class map;
它有4個參數，其中比較熟悉的有兩個：key和value。第4個是allocator，用來定義存儲配置設定模型的，此處不作介紹。
現在重點看下第3個參數：
class compare =
less<key>
這也是一個class類型的，而且提供了預設值less<key>。less是stl裡面的一個函數對象，那麼什麼是函數對象呢？
所謂的函數對象，即調用操作符的類，其對象常稱為函數對象（function object），它們是行為類似函數的對象。表現出一個函數的特征，就是通過“對象名+(參數清單)”的方式使用一個類，其實質是對operator()操作符的重載。
現在來看一下less的實作：
template
<class t> struct less : binary_function <t,t,bool> {
bool operator() (const t& x, const
t& y) const
{return x<y;}
};
它是一個帶模闆的struct，裡面僅僅對()運算符進行了重載，實作很簡單，但用起來很友善，這就是函數對象的優點所在。stl中還為四則運算等常見運算定義了這樣的函數對象，與less相對的還有greater：
<class t> struct greater : binary_function <t,t,bool> {
{return x>y;}
是以，要想讓map中的元素按照key從大到小排序，可以如例3.27所示。
【例3.27】 讓map中的元素按照key從大到小排序。
map<string, int, greater<string>
> mapstudent;
mapstudent["limin"]=90;
mapstudent["zilinmi"]=72;
mapstudent["bob"]=79;
map<string, int>::iterator
cout<<iter->first<<" "<<iter->second<<endl;
return 0;
zilinmi 72
limin 90
bob 79
如例3.27中所示，隻需指定它的第3個參數compare，把預設的less指定為greater，即可達到按照key從大到小排序。現在知道如何為map指定compare類了，如果想自己寫一個compare的類，讓map按照想要的順序來存儲，比如按照學生姓名的長短排序進行存儲，那麼隻要自己寫一個函數對象，實作想要的邏輯，并在定義map的時候把compare指定為自己編寫的這個就可以實作了，代碼如下：
struct
cmpbykeylength {
bool operator()(const string& k1, const
string& k2) {
return k1.length() < k2.length();
這裡不用把compare定義為模闆，直接指定它的參數為string類型就可以了。
【例3.28】 重定義map内部的compare函數。
#include <string>
map<string, int, cmpbykeylength >
mapstudent;
mapstudent["limin"]=90;
mapstudent["zilinmi"]=72;
mapstudent["bob"]=79;
是以，想改變map的key排序方法，可以通過修改compare函數實作。
key是結構體的，如果沒有重載小于号（<）操作，就會導緻insert函數在編譯時就無法編譯成功。其實，為了實作快速查找，map内部本身就是按序存儲的（比如紅黑樹）。在插入<key, value>鍵值對時，就會按照key的大小順序進行存儲。這也是作為key的類型必須能夠進行<運算比較的原因。
【例3.29】 key是結構體的map排序。
typedef struct
tagstudentinfo
int iid;
string
strname;
bool operator < (tagstudentinfo
const& r) const {
// 這個函數指定排序政策，按iid排序，如果iid相等的話，按strname排序
if(iid < r.iid) return true;
if(iid == r.iid) return
strname.compare(r.strname) < 0;
return false;
}studentinfo;// 學生資訊
/*用學生資訊映射分數*/
map<studentinfo, int>mapstudent;
studentinfo studentinfo;
studentinfo.iid = 1;
studentinfo.strname =
"student_one";
mapstudent[studentinfo]=90;
studentinfo.iid = 2;
"student_two";
mapstudent[studentinfo]=80;
map<studentinfo, int>::iterator
for(;iter!=mapstudent.end();iter++){
cout<<iter->first.iid<<"
"<<iter->first.strname<<"
1 student_one 90
2 student_two 80
例3.29中，mapstudent的key是studentinfo類型的，要重載studentinfo類型的<号，這樣才能正常地插入到mapstudent中。
如果想按照map的value（第二個元素）排序，第一反應是利用stl中提供的sort算法實作，這個想法是好的，不幸的是，sort算法有個限制，利用sort算法隻能對序列容器進行排序，隻能是線性的（如vector、list、deque）。map也是一個集合容器，它裡面存儲的元素是pair，但是它不是線性存儲的（如紅黑樹），是以利用sort不能直接和map結合進行排序。雖然不能直接用sort對map進行排序，那麼可以間接進行，把map中的元素放到序列容器（如vector）中，然後再對這些元素進行排序呢？這個想法看似是可行的。要對序列容器中的元素進行排序，也有個必要條件：就是容器中的元素必須是可比較的，也就是實作了<操作的。那麼現在就來看下map中的元素是否滿足這個條件。
已知map中的元素類型為pair，具體定義如下：
<class t1, class t2> struct pair
typedef t1 first_type;
typedef t2 second_type;
t1 first;
t2 second;
pair() : first(t1()), second(t2()) {}
pair(const t1& x, const t2& y) :
first(x), second(y) {}
template <class u, class v>
pair (const pair<u,v> &p) :
first(p.first), second(p.second) { }
pair也是一個模闆類，這樣就實作了良好的通用性。它僅有兩個資料成員f?irst和second，即key和value，而且在<utility>頭檔案中，還為pair重載了< 運算符，具體實作如下所示：
template<class
_t1, class _t2>
inline bool
operator<(const pair<_t1,
_t2>& __x, const pair<_t1, _t2>& __y)
{ return __x.first < __y.first
|| (!(__y.first < __x.first)
&& __x.second < __y.second); }
重點看下其實作，如下所示：
__x.first <
__y.first || (!(__y.first < __x.first) && __x.second <
__y.second)
這個less在兩種情況下傳回true。第一種情況：__x.f?irst < __y.f?irst，這種情況較好了解，就是比較key與__x、__y的大小，如果__x的key小于__y的key則傳回true。
第二種情況有點費解，代碼如下所示：
!(__y.first <
__x.first) && __x.second < __y.second
當然由于||運算具有短路作用，即目前面的條件不滿足時，才進行第二種情況的判斷。第一種情況__x.f?irst < __y.f?irst不成立，即__x.f?irst >= __y.f?irst成立，在這個條件下，再來分析下!(__y.f?irst < __x.f?irst)
&& __x.second < __y.second。
!(__y.f?irst
< __x.f?irst)表示y的key不小于x的key，結合前提條件，__x.f?irst < __y.f?irst不成立，即x的key不小于y的key。
即：!(__y.f?irst < __x.f?irst) &&!(__x.f?irst < __y.f?irst
)等價于__x.f?irst ==
__y.f?irst ，也就是說，第二種情況是在key相等的情況下，比較兩者的value（second）。
這裡比較令人費解的地方就是，為什麼不直接寫__x.f?irst == __y.f?irst呢？這麼寫看似費解，但其實也不無道理：前面講過，作為map的key必須實作<操作符的重載，但是并不保證==操作符也被重載了，如果key沒有提供==，那麼__x.f?irst == __y.f?irst的寫法就不對。由此可見，stl中的代碼是相當嚴謹的，值得好好研讀。
現在知道了pair類重載了<符，但是它并不是按照value進行比較的，而是先對key進行比較，key相等時候才對value進行比較。顯然不能滿足按value進行排序的要求。
而且，既然pair已經重載了<符，但不能修改其實作，也不能在外部重複實作重載
<符。
如果pair類本身沒有重載<符，那麼按照下面的代碼重載<符，是可以實作對pair類按value比較的。但現在這樣做不行了，甚至會出錯（編譯器不同，嚴格的就報錯）。
typedef
pair<string, int> pair;
bool
operator< (const pair& lhs, const pair& rhs) {
return lhs.second < rhs.second;
那麼要如何實作對pair按value進行比較呢？第一種是最原始的方法，寫一個比較函數；第二種剛才用到了，寫一個函數對象，如下所示。這兩種方式實作起來都比較簡單。
cmp_by_value(const pair& lhs, const pair& rhs) {
cmpbyvalue {
bool operator()(const pair& lhs, const
pair& rhs) {
return lhs.second < rhs.second;
接下來使用sort算法，來檢驗其是不是像map一樣，也可以對指定的元素進行比較，代碼如下所示：
<class randomaccessiterator>
void sort (
randomaccessiterator first, randomaccessiterator last );
<class randomaccessiterator, class compare>
randomaccessiterator first, randomaccessiterator last, compare comp );
結果表明，sort算法和map一樣，也可以對指定元素進行比較，即指定compare。需要注意的是，map是在定義時指定的，是以傳參的時候直接傳入函數對象的類名，就像指定key和value時指定的類型名一樣；sort算法是在調用時指定的，需要傳入一個對象，當然這個也簡單，類名()就會調用構造函數生成對象。
這裡也可以傳入一個函數指針，就是把上面說的第一種方法的函數名傳過來。
【例3.30】 将map按value排序。
<vector>
map<string, int> name_score_map;
name_score_map["limin"] = 90;
name_score_map["zilinmi"] = 79;
name_score_map["bob"] = 92;
name_score_map.insert(make_pair("bing",99));
name_score_map.insert(make_pair("albert",86));
/*把map中元素轉存到vector中*/
vector<pair>
name_score_vec(name_score_map.begin(), name_score_map.end());
sort(name_score_vec.begin(),
name_score_vec.end(), cmpbyvalue());
/*sort(name_score_vec.begin(),
name_score_vec.end(), cmp_by_value);也是可以的*/
for (int i = 0; i != name_score_vec.size();
++i) {
cout<<name_score_vec[i].first<<"
"<<name_score_vec[i].second<<endl;
例3.30中要對map中的value進行排序，先把map的元素按pair形式插入到vector中，再對vector進行排序（用一個新寫的比較函數），這樣就可以實作按map的value排序了。
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)