STL容器之 set(原理，成员函数)

缺乏、安全感 2022-11-24 14:20 241阅读 0赞

### 文章目录 ###

*  底层实现：红黑树
 *   *  查找效率
     *  迭代器的值不会变
     *  为什么set, map等的插入效率比vector，deque高
 *  不可以加减运算，只能递增递减，因为内存不连续
 *  成员方法
 *   *  初始化
     *  clear()
     *  erase()
 *  自定义set的排序函数

# 底层实现：红黑树 #

![在这里插入图片描述][20200806152759908.png]

## 查找效率 ##

因为是二叉树，且是比较平衡的二叉查找树，所以查找效率自然是很好的， O ( log ⁡ n ) O(\\log n) O(logn),用的是二分查找  
![在这里插入图片描述][20200806153510956.png]  
随着元素数目的增多，即横坐标x增大，纵坐标，即查找次数 y = log ⁡ 2 x y=\\log\_2 x y=log2x,增大的越来越缓慢，所以集合不担心元素过多。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

## 迭代器的值不会变 ##

这是内存不连续的容器的共同好处，因为大家都是用的链表的方式，不会遇到内存不够了再开一块更大内存集体搬家的情况。而连续内存的vector， deque等就有可能集体搬家，于是造成迭代器失效。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]

## 为什么set, map等的插入效率比vector，deque高 ##

因为set和map等用的是红黑树，即高度平衡的二叉查找树，本质是用链表的方式存储的（二叉链表），所以不会遇到内存不够用又重新开一块大内存然后集体搬家的情况，而vector的push\_back就有可能造成这种情况，所以效率低一些。

链表的插入本就是O(1)复杂度，平衡二叉树的插入是O(log n)复杂度，因为最多比较log n次。

# 不可以加减运算，只能递增递减，因为内存不连续 #

*  set，map,multiset, mutilmap都是用红黑树实现的，是STL对二叉树的封装，他们的迭代器只支持递增递减运算，不可以加减整数！！！`s.end()-1`会编译错误。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]  
原来只有内存连续的容器的迭代器可以加减，**双端队列的底层用的vector实现**，所以也是连续内存，不是用链表实现的，注意哦。

原来++i和i++是这么个区别，那效率差别还是很大的呢。i++加完了以后，要返回临时对象，但是返回的临时对象又不赋值所以无用，就会被立即销毁，所以还不如直接用++i,返回引用的效率高得多。

# 成员方法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][20200806152505583.png]  
![在这里插入图片描述][20200806152546496.png]  
![在这里插入图片描述][20200806152557876.png]

## 初始化 ##

*  初始化set容器:`std::set<int>myset{1,2,3,4,5};`,注意STL中这些容器都是时限为类模板的，需要用尖括号把类型参数传进去

int a[] = { 20,10,30,40,50};
    set<int> s(a, a + 5);//可以用内置数组初始化

## clear() ##

*  清空set容器直接用clear成员方法，不需要传入任何参数，也没有任何返回值。。清空后，s.size()变为0。

## erase() ##

*  set 类模板中，erase() 方法有 3 种语法格式

size_type erase (const value_type & val);//删除 set 容器中值为 val 的元素，返回值为一个整数，表示成功删除的元素个数
    iterator erase (const_iterator position);//删除 position 迭代器指向的元素
    //返回迭代器指向的是 set 容器中删除元素之后的第一个元素
    iterator erase (const_iterator first, const_iterator last);//删除 [first,last) 区间内的所有元素
    //返回迭代器指向的是 set 容器中删除元素之后的第一个元素
    //注意第二个参数last指向的元素不会删除

使用示例程序

#include <iostream>
    #include <set>
    using namespace std;
    void showSet(const std::set<int> & s)
    { 
        for (auto it=s.cbegin();it!=s.cend();++it)
            cout << *it << ' ';
        cout << endl;
        cout << "s.size() = " << s.size() << endl;
    }
    int main()
    { 
        std::set<int> s { 1, 2, 3, 4, 5};//初始化
        showSet(s);
    
        int n = s.erase(3);//第一种原型，删掉元素3
        showSet(s);
        cout << "n = " << n << endl << endl;
    
        auto it1 = s.erase(s.cbegin());//第二种原型
        showSet(s);
        cout << "*it1 = " << *it1 << endl << endl;
    
        auto it2 = s.erase(s.cbegin(), --s.cend());//第三种原型,注意第二个参数指向的元素不会删除,如果传入的第二个参数不是--s.end()而是s.end(),则set的元素会被全部删掉
        showSet(s);
        cout << "*it2 = " << *it2 << endl;
        
    	return 0;
    }

1 2 3 4 5
    s.size() = 5
    1 2 4 5
    s.size() = 4
    n = 1
    
    2 4 5
    s.size() = 3
    *it1 = 2
    
    5
    s.size() = 1
    *it2 = 5

注意我的代码里用了cbegin()，但是这并不能阻止他指向的元素被删除  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]

# 自定义set的排序函数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]  
我们自己定义排序函数，需要写一个结构体（相当于类，用class关键字也可以），在里面定义一个重载圆括号运算符的const成员函数，由于只是排序，不改动元素，所以传入的两个参数都设置为const引用。

自己写个性化的排序定义，返回值是bool类型，return的条件就是排序的说明方法

#include <iostream>
    #include <string>
    #include <set>
    using namespace std;
    
    struct intComp { 
    	bool operator() (const int& lhs, const int& rhs) const{ 
    		return lhs > rhs;//则数值大的排在前面，即降序排列
    	}
    };
    
    struct strComp
    { 
    	bool operator() (const string& str1, const string& str2) const { 
    		return str1.length() < str2.length();//则长度短的字符串排在前面
    	}
    };
    
    int main() { 
    	int a[] = { 10, 20, 30, 40, 50};
    	set<int, intComp> s1(a, a + 5);
    	for (auto it = s1.cbegin(); it != s1.cend(); it++)
    	{ 
    		cout << *it << " ";
    	}
    	cout << endl;
    
    	string b[] = { "apple", "banana", "pear", "orange", "strawberry"};
    	set<string, strComp > s2(b, b + 5);
    	for (auto it = s2.cbegin(); it != s2.cend(); it++)
    	{ 
    		cout << *it << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }

50 40 30 20 10
    pear apple banana strawberry

[20200806152759908.png]: /images/20221124/acf8d0cebb004b1c895367c92422600e.png
[20200806153510956.png]: /images/20221124/3770fcadd6c44c34bb19a8d01a23836e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: /images/20221124/e38a61f7e81a4cee8c2647443bf685f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: /images/20221124/f672240ab2d140158d9b8c22377638b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: /images/20221124/49a0b3acc9404db2b959ce3571512f71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: /images/20221124/4b55c674b15947f0adddd0b8bd732b11.png
[20200806152505583.png]: /images/20221124/59e04a7d473944da8eaf0a089b465bdc.png
[20200806152546496.png]: /images/20221124/6b543f4e5b0445f487897aa26a8a5a29.png
[20200806152557876.png]: /images/20221124/f003234ab8044cda992775e277a47f44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: /images/20221124/a86bab5992644020b6722dd08b5935cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]: /images/20221124/37ec4cafc126436c9aa29a0301031ec6.png