為何要學習STL：

數據結構與算法是編程的核心，STL中包含各種數據結構和優秀的算法，確實值得深入學習，本文中雖然著重使用，但希望有心的朋友能多看看相關數據結構的實現，對于C++語言確實會有較大幫助。

?

STL庫有多個版本，我采用的是SGI版本，編譯安裝方法請參考如下鏈接：

http://blog.csdn.net/hong201/archive/2009/07/06/4322975.aspx

PS：按照網上孟巖老師的安裝方法，我出現了一些問題，后來按照上面文章所說的安裝成功。

?

關于為何采用SGI版本STL庫，目前我并沒有較深感觸，網上的說法是：

1.開源

2.可讀性強

3.自設了一些容器，如slist、hash_set等

談點我的感覺：運用VC自帶庫使用set容器時，發現可以通過迭代器來改變set的元素，改變會破壞紅黑樹，但編譯通過，這個是比較嚴重的BUG。

可以的話建議安裝SGI版本的STL庫。

?

在筆記中，我主要介紹各容器的用法，工具選用VC6.0。關于自定義類型數據如何使用容器，這個是許多人糾結的問題，我盡量寫一些例子。

因為是新學C++，所以文中不可避免會存在錯誤的地方，希望大家批評指正。

/*
?*
?********************************************
?*??deque雙端隊列容器的基礎說明：
?********************************************
?*?
?*
?*?可進行隨機訪問，在**頭部和尾端**插入、刪除元素，時間復雜度為O(1)
?*?Random Access Container?? Back Insertion Sequence?? Front Insertion Sequence
?*?
?************************************************************************************?
?*?當考慮容器元素的內存分配策略和操作的性能時，deque較vector更具優勢????*
?*?map管理塊，塊中包含一組數據，內存分配更細致(以塊為單位，使用二級的MAP進行管理)?*
?************************************************************************************?
?*?
?*?使用deque必須使用宏語句#include <deque>
?*
?**************************************************************************************
?*
?*?創建deque對象:
?*?1.deque<int> a;
?*?2.deque<int> a(10);??????//具有10個元素的對象a，每個元素默認值為0
?*?3.deque<char> a(5,'k');
?*?4.deque<char> b(a);??????//deque<char> c(a.begin(),a.end())
?*
?**************************************************************************************
?*
?*?初始化賦值
?*?void push_back(const T& value)
?*
?**************************************************************************************
?*
?*?遍歷訪問
?*?reference operator[](size_type n)
?*?iterator begin()
?*?iterator end()
?*
?**************************************************************************************
?*
?*?常用函數
?*
?*?bool empty();
?*?size_type size();size_type max_size();??//無size_type capacity();reverse();
?*?reference front();reference back();
?*?void pop_front();void push_front();???//相較vector增加部分
?*?void pop_back();void push_back();
?*?void clear();
?*????????????//還有些函數直接見代碼如erase();
?*
?*
?*
?********************************************
?*?Author: cumirror???
?*?Email:?tongjinooo@163.com
?********************************************
?*
?*/

#include <iostream>
#include <deque>

?

int main()
{
?using namespace std;
?deque<int> a(10,5);

//?數組方式
?cout<<"數組方式訪問:"<<endl;
?a[0]=100;
?for(int s=0;s<a.size();s++){
??cout<<a[s]<<endl;
?}

//?迭代器方式
?cout<<"迭代器方式訪問:"<<endl;
?deque<int>::iterator i,iend;
?i=a.begin();
?iend=a.end();
?*i=101;
?for(deque<int>::iterator j=i;j!=iend;j++){
??cout<<*j<<endl;
?}

//注意插入刪除時迭代器的失效問題,偷個懶,大家可以看下面的網頁,里面有說明但沒介紹原因,其實這與各個容器是如何實現的有很大關系,若想深究可看《STL源碼剖析》
//http://blog.csdn.net/jokenchang2000/archive/2008/07/01/2603485.aspx
?cout<<"插入"<<endl;
?a.insert(a.begin(),102);

//?刪除時注意，它是一個半閉區間
//?也支持 erase(iterator pos)單個元素的刪除
?cout<<"刪除"<<endl;
?a.erase(a.begin()+4,a.begin()+6);
?for(deque<int>::iterator k=a.begin();k!=a.end();k++){
??cout<<*k<<endl;
?}

//?頭部插入
?a.push_front(999);

//?反向遍歷訪問
?cout<<"反向訪問"<<endl;
?deque<int>::reverse_iterator ri;
?for(ri=a.rbegin();ri!=a.rend();ri++){
??cout<<*ri<<endl;
?}

?deque<int> b;
?b.push_back(4);
?b.push_back(5);
?b.push_front(3);
?b.push_front(2);
?cout<<"互換"<<endl;
?b.swap(a);
?for(int l=0;l<a.size();l++){
??cout<<a[l]<<endl;
?}
?return 0;
}

?

/*
?*
?********************************************
?*???list雙向鏈表容器的基礎說明：
?********************************************
?*
?*?list雙向鏈表容器采用雙向鏈表的數據結構來存儲元素數據，可以高效查找、插入、刪除容器元素
?*
?*?Reversibe Container? Back Insertion Sequence? Front Insertion Sequence
?*?不同于vector，list查找、插入、刪除元素的時間復雜度均為O(1)
?*?
?*?使用list必須使用宏語句#include <list>
?*
?**************************************************************************************
?*
?*?創建list對象:
?*?1.list<int> a;
?*?2.list<int> a(10);??????//具有10個元素的對象a，每個元素默認值為0
?*?3.list<char> a(5,'k');
?*?4.list<char> b(a);??????//list<char> c(a.begin(),a.end())
?*
?**************************************************************************************
?*
?*?初始化賦值
?*?void push_back(const T& value)
?*
?**************************************************************************************
?*
?*?遍歷訪問
?*?iterator begin()???//只能使用迭代器的方式進行遍歷
?*?iterator end()
?*? iterator rbegin();???//反向遍歷
?*? iterator rbegin();
?*?
?**************************************************************************************
?*
?*?常用函數
?*
?*?bool empty();
?*?
?*?void pop_front();?void pop_back();
?*?
?*?void push_front(const T&);?void push_back(const T&);
?*?iterator insert(iterator pos,const T&x);?//注意它是插入到pos前
?*
?*?iterator erase(iterator pos);
?*?iterator erase(iterator first,iterator last);
?*?void clear();
?*?void remove(const T& value);
?*
?*?void swap()?????????//通過交換頭指針來實現元素的交換
?*?//list內部提供的一個遷移操作
?*?void transfer();???????//transfer(iterator position,iterator first,iterator last)在A鏈表position位置前插入
?*????????????//B鏈表迭代器區間[first,last)的元素，并將這部分元素從B鏈表中抹去
?*?void splice(iterator pos,list& X);???//調用transfer函數將一個鏈表的所有元素全部歸并到當前鏈表，
?*????????????//并將鏈表對象X清空，
?*?void splice(iterator pos,list& X,iterator i);?//將X中迭代器i所指的元素歸并到當前鏈表pos前，并將X中i所指元素抹去
?*?
?*?void merge(list&X);?//對兩個鏈表進行歸并，要求先排序，否則merge沒有太大意義
?*
?*?void unique();??//可將連續重復的元素刪除，只保留一個
?*
?*
?*
?********************************************
?*?Author: cumirror???
?*?Email:?tongjinooo@163.com
?********************************************
?*
?*/

