std::set
std::set is an associative container provided by the Standard Template Library (STL). It represents a sorted set of unique elements.
Each element in the set is unique, and the elements are stored in ascending order by default.
std::set uses a balanced binary search tree (usually Red-Black tree) to efficiently maintain the sorted order and to provide fast lookup, insertion, and deletion operations.
Table of Contents
Creating a std::set:
To use std::set, you need to include the <set> header.
#include <iostream>
#include <set>
int main() {
// Create an empty set of integers
std::set<int> mySet;
// Create a set with initial values using initializer list
std::set<int> initializedSet = {10, 20, 30, 40, 50};
return 0;
}
Advantages of std::set:
- Sorted and unique elements: The elements in the set are always sorted in ascending order and are unique, ensuring efficient search operations.
- Fast search, insert, and delete: The balanced binary search tree allows
std::setto provide logarithmic time complexity for these operations. - Automatic sorting: Elements are automatically sorted upon insertion, and maintaining sorted order is not the responsibility of the user.
Disadvantages of std::set:
- Overhead: The balanced binary search tree used internally may require additional memory overhead compared to other containers like
std::vectororstd::deque. - Lack of direct access: Unlike
std::vectororstd::deque, elements instd::setcannot be accessed directly using indexing, as it does not provide random access.
std::set is a great choice when you need a collection of elements that must be unique and maintained in sorted order. It is particularly useful when you need to frequently search for elements or perform range-based operations efficiently. If you require direct access using indexing or need to store duplicate elements, consider other containers like std::vector or std::unordered_set.
Important Functions of std::set:
insert(value):
Inserts the specified element into the set.
- Time Complexity: Logarithmic time (
O(log n)), wherenis the number of elements in the set. - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
mySet.insert(40); // After this, mySet contains {10, 20, 30, 40}
return 0;
}
erase(value):
Removes the specified element from the set, if it exists.
- Time Complexity: Logarithmic time (
O(log n)), wherenis the number of elements in the set. - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
mySet.erase(20); // After this, mySet contains {10, 30}
return 0;
}
find(value):
Searches for the specified element in the set and returns an iterator to it. If the element is not found, it returns the end() iterator.
- Time Complexity: Logarithmic time (
O(log n)), wherenis the number of elements in the set. - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
auto it = mySet.find(20);
if (it != mySet.end()) {
std::cout << "Element found: " << *it << std::endl;
} else {
std::cout << "Element not found." << std::endl;
}
return 0;
}
count(value):
Returns the number of occurrences of the specified element in the set (since it only contains unique elements, it will return either 0 or 1).
- Time Complexity: Logarithmic time (
O(log n)), wherenis the number of elements in the set. - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
int count = mySet.count(20); // count = 1
return 0;
}
size():
Returns the number of elements in the set.
- Time Complexity: Constant time (
O(1)). - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
std::cout << "Size of the set: " << mySet.size() << std::endl; // Output: 3
return 0;
}
empty():
Checks if the set is empty.
- Time Complexity: Constant time (
O(1)). - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet;
if (mySet.empty()) {
std::cout << "Set is empty." << std::endl;
} else {
std::cout << "Set is not empty." << std::endl;
}
return 0;
}
clear():
Removes all elements from the set.
- Time Complexity: Linear time (
O(n)), wherenis the number of elements in the set. - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
mySet.clear(); // After this, mySet is empty
return 0;
}
begin():
Returns an iterator to the beginning of the set (first element).
- Time Complexity: Constant time (
O(1)). Space Complexity: Constant space (O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
auto it = mySet.begin();
std::cout << "First element: " << *it << std::endl; // Output: 10
return 0;
}
end():
Returns an iterator to the end of the set (past-the-end element).
- Time Complexity: Constant time (
O(1)). - Space Complexity: Constant space (
O(1)).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
auto it = mySet.end();
--it; // Move iterator to the last element
std::cout << "Last element: " << *it << std::endl; // Output: 30
return 0;
}
rbegin():
Returns a reverse iterator to the beginning of the reversed set (last element).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
auto it = mySet.rbegin();
std::cout << "First element (reversed): " << *it << std::endl; // Output: 30
return 0;
}
rend():
Returns a reverse iterator to the end of the reversed set (before-the-beginning element).
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {10, 20, 30};
auto it = mySet.rend();
--it; // Move iterator to the last element in the reversed set
std::cout << "Last element (reversed): " << *it << std::endl; // Output: 10
return 0;
}