【STL】set和multiset的初步认知

ゝ一纸荒年。 2022-07-15 10:18 194阅读 0赞

set/multiset是一个集合容器，我们可以对这个容器进行插入，删除，查找等工作。set的元素内容只有一个键值（key，key和value为同一个值），不允许重复冗余，当对它插入一个已经存在的元素时，它会自动忽略。set/multiset的底层是用红黑树（RBTree）实现，拥有平衡二叉搜索树的结构，所以在进行检索时，效率会很高。而正因为它是一颗红黑树结构，当我们顺序遍历它时，序列是有序的。我们就不能通过迭代器取修改相应的元素的key值。我们可以借源码看到，set的迭代器是红黑树const迭代器的typedef。  
![这里写图片描述][20161113152417365]  
multiset大部分功能与set相同，不同之处在于multiset允许出现相同的key值，也就是说允许出现重复的元素。所以再insert，erase的实现上会有所不同。其它都一样。我会再讲到insert，erase时剖析一下不同点，下面以set开讲。

### 构造/析构函数/赋值运算符重载 ###

它的构造函数实现有三种。

#### 构造函数 ####

explicit set ( const Compare& comp = Compare(), const Allocator& = Allocator() );`

explicit关键字用来修饰类的构造函数，防止发生隐式的类型转换。也可以理解为防止构造函数被隐式调用。  
它有两个参数，Compare是一个类型，Compare()是这个类型的匿名对象。这是一个比较函数，内部是以仿函数的形式来使用它，来实现排序时比较等功能。Allocator是一个空间配置器，它是c++标准库中最神秘的存在。以我现在的水平，还分析不出它。但是对我们理解set也不会有影响。  
2.

template <class InputIterator>
    set ( InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );

这个构造函数是以模板形式定义。模板参数InputIterator是一个类型的迭代器。  
它有四个参数，前两个参数都是迭代器，（first，last）所表示的是一个左闭右开的区间。可想而知，这个构造函数是以其他容器的一段数据进行构造。后两个参数与上相同。  
3.  
最后一个，拷贝构造函数，不再多说。

set ( const set<Key,Compare,Allocator>& x );

#### 析构函数 ####

~set（）

#### 赋值运算符重载 ####

set<Key,Compare,Allocator>& operator= ( const set<Key,Compare,Allocator>& x );

返回值为一个set的引用，参数为另一个set的引用。

### 迭代器Iterators: ###

#### begin ####

iterator begin ();//非const
    const_iterator begin () const;//const

正向迭代器，返回第一个元素的位置。

#### end ####

iterator end ();// 非const
    const_iterator end () const; //const

正向迭代器，返回最后一个元素的下一个位置。

#### rbegin ####

reverse_iterator rbegin();.//非const
    const_reverse_iterator rbegin() const; //const

反向迭代器，返回最后一个元素的位置。

#### rend ####

reverse_iterator rend();//非const
    const_reverse_iterator rend() const;//const

反向迭代器，返回第一个元素的前一个位置。

注意：有人可能以为，我调用rbegin()得到的迭代器是最后一个元素的位置，那对这个迭代器进行–(减减)操作就可以从后向前遍历这个set？不是，还是++(加加)。看一个例子：

#include<iostream>
    #include<set>
    using namespace std;
    void TestSet()
    {
        set<int> s;
    
        for (int i = 0; i < 10; ++i)
        {
            s.insert(i);
        }
        set<int>::reverse_iterator it = s.rbegin();//用反向迭代器接收
        while (it != s.rend())
        {
            cout << *it << " ";
            ++it;//使用++从前向后遍历
        }
        cout << endl;
    }
    int main()
    {
        TestSet();
        system("pause");
        return 0;
    }

输出结果：  
![这里写图片描述][20161113100150195]

### Capacity: ###

#### empty ####

bool empty ( ) const;

判空，当为空时返回true，不空时返回false。加const修饰是防止这个函数对类的成员做出修改。

#### size ####

size_type size() const;

返回set内元素的数量。 const作用同上。

#### max\_size ####

size_type size() const;

返回能插入元素的最大值，这个数输出来应该是214748364。为什么是这个数，由于系统和库的限制。

### 调节器Modifiers ###

#### insert ####

##### set的insert有3种实现 #####

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

返回值为一个pair，pair是一个模板类型，有两个模板参数，第一个叫first，第二个叫second。（想深入了解的自己查一下）  
这里的first是一个迭代器，第二个参数是一个bool值。  
当插入一个新元素时，返回值的first是新插入元素位置的迭代器，second是true。  
当插入一个已有的元素时，不插入，返回值得first是已有元素位置的迭代器，second是false。  
2.

iterator insert ( iterator position, const value_type& x );

第二种实现的返回值是一个迭代器，第一个参数是一个迭代器位置，第二个参数是要插入的元素。意思是在postion位置插入x。  
当插入一个新元素，返回新元素的迭代器。  
当插入一个已存在元素，不插入，返回已存在元素的迭代器。  
3.

template <class InputIterator>
    void insert ( InputIterator first, InputIterator last );

第3种实现，返回值为空，参数是两个模板类型的迭代器，（first，last）是一个左闭右开的区间，意思是将这个区间的元素插入set。可以理解为批量插入。

##### multiset的insert #####

multiset的insert定义，返回值，参数与set全部相同，不同之处在于它们耳朵内部实现。我们在开头说过set/multiset的底层实现是红黑树，所以它们大部分的功能函数都是调用的红黑树的函数。我们来看一下insert源码的定义：（参照《STL源码剖析》）

##### set的源码 #####

![这里写图片描述][20161113133019796]  
（ps：t是一个红黑树的对象）  
我们可以从图中看到，set的insert的三种实现都调用了一个叫insert\_unipue()的函数，我们不需要看它的实现了，从字面就可以看出，unique独一无二，这种插入方法不允许出现重复数据。

##### multiset源码 #####

![这里写图片描述][20161113133633521]  
（ps：注意红色箭头指向的内容，意思是其他函数的实现，multise与set相同）  
可以看出不同了吧，multiset底层调用的insert\_equal()这个函数。equal什么意思呢？英语不好的就去查吧！^v^!

#### erase ####

##### set的erase三种实现。 #####

void erase ( iterator position );

指定位置擦除，参数为一个迭代器，意思是擦拭position位置的数据。  
2.

size_type erase ( const key_type& x );

指定元素擦除，参数为一个数据，意思是擦除键值（key）为x的数据。  
3.

void erase ( iterator first, iterator last );

指定区间擦除，擦除左闭右开区间（first，last）的元素。

##### multiset的erase #####

我们已经知道了，multiset允许插入相同的元素，删除呢？  
1.

void erase ( iterator position );

指定位置删除，与set相同  
2.

void erase ( iterator first, iterator last );

删除区间 \[first，last）,与set相同。  
3.  
不同的来了！

size_type erase ( const key_type& x );

指定元素删除，删除参数x。删除key等于x的*所有元素*。返回删除元素的个数。

#### clear ####

void clear ( );

清空所有元素，它内部调用的红黑树的clear。

#### swap ####

void swap ( set<Key,Compare,Allocator>& st );

交换两个set的值，返回值为空，参数是另一个set的引用。

### Observers ###

#### key\_comp ####

key_compare key_comp ( ) const;

这个方法的功能是返回set排序所调用的比较函数。返回值是key\_compare，什么是key\_compare呢？  
查看key\_compare的定义，发现它是\_Pr的一个typedef

![这里写图片描述][20161113115656622]

再查看\_Pr的定义，

![这里写图片描述][20161113115831348]

![这里写图片描述][20161113120040045]

到这里我们就能看到，\_Pr是一个名为less的类型。再查看less的定义。  
一目了然了吧，less就是一个结构体，它内部实现了对()的重载，功能是比较两个值得大小,left小于right的时候返回true。当把这个结构体类型传入当模版参数时，在类内部就可以以仿函数的形式调用它。  
再回来说到，key\_compare就是一个类型，key\_comp的返回值就是set的比较函数，也可以说是底层红黑树的比较函数。当然我们还可以调用这个比较函数。我们来测一下：

set<int>::key_compare ret2 = s.key_comp();
    cout << "less:1<2?" << endl;
    cout << ret2(1, 2) << endl;
    cout << "less:1>2?" << endl;
    cout << ret2(2, 1) << endl;

结果：  
![这里写图片描述][20161113121507832]

#### value\_comp ####

set的key和value都是同一个值，都是键值（key），所以这个函数与key\_comp的功能一样，返回值也相同。

### Operations ###

#### find ####

iterator find ( const key_type& x ) const;

查找一个值x的位置，返回值为迭代器。const保证这个函数内部不对类的成员做出修改。  
当这个值x存在时，返回这个值的迭代器。  
当这个值x不存在时，返回end（最后一个元素的下一个位置），end是一个不可访问的位置。

set/multiset的find的find函数功能都相同，返回的都是指向第一个匹配元素位置的迭代器。

#### count ####

size_type count ( const key_type& x ) const;

查找一个元素是否存在。返回值类型为size\_type（我们理解为size\_t）

如果元素存在，返回元素的个数。  
如果元素不存在，返回0。  
思考：既然set里面不允许出现相同的元素，次数只能是0或1，为什么它要用一个size\_type来接收返回值？为什么不用bool？

因为multiset与set的count函数相同，底层都是调用的红黑树的count函数，multiset允许重复数据出现，那就有大于1的次数。所以用size\_type。

#### lower\_bound ####

iterator lower_bound ( const key_type& x ) const;

返回值是一个迭代器，返回指向set中第一个大于等于x的值的迭代器。当没有比x大的元素的时候，返回end。  
看一个例子：  
我插入的原始数据为 1， 3， 5， 7 ，9

set<int> s;
        for (int i = 1; i < 10; i+=2)
        {
            s.insert(i);
        }
        set<int>::iterator it = s.begin();
        while (it != s.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        cout << "lower_bound: 大于等于0的第一个元素" << endl;
        cout << *(s.lower_bound(0)) << endl;
        cout << "lower_bound: 大于等于1的第一个元素" << endl;
        cout << *(s.lower_bound(1)) << endl;
        cout << "lower_bound: 大于等于2的第一个元素" << endl;
        cout << *(s.lower_bound(2)) << endl;
        cout << "lower_bound: 大于等于3的第一个元素" << endl;
        cout << *(s.lower_bound(4)) << endl;
        cout << "lower_bound: 大于等于4的第一个元素" << endl;
        cout << *(s.lower_bound(6)) << endl;

结果：  
![这里写图片描述][20161113125635551]

#### upper\_bound ####

iterator upper_bound ( const key_type& x ) const;

返回指向第一个大于x的值的迭代器，例子不再给出，测试方法与上相同。

#### equal\_range ####

pair<iterator,iterator> equal_range ( const key_type& x ) const;

返回值为一个pair，pair的两个值都是迭代器，这个函数的功能是上面两个函数的结合体。找到指向第一个大于等于x的值的迭代器，存到pair的first里面去。找到指向第一个大于x的值的迭代器，存到pair的second里面去。

看一个例子，插入数据1，3，5，7，9

set<int> s;
    for (int i = 1; i < 10; i += 2)
    {
        s.insert(i);
    }
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    pair<set<int>::iterator, set<int>::iterator> ret = s.equal_range(3);
    cout << "pair.first:lower_bound:" << *ret.first << endl;
    cout << "pair.second:upper_bound:" << *ret.second << endl;

结果：  
![这里写图片描述][20161113130842464]

### Allocator ###

空间配置器等我搞明白了再写出来。。。。。

[20161113152417365]: /images/20220715/5a94f16fd822449692ea6bebac255459.png
[20161113100150195]: /images/20220715/f648e300e071415fbd06db167b729b6f.png
[20161113133019796]: /images/20220715/fdfb7035c68a4369ac6d36ef5a174097.png
[20161113133633521]: /images/20220715/af9e22df431041c3b434bac939ce285a.png
[20161113115656622]: /images/20220715/044a9f86a7ab422b93f56518a4141dc0.png
[20161113115831348]: /images/20220715/99ace1d349a349d497955efe0707784c.png
[20161113120040045]: /images/20220715/693960fc274e4c58a7dd9b3cba422305.png
[20161113121507832]: /images/20220715/ad7e8cfdf8564aafbc30f5611d989558.png
[20161113125635551]: /images/20220715/d4041411ec6445e69a65a45c84078fc5.png
[20161113130842464]: /images/20220715/b5773a40777047219737623f02836142.png