Cpp

set

scorlw 发布于

set

c++

一、关于set

1）为何map和set的插入删除效率比其他序列容器高？

因为对于关联容器来说，不需要做内存拷贝和内存移动。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：

1
2
3
4
5
   A
 /   \
 B    C
/ \  / \
D  E F G

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

2）为何每次insert后，以前保存的iterator不会失效？

iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。

相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

3）当数据元素增多时，set的插入和搜索速度变化如何？

在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。

二、set中的常用方法

1）基础函数

1
2
3
4
5
6
7
8
begin()     　　 ,返回set容器第一个元素的迭代器
end() 　　　　 ,返回一个指向当前set末尾元素的下一位置的迭代器.
clear()   　　     ,删除set容器中的所有的元素
empty() 　　　,判断set容器是否为空
max_size() 　 ,返回set容器可能包含的元素最大个数
size() 　　　　 ,返回当前set容器中的元素个数
rbegin()　　　　 ,返回的值和end()相同
rend()　　　　 ,返回的值和begin()相同

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout << "set 的 size 值为 ：" << s.size() << endl;
    cout << "set 的 maxsize的值为 ：" << s.max_size() << endl;
    cout << "set 中的第一个元素是 ：" << *s.begin() << endl;
    cout << "set 中的最后一个元素是:" << *s.end() << endl;
    s.clear();
    if (s.empty())
    {
        cout << "set 为空 ！！！" << endl;
    }
    cout << "set 的 size 值为 ：" << s.size() << endl;
    cout << "set 的 maxsize的值为 ：" << s.max_size() << endl;
    system("pause");
    return 0;
}

I/O:

1
2
3
4
5
6
7
set 的 size 值为 ：3
set 的 maxsize的值为 ：461168601842738790
set 中的第一个元素是 ：1
set 中的最后一个元素是:3
set 为空 ！！！
set 的 size 值为 ：0
set 的 maxsize的值为 ：461168601842738790

小结：插入3之后虽然插入了一个1，但是我们发现set中最后一个值仍然是3，这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.

2）计数count()

用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>
 
using namespace std;
 
int main()
{
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(1);
	cout<<"set 中 1 出现的次数是 ："<<s.count(1)<<endl;
	cout<<"set 中 4 出现的次数是 ："<<s.count(4)<<endl;
	return 0;
}

I/O:

1
2
set 中 1 出现的次数是 ：1
set 中 4 出现的次数是 ：0

3）equal_range()

equal_range()是c++ STL中一种二分查找的方法。set中包含了自己的equal_range()函数。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    set<int> s;
	set<int>::iterator iter;
	for(int i = 1 ; i <= 5; ++i)
	{
		int x;
		scanf("%d",&x);
		s.insert(x); //向set中加入数据
	}
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout << *iter << " ";  //输出set中的数据
	}
	cout<<endl;
	pair<set<int>::const_iterator,set<int>::const_iterator> pr;
	pr = s.equal_range(3);
	cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
	cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
    system("pause");
    return 0;
}

I\O：

1
2
3
4
5
6
7
8
9
10
输入：
1
1
2
2
4
输出：
1 2 4
第一个大于等于 3 的数是 ：4
第一个大于 3的数是 ： 4

4）删除erase()

1
2
3
erase(iterator)         ,删除定位器iterator指向的值
erase(first,second) ,删除定位器first和second之间的值
erase(key_value)    ,删除键值key_value的值

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int main()
{
    set<int> s;
	set<int>::iterator it;
	set<int>::const_iterator iter;
	set<int>::iterator first;
	set<int>::iterator second;
	for(int i = 1 ; i <= 10 ; ++i)
	{
		s.insert(i);
		cout << i << "  " ;
	}
	cout << endl;
    //方法一
	it = s.begin();
	cout << "第一次删除的是：" << *it << endl;
	s.erase(it);
	cout << "第一种删除之后 ："  << endl; 
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout<<*iter<<" ";
	}
	cout << endl;
    cout << "此时it指向：" << *it << endl;
    cout << "此时s的第一个元素是：" << *s.begin() << endl;
    //方法二
	first = s.begin();
	second = s.begin();
	second++;
	second++;
	cout << "l == " << *first  << "  r == " << *second << endl;
	cout << "第二种删除之后 ："  << endl; 
	s.erase(first,second);
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout<<*iter<<" ";
	}
	cout << endl;
    //方法三
	s.erase(8);
	cout << "第三次删除的是： 8" << endl;
	cout<<"	第三种删除后 set 中元素是 ：";
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout<<*iter<<" ";
	}
	cout << endl;
    system("pause");
    return 0;
}

IO：

1
2
3
4
5
6
7
8
9
10
11
1  2  3  4  5  6  7  8  9  10
第一次删除的是：1
第一种删除之后 ：
2 3 4 5 6 7 8 9 10
此时it指向：-17891602
此时s的第一个元素是：2
l == 2  r == 4
第二种删除之后 ：
4 5 6 7 8 9 10
第三次删除的是： 8
第三种删除后 set 中元素是 ：4 5 6 7 9 10

小结：set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。第二种删除是左闭右开[ l, r);

5）查找find()

返回给定值的定位器，如果没找到则返回end()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    int a[] = { 4, 6, 2 , 3};
	set<int> s(a,a + 4);//set的一种赋值方法
	set<int>::iterator iter;
	for(iter = s.begin();iter != s.end();iter++)
	{
		cout << *iter << "  " ;
	}
	cout << endl;
	if((iter = s.find(2)) != s.end())
		cout<<"find" << *iter<<endl;
	if((iter = s.find(1)) != s.end())
		cout<<*iter<<endl;
    system("pause");
    return 0;
}

IO：

1
2
2  3  4  6
find2

小结：find(x)是返回的是x的值，如果x没有在set中则会输出end()；

set的迭代器是不支持加减法的，见迭代器的加减法。

set实现自排序。

6）插入insert()

insert(key_value); 将key_value插入到set中 ，返回值是pair<set::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。

inset(first,second); 将定位器first到second之间的元素插入到set中，返回值是void.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main()
{
    int a[] = {1, 4, 3, 7};
	set<int> s;
	set<int>::iterator iter;
	s.insert(a,a + 4);//方法二
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout<<*iter<<" ";
	}
	cout<<endl;
	pair<set<int>::iterator,bool> pr;
	pr = s.insert(5);//方法一
	if(pr.second)
	{
		cout<<*pr.first<<endl;
	}
	cout << "插入数值之后的set中有：" << endl;
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout<<*iter<<" ";
	}
	cout<<endl;
    system("pause");
    return 0;
}

IO:

1
2
3
4
1 3 4 7
5
插入数值之后的set中有：
1 3 4 5 7

7）上下界查找

lower_bound(key_value) ，返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于key_value的定位器

没有就返回end()-1。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    set<int> s;
	for(int i = 1;i <= 5;i ++)
	{
		int x;
		cin >> x;
		s.insert(x);
	}
	set<int>::iterator iter;
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;
	cout << "第一个大于等于 2 的值是:   ";
		cout<<*s.lower_bound(2)<<endl;
	cout << "第一个大于等于 3 的值是:   ";
		cout<<*s.lower_bound(3)<<endl;
	cout << "第一个大于 3 的值是:   ";
		cout<<*s.upper_bound(3)<<endl;
    system("pause");
    return 0;
}

IO:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输入：
    1
    2
    3
    4
    5
输出：
    1 2 3 4 5
第一个大于等于 2 的值是:   2
第一个大于等于 3 的值是:   3
第一个大于 3 的值是:   4
    
输入：
    1
    2
    2
    1
    1
输出：
    1 2
第一个大于等于 2 的值是:   2
第一个大于等于 3 的值是:   2
第一个大于 3 的值是:   2

三、自定义比较函数

1)结构体对象

如果对象是个结构体，可以在结构体里直接运算符重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct People  
{  
    string name;  
    int age;  
    bool operator <(const People p) const  //运算符重载   
    {  
        return age<p.age;       //按照年龄由小到大进行排序   
    }  
}; 

int main()
{
    set<People>s;  
    s.insert((People){"张三",14});  
    s.insert((People){"李四",16});  
    s.insert((People){"王二",10});  
    set<People>::iterator it;              
    for(it=s.begin();it!=s.end();it++)  //使用迭代器进行遍历   
    {  
        printf("姓名：%s 年龄：%d\n",(*it).name.c_str(),(*it).age);  
    }
    system("pause");
    return 0;
}

IO：

1
2
3
姓名：王二 年龄：10
姓名：张三 年龄：14
姓名：李四 年龄：16

2）非结构体对象

如果对象是非结构体（如class），则可以重载()运算符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class CTest
{
public:
    CTest()
    {
        num = 0;
        str = "";
    }
    CTest(int _num, string _str)
    {
        num = _num;
        str = _str;
    }
    string str;
    int num;
};

class CTestCmp
{
public:
    bool operator()(const CTest &lc, const CTest &rc)
    {
        return !!(lc.num < rc.num);//双叹号的目的是把非零值转换为1
        //return !!(lc.str < rc.str);
    }
};

typedef set<CTest, CTestCmp> CTestSet;

void OutputCTestSet(const CTestSet &_set)
{
    cout << "Set [" << endl;
    for (CTestSet::iterator it = _set.begin(); it != _set.end(); ++it)
    {
        cout << "str:" << it->str << ", num:" << it->num << endl;
    }
    cout << "]" << endl;
}

int main()
{
    CTestSet _set;
    _set.insert(CTest(2, "hello"));
    _set.insert(CTest(1, "world"));
    _set.insert(CTest(3, "blowing"));
    OutputCTestSet(_set);
    system("pause");
    return 0;
}

IO:

1
2
3
4
5
Set [
str:world, num:1
str:hello, num:2
str:blowing, num:3
]

原文地址：https://blog.csdn.net/Strawberry_595/article/details/81188509