C++标准程序库之set,multiset

set和multiset会根据特定的排序准则，自动将元素排序。两者的不同之处在于multiset允许元素重复而set不允许。

使用set或multiset之前，必须包含头文件<set>，在该头文件中，上述两个类型都被定义为命名空间std内的class template：

namespace std {
	template <class T, class Compare = less<T>, class Allocator = allocator<T>>
	class set;
	
	template <class T, class Compare = less<T>, class Allocator = allocator<T>>
	class multiset;
}

namespace std {

template <class T, class Compare = less<T>, class Allocator = allocator<T>>

class set;

template <class T, class Compare = less<T>, class Allocator = allocator<T>>

class multiset;

}

只要是assignable、copyable、comparable(根据某个排序准则)的类型T,都可以成为set或multiset的元素类型。
可有可无的第二个参数用来定义排序准则，如果没有传入特别的排序准则，就采用缺省准则less——这是个仿函数，以operator<对元素进行比较，以便完成排序。
可有可无的第三个参数用来定义内存模型。缺省的内存模型是allocator，有C++标准程序库提供。

1.set和multiset的能力

（1）和所有标准关联式容器类似，set和multiset通常以平衡二叉树完成。
（2）自动排序的主要优点在于使二叉树于搜寻元素时具有良好性能。其搜寻函数算法具有对数复杂度。
（3）但是，自动排序造成set和multiset的一个重要限制：你不能直接改变元素值，因为这样会打乱原本正确的顺序。因此，要改变元素值，必须先删除旧元素，再插入新元素。这里提供的接口正反映了这种行为：

set和multiset不提供用来直接存取元素的任何操作函数。
通过迭代器进行元素间接存取，有一个限制：从迭代器的角度来看，元素值是常数。

2.set和multiset的操作函数

（1）set和multiset的构造函数和析构函数

set c        产生一个空的set/multiset，其中不含元素
set c(op)    以op为排序准则，产生一个空的set/multiset
set c1(c2)   产生某个set/multiset的副本，所有元素均被复制
set c(beg,end)    以区间[beg,end)内的元素产生一个set/multiset
set c(beg,end,op) 以op为排序准则，利用[beg,end)内的元素生成一个set/multiset
c.~set()      销毁所有元素，释放内存

其中set可为下列形式：
set<Elem>        一个set，以less<>(operator<)为排序准则
set<Elem,Op>     一个set，以op为排序准则
multiset<Elem>   一个multiset，以less<>(operator<)为排序准则
multiset<Elem,Op>一个multiset,以op为排序准则

set c 产生一个空的set/multiset，其中不含元素

set c(op) 以op为排序准则，产生一个空的set/multiset

set c1(c2) 产生某个set/multiset的副本，所有元素均被复制

set c(beg,end) 以区间[beg,end)内的元素产生一个set/multiset

set c(beg,end,op) 以op为排序准则，利用[beg,end)内的元素生成一个set/multiset

c.~set() 销毁所有元素，释放内存

其中set可为下列形式：

set<Elem> 一个set，以less<>(operator<)为排序准则

set<Elem,Op> 一个set，以op为排序准则

multiset<Elem> 一个multiset，以less<>(operator<)为排序准则

multiset<Elem,Op>一个multiset,以op为排序准则

（2）set和multiset的非变动性操作

c.size()    返回容器的大小
c.empty()   判断容器大小是否为0
c.max_size()返回可容纳的最大元素数量
c1 == c2    ...
c1 != c2
c1 < c2
c1 > c2
c1 <= c2
c1 >= c2

c.size() 返回容器的大小

c.empty() 判断容器大小是否为0

c.max_size()返回可容纳的最大元素数量

c1 == c2 ...

c1 != c2

c1 < c2

c1 > c2

c1 <= c2

c1 >= c2

（3）set和multiset的搜寻操作函数

count(elem)        返回“元素值为elem”的元素个数
find(elem)         返回“元素值为elem”的第一个元素，如果找不到就返回end()
lower_bound(elem)  返回elem的第一个可安插位置，也就是“元素值 >=elem”的第一个元素位置
upper_bound(elem)  返回elem的最后一个可安插位置，也就是“元素值>elem”的第一个元素位置
equal_range(elem)  返回elem可安插的第一个位置和最后一个位置，也就是“元素值==elem”的元素区间。即将lower_bound和upper_bound的返回值做成一个pair返回。