#include <list>
#include <iostream>???
#include <string>???
using namespace std;

struct student{
?char* name;
?int age;
?char* city;
?char* phone;
};

class studentNew{
public:
?char name[10];
?int age;
?char city[10];
?char phone[11];
?studentNew(){}
?studentNew(char* a,int b,char* c,char* d){
??strcpy(name,a);
??age=b;
??strcpy(city,c);
??strcpy(phone,d);
?}

//為何友元函數在類外定義，出現錯誤error C2593: 'operator >' is ambiguous
//friend bool operator < (studentNew&a,studentNew& b);
//friend bool operator > (studentNew&a,studentNew& b);
//friend bool operator == (studentNew&a,studentNew& b);

friend bool operator< (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)<0;
}
friend bool operator> (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)>0;
}
friend bool operator== (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)==0;
}

bool operator() (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)==-1;
}
};
/*
bool operator < (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)<0?true:false;
}
bool operator > (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)>0?true:false;
}
bool operator == (studentNew& a,studentNew& b){
?return strcmp(a.name,b.name)==0?true:false;
}
*/

int main(){
/*?list<int> a;
?a.push_back(4);
?a.push_back(3);
?a.push_back(2);
?a.push_back(8);
?a.push_back(7);
?a.push_back(5);
?a.push_back(6);
?a.push_back(9);
?a.push_back(10);
?a.push_back(1);

//?list的sort函數實現方法，如下

?list<int> carry;
?list<int> counter[64];
?int fill=0;
?while(!a.empty()){
?carry.splice(carry.begin(),a,a.begin());
?int i=0;
?while(i<fill&&!counter[i].empty()){
??counter[i].merge(carry);
??carry.swap(counter[i++]);
?}
?carry.swap(counter[i]);
?if(i==fill)++fill;
?}
?for(int i=1;i<fill;++i){
??counter[i].merge(counter[i-1]);
??a.swap(counter[fill-1]);
?}
?for(list<int>::iterator j=a.begin();j!=a.end();j++){
??cout<<*j<<endl;
?}
*/
//?其它函數使用示例,如下：

?student s[]={
??{"童進",23,"武漢","XXX"},
??{"老大",23,"武漢","XXX"},
??{"餃子",23,"武漢","XXX"}
?};
?list<student> classA;
?classA.push_back(s[0]);
?classA.insert(classA.begin(),s[1]);
?classA.push_back(s[3]);
?cout<<classA.begin()->name<<endl;
//?classA.sort();????????????????//對于自定義結構體，沒有重載</>/==這些操作符，故無法排序

//?自己創建一個新類studentNew重載操作符再進行判斷
?studentNew m1("童進",23,"武漢","XXX");
?studentNew m2("老大",23,"武漢","XXX");
?studentNew m3("餃子",23,"武漢","XXX");
?list<studentNew> classNew;
?classNew.push_back(m1);
?classNew.push_back(m2);
?classNew.push_back(m3);
//?判斷友元函數是否起作用
?if( m1>m2 ){
??cout<<"新類中操作已經重載成功"<<endl;
?}
//?運用SGI STL庫時
//?用函數對象studentNew,替換了greater<T>
?classNew.sort(studentNew());
//?若用VC自帶的STL庫時,下面這樣書寫即可實現.至于為何有這樣的差異,目前我還不知
// classNew.sort();?
?for(list<studentNew>::iterator m=classNew.begin();m!=classNew.end();m++){?//通過結果可以看出
??cout<<m->name<<endl;?????????????//classNew已經進行了重新排列
?}??????????????????????????????

?list<string> classB;
?classB.push_back("童");
?classB.push_back("蘭");
?classB.push_front("張");
?classB.push_back("童");
?classB.sort();????????????????//對于string類型,有默認類型的greater<T>
?classB.unique();???????????????//剔除重復數據
?for(list<string>::iterator k=classB.begin();k!=classB.end();k++){
??cout<<*k<<endl;
?}
?return 0;
}

/*
?*
?********************************************
?*???slist單向鏈表容器的基礎說明：
?********************************************
?*
?*?slist是SGI C++STL自設的一個容器，要安裝配置stlport才可以使用
?*
?*?Front Insertion Sequence
?*?slist為單向鏈表的泛化容器,故不再支持迭代器的反向移動
?*
?*?使用slist必須使用宏語句#include <slist>
?*
?**************************************************************************************
?*
?*?創建slist對象:
?*?1.slist<int> a;
?*?2.slist<int> a(10);?????????//具有10個元素的對象a，每個元素默認值為0
?*?3.slist<char> a(5,'k');
?*?4.slist<char> b(a);??????
?*?5.slist(InputIterator first,InputIterator last);?//slist<char> c(a.begin(),a.end())
?*
?**************************************************************************************
?*
?*?初始化賦值
?*?void push_front(const T& value)
?*
?**************************************************************************************
?*
?*?遍歷訪問
?*?僅定義了向前移動的迭代器iterator和const_iterator
?*?iterator begin();iterator end();
?*
?**************************************************************************************
?*
?*?常用函數
?*
?*?void swap(slist&);
?*?iterator insert_after(iterator pos,const T& x);??//?注意與前面不同的是，這里是在POS位置之后進行插入
?*??????????????//?vector、deque、list都是POS前插入
?*?iterator insert(iterator pos,const T& X);???//?找到pos的前驅，再調用insert_after進行插入(pos前插入)
?*
?*?void pop_front();
?*
?*?iterator erase(iterator pos);
?*?iterator erase(iterator first,iterator last);??//?注意是半閉區間[first,last)
?*?void clear();
?*?void remove(const T& x);???????//?刪除所有等于value的元素
?*
?*?void splice(iterator pos,slist& x);
?*?void splice(iterator pos,iterator i);
?*
?*?void merge(slist& x);
?*
?*?void sort();??????????//?按"<"關系進行排序
?*?void unique();??????????//?刪除重復元素，僅保留一個
?*
?*
?*
?********************************************
?*?Author: cumirror???
?*?Email:?tongjinooo@163.com
?********************************************
?*
?*/

