Set in C++ STL

A Set is a container which stores unique elements in some sorted order. It is an implementation of a Self-Balancing Binary Search Tree, specifically a Red-Black Tree which ensures,

• Search, insert, and delete in O(log n) time.
• Does not allow duplicates.
• Elements are always sorted in ascending order by default. You can also choose your own way of ordering them using a custom rule (comparator).
• Compared to unordered_set, the time taken to search, insert, and delete an higher, but we get elements in sorted order and also support additional functions likeupper_bound() andlower_bound().

Let us take a look at an example to create a set and traverse it.

#include <iostream> #include <set> using namespace std; int main() {  // Creating an empty set  set<int> s1;  // Initialize set with list   set<int> s2 = {1, 2, 3, 2, 1};   // Traversing the set  for (auto& x : s2)  cout << x << " ";  cout << endl;  return 0; } 

1 2 3 

Syntax

The set contaiiner is defined as std::set class template inside <set> header file.

set<T> s;

where,

• T: Data type of elements in the set.
• s: Name assigned to the set.

Basic Operations

Basic operations on set containers are shown below:

Inserting Elements

• Theinsert() operation adds a new element to the set only if it not already present.
• If the element already exists, insert() does nothing (since duplicates are not allowed in set).
• Time complexity to insert is O(log n), as the underlying data structure is a Red-Black Tree.

#include <iostream> #include <set> using namespace std; int main() {  // Initialize set with values  set<int> s = {2, 3};  // Inserting an element  s.insert(1);  // Traversing the set  for (auto x : s)  cout << x << endl;  return 0; } 

1 2 3 

Searching Elements

• The find() function is used to check whether an element exists. It returns an iterator to the element if found, else returns end() if the element is not found.
• The count() function can also be used to check existence, returns 1 if the element is present, 0 otherwise.
• Time complexity for searching an element is O(log n).

#include <iostream> #include <set> using namespace std; int main() {  set<int> s = {1, 2, 3};  // Accessing elements using find()  auto it = s.find(1);  if (it != s.end())  cout << "Element found: " << *it << endl;  // Accessing elements using count()  if (s.count(2))  cout << "2 exists in the set" << endl;  // Accessing all elements by traversal  cout << "All elements: ";  for (auto x : s)  cout << x << " ";  cout << endl;  return 0; } 

Element found: 1 2 exists in the set All elements: 1 2 3 

Traversing

• Loops (like range-based for loop or iterators) can be used to traverse all elements in a set.
• The traversal visits elements in sorted order (by default ascending, or according to a custom comparator).
• Time complexity to traverse a set is O(n), since each of the n elements is visited exactly once.

#include <iostream> #include <set> using namespace std; int main() {  set<int> s = {1, 2, 3};  // Traversing using iterators  for (auto it = s.begin(); it != s.end(); ++it)  cout << *it << endl;   return 0; } 

1 2 3 

Deleting Elements

• To delete an element from a set, use erase(), it removes the element if it exists, else does nothing.
• Time complexity to delete an element is O(log n), since the set is implemented using a Red-Black Tree.

#include <iostream> #include <set> using namespace std; int main() {  set<int> s = {1, 2, 3, 4};  // Deleting by value  s.erase(2);  // Deleting by iterator  s.erase(s.begin());  // Traversing the set  for (auto i : s)  cout << i << " ";  cout << endl;  return 0; } 

3 4