STL三

map

find和count

用来查找

1
2
3
4
5
6
map<int,string>::iterator it = m.find(key);
if(it != m.end()){
    cout << it.first <<", "<< it.second;
}

m.count(key);

和set基本一致 ，只是要注意，find的返回值是一个pair类型

insert

与set基本相同，也可以进行插入一个元素或一个迭代器范围的，或者大括号范围的元素，与set的insert的不同之处是，待插入元素value_type是一个pair类型
返回值是一个pair<map<value_type,value_type>::iterator,bool>类型

1
2
3
4
5
6
7
8
9
10
pair<map<value_type,value_type>::iterator,bool> ret = m.insert({key,value});

if(it.second){
    //插入成功
    //it。first也是一个迭代器类型，所以it.first.first是map的key,it.first.second是map的value
    cout << it.first.first << ":" << it.first.second << endl;
}else{
    //插入失败
}

下标操作

下标非索引，而是key值，通过key值找到相应的value值，也就是说下标具备查找的功能，如果查找的key是存在的，可以把对应的value找出来，如果key不存在，则会把一个空的value插入进去与该key对应起来,也就是下标操作具备插入功能，此外，还可以进行修改，通过key找到value是可以修改的

1
2
const map<key,value> tmp = {{k,v}};
tmp[0];//error  不允许下标访问了因为加上const关键词，就不允许修改了，而下标访问可能会修改

map存储自定义类型

1
2
3
4
5
6
7
class Point{
    ...
};

void test(){
    map<string,Point> m = {{"hello",Point(1,2)},{"world",Point(3,4)},make_pair("haha",Point(5,6)),pair<string,Point>("gigity",Point(7,8))};
}

这里自定义类型存在了value，所以初始化是没有问题的，但是如果key值存的自定义类型，那么就要像set一样提供一个排序方法

multimap

与map的区别就是key值可以是重复的

insert

与map也有区别，因为返回值类型不一样，multimap的insert的返回值是一个迭代器，而map的返回值是一个pair,因为map的key可以是重复的，所以pair的第二个bool值一定是true,所以不需要了，只保留了第一个迭代器

不支持下标操作

multimap是没有下标操作的，因为multimap的key值是可以重复的的，而下标传递的是key类型，所以可能出现二义性

总结：

1.关联式容器的底层实现是红黑树

2.关联式容器中的元素是有序的

3.关联式容器中只有map具备下标

无序关联式容器

底层实现是哈希表

哈希相关的概念

哈希函数

通过key值找到在哈希表中的位置值

1
index = H(key);

构建函数

定址法：H(key)=a*key+b
平方取中法：key^2=1234^2=1522756 —–>227
数字分析法：H(key)=key %10000;
除留取余法：H(key)=key mod p(p<=m,m为表长)

哈希冲突

不同的key值通过哈希函数映射之后，对应的位置值是一样的，这叫哈希冲突

1
H(key1) = H(key2),//并且key1 != key2

解决哈希冲突的方式

开放定址法
链地址法(推荐使用这种，这也是STL中使用的方法)
再散列法
建立公共溢出区

装载因子

装载因子 = 元素的个数/表长

如果装载因子的值比较大，那么说明空间的利用率比较高，同时冲突的概率也会比较高，如果装载因子的值比较小，那么说明空间的利用率比较低，同时冲突的概率也会比较低

unordered_set

构造函数

与set,vector类似，也有五种初始化的方法

1
2
unordered_set<int> us = {2,3,5,6,1,6,8,5,3,2};
print(us);

unordered_set存放的是key类型，key值是唯一的，不能重复
key值是没有顺序的（如存入时 的顺序也是不一样的，是通过哈希映射来确定下标的）

其他操作

查找count, find , 插入insert, 删除erase与set是完全一样的，也没有下标操作

针对于自定义类型的写法

