Home » C++ programming language

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

What is a set structure in C++?

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:

1. Insertion
2. Deletion
3. Searching

The C++ standard library contains two set implementations:

1. The structureset is based on a balanced binary tree and its operations work in O(log_n) time.
2. 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:

1. 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.
2. 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.
3. Erase
   The function erase is used to remove or delete the element from the set.

Example of set structures in C++

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

0
1
1
0
0
1

Iterating over set structure

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:

Example

#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

4
2
5
6
8

Set's all elements are distinct

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:

Example

#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

1

Multiset and Unordered_multiset

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:

Example

#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

3

Remove all instances of an element from a multiset

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

Example

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

int main() {
  multiset<int> s;

  s.erase(5);

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

  return 0;
}

Output

0

Example

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

2