#include <slist>
#include <string>
#include <iostream>
using namespace std;

//具體使用請參照前面的容器例子，這里不進行舉例說明
int main(){
?slist<string> a;
?a.push_front("武漢");
?a.push_front("長沙");
?for(slist<string>::iterator i=a.begin();i!=a.end();i++){
??cout<<*i<<endl;
?}
?return 0;
}

/*
?*
?********************************************
?*???set集合容器的基礎說明：
?********************************************
?*
?*?set集合容器使用RB-Tree的平衡二叉檢索樹的數據結構,不允許插入重復鍵值
?*?每個子樹根節點的鍵值大于左子樹所有節點的鍵值，而小于右子樹所有節點的所有鍵值
?*?插入過程中要進行平衡處理，但檢索過程效率高
?*
?*?提供了元素插入、刪除、檢索的功能
?*?Unique Sorted Associative Container? Simple Associative Container
?*
?*?使用set必須使用宏語句#include <set>
?*
?**************************************************************************************
?*
?*?創建set對象:
?*?1.set<int> a;
?*?2.set(const key_compare& comp)??????//指定一個比較函數對象comp來創建set對象
?*
?*?srtuct strLess{?
?*??bool operator()(const char* s1,const char* s2) const{
?*???return strcmp(s1,s2)<0;
?*??}
?*?};
?*?set<const char*,strLess> s(strLess());
?*
?*? 3.set(const set&);?????????//set<int> b(a);
?*?4.set(first,last);?????????//set<char> c(a.begin(),a.end())
?*?5.set(first,last,const key_compare& comp);
?**************************************************************************************
?*
?*?元素的插入???????????//不允許插入重復鍵值
?*?pair<iterator,bool> insert(const value_type& v);?//可用于判斷是否重復插入元素,對于特殊的信息可以提供這樣的判斷
?*?iterator insert(iterator pos,const value_type& v);
?*?void insert(first,last);
?*
?**************************************************************************************
?*
?*?元素的刪除
?*?void erase(iterator pos);
?*?size_type erase(const key_type& k);?????//刪除等于鍵值k的元素
?*?void erase(first,last);????????//刪除[first,last)區間的元素
?*?void clear();
?*
?**************************************************************************************
?*
?*?訪問與搜索
?*
?*?iterator begin();iterator end();?????
?*?reverse_iterator rbegin();reverse_iterator rend();
?*
?*?iterator find(const key_type& k) const;
?*
?*?其它常用函數
?*?bool empty() const;
?*?size_type size() const;
?*?void swap();
?*
?*?//下面三個函數還沒找到合適的例子，故不做說明
?*?iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下屆、確定區間
?*
?*
?*
?********************************************
?**?? cumirror ** tongjinooo@163.com **??? **
?********************************************
?*
?*/

#include <set>
#include <iostream>

//自定義數據的插入
struct student{
?char name[20];
?int age;
?char city[20];
?char phone[20];
?bool operator()(const student& a,const student& b) const{
??return strcmp(a.name,b.name)<0;
?}
};

int main(){
?using namespace std;
?set<int> a;
?a.insert(10);
?a.insert(19);
?a.insert(8);
?a.insert(102);
?a.insert(1);
?pair<set<int>::iterator, bool> p=a.insert(18);
?if(p.second){
??cout<<"插入的新元素為："<<*(p.first)<<endl;
?}
?else{
??cout<<"已存在該元素，重復插入"<<endl;
?}

?set<int>::iterator i=a.find(8);
//?*i=250;?????????//與侯捷STL源碼剖析237頁所述有出入
?cout<<*i<<endl;???????//原文為：企圖通過迭代器改變元素是不被允許的
//?a.insert(251);???????//但VC6.0編譯運行沒有問題，只是set中的排序不正確了
???????????//即使重新插入251，因沒有違反紅黑樹標準，錯誤不被修正
???????????//是否是因為STL版本問題:換STLport后編譯果然報錯
???????????//vc6.0中的STL庫存在一定問題,大家注意
?cout<<"元素訪問："<<endl;
?for(set<int>::iterator j=a.begin();j!=a.end();j++){
??cout<<*j<<endl;
?}

//?為何稱為容器，我認為在于對于用戶自定義數據的包容，故寫如下例子進行測試驗證
//?也可以嘗試用age作為判斷條件
?student stu1={"童進",23,"武漢","XXX"};
?student stu2={"老大",28,"武漢","XXX"};????//老大，你成熟了5歲，哈哈
?student stu3={"餃子",23,"武漢","XXX"};
?set<student,student> b(student());
?b.insert(stu1);
?b.insert(stu2);
?b.insert(stu3);

?student stu4={"餃子123",88,"福州","XXX"};???
?pair<set<student,student>::iterator,bool> query=b.insert(stu4);?
?if(query.second==false)????????//query.first返回插入元素的迭代器;query.second代表插入是否成功,true成功:false失敗
??cout<<"重復元素插入會失敗"<<endl;
?cout<<query.first->name<<endl;
?for(set<student,student>::iterator k=b.begin();k!=b.end();k++){
??cout<<k->name<<endl;
?}

//?student test1={"老大",23,"武漢","XXX"};????//這樣的元素，可以找到
//?set<student,student>::iterator v=b.find(test1);
//?student test2={"",23,"武漢","XXX"};?????//無法找到
//?set<student,student>::iterator v=b.find(test2);??
?student test3={"老大",99,"",""};?????//可以找到，推測：
?set<student,student>::iterator v=b.find(test3);??//1.鍵值的設定依據key_compare()函數中的設置
?cout<<v->age<<endl;?????????//2.鍵值直接為定義數據類型中的第一個元素
??????????????//結論：推測1正確。
??????????????//可以修改operator()函數進行驗證，也可以看后續multiset中的例子
?return 0;???????????
}

