首页 > 代码库 > 0717-----C++Primer听课笔记----------STL之关联容器

0717-----C++Primer听课笔记----------STL之关联容器

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;}

图像 6

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;}

图像 1

2.2 map中key的值是唯一的set中的元素都是唯一的。