C++ multiset，STL multiset详解

multiset 是关联容器的一种，是排序好的集合（元素已经进行了排序），并且允许有相同的元素。

不能直接修改 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 multiset 容器中某个元素的值，正确的做法是先删除该元素，再插入新元素。

使用 multiset 必须包含头文件 <set>。multiset 类模板的定义如下：

template <class Key, class Pred = less<Key>, class B = allocator<Key> > class multiset {
    ...
};

该模板有三个类型参数：Key、Pred 和 B。类型参数可以有默认值，默认值就是某种类型。例如，Pred 类型参数的默认值就是 less<Key> 类型，B 的默认值就是 allocator<Key> 类型。第三个类型参数极少用到，一般都用默认值，因此这里不做介绍。

第一个类型参数说明 multiset 容器中的每个元素都是 Key 类型的。第二个类型参数 Pred 用于指明容器中元素的排序规则，在被实例化后，Pred 可以是函数对象类，也可以是函数指针类型。

multiset 内部在排序时定义了一个变量Pred op，根据表达式op(x, y)来比较两个元素 x、y 的大小。该表达式的值为 true，则说明 x 比 y 小。Pred 的默认值是 less<Key>，less 是 STL 中的函数对象类模板，其定义如下：

template <class_Tp>
struct less
{
    bool operator() (const _Tp &__x, const _Tp &__y) const
    { return __x < __y; }
};

这说明，在默认情况下，multiset 容器中的元素是用<运算符比较大小的。例如，假设 A 是一个类的名字，可以定义一个如下的容器对象：

multiset <A> s;

由于 multiset 的类型参数可以使用默认值，因此上面的语句等价于：

multiset < int, less<A>, allocator<A> > s;

模板类 multiset < A, less<A>, allocator<A> > 的 insert 成员函数可以用来插入一个元素。 插入过程中需要进行元素之间的比较，可以认为 insert 成员函数中定义了一个变量 less <A> op，用 op(x, y) 来比较元素 x、y 的大小。归根到底，还是用<运算符比较 x、y 的大小。 因此，<运算符必须经过适当重载，才可以向 multiset <A>容器中插人元素。

下面的程序 会编译出错：

#include <set>
using namespace std;
class A{};
int main(){
    multiset <A> a;
    a.insert( A() );  //编译出错，因为不能用“<”运算符比较两个A对象
}

multiset 常用的成员函数如表 1 所示。有的成员函数有不止一个版本，这里不一一 列出。

表1：multiset 的成员函数

成员函数或成员函数模板	作  用
iterator find (const T & val);	在容器中查找值为 val 的元素，返回其迭代器。如果找不到，返 回 end()
iterator insert( const T & val);	将 val 插入容器中并返回其迭代器
void insert(iterator first, iterator last);	将区间 [first, last) 中的元素插人容器
int count( const T & val);	统计有多少个元素的值和 val 相等
iterator lower_bound( const T & val);	查找一个最大的位置 it，使得 [begin(), it) 中所有的元素者比 val 小
iterator upper_bound( const T & val);	查找一个最小的位置 it，使得 [it, end()) 中所有的元素都比 val 大
pair <iterator, iterator > equal_range (const T & val);	同时求得 lower_bound 和 upper_bound
iterator erase(iterator it);	删除 it 指向的元素，返回其后面的元素的迭代器（Visual Studio 2010 中如此，但是在 C++ 标准和 Dev C++ 中，返回值不是这样）
iterator erase(iterator first, iterator last);	删除区间 [first, last)，返回 last（Visual Studio 2010 中如此，但是在 C++ 标准和 Dev C++ 中，返回值不是这样）

multiset 及 set 中的 find 和 count 并不是用==运算符比较元素是否和待查找的值相等的。它们进行比较的原则是：如果x比y小和y比x小同时为假，就认为 x 和 y 相等。

下面通过一个例子说明 multiset 的用法。

#include <iostream>
#include <set>  //使用multiset须包含此头文件
using namespace std;
template <class T>
void Print(T first, T last)
{
    for (; first != last; ++first)
        cout << *first << " ";
    cout << endl;
}
class A
{
private:
    int n;
public:
    A(int n_) { n = n_; }
    friend bool operator < (const A & a1, const A & a2)
    { return a1.n < a2.n; }
    friend ostream & operator << (ostream & o, const A & a2)
    { o << a2.n; return o; }
    friend class MyLess;
};
class MyLess
{
public:
    bool operator() (const A & a1, const A & a2)  //按个位数比较大小
    { return (a1.n % 10) < (a2.n % 10); }
};
typedef multiset <A> MSET1;  //MSET1 用“<”运算符比较大小
typedef multiset <A, MyLess> MSET2;  //MSET2 用 MyLess::operator() 比较大小
int main()
{
    const int SIZE = 6;
    A a[SIZE] = { 4, 22, 19, 8, 33, 40 };
    MSET1 m1;
    m1.insert(a, a + SIZE);
    m1.insert(22);
    cout << "1)" << m1.count(22) << endl;  //输出 1)2
    cout << "2)"; Print(m1.begin(), m1.end());  //输出 2)4 8 19 22 22 33 40
    MSET1::iterator pp = m1.find(19);
    if (pp != m1.end())  //条件为真说明找到
        cout << "found" << endl;  //本行会被执行，输出 found
    cout << "3)"; cout << *m1.lower_bound(22)
        << "," << *m1.upper_bound(22) << endl; //输出 3)22,33
    pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));
    //pp指向被删元素的下一个元素
    cout << "4)"; Print(m1.begin(), m1.end());  //输出 4)4 8 19 33 40
    cout << "5)"; cout << *pp << endl;  //输出 5)33
    MSET2 m2;  //m2中的元素按n的个位数从小到大排序
    m2.insert(a, a + SIZE);
    cout << "6)"; Print(m2.begin(), m2.end());  //输出 6)40 22 33 4 8 19
    return 0;
}

第 30 行，MSET2 类的排序规则和 MSET1 不同。MSET2 用 MyLess 定义排序规则，即 n 的个位数小的元素排在前面。

第 43、44 行，lower_bound 返回的迭代器指向第一个 22，upper_bound 返回的迭代器指向 33。

第 45 行，删除所有值为 22 的元素。erase 成员函数删除一个元素后，返回下一个元素的迭代器应该是很合理的，但是 C++ 标准委员会认为，返回下一个元素的迭代器也是需要时间开销的，如果程序员不想要这个返回值，那么这个开销就是浪费的——因此在遵循 C++ 标准的 Dev C++ 中，本行无法编译通过。但是微软公司认为应该对这一点做出改进，因此 Visual Studio 2010 将 erase 成员函数处理成返回被删元素下一个元素的迭代器。

不论在哪种编译器中，用 erase 成员函数删除迭代器 i 指向的元素后，迭代器 i 即告失效， 此时不能指望 ++i 后 i 会指向被删除元素的下一个元素；相反，++i 可能立即导致出错。如果想要得到被删除元素后面那个元素的迭代器，可以在删除前获取其迭代器并保存起来（这同样适用于 set、map、multimap 的 erase 成员函数）。事实上，如果得到了某关联容器的迭代器，则该迭代器并不会因为容器中元素的插入以及其他元素的删除而失效。只要该迭代器指向的元素没有被删除，就可以一直使用它。