?

/*
?*
?********************************************
?*???multiset多重集合容器的基礎說明：
?********************************************
?*
?*?multiset多重集合容器使用RB-Tree的平衡二叉檢索樹的數據結構。
?*?允許將重復鍵值的元素插入到multiset中
?*?插入過程中要進行平衡處理，但檢索過程效率高
?*
?*?提供了元素插入、刪除、檢索的功能
?*?Sorted Associative Container? Simple Associative Container?? Multiple Associative Container
?*
?*?使用multisetr必須使用宏語句#include <set>???//與set相同
?*
?**************************************************************************************
?*
?*?創建multisetr對象:
?*?template < class Key, class Compare=less<Key>, class Alloc=alloc >
?*
?*?1.multisetr<int> a;
?*?2.multisetr(const key_compare& comp)????//指定一個比較函數對象comp來創建set對象，詳細使用見main()中示例
?*? 3.multisetr(const multisetr&);??????//multisetr<int> b(a);
?*?4.multisetr(first,last);???????//multisetr<char> c(a.begin(),a.end())
?*?5.multisetr(first,last,const key_compare& comp);?//依據comp函數進行插入排序
?**************************************************************************************
?*
?*?元素的插入
?*?iterator insert(const value_type& v);????//不再是返回pair，而是插入的迭代器位置
?*?iterator insert(iterator pos,const value_type& v);
?*?void insert(first,last);
?*
?**************************************************************************************
?*
?*?元素的刪除
?*?void erase(iterator pos);
?*?size_type erase(const key_type& k);?????//刪除等于鍵值k的元素
?*?void erase(first,last);????????//刪除[first,last)區間的元素
?*?void clear();
?*
?**************************************************************************************
?*
?*?訪問與搜索
?*
?*?iterator begin();iterator end();?????//企圖通過迭代器改變元素是不被允許的
?*?reverse_iterator rbegin();reverse_iterator rend();
?*
?*?iterator find(const key_type& k) const;
?*?pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair對象，
?*????????????????//first為lower_bound(k);大于等于k的第一個元素位置
?*????????????????//second為upper_bound();大于k的第一個元素位置
?*
?*?其它常用函數
?*?bool empty() const;
?*?size_type size() const;
?*?size_type count(const key_type& k) const;???//返回鍵值等于k的元素個數
?*?void swap();
?*
?*?//main中包含了一下函數的簡單例子
?*?iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下屆、確定區間
?*
?*
?*
?********************************************
?**?? cumirror ** tongjinooo@163.com **??? **
?********************************************
?*
?*/

#include <set>
#include <iostream>

//?自定義數據的插入
struct student{
?char name[20];
?int age;
?char city[20];
?char phone[20];
};

//?這里采用函數對象的方式設置,與set中有不同,key設置為city,注意應設置為public
class stuCmp{
public:
?bool operator()(const student& a,const student& b) const{
??return strcmp(a.city,b.city)<0;
?}
};

//?對于一些基本數據類型，如int，string等可參照set
int main(){
?using namespace std;
?student stu1={"童進",23,"長沙","XXX"};
?student stu2={"老大",28,"武漢","XXX"};????//老大，你成熟了5歲，哈哈
?student stu3={"餃子",23,"福州","XXX"};
//?multiset<student,stuCmp> b;???????
?multiset<student,stuCmp> b(stuCmp());
?b.insert(stu1);
?b.insert(stu2);
?b.insert(stu3);
//?武漢同學最多,只是現在大家又都天各一方
?student stu4={"小芳",23,"武漢","XXX"};
?student stu5={"黃慶",23,"武漢","XXX"};
?student stu6={"英俊",23,"武漢","XXX"};
?b.insert(stu4);
?b.insert(stu5);
?b.insert(stu6);

?for(multiset<student,stuCmp>::iterator i=b.begin();i!=b.end();i++){
??cout<<i->name<<endl;
?}

?student key={"",99,"武漢","XXX"};
?cout<<"武漢朋友數目："<<b.count(key)<<endl;
?cout<<"武漢的第一個朋友："<<b.lower_bound(key)->name<<endl;
?cout<<"武漢最后一個朋友："<<(--b.upper_bound(key))->name<<endl;?//?這里武漢是最后的,再大于這個鍵值,就會返回end()指向頭節點,所以--
?for(multiset<student,stuCmp>::reverse_iterator j=b.rbegin();j!=b.rend();j++){
??cout<<j->name<<endl;
?}

//?驗證set中的猜測,此時鍵值為city
?student test={"路人甲",99,"武漢","XXX"};????
?multiset<student,stuCmp>::iterator v=b.find(test);?//返回第一個與鍵值相等的迭代器 ?
?cout<<"尋找武漢的路人甲："<<v->name<<endl;

//?元素搜索
?cout<<"搜索武漢的朋友們："<<endl;
?pair<multiset<student,stuCmp>::iterator,multiset<student,stuCmp>::iterator> p=b.equal_range(test);
?for(multiset<student,stuCmp>::iterator k=p.first;k!=p.second;k++){
??cout<<k->name<<endl;
?}
?return 0;
}

