首页 > 代码库 > C++学习STL之关联容器 --- pair、map、set
C++学习STL之关联容器 --- pair、map、set
本博文我们继续讨论标准模板库STL的关联容器;
主要有:pair、map、set。
一:pair
pair是一种简单的关联类型,不属于容器范围。而是代表一个 key-value键值对。
创建、初始化、操作 示例代码如下:
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 using namespace std; 5 //将pair放入容器&initpair 6 int main(int argc, const char *argv[]) 7 { 8 vector<pair<string, int> > vec;//初始化vector 9 10 pair<string, int> p1;//num.111 p1.first = "hello";12 p1.second = 12 ;13 vec.push_back(p1);14 15 pair<string, int> p2("world", 22);//num.216 vec.push_back(p2);17 18 vec.push_back(make_pair<string, int>("foo", 44));//num.319 20 for(vector<pair<string,int> >::iterator it = vec.begin(); //g++ main.cc -std=c++0x21 it != vec.end(); 22 ++it)23 {24 cout << "key: " << it->first << " val:"<< it->second << endl; 25 }26 27 return 0;28 }
二:map
1):map则是一个容器,里面存储的是 pair对象。但存储的方式与vector<pair>这种 连续存储有所不同, map采用的是 二叉排序树存储pair,一般是红黑树。
2):map使用下标访问时,如果 key不存在,那么会在map 中自动添加一个新的pair,value为默认值。
性能分析:由于map采用二叉排序树(红黑树),树的高度不超过 [logN] +1。所以 插入和查询时间复杂度 为 O(lgN);
注意:使用insert插入map元素时,如果失败,则不会更新原来的值。
a):初始化(示例代码如下):
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <map> 5 #include <algorithm> 6 using namespace std; 7 //Red_black Tree 8 int main(int argc, const char *argv[]) 9 {10 map<string, int> m;11 m["beijing"] = 2000;12 m["hangzhou"] = 880;13 m["shanghai"] = 1500;14 // key --> value 采用二叉排序树对key排序15 //两种打印方式16 for(map<string, int>::const_iterator it = m.begin();17 it != m.end();18 it++)19 {20 //*it pair21 cout << it->first <<":" << it->second << endl;22 }23 for(const pair<int, string> &p: m) // -std=c++0x(C++11) 注意要用pair 24 cout << p.first << ":" << p.second << endl;25 return 0;26 }
b):下标访问
每当用下标访问map元素的时候,如果元素不存在,那么会在map中新生成一个键值对。所以,用下标访问不存在的键值对时,会增加容器的大小。 (应用:单词计数程序)
1 map<string, int> word_count;2 string word;3 while (cin >> word) {4 word_count[word]++; 5 for_each(word_count.begin(), word_count.end(), print);
c):insert操作(map,set有insert操作, 而vector没有)
示例如下;
1 //本例测试insert的返回值 2 int main(int argc, const char *argv[]) 3 { 4 map<string, int> m ; 5 6 m.insert(make_pair("hello",1)); 7 m.insert(make_pair("wordl",2)); 8 m.insert(make_pair("foo",1)); 9 10 cout << m.size() << endl; //311 12 //insert的返回值类型13 pair<map<string, int>::iterator, bool> ret ;14 //插入成功15 ret = m.insert(make_pair("faasdf",23));16 cout << "ret:" << ret.second << endl; //117 //插入失败18 ret = m.insert(make_pair("hello",234)); //false19 cout << "ret:" << ret.second << endl;20 21 //ret.first 代表指向迭代器的指针。22 cout << "ret:" << ret.first->second << endl; // 123 24 return 0;25 }
d):count,find 函数测试 key值得存在性。
注意:下标操作 与 count 的区别
使用下标获取value值的时候,存在这样一个弊端,如果下表访问的是不存在的元素,俺么会自动给map 增加一个 key-value键值对,有时候这不是我们所预期的。
而count和find可以较好解决这一问题。
count:仅仅能得出该元素是否存在。
find: 能够返回该元素的迭代器 。
示例代码如下:
1 //count、 insert、find 测试key存在性 2 int main(int argc, const char *argv[]) 3 { 4 map<string, string> m; 5 m["beijing"] = "good"; 6 m["shanghai"] ="good"; 7 m["shenzhen"]= "good"; 8 9 cout << m.count("beijing") << endl;// 110 cout << m.count("HK") << endl;// 011 12 map<string, string>::iterator it = m.find("beijing");13 //m.find("Hk")--->不存在14 if(it == m.end())15 cout << "不存在" <<endl;16 else17 cout << it->first <<":" << it->second << endl ; //18 return 0;19 }
三:set (停用词功能)
insert、erase、find操作。
实例代码如下:
1 //set 三个性质; 确定性,唯一性,无序性 2 //和 map 一样, 采用 红黑树 RB_Tree 有序的 查询时间复杂度 lgN 3 int main(int argc, const char *argv[]) 4 { 5 set<int> s ; 6 int i; 7 for (i = 0; i < 20; i++) 8 { 9 s.insert(i);10 s.insert(i);11 }12 cout << "size:" <<s.size() << endl;// 20 -->唯一性13 14 for(int i : s) // -std=c++0x15 cout << i << " " ;16 cout << endl ;17 return 0;18 }
注意:set(集合) 与map(映射) 的区别
a) 二者均使用红黑树实现;
b) key需要支持<操作(能够比较,对于整个结构体而言,则无法比较);
c) map侧重于key-value的快速查找;
d) set侧重于查看元素是否存在。
共同点:map和set中的元素无法排序。由于其具有二叉排序性质,故不能排序。
C++学习STL之关联容器 --- pair、map、set