Skip to content

Set and Multiset — Ordered and Unordered Sets, Performance

DodaTech Updated 2026-06-28 7 min read

In this tutorial, you will learn about Set and Multiset. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ std::set is a sorted associative container with unique keys and O(log n) operations using balanced binary trees, while std::unordered_set provides average O(1) access through hash tables.

What You'll Learn

You will use std::set for sorted unique elements with logarithmic operations, use std::unordered_set for fast lookups with hash tables, use std::multiset and std::unordered_multiset for non-unique elements, understand hashing and custom hash functions, and choose between ordered and unordered sets based on performance requirements and iteration order needs.

Why It Matters

Sets answer the question "is this element in the collection?" efficiently. Ordered sets maintain sorted order for iteration and range queries. Unordered sets offer the fastest possible lookups when order does not matter. Mastering sets is essential for algorithm design, data deduplication, and implementing mathematical set operations.

Learning Path

graph LR
    A["31: Deque, List, Forward List"] --> B["32: Set & Multiset"]
    B --> C["33: Map & Multimap"]
    C --> D["34: Stack, Queue, Priority Queue"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

std::set

#include <iostream>
#include <set>

int main() {
    std::set<int> s;
    
    // Insert (returns pair<iterator, bool>)
    auto [it1, inserted1] = s.insert(5);
    std::cout << "Inserted 5: " << inserted1 << "\n";  // 1
    
    auto [it2, inserted2] = s.insert(5);
    std::cout << "Inserted 5 again: " << inserted2 << "\n";  // 0
    
    s.insert(3);
    s.insert(7);
    s.insert(1);
    s.insert(9);
    
    // Elements are always sorted
    for (int x : s) std::cout << x << " ";
    std::cout << "\n";  // 1 3 5 7 9
    
    // Find
    auto it = s.find(7);
    if (it != s.end()) {
        std::cout << "Found: " << *it << "\n";
    }
    
    // Count (0 or 1 for set)
    std::cout << "Count of 3: " << s.count(3) << "\n";
    std::cout << "Count of 99: " << s.count(99) << "\n";
    
    // Erase
    s.erase(3);
    
    // Range queries
    auto lower = s.lower_bound(4);  // first >= 4
    auto upper = s.upper_bound(7);  // first > 7
    for (auto it = lower; it != upper; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";  // 5 7
    
    // Contains (C++20)
    // std::cout << s.contains(5) << "\n";
}

std::multiset

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;
    
    ms.insert(5);
    ms.insert(3);
    ms.insert(5);  // duplicate allowed
    ms.insert(1);
    ms.insert(5);  // another duplicate
    
    for (int x : ms) std::cout << x << " ";
    std::cout << "\n";  // 1 3 5 5 5
    
    // Count returns number of occurrences
    std::cout << "Count of 5: " << ms.count(5) << "\n";  // 3
    
    // Find returns first occurrence
    auto it = ms.find(5);
    if (it != ms.end()) {
        std::cout << "First 5: " << *it << "\n";
    }
    
    // Equal range: pair of iterators covering all matching elements
    auto [low, high] = ms.equal_range(5);
    for (auto it = low; it != high; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";  // 5 5 5
    
    // Erase all occurrences
    ms.erase(5);  // removes all 5s
}

std::unordered_set

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> us;
    
    us.insert("apple");
    us.insert("banana");
    us.insert("cherry");
    us.insert("apple");  // ignored
    
    std::cout << "Size: " << us.size() << "\n";  // 3
    
    // No guaranteed order
    for (const auto& s : us) {
        std::cout << s << " ";
    }
    std::cout << "\n";
    
    // Fast lookup
    if (us.find("banana") != us.end()) {
        std::cout << "banana found\n";
    }
    
    // Bucket interface
    std::cout << "Bucket count: " << us.bucket_count() << "\n";
    std::cout << "Load factor: " << us.load_factor() << "\n";
    
    // Reserve to avoid rehash
    us.reserve(1000);
}

Custom Hash and Comparison

#include <iostream>
#include <unordered_set>
#include <set>

struct Point {
    int x, y;
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Custom hash for unordered_set
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

// Custom comparison for ordered set
struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};

int main() {
    std::unordered_set<Point, PointHash> us;
    us.insert({1, 2});
    us.insert({3, 4});
    
    std::set<Point, PointCompare> ordered;
    ordered.insert({1, 2});
    ordered.insert({3, 4});
    
    std::cout << "Found: " << (us.find({1, 2}) != us.end()) << "\n";
    std::cout << "Ordered size: " << ordered.size() << "\n";
}

Performance Comparison

#include <iostream>
#include <set>
#include <unordered_set>
#include <chrono>
#include <random>

int main() {
    constexpr int N = 1000000;
    
    std::set<int> ordered;
    std::unordered_set<int> unordered;
    
    // Insert benchmark
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) ordered.insert(i);
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Ordered insert: "
              << std::chrono::duration<double, std::milli>(end - start).count()
              << " ms\n";
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) unordered.insert(i);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Unordered insert: "
              << std::chrono::duration<double, std::milli>(end - start).count()
              << " ms\n";
    
    // Find benchmark
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) ordered.find(i);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Ordered find: "
              << std::chrono::duration<double, std::milli>(end - start).count()
              << " ms\n";
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) unordered.find(i);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Unordered find: "
              << std::chrono::duration<double, std::milli>(end - start).count()
              << " ms\n";
}

