In this tutorial, we will discuss about Set Container in C++ Standard Template Library.

What is Set in C++?

A set is an associative container provided by the Standard Template Library in C++. It can store only unique elements of the same type. This means we cannot add duplicate elements to it. It also stores the elements in sorted order. Internally, a set uses red-black trees to store the elements, and therefore it supports fast searching with a complexity of log(n).

For example, if you add certain numbers to a set like,

12, 67, 35, 91, 11, 10, 7, 4, 100, 11, 10, 23, 12, 33, 67, 30, 33.

It will store the elements in sorted order and will also reject the duplicate elements. The contents of the set will be as follows:

All the duplicate elements were not stored in the set; it basically contains only unique elements. Also, elements in a set are stored in ascending order by default. If you want, you can make it store in descending order too, but elements will always be stored in sorted order in a set. When we add an element to a set, it internally adjusts them to store the elements in sorted order.

Seven Important Facts about Set in C++

Let’s look at some of the important features of the Set container

1. Internal Implementation

The set container in C++ internally uses a self-balancing binary search tree, most commonly red-black trees. Therefore, when we add or remove any element in the set, it internally rearranges the tree to make it balanced. This ensures that operations like insertion, deletion, and searching are efficient. A balanced tree ensures that none of the branches of the tree get too long compared to the others, making lookups very fast in this set.

2. Order of Elements

All the elements in the set are stored in sorted order by default. It organizes elements in ascending order, but it also provides the facility to use an external comparator. This allows us to change the sorting order, making it possible to store elements in descending order. As the elements are stored in a sorted manner, searching becomes very efficient in the set.

3. Uses < Operator by default

By default, the set uses the “less than” operator to compare elements while sorting them internally. This means elements are stored in ascending order. For all built-in data types, the “less than” operator is predefined. However, if you are trying to insert custom objects into a set, you need to implement the “less than” operator for your class. This allows you to create a set of these custom objects. For this purpose, you can either override the “less than” operator or provide a custom comparator function.

4. Only Unique elements

The set contains only unique elements, which means no duplicates are allowed. In the set, the value acts as a key. If you try to insert a duplicate value into the set, it will simply be ignored, ensuring all elements in the set are distinct.

5. Fast Lookup

Sets are designed to support quick searching. The average time taken to find an element in a set is log(n). This is efficient compared to linear data structures. Therefore, sets are used in situations where frequent lookups are required.

6. No Indexing Support

Sets do not support random access operations. You cannot directly access, say, the 8th element from a set, although such direct access is possible in arrays and vectors. The set does not offer functionality to access elements using an index position. If you want to access set elements, you must use iterators. Then, you can move the iterator through the set and access each element one by one, not by index position.

7.Immutable Elements

Once an element is added to a set, it cannot be modified, as its value serves as its key. Modifying an element might affect the order of other elements in the set, which could disrupt its internal structure. If you wish to modify a value in a set, you must first remove it and then add the new value.

Summary

In C++, a set is required where we need to store unique, automatically sorted elements, ensuring efficient O(log n) search, insertion, and deletion operations. This dynamic container adapts its size based on content, eliminating manual sorting and duplicate-checking, making it an essential tool for scenarios demanding organized, distinct data.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.