關(guān)聯(lián)容器： 1)map：經(jīng)過排序了的二元組的集合，map中的每個(gè)元素都是由兩個(gè)值組成，其中的key（鍵值，一個(gè)map中的鍵值必須是唯一的） 是在排序或搜索時(shí)使用，它的值可以在容器中重新獲取；而另一個(gè)值是該元素關(guān)聯(lián)的數(shù)值。 2)set：包含了經(jīng)過排序了的數(shù)據(jù)，這些數(shù)據(jù)的值(value)必須是唯一的 map和set的基本原理：紅黑樹。
一.紅黑樹實(shí)現(xiàn)——STL中的map 1.map是一類關(guān)聯(lián)式容器。它的特點(diǎn)是增加和刪除節(jié)點(diǎn)對(duì)迭代器的影響很小，除了那個(gè)操作節(jié)點(diǎn)，對(duì)其他的節(jié)點(diǎn)都沒有什么影響。對(duì)于迭代器來說，可以修改實(shí)值，而不能修改key。
2.map的功能： 1）自動(dòng)建立Key － value的對(duì)應(yīng)（key 和 value可以是任意你需要的類型） 2）根據(jù)key值快速查找記錄，查找的復(fù)雜度基本是Log(N)，如果有1000個(gè)記錄，最多查找10次，1,000,000個(gè)記錄，最多查找20次。 3）快速插入Key - Value 記錄 4）快速刪除記錄 5）根據(jù)Key 修改value記錄 6）遍歷所有記錄
3.map對(duì)象是模板類，需要關(guān)鍵字和存儲(chǔ)對(duì)象兩個(gè)模板參數(shù),這樣就定義了一個(gè)用int作為索引,并擁有相關(guān)聯(lián)的指向string的指針.
4.map使用： 1.數(shù)據(jù)的插入 在構(gòu)造map容器后，我們就可以往里面插入數(shù)據(jù)了 1)用insert函數(shù)插入pair數(shù)據(jù)
#include <map>#include <string>#include <iostream>using namespace std;int main(){ map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, "student_one")); mapStudent.insert(pair<int, string>(2, "student_two")); mapStudent.insert(pair<int, string>(3, "student_three")); map<int, string>::iterator iter; for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { cout << iter->first << " "<< iter->second << endl; }}2)用insert函數(shù)插入value_type數(shù)據(jù)
#include <map>#include <string>#include <iostream>using namespace std;int main(){ map<int, string> mapStudent; mapStudent.insert(map<int, string>::value_type(1, "student_one")); mapStudent.insert(map<int, string>::value_type(2, "student_two")); mapStudent.insert(map<int, string>::value_type(3, "student_three")); map<int, string>::iterator iter; for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { cout << iter->first << " " << iter->second <<endl; }}3)用數(shù)組方式插入數(shù)據(jù)
#include <map>#include <string>#include <iostream>using namespace std;int main(){ map<int, string> mapStudent; mapStudent[1] = "student_one"; mapStudent[2] = "student_two"; mapStudent[3] = "student_three"; map<int, string>::iterator iter; for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { cout << iter->first << " " << iter->second << endl; }}以上三種用法，雖然都可以實(shí)現(xiàn)數(shù)據(jù)的插入，但是它們是有區(qū)別的，當(dāng)然了第一種和第二種在效果上是完成一樣的，用insert函數(shù)插入數(shù)據(jù)，在數(shù)據(jù)的插入上涉及到集合的唯一性這個(gè)概念，即當(dāng)map中有這個(gè)關(guān)鍵字時(shí)，insert操作是插入數(shù)據(jù)不了的，但是用數(shù)組方式就不同了，它可以覆蓋以前該關(guān)鍵字對(duì)應(yīng)的值，用程序說明
mapStudent.insert(map<int, string>::value_type (1, “student_one”));mapStudent.insert(map<int, string>::value_type (1, “student_two”));上面這兩條語句執(zhí)行后，map中1這個(gè)關(guān)鍵字對(duì)應(yīng)的值是“student_one”，第二條語句并沒有生效，那么這就涉及到我們?cè)趺粗纈nsert語句是否插入成功的問題了，可以用pair來獲得是否插入成功，程序如下
Pair<map<int, string>::iterator, bool> Insert_Pair;Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”));我們通過pair的第二個(gè)變量來知道是否插入成功，它的第一個(gè)變量返回的是一個(gè)map的迭代器，如果插入成功的話Insert_Pair.second應(yīng)該是true的，否則為false。
下面給出完成代碼，演示插入成功與否問題:
#include <map>#include <string>#include <iostream>using namespace std;int main(){ map<int, string> mapStudent; 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 { cout << "Insert Failure" << endl; } Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_two")); if(Insert_Pair.second == true) { cout << "Insert Successfully" << endl; } else { cout << "Insert Failure" << endl; } map<int, string>::iterator iter; for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { cout << iter->first << " " << iter->second << endl; } system("pause"); return 0;}2.刪除： erase() 1) erase ( iterator position ); 刪除的是position位置的元素 2）size_type erase ( const key_type& x ); 刪除的是鍵值所在的位置，成功為1，否則為0 3）void erase ( iterator first, iterator last ); 刪除一段迭代器區(qū)間
二.set 方法： clear() 清除所有元素 count() 返回某個(gè)值元素的個(gè)數(shù) empty() 如果集合為空，返回true(真） erase() 刪除一段迭代器區(qū)間 find() 返回一個(gè)指向被查找到元素的 迭代器 insert() 在集合中插入元素
count():count是為了統(tǒng)計(jì)某個(gè)數(shù)值出現(xiàn)的次數(shù)，在set里面不能重復(fù)出現(xiàn)相同的數(shù)值，count的返回值只有0和1兩個(gè)值，0表示的是不存在，1表示存在。
三.應(yīng)用：統(tǒng)計(jì)水果出現(xiàn)最多次數(shù)的問題：
using namespace std;#include<cstdlib> #include<set> #include<map> #include<vector> #include<string> #include<algorithm> //統(tǒng)計(jì)水果出現(xiàn)次數(shù)最多的前三個(gè) void CountTopK(vector<string>& v){ map<string, int> countMap; for (size_t i = 0; i<v.size(); ++i) { // 第一種方法 // find()遍歷了一遍，insert()又重復(fù)遍歷了一遍 // map<string,int>::iterator ret=countMap.find(v[i]); // if(ret!=countMap.end()) //找到 // { // ret->second ++; // } // else //沒找到 // countMap.insert(pair<string,int>(v[i],1)); // 第二種方法 //pair<map<string,int>::iterator ,bool> ret=countMap.insert(pair<string,int>(v[i],1)); //if(ret.second ==false) //沒插入成功，說明已有 // ret.first ->second ++; // 第三種方法 countMap[v[i]]++; } //只能統(tǒng)計(jì)出數(shù)量最多的一個(gè) /*map<string,int>::iterator countit=countMap.begin (); map<string,int>::iterator max=countMap.begin (); while(countit!=countMap.end()) { if(countit->second >max->second ) max=countit; ++countit; }*/ //為了統(tǒng)計(jì)出排在前三位置的水果 //第一種解法：把map的迭代器push到vector中，然后調(diào)用算法中的sort方法 //vector<map<string,int>::iterator > vinfos; //map<string,int>::iterator countit=countMap.begin (); //while(countit!=countMap.end()) //{ // vinfos.push_back (countit); // countit++; //} //仿函數(shù) //struct Compare //{ // bool Operator()(map<string,int>::iterator& l,map<string,int>::iterator& r) // { // return l->second > r->second; // } //}; //sort(vinfos.begin(),vinfos.end(),Compare()); //從大到小排列 //第二種解法：把pair結(jié)構(gòu)插入到vector中 vector<pair<string, int>> vinfos(countMap.begin(), countMap.end()); //仿函數(shù) struct Compare { bool operator()(pair<string, int>& l, pair<string, int>& r) { return l.second > r.second; } }; sort(vinfos.begin(), vinfos.end(), Compare()); //從大到小排列 }int main(){ vector<string> v; v.push_back("蘋果"); v.push_back("蘋果"); v.push_back("香蕉"); v.push_back("蘋果"); v.push_back("蘋果"); v.push_back("梨"); v.push_back("梨"); v.push_back("蘋果"); v.push_back("蘋果"); v.push_back("蘋果"); v.push_back("蘋果"); v.push_back("梨"); //給it指向的位置插入“西瓜”，其他的依次向后拷貝，size+1 /*vector<string>::iterator it=v.begin(); it++; v.insert(it,"西瓜");*/ CountTopK(v); system("pause"); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
