三、map
1.map特点
(1) map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
(2)在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:
typedef pair<const Key, T> value_type;
(3) 在内部,map中的元素总是按照键值key进行比较排序的。
(4) map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。
(5) map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
(6)map通常被实现为平衡二叉搜索树(红黑树)。
2.map类
(1)map类的构造
1. template < class Key, // map::key_type,Key的类型 2. class T, // map::mapped_type,value的类型 3. class Compare = less<Key>, // map::key_compare,比较器类型,默认小于,自定义类型需写函数指针或仿函数 4. class Alloc = allocator<pair<const Key,T> > // map::allocator_type 空间配置器 5. > class map; 6. 7. //构造map 8. explicit map (const key_compare& comp = key_compare(), 9. const allocator_type& alloc = allocator_type()); 10. 11. 使用迭代器区间构造map 12. template <class InputIterator> 13. map (InputIterator first, InputIterator last, 14. const key_compare& comp = key_compare(), 15. const allocator_type& alloc = allocator_type()); 16. 17. //拷贝构造map 18. map (const map& x);
创建map对象:
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<iostream> 3. #include<map> 4. using namespace std; 5. 6. int main() 7. { 8. map<string, int> m;//创建一个map对象m 9. //向m中插入pair 10. 11. map<string, int> m1(m.begin(), m.end);//用m的区间构造m1 12. map<string, int> m2(m1);//用m1拷贝构造m2 13. 14. return 0; 15. }
(2)插入insert( )
1. pair<iterator,bool> insert (const value_type& val);//当val的first已存在时返回值pair的second为false,否则返回pair的second为true 2. 3. iterator insert (iterator position, const value_type& val);//在map的指定位置插入pair 4. 5. template <class InputIterator> 6. void insert (InputIterator first, InputIterator last);//在map中插入一段迭代器区间
①插入pair,由于此时map中没有足球,因此pair的second为true:
1. bool b = m.insert(pair<string, int>("足球", 2)).second; 2. cout << b << endl; 3. 4. m.insert (pair<string, int>("篮球", 6)); 5. m.insert (pair<string, int>("羽毛球", 3)); 6. m.insert (pair<string, int>("排球", 1));
make_pair对pair进行了包装,构造了pair对象:
1. template <class T1,class T2> 2. pair<T1,T2> make_pair (T1 x, T2 y) 3. { 4. return ( pair<T1,T2>(x,y) ); 5. }
因此,在项目中,不展开命名空间时,都要指定std,make_pair要比pair写起来更简洁一些,对比以下两种写法:
1. m.insert(std::pair<std::string, int>("网球", 7)); 2. m.insert(std::make_pair("网球", 7));
明显make_pair的写法更简洁。
②在map的指定位置插入pair
1. map<string, int> m; 2. //向m中插入pair 3. m.insert (pair<string, int>("足球", 2)); 4. m.insert (pair<string, int>("篮球", 6)); 5. m.insert (pair<string, int>("羽毛球", 3)); 6. m.insert (pair<string, int>("排球", 1)); 7. 8. //在m开始插入乒乓球 9. map<string, int>:: iterator it = m.begin(); 10. m.insert(it, pair<string, int>("乒乓球",5));
监视:
③在map中插入一段迭代器区间
向m1中插入m从第二个位置开始到结束位置的区间:
1. map<string, int> m1; 2. m1.insert(++m.begin(), m.end());
监视:
这里少了篮球,说明m的第一个pair是<"篮球",6>。
(3)map遍历
auto在变量被定义并初始化之后编译器才能根据初始化表达式来推导auto的实际类型,所以在定义map对象时,不能使用auto关键字,在变量被定义并初始化之后可以使用auto关键字:
1. map<string, int> m; 2. 3. m.insert(pair<string, int>("足球", 2)); 4. m.insert(pair<string, int>("篮球", 6)); 5. m.insert(pair<string, int>("羽毛球", 3)); 6. m.insert(pair<string, int>("排球", 1)); 7. m.insert(make_pair("网球", 7)); 8. 9. //map<string, int>::iterator mit = m.begin(); 10. auto mit = m.begin();//同map<string, int>::iterator mit = m.begin(); 11. while (mit != m.end()) 12. { 13. cout << mit->first << ":" << mit->second<< endl; 14. mit++; 15. } 16. cout << endl;
map本身有两个模板参数,会导致有些类型比较长,项目中可以用typedef简化命名:
1. typedef std::map<std::string, int> MAP;//简化map命名 2. typedef std::pair<std::string, int> MAP_KV;//简化pair命名 3. typedef std::map<std::string, int>::iterator MAP_IT;//简化迭代器命名 4. 5. MAP m; 6. m.insert(MAP_KV("足球", 2)); 7. m.insert(MAP_KV("篮球", 6)); 8. m.insert(MAP_KV("羽毛球", 3)); 9. m.insert(MAP_KV("排球", 1)); 10. m.insert(MAP_KV("网球", 7)); 11. 12. MAP_IT mit = m.begin(); 13. while (mit != m.end()) 14. { 15. std::cout << mit->first << ":" << mit->second << std::endl; 16. mit++; 17. } 18. std::cout << std::endl;
同set一样,map的key不允许修改
1. typedef std::map<std::string, std::string> MAP;//简化map命名 2. typedef std::pair<std::string, std::string> MAP_KV;//简化pair命名 3. typedef std::map<std::string, std::string>::iterator MAP_IT;//简化迭代器命名 4. 5. MAP m; 6. m.insert(MAP_KV("spring", "春天")); 7. m.insert(MAP_KV("summer", "夏天")); 8. m.insert(MAP_KV("autumn", "秋天")); 9. m.insert(MAP_KV("winter", "冬天")); 10. 11. MAP_IT mit = m.begin(); 12. while (mit != m.end()) 13. { 14. mit->first = "night";//修改key为night,报错 15. mit++; 16. } 17. std::cout << std::endl;
报错:
但是map的value可以修改:
先给中文翻译加上{ }
1. MAP_IT mit = m.begin(); 2. while (mit != m.end()) 3. { 4. mit->second.insert(0, "{"); 5. mit->second += "}"; 6. std::cout << mit->first << ":" << mit->second << std::endl; 7. mit++; 8. } 9. std::cout << std::endl;
再给spring的中文翻译加上其他释义:
1. auto ret = m.find("spring"); 2. 3. mit = m.begin(); 4. if(ret != m.end()) 5. { 6. std::string& str = ret->second;//用str作为ret->second的别名,因此控制的就是ret的second 7. str.insert(str.size() - 1, "、温泉"); 8. } 9. 10. while (mit != m.end()) 11. { 12. std::cout << mit->first << ":" << mit->second << std::endl; 13. mit++; 14. } 15. std::cout << std::endl;
map也可以用来统计次数,比如找出大家最喜欢的球类,统计技术有3种方式:
第一种方式:找到就增加次数,否则就插入
1. //1.统计次数 2. string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球","足球","排球","羽毛球","篮球","足球" }; 3. map<string, int> countMap; 4. for (const auto& str : arr) 5. { 6. map<string, int>::iterator ret = countMap.find(str); 7. if (ret != countMap.end())//找到了,只增加次数 8. { 9. ret->second++; 10. } 11. else//没找到就插入 12. { 13. countMap.insert(make_pair(str, 1)); 14. } 15. } 16. 17. //2.找出大家最喜欢的球类 18. for (const auto& e : countMap) 19. { 20. cout << e.first << ":" << e.second << endl; 21. }
第二种方式:由于insert的返回值类型为pair<iterator, bool>,pair中的第二个值类型为bool,向map中插入时,如果map中已经有了,pair返回的第一个值为插入值所在节点的迭代器,第二个值就为false,否则pair返回的第一个值为插入值所在节点的迭代器,第二个值就为true。
pair<iterator,bool> insert (const value_type& val);
因此第二种方式根据插入的返回值pair的第二个值判断为true还是false,决定返回的pair的第一个值即迭代器的第二个值是否++:
1. string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球","足球","排球","羽毛球","篮球","足球" }; 2. map<string, int> countMap; 3. 4. //先插入,如果str已经在map中,insert会返回str所在节点的迭代器,++次数即可 5. for (const auto& str : arr) 6. { 7. //pair<map<string,int>::iterator,bool> ret = countMap.insert(make_pair(str, 1));//可用auto推导 8. auto ret = countMap.insert(make_pair(str, 1)); 9. if (ret.second == false) 10. { 11. ret.first->second++; 12. } 13. } 14. 15. for (const auto& e : countMap) 16. { 17. cout << e.first << ":" << e.second << endl; 18. }