Unique Elements with std::set and std::multiset in C++

In the C++ Standard Library, set and multiset are associative containers that store elements in a sorted structure and operate on tree-based implementations. The main difference is that set stores only unique elements, while multiset allows multiple occurrences of the same element. Both are implemented using a red-black tree and provide automatic ordering.

1) What is set?

std::set is a container that stores each element exactly once and keeps them in a sorted order automatically.

• Elements are always sorted in ascending order.
• No duplicate elements are allowed.
• Insertion, search, and removal: O(log n)
• No random access → iteration required.

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

int main() {
    set<int> numbers;

    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // duplicates are not added

    for (int n : numbers)
        cout << n << " ";
}

Output: 10 20 30

2) Features of set

• Sorted element storage
• All elements are unique
• O(log n) for insertion and search
• Supports lower_bound / upper_bound

// Searching elements
set<int> s = {10, 20, 30};

if (s.contains(20))
    cout << "Found!";

3) What is multiset?

std::multiset is similar to set, but it allows multiple occurrences of the same element.

• Elements are stored in sorted order.
• Duplicate elements are allowed.
• Insertion, search, and removal: O(log n)
• No random access.

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

int main() {
    multiset<int> nums;

    nums.insert(20);
    nums.insert(10);
    nums.insert(20);  // duplicate allowed
    nums.insert(30);

    for (int n : nums)
        cout << n << " ";
}

Output: 10 20 20 30

4) Counting elements in multiset

multiset<int> ms = {10, 20, 20, 30};

cout << "Count of 20: " << ms.count(20) << endl;

Output: Count of 20: 2

5) Comparison: set vs multiset

Conclusion: If you need only unique values → use set. If duplicates must be stored → use multiset.

6) Ordered access and range queries

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

auto it = s.lower_bound(25); // first element >= 25
cout << *it << endl;

it = s.upper_bound(30); // first element > 30
cout << *it << endl;

7) Removal operations

set<int> s = {10, 20, 30};

s.erase(20);        // erase by key
s.erase(s.begin()); // erase by iterator

multiset<int> ms = {10, 20, 20, 30};

ms.erase(20); // removes ALL elements equal to 20

8) Practical Example – Word Frequency Analysis

Counting words using multiset

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

int main() {
    multiset<string> words;

    words.insert("hello");
    words.insert("world");
    words.insert("hello");
    words.insert("cpp");

    cout << "Count of 'hello': " << words.count("hello") << endl;

    for (auto& w : words)
        cout << w << " ";
}

9) Which one should you use?

• If you need unique values → set
• If duplicates are allowed → multiset
• Both are suitable when sorted data is needed
• Both have O(log n) performance for basic operations

Summary:
set = unique elements
multiset = duplicate elements
Both automatically keep elements sorted.

10) TL;DR

Related Articles