存入自定义类型，需要自定义hash方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//模板的特化
namespace std
{
    template <>
    struct hash<Point>
    {
        size_t operator()(const Point &rhs,const Point &rhs) const
        {
            //自己设计一个哈希算法
           return (rhs.getX() << 1) ^ (rhs.getY()<<2);
        }    
    };
}//除了特化这个还需要考虑keyEqual
//模板的特化方法
namespace std{
    template <>
    struct equal_to<Point>
    {
        bool operator()(const Point &lsh,const Point &rhs)const{
            return (lhs.getX() == rhs.getX() && lhs.getY() && rhs.getY());
        }
    };
}


unordered_set<Point> number = {
    Point(1,2),
    Point(3,4),
    Point(5,6)
}

使用函数对象的方法特化哈希方法

1
2
3
4
5
6
7
//函数对象的方法
struct HashPoint
{
    size_t operator()(const Point &rhs,,const Point &rhs) const{
         return (rhs.getX() << 1) ^ (rhs.getY()<<2);
    }
};

keyEqual的其他方法

1
2
3
4
5
6
//函数对象的方法
struct EqualToPoint{
    bool operator()(const Point &rhs,,const Point &rhs) const{
        return (lhs.getX() == rhs.getX() && lhs.getY() && rhs.getY());
    }
};
1
2
3
4
//运算符的重载
bool operator==(const Point &lhs, const Point &rhs){
     return (lhs.getX() == rhs.getX() && lhs.getY() && rhs.getY());
}

模板的特化和运算符重载同时存在的情况下优先执行模板的特化

unordered_map

基本特征

与map基本一致，但是底层是用哈希表实现的，插入顺序与存储位置无关

其他操作

查找插入删除完全一样

下标操作

也是可以进行下标操作的

针对自定义类型

key存储自定义类型也需要特化Hash,KeyEqual

key存储的是string类型的话不需要特化Hash,keyEqual，因为string以及提供好了

下午练习

Q:无序关联式容器有哪些？各自具有哪些特点？

A:无序关联式容器有：

unordered_map unordered_set

unordered_set 不允许有重复值，底层用哈希表实现，所以存储的位置与插入的顺序无关，所以没有取下表操作，支持快速查找和修改操作

unordered_map 不允许出现重复的key值，value值可以重复，底层用哈希表实现，存储位置和插入的顺序无关，但这个可以取下标，支持快速查找和修改操作。

Q:使用unordered_map重写词频统计作业。再比较一下使用map和vector时所花费的时间，体会这几种容器的区别

A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <unordered_map>
#include <string>
#include <fstream>
#include <memory>
#include <sstream>
#include <algorithm>
using namespace std;

struct IFstreamDeleter{
    void operator()(ifstream *ptr){
        if(ptr){
            ptr->close();
        }
    }
};
struct OFstreamDeleter{
    void operator()(ofstream *ptr){
        if(ptr){
            ptr->close();
        }
    }
};

class StaticWord{
public:
    StaticWord(string openfilename, string writefilename)
    :_ifs(new ifstream(openfilename,ios::in),IFstreamDeleter())
    ,_ofs(new ofstream(writefilename), OFstreamDeleter())
    {
        
        static_word();
        WriteToFile();
    }
    void search(string word){
        if(_dict.find(word) != _dict.end()){
            cout << word << "出现了" << _dict[word] << "次"<<endl;
        }else{
            cout << "该单词没有出现" << endl;
        }
        
    }

private:
    void WriteToFile(){
        for(auto &e : _dict){
            *_ofs << e.first << ":" << e.second << endl;
        }
    }
    void static_word(){
        stringstream content;
        content << _ifs->rdbuf();//读入文件内容
        istringstream iss(content.str());
        string line;
        string word;
        while(getline(iss, line)){
            ToWord(line);
            istringstream w(line);
            while(w >> word){
                ++_dict[word];
            }
        }
    }
    
