Home C++ multiset
Post
Cancel

C++ multiset

multisetset 库中一个非常有用的类型, 用它插入、删除一个数都能够在 O(logn) 的时间内完成, 还能时刻保证序列中的数是有序的, 并且序列中可以存在重复的数.

random_shuffle 定义在 algorithm 头文件中, 可以随机打乱一个序列.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <ctime>
#include <set>
using namespace std;
int main() {
    srand(time(0));
    int n=10,a[12];
    for(int i=1;i<=10;++i) a[i]=i;
    random_shuffle(a+1,a+1+n);
    multiset<int>mset;
    for(int i=1;i<=10;++i){
        cout<<a[i]<<" ";
        mset.insert(a[i]);
    }
    cout<<endl<<"FIRST:"<<endl;
    for(auto it=mset.begin();it!=mset.end();++it)
        cout<<*it<<" ";
    cout<<endl<<"SECOND:"<<endl;
    while(!mset.empty()){
        cout<<*(mset.begin())<<" ";
        mset.erase(mset.begin());
    }
    return 0;
}

Output:

1
2
3
4
5
7 1 4 6 8 9 5 2 3 10 
FIRST:
1 2 3 4 5 6 7 8 9 10 
SECOND:
1 2 3 4 5 6 7 8 9 10 

自定义比较器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
struct node{
    int id;
    string name;
    bool operator<(const node& x)const{
        if(name!=x.name) return name>x.name;
        return id<x.id;
    }
};
int main() {
    multiset<node>mset;
    mset.insert({12,"Pal"});
    mset.insert({14,"Kaldkn"});
    mset.insert({13,"Awdw"});
    mset.insert({1,"Pal"});
    for(auto it=mset.begin();it!=mset.end();++it)
        cout<<(*it).id<<" "<<(*it).name<<endl;
    return 0;
}

另一种写法: 重载运算符写在结构体 node 外面 (但是要放在另一个结构体中):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
struct node{
    int id;
    string name;
};
struct cmp{
    bool operator()(const node& x,const node& y)const{
        if(x.name!=y.name) return x.name>y.name;
        return x.id<y.id;
    }
};
int main() {
    multiset<node,cmp>mset;
    mset.insert({12,"Pal"});
    mset.insert({14,"Kaldkn"});
    mset.insert({13,"Awdw"});
    mset.insert({1,"Pal"});
    for(auto it=mset.begin();it!=mset.end();++it)
        cout<<(*it).id<<" "<<(*it).name<<endl;
    return 0;
}

rbegin(): 返回一个逆向迭代器, 指向逆向迭代的第一个元素.

rend(): 返回一个逆向迭代器, 指向逆向迭代的最后一个元素的下一个位置.

应该这样理解: mset.begin() 处是有值的, mset.end() 处是无值的. mset.rbegin() 处是有值的, mset.rend() 处是无值的. mset.rend() 指向 mset 中的最后一个元素, mset.end() 指向 mset 中最后一个元素的下一个位置; mset.begin() 指向 mset 中的第一个元素, mset.rbegin() 指向 mset 中的第一个元素的前一个位置.

insert(), erase() 成员函数都是有返回值的, 返回的就是这个元素插入到集合中 (排好序后) 的位置, 返回值类型是一个迭代器.

注意 mset.begin() 的迭代器类型和 mset.rbegin() 的迭代器类型不一样: mset.begin() 的迭代器类型是 multiset<node>::iterator, mset.rbegin() 的迭代器类型是 multiset<node>::reverse_iterator.

1
2
3
4
5
6
7
8
9
10
multiset<node,cmp>mset;
auto it=mset.insert({12,"Pal"});
if(it==mset.begin()) cout<<"YES"<<endl;
mset.insert({14,"Kaldkn"});

it=mset.begin();
cout<<(*it).id<<" "<<(*it).name<<endl;

auto itr=mset.rbegin(); //这里如果还用 it=mset.begin()的话就会报错,因为是reverse_iterator
cout<<(*itr).id<<" "<<(*itr).name<<endl;

注意访问结构体中成员的时候要 *(it).id 而不是 *it.id.

这样也是对的:

1
2
3
4
5
6
7
__typeof(mset.rend()) itr=mset.rbegin();
//or
__typeof(mset.rbegin()) itr=mset.rbegin();
//or
multiset<node>::reverse_iterator itr=mset.rbegin();

cout<<(*itr).id<<" "<<(*itr).name<<endl;

但是 __typedef(mset.end()) itr=mset.rbegin(); 就会报错.

