STL--set和multiset集合

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

使用set或multiset，必须先包含头文件:

#include <set>
1

上述两个类型都被定义为命名空间std内的class template:

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

    template <typename T,
    typename Compare = less<T>,
    typename Allocator = allocator<T> >
    class multiset;
}
1
2
3
4
5
6
7
8
9
10
11

其中T是能进行排序的数据类型。第二个参数是进行排序的规则,默认为升序(小于,<),第三个是内存分配器,不用管。

set 和multiset通常用平衡二叉树(balanced binary tree,确切说是红黑树)实现。这样在插入数据时能自动排序,使得查找元素时有良好性能。其查找函数具有对数O(logn)时间复杂度。

但是,自动排序也造成set和multiset的一个重要限制:你**不能直接改变元素值，**因为这样会打乱原本正确的顺序。

从其接口也能反映这种情况:

set和multiset不提供任何函数可以直接访问元素。

通过迭代器访问元素时都是常量。

1.1 定义及初始化

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/624150