Set Structures in C++

Learn: In this article we understand the function and features of set data type present in C++ standard library. We understand how to use set data type and when we have to use it. We understand the benefits of set data type. We understand the use of multiset.
Submitted by Amit Shukla, on October 04, 2017

A set is a data structure present in standard library of C++, it is used to maintains the collection of elements in a particular data type.

Following are the basic operations of any set data type:

Insertion
Deletion
Searching

The C++ standard library contains two set implementations:

The structureset is based on a balanced binary tree and its operations work in O(log_n) time.
The structure unordered set uses hashing, and its operations work in O(1) timeon average.

The choice of which set implementation to use is often a matter of taste. The benefit of the set structure is that it maintains the order of the elements and provides functions that are not available in unordered set. On the other hand, unordered set can be more efficient.

The following code creates a set that contains integers, and shows some of the Operations:

Insert
The function insert is used to add an element to the set. This function inserts the element if the set is empty or append the element if the set is not empty.
Count
The function count is used to calculate the number of occurrences of elements present in the set. The function count returns the number of occurrences of an element in the set.
Erase
The function erase is used to remove or delete the element from the set.

The following program uses all the above function:

#include<iostream>
#include<set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);

	cout<<s.count(1) <<endl;
	cout<<s.count(2) <<endl;
	cout<<s.count(4) <<endl;

	s.erase(2);
	s.erase(4);
	s.insert(1);

	cout<<s.count(2) <<endl;
	cout<<s.count(4) <<endl;
	cout<<s.count(1) <<endl;

	return 0;
}

Output

A set can be used mostly like a vector, but it is not possible to access the elements using the [] notation. The following code creates a set, prints the number of elements in it, and then iterates through all the elements:

#include<iostream>
#include<set>
using namespace std;

int main()
{
	set<int> s = {2,5,6,8};

	cout<<s.size() << "\n"; // 4

	for (auto x : s) 
	{
		cout<< x << "\n";
	}

	return 0;
}

Output

An important property of sets is that all their elements are distinct. Thus, the function count always returns either 0 (the element is not in the set) or 1 (the element is in the set), and the function insert never adds an element to the set if it is already there. The following code illustrates this:

#include<iostream>
#include<set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(5);
	s.insert(5);
	s.insert(5);

	cout<<s.count(5) << "\n"; // 1

	return 0;
}

Output

C++ also contains the structures multiset and unordered_multiset that otherwise work like set and unordered_set but they can contain multiple instances of an element. For example, in the following code all three instances of the number 5 are added to a multiset:

#include<iostream>
#include<set>
using namespace std;

int main()
{
	multiset<int> s;

	s.insert(5);
	s.insert(5);
	s.insert(5);

	cout<<s.count(5) << "\n"; // 3

	return 0;
}

Output

The function erase removes all instances of an element from a multiset:

#include<iostream>
#include<set>
using namespace std;

int main()
{
	multiset<int> s;

	s.erase(5);

	cout<<s.count(5) << "\n"; // 0

	return 0;
}

Output

Often, only one instance should be removed, which can be done as follows:

#include<iostream>
#include<set>
using namespace std;

int main()
{
	multiset<int> s;

	s.insert(5);
	s.insert(5);
	s.insert(5);

	s.erase(s.find(5));

	cout<<s.count(5) << "\n"; // 2

	return 0;
}

Output