/*
?*
?********************************************
?*???map映照容器的基礎說明：
?********************************************
?*
?*?map映照容器:容器的數據結構采用紅黑樹進行管理,插入的元素鍵值不允許重復
?*?map的所有元素都是pair:第一元素為鍵值(key),不能修改;第二元素為實值(value),可被修改
?*?
?*?map和list一樣,使用insert或erase后,操作前的所有迭代器,在操作完成后依然有效
?*?[]:不僅可用鍵值的數組方式訪問元素的映照數據,還可用來添加map容器的元素?//main中示例
?*?
?*?Sorted Associative Container? Pair Associative Container?? Unique Associative Container
?*
?*?使用map必須使用宏語句#include <map>???
?*
?**************************************************************************************
?*
?*?創建map對象:
?*?1.map<char,int,greater<char> > a;????//元素鍵值類型為char,映照數據類型為int,鍵值的比較函數對象為greater<char>
?*?2.map(const key_compare& comp)?????//指定一個比較函數對象comp來創建map對象
?*? 3.map(const map&);??????//map<int,char*> b(a);?//此時使用默認的鍵值比較函數less<int>
?*?4.map(first,last);?????????
?*?5.map(first,last,const key_compare& comp);??
?*
?*?//Example:
?*?pair<const int ,char> p1(1,'a');
?*?pair<const int ,char> p2(2,'b');
?*?pair<const int ,char> p3(3,'c');
?*?pair<const int ,char> p4(4,'d');
?*?pair<const int ,char> pairArray[]={p1,p2,p3,p4};
?*?map<const int,char> m4(pairArray,pairArray+5);
?*?map<const int,char> m3(m4);
?*?map<const int,char,greater<const int> > m5(pairArray,pairArray+5,greater<const int>());
?*
?**************************************************************************************
?*
?*?元素的插入
?*?//typedef pair<const key,T> value_type;
?*?pair<iterator,bool> insert(const value_type& v);????
?*?iterator insert(iterator pos,const value_type& v);
?*?void insert(first,last);
?*
?**************************************************************************************
?*
?*?元素的刪除
?*?void erase(iterator pos);
?*?size_type erase(const key_type& k);?????//刪除等于鍵值k的元素
?*?void erase(first,last);????????//刪除[first,last)區間的元素
?*?void clear();
?*
?**************************************************************************************
?*
?*?訪問與搜索
?*
?*?iterator begin();iterator end();?????//企圖通過迭代器改變元素是不被允許的
?*?reverse_iterator rbegin();reverse_iterator rend();
?*
?*?iterator find(const key_type& k) const;
?*?pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair對象，
?*????????????????//first為lower_bound(k);大于等于k的第一個元素位置
?*????????????????//second為upper_bound();大于k的第一個元素位置
?*
?*?其它常用函數
?*?bool empty() const;
?*?size_type size() const;
?*?void swap();
?*
?*?iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下屆、確定區間
?*
?*
?*
?********************************************
?**?? cumirror ** tongjinooo@163.com **??? **
?********************************************
?*
?*/

#include <map>
#include <string>
#include <iostream>

//?基本操作與set類似,牢記map中所有元素都是pair
//?對于自定義類,初學者會覺得比較函數如何構造很麻煩,這個可以參照前面的書寫示例
//?但若設置鍵值為int或char類型，無須構造比較函數

struct student{
?char* name;
?int age;
?char* city;
?char* phone;
};

struct strCmp{
?bool operator () (const char* a,const char* b) const{
??return strcmp(a,b)<0;
?}
};

struct strCmpBig{
?bool operator () (const char* a,const char* b) const{
??return strcmp(a,b)>0;
?}
};

int main(){
?using namespace std;
//?使用[]操作符
?map<string,int> animal;
?animal[string("fish")]=12;
?animal[string("dog")]=10;
?animal[string("cat")]=5;
?cout<<animal["cat"]<<endl;

//?string類有默認的比較函數,故下面的語句可以執行,若換為char*類型,則執行會出現問題
//?迭代器i指向pair類型
?for(map<string,int>::iterator i=animal.begin();i!=animal.end();i++){
??cout<<"The number of "<<i->first<<" : "<<i->second<<endl;
?}

?student s[]={
??{"童進",23,"武漢","XXX"},
??{"老大",23,"武漢","XXX"},
??{"餃子",23,"武漢","XXX"}
?};
??pair<int,student> p1(4,s[0]);
??pair<int,student> p2(2,s[1]);
??pair<int,student> p3(3,s[2]);
?map<int,student> a;
?a.insert(p1);
?a.insert(p2);
?a.insert(p3);
//?按照鍵值2、3、4進行排列輸出
?for(map<int,student>::iterator j=a.begin();j!=a.end();j++){??????
??cout<<"The name: "<<j->second.name<<"?? "<<"age: "<<j->second.age<<"?? "
???<<"city: "<<j->second.city<<"?? "<<"phone: "<<j->second.phone<<endl;
?}

//?思考，這是按照鍵值進行排列，若我想變換，按照name或者年齡進行重新排列，那么又該如何實現呢？
?
?cout<<"新的排列"<<endl;
??pair<const char*,student> q1(s[0].name,s[0]);
??pair<const char*,student> q2(s[1].name,s[1]);
??pair<const char*,student> q3(s[2].name,s[2]);

?student testStu={"AB",23,"武漢","XXX"};

//?為何要采用函數對象的形式，而不只能是函數，這個與C++內部實現機制有關

?map<const char*,student,strCmp> b;
?b.insert(q1);
?b.insert(q2);
?b.insert(q3);

//?insert函數的測試,觀察其放回迭代器的值,可改變名字看看,插入位置視實際情況定
//?返回插入元素的迭代器
??pair<const char*,student> q4(testStu.name,testStu);
?map<const char*,student,strCmp>::iterator test=b.insert(b.begin()++,q4);
?cout<<test->second.name<<endl;

?for(map<const char*,student,strCmp>::iterator k=b.begin();k!=b.end();k++){??????
??cout<<"The name: "<<k->second.name<<"?? "<<"age: "<<k->second.age<<"?? "
???<<"city: "<<k->second.city<<"?? "<<"phone: "<<k->second.phone<<endl;
?}

//?拷貝的時候也可以進行函數對象的設置，那如果函數對象變換了，能實現順序的變化嗎？
//?目前還沒實現，不知道具體可行嗎？以后再進行測試吧

//?個人觀點：不可行。函數對象比較的是key，若重新排列，key不能變換，
//?那么所謂的重新排列，豈不僅僅是反序排列，而反序輸出map已經具有了這樣的函數了。

?cout<<"拷貝時實現重新排列"<<endl;?????//并未實現
?map<const char*,student,strCmp> c(b);
?for(map<const char*,student,strCmp/*strCmpBig*/>::iterator m=c.begin();m!=c.end();m++){??????
??cout<<"The name: "<<m->second.name<<"?? "<<"age: "<<m->second.age<<"?? "
???<<"city: "<<m->second.city<<"?? "<<"phone: "<<m->second.phone<<endl;
?}?

?return 0;
}

