C++ - C++ std::set and std::unordered_set?

In C++, std::set and std::unordered_set are Standard Template Library (STL) containers used to store unique elements. Unlike a vector or list, these containers do not allow duplicate values. They are particularly useful when a program needs to maintain a collection of distinct values and frequently perform operations such as searching, inserting, and deleting elements. The main difference between them is how they organize their elements: std::set keeps elements sorted, while std::unordered_set stores them using a hash table and does not maintain a particular order.

1. What is std::set?

std::set is an associative container that stores unique elements in sorted order. By default, elements are arranged in ascending order using the < comparison operator.

Example

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> numbers;

    numbers.insert(50);
    numbers.insert(20);
    numbers.insert(40);
    numbers.insert(20);
    numbers.insert(10);

    for (int value : numbers) {
        cout << value << " ";
    }

    return 0;
}

Output

10 20 40 50

Although 20 was inserted twice, it appears only once because a set stores only unique values. The elements are automatically arranged in ascending order.

2. Important Characteristics of std::set

A std::set has several important properties:

  • It stores only unique elements.

  • Elements are automatically maintained in sorted order.

  • Duplicate values are ignored.

  • Searching is efficient.

  • Insertion and deletion generally take O(log n) time.

  • Elements cannot be accessed using numerical indexes such as set[0].

  • Iterators can be used to traverse the elements.

The sorted nature of set makes it useful when the order of elements is important.

3. Inserting Elements into a set

The insert() function is used to add elements.

set<int> numbers;

numbers.insert(30);
numbers.insert(10);
numbers.insert(50);
numbers.insert(20);

The resulting set is:

10 20 30 50

If an existing value is inserted again, the set remains unchanged.

numbers.insert(30);

There will still be only one 30.

The insert() function can also provide information about whether the insertion was successful.

auto result = numbers.insert(40);

if (result.second) {
    cout << "Element inserted";
} else {
    cout << "Element already exists";
}

The second value in the returned pair indicates whether the insertion actually took place.

4. Searching in a set

The find() function can be used to search for an element.

set<int> numbers = {10, 20, 30, 40, 50};

auto it = numbers.find(30);

if (it != numbers.end()) {
    cout << "Element found";
} else {
    cout << "Element not found";
}

If the element exists, find() returns an iterator pointing to it. If it does not exist, it returns numbers.end().

Another useful function is count().

if (numbers.count(30) > 0) {
    cout << "30 exists";
}

Since a set cannot contain duplicates, count() returns either 0 or 1.

5. Removing Elements from a set

The erase() function removes elements.

set<int> numbers = {10, 20, 30, 40, 50};

numbers.erase(30);

The resulting set becomes:

10 20 40 50

You can also erase an element using an iterator.

auto it = numbers.find(40);

if (it != numbers.end()) {
    numbers.erase(it);
}

To remove every element:

numbers.clear();

The empty() function can be used to check whether the set contains any elements.

if (numbers.empty()) {
    cout << "Set is empty";
}

6. What is std::unordered_set?

std::unordered_set is another STL container that stores unique elements. However, unlike std::set, it does not maintain sorted order.

It uses a hash table internally to organize elements.

Example

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> numbers;

    numbers.insert(50);
    numbers.insert(20);
    numbers.insert(40);
    numbers.insert(20);
    numbers.insert(10);

    for (int value : numbers) {
        cout << value << " ";
    }

    return 0;
}

The output might look like:

10 40 20 50

The exact order is not guaranteed. It can vary depending on the implementation and hash-table state.

The important point is that the duplicate 20 is still stored only once.

7. Important Characteristics of std::unordered_set

unordered_set has the following characteristics:

  • It stores unique elements.

  • It does not maintain sorted order.

  • It uses hashing internally.

  • Average insertion time is O(1).

  • Average search time is O(1).

  • Average deletion time is O(1).

  • Worst-case complexity can become O(n).

  • Elements cannot be accessed using indexes.

  • The order of traversal should not be relied upon.

Because of its fast average lookup performance, unordered_set is useful when ordering is not important.

