11-关联容器

秒速五厘米 2022-06-08 10:54 192阅读 0赞

#### 关联容器 ####

1.  顺序容器是按照容器里面元素的位置来进行保存和访问的;关联容器是按照容器里面的关键字来保存和进行访问的;
2.  关联容器的类型:  
    ![这里写图片描述][SouthEast]
3.  关联容器支持高效的关键字查找和访问,两个主要的关联容器是`map`和`set`;
    
     *  `map`:表示的是`key-value`关键字-值对,关键字起到索引的作用,值用来表示和索引相关的数据;电子词典是使用`map`;
     *  `set` 中每个元素质保含一个关键字,`set`支持高效的关键字查询操作;
     *  标准库提供了8个关联容器的区别有以下三点:  
        
        
         *  1.容器要不是一个`set`,要不是一个`map`;
         *  2.容器要不要求不重复的关键字,要不允许重复的关键字;
         *  3.元素按照顺序进行保存或者不按照顺序进行保存;
         *  允许重复的关键字里面包含`multi`;关键字不按照顺序存储的包含`unordered`,无序容器使用`hash`函数来组织容器;
     *  关联容器的迭代器都是双向的;
     *  当定义一个`map`时,必须既指明关键字类型,有需要指明值类型,但是在定义`set`时,只需要声明关键字类型;
     *  每个关联容器都定义了一个默认的构造函数,它创建一个制定类型的空容器;
     *  对于关联容器进行值初始化;
     *  对于`map`和`set`来说关键字要求必须是唯一的,当关键字不唯一时,可以使用`multimap`和`multiset`;
     *  关键字对于类型的要求:
        
         *  对于有序容器`map`,`multimap`,`set`以及`multiset`来说,关键字类型必须定义关键字的比较方法,默认情况下标准库使用`<`运算符来比较;
         *  在集合类型里面关键字类型就是元素类型,在映射类型中,关键字类型是元素的第一部分类型;
         *  传递给排序算法的可调用对象必须满足与关联容器中关键字一样的要求;
         *  对于自己提供的满足严格弱序的几个规则:  
            
            
             *  两个关键字不能够同时小于对方;
             *  `<`,`>`,`==`运算符应该具有传递性;
             *  也就是说上述的规则应该满足比较运算符的基本特性;
         *  需要注意的是当使用`decltype`来指出自定义的操作类型时,必须加上一个`*`来指出我们要使用一个给定函数类型的指针;  
            
            
                bool compareIsbn(const Sales_data &Ihs,const Sales_data &rhs){
                    return lhs.isbn() < rhs.isbn();
                }
                multiset<Sales_data,decltype(compareIsbn)*>
                    bookstore(compareIsbn);
     *  `pair`类型
        
         *  定义在标准库`utility` 里面,是一个用来生成指定类型的模板,`pair`可以保存两个数据成员,必需提供两个类型名,对于两个类型名没有要求一样;
         *  `pair`支持的操作:  
            ![这里写图片描述][SouthEast 1]
         *  `pair`的数据成员是`public`,可以使用`.`运算符来访问;
         *  如果函数需要返回`pair`对象:
            
                pair<string,int>
                process(vector<string> &v){
                    if(!v.empty())
                        return (v.back(),v.back().size());
                    else
                        return pair<string,int>();  //隐式的构造返回值;
                }
         *  上面的例子就是一个返回`pair`类型的例子,如果需要生成一个`pair`对象,可以使用`make_pair`对象;
     *  关联容器的操作:
        
         *  关联容器额外的类型别名:  
            
            
             *  `key_type`:此容器类型的关键字类型;
             *  `mapped_type`:每个关键字关联的类型,只适用于`map`;
             *  `value_type`:对于`set`,和`key_type`相同,对于`map`,为`pair<const key_type,mapped_type>`;
         *  关联容器迭代器:  
            
            
             *  如果解引用一个关联迭代器时,就会得到一个类型为容器的`value_type`的值的引用;
             *  `set`的迭代器是`const`类型的,不允许进行修改,`map`类型元素里面的关键字也一样也是不允许修改的;
             *  `map`和`set`类型都支持`begin()`和`end()`操作,可以使用迭代器来遍历容器;
             *  不能将关联容器传递给修改或者重排容器元素的算法,通常来说`set`类型中的元素是`const`的,`map`中的元素是`pair`,第一个元素的类型是`const`;
             *  关联容器可用于只读元素的算法,在实际过程中,不建议对关联容器使用泛型算法;
             *  对于`set` 来说,插入重复的元素没有任何的影响,`set`的插入支持两种类型,一种是迭代器,另一种是初始化列表;
             *  向`map`里面添加元素:元素类型必须是`pair`类型,如果没有`pair`类型,需要在`insert`的参数列表中创建`pair`;
             *  常用的四中类型:  
                `word_count.insert((word,1)); word_count.insert(make_pair(word,1)); word_count.insert(pair<string,size_t>(word,1)); word_count.insert(map<string,size_t>::value_type(word,1));`
             *  `insert`的返回值依赖于容器的类型和参数,对于`map`不允许包含重复元素时,返回值类型是`pair`类型,`first`成员表示的是一个迭代器,指向给  
                定的关键字;`second`表示一个`bool`值,如果关键字位于容器里面,将`bool`值改为`false`,然后什么也不做,否则`bool`值为`true`,并且将元素插入;
         *  如果需要添加具有重复元素的映射,就需要使用`multiset`或者`multimap`,因为允许重复值,所以不需要检测锁插入的值是否已经存在;
         *  对于允许重复关键字的容器,接受但个元素的`insert`操作,返回一个指向新元素的迭代器;
         *  对于删除元素来说,提供了三个版本的`erase`操作,  
            
            
             *  1.可以传递给`erase`一个迭代器来进行删除操作,返回值为`void`;
             *  2.可以传递给`erase`一个迭代器范围来进行删除操作,返回值为`void`;
             *  3.同样的还可以传递给关联容器一个`key_type`参数,这个函数返回实际删除元素的数量;
         *  分析一个下标插入的过程:
            
                map<string,size_t> word_count;
                word_count["Anna"] = 1;
         *  上述代码执行的操作:
         *  1.在`word_count`中搜索关键字为`Anna`的元素,未找到;
         *  2.将一个新的`key-value`对插入到`word_count`中,关键字是一个`const string`保存`Anna`,进行值初始化;
         *  3.提取出新插入的元素,并将`1`赋予它;
         *  对已`map`使用下表操作和对于数组或者`vector`使用下标很不一样,`map`中如果没有这个下标,就会添加一个新的元素到`map`里面;
         *  如果使用`.at()`回进行参数检查,如果不在`map`里面,会抛出一个`out_of_range`的异常;
         *  通常情况下,解引用一个迭代器所返回的类型与下表运算符返回类型是一样的;
         *  对于`map`来说,当对一个`map`进行下标操作时,会获得一个`mapped_type`对象,但是当解引用一个`map`迭代器时,会的到一个`value_type`对象;
         *  对于元素的访问查找使用`find()`,计数使用`count()`;
         *  下标和`.at()`只适用于非`const`的`map`和`unordered_map`操作;
         *  因为使用下标在访问时,如果元素不存在,就会添加新的元素进去,所以如果仅仅需要进行查找,建议使用`find`;
         *  如果在`multimap`或者`multiset`里面存在多个元素具有给定的关键字,那么这些元素会在容器里面相邻存储;
         *  在遍历一个`multimap`或者`multiset`时,保证可以得到序列中所有具有给定关键字的元素;
         *  对于`lower_bound`和`upper_bound`来说,如果查找的关键字不存在,那么就返回一个不影响排序的关键字位置;
         *  `euqal_range`:不必调用`upper_bound`以及`lower_bound`,直接调用`equal_range`就可以用来查询符合搜索关键字的范围;
            
                for(auto pos = authors.equal_range(search_item);pos.first != pos.second;++pos.first)
                    cout << pos.first->second << endl;
         *  照抄书上面的关于单词转换的函数:
            
                map<string,string> uildMap(ifstream &map_file){
                    map<string,string> trans_map;
                    string key;
                    string value;
                
                    while(map_file >> key && getline(map_file,value))
                        if(value.size() > 1 )
                            trans_map[key] = value.substr(1);
                        else
                            throw runtime_error("no rule for" + key);
                            return trans_map;
                    }
                void word_transfrom(ifstream &map_file, ifstream &input){
                    auto trans_map = buildMap(map_file);
                    string test;
                    while(getline(intpu,text)){
                        istringstream stream(text);
                        string word;
                        bool firstword = true;
                        while(stream >> word){
                            if(firstword)
                                firstword = false;
                            else
                                cout << " ";
                            cout << transform(word,trans_map);
                        }
                        cout << endl;
                    }
                }
                const string &
                transform(const string &s,const map<string,string> &m){
                    auto map_it = m.find(s);
                    if(map_it != m.cend())
                        return map_it->second;
                    else
                        return s;
                }
     *  无序容器
        
         *  无序容器不使用比较运算符来组织元素,而是使用`hash function`和关键字类型的`==`运算符来构建函数;
         *  如果关键字类型没有明显的有序关系,使用无序容器是很有必要的;
         *  对于无序容器,关键字重复元素不一定是按照相邻顺序进行存储的;
         *  关于桶
            
             *  无序容器使用一个哈希函数将所有的元素映射到不同哈希值的痛里面;
             *  容器将具有一个特定哈希值的元素保留在相同的桶里面;
             *  如果具有重复值,那么会将具有相同关键字的元素保存在同一个桶里面;
             *  无序容器的性能十分依赖于哈希函数的质量和桶的数量和大小;
             *  无序容器对于关键字类型的要求:内置类型,`string`类型,或者智能指针类型;
             *  不能够直接定义关键字类型为自定义类类型的无序容器,不能够直接使用哈希函数模板,而是需要自己提供哈希函数模板;
            
                size_t hasher(const Sales_data &sd){
                    return hash<string>() (sd.isn());
                }
                bool eqOp(const Sales_data &lhs,Sales_data &rhs){
                    return lhs.isbn() == rhs.isbn();
                }

[SouthEast]: /images/20220608/98a7b3591f1a4f31bdc9c4786e7d8c81.png
[SouthEast 1]: /images/20220608/ff38bbc1b7ce4b2daea08d74f3bcdd66.png