# Set in C++

## Overview

Set is a standard template library (STL) container in C++, used in programming whenever we need to store unique elements (no duplicate values) and stored in a specifically sorted manner. The elements inside the set can be inserted or removed, but when inserted once, they cannot be modified.

Generally, The time complexity of operations like insertion and deletion in the set in C++ is $O(log n)$.

## What is Set in C++?

A set in c++ is an associative(STL) container used to store unique elements that are stored in a specific sorted order(increasing or decreasing).

Elements of the set are unique, i.e., no duplicate values can be stored in the set because each value in the set is a key, and the set doesn't support indexing. So, the elements/values(keys) are the indexes themselves, and there cannot be more than one index. Also, the values in the set need to be accessed using the keys/values only.

The Set also has elements stored in sorted order. We can specify whether the elements will be sorted in ascending or descending order by changing the syntax during the set declaration.

The element in the set can be inserted, removed, and searched in logarithmic time complexity. Once the element is inserted in the set, they become constants and cannot be modified(the value can't be changed). Internally the set STL in C++ is implemented by the binary search tree(Red-Black Tree).

**Note:** To use set in C++, we must use the header file <set> using #include.

## Syntax

To define a set, we need first to use the STL set, and then in the angle brackets < >, we need to specify the data type of the elements of the set and, after that, the name of the set.

By default, the set stores the elements in ascending order, but if you want the elements to be sorted in descending order, you’ll need to write greater<datatype> along with the data type.

**Syntax:**

## Set Operations in C++

### Declaration

Sets can be declared by various methods, which are discussed individually.

First, the set can be initialized without any assigned value, i.e., an empty set.

The set s is created with a data type of int, and the elements will be sorted in increasing order.

Values can also be assigned to the set while initialization, all we have to do is to give the values in the curly braces after the declaration syntax of the set.

**Example:**

A set in C++ can be assigned using the other set, and the values of the previous(old) set will be assigned to the new set.

Now here, the values of the set $s1$ will be copied to the set $s2$

A set in C++ can also be assigned by using the array having some values. The subarray of the array can be copied to the set.

The array arr has six elements, now when the set s3 is declared, the sub-array of the array will be copied to the set as arr points to the first element of the array, and arr+3 points to the third element of the array. So, a subarray of length three will be copied to the set.

### Insertion

We use the insert() function in C++ to insert elements in the set. We need to specify the set's name and then use insert and, in brackets, give the value that needs to be inserted.

The insert function returns a pair, with an iterator pointing to the newly inserted element in the set, which is the first element of the pair. The second element of the pair represents a boolean value which is true if the element was not present and false if the element was already present in the set.

### Deletion

We use the erase() function in C++ to delete elements from the set. We need to specify the set's name and then use erase and brackets to give the element's position to be erased in the form of an iterator. And if we want to erase/remove multiple elements from the set, we need to give the specified range using the start and end iterator.

If we want to delete a single element from the set, we can pass that specific element also. In this case, this function will return one if the element is present; otherwise, zero.

### Traversal

There are different methods of iterating over a set. We’ll be discussing two of the most used methods.

First, we will use an iterator that will iterate over the set. But before that, we need to understand two functions.

**begin():** It returns the iterator pointing to the first element of the set.

**end():** It returns the iterator pointing to the location next to the set's last element.

Now, by using these two functions, we will iterate the set, and by using the iterator, we will access the values.

The iterator starts from the first element of the set with the help of begin() and goes up to the last element by checking if the element is last or not with the help of end(). And we accessed the values by using the dereference operator(*).

**Output**

In the second method, we will use a range-based for loop, which will iterate over the set elements. For the parameters of the for loop, we will declare an element/iterator of the same data type as the set using the auto specifier for automatic type deduction. And then, we will give a colon(:) and then the set's name. After that, we can directly access the elements using the iterator name.

**Output**

## Set STL Functions / Methods with Time Complexity

**Iterators**

Set STL Function | Work | Time Complexity |
---|---|---|

begin() | Returns the iterator pointing to the first element of the set | O(1) |

end() | Returns the pointer to the location which is next to the last element of the set. | O(1) |

rbegin() | Returns the reverse iterator pointing to the last element | O(1) |

rend() | Returns the reverse iterator pointing to the location before the first element | O(1) |

**Example explaining all the Set functions given above**

**Output**

In this example, after creating the set s, we created an iterator it.

First, we assigned it to point to the starting element of the set using set.begin() function, and after that, to check, we printed the value using dereference operator. After that, we assigned the iterator to point to the last element of the set using the set.end() function.

To use the rbegin() and rend() functions, we made the reverse iterator "rit". and then using the set.rbegin() and set.rend() functions, we pointed the iterator to the first element from the back and the last element from the back of the set.

**Capacity**

Set STL Function | Work | Time Complexity |
---|---|---|

size() | Returns the size/number of element of the set | O(1) |

empty() | Checks if the set is empty or not | O(1) |

max_size() | Returns the maximum allowed size/length of the set | O(1) |

**Example explaining all the Set functions given above**

**Output**

In this example, we created an empty set s, then checked for its maximum possible size using the set.max_size() function.

Then we inserted the elements in the set and checked the size of the set using the set.size() function. Then we used the set.empty() function to check if the set was empty or not. And it returned "0" (the set is not empty).

**Modifiers**

Set STL Function | Work | Time Complexity |
---|---|---|

insert() | Insert the specified element in the set | O(logN) |

erase(position) | Removes the element from the specified address from the set | O(1) |

erase(value) | Removes the specified element from the set | O(logN) |

erase(first, last) | Removes the specified range of elements from the set | O(N) |

clear() | Deletes/clears all the elements from the set. | O(N) |

emplace() | Works similar to the insert() function. It is used to insert elements to the set | O(logN) |

swap() | Swaps the elements of the two sets | constant |

**Example explaining all the Set functions given above**

**Output**

Here in this example, a set s is created, and after that, we use the insert() function to insert element nine into the set, and then we print the updated set.

Then we use the erase() function to remove the element 234 from the set.

Again after removing, we are inserting a new element 69 in the set, using the emplace() function.

We needed two sets for the swap() function, so we created the s2 set, then used the swap() function and printed the swapped set to understand how it works. Learn more about C++ Modifiers.

**Operations**

Set STL Function | Work | Time Complexity |
---|---|---|

find() | Returns the iterator to the element specified if found, else return the iterator to the end of the set | O(logN) |

count() | Returns 1 if the specified element is found, else 0 | O(logN) |

lower_bound() | Returns the iterator to the specified element if it is found, else return the just greater next element. | O(logN) |

upper_bound() | Returns the iterator to the very next element of the specified element | O(logN) |

**Example explaining all the Set functions given above**

**Output**

In this example, we have created a set s and an iterator it. We used the set.find() function to find the element 54 and assign its location to the iterator. As the element was present, the location got assigned, and finally, the element got printed.

We then used set.count() to check if the value is present in the set or not. As it was present, the "if" statement got executed.

We use set.lower_bound() and set.upper_bound() functions to get the lower and upper bound of the set and then print it with the help of the iterator. Use this C++ Online Compiler to compile your code.

## Difference between Set, Multiset, and Unordered_set

**Set** in C++ is an associative (STL) container that is used to store unique elements, and also they are stored in a specific sorted order(increasing or decreasing). Elements in the set are immutable, i.e., the elements can only be inserted or deleted but cannot be modified. Sets are implemented as a Binary Search Tree.

**Multiset** is an associative container that stores elements in sorted order. It has properties similar to the set. The only difference is that Multiset can store multiple similar valued elements(duplicates allowed).

**unordered_set** is an associative container used to store unique elements. There is no order in which the elements are stored (unordered). Hash-table is used to store elements here. Rest all other properties are similar to the set.

**Don't miss this chance to become a certified C++ programmer. Enroll now in our C++ full course and gain a competitive edge in the coding landscape.**

## Conclusion

- Set is a standard template library(STL) container in C++. The elements stored in the set are unique, sorted, and immutable.
- To define a set, first use the STL set, and then, in the angle brackets < >, specify the data type of the set elements and, after that, the set's name.
- By default, the set stores the elements in ascending order. Use greater<datatype> along with the data type for descending order.
- Internally, the set STL in C++ is implemented by the binary search tree.
- For insertion, use the insert function with the name of the set. name_of_set.insert(data);
- For deletion, use the erase function with the name of the set, and give the location(s) in the form of iterator(s). name_of_set.erase(iterator);.
- Operations like begin, end, size, and empty in the set take constant time.
- Operations like insert, find, count, upper_bound, and lower_bound in the set take logarithmic time.
- Operations like erase, and clear in the set take linear time.