/*
?*
?********************************************
?*??multimap多重映照容器的基礎說明：
?********************************************
?*
?*?multimap多重映照容器:容器的數據結構采用紅黑樹進行管理
?*?multimap的所有元素都是pair:第一元素為鍵值(key),不能修改;第二元素為實值(value),可被修改
?*
?*?multimap特性以及用法與map完全相同，唯一的差別在于:
?*?允許重復鍵值的元素插入容器(使用了RB-Tree的insert_equal函數)?
?*?因此:
?*?鍵值key與元素value的映照關系是多對多的關系
?*?沒有定義[]操作運算?
?*?
?*?Sorted Associative Container? Pair Associative Container?? Unique Associative Container
?*
?*?使用multimap必須使用宏語句#include <map>??????????
?*
?**************************************************************************************
?*
?*?創建multimap對象:
?*?1.multimap<char,int,greater<char> > a;????//元素鍵值類型為char,映照數據類型為int,鍵值的比較函數對象為greater<char>
?*?2.multimap(const key_compare& comp)?????//指定一個比較函數對象comp來創建map對象
?*? 3.multimap(const multisetr&);??????//multimap<int,char*> b(a);?//此時使用默認的鍵值比較函數less<int>
?*?4.multimap(first,last);?????????
?*?5.multimap(first,last,const key_compare& comp);??
?*
?*?//Example:
?*?pair<const int ,char> p1(1,'a');
?*?pair<const int ,char> p2(2,'b');
?*?pair<const int ,char> p3(3,'c');
?*?pair<const int ,char> p4(4,'d');
?*?pair<const int ,char> pairArray[]={p1,p2,p3,p4};
?*?multimap<const int,char> m4(pairArray,pairArray+5);
?*?multimap<const int,char> m3(m4);
?*?multimap<const int,char,greater<const int> > m5(pairArray,pairArray+5,greater<const int>());
?*
?**************************************************************************************
?*
?*?元素的插入
?*?//typedef pair<const key,T> value_type;
?*?pair<iterator,bool> insert(const value_type& v);????
?*?iterator insert(iterator pos,const value_type& v);
?*?void insert(first,last);
?*
?**************************************************************************************
?*
?*?元素的刪除
?*?void erase(iterator pos);
?*?size_type erase(const key_type& k);?????//刪除等于鍵值k的元素
?*?void erase(first,last);????????//刪除[first,last)區間的元素
?*?void clear();
?*
?**************************************************************************************
?*
?*?訪問與搜索
?*
?*?iterator begin();iterator end();?????//企圖通過迭代器改變元素是不被允許的
?*?reverse_iterator rbegin();reverse_iterator rend();
?*
?*?iterator find(const key_type& k) const;
?*?pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair對象，
?*????????????????//first為lower_bound(k);大于等于k的第一個元素位置
?*????????????????//second為upper_bound();大于k的第一個元素位置
?*
?*?其它常用函數
?*?bool empty() const;
?*?size_type size() const;
?*?size_type count(const key_type& k) const;???//返回鍵值等于k的元素個數
?*?void swap();
?*
?*?iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下屆、確定區間
?*
?*
?*
?********************************************
?**?? cumirror ** tongjinooo@163.com **??? **
?********************************************
?*
?*/

#include <map>
#include <string>
#include <iostream>

//?基本操作與set類型,牢記map中所有元素都是pair
//?對于自定義類,初學者會覺得比較函數如何構造很麻煩,這個可以參照前面的書寫示例
//?但若設置鍵值為int或char類型，無須構造比較函數

struct student{
?char* name;
?int age;
?char* city;
?char* phone;
};

int main(){
?using namespace std;

?student s[]={
??{"童進",23,"武漢","XXX"},
??{"老大",23,"武漢","XXX"},
??{"餃子",23,"武漢","XXX"},
??{"王老虎",23,"武漢","XXX"},
??{"周潤發",23,"武漢","XXX"},
??{"周星星",23,"武漢","XXX"}
?};
??pair<int,student> p1(4,s[0]);
??pair<int,student> p2(2,s[1]);
??pair<int,student> p3(3,s[2]);
??pair<int,student> p4(4,s[3]);??//鍵值key與p1相同
??pair<int,student> p5(5,s[4]);
??pair<int,student> p6(6,s[5]);
?multimap<int,student> a;
?a.insert(p1);
?a.insert(p2);
?a.insert(p3);
?a.insert(p4);
?a.insert(p5);
?a.insert(p6);
?typedef multimap<int,student>::iterator int_multimap;
?pair<int_multimap,int_multimap> p=a.equal_range(4);
?int_multimap i=a.find(4);
?cout<<"班上key值為"<<i->first<<"的學生有："<<a.count(4)<<"名,"<<"?? 他們是:"<<endl;
?for(int_multimap k=p.first;k!=p.second;k++){
??cout<<k->second.name<<endl;
?}
?cout<<"刪除重復鍵值的同學"<<endl;
?a.erase(i);
?cout<<"現在班上總人數為："<<a.size()<<".?? 人員如下："<<endl;
?for(multimap<int,student>::iterator j=a.begin();j!=a.end();j++){??????
??cout<<"The name: "<<j->second.name<<"????? "<<"age: "<<j->second.age<<"?? "
???<<"city: "<<j->second.city<<"????? "<<"phone: "<<j->second.phone<<endl;
?}

?return 0;
}

