C++STL4种关联容器（set、multiset、map和multimap）

ゞ浴缸里的玫瑰 2022-11-21 09:44 185阅读 0赞

**关联容器将值和键关联在一起，并使用键来查找值。**  
特点：

*  可对元素进行快速访问
 *  允许插入元素，但不能指定位置。
 *  通常使用某种数来实现。

这四类容器仅仅只是在RBTree上进行了一层封装，首先，set和map的区别就在于键和值是否相同，set中将值作为键，支持STL的提供的一些交集、并集和差集等运算；map的键和值不同，每个键都有自己的值，键不能重复，但是值可以重复。multimap和multiset就在map和set的基础上，使他们的键可以重复，除此之外基本等同。

### 四种关联容器 ###

*  set-集合
 *   *  insert()的返回值
     *   *  单值插入
         *  基于范围的插入
 *  multiset
 *   *  insert()函数的返回值
 *  map-键值对
 *  multimap

# set-集合 #

set是最简单的关联容器，其值类型和键相同，键是唯一的，值在集合中不会重复出现。可反转，可以排序。

*  set以红黑树（RBTree）作为底层容器
 *  所得元素的只有key没有value，value就是key
 *  不允许出现键值重复
 *  所有的元素都会被自动排序
 *  不能通过迭代器来改变set的值，因为set的值就是键

**set常用函数：**

*  **set\_union()、set\_intersection()、set\_difference().集合的交并差**。集合set都是经过排序的，天然满足使用这三个函数的先决条件。
 *  **insert()** —因为集合是排好序的，所以插入元素时不用指定位置。
 *  **lower\_bound()** —将键作为参数并返回一个迭代器，该迭代器指向集合中第一个不小于键参数的成员。
 *  **upper\_bound()** —将键作为参数并返回一个迭代器，该迭代器指向集合中第一个大于键参数的成员。

#include <iostream>
    #include<string>
    #include<set>
    #include<algorithm>
    #include<iterator>
    #include<vector>
    using namespace std;
    
    int main(void) {
        
    	const int N = 6;
    	string s1[N] = {
         "buffoon","thinkers","for","heavy","can","for" };
    	string s2[N] = {
         "metal","any","food","elegant","deliver","for" };
    
    	//使用构造函数初始化集合，集合会自动排序。
    	set<string> A(s1, s1 + N);//buffoon can for heavy thinkers
    	set<string> B(s2, s2 + N);//any deliver elegant food for metal
    
    	ostream_iterator<string, char> out(cout, " ");
    	cout << "Set A:    " ;
    	copy(A.begin(), A.end(), out);//buffoon can for heavy thinkers
    	cout << "" << endl;
    	cout << "Set B:    ";
    	copy(B.begin(), B.end(), out);//any deliver elegant food for metal
    	cout << "" << endl;
    
    	//set_union()--求并集
    	cout << "Union of A and B:    " ;
    	set_union(A.begin(), A.end(), B.begin(), B.end(),out);
    	//any buffoon can deliver elegant food for heavy metal thinkers
    	
    	cout << "" << endl;
    	cout << "Intersection of A and B:    " ;
    	set_intersection(A.begin(), A.end(), B.begin(), B.end(), out);
    
    	cout << "" << endl;
    	cout << "Difference of A and B:    ";
    	set_difference(A.begin(), A.end(), B.begin(), B.end(), out);
    
    	set<string> C;
    	cout <<endl <<"Set C: " << endl;
    	set_union(A.begin(), A.end(), B.begin(), B.end(), insert_iterator<set<string> >(C, C.begin()));
    	copy(C.begin(), C.end(), out);
    	cout << "" << endl;
    
    	string s3("grungy");
    	C.insert(s3);
    	cout << "After insertion:" << endl;
    	copy(C.begin(), C.end(), out);
    	cout << "" << endl;
    
    	cout << "Showing a range:" << endl;
    	copy(C.lower_bound("ghost"), C.upper_bound("spook"), out);
    	cout << "" << endl;
    	return 0;
    }
    /*
    结果:
    
    Set A:    buffoon can for heavy thinkers
    Set B:    any deliver elegant food for metal
    Union of A and B:    any buffoon can deliver elegant food for heavy metal thinkers
    Intersection of A and B:    for
    Difference of A and B:    buffoon can heavy thinkers
    Set C:
    any buffoon can deliver elegant food for heavy metal thinkers
    After insertion:
    any buffoon can deliver elegant food for grungy heavy metal thinkers
    Showing a range:
    grungy heavy metal
    */

