In C++ STL (Standard Template Library), the `set` is a container that comes with built-in “ordered + deduplication” buffs, implemented based on a red-black tree. It can automatically sort elements and ensure no duplicate values, making it particularly useful in daily development for handling deduplication, ordered traversal, and fast searching scenarios. Today, we will master the core usage of `set` from scratch!

1. Core Features of Set

Before learning the usage, let’s understand the core advantages of set and know when to use it:

Automatic Sorting Defaults to ascending order (custom sorting rules can be defined);
No Duplicate Elements Inserting duplicate values will be automatically ignored, naturally supporting deduplication;
Fast Searching The underlying red-black tree is a balanced binary search tree, with time complexity for searching, inserting, and deleting all being O(log n);
Elements Cannot Be Modified Directly To modify an element, you must first delete the old value and then insert the new value (because the elements are ordered, direct modification would disrupt the sorting structure).

Note: If you need to allow duplicate elements, you can use multiset (usage is basically the same as set, only supports duplicate values); if you pursue faster search speed (O(1)), you can use unordered_set (unordered, deduplication, implemented with a hash table).

2. Basic Usage: From Initialization to Common Operations

1. Header Files and Namespaces

Using set requires including the header file <set>, and it is by default in the std namespace:

#include <set>
using namespace std;  // Simplifies code, can also explicitly write std::set

2. Initialization Methods

set supports various initialization methods, choose as needed:

// 1. Empty set (default ascending order)
set<int> s1;

// 2. Initialize with multiple elements (C++11 and above)
set<int> s2 = {3, 1, 4, 1, 5};  // Automatically deduplicates + sorts, final is {1,3,4,5}

// 3. Copy constructor
set<int> s3(s2);  // s3 = {1,3,4,5}

// 4. Range constructor (copy elements from other containers)
vector<int> vec = {2, 7, 1, 8};
set<int> s4(vec.begin(), vec.end());  // s4 = {1,2,7,8}

// 5. Custom sorting (descending)
set<int, greater<int>> s5 = {3,1,4};  // Final is {4,3,1}

3. Core Operations: Insert, Delete, Search, Modify

(1) Insert Elements (insert)

Supports inserting a single element, multiple elements, and range elements:

set<int> s;

// Insert a single element
s.insert(5);
s.insert(3);
s.insert(5);  // Duplicate element, insertion fails, s remains {3,5}

// Insert multiple elements (C++11)
s.insert({1, 4, 2});  // After insertion s = {1,2,3,4,5}

// Insert range (copy from vector)
vector<int> vec = {6, 0};
s.insert(vec.begin(), vec.end());  // Final s = {0,1,2,3,4,5,6}

(2) Delete Elements (erase)

Supports deletion by value, by iterator, and clearing all elements:

set<int> s = {0,1,2,3,4,5,6};

// 1. Delete by value (returns the number of deleted elements, 0 or 1)
int count = s.erase(3);  // Deletes 3, returns 1; s = {0,1,2,4,5,6}
count = s.erase(7);      // 7 does not exist, returns 0

// 2. Delete by iterator (must be a valid iterator)
auto it = s.find(4);     // Find iterator for 4
if (it != s.end()) {
    s.erase(it);         // Deletes 4, s = {0,1,2,5,6}
}

// 3. Delete range (left closed right open)
auto it1 = s.find(1);
auto it2 = s.find(5);
s.erase(it1, it2);       // Deletes 1,2, s = {0,5,6}

// 4. Clear all elements
s.clear();  // s is empty

(3) Find Elements (find, count, lower_bound, upper_bound)

find(x) Finds the element with value x, returns an iterator (points to x if found, otherwise points to end());
count(x) Returns the count of x (only 0 or 1 in set, can be greater than 1 in multiset);
lower_bound(x) Returns the iterator to the first element >= x;
upper_bound(x) Returns the iterator to the first element > x.

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

// 1. find search
auto it = s.find(3);
if (it != s.end()) {
    cout << "Found element: " << *it << endl;  // Outputs 3
} else {
    cout << "Element not found" << endl;
}

// 2. count check existence
if (s.count(4)) {
    cout << "4 exists in set" << endl;
}

// 3. Range search (find elements between 2~4)
auto low_it = s.lower_bound(2);  // Points to 2
auto up_it = s.upper_bound(4);   // Points to 5
cout << "Elements between 2~4:";
for (auto i = low_it; i != up_it; ++i) {
    cout << *i << " ";  // Outputs 2 3 4
}
cout << endl;

(4) Modify Elements (Indirect Modification)

set does not support direct modification of elements (as it would disrupt sorting), you must first delete the old value and then insert the new value:

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

// To change 3 to 4: first delete 3, then insert 4
s.erase(3);
s.insert(4);  // Final s = {1,4,5}

4. Other Common Interfaces

size() Returns the number of elements;
empty() Checks if it is empty (returns true if empty);
begin()/end()

Returns the iterator to the first element / past-the-end iterator (for traversal)

rbegin()/rend()

Returns reverse iterators (for reverse traversal).

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

// 1. Forward traversal (ascending order)
cout << "Forward traversal:";
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";  // Outputs 1 2 3 4 5
}
cout << endl;

// 2. Reverse traversal (descending order)
cout << "Reverse traversal:";
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " ";  // Outputs 5 4 3 2 1
}
cout << endl;

// 3. Range for traversal (C++11 and above, most concise)
cout << "Range for traversal:";
for (int num : s) {
    cout << num << " ";  // Outputs 1 2 3 4 5
}
cout << endl;

