程序设计实习：9.1Set和Multiset

标准模板库STL set和multiset：关联容器

set, multiset, map, multimap 内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。 除了各容器都有的函数外，还支持以下成员函数： find: 查找等于某个值 的元素(x小于y和y小于x同时不成立即为相等) lower_bound : 查找某个下界 upper_bound : 查找某个上界 equal_range : 同时查找上界和下界 count :计算等于某个值的元素个数(x小于y和y小于x同时不成立即为相等) insert: 用以插入一个元素或一个区间。

预备知识： pair 模板

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 大。

multiset的成员函数 pairequal_range(const T & val); 同时求得lower_bound和upper_bound。 iterator erase(iterator it); 删除it指向的元素，返回其后面的元素的迭代器(Visual studio 2010上如此，但是在 C++标准和Dev C++中，返回值不是这样)。

multiset 的用法：

multiset 的用法示例：

输出：

1) 2

2) 4 8 19 22 22 33 40

3) 22,33

4) 4 8 19 33 40

5) 33

6) 40 22 33 4 8 19

set：template, class A = allocator> class set { … } 插入set中已有的元素时，忽略插入。

set用法示例：

In-Video Quiz

1. 以下哪个对象定义语句是错的? A)paira(3.4,5.5); B)pairb; C)pairk(pair(“this”,4.5)); D)pairx(pairb(3.4,100)); 2. 要让下面一段程序能够编译通过，需要重载哪个运算符？ class A { }; multiset > b; b.insert(A()); A)== B)= C)> D)<

1. 以下哪个对象定义语句是错的? A)paira(3.4,5.5); B)pairb; C)pairk(pair(“this”,4.5)); D)pairx(pairb(3.4,100));

2. 要让下面一段程序能够编译通过，需要重载哪个运算符？ class A { }; multiset > b; b.insert(A()); A)== B)= C)> D)<

3. 下面程序片段输出结果是： int a[] = { 2,3,4,5,7,3}; multisetmp(a,a+6); cout << * mp.lower_bound(4); A)2 B)3 C)4 D)5

4. set类的equal_range成员函数的返回值类型是： A)void B)pair::iterator, set::iterator> C)pairD)pair::iterator,bool>