/*
?*
?************************************************************************************
?*??????hash_set哈希集合容器的基礎說明：
?************************************************************************************
?*
?*?hash_set哈希集合容器:使用hashtable數據結構的具有高效數據檢索的關聯容器
?*?
?*?不提供反向迭代器，只有前向迭代器iterator和const_iterator
?*?不允許插入重復的元素鍵值
?*?Hashed Associative Container? Simple Associative Container?? Unique Associative Container
?*
?*?目前還不是C++的標準容器，只是SGI C++ STL的一個擴展容器
?*?使用hash_set必須使用宏語句#include <hash_set>??????????
?*?
?**************************************************************************************
?*
?*?創建hash_set對象:
?*?1.hash_set<int> hs;????????//鍵值比較使用默認的函數對象equal_to<Value>
?*?2.hash_set(size_type n);??????//在質數列表中找出第一個大于等于n的質數作為表長:hash_set<int> hs(100);
?*? 3.hash_set(size_type n,const hasher& h);??//hash函數對象為h
?*?4.hash_set(size_type n,const hasher& h,const key_equal& k);//鍵值比較函數對象k?????????
?*?5.hash_set(const hash_set& h);?????//用一個hash集合容器拷貝生成另一個hash集合容器:hash_set<int> hs2(hs);?
?*
?**************************************************************************************
?*
?*?元素的插入
?*?//typedef pair<const key,T> value_type;
?*?pair<iterator,bool> insert(const value_type& v);//second:返回true/false插入成功標志???
?*?void insert(iterator pos,const value_type& v);
?*
?**************************************************************************************
?*
?*?元素的刪除
?*?void erase(iterator pos);
?*?size_type erase(const key_type& k);?????//刪除等于鍵值k的元素
?*?void erase(first,last);????????//刪除[first,last)區間的元素
?*?void clear();
?*
?**************************************************************************************
?*
?*?訪問與搜索
?*
?*?iterator begin();iterator end();?????//不會將元素排序遍歷出來
?*
?*?iterator find(const key_type& k) const;????//對于非默認類型如char*,在搜素時應定義相關的函數對象
?*
?*?其它常用函數
?*?bool empty() const;
?*?size_type size() const;
?*?size_type bucket_count(const key_type& k) const;?//獲得hash表的表長
?*?void swap();
?*?resize();
?*?iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下屆、確定區間
?*
?*?在SGI STL中，提供了以下hash函數：
?*?struct hash<char*>
?*?struct hash<const char*>
?*?struct hash<char>
?*?struct hash<unsigned char>
?*?struct hash<signed char>
?*?struct hash<short>
?*?struct hash<unsigned short>
?*?struct hash<int>
?*?struct hash<unsigned int>
?*?struct hash<long>
?*?struct hash<unsigned long>
?*
?*?hash函數決定了如何劃分散列表
?*
?*
?*
?********************************************
?**?? cumirror ** tongjinooo@163.com **??? **
?********************************************
?*
?*/

#include <hash_set>
#include <iostream>

struct student{
?char* name;
?int age;
?char* city;
?char* phone;
};
//自定義數據的比較函數
class stuequal{
public:
?bool operator() (const student& a,const student& b){
??return strcmp(a.city,b.city)==0;??????//不允許同名，name為鍵值
?}???????????????//將name換為city測試下
};
//自定義數據的hash函數
//typedef unsigned int size_t;
struct stu_hash{
?size_t operator()(const student& stu) const
?{
??unsigned long res = 0;
??char* s=stu.city;
??for( ; *s; ++s ){
???res=5*res+*s;
??}
??return size_t(res);
?}
};

//針對字符串的比較函數對象
class strequal{
public:
?bool operator () (const char* a,const char* b)const{
??return strcmp(a,b)==0;?????????
?}
};

int main(){
?using namespace std;

?hash_set<const char*,hash<const char*>,strequal> a;
?a.insert("tongjin");
?a.insert("cumirror");
?a.insert("makelaugh");
?a.insert("feiguodeyun");

//?hash<const char*>默認提供的hash函數對象
?hash_set<const char*,hash<const char*>,strequal>::const_iterator b=a.find("tongjin");
?cout<<*b<<" is "<<(b!=a.end()?"present":"not present")<<endl;

//?對于自定義類型數據,使用hash相關容器時應構造hash函數對象、比較函數對象
//?注意區別hash函數對象與比較函數對象各自的作用
?student s[]={
??{"童進",23,"長沙","XXX"},
??{"老大",23,"武漢","XXX"},
??{"餃子",23,"福州","XXX"},
??{"王老虎",23,"地球","XXX"},
??{"周潤發",23,"香港","XXX"},
??{"周星星",23,"香港","XXX"},???//city重復
??{"童進",23,"香港","XXX"}???//name重復、city也有重復
?};?????????

?hash_set<student,stu_hash,stuequal> c;
?c.insert(s[0]);
?c.insert(s[1]);
?c.insert(s[2]);
?c.insert(s[3]);
?c.insert(s[4]);
?c.insert(s[5]);
?c.insert(s[6]);
//?注意hash容器并不能實現排序
?for(hash_set<student,stu_hash,stuequal>::iterator i=c.begin();i!=c.end();i++){
??cout<<i->name<<"?"<<i->age<<"?"<<i->city<<endl;
?}
?return 0;
}

/*
?*
?************************************************************************************
?*???????hash_map映照容器的基礎說明：
?************************************************************************************
?*
?*?hash_map哈希映照容器:使用hash表的數據結構,插入的元素鍵值不允許重復
?*?hash_map的所有元素都是pair:第一元素為鍵值(key),不能修改;第二元素為實值(value),可被修改
?*?
?*?不提供反向迭代器,只有前向迭代器iterator和const_iterator
?*?可定義出操作符[]
?*?
?*?Hashed Associative Container? Pair Associative Container?? Unique Associative Container
?*
?*?目前還不是C++的標準容器，只是SGI C++ STL的一個擴展容器
?*?使用hash_map必須使用宏語句#include <hash_map>???
?*?可與map作比較:?hash_map檢索時使用的鍵值比較次數少，容器需占用較多的空間，用迭代器遍歷出來的元素是非排序的；
?*?????map則使用鏈表的二分法進行檢索，空間使用率高，遍歷出來的元素是排序的，而且可提供反向迭代器。
?*?
?**************************************************************************************
?*
?*?創建map對象:
?*?1.hash_map<char,int> a;???????//鍵值類型為char,映照數據類型為int,默認表長為193
?*?2.hash_map(size_type n);??????//hash_map<char,int> a(300);此時表長為389?
* *? 3.hash_map(size_type n,const hasher& h);??
* *?4.hash_map(size_type n,const hasher& h,const key_equal& k);??????????
?*?5.hash_map(const hash_map&);??
?*
?*?//Example4:
?*?struct strequal{
?*??bool operator() (const char* a,const char* b) const {
?*???return strcmp(a,b)==0;}
?*?};
?*?hash_map<char*,int,hash<char*>,strequal> hm(300,hash<char*>(),strequal());
?*
?**************************************************************************************
?*
?*?元素的插入
?*?//typedef pair<const key,T> value_type;
?*?pair<iterator,bool> insert(const value_type& v);????
?*?void insert(first,last);
?*
?**************************************************************************************
?*
?*?元素的刪除
?*?void erase(iterator pos);
?*?size_type erase(const key_type& k);?????//刪除等于鍵值k的元素
?*?void erase(first,last);????????//刪除[first,last)區間的元素
?*?void clear();
?*
?**************************************************************************************
?*
?*?訪問與搜索
?*
?*?iterator begin();iterator end();?????//企圖通過迭代器改變元素是不被允許的
?*
?*?iterator find(const key_type& k) const;
?*?pair<iterator,iterator> equal_range(const key_type& k) const;?//此時鍵值不允許重復，故沒有太大用途
?*
?*?其它常用函數
?*?bool empty() const;
?*?size_type size() const;
?*?size_type bucket_count(const key_type& k) const;?//獲得hash表的表長
?*?void swap();
?*?resize();
?*?void swap();
?*
?*?iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下屆、確定區間
?*
?*
?*
?********************************************
?**?? cumirror ** tongjinooo@163.com **??? **
?********************************************
?*
?*/

