1.Map
1.1 map<K, V>是一种pair的容器，pair的种类是pair<K, V>。map采用下标访问一个已存在的key， 会更新value，访问map中不存在的元素时，会增加一个新的键值对。map中的元素按照key进行从小到大排列。map的底层实现是采用二叉树，一般是使用红黑树。
#include <iostream> #include <string> #include <map> using namespace std; /* * map 是 pair的容器 * map 可以直接用迭代器访问 * map 中的元素按照key 从小到大排列 */ int main(int argc, const char *argv[]) { map<string, int> m; m["beijing"] = 33; m["shanghai"] = 34; m["guangzhou"] = 35; m["shenzhen"] = 36; for(map<string, int>::iterator it = m.begin(); it != m.end(); ++it){ cout << it->first << " " << it->second << endl; } m["beijing"] = 50; //更新 value m["chongqing"] = 40; //增加一个新的键值对 cout << "---------------" << endl; for(map<string, int>::iterator it = m.begin(); it != m.end(); ++it){ cout << it->first << " " << it->second << endl; } return 0; }
1.2 map对容器的要求：key类型必须支持<比较，而value不做要求。map的key 值是不可更改的。如下例，将报错。
#include <iostream> #include <string> #include <map> using namespace std; /* * map 要求 key的类型必须支持 < 比较 * 这里的animal没有提供比较规则， 所以不能作为map的key */ class Animal{ }; int main(int argc, const char *argv[]) { map<Animal, int> m; Animal a1; m[a1] = 10; return 0; }
1.3 insert 插入一个已存在的key ，将会插入失败。insert 返回一个pair类型 第一个是指向插入元素的迭代器（若若元素已存在，则指向存在的那个键值对，否则指向新插入的那个键值对。）第二个是一个bool值，表示插入是否成功。
#include <iostream> #include <string> #include <utility> #include <map> using namespace std; /* * insert */ int main(int argc, const char *argv[]) { map<string, int> m; m["beijing"] = 33; m["tianjin"] = 34; m["shenzhen"] = 30; m["longhua"] = 40; pair<map<string, int>::iterator, bool> ret; //insert 的返回值类型 ret = m.insert(make_pair("beijing", 8)); if(ret.second == false){ cout << "Insert Failed " <<endl; } ret = m.insert(make_pair("chongqing", 44)); if(ret.second == true){ cout << "Insert Success " << endl; } for(map<string, int>::iterator it = m.begin(); it != m.end(); ++it){ cout << it->first << " : " << it->second << endl; } return 0; }
1.4 统计单词个数
1.4.1 方法一，直接用map下标。这里的 words[word]++; 如果word是一个不存在的值，那么首先在map中添加一个键值对，为(word, 0)，然后对value执行+1操作。因此不管是否存在 ，该语句均可；
#include <iostream> #include <string> #include <map> #include <utility> using namespace std; int main(int argc, const char *argv[]) { map<string, int> words; string wd; while(cin >> wd){ words[wd]++; } for(map<string, int>::iterator it = words.begin(); it != words.end(); ++it){ cout << it->first << " : " << it->second << endl; } return 0; }
1.4.2 方法二，每次都生成一个pair 对象，然后insert。
#include <iostream> #include <string> #include <map> #include <utility> using namespace std; int main(int argc, const char *argv[]) { map<string, int> words; string wd; pair<map<string, int>, bool> ret; while(cin >> wd){ ret = words.insert(make_pair(wd, 1)); if(ret.second == false){ // 插入失败说明该单词已存在，次数加1即可 ret.first->second ++; } } for(map<string, int>::iterator it = words.begin(); it != words.end(); ++it){ cout << it->first << " : " << it->second << endl; } return 0; }
1.4.3 升级版 统计词频，本地保存一个停用词文件，表示不需要统计的词汇，注意要用类实现。
#ifndef __WORDS_CNT_H__ #define __WORDS_CNT_H__ #include <string> #include <map> #include <set> class WordsCnt{ public: WordsCnt(const std::string &filename); void add(const std::string &word); void print()const; private: std::map<std::string, int> words_; std::set<std::string> exclude_; }; #endif #include "words_cnt.h" #include <iostream> using namespace std; int main(int argc, const char *argv[]) { string filename("a.txt"); WordsCnt w(filename); string wd; while(cin >> wd){ w.add(wd); } w.print(); return 0; } #include "words_cnt.h" #include <iostream> #include <string> #include <map> #include <set> #include <fstream> using namespace std; WordsCnt::WordsCnt(const string &filename){ ifstream is; string word; is.open(filename.c_str()); while(is >> word){ exclude_.insert(word); } is.close(); } void WordsCnt::add(const string &word){ if(exclude_.count(word) == 0){ words_[word]++; } } void WordsCnt::print()const{ for(map<string, int>::const_iterator it = words_.begin(); it != words_.end(); ++it){ cout << it->first << " : " << it->second << endl; } }
2.Set集合
2.1 set底层采用红黑树实现，按照值进行排序。
#include <iostream> #include <string> #include <set> using namespace std; int main(int argc, const char *argv[]) { set<int> s; s.insert(99); s.insert(9); s.insert(29); s.insert(49); s.insert(1); s.insert(103); cout << "size " << s.size() << endl; for(set<int>::iterator it = s.begin(); it != s.end(); ++it){ cout << *it << endl; } return 0; }
2.2 map中key的值是唯一的，set中的元素都是唯一的。