count(elem) 返回“元素值为elem”的元素个数

find(elem) 返回“元素值为elem”的第一个元素，如果找不到就返回end()

lower_bound(elem) 返回elem的第一个可安插位置，也就是“元素值 >=elem”的第一个元素位置

upper_bound(elem) 返回elem的最后一个可安插位置，也就是“元素值>elem”的第一个元素位置

equal_range(elem) 返回elem可安插的第一个位置和最后一个位置，也就是“元素值==elem”的元素区间。即将lower_bound和upper_bound的返回值做成一个pair返回。

考虑如下示例：

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

int main()
{
        set<int> c;

        c.insert(1);
        c.insert(2);
        c.insert(4);
        c.insert(5);
        c.insert(6);

        cout << "lower_bound(3): " << *c.lower_bound(3) << endl;
        cout << "upper_bound(3): " << *c.upper_bound(3) << endl;
        cout << "equal_range(3): " << *c.equal_range(3).first << " " << *c.equal_range(3).second << endl;

        cout << endl;
        cout << "lower_bound(5): " << *c.lower_bound(5) << endl;
        cout << "upper_bound(5): " << *c.upper_bound(5) << endl;
        cout << "equal_range(5): " << *c.equal_range(5).first << " " << *c.equal_range(5).second << endl;
}

#include <iostream>

#include <set>

using namespace std;

int main()

{

set<int> c;

c.insert(1);

c.insert(2);

c.insert(4);

c.insert(5);

c.insert(6);

cout << "lower_bound(3): " << *c.lower_bound(3) << endl;

cout << "upper_bound(3): " << *c.upper_bound(3) << endl;

cout << "equal_range(3): " << *c.equal_range(3).first << " " << *c.equal_range(3).second << endl;

cout << endl;

cout << "lower_bound(5): " << *c.lower_bound(5) << endl;

cout << "upper_bound(5): " << *c.upper_bound(5) << endl;

cout << "equal_range(5): " << *c.equal_range(5).first << " " << *c.equal_range(5).second << endl;

}

输出：

[root@VM_198_209_centos cppstl]# make
g++     set_lower_bound.cpp   -o set_lower_bound
[root@VM_198_209_centos cppstl]# ./set_lower_bound 
lower_bound(3): 4
upper_bound(3): 4
equal_range(3): 4 4

lower_bound(5): 5
upper_bound(5): 6
equal_range(5): 5 6

[root@VM_198_209_centos cppstl]# make

g++ set_lower_bound.cpp -o set_lower_bound

[root@VM_198_209_centos cppstl]# ./set_lower_bound

lower_bound(3): 4

upper_bound(3): 4

equal_range(3): 4 4

lower_bound(5): 5

upper_bound(5): 6

equal_range(5): 5 6

（4）set和multiset的赋值操作

c1 = c2        将c2中所有元素赋值给c1
c1.swap(c2)    将c1和c2的元素互换
swap(c1,c2)    同上。此为全局函数

c1 = c2 将c2中所有元素赋值给c1

c1.swap(c2) 将c1和c2的元素互换

swap(c1,c2) 同上。此为全局函数

（5）set和multiset的迭代器相关操作函数

c.begin()        返回一个双向迭代器，指向第一个元素
c.end()          返回一个双向迭代器，指向最后元素的下一位置
c.rbegin()       返回一个逆向迭代器，指向逆向遍历时的第一个元素
c.rend()         返回一个逆向迭代器，指向逆向遍历时的最后元素的下一位置

c.begin() 返回一个双向迭代器，指向第一个元素

c.end() 返回一个双向迭代器，指向最后元素的下一位置

c.rbegin() 返回一个逆向迭代器，指向逆向遍历时的第一个元素

c.rend() 返回一个逆向迭代器，指向逆向遍历时的最后元素的下一位置

（6）set和multiset的元素插入和移除

