Wiki

set / multiset containers

Updated 2023-10-05About 8 min read

Existing English translations were reused. 1 current source blocks remain in Simplified Chinese, without triggering paid translation.

1.set/ multiset 容器

1.1.Basic concepts of set

Introduction:

All elements are automatically sorted upon insertion.

Essence:

set/multiset belongs toassociative containersand its underlying structure is implemented using abinary tree.

Difference between set and multiset:

set does not allow duplicate elements in the container
multiset allows duplicate elements in the container

1.2.set construction and assignment

Function description: create a set container and assign values

Construction:

set<T> st; // Default constructor:
set(const set &st); // Copy constructor

Assignment:

set& operator=(const set &st); // Overload the assignment operator

Example:

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//构造和赋值
void test01()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//拷贝构造
	set<int>s2(s1);
	printSet(s2);

	//赋值
	set<int>s3;
	s3 = s2;
	printSet(s3);
}

int main() {

	test01();


	return 0;
}

Operation result:

10 20 30 40
10 20 30 40
10 20 30 40

Summary:

When inserting data into a set container, use insert.
Data inserted into a set container is automatically sorted.

1.3.set size and swap

Function description:

Obtain the size of a set container and swap set containers

Function prototype:

size(); // Returns the number of elements in the container
empty(); // Determines whether the container is empty
swap(st); // Swaps two set containers

Example:

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//大小
void test01()
{

	set<int> s1;
	
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	if (s1.empty())
	{
		cout << "s1为空" << endl;
	}
	else
	{
		cout << "s1不为空" << endl;
		cout << "s1的大小为： " << s1.size() << endl;
	}

}

//交换
void test02()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	set<int> s2;

	s2.insert(100);
	s2.insert(300);
	s2.insert(200);
	s2.insert(400);

	cout << "交换前" << endl;
	printSet(s1);
	printSet(s2);
	cout << endl;

	cout << "交换后" << endl;
	s1.swap(s2);
	printSet(s1);
	printSet(s2);
}

int main() {

	//test01();

	test02();


	return 0;
}

Operation result:

交换前
10 20 30 40
100 200 300 400

交换后
100 200 300 400
10 20 30 40

Summary:

Statistical size --- size
Determine whether it is empty --- empty
Swap containers --- swap

1.4.set insertion and deletion

Function description:

Insert and delete data in a set container

Function prototype:

insert(elem); //Insert elements into the container.
clear(); //Clear all elements
erase(pos); //Delete the element pointed to by the iterator pos, and return an iterator to the next element.
erase(beg, end); //Delete all elements in the range [beg,end), and return an iterator to the next element.
erase(elem); //Delete the element with value elem from the container.

Example:

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//插入和删除
void test01()
{
	set<int> s1;
	//插入
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//删除
	s1.erase(s1.begin());
	printSet(s1);

	s1.erase(30);
	printSet(s1);

	//清空
	//s1.erase(s1.begin(), s1.end());
	s1.clear();
	printSet(s1);
}

int main() {

	test01();


	return 0;
}

Operation result:

10 20 30 40
20 30 40
20 40

Summary:

Insert --- insert
Delete --- erase
Clear --- clear

1.5.set lookup and statistics

Function description:

Search for data in the set container and collect statistics

Function prototype:

find(key); //Check whether the key exists. If it exists, return an iterator to the element for that key; if it does not exist, return set.end();
count(key); //Count the number of elements for the key

Example:

#include <iostream>
#include <set>

using namespace std;

//查找和统计
void test01()
{
	set<int> s1;
	//插入
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	
	//查找
	set<int>::iterator pos = s1.find(30);

	if (pos != s1.end())
	{
		cout << "找到了元素 ： " << *pos << endl;
	}
	else
	{
		cout << "未找到元素" << endl;
	}

	//统计
	int num = s1.count(30);
	cout << "num = " << num << endl;
}

int main() {

	test01();


	return 0;
}

Operation result:

找到了元素 ： 30
num = 1

Summary:

find --- find (returns an iterator)
count --- count (for set, the result is 0 or 1)

1.6.Difference between set and multiset

Learning Objectives:

Master the difference between set and multiset

Difference:

set cannot insert duplicate data, whereas multiset can
When set inserts data, it also returns the insertion result, indicating whether the insertion was successful
multiset does not check data, so duplicate data can be inserted

Example:

#include <iostream>
#include <set>

using namespace std;

//set和multiset区别
void test01()
{
	set<int> s;
	pair<set<int>::iterator, bool>  ret = s.insert(10);
	if (ret.second) {
		cout << "第一次插入成功!" << endl;
	}
	else {
		cout << "第一次插入失败!" << endl;
	}

	ret = s.insert(10);
	if (ret.second) {
		cout << "第二次插入成功!" << endl;
	}
	else {
		cout << "第二次插入失败!" << endl;
	}
    
	//multiset
	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);

	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();


	return 0;
}

Operation result:

第一次插入成功!
第二次插入失败!
10 10

Summary:

If duplicate data is not allowed to be inserted, set can be used.
If duplicate data needs to be inserted, multiset can be used.

1.7.pair group creation

Function description:

For data that appears in pairs, pairs can be used to return two pieces of data

Two creation methods:

pair<type, type> p ( value1, value2 );
pair<type, type> p = make_pair( value1, value2 );

Example:

#include <iostream>
#include <string>

using namespace std;

//对组创建
void test01()
{
	pair<string, int> p(string("Tom"), 20);
	cout << "姓名： " <<  p.first << " 年龄： " << p.second << endl;

	pair<string, int> p2 = make_pair("Jerry", 10);
	cout << "姓名： " << p2.first << " 年龄： " << p2.second << endl;
}

int main() {

	test01();


	return 0;
}

Operation result:

姓名： Tom 年龄： 20
姓名： Jerry 年龄： 10

Summary:

Both methods can create a peer group; just remember one of them.

1.8.Sorting a set container

Learning objectives:

The default sorting rule of the set container is from smallest to largest; master how to change the sorting rule.

Key technical points:

Using a functor, the sorting rule can be changed.

Example 1 set stores built-in data types

#include <iostream>
#include <set>

using namespace std;

class MyCompare 
{
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() 
{    
	set<int> s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(30);
	s1.insert(50);

	//默认从小到大
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//指定排序规则
	set<int,MyCompare> s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(30);
	s2.insert(50);

	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();


	return 0;
}

Result: Compilation failed: the comparison functor's operator() lacks a const qualifier, so modern standard libraries cannot call it on a const comparator object.

Summary: Functors can be used to specify the sorting rule of the set container.

Example 2 Storing custom data types in a set

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

using namespace std;

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

	string m_Name;
	int m_Age;

};
class comparePerson
{
public:
	bool operator()(const Person& p1, const Person &p2)
	{
		//按照年龄进行排序  降序
		return p1.m_Age > p2.m_Age;
	}
};

void test01()
{
	set<Person, comparePerson> s;

	Person p1("刘备", 23);
	Person p2("关羽", 27);
	Person p3("张飞", 25);
	Person p4("赵云", 21);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
	}
}
int main() {

	test01();


	return 0;
}

Result: Compilation failed: the comparison functor's operator() lacks a const qualifier, so modern standard libraries cannot call it on a const comparator object.

Summary:

For custom data types, set must specify a sorting rule before data can be inserted.