1
2
error: no viable conversion from 'std::multiset<node, cmp>::reverse_iterator' (aka 'reverse_iterator<__tree_const_iterator<node, std::__tree_node<node, void *> *, long>>') to 'typeof (mset.end())' (aka '__tree_const_iterator<node, std::__tree_node<node, void *> *, long>')
    __typeof(mset.end()) itr=mset.rbegin();
1
2
__typeof(mset.rbegin()) temp=mset.rbegin();
cout<<*temp<<endl;

mset.insert(pos,elem) 这个成员函数是在指定位置插入元素. 由于会自动排序, 因此这个函数本质上是为了提高插入速度, 减少查找时间. 如果你事先不知道怎样才能最高效, 就不必使用. 返回值是插入的新元素的位置.

mset.insert(pos1,pos2) 是将范围 [pos1, pos2) 内的元素插入 mset 中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
multiset<int>mset,s;
int a[]={1,4,1,5,1,3};
for(int i=0;i<sizeof(a)/sizeof(a[0]);++i)
    mset.insert(a[i]);
cout<<"BEFORE OPERATION:"<<endl;
for(auto it=mset.begin();it!=mset.end();++it)
    cout<<*it<<" ";
cout<<endl;
cout<<mset.size()<<endl;
cout<<"INSERT 2:"<<endl;
s.insert(mset.find(3),mset.find(5));
for(auto it=s.begin();it!=s.end();++it)
    cout<<*it<<" ";
cout<<endl;
cout<<s.size()<<endl;

mset.erase(elem): 删除指定值的所有元素, 只要与这个值相等就都会被删掉.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
multiset<int>mset;
int a[]={1,1,4,1,5,1,3};
for(int i=0;i<sizeof(a)/sizeof(a[0]);++i)
    mset.insert(a[i]);
for(auto it=mset.begin();it!=mset.end();++it)
    cout<<*it<<" ";
cout<<endl;
cout<<mset.size()<<endl;
auto num=mset.erase(1);
cout<<num<<endl; //返回被移除的元素个数
for(auto it=mset.begin();it!=mset.end();++it)
    cout<<*it<<" ";
cout<<endl;
cout<<mset.size()<<endl;

mset.erase(pos): 删除指定位置的元素, 无返回值.

1
2
3
4
5
mset.erase(mset.find(4));
for(auto it=mset.begin();it!=mset.end();++it)
    cout<<*it<<" ";
cout<<endl;
// 1 1 1 1 3 5

erase(pos1,pos2): 移除区间 [pos1, pos2) 内的所有元素, 无返回值.

1
2
3
4
5
mset.erase(mset.find(1),mset.find(4));
for(auto it=mset.begin();it!=mset.end();++it)
    cout<<*it<<" ";
cout<<endl;
// 4 5

count(elem): 返回元素值为 elem 的元素个数.

find(elem): 返回元素值为 elem 的第一个元素, 如果没有就返回 end().

lower_bound(elem): 返回元素值为 elem 的第一个可插入位置, 也就是元素值 >=elem 的第一个元素位置.

upper_bound(elem): 返回元素值为 elem 的最后一个可插入位置, 也就是元素值 >elem 的第一个元素位置.

equal_range(elem): 返回 elem 可插入的第一个位置和最后一个位置, 也就是元素值 ==elem 的区间.

注意这个 equal_range 的返回值是 pair:

1
2
pair<const_iterator,const_iterator> equal_range (const value_type& val) const;
pair<iterator,iterator>                    equal_range (const value_type& val);

用法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
multiset<int>mset;
int a[]={1,7,4,1,5,1,3};
for(int i=0;i<sizeof(a)/sizeof(int);++i)
    mset.insert(a[i]);
for(auto it=mset.begin();it!=mset.end();++it)
    cout<<*it<<" ";
cout<<endl;
auto pos=mset.lower_bound(2);
if(pos!=mset.end()) cout<<*pos<<endl;
pos=mset.lower_bound(3);
if(pos!=mset.end()) cout<<*pos<<endl;
pos=mset.lower_bound(7);
if(pos!=mset.end()) cout<<*pos<<endl;
pos=mset.lower_bound(4);
if(pos!=mset.end()) cout<<*pos<<endl;
pos=mset.upper_bound(4);
if(pos!=mset.end()) cout<<*pos<<endl;
auto ret=mset.equal_range(1);
if(ret.first!=mset.end()) cout<<*ret.first<<endl;
if(ret.second!=mset.end()) cout<<*ret.second<<endl;
ret=mset.equal_range(4);
if(ret.first!=mset.end()) cout<<*ret.first<<endl;
if(ret.second!=mset.end()) cout<<*ret.second<<endl;
This post is licensed under CC BY 4.0 by the author.