#include <string>
#include <hash_map>
#include <iostream>
using namespace std;

template<class Key,class NameType,class AgeType,class AdressType>
struct StudentRecord_tag{??//學生記錄結構體
?struct StudentInfo_tag{
??NameType name;
??AgeType age;
??AdressType city;
?};
?typedef Key IdType;
?typedef StudentInfo_tag StudentInfo;
?IdType id;
?StudentInfo stuinfo;
};

//針對最后的示例，設置的hash函數
struct myhash{
?size_t operator() (const string& str) const
?{
??unsigned long __h = 0;
??for (size_t i = 0 ; i < str.size() ; i ++)
???__h = 5*__h + str[i];
??return size_t(__h);
?}
};

class str_compare{
public:
?bool operator()(const string& str1,const string& str2)const
?{
??return?? str1==str2;
?}
};

int main(){
//?使用[]操作符
?hash_map<string,int> animal;
?animal[string("fish")]=12;
?animal[string("dog")]=10;
?animal[string("cat")]=5;
?cout<<animal["cat"]<<endl;
//?結構體A中定義的結構體B，在結構體A外可以使用嗎？
//?StudentInfo_tag a;??//直接這樣是無法使用的,若想獨立使用可以參照下面的方法
//?typedef StudentRecord_tag<int,char*,int,char*> StudentRecorda;
//?StudentRecorda::StudentInfo_tag testa;

?typedef StudentRecord_tag<int,char*,int,char*> StudentRecord;
?StudentRecord stuArray[]={
??{192,"黃慶",23,"北京"},
??{191,"童進",23,"長沙"},
??{194,"餃子",23,"福州"},
??{193,"小芳",23,"寧波"},
?};
//?此處應該留意typedef的使用
?hash_map<StudentRecord::IdType,StudentRecord::StudentInfo> school;?
?typedef pair<const StudentRecord::IdType,StudentRecord::StudentInfo> value_type;
?for(int i=0;i<4;i++){
??value_type p(stuArray[i].id,stuArray[i].stuinfo);
??school.insert(p);
?}
//?測試是否插入成功
?cout<<school[193].name<<endl;
//?采用迭代器訪問，注意map類型容器，其元素為pair類型，pair中first/second要明白
?hash_map<StudentRecord::IdType,StudentRecord::StudentInfo>::iterator j;
?cout<<"同學"<<"?"<<"住址"<<endl;
?for(j=school.begin();j!=school.end();j++){
??cout<<j->second.name<<"?"<<
???j->second.city<<endl;
?}
//?其它函數示例
//?元素的重復插入
?value_type p(stuArray[0].id,stuArray[0].stuinfo);
?pair<hash_map<const StudentRecord::IdType,StudentRecord::StudentInfo>::iterator,bool> insertReturn;
?cout<<(
??(insertReturn=school.insert(p)).second==true?"插入成功":"插入失敗"
??)
??<<endl;
?cout<<"總人數："<<school.size()<<endl;
?cout<<"hash表長："<<school.bucket_count()<<endl;

//?如下思考：

//?上例中key:IdType為int型,故不用定義hash函數對象,也可將IdType定為string類型，形如"0120504140227"這樣的類型
//?此時需要定義hash函數,具體解法如下:(在原來定義的變量名后+1)

//?原想在上面例子的基礎上進行改進,但不成功，可能與string類型內存分配模式有關

//?typedef StudentRecord_tag< string,char*,int,char*> StudentRecord1;
//?StudentRecord1 stuArray1[]={??????//不好意思,你們暫時先入我班吧
//??{string("0120504140208"),"黃慶",23,"北京"},
//??{string("0120504140227"),"童進",23,"長沙"},
//??{string("0120504140209"),"餃子",23,"福州"},
//??{string("0120504140216"),"小芳",23,"寧波"},
//?};
//?hash_map<StudentRecord1::IdType,StudentRecord1::StudentInfo,myhash> school1;?
//?typedef pair<const StudentRecord1::IdType,StudentRecord1::StudentInfo> value_type1;
//?for(int i=0;i<4;i++){
//??value_type1 p(stuArray1[i].id,stuArray1[i].stuinfo);
//??school.insert(p);
//?}

//?在網上看到一份較為簡單的例子,根據自己的稍稍改了下(注意前面的hash函數與比較函數)
?hash_map<string,string,myhash,str_compare>? myHash;
?string strArray[][2]={
??{"0120504140227","童進"},
??{"0120504140236","zyl"},
??{"0120504140216","hq"},
??{"0120504140209","jz"},
?};
?typedef pair<string,string> value_type2;

?for(int k=0;k<4;k++){
??value_type2 p(strArray[k][0],strArray[k][1]);
??myHash.insert(p);
?}
?hash_map<string,string,myhash,str_compare>::iterator p1;
?for(p1=myHash.begin();p1!=myHash.end();p1++){
??cout<<p1->first<<"?"<<
???p1->second<<endl;
?}
?return 0;
}