C++ set

🔐 C++ set (STL)

std::set is an associative container in the C++ STL that stores unique elements in a sorted order (by default, ascending).

It is typically implemented using a balanced binary search tree (Red–Black Tree).

🔹 1. Why Use set?

  • Automatically keeps elements sorted

  • Stores unique values only

  • Fast search, insert, delete → O(log n)

  • Useful when duplicates are not allowed

🔹 2. Include Header

#include <set>

🔹 3. Declaring a Set

std::set<int> s;

With initialization:

std::set<int> s = {5, 1, 3, 3, 2};

Result:

1 2 3 5

🔹 4. Inserting Elements

s.insert(10);
s.insert(5);

Duplicate insert ignored:

s.insert(10); // no effect

🔹 5. Accessing Elements

❌ No indexing ([] not allowed)

✔ Access using iterators:

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

🔹 6. Finding Elements

if (s.find(3) != s.end()) {
cout << "Found";
}

🔹 7. Erasing Elements

s.erase(3); // erase by value
s.erase(s.begin()); // erase by iterator

🔹 8. Size & Empty

s.size();
s.empty();

🔹 9. Lower Bound & Upper Bound

auto it1 = s.lower_bound(3); // ≥ 3
auto it2 = s.upper_bound(3); // > 3

🔹 10. Custom Sorting (Descending Order)

set<int, greater<int>> s;

🔹 11. set vs multiset

Featuresetmultiset
Duplicates❌ No✔ Yes
Sorted✔ Yes✔ Yes
InsertO(log n)O(log n)

🔹 12. set vs unordered_set

Featuresetunordered_set
OrderSortedNo order
SearchO(log n)O(1) average
ImplementationTreeHash table

🔹 13. Example: Remove Duplicates

vector<int> v = {1, 2, 2, 3, 4, 4};

set<int> s(v.begin(), v.end());

for (int x : s)
cout << x << " ";

🔹 14. Time Complexity

OperationComplexity
InsertO(log n)
FindO(log n)
EraseO(log n)

❌ Common Mistakes

s[0]; // ❌ invalid
*it = 5; // ❌ elements are read-only

📌 Summary

  • set stores unique sorted elements

  • No indexing allowed

  • Balanced BST based

  • Fast search and insert

  • Ideal when uniqueness + order matters

You may also like...