8. Searching in unordered_set

Searching works similarly to set.

unordered_set<string> names = {
    "Alice",
    "Bob",
    "Charlie"
};

if (names.find("Bob") != names.end()) {
    cout << "Bob found";
}

The count() function can also be used:

if (names.count("Alice")) {
    cout << "Alice exists";
}

Since duplicates are not allowed, the result is either 0 or 1.

9. set vs unordered_set

The fundamental difference is the way the containers organize their data.

Feature std::set std::unordered_set
Duplicate values Not allowed Not allowed
Ordering Sorted No guaranteed order
Internal structure Typically balanced search tree Hash table
Average search O(log n) O(1)
Average insertion O(log n) O(1)
Average deletion O(log n) O(1)
Worst-case search O(log n) O(n)
Supports sorted traversal Yes No
Requires hashing No Yes
Requires ordering comparison Yes No

10. When Should You Use std::set?

Use std::set when sorted and unique data is required.

For example, suppose a school maintains unique student marks:

set<int> marks = {85, 72, 95, 85, 60};

The result is:

60 72 85 95

This is useful when you need to display unique values in sorted order.

Another example is maintaining unique product IDs in ascending order:

set<int> productIDs;

Whenever you iterate over the set, the IDs will appear in sorted order.

11. When Should You Use std::unordered_set?

Use std::unordered_set when you mainly need fast membership checking and the order of elements does not matter.

For example:

unordered_set<string> usernames;

usernames.insert("user101");
usernames.insert("user205");
usernames.insert("user310");

You can quickly check whether a username exists:

if (usernames.count("user205")) {
    cout << "Username exists";
}

This can be particularly useful for duplicate detection, membership testing, and maintaining collections where ordering is irrelevant.

12. Duplicate Detection Example

Both containers are excellent for identifying duplicate values.

Consider the following data:

10 20 30 20 40 10

Using an unordered_set:

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> values;

    int numbers[] = {10, 20, 30, 20, 40, 10};

    for (int number : numbers) {
        if (values.count(number)) {
            cout << "Duplicate: " << number << endl;
        } else {
            values.insert(number);
        }
    }

    return 0;
}

Output:

Duplicate: 20
Duplicate: 10

Here, the set keeps track of values that have already been encountered. When the same value appears again, it can be identified as a duplicate.

13. Custom Ordering in std::set

A set can also use a custom comparison function.

For example, to store numbers in descending order:

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int, greater<int>> numbers = {
        10, 50, 20, 40, 30
    };

    for (int number : numbers) {
        cout << number << " ";
    }

    return 0;
}

Output:

50 40 30 20 10

This demonstrates one advantage of set: its ordering behavior can be customized.

14. Custom Types with unordered_set

An unordered_set can also store user-defined objects, but the program needs a suitable hashing mechanism and equality comparison.

For example, when using a custom class, C++ needs to know how to calculate a hash value for an object and how to determine whether two objects are equal.

This makes unordered_set very powerful, but slightly more complicated when working with user-defined types.

15. Choosing Between set and unordered_set

A simple decision rule is:

Choose set when:

  • You need elements in sorted order.

  • You need ordered traversal.

  • You need operations based on ordering.

  • Predictable logarithmic performance is desirable.

Choose unordered_set when:

  • You do not care about element order.

  • Fast average lookup is important.

  • You mainly need to determine whether an element exists.

  • You want efficient average-case insertion and deletion.

For example, if you need to display unique employee IDs from smallest to largest, set is appropriate. If you only need to check whether an employee ID exists, unordered_set is generally more suitable.

Conclusion

std::set and std::unordered_set are important C++ STL containers for managing unique data. Both automatically prevent duplicate elements and provide efficient searching, insertion, and deletion. The major distinction is that std::set maintains elements in sorted order and generally provides O(log n) operations, whereas std::unordered_set uses hashing and provides O(1) average-case operations without guaranteeing any ordering.

Understanding this difference helps programmers select the appropriate container based on whether ordering or fast average lookup is the primary requirement.