关联容器知识点通关

1.关联容器与顺序容器的区分

顺序容器，顾名思义就是其存储时是按照“位置顺序”来进行存储的，这里的顺序的含义就是我们常常理解的编号。以我们常用的vector和string为例，其每个元素都是按照编号来进行存储的，而且我们在顺序容器上的操作一般也是基于这些位置（编号）的遍历来实现的。与顺序容器不同的是，关联容器的设计原因就是为了实现“高效按值访问”，所以关联容器的数据存储核心一般都是“关键字”。关联二字的应有之义就是关键字和值建立关联关系。

另外，对于顺序容器而言，其底层存储结构是数组或者链表这种线性数据结构，而关联容器一般是由红黑树、哈希表等来实现的。所以顺序容器一般是基于位置处理，关联容器是基于关键字进行处理。

我们不能简单的将顺序顺序和关联容器的区分理解为是否有序；关联容器并不代表就是无序的，基于红黑树实现的关联容器都是有序的，只有基于哈希表实现的unordered_map和unordered_set才是无序的。

2.关联容器的数据

2.1 数据存储

2.1.1 pair类型

关联容器的数据存储一般是采用键值对的形式。也就是我们常常见到的key-value；我们在第一部分提到过，关联容器的访问是根据key值进行访问的，关联二字的含义也是key与value建立的关联关系。所以很有必要以一种数据类型来表达这个键值对。C++中提供了标准库类型pair来表示一对数据，它定义于头文件utility中。对于一个pair数据来说，有以下几种方式进行定义。

	pair<string,string> anon;
	pair<string,int> p("hello",1);
	pair<int,string> p1 = {1,"world"};
	make_pair("hello","world");

我们可以使用first和second来访问其键和值两个数据成员。

	cout<<p.first;	//输出hello
	cout<<p.second;	//输出1

2.1.2 关联容器的类型别名

在使用关联容器时，除了可以使用根前面的顺序容器相同的一些类型别名之外（如iterator,size_type,value_type,reference），还有一些自己特殊的类型别名总结如下：

2.1.3 关联容器迭代器

关联容器的迭代器使用与顺序容器的迭代器使用是相同的。但是对于解引用之后的操作要看其是否是一个pair类型，如果是map的话，对迭代器解引用就是一个pair，需要使用first和second来进行键值访问。

对于set和map而言，如果用迭代器进行访问的话，是不能通过迭代器来进行修改key值的。我们可以理解为：对于set，迭代器必然是const_iterator；对于map，虽然迭代器可能为简单的iterator，但是还是不能通过迭代器修改关键字成员的值。

2.2 关联容器的初始化

不能说与顺序容器的十分相似，只能说初始化一模一样。

3. 关联容器的增删改查

对于增删改查来说，方法还是那么些方法。只是在使用时可能要根据set和map的特性注意一下。下面只介绍特殊性。

3.1 关联容器增加元素

基于关联容器的特性，肯定是不能使用push_back和push_front这种方法。但是，关联容器的添加元素还是一样可是使用普通的insert方法和emplace方法。使用方法类似。

	//定义一个保存数据的vector
	vector<int> ivec = {2, 4, 6, 7, 2, 4, 6, 7};
    map<string,size_t> wordCount;
    set<int> s;
    // 给set插入元素
    //使用范围迭代器插入
    s.insert(ivec.cbegin(),ivec.cend());
    // 给map插入元素
    wordCount.insert({"wow",1});

使用虽然相同，但是在进行数据插入时，我们要区分好关联容器是否允许元素重复。对于set等不允许重复关键字的关联容器而言，如果插入一个已有的键，那么就会直接忽略这个操作。而对于multiset等允许重复的关联容器而言，就会继续执行插入。

除了使用上面的函数进行元素添加，我们通常更习惯使用下标来添加元素，示例如下：

	//当从输入流输入一个string，就建立一个以此string为关键字的元素
	while(cin>>word){
        ++word_count[word];
    }

3.2 删除关联容器的元素

同前面一样，由于使用的是根据关键字访问，所以pop_back、pop_back方法是不能再使用的。我们使用erase方法来进行关联容器的数据删除。此时的erase特性如下

 map<int,string> ma = {{1,"hello"},{2,"world"},
        {3,"nihao"},{4,"shijie"}
    };
    //删除关键字为2的值，返回值为删除元素的数量
    cout<<"删除的元素个数为："<<ma.erase(2)<<endl;

3.3 修改map的元素

关联容器的键不能修改，但是其值却是可以修改的，虽然关联容器某种程度上而言并不是根据位置序号访问，但它可以用特殊的下标——键进行访问元素。使用形式与顺序容器一样，可以通过at函数或者[]来实现。

	//访问map的元素
    cout<<"ma[1] is :"<<ma[1]<<endl;
    cout<<"ma[1] is :"<<ma.at(1)<<endl;
    //map的下标运算符获得的对象与解引用map迭代器后的对象是不同的
    //是一个mapped_type
    auto m =ma[1];

使用map的下标操作还可以进行元素的添加，如果使用一个不在容器中的关键字作为下标，就会添加一个具有此关键字的元素到map中。这也就造成在顺序容器和关联容器使用下标访问时返回值是不一样的，前者是元素类型本身，后者则是一个对应的mapped_value.

3.3 查找关联容器的元素

在关联容器中使用的查找元素的方法一般有以下两种

4. 关联容器使用示例

下面的例子是基于C++primer第五版中的单词转换程序的实现。

#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<stdexcept>
using std::ifstream;using std::endl;
using std::cout;using std::cin;
using std::string;using std::map;
using std::runtime_error;
using std::istringstream;

//根据映射文件建立单词映射map
map<string,string> buildMap(ifstream& mapfile){
    map<string,string> w_map;
    string key;
    string value;
    //注意getline的读取包含空格
    while(mapfile>>key && getline(mapfile,value)){
        if(value.size()<1){
            throw runtime_error("no similiar rule\n");
        }
        //  w_map[key] = value.substr(1);
        w_map.insert({key,value.substr(1)});
    }
    return w_map;
}
//单个单词的转换
const string &transform(const string &s,const map<string,string> &m){
    auto mp = m.find(s);
    //若存在映射则转换
    // 否则输出本身
    if(mp != m.end()){
        return mp->second;
    }
    else return s;
}
// 读取文件并转换
void wordTransform(ifstream& mapFile,ifstream& input){
    map<string,string> w_map = buildMap(mapFile);
    //保存输入的一行
    string text;
    while(getline(input,text)){
        istringstream strin(text);
        string word;
        //第一个单词的话前面没有空格
        bool first = true;
        while(strin>>word){
            if(first){
                first =false;
            }else cout<<" ";
            cout<<transform(word,w_map);    
        }
        cout<<endl;
    }
}

int main(){
    ifstream mapfile("./STL_associative/rule.txt");
    if(!mapfile){
        throw runtime_error("no rules file");
    }
    ifstream input("./STL_associative/tran.txt");
    if(!input){
        throw runtime_error("no trans file");
    }
    wordTransform(mapfile,input);
    return 0;
}