Set: Container, C++

Set Container in C++: Usage and Operations

In C++, the set container is part of the Standard Template Library (STL). A set is a container that stores unique elements in a specific order, usually sorted according to a comparison function. This container is implemented using a balanced binary search tree (often Red-Black Tree), which ensures that insertions, deletions, and lookups occur in logarithmic time complexity. This makes set ideal for scenarios where you need to maintain a collection of unique items and also require the elements to be sorted.

In this guide, we will explore everything about the set container, including how to construct sets, perform common operations, and effectively utilize its capabilities in C++.

---

Table of Contents

1. Introduction to Set in C++
2. Different Ways to Construct a Set
3. Common Operations on Set
   • insert()
   • erase()
   • find()
   • count()
   • size()
   • empty()
   • clear()
4. Working with Custom Data Types
5. Iterators in Sets
6. Summary and Best Practices

---

1. Introduction to Set in C++

A set in C++ is a container that stores unique elements, sorted in a specific order (typically ascending by default). It provides efficient access to elements, with logarithmic time complexity for common operations like insertion, deletion, and lookup.

Key Features:

• Unique Elements: Each element in a set is unique. Duplicates are automatically discarded.
• Sorted Order: Elements are stored in sorted order (default is ascending order).
• Efficient Operations: Operations such as insertion, deletion, and search occur in O(log n) time due to the tree-based implementation.

When to Use:

• Use set when you need to store unique elements and want them to be automatically sorted.
• If you don't need the elements to be ordered, consider using unordered_set for potentially faster operations.

---

2. Different Ways to Construct a Set

You can create a set in several ways depending on your needs.

2.1 Default Constructor

The default constructor creates an empty set.

set<int> s;

This creates an empty set of integers, which can be populated later.

2.2 Constructor with Initializer List

You can initialize a set directly with a list of values.

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

This creates a set containing the values 1, 2, 3, 4, 5 sorted in ascending order.

2.3 Constructor with Another Set

You can create a set by copying elements from another set.

set<int> s1 = {1, 2, 3, 4, 5};
set<int> s2(s1);  // Initializes s2 as a copy of s1

2.4 Constructor with Another Container

You can create a set by copying elements from another container such as a vector or list.

vector<int> v = {1, 2, 3, 4, 5};
set<int> s(v.begin(), v.end());  // Initializes a set using iterators from a vector

2.5 Assignment Operator

The assignment operator allows you to copy elements from one set to another.

set<int> s1 = {1, 2, 3};
set<int> s2;
s2 = s1;  // Now s2 contains the same elements as s1

The assignment operator performs a deep copy, meaning that the elements of s1 are fully copied into s2.

---

3. Common Operations on Set

3.1 insert()

The insert() function adds an element to the set. If the element already exists, it will not be added again.

Syntax:

• Insert a single element:

  s.insert(element);

• Insert multiple elements using an initializer list:

  s.insert({element1, element2, ...});

• Insert elements from another container:

  s.insert(container.begin(), container.end());

Example:

set<int> s;

// Insert a single element
s.insert(10);  // Inserts 10
s.insert(20);  // Inserts 20
s.insert(30);  // Inserts 30

// Insert multiple elements
s.insert({40, 50, 60});  // Inserts 40, 50, and 60

// Insert elements from another container
vector<int> v = {70, 80, 90};
s.insert(v.begin(), v.end());  // Inserts 70, 80, 90

After these operations, the set s will contain: {10, 20, 30, 40, 50, 60, 70, 80, 90}.

3.2 erase()

The erase() function removes an element from the set.

Syntax:

• Erase a single element:

  s.erase(element);

• Erase an element using an iterator:

  s.erase(iterator);

• Erase a range of elements:

  s.erase(start_iterator, end_iterator);

Example:

set<int> s = {10, 20, 30, 40, 50};

// Erase a single element
s.erase(20);  // Removes 20

// Erase using an iterator
auto it = s.find(30);
s.erase(it);  // Removes 30

// Erase a range of elements
s.insert({10, 20, 30, 40, 50});  // Reinsert elements for demonstration
auto start = s.find(10);
auto end = s.find(40);
s.erase(start, end);  // Removes 10, 20, and 30

After these operations, the set s will contain: {40, 50}.

3.3 find()

The find() function searches for an element in the set and returns an iterator to it if found, or end() if not found.

Syntax:

auto it = s.find(element);

Example:

set<int> s = {10, 20, 30};
auto it = s.find(20);
if (it != s.end()) {
    cout << "Element found: " << *it << endl;  // Outputs: Element found: 20
} else {
    cout << "Element not found." << endl;
}

3.4 count()

The count() function returns the number of occurrences of an element in the set. Since set only allows unique elements, it will return either 0 or 1.

Syntax:

size_t count = s.count(element);

Example:

set<int> s = {10, 20, 30};
cout << "Count of 20: " << s.count(20) << endl;  // Outputs: Count of 20: 1
cout << "Count of 40: " << s.count(40) << endl;  // Outputs: Count of 40: 0

3.5 size()

The size() function returns the number of elements in the set.

Syntax:

size_t size = s.size();

Example:

set<int> s = {10, 20, 30};
cout << "Size of set: " << s.size() << endl;  // Outputs: Size of set: 3

3.6 empty()

The empty() function checks whether the set is empty.

Syntax:

bool isEmpty = s.empty();

Example:

set<int> s;
cout << "Is set empty? " << (s.empty() ? "Yes" : "No") << endl;  // Outputs: Yes
s.insert(10);
cout << "Is set empty? " << (s.empty() ? "Yes" : "No") << endl;  // Outputs: No

3.7 clear()

The clear() function removes all elements from the set.

Syntax:

s.clear();

Example:

set<int> s = {10, 20, 30};
s.clear();  // Removes all elements

After calling clear(), the set will be empty.

---

4. Working with Custom Data Types

You can store custom data types in a set, provided that the type supports comparison using the < operator or a custom comparator.

Example:

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

struct Person {
    string name;
    int age;

    bool operator<(const Person& other) const {
        return name < other.name;  // Define sorting order by name
    }
};

int main() {
    set<Person> people;

    people.insert({"Alice", 30});
    people.insert({"Bob", 25});
    people.insert({"Charlie", 35});

    for (const auto& person : people) {
        cout << person.name << " - " << person.age << endl;
    }
    return 0;
}

In this example, the Person struct is stored in a set, and the sorting order is based on the name field.

---

5. Iterators in Sets

You can iterate over the elements of a set using iterators, just like other STL containers.

Syntax:

for (auto it = s.begin(); it != s.end(); ++it) {
    // Access the element via *it
}

You can also use range-based for loops:

for (const auto& element : s) {
    // Access each element
}

---

6. Summary and Best Practices

Key Takeaways:

• set is ideal for storing unique elements that need to be sorted.
• Common operations like insert(), erase(), and find() are efficient due to the tree-based implementation.
• Use set when you need elements to be stored in a specific order.
• To store custom types, ensure they support the < operator or provide a custom comparator.

Best Practices:

• Ensure your custom types can be compared using the < operator or provide a custom comparator.
• Use set when the order of elements is important and uniqueness is required.
• If performance is critical and order doesn't matter, consider using unordered_set.

This concludes our guide on using set in C++. It's an essential tool for many common programming tasks where sorting and uniqueness are required.