c.insert(elem)        安插一份elem副本，返回新元素位置(不论是否成功——对set而言)
c.insert(pos,elem)    安插一份elem副本，返回新元素位置(pos是个提示，指出安插操作的搜寻起点。如果提示恰当，可大大加快速度)
c.insert(beg,end)     将区间[beg,end)内所有元素的副本安插到c
c.erase(elem)         移除"与elem相等"的所有元素，返回被移除的元素个数
c.erase(pos)          移除迭代器pos所指位置上的元素，无返回值
c.erase(beg,end)      移除区间[beg,end)内的所有元素，无返回值
c.clear()             移除全部元素，将整个容器清空

c.insert(elem) 安插一份elem副本，返回新元素位置(不论是否成功——对set而言)

c.insert(pos,elem) 安插一份elem副本，返回新元素位置(pos是个提示，指出安插操作的搜寻起点。如果提示恰当，可大大加快速度)

c.insert(beg,end) 将区间[beg,end)内所有元素的副本安插到c

c.erase(elem) 移除"与elem相等"的所有元素，返回被移除的元素个数

c.erase(pos) 移除迭代器pos所指位置上的元素，无返回值

c.erase(beg,end) 移除区间[beg,end)内的所有元素，无返回值

c.clear() 移除全部元素，将整个容器清空

注意，插入函数的返回类型不尽相同：

set提供如下接口：

C++

pair<iterator,bool> insert (const value_type& elem); iterator insert (iterator pos_hint, const value_type& elem);

1
2

pair<iterator,bool> insert (const value_type& elem);
iterator insert (iterator pos_hint, const value_type& elem);
multiset提供如下接口：

C++

iterator insert (const value_type& elem); iterator insert (const pos_hint, const value_type& elem);

1
2

iterator insert (const value_type& elem);
iterator insert (const pos_hint, const value_type& elem);

返回类型不同的原因是：multiset允许元素重复，而set不允许。因此如果将某元素插入set内，而该set已经内含同值元素，则插入操作将失败。所以set的返回类型是以pair组织起来的两个值：
1）pair结构中的second成员表示插入是否成功。
2）pair结构中的first成员返回新元素的位置，或返回现存的同值元素的位置。

注意，作用于序列式容器和关联式容器erase()函数，其返回值有一下不同：
1）序列式容器earse()成员函数：
iterator erase(iterator pos);
iterator erase(iterator beg, iterator end);

2）关联式容器erase()成员函数：
void erase(iterator pos);
void erase(iterator beg, iterator end);

存在这种差别，完全是为了性能。在关联式容器中“搜寻某元素并返回后继元素”可能颇为耗时，因为这种容器的底部是以二叉树完成，所以如果你想编写对所有容器都适用的程序，你必须忽略返回值。

3.异常处理

set和multiset是“以节点(nodes)为基础”的容器。如果节点构造失败，容器仍保持原样。此外，由于析构函数通常不抛出异常，所以节点的移除不可能失败。

然后，面对多重元素插入操作，“保持元素次序”这一条件会造成“异常抛出时能够完全复原”这一需求变得不切实际。因此只有“单一元素插入操作”才支持“成功，否则无效”的操作原则。至于“多元素删除操作”总是能够成功。如果排序准则之复制/赋值操作会抛出异常，则swap()也会抛出异常。

4.set和multiset运用实例

（1）set.cpp

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main()
{
        typedef set<int,greater<int> > IntSet;

        IntSet coll1;

        coll1.insert(4);
        coll1.insert(3);
        coll1.insert(5);
        coll1.insert(1);
        coll1.insert(6);
        coll1.insert(2);
        coll1.insert(5);

        IntSet::iterator pos;
        for (pos = coll1.begin(); pos != coll1.end(); ++pos)
                cout << *pos <<  ' ';
        cout << endl;

        pair<IntSet::iterator, bool> status = coll1.insert(4);
        if (status.second) {
                cout << "4 inserted as element " << distance(coll1.begin(), status.first) + 1
                << endl;
        }
        else
                cout << "4 already exists" << endl;

        set<int> coll2(coll1.begin(), coll1.end());

        copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
        cout << endl;

        coll2.erase(coll2.begin(), coll2.find(3));

        int num;
        num = coll2.erase(5);
        cout << num << " element(s) removed" << endl;

        copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
        cout << endl;
}