3. Practical Examples: Typical Application Scenarios of Set

Scenario 1: Automatic Deduplication + Sorting

Requirement: Given an unordered array, remove duplicate elements and output in ascending order.

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

int main() {
    vector<int> arr = {5, 2, 7, 2, 3, 5, 1, 7};

    // Use set for automatic deduplication + sorting
    set<int> s(arr.begin(), arr.end());

    // Output result
    cout << "Deduplicated and sorted:";
    for (int num : s) {
        cout << num << " ";  // Outputs 1 2 3 5 7
    }

    cout << endl;

    return 0;
}

Scenario 2: Fast Searching + Existence Check

Requirement: Simulate a “keyword library” that supports adding keywords and checking if keywords exist.

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

int main() {
    set<string> keyword_set = {"C++", "STL", "set", "vector"};

    // Add keywords
    keyword_set.insert("map");
    keyword_set.insert("C++");  // Duplicate, insertion fails

    // Query keywords
    string query = "STL";
    if (keyword_set.find(query) != keyword_set.end()) {
        cout << "Keyword \"" << query << "\" exists" << endl;
    } else {
        cout << "Keyword \"" << query << "\" does not exist" << endl;
    }

    query = "Java";
    if (keyword_set.count(query) == 0) {
        cout << "Keyword \"" << query << "\" does not exist" << endl;
    }

    return 0;
}

Scenario 3: Custom Sorting Rules

Requirement: Store custom structures (such as student information) and sort by student ID in descending order.

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

// Define student structure
struct Student {
    int id;         // Student ID
    string name;    // Name
    int score;      // Score
};

// Custom sorting rule: sort by student ID in descending order (must be a global function or function object)
struct CompareByIdDesc {
    bool operator()(const Student&amp; s1, const Student&amp; s2) const {
        return s1.id > s2.id;  // Descending: larger IDs come first
    }
};

int main() {
    // Define set with specified sorting rule
    set<Student, CompareByIdDesc> student_set = {
        {103, "Zhang San", 85},
        {101, "Li Si", 92},
        {102, "Wang Wu", 78}
    };

    // Insert new student
    student_set.insert({104, "Zhao Liu", 90});

    // Traverse and output (sorted by student ID in descending order)
    cout << "Student information (sorted by student ID in descending order):" << endl;
    for (const auto&amp; stu : student_set) {
        cout << "Student ID: " << stu.id << ", Name: " << stu.name << ", Score: " << stu.score << endl;
    }

    return 0;
}
Output:
Student information (sorted by student ID in descending order):
Student ID: 104, Name: Zhao Liu, Score: 90
Student ID: 103, Name: Zhang San, Score: 85
Student ID: 102, Name: Wang Wu, Score: 78
Student ID: 101, Name: Li Si, Score: 92

4. Precautions and Common Pitfalls

Cannot Modify Elements Directly As emphasized earlier, direct modification would disrupt the sorting structure of the red-black tree, you must “delete old and insert new”;
Iterator Stability When inserting or deleting elements, except for the iterator of the deleted element, other iterators remain valid (due to the properties of the red-black tree);
Pitfalls of Custom Sorting The sorting rule must be a “strict weak ordering” (i.e., it cannot be true that both a < b and b < a are true at the same time, and it cannot be true that a < a is true), otherwise it will lead to undefined behavior;
Efficiency Comparison

Ordered scenario + deduplication: use set (O(log n) operations);
Unordered scenario + deduplication: use unordered_set (O(1) operations, faster);
Allowing duplicate elements: use multiset or unordered_multiset.

5. Conclusion

set is a powerful tool in C++ for handling “ordered + deduplication” scenarios, with the underlying red-black tree ensuring efficient insertion, searching, and deletion operations, and a simple and easy-to-use interface. Remember the core points:

Automatic sorting + deduplication, no manual handling required;
Use find for searching, deletion supports by value / iterator;
Custom sorting requires providing a strict weak ordering comparison rule.

Mastering these usages will easily handle deduplication, sorting, and fast searching needs in daily programming.

Comprehensive Guide to C++ Set Container: The “Magic Tool” for Ordered Deduplication

1. Core Features of Set

2. Basic Usage: From Initialization to Common Operations

1. Header Files and Namespaces

2. Initialization Methods

3. Core Operations: Insert, Delete, Search, Modify

(1) Insert Elements (insert)

(2) Delete Elements (erase)

(3) Find Elements (find, count, lower_bound, upper_bound)

(4) Modify Elements (Indirect Modification)

4. Other Common Interfaces

Scenario 1: Automatic Deduplication + Sorting

Scenario 2: Fast Searching + Existence Check

Scenario 3: Custom Sorting Rules

5. Conclusion

Leave a Comment Cancel reply

1. Core Features of Set

2. Basic Usage: From Initialization to Common Operations

1. Header Files and Namespaces

2. Initialization Methods

3. Core Operations: Insert, Delete, Search, Modify

(1) Insert Elements (insert)

(2) Delete Elements (erase)

(3) Find Elements (find, count, lower_bound, upper_bound)

(4) Modify Elements (Indirect Modification)

4. Other Common Interfaces

Scenario 1: Automatic Deduplication + Sorting

Scenario 2: Fast Searching + Existence Check

Scenario 3: Custom Sorting Rules

5. Conclusion

Related posts

Leave a Comment Cancel reply