C++中的关联容器与无序关联容器

我就是我 2023-10-06 08:30 43阅读 0赞

## C++中的关联容器与无序关联容器 ##

#### 目录 ####

*  C++中的关联容器与无序关联容器
 *   *  关联容器：
     *   *  set与multiset:
         *  map与multimap:
     *  无序关联容器:
     *   *  unordered\_set、unordered\_multiset、unordered\_map、unordered\_multimap:

### 关联容器： ###

关联容器将值与键关联在一起，并用键来查找值  
关联容器通常是使用某种树实现的  
STL提供了4中关联容器：set、multiset、map、multimap  
前两种在头文件< set >中定义，后两种在头文件< map >中定义

#### set与multiset: ####

set的值类型与键相同，键是惟一的，集合中不会存在多个相同的键，因此，对于set来说，值就是键

set是关联集合，可反转，可排序，且键是唯一的，所以不能存储多个相同的值

multiset与set类似，只是可能有多个值的键相同，例如，若键和值的类型为int，则multiset对象包含的内容可以为 1,2，2,2，3,5，5,7。而set对象包含的内容可为1,2,3,5,7

**set使用模板参数指定要存储的值类型：**

set<string> A;  // a set of string object

**set的初始化：**  
1.调用insert方法

set<int> s;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        
    	int x;
        cin>>x;
        s.insert (x);
    }

2.使用以迭代器区间作为参数的构造函数

const int N=6;
    string s1[N]={
        "buffer","thinkers","for","heavy","can","for"};
    set<string> A(s1,s1+N);

**两个有用的set方法：**  
lower\_bound(): 将键作为参数并返回一个迭代器，该迭代器指向集合中第一个第一个不小于键参数的成员  
upper\_bound(): 将键作为参数并返回一个迭代器，该迭代器指向集合中第一个第一个大于键参数的成员

set<int> s;
    s.insert(1);
    s.insert(3);
    s.insert(4);
    cout<<*s.lower_bound(2)<<endl;	//打印出3
    cout<<*s.lower_bound(3)<<endl;	//打印出3
    cout<<*s.upper_bound(3)<<endl;	//打印出4

**set中常用方法：**

begin()     　　 返回指向set容器的第一个元素的迭代器
    
    end() 　　　　 返回set容器的超尾迭代器
    
    clear()   　　     删除set容器中的所有的元素
    
    empty() 　　　判断set容器是否为空
    
    max_size() 　 返回set容器可能包含的元素最大个数
    
    size() 　　　　 返回当前set容器中的元素个数
    
    rbegin　　　　 返回的值和end()相同
    
    rend()　　　　 返回的值和begin()相同

**其他set中的方法:**  
**count()：**  
用来查找set中某个键值出现的次数。由于一个键值在set中只可能出现0或1次，这样count()方法的作用就变成了判断某一键值是否在set出现过。

**erase():**  
erase(iterator) 删除迭代器iterator指向的值

erase(first,second) 删除迭代器first和second之间的值（左闭右开，\[first,second) ）

erase(key\_value) 删除键值为key\_value的值

**find() ：**  
返回指示给定值的迭代器，如果没找到则返回end()

**insert():**  
insert(key\_value) ：  
将key\_value插入到set中 ，返回值是pair<set::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key\_value已经在set中，则iterator表示的是key\_value在set中的位置。

inset(first,second)：  
将迭代器first到second之间的元素插入到set中，返回值是void.

#### map与multimap: ####

在map中，值与键的类型不同，键是惟一的，每个键只对应一个值。multimap与map类似，只是一个键可与多个值相关联

**map的声明：**  
使用模板参数指定键的类型和存储的值的类型：

map<int,string> codes;

**数据的插入：**  
为将信息结合在一起，实际的值类型将键类型和数据类型结合为一对。STL使用模板类pair<class T,class U>将这两种值存储到一个对象中，  
即 pair< const keytype,datatype >  
**1.用insert方法插入pair数据：**

**2.用数组方式插入数据：**

map<int, string> mapStudent;  
    mapStudent[1] = "student_one";  
    mapStudent[2] = "student_two";  
    mapStudent[3] = "student_three";

用insert方法插入数据，在数据的插入上涉及到集合的唯一性，即当map中有这个关键字时，insert操作是插入数据不了的，即插入不成功。但是用数组方式可以覆盖以前该关键字对应的值

**map中的常用方法：**

size()
    erase()
    clear()
    upper_bound()
    lower_bound()
    swap()			两个容器所有元素进行交换
    insert()

**map中数据的遍历：**  
**1.利用迭代器：**

for(iter = mapStudent.begin();iter!=mapStudent.end(); iter++)  
    	cout<<iter->first<<' '<<iter->second<<endl;

**2.利用数组形式：**

map<int, string> mapStudent;  
    mapStudent.insert(pair<int, string>(1,"student_one"));  
    mapStudent.insert(pair<int, string>(2, "student_two"));  
    mapStudent.insert(pair<int, string>(3, "student_three"));  
    int nSize = mapStudent.size();
    for(int nindex = 1; nindex <= nSize; nindex++)
     	cout<<mapStudent[nindex]<<endl;

**查找并获取map中的元素：**  
**1.count()方法：**  
能判断关键字是否出现，但无法定位数据出现的位置，与set类似，一对一的映射关系，决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，返回1  
**2.find()方法：**  
返回迭代器

### 无序关联容器: ###

#### unordered\_set、unordered\_multiset、unordered\_map、unordered\_multimap: ####

无序关联容器使用键和哈希表。若键为string对象，哈希函数可能将其中每个字符的数字编码相加，再将计算结果除以13的余数，从而得到一个0~12的索引。无序容器将使用13个桶(bucket)来存储string，例如所有索引为4的string都将存储在第四个桶中。若要在容器中搜索键，将对键执行哈希函数，进而只在索引对应的桶中搜索。

它们的操作及方法与关联容器类似

由于unordered\_map里面的元素是以pair类型来存贮的，因此键与值的类型可以相同