## insert()的返回值 ##

### 单值插入 ###

函数原型：

std::pair<iterator,bool> insert( const value_type& value );
    std::pair<iterator,bool> insert( value_type&& value );

**返回由指向被插入元素（或阻止插入的元素）的迭代器和若插入发生则设为 true 的 bool 值。**

#include <iostream>
    #include<string>
    #include<set>
    #include<algorithm>
    #include<iterator>
    #include<vector>
    #include<tuple>
    #include <utility>
    using namespace std;
    int main()
    {
        
    
    	set<int> s1{
         1,3,5,7,9 };
    	pair<set<int>::iterator, bool> ret = s1.insert(8);
    
    	cout << "插入8，结果："<< ret.second <<", 所返回的迭代器指向的值："<< *ret.first << endl;
    
    	cout << "打印结果：" << endl;
    	for (set<int>::iterator it= s1.begin(); it!=s1.end();it++)
    	{
        
    		cout  << *it<< ' ';
    	}
    	cout << "" << endl;
    
    	ret = s1.insert(8);
    	cout << "再次插入8，结果：" << ret.second << ", 所返回的迭代器指向的值：" << *ret.first << endl;
    
    	cout << "从ret.first开始打印结果：" << endl;
    	for (set<int>::iterator it = ret.first; it != s1.end(); it++)
    	{
        
    		cout << *it << ' ';
    	}
    	cout << "" << endl;
    	return 0;
    }
    /**
     * 结果：
    插入8，结果：1, 所返回的迭代器指向的值：8
    打印结果：
    1 3 5 7 8 9
    再次插入8，结果：0, 所返回的迭代器指向的值：8
    从ret.first开始打印结果：
    8 9
     */

单值插入时，返回的是一个pair类型的值，它里面包含了两个值：set对应的迭代器iterator(上文集合内的数据为int类型，所以迭代器类型为**set< int >::iterator**)，和插入结果（bool类型)

*  插入成功时，迭代器指向被插入元素，也就是被插入元素所在集合的位置，bool为true
 *  插入失败时，迭代器指向阻止插入动作进行的元素，也就是说插入的是重复元素，返回的是集合中已存在的，跟当前要插入元素相同的元素的迭代器。bool为false。

### 基于范围的插入 ###

函数原型：

template< class InputIt >
    void insert( InputIt first, InputIt last );//迭代器
    void insert( std::initializer_list<value_type> ilist );//初始化列表

set<int> s1{
         1,3,5,7,9 };
    	set<int> s2;
    	s2.insert(s1.begin(), s1.end());
    	for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
    	{
        
    		cout << *it << ' ';//1 3 5 7 9
    	}
    	cout << "" << endl;
    
    	//插入部分有重复的初始化列表，
    	s2.insert({
         1,2,3,4 });
    	for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
    	{
        
    		cout << *it << ' ';//1 2 3 4 5 7 9
    	}
    	cout << "" << endl;

**下文的map的插入操作也是如此。**

# multiset #

set和multiset会根据特定的排序原则将元素排序。两者不同之处在于，**multisets允许元素重复，而set不允许重复。**  
![在这里插入图片描述][20201031170237824.png_pic_center]  
multiset 容器和 set 容器有相同的成员函数，但是因为 multiset 可以保存重复元素，有些函数的表现会有些不同。和 set 容器中的成员函数表现不同的是：

*  insert() 总是可以成功执行。当插入单个元素时，返回的迭代器指向插入的元素。当插入一段元素时，返回的迭代器指向插入的最后一个元素。
 *  emplace() 和 emplace\_hint() 总是成功。它们都指向创建的新元素。
 *  find() 会返回和参数匹配的第一个元素的迭代器，如果都不匹配，则返回容器的结束迭代器。
 *  equal\_range() 返回一个包含迭代器的 pair 对象，它定义了一个和参数匹配的元素段。如果没有元素匹配的话，pair 的第一个成员是容器的结束迭代器；在这种情况下，第二个成员是比参数大的第一个元素，如果都没有的话，它也是容器的结束迭代器。
 *  lower\_bound() 返回和参数匹配的第一个元素的迭代器，如果没有匹配的元素，会返回容器的结束迭代器。返回的迭代器和 range() 返回的 pair 的第一个成员相同。
 *  upper\_bound() 返回的迭代器和 equal\_range() 返回的 pair 的第二个成员相同。
 *  count() 返回和参数匹配的元素的个数。

## insert()函数的返回值 ##

iterator insert( const value_type& value );//iterator 是指向被插入元素的迭代器。
    void insert( InputIt first, InputIt last );
    void insert( std::initializer_list<value_type> ilist );

**multimap同上。**

# map-键值对 #

map和set一样是关联式容器，它们的底层容器都是红黑树，区别就在于map的值不作为键，键和值是分开的。它的特性如下：

*  map以RBTree作为底层容器
 *  所有元素都是键+值存在
 *  不允许键重复
 *  所有元素是通过键进行自动排序的
 *  map的键是不能修改的，但是其键对应的值是可以修改的

在map中，一个键对应一个值，其中键不允许重复，不允许修改，但是键对应的值是可以修改的。由于map是key\_value的形式，所以map里的所有元素都是pair类型。pair里面的first被称为key(键），second被称为value(值）。它可以通过关键字查找映射关联信息value，**同时根据key值进行排序**。

**插入：**

map<string, string> dict;
    dict.insert(pair<string, string>("string", "字符串"));//模板类型pair：构造了一个匿名对象插入到map
    dict.insert(make_pair("apple", "苹果"));//模板函数make_pair：偷懒了，实际调的是pair
    dict.insert({
         "left", "左边" });
    dict.insert({
         "left", "剩余" });//插入不进去了，因为key值已经有了
    dict.insert(map<string, string>::value_type("test", "测试"));

插入有三种方法：

> 采用创建pair的形式插入pair<string, string>(“string”, “字符串”)  
> 采用make\_pair的形式进行插入make\_pair(“apple”, “苹果”)  
> 采用大括号的形式进行插入\{ “left”, “左边”\}  
> 用insert函数插入value\_type数据map<string, string>::value\_type(“test”, “测试”)

**遍历方法：**

//新式for循环
    for (const auto &e : dict)
    {
        
    	cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    
    //迭代器遍历
    map<string, string>::iterator mit = dict.begin();
    while (mit != dict.end())
    {
        
    	cout << mit->first << ":" << mit->second << endl;
    	cout << (*mit).first << ":" << (*mit).second << endl;
    	mit++;
    }

**访问元素operator\[ \]**：  
operator\[\]可以通过key值找到对应的value值。并且还可以**使用operator\[\]插入数据**。

dict["banana"];

插入一个pair，这个pair的key值为“banana”，value为空字符串(\\0)

dict["key"] = "关键字";

插入一个pair，这个pair的key值为“key”，value为“关键字”

dict["left"] = "剩余";

因为本来map里“left”这个key值，所以operator\[\]找到了这个key值，将它的value改成“剩余”。

**查找元素**

当所查找的关键key出现时，它返回数据所在对象的位置，如果沒有，返回iter与end函数的值相同。

// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
    iter = mapStudent.find("123");
    if(iter != mapStudent.end())
           cout<<"Find, the value is"<<iter->second<<endl;
    else
       cout<<"Do not Find"<<endl;

**其他函数：**

// 返回小于当前元素的第一个可插入的位置
    iterator lower_bound(const key_type& x) {
        return t.lower_bound(x); }
    const_iterator lower_bound(const key_type& x) const
    {
        
      return t.lower_bound(x);
    }
     
    // 返回大于当前元素的第一个可插入的位置
    iterator upper_bound(const key_type& x) {
        return t.upper_bound(x); }
    const_iterator upper_bound(const key_type& x) const
    {
        
      return t.upper_bound(x);
    }
    // 返回与指定键值相等的元素区间
    pair<iterator,iterator> equal_range(const key_type& x)
    {
        
      return t.equal_range(x);
    }

测试用例：

#include <iostream>
    #include<string>
    #include<map>
    using namespace std;
    
    int main(void) {
        
    	//创建一个键为int类型，值为string类型的map
    	map<int, string> m1;
    
    	//插入键值对
    	m1.insert(pair<int, string>(1, "Mon"));
    	m1.insert(make_pair(2, "Tue"));
    	m1.insert({
         3,"Wed" });
    	m1.insert(map<int, string>::value_type(4, "Thur"));//
    
    	//判断是否插入成功
    	pair<map<int, string>::iterator, bool> ret;
    	ret = m1.insert(map<int, string>::value_type(4, "Thur"));//返回的是pair类型
    	if (ret.second) {
        
    		cout << "insert successfully" << endl;
    	}
    	else {
        
    		cout << "insert unsuccessfully" << endl;
    	}
    
    	//遍历map，元素的first为键 ，second为值
    	for (auto x : m1) {
        
    		cout <<"key: "<< x.first<<"   value: "<<x.second << endl;
    	}
    	cout << "" << endl;
    	//访问元素
    	m1[1] = "Monday";
    	m1[5] = "Fri";
    
    	for (auto i = m1.begin(); i != m1.end(); i++) {
        
    		cout << "key: " << i->first << "   value: " << (*i).second << endl;
    	}
    	return 0;
    }
    /*
    结果：
    insert unsuccessfully
    key: 1   value: Mon
    key: 2   value: Tue
    key: 3   value: Wed
    key: 4   value: Thur
    
    key: 1   value: Monday
    key: 2   value: Tue
    key: 3   value: Wed
    key: 4   value: Thur
    key: 5   value: Fri
    */

常用函数总结：

begin()         返回指向map头部的迭代器
    
     clear(）        删除所有元素
    
     count()         返回指定元素出现的次数
    
     empty()         如果map为空则返回true
    
     end()           返回指向map末尾的迭代器
    
     equal_range()   返回特殊条目的迭代器对
    
     erase()         删除一个元素
    
     find()          查找一个元素
    
     get_allocator() 返回map的配置器
    
     insert()        插入元素
    
     key_comp()      返回比较元素key的函数
    
     lower_bound()   返回键值>=给定元素的第一个位置
    
     max_size()      返回可以容纳的最大元素个数
    
     rbegin()        返回一个指向map尾部的逆向迭代器
    
     rend()          返回一个指向map头部的逆向迭代器
    
     size()          返回map中元素的个数
    
     swap()           交换两个map
    
     upper_bound()    返回键值>给定元素的第一个位置
    
     value_comp()     返回比较元素value的函数

# multimap #

multimap也是可反转的，经过排序的关联容器，但是同一个键可以关联多个值。multimap和map的关系就跟multiset和set的关系一样，multimap允许键的值相同，因此在插入操作的时候用到insert\_equal()，除此之外，基本上与map相同。

[20201031170237824.png_pic_center]: /images/20221120/a7ec4d1e9b6b475fad8de41f5e6afee1.png