#include <iostream>

#include <set>

#include <iterator>

using namespace std;

int main()

{

typedef set<int,greater<int> > IntSet;

IntSet coll1;

coll1.insert(4);

coll1.insert(3);

coll1.insert(5);

coll1.insert(1);

coll1.insert(6);

coll1.insert(2);

coll1.insert(5);

IntSet::iterator pos;

for (pos = coll1.begin(); pos != coll1.end(); ++pos)

cout << *pos << ' ';

cout << endl;

pair<IntSet::iterator, bool> status = coll1.insert(4);

if (status.second) {

cout << "4 inserted as element " << distance(coll1.begin(), status.first) + 1

<< endl;

}

else

cout << "4 already exists" << endl;

set<int> coll2(coll1.begin(), coll1.end());

copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));

cout << endl;

coll2.erase(coll2.begin(), coll2.find(3));

int num;

num = coll2.erase(5);

cout << num << " element(s) removed" << endl;

copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));

cout << endl;

}

输出：

[root@VM_198_209_centos cppstl]# ./set
6 5 4 3 2 1 
4 already exists
1 2 3 4 5 6 
1 element(s) removed
3 4 6

[root@VM_198_209_centos cppstl]# ./set

6 5 4 3 2 1

4 already exists

1 2 3 4 5 6

1 element(s) removed

3 4 6

（2）multiset.cpp

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main()
{
        typedef multiset<int, greater<int> >IntSet;

        IntSet coll1;

        coll1.insert(4);
        coll1.insert(3);
        coll1.insert(5);
        coll1.insert(1);
        coll1.insert(6);
        coll1.insert(5);
        coll1.insert(2);

        for (int i : coll1)
                cout << i << " ";
        cout << endl;

        IntSet::iterator ipos = coll1.insert(4);
        cout << "4 inserted as element " << distance(coll1.begin(), ipos) + 1
        << endl;

        multiset<int> coll2(coll1.begin(), coll1.end());

        copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
        cout << endl;

        coll2.erase(coll2.begin(), coll2.find(3));

        int num;
        num = coll2.erase(5);
        cout << num << " element(s) removed" << endl;

        copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));
        cout << endl;
}

#include <iostream>

#include <set>

#include <iterator>

using namespace std;

int main()

{

typedef multiset<int, greater<int> >IntSet;

IntSet coll1;

coll1.insert(4);

coll1.insert(3);

coll1.insert(5);

coll1.insert(1);

coll1.insert(6);

coll1.insert(5);

coll1.insert(2);

for (int i : coll1)

cout << i << " ";

cout << endl;

IntSet::iterator ipos = coll1.insert(4);

cout << "4 inserted as element " << distance(coll1.begin(), ipos) + 1

<< endl;

multiset<int> coll2(coll1.begin(), coll1.end());

copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));

cout << endl;

coll2.erase(coll2.begin(), coll2.find(3));

int num;

num = coll2.erase(5);

cout << num << " element(s) removed" << endl;

copy(coll2.begin(), coll2.end(), ostream_iterator<int>(cout, " "));

cout << endl;

}

编译输出：

[root@VM_198_209_centos cppstl]# g++ -Wall -g multiset.cpp -o multiset -std=c++11
[root@VM_198_209_centos cppstl]# ./multiset 
6 5 5 4 3 2 1 
4 inserted as element 5
1 2 3 4 4 5 5 6 
2 element(s) removed
3 4 4 6

[root@VM_198_209_centos cppstl]# g++ -Wall -g multiset.cpp -o multiset -std=c++11

[root@VM_198_209_centos cppstl]# ./multiset

6 5 5 4 3 2 1

4 inserted as element 5

1 2 3 4 4 5 5 6

2 element(s) removed

3 4 4 6

1.set和multiset的能力

2.set和multiset的操作函数

3.异常处理

发表评论 取消回复

发表评论取消回复