    void ToWord(string &str){
        for(int i = 0; i < str.size(); ++i){
            if(!isalpha(str[i])){
                str[i] = ' ';
            }else{
                str[i] = tolower(str[i]);
            }
        }
    }

private:
    unordered_map<string ,int> _dict;
    shared_ptr<ifstream> _ifs;
    shared_ptr<ofstream> _ofs;
    int _fileLength;
};



int main(int argc, char *argv[])
{
    if(argc < 3){
        cout << "请输入读入的文件名和输出的文件名" << endl;
    }
    else{
        StaticWord sw(argv[1],argv[2]);
    }
    return 0;
}

Q:使用unordered_map/map实现单词转换程序。给定一个string，将它转换为另一个string。程序的输入是两个文件，第一个文件保存的是一些规则，用来转换第二个文件中的文本。每条规则由两部分组成：一个可能出现在输入文件中的单词和一个用来替换它的短语。表达的含义是，每当第一个单词出现在输入中时，我们就将它替换为对应的短语，第二个输入文件包含要转换的文本。（C++ primer 11.3.6）

提示：

规则文件：map.txt文件，其实就是第一个单词，被后面的一串所替换。

待转换文本：file.txt文件，该文件中的单词如果出现在map.txt文件的第一个单词的话，就用map.txt的后面一串替代。

结果：最后结果其实就是，将file.txt文件中的并且出现在map.txt中第一个单词转换为map.txt后面的一串。例如：where r u的输出结果就是where are you. r替换为are，u替换为you

//file.txt
where r u
y dont u send me a pic
k thk l8r

//map.txt
brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks!
l8r later

A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <memory>
#include <fstream>
#include <sstream>
#include <iostream>
#include <map>
using namespace std;

struct FstreamDeleter{
    void operator()(fstream *ptr){
        if(ptr){
            ptr->close();
            delete ptr;
        }
    }
};
struct IFstreamDeleter{
    void operator()(ifstream *ptr){
        if(ptr){
            ptr->close();
            delete ptr;
        }
    }
};

class ReplaceWord{
public:
    ReplaceWord(string openfilename,string replaceFilename)
    :_ifs_map(new ifstream(openfilename,ios::in),IFstreamDeleter())
    ,_ifs_rep(new fstream(replaceFilename,ios::in | ios::out),FstreamDeleter())
    {
        stringstream content;
        content << _ifs_map->rdbuf();
        istringstream iss(content.str());
        string line;
        while(getline(iss,line)){
            int flag = 0;
            int num = 0;
            string key,value;
            for(int i = 0; i < line.size(); ++i){
                if(line[i] == ' '){
                    flag = 1;
                    num++;
                }
                if(num == 1){
                    num++;
                    continue;
                }
                if(flag == 0){
                    key += line[i];
                }else{
                    value +=line[i];
                }
            }
            cout << key <<":" << value << endl;
            _replace_rule[key] = value;
        }
        Replace();
    }
private:
    void Replace(){
        stringstream content;
        content << _ifs_rep->rdbuf();
        istringstream iss(content.str());
        string newContent;
        string line, word;
        while(getline(iss,line)){
            cout << line << endl;
            istringstream w(line);
            while(w >> word){
                if(_replace_rule.find(word) != _replace_rule.end()){
                    //找到了 替换
                    newContent = newContent +_replace_rule[word] +' ';
                    //cout << newContent << endl;
                }else{
                    //没找到 直接加
                    newContent = newContent + word + ' '; 
                    //cout << newContent << endl;
                }
            }
            newContent += '\n';
        }
        cout << newContent << endl;
        _ifs_rep->seekg(0,ios::beg);
        //写回数据
        _ifs_rep->write(newContent.c_str(),newContent.size());
    }

private:
    shared_ptr<ifstream> _ifs_map;
    shared_ptr<fstream> _ifs_rep;
    map<string,string> _replace_rule;
};


int main(int argc, char * argv[])
{
    if(argc < 3){
        cout<< "输入的参数不够" << endl;
    }else{
        ReplaceWord rw(argv[1], argv[2]);
    }
    return 0;
}