Set vs Multiset in C++: Key Differences and Usage

In C++, set stores unique sorted elements, while multiset allows multiple identical elements in sorted order. Use set when duplicates are not allowed and multiset when duplicates are needed.

Quick Comparison

This table summarizes the main differences between set and multiset in C++.

Feature	set	multiset
Element Uniqueness	Stores unique elements only	Allows duplicate elements
Ordering	Elements are sorted automatically	Elements are sorted automatically
Insertion Behavior	Inserting existing element does nothing	Inserting duplicates adds new elements
Use Case	When duplicates are not allowed	When duplicates are allowed
Underlying Structure	Usually a balanced binary search tree	Usually a balanced binary search tree
Count of Elements	Count of a specific element is 0 or 1	Count can be more than 1

Key Differences

The set container in C++ stores elements in sorted order and ensures each element is unique. If you try to insert an element that already exists, the insertion is ignored. This makes set ideal for collections where duplicates are not allowed, like a list of unique IDs.

On the other hand, multiset also stores elements in sorted order but allows multiple identical elements. This means you can have several copies of the same value. It is useful when you want to keep track of all occurrences, such as counting repeated events or scores.

Both containers use balanced binary search trees internally, so they provide efficient insertion, deletion, and lookup operations. The main difference is how they handle duplicates: set forbids them, while multiset permits them.

Code Comparison

Here is an example showing how to insert elements into a set and print them. Notice that duplicates are ignored.

cpp

#include <iostream>
#include <set>

int main() {
    std::set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2); // duplicate ignored

    for (int x : s) {
        std::cout << x << " ";
    }
    return 0;
}

Output

1 2 3 

Multiset Equivalent

This example shows the same insertions using a multiset. Duplicates are stored and printed.

cpp

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;
    ms.insert(3);
    ms.insert(1);
    ms.insert(2);
    ms.insert(2); // duplicate allowed

    for (int x : ms) {
        std::cout << x << " ";
    }
    return 0;
}

Output

1 2 2 3 

When to Use Which

Choose set when you need a collection of unique elements and want to avoid duplicates automatically. It is perfect for cases like storing unique user IDs, tags, or keys.

Choose multiset when duplicates matter and you want to keep track of how many times an element appears. For example, use it for counting repeated values, frequency analysis, or when duplicates have meaning in your data.

Key Takeaways

Use set for unique sorted elements without duplicates.

Use multiset to allow and store duplicate sorted elements.

Both containers keep elements sorted and provide efficient operations.

Insertion in set ignores duplicates; multiset stores all duplicates.

Pick based on whether duplicates are meaningful in your data.