Set Basics

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

int main() {
    // Create set
    set<int> numbers;
    
    // Insert elements
    numbers.insert(5);
    numbers.insert(2);
    numbers.insert(8);
    numbers.insert(1);
    numbers.insert(5);  // Duplicate, will be ignored
    numbers.insert(3);
    
    // Display set
    cout << "Set elements (sorted and unique): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    // Check if element exists
    if (numbers.find(5) != numbers.end()) {
        cout << "Element 5 found in set" << endl;
    }
    
    // Count occurrences (0 or 1 for set)
    cout << "Count of 5: " << numbers.count(5) << endl;
    cout << "Count of 10: " << numbers.count(10) << endl;
    
    // Size
    cout << "Set size: " << numbers.size() << endl;
    
    // Erase element
    numbers.erase(5);
    cout << "\nAfter erasing 5: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    // Lower and upper bound
    set<int> s = {1, 2, 3, 5, 7, 9};
    auto it_low = s.lower_bound(4);  // First element >= 4
    auto it_up = s.upper_bound(6);   // First element > 6
    
    cout << "\nLower bound of 4: " << *it_low << endl;
    cout << "Upper bound of 6: " << *it_up << endl;
    
    return 0;
}

Set elements (sorted and unique): 1 2 3 5 8
Element 5 found in set
Count of 5: 1
Count of 10: 0
Set size: 5

After erasing 5: 1 2 3 8
Lower bound of 4: 5
Upper bound of 6: 7

This program teaches you how to use Set Basics in C++. Set is a container from the STL that stores unique elements in automatically sorted order. Duplicates are automatically removed, making sets perfect for maintaining sorted, unique collections.

---

1. What This Program Does

The program demonstrates basic set operations:

• Creating and inserting elements
• Automatic sorting and duplicate removal
• Finding elements
• Counting occurrences
• Erasing elements
• Using lower_bound() and upper_bound()

Sets provide efficient storage of unique, sorted elements.

---

2. Header Files Used

1. #include <iostream>

   • Provides cout and cin for input/output operations.

2. #include <set>

   • Provides set container class.

---

3. Understanding Sets

Set Concept:

• Stores unique elements (no duplicates)
• Automatically sorted
• Fast search operations
• Balanced binary search tree implementation

Key Features:

• Unique elements only
• Automatic sorting
• Efficient search (O(log n))
• Ordered traversal

---

4. Creating Sets

Declaration:

set<int> numbers;

How it works:

• Template: set<dataType>
• Initially empty
• Elements automatically sorted
• Duplicates automatically removed

---

5. Inserting Elements

Using insert():

numbers.insert(5); numbers.insert(2); numbers.insert(8); numbers.insert(5); // Duplicate ignored

How it works:

• insert() adds element
• Duplicates automatically ignored
• Elements automatically sorted
• O(log n) time complexity

Result: {1, 2, 3, 5, 8} (sorted, unique)

---

6. Finding Elements

Using find():

auto it = numbers.find(5); if (it != numbers.end()) { // Element found }

How it works:

• Returns iterator to found element
• Returns end() if not found
• O(log n) time complexity
• Efficient search

---

7. Counting Occurrences

Using count():

int count = numbers.count(5); // Returns 1 or 0

How it works:

• Returns 1 if element exists
• Returns 0 if element doesn't exist
• For set, always 0 or 1 (unique elements)
• O(log n) time complexity

---

8. Erasing Elements

Using erase():

numbers.erase(5);

How it works:

• Removes element from set
• Maintains sorted order
• O(log n) time complexity
• Reduces size

---

9. Lower and Upper Bound

lower_bound():

auto it = s.lower_bound(4); // First element >= 4

upper_bound():

auto it = s.upper_bound(6); // First element > 6

How it works:

• lower_bound: first element >= value
• upper_bound: first element > value
• Useful for range queries
• O(log n) time complexity

---

10. When to Use Sets

Best For:

• Maintaining unique elements
• Sorted collections
• Fast search requirements
• Removing duplicates
• Ordered data storage

Example Scenarios:

• Unique ID storage
• Sorted data requirements
• Fast membership testing
• Removing duplicates from data

---

11. Important Considerations

Automatic Sorting:

• Elements always sorted
• Order maintained automatically
• Sorted by comparison operator
• Cannot change sort order (use custom comparator)

Uniqueness:

• Duplicates automatically removed
• Each element appears once
• Inserting duplicate has no effect

Performance:

• Insert: O(log n)
• Find: O(log n)
• Erase: O(log n)
• Balanced binary search tree

---

12. return 0;

This ends the program successfully.

---

Summary

• Set: container storing unique elements in sorted order.
• Duplicates automatically removed, elements automatically sorted.
• Operations: insert(), find(), erase(), count(), lower_bound(), upper_bound().
• Implemented as balanced binary search tree, O(log n) operations.
• Understanding sets enables efficient unique, sorted data storage.
• Essential for maintaining sorted, unique collections.

This program is fundamental for learning associative containers, understanding unique data storage, and preparing for advanced algorithms and data structures in C++ programs.