Set Operations Using <algorithm>

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

int main() {
    std::set<int> a = {1, 2, 3, 4, 5};
    std::set<int> b = {3, 4, 5, 6, 7};
    
    std::set<int> result;
    
    // Union
    std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                   std::inserter(result, result.begin()));
    std::cout << "Union: ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
    
    // Intersection
    result.clear();
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                          std::inserter(result, result.begin()));
    std::cout << "Intersection: ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
    
    // Difference
    result.clear();
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                        std::inserter(result, result.begin()));
    std::cout << "Difference (a - b): ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
}

Common Mistakes

Mistake 1: Using set When unordered_set Is Faster

If you do not need sorted iteration, unordered_set is usually faster. Profile to confirm.

Mistake 2: Bad Hash Functions

struct BadHash {
    std::size_t operator()(const Point& p) const {
        return p.x + p.y;  // many collisions for (1,2) and (2,1)
    }
};

Create well-distributed hashes to minimize collisions.

Mistake 3: Modifying Elements in Set

Set elements are const. You cannot modify them in place because that would break the ordering.

std::set<int> s = {1, 2, 3};
// *s.begin() = 5;  // Error: const

Erase and reinsert.

Mistake 4: Using multiset When a vector with Sort Would Work

If you insert all elements at once and then iterate, a vector sorted once is faster than maintaining a multiset.

Mistake 5: Ignoring Rehash Costs

unordered_set rehashes when the load factor exceeds max_load_factor(). Use reserve() to preallocate.

Mistake 6: Not Using insert Return Value

s.insert(5);
if (s.count(5)) { ... }  // O(log n) for second lookup

Use the pair returned by insert.

Practice Questions

  1. When would you choose std::set over std::unordered_set?
  2. How do you allow duplicates in sorted order?
  3. Write a custom hash function for a std::pair<int, int>.
  4. What is the difference between lower_bound and upper_bound?
  5. Implement set intersection without using std::set_intersection.

Challenge

Implement a spell checker using std::unordered_set<std::string>. Load a dictionary, accept user input, and highlight misspelled words. Measure lookup time for a paragraph of text.

FAQ

What is the underlying data structure of `std::set`?

Typically a red-black tree (balanced binary search tree). The standard requires O(log n) operations, which a balanced tree provides.

What is a bucket in `unordered_set`?

A bucket is a slot in the hash table that holds all elements with the same hash value (a collision chain).

What happens if the hash function is poor?

Many collisions degrade performance from O(1) to O(n) on average. A good hash function distributes elements uniformly across buckets.

Can I use `std::set` with custom objects?

Yes, but you must provide a comparison operator (default operator<) or a custom comparator.

What is `load_factor`?

The ratio of elements to buckets. A higher load factor means more collisions. The default maximum is 1.0 for unordered_set.

Is `std::set` faster or slower than `std::vector` for small collections?

For small collections (fewer than about 50 elements), a sorted vector with binary search can be faster due to cache locality.

Mini Project

Build a simple unique word counter:

#include <iostream>
#include <unordered_set>
#include <string>
#include <sstream>

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the fox barks";
    std::unordered_set<std::string> uniqueWords;
    std::unordered_set<std::string> duplicates;
    
    std::istringstream stream(text);
    std::string word;
    
    while (stream >> word) {
        if (!uniqueWords.insert(word).second) {
            duplicates.insert(word);
        }
    }
    
    std::cout << "Unique words: " << uniqueWords.size() << "\n";
    std::cout << "Duplicates: ";
    for (const auto& w : duplicates) {
        std::cout << w << " ";
    }
    std::cout << "\n";
}

What's Next

Sets are for element membership tests. The next lesson covers map and multimap: key-value associative containers for dictionaries and lookup tables.

← Previous Deque, List, Forward List — Double-Ended Queue, Linked Lists Performance Next → Map and Multimap — Ordered and Unordered Maps, emplace, try_emplace

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp