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

  • Post author:
  • Post category:其他




底层实现:红黑树

在这里插入图片描述



查找效率

因为是二叉树,且是比较平衡的二叉查找树,所以查找效率自然是很好的,



O

(

log

n

)

O(\log n)






O


(


lo

g





n


)





,用的是二分查找

在这里插入图片描述

随着元素数目的增多,即横坐标x增大,纵坐标,即查找次数



y

=

log

2

x

y=\log_2 x






y




=









lo

g











2




















x





,增大的越来越缓慢,所以集合不担心元素过多。

在这里插入图片描述



迭代器的值不会变

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

在这里插入图片描述



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

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

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



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

  • set,map,multiset, mutilmap都是用红黑树实现的,是STL对二叉树的封装,他们的迭代器只支持递增递减运算,不可以加减整数!!!

    s.end()-1

    会编译错误。

在这里插入图片描述

原来只有

内存连续

的容器的迭代器可以加减,

双端队列的底层用的vector实现

,所以也是连续内存,不是用链表实现的,注意哦。

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



成员方法

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述



初始化

  • 初始化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(),但是这

并不能阻止他指向的元素被删除


在这里插入图片描述



自定义set的排序函数

在这里插入图片描述

我们自己定义排序函数,需要写一个结构体(相当于类,用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



版权声明:本文为qq_36607894原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。