首页 > 代码库 > 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