std::setis an associated container in the C++ standard library, which provides an ordered collection of unique elements. It provides efficient insertion, deletion and search operations, and can automatically maintain the order and uniqueness of elements.
1. Underlying implementation
std::setThe underlying principle is based onRed and black tree(Red-Black Tree). The red and black tree is a self-balancing binary search tree, which ensures the balance of the tree, thus ensuring that the time complexity of insertion, deletion and search operations is O(log n). It meets the following properties:
1. Each node is either red or black.
2. The root node is black. (The first element inserted)
3. All leaf nodes (NIL nodes) are black.
4. If a node is red, both of its child nodes are black.
5. For each node, the number of black nodes is the same on the simple path from that node to its descendant leaf nodes.
existstd::setIn , each element is inserted into the red and black tree as a node. When a new element is inserted,std::setIt will be inserted into the appropriate position according to the size of the element value, while maintaining the balance of the red and black trees. When looking for elements in a red and black tree, according to the characteristics of the red and black tree, you can efficiently locate the target element through binary search.
Since the red and black tree is an efficient self-balancing binary search tree,std::setAble to provide efficient insertion, deletion and search operations while maintaining the order and uniqueness of elements.
2. Member functions
std::setProvides a series of member functions to manipulate the set.
-
insert: Insert elements into the collection. -
emplace: Construct elements in-place in the collection. -
erase: Removes the specified element from the collection. -
find: Finds whether the specified element exists in the collection. -
count: Returns the number of elements in the set that are equal to the specified element (usually 0 or 1). -
clear: Clear all elements in the collection. -
size: Returns the number of elements in the collection. -
empty: Check whether the collection is empty. -
swap: Exchange the contents of two sets. -
begin: Returns an iterator pointing to the first element in the collection. -
end: Returns an iterator pointing to the position after the last element in the collection. -
lower_bound: Returns an iterator pointing to the first element not smaller than the given key value. -
upper_bound: Returns an iterator pointing to the first element larger than the given key value. -
equal_range: Returns a range containing all elements equal to the given key value. -
max_size: Returns the maximum number of elements that the set can accommodate.
Demo Demo:
std::set<int> set1;
(1);
(2);
(3);
(4);
std::cout<<()<<std::endl; // 4
std::cout<<()<<std::endl; // 0
std::cout<<*(2)<<std::endl; // 2
(2);
std::cout<<((2)==())<<std::endl; // 1
std::cout<<(3)<<std::endl; // 1
auto lower = set1.lower_bound(3);
auto upper = set1.upper_bound(3);
std::cout << "Lower bound of 3: " << *lower << std::endl; // Lower bound of 3: 3
std::cout << "Upper bound of 3: " << *upper << std::endl; // Upper bound of 4: 4
std::set<int> set2;
(set1);
std::cout<<()<<" "<<()<<std::endl; // 0 3
std::cout<<set1.max_size()<<std::endl; // 230584300921369395
for (auto it = (); it != (); ++it) {
std::cout << *it << " "<<std::endl; // 1 3 4
}
auto range = set2.equal_range(3);
std::cout<<*<<std::endl; // 3
3. Custom sorting rules
std::setThe default is sorted according to the size of the elements, and adopts a Strict Weak Ordering comparison method. This means that elements must support<Operator, elements are arranged in ascending order.
Sorting rules can be implemented by providing custom comparison functions or function objects. Two steps are required:
1、 Define a comparison function or function object：
Comparison function: define a function, accept two parameters, compare their sizes, and returntrueorfalse, represent their sequential relationship.
Function object (Functor): defines a class, overloadoperator(), so that the object can be called like a function, where the comparison logic is implemented.
2、 Pass the comparison function or function object tostd::setConstructor：
Creatingstd::setWhen an object is used, the comparison function or function object is passed as the second parameter to tell the set how to compare the order of elements.
#include <iostream>
#include <set>
// Custom comparison functionbool customCompare(int a, int b) {
// Implement custom comparison logic, here we take the absolute value size of integers as an example return abs(a) < abs(b);
}
// Custom function object (Functor)struct CustomComparator {
bool operator()(int a, int b) const {
// Implement custom comparison logic, here we take the square size of integers as an example return (a * a) < (b * b);
}
};
int main() {
// Create std::set using custom comparison function std::set<int, decltype(&customCompare)> customSet(customCompare);
// Create std::set using custom function object std::set<int, CustomComparator> functorSet;
// Insert element (5);
(-3);
(2);
(5);
(-3);
(2);
// traversal output results std::cout << "Custom compare function set: ";
for (int num : customSet) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Functor set: ";
for (int num : functorSet) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
4. Custom object sorting
whenstd::setWhen the elements stored in the replace the custom object, it needs to be overloaded<operator, so thatstd::setAbility to compare and sort objects. Overload<The purpose of the operator is to define the rules of comparison between objects to determine their order in the collection. so,std::setThese rules can be used to maintain the order of the collection.
Here is an example that demonstrates how to define a custom typePersonObject, and instd::setUse custom comparison functions to sort:
#include <iostream>
#include <set>
#include <string>
// Define a custom Person classclass Person {
private:
std::string name;
int age;
public:
Person(std::string name, int age) : name(name), age(age) {}
// Overload the < operator, for custom object comparison rules bool operator<(const Person& other) const {
// Compare by age return age < ;
}
// For easy output, overload the << operator friend std::ostream& operator<<(std::ostream& os, const Person& person) {
os << "Name: " << << ", Age: " << ;
return os;
}
};
int main() {
// Create a std::set container that stores Person objects and sort it using a custom comparison function std::set<Person> people;
// Insert some Person objects into the collection (Person("Alice", 30));
(Person("Bob", 25));
(Person("Charlie", 35));
// Iterate through elements in the output set. Since custom comparison rules are used, the output will be sorted in ascending order of age when outputting for (const auto& person : people) {
std::cout << person << std::endl;
}
return 0;
}
In this example,PersonClass hasnameandageTwo attributes, we reload<Operators define the comparison rules between objects and compare according to age. Then, we created astd::set<Person>Container and several inserted into itPersonObject. Since we use a custom comparison function, when we output elements in the container, they are arranged in ascending order of age.
V. Performance issues
std::setIt has stable and good performance characteristics in operations such as insertion, deletion and search, and is suitable for scenarios where orderly unique elements are needed to efficiently manage. However, in terms of space efficiency, it may be inferior to other data structures (e.g.std::unordered_set) That's superior. Therefore, when selecting a data structure, its performance characteristics need to be weighed according to specific needs.
1、 Performance of insertion and deletion operations：
The time complexity of the insertion and deletion operations is O(log n), where n is the number of elements in the set. This is because the red and black tree is a self-balancing binary search tree. Insertion and deletion operations will cause the tree to be rebalanced, but due to the characteristics of the red and black tree, the cost of rebalancing is controlled.
therefore,std::setThe performance in insertion and deletion is relatively stable and is not affected by the collection size.
2、 Find the performance of the operation：
The time complexity of the search operation is also O(log n), because the red and black trees have good balance and can ensure that elements are quickly searched under average conditions.std::setProvides efficient search function, suitable for scenarios where elements need to be retrieved quickly.
3、 Iterator performance：std::setThe iterator is a bidirectional iterator that supports forward and backward traversals. Its performance is independent of the set size and is an operation of constant time complexity.
This means traversingstd::setWhen it comes to elements in, the iterator's operations are very efficient regardless of the set size.
4、 Memory usage：std::setUsing red and black trees as the underlying data structure, it is an efficient balanced binary search tree, but it may take up more memory compared to other data structures (such as hash tables).
The red and black tree needs to maintain additional node information to maintain balance, so when storing the same number of elements,std::setIt may take up more memory space.
This is the article about the example project of C++ implementing std::set. For more related C++ std::set content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!