C++中set/multiset容器_c++ set 会自动排序吗

1.

set/multiset容器是一个可以自动排序的容器，所有所有元素都会在插入时自动被排序，set/multiset属于关联式容器，底层结构是用二叉树实现的；这连个也有一定的区别，set不允许容器中有重复的元素，所以在插入值相同元素的时候就会被舍弃掉，而multiset允许容器中有重复的元素。
赋值和构造:

set st;//默认构造函数；
set(const set & st); //拷贝构造函数
set & operator=(const set &st);//重载等号操作符

set <T> s;	//默认构造
set <T> s1（s）;	//拷贝构造构造
set <T>s2 = s1;	//赋值

1
2
3
4

下面是set容器中常见的方法

begin()	返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
find(val)	在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)	返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)	返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 set 容器中存有元素的个数。不支持resize
max_size()	返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
insert()	向 set 容器中插入元素。
erase()	删除 set 容器中存储的元素。
swap()	交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。
clear()	清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。
emplace()	在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
count(val)	在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里说明一下：当set/multiset容器存储对象的时候需要指定排序规则，要提供一个仿函数，也就是一个类中只包含对（）进行重载，并且参数限定为const，同样也适用于普通非对象元素:
例如：

class compare1
{
public:
	bool operator()(int a,int b)const
	{
		return a > b; 
	}
};

void Print(set<int,compare1> &s)
{
	for(set<int,compare1>::iterator it = s.begin();it != s.end();it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}
...
//用法：
set <int,compare1> s;

/***********************************************************************************************************************/
class Person{
public:
	Person(string nam,int ag)
	{
		this->name = nam;
		this->age = ag;
	}
	string name;
	int age;

};
class Compare
{
public:
	bool operator()(const Person& p1,const Person& p2) const//一定要定义为常函数，且参数需要限定为const
	{
			return p1.age > p2.age;
	}
};
...

//用法：
set <Person,Compare> s1;

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

这样子的话就可以

还有就是set的insert的原型：

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

1
2

返回布尔对以表示是否发生插入，如果重复插入一个元素会返回false。返回迭代器指向新插入元素;而multiset则只返回迭代器，不反回bool类型的插入结果
pair对组在后面的文章中再总结，这里就不展开了

整体代码例子：

#include <iostream>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

class compare1
{
public:
	bool operator()(int a,int b)const
	{
		return a > b; 
	}
};
void Print(set<int> &s)
{
	for(set<int>::iterator it = s.begin();it != s.end();it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

void Print(set<int,compare1> &s)
{
	for(set<int,compare1>::iterator it = s.begin();it != s.end();it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}
void mPrint(multiset<int> &s)
{
	for(multiset<int>::iterator it = s.begin();it != s.end();it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}
void test01(void)
{
	set <int> s1;
	multiset <int> ms1;
	

	if(s1.empty())
	{
		cout << "s1 is empty" << endl;
	}
	else
	{
		cout << "s1 is not empty" << endl;
	}

	if(ms1.empty())
	{
		cout << "ms1 is empty" << endl;
	}
	else
	{
		cout << "ms1 is not empty" << endl;
	}

	s1.insert(50);
	s1.insert(30);
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	
	s1.insert(20);	//	重复的元素无效

	Print(s1);

	set <int> s2(s1);
	cout << "交换前："<<endl;
	Print(s2);

	set <int> s3;
	s3.insert(600);
	s3.insert(400);
	s3.insert(200);
	s3.insert(300);
	s3.insert(100);
	s3.insert(700);
	
	Print(s3);
	cout << "大小： "<< endl;
	cout << s3.size() << endl;

	cout << "统计个数： "<<endl;
	cout << s3.count(600) << endl;
	
	cout << "在s3里查找600："<<endl;
	cout << *(s3.find(600)) << endl;

	s2.swap(s3);
	cout << "交换后："<<endl;
	Print(s2);
	Print(s3);

	cout << "使用具体的值删除s2中的100:  " << endl;
	s2.erase(100);
	Print(s2);

	cout << "使用迭代器begin: "<< endl;
	s2.erase(s2.begin());
	Print(s2);

	cout << "迭代器清空s2:  " <<endl;
	s2.erase(s2.begin(),s2.end());
	Print(s2);

	cout << "使用clear函数s3："<<endl;
	s3.clear();
	Print(s3);

	cout << "multiset :  "<< endl;
	ms1.insert(50);
	ms1.insert(30);
	ms1.insert(10);
	ms1.insert(40);
	ms1.insert(20);

	ms1.insert(20);	//	重复的元素有效

	mPrint(ms1);

	multiset <int> ms2(ms1);
	mPrint(ms2);
	cout << "统计个数： "<<endl;
	cout << ms1.count(20) << endl;
	
	if(s1.empty())
	{
		cout << "s1 is empty" << endl;
	}
	else
	{
		cout << "s1 is not empty" << endl;
	}

	if(ms1.empty())
	{
		cout << "ms1 is empty" << endl;
	}
	else
	{
		cout << "ms1 is not empty" << endl;
	}

	cout << "s1的大小: "<< s1.size() << endl;
	cout << "ms1的大小：" << ms1.size() << endl;
	
	cout << "指定排序规则: " <<endl;
	set <int,compare1> s5;
	s5.insert(1000);
	s5.insert(8000);
	s5.insert(3000);
	s5.insert(5000);
	s5.insert(2000);
	s5.insert(7000);
	s5.insert(4000);
	Print(s5);



}

class Person{
public:
	Person(string nam,int ag)
	{
		this->name = nam;
		this->age = ag;
	}
	string name;
	int age;

};

class Compare
{
public:
	bool operator()(const Person& p1,const Person& p2) const//一定要定义为常函数，且参数需要限定为const
	{
			return p1.age > p2.age;
	}
};

void Print(set<Person,Compare> &s)                                                                                                                         
{
    for(set<Person,Compare>::iterator it = s.begin();it != s.end();it++)
    {
        cout << "name: " << it->name  << "age: " << it->age <<endl;
    }
    cout << endl;
}

void mPrint(multiset<Person,Compare> &s)
{
    for(multiset<Person,Compare>::iterator it = s.begin();it != s.end();it++)
    {
        cout << "name: " << it->name  << "age: " << it->age <<endl;
    }
    cout << endl;
}


void test02(void)
{
	cout << "set 存储对象:  "<<endl; 
	Person p1("唐僧",10);
    Person p2("八戒",30);
    Person p3("沙僧",20);
    Person p4("悟空",9);
    Person p5("白骨精",200);

	set <Person,Compare> s1;
	s1.insert(p1);
	s1.insert(p2);
	s1.insert(p3);
	s1.insert(p4);
	Print(s1);
	cout << "s1的大小：" << s1.size()<<endl;

	cout << "统计个数： "<<endl;
	cout << s1.count(p1) << endl;

	cout << "在s1里查找p1："<<endl;
	set <Person,Compare>::iterator it = s1.find(p1);
	cout << it->name << "   "<< it->age<< endl;

	pair <set<Person,Compare>::iterator,bool> ret = s1.insert(p5);	
	if(ret.second)
	{
		cout <<"insert successed"<<endl;
	}
	else
	{
		cout << "insert failed" << endl;
	}
	Print(s1);
	ret = s1.insert(p5);//这里如过是multiset的花就会插入成功,这里就不演示了

	if(ret.second)
	{
		cout <<"insert successed"<<endl;
	}
	else
	{
		cout << "insert failed" << endl;
	}

}

int main(void)
{
	test01();
	test02();
	return 0;
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263