墨滴
E

EdwardWong

V1

2022/12/14阅读：23主题：姹紫

STL关联型容器之multimap和multiset

multimap容器

multimap容器与map容器的区别

multimap与map相似，都是关联式容器。所谓“相似”，指的是 multimap 容器具有和 map 相同的特性，即 multimap 容器也用于存储 pair<const K, T> 类型的键值对（其中 K 表示键的类型，T 表示值的类型），其中各个键值对的键的值不能做修改；并且，该容器也会自行根据键的大小对存储的所有键值对做排序操作。和 map 容器的区别在于，multimap 容器中可以同时存储多（≥2）个键相同的键值对.

和 map 容器一样，实现 multimap 容器的类模板也定义在<map>头文件，并位于 std 命名空间中。因此，在使用 multimap 容器前，程序应包含如下代码：

#include <map>
using namespace std;

multimap 容器类模板的定义如下：

template < class Key, // 指定键（key）的类型        
          class T,  // 指定值（value）的类型
           class Compare = less<Key>,                 // 指定排序规
           class Alloc = allocator<pair<const Key,T> >  // 指定分配器对象的类型
           > class multim

创建multimap容器的方法

multimap 类模板内部提供有多个构造函数,可以归纳为以下5种：

  1. 通过调用 multimap 类模板的默认构造函数，可以创建一个空的 multimap 容器：

std::multimap<std::string, std::string> mymultimap

  1. 创建并初始化multimap 
//创建并初始化 multimap 容器
multimap<string, string>mymultimap{ {"C语言教程", "http://c.biancheng.net/c/"}, {"Python教程", "http://c.biancheng.net/python/"},
{"STL教程", "http://c.biancheng.net/stl/"} };

使用此方式初始化 multimap 容器时，其底层会先将每一个{key, value}创建成 pair 类型的键值对，然后再用已建好的各个键值对初始化 multimap 容器。

我们完全可以先手动创建好键值对，然后再用其初始化 multimap 容器。下面程序使用了 2 种方式创建 pair 类型键值对，再用其初始化 multimap 容器，它们是完全等价的：

//借助 pair 类模板的构造函数来生成各个pair类型的键值对
multimap<string, string>mymultimap{
    pair<string,string>{"C语言教程", "http://c.biancheng.net/c/"},
    pair<string,string>{ "Python教程", "http://c.biancheng.net/python/"},
    pair<string,string>{ "STL教程", "http://c.biancheng.net/stl/"}
};
//调用 make_pair() 函数，生成键值对元素
//创建并初始化 multimap 容器
multimap<string, string>mymultimap{
    make_pair("C语言教程", "http://c.biancheng.net/c/"),
    make_pair("Python教程", "http://c.biancheng.net/python/"),
    make_pair("STL教程", "http://c.biancheng.net/stl/")
};
  1. 调用拷贝或移动构造函数

multimap<string, string>newmultimap(mymultimap); //拷贝构造函数

//创建一个会返回临时 multimap 对象的函数
multimap<string, string> dismultimap() {
    multimap<string, string>tempmultimap{ {"C语言教程", "http://c.biancheng.net/c/"},{"Python教程", "http://c.biancheng.net/python/"} };
    return tempmultimap;
}  
//调用 multimap 类模板的移动构造函数创建 newMultimap 容器
multimap<string, string>newmultimap(dismultimap());
  1. multimap 类模板还支持从已有 multimap 容器中，选定某块区域内的所有键值对，用作初始化新 multimap 容器时使用。 
//创建并初始化 multimap 容器
multimap<string, string>mymultimap{ {"C语言教程", "http://c.biancheng.net/c/"},
                                    {"Python教程", "http://c.biancheng.net/python/"},
                                    {"STL教程", "http://c.biancheng.net/stl/"} };
multimap<string, string>newmultimap(++mymultimap.begin(), mymultimap.end());
  1. multimap 类模板共可以接收 4 个参数，其中第 3 个参数可用来修改 multimap 容器内部的排序规则。默认情况下，此参数的值为std::less<T>，这意味着以下 2 种创建 multimap 容器的方式是等价的: 
//升序排序
multimap<char, int>mymultimap{ {'a',1},{'b',2} };
multimap<char, int, std::less<char>>mymultimap{ {'a',1},{'b',2} };
//降序排序
multimap<char, int, std::greater<char>>mymultimap{ {'a',1},{'b',2} };

multimap容器包含的成员方法

和 map 容器相比，multimap 未提供 at() 成员方法，也没有重载 [] 运算符。这意味着，map 容器中通过指定键获取指定指定键值对的方式，将不再适用于 multimap 容器。其实这很好理解，因为 multimap 容器中指定的键可能对应多个键值对，而不再是 1 个.

#include <iostream>
#include <map>  //map
using namespace std;   

int main()
{
    //创建并初始化 multimap 容器
    multimap<char, int>mymultimap{ {'a',10},{'b',20},{'b',15}, {'c',30} };
    //输出 mymultimap 容器存储键值对的数量
    cout << mymultimap.size() << endl;
    //输出 mymultimap 容器中存储键为 'b' 的键值对的数量
    cout << mymultimap.count('b') << endl;

    for (auto iter = mymultimap.begin(); iter != mymultimap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

multiset容器

和 set 容器不同的是，multiset 容器可以存储多个值相同的元素.

multiset 容器和 set 容器唯一的差别在于，multiset 容器允许存储多个值相同的元素，而 set 容器中只能存储互不相同的元素。

和 set 类模板一样，multiset 类模板也定义在<set>头文件，并位于 std 命名空间中。这意味着，如果想在程序中使用 multiset 容器，该程序代码应包含如下语句：

#include <set>
using namespace std;

multiset 容器类模板的定义如下所示：

template < class T,                        // 存储元素的类型
       class Compare = less<T>,              // 指定容器内部的排序规则
       class Alloc = allocator<T> >          // 指定分配器对象的类型
      > class multiset;

multiset容器的创建

创建方法与set类似，详细的可见STL关联型容器之set

multiset容器成员方法

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    std::multiset<int> mymultiset{1,2,2,2,3,4,5};
    cout << "multiset size = " << mymultiset.size() << endl;
    cout << "multiset count(2) =" << mymultiset.count(2) << endl;
    //向容器中添加元素 8
    mymultiset.insert(8);
    //删除容器中所有值为 2 的元素
    int num = mymultiset.erase(2);
    cout << "删除了 " << num << " 个元素 2" << endl;
    //输出容器中存储的所有元素
    for (auto iter = mymultiset.begin(); iter != mymultiset.end(); ++iter) {
        cout << *iter << " ";
    }
    return 0;
}

STL关联式容器的排序规则

使用函数对象自定义排序规则

无论关联式容器中存储的是基础类型（如 int、double、float 等）数据，还是自定义的结构体变量或类对象（包括 string 类），都可以使用函数对象的方式为该容器自定义排序规则。

#include <iostream>
#include <set>      // set
#include <string>       // string
using namespace std;
//定义函数对象类
class cmp {
public:
    //重载 () 运算符
    bool operator ()(const string &a,const string &b) {
        //按照字符串的长度，做升序排序(即存储的字符串从短到长)
        return  (a.length() < b.length());
    }
};

int main() {
    //创建 set 容器，并使用自定义的 cmp 排序规则
    std::set<string, cmp>myset{"http://c.biancheng.net/stl/",
                               "http://c.biancheng.net/python/",
                               "http://c.biancheng.net/java/"};
    //输出容器中存储的元素
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
            cout << *iter << endl;
    }
    return 0;
}

其定义了一个函数对象类，并在其重载 () 运算符的方法中自定义了新的排序规则，即按照字符串的长度做升序排序。通过将函数对象类的类名 cmp 通过 set 类模板的第 2 个参数传递给 myset 容器，该容器内部排序数据的规则，就改为了以字符串的长度为标准做升序排序。

函数对象类 cmp 也可以使用 struct 关键字创建：

//定义函数对象类
struct cmp {
    //重载 () 运算符
    bool operator ()(const string &a, const string &b) {
        //按照字符串的长度，做升序排序(即存储的字符串从短到长)
        return  (a.length() < b.length());
    }
};

在定义函数对象类时，也可以将其定义为模板类:

//定义函数对象模板类
template <typename T>
class cmp {
public:
    //重载 () 运算符
    bool operator ()(const T &a, const T &b) {
        //按照值的大小，做升序排序
        return  a < b;
    }
};

注意，此方式必须保证 T 类型元素可以直接使用关系运算符（比如这里的 < 运算符）做比较。

重载关系运算符实现自定义排序

表中的这些排序规则，其底层也是采用函数对象的方式实现的。以 std::less<T> 为例，其底层实现为:

template <typename T>
struct less {
    //定义新的排序规则
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
}

在此基础上，当关联式容器中存储的数据类型为自定义的结构体变量或者类对象时，通过对现有排序规则中所用的关系运算符进行重载，也能实现自定义排序规则的目的

当关联式容器中存储的元素类型为结构体指针变量或者类的指针对象时，只能使用函数对象的方式自定义排序规则，此方法不再适用。

#include <iostream>
#include <set>      // set
#include <string>       // string
using namespace std;
//自定义类
class myString {
public:
    //定义构造函数，向 myset 容器中添加元素时会用到
    myString(string tempStr) :str(tempStr) {};
    //获取 str 私有对象，由于会被私有对象调用，因此该成员方法也必须为 const 类型
    string getStr() const;
private:
    string str;
};
string myString::getStr() const{
    return this->str;
}
//重载 < 运算符，参数必须都为 const 类型
bool operator <(const myString &stra, const myString & strb) {
    //以字符串的长度为标准比较大小
    return stra.getStr().length() < strb.getStr().length();
}

int main() {
    //创建空 set 容器，仍使用默认的 less<T> 排序规则
    std::set<myString>myset;
    //向 set 容器添加元素，这里会调用 myString 类的构造函数
    myset.emplace("http://c.biancheng.net/stl/");
    myset.emplace("http://c.biancheng.net/c/");
    myset.emplace("http://c.biancheng.net/python/");
    //
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
        myString mystr = *iter;
        cout << mystr.getStr() << endl;
    }
    return 0;
}

上面程序以全局函数的形式实现对 < 运算符的重载，还可以使用成员函数或者友元函数的形式实现。其中，当以成员函数的方式重载 < 运算符时，该成员函数必须声明为 const 类型，且参数也必须为 const 类型：

bool operator <(const myString & tempStr) const {
    //以字符串的长度为标准比较大小
    return this->str.length() < tempStr.str.length();
}

同样，如果以友元函数的方式重载 < 运算符时，要求参数必须使用 const 修饰

//类中友元函数的定义
friend bool operator <(const myString &a, const myString &b);

//类外部友元函数的具体实现
bool operator <(const myString &stra, const myString &strb) {
    //以字符串的长度为标准比较大小
    return stra.str.length() < strb.str.length();
}

修改关联式容器中键值对的键

需要指出的是，对于如何修改容器中某个键值对的键，所有关联式容器可以采用同一种解决思路，即先删除该键值对，然后再向容器中添加修改之后的新键值对

map<int, int> mymap{ {1,10},{2,20} };
//map 容器的键为 const 类型，不能被修改
mymap.begin()->first = 100;

multimap<int, int> mymultimap{ {10,100},{20,200} };
//multimap 容器的键为 const 类型，同样不能被修改
mymultimap.begin()->first = 100;

上述代码试图直接将 mymap 容器中 {1,10} 的键改为 100，同样试图直接将 mymultimap 容器中 {10,100} 的键改为 100，它们都是不能通过编译的。

直接修改 map 或 multimap 容器中某个键值对的键是行不通的。但对于 set 或者 multiset 容器来说，却是可行的

和 map、multimap 不同，C++ STL 标准中并没有用 const 限定 set 和 multiset 容器中存储元素的类型。换句话说，对于 set<T> 或者 multiset<T> 类型的容器，其存储元素的类型是 T 而不是 const T.

对 set 和 multiset 容器中的元素类型作 const 修饰，是违背常理的。举个例子，假设我们使用 set 容器存储多个学生信息，如下是一个表示学生的类:

class student {
public:
    student(string name, int id, int age) :name(name), id(id), age(age) {
    }
    const int& getid() const {
        return id;
    }
    void setname(const string name){
        this->name = name;
    }
    string getname() const{
        return  name;
    }
    void setage(int age){
        this->age = age;
    }
    int getage() const{
        return  age;
    }
private:
    string name;
    int id;
    int age;
};

在创建 set 容器之前，我们还需要为其设计一个排序规则，这里假定以每个学生的 id 做升序排序，其排序规则如下：

class cmp {
public:
    bool operator ()(const student &stua, const student &stub) {
        //按照字符串的长度，做升序排序(即存储的字符串从短到长)
        return  stua.getid() < stub.getid();
    }
};

创建一个可存储 student 对象的 set 容器:

set<student, cmp> myset{ {"zhangsan",10,20},{"lisi",20,21},{"wangwu",15,19} };

总之，set 和 multiset 容器的元素类型没有用 const 修饰。所以从语法的角度分析，我们可以直接修改容器中元素的值，但一定不要修改元素的键。

set<student>::iterator iter = mymap.begin();
(*iter).setname("xiaoming");

虽然 C++ STL 标准没有用 const 修饰 set 或者 multiset 容器中元素的类型，但也做了其它工作来限制用户修改容器的元素。例如上面代码中，*iter 会调用 operator*，其返回的是一个 const T& 类型元素。这意味着，**C++ STL 标准不允许用户借助迭代器来直接修改 set 或者 multiset 容器中的元素**。

我们只需要借助 const_cast 运算符对上面程序稍作修改，就可以运行成功：

set<student>::iterator iter = mymap.begin();
const_cast<student&>(*iter).setname("xiaoming");

mymap 容器中的 {"zhangsan",10,20} 就变成了 {"xiaoming",10,20}。

再次强调，虽然使用 const_cast 能直接修改 set 或者 multiset 容器中的元素，但一定不要修改元素的键！如果要修改，只能采用“先删除，再添加”的方式。另外，不要试图以同样的方式修改 map 或者 multimap 容器中键值对的键，这违反了 C++ STL 标准的规定。

分类：

后端

标签：

C++

作者介绍

E
EdwardWong
V1