set container principle
std::set is a container in the C++ standard library that provides an ordered, non-duplicate collection of elements. The implementation of std::set is based on balanced binary search trees (red-black trees).
The following are the main features and implementation principles of std::set:
Ordering: The elements in std::set are stored in a specific order and remain ordered. By default, it uses the element’s comparison operator
<for sorting, but you can also specify the sorting method through a custom comparison function.Non-repetition: The elements in std::set are unique and duplicate elements are not allowed to exist. When inserting an element, if the element already exists, the insertion operation will not change the contents of std::set.
Balanced binary search tree: The implementation of std::set is based on a balanced binary search tree, and red-black trees are commonly used. The red-black tree is a self-balancing binary search tree. It maintains balance by coloring and rotating nodes, thereby ensuring that the height of the tree is always low, that is, it can be completed within the time complexity of O(logN) Find, insert and delete operations.
Search: std::set supports ordered search operations, and elements can be found by keywords. The average time complexity of a search operation is O(logN).
Insertion and deletion: The average time complexity of inserting and deleting elements is also O(logN), and the tree structure can be automatically adjusted to maintain balance.
It should be noted that the set container has an iterator, and the iterator is a read-only iterator.
set container API
#include <iostream>
#include<set>
using namespace std;
/*
* set<T> set1; //Default constructor
* set(const set & amp;set); //Default copy constructor
*
* set assignment operation
* set & amp;operator=(const set & amp;set);
* swap(set);
*
* set size operation
* size();
* empty();
*
* set insertion and deletion operations
* insert(element);
* clear();
* erase(position);//Delete the element at position
* erase(begin,end);//Delete elements in the interval [begin,end)
* erase(element);//Delete the element of element in the set container
*
* set search operation
* find(key);//Check whether the key key exists. If it exists, return the iterator of the key. If it does not exist, return set.end();
* count(key);//Find the number of keys
*/
void printSetint(set<int> & amp;set1){
set<int>::iterator it=set1.begin();
for(;it!=set1.end();it + + ){
cout<<*it<<" ";
}
cout<<endl;
}
void test(){
set<int> set1;
set1.insert(100);
set1.insert(900);
set1.insert(100000);
set1.insert(100000);
set1.insert(888888);
printSetint(set1);
set1.erase(900);
printSetint(set1);
auto it1=set1.find(888888);
if(it1!=set1.end()){
cout<<"Search results:"<<*it1<<endl;
}else{
cout<<"The element was not found"<<endl;
}
auto it2=set1.find(666);
if(it2!=set1.end()){
cout<<"Search results:"<<*it2<<endl;
}else{
cout<<"The element was not found"<<endl;
}
//Find the number of elements
cout<<set1.count(100000)<<endl;//The return result is 1, because set does not allow duplicate key values, otherwise the new value will overwrite the old value
}
int main()
{
test();
return 0;
}
Output result: 
Tips: I talked about the pair in the group, why the key values in the key-value pair are not allowed to be repeated, because the set container is sorted according to the key value. If the key value is repeated, the new value will overwrite the old value, especially when storing data. It is particularly important to note here that the characteristics of the set container can be used for unique purposes.
Challenge the rules and modify the set sorting rules
#include <iostream>
#include<set>
using namespace std;
/*
* set<T> set1; //Default constructor
* set(const set & amp;set); //Default copy constructor
*
* set assignment operation
* set & amp;operator=(const set & amp;set);
* swap(set);
*
* set size operation
* size();
* empty();
*
* set insertion and deletion operations
* insert(element);
* clear();
* erase(position);//Delete the element at position
* erase(begin,end);//Delete elements in the interval [begin,end)
* erase(element);//Delete the element of element in the set container
*
* set search operation
* find(key);//Check whether the key key exists. If it exists, return the iterator of the key. If it does not exist, return set.end();
* count(key);//Find the number of keys
*/
class myRule{
public:
bool operator()(int v1,int v2){
return v1>v2;
}
};
void printSetint(set<int,myRule> & amp;set1){
set<int,myRule>::iterator it=set1.begin();
for(;it!=set1.end();it + + ){
cout<<*it<<" ";
}
cout<<endl;
}
void test(){
set<int,myRule> set1;
set1.insert(100);
set1.insert(900);
set1.insert(100000);
set1.insert(100000);
set1.insert(888888);
printSetint(set1);
/*set1.erase(900);
printSetint(set1);*/
auto it1=set1.find(888888);
if(it1!=set1.end()){
cout<<"Search results:"<<*it1<<endl;
}else{
cout<<"The element was not found"<<endl;
}
auto it2=set1.find(666);
if(it2!=set1.end()){
cout<<"Search results:"<<*it2<<endl;
}else{
cout<<"The element was not found"<<endl;
}
//Find the number of elements
//cout<<set1.count(100000)<<endl;//The return result is 1, because set does not allow duplicate key values, otherwise the new value will overwrite the old value
}
int main()
{
test();
return 0;
}
Output result: 
Tips: The rules for sorting set containers in order have been changed from large to small. But the more troublesome thing is that after adding the function object, the rule modification is successful, but other functions are not recognized, such as erase and count. The rules have changed, and an error will be reported when calling them. The phenomenon is as follows: 
It means that we have to continue matching, and troubles are coming~
However, the set container under the existing rules is really boring. If you want to prosper, you must break the rules!
set container stores custom data
#include <iostream>
#include<set>
using namespace std;
/*
* set<T> set1; //Default constructor
* set(const set & amp;set); //Default copy constructor
*
* set assignment operation
* set & amp;operator=(const set & amp;set);
* swap(set);
*
* set size operation
* size();
* empty();
*
* set insertion and deletion operations
* insert(element);
* clear();
* erase(position);//Delete the element at position
* erase(begin,end);//Delete elements in the interval [begin,end)
* erase(element);//Delete the element of element in the set container
*
* set search operation
* find(key);//Check whether the key key exists. If it exists, return the iterator of the key. If it does not exist, return set.end();
* count(key);//Find the number of keys
*/
class myRule1;
class myRule{
friend class myRule1;
friend void printSetStudent(set<myRule,myRule1> & amp;set1);
private:
int num;
string name;
double score;
public:
myRule(){}
myRule(int num,string name,double score){
this->name=name;
this->num=num;
this->score=score;
}
#if 0
bool operator<(const myRule object)const{
return num<object.num;
}
#endif
};
class myRule1
{
public:
myRule1() {}
bool operator()(myRule ob1,myRule ob2){
if(ob1.num==ob2.num){
return ob1.score>ob2.score;
}else{
return ob1.num<ob2.num;
}
}
};
void printSetStudent(set<myRule,myRule1> & amp;set1){
set<myRule,myRule1>::const_iterator it=set1.begin();
for(;it!=set1.end();it + + ){
cout<<(*it).num<<" "<<(*it).name<<" "<<(*it).score<<endl;
}
}
void test(){
set<myRule,myRule1> set1;
set1.insert(myRule(100,"Lucy",99));
set1.insert(myRule(101,"Bob",99.8));
set1.insert(myRule(104,"Tom",100));
set1.insert(myRule(103,"Juck",99.6));
set1.insert(myRule(102,"Alice",100));
printSetStudent(set1);
/*set1.erase(900);
printSetint(set1);*/
/*auto it1=set1.find(888888);
if(it1!=set1.end()){
cout<<"Search results:"<<*it1<<endl;
}else{
cout<<"The element was not found"<<endl;
}
auto it2=set1.find(666);
if(it2!=set1.end()){
cout<<"Search results:"<<*it2<<endl;
}else{
cout<<"The element was not found"<<endl;
}
//Find the number of elements
cout<<set1.count(100000)<<endl;//The return result is 1, because set does not allow duplicate key values, otherwise the new value will overwrite the old value
*/
}
int main()
{
test();
return 0;
}
Output result: 
Tips: Customize a class as an element of the set container, use the myRule1 function object as a rule-breaker, customize the traversal algorithm, and implement the set container data to be traversed according to my custom rules.
set the upper and lower limits of the container
#include <iostream>
#include<set>
using namespace std;
/*
* lower_bound(keyelement);//Returns the iterator of the first key>=keyelement element
* upper_bound(keyelement);//Returns the iterator of the first key>keyelement element
* equal_range(keyelement);//Returns two iterators with upper and lower limits where key and keyelement are equal in the container
*/
void printSetInt(set<int> & amp;set1){
set<int>::iterator it=set1.begin();
for(;it!=set1.end();it + + ){
cout<<*it<<" ";
}
cout<<endl;
}
void test(){
set<int> set1;
set1.insert(90000);
set1.insert(19000);
set1.insert(800000);
set1.insert(77744);
set1.insert(897979);
printSetInt(set1);
set<int>::const_iterator it1;
it1=set1.lower_bound(77744);
if(it1!=set1.end()){
cout<<"Lower limit:"<<*it1<<endl;
}else{
cout<<"Not found"<<endl;
}
it1=set1.upper_bound(90000);
if(it1!=set1.end()){
cout<<"Upper limit:"<<*it1<<endl;
}else{
cout<<"Not found"<<endl;
}
//You can also return the upper and lower limits through pairs
pair<set<int>::const_iterator,set<int>::const_iterator> pair1;
pair1=set1.equal_range(77744);
if(pair1.first!=set1.end()){
cout<<"Lower limit:"<<*(pair1.first)<<endl;
}else{
cout<<"Not found"<<endl;
}
if(pair1.second!=set1.end()){
cout<<"Upper limit:"<<*(pair1.second)<<endl;
}else{
cout<<"Not found"<<endl;
}
}
int main()
{
test();
return 0;
}
Output result: 
Principle of multiset container
Multiset is one of the containers in the C++ standard library. It is an ordered associative container that can hold multiple elements with the same key value. The characteristic of multiset is that its internal elements are automatically sorted according to key values, and multiple identical key values are allowed to be stored.
The internal implementation of multiset is generally based on the Red-Black Tree data structure. A red-black tree is a self-balancing binary search tree with good average and worst-case performance. By using red-black trees, multiset can maintain the order of elements and support efficient insertion, deletion and search operations.
In a multiset container, elements are automatically sorted according to key values, and the sorting criteria are determined by the comparison function of the container or the default comparison function. When an element is inserted, the container inserts the element into the appropriate position according to the comparison function to maintain the order of the container. At the same time, multiset also provides a reverse iterator, allowing the container to be traversed in reverse order.
Since the multiset container allows the storage of multiple identical key values, its insertion operation has a constant time complexity of O(1), and the deletion and search operations have a logarithmic time complexity of O(logN), where N is the number of elements in the container. number.
Tips: The difference between a multiset container and a set is that the multiset container allows duplication of key values.
Multiset container API
#include <iostream>
#include<set>
using namespace std;
/*
* lower_bound(keyelement);//Returns the iterator of the first key>=keyelement element
* upper_bound(keyelement);//Returns the iterator of the first key>keyelement element
* equal_range(keyelement);//Returns two iterators with upper and lower limits where key and keyelement are equal in the container
*/
void printSetInt(multiset<int> & set1){
multiset<int>::iterator it=set1.begin();
for(;it!=set1.end();it + + ){
cout<<*it<<" ";
}
cout<<endl;
}
void test(){
multiset<int> set1;
set1.insert(90000);
set1.insert(19000);
set1.insert(800000);
set1.insert(77744);
set1.insert(897979);
set1.insert(90000);
set1.insert(19000);
set1.insert(800000);
set1.insert(77744);
set1.insert(897979);
printSetInt(set1);
multiset<int>::const_iterator it1;
it1=set1.lower_bound(77744);
if(it1!=set1.end()){
cout<<"Lower limit:"<<*it1<<endl;
}else{
cout<<"Not found"<<endl;
}
it1=set1.upper_bound(90000);
if(it1!=set1.end()){
cout<<"Upper limit:"<<*it1<<endl;
}else{
cout<<"Not found"<<endl;
}
//You can also return the upper and lower limits through pairs
pair<multiset<int>::const_iterator,multiset<int>::const_iterator> pair1;
pair1=set1.equal_range(77744);
if(pair1.first!=set1.end()){
cout<<"Lower limit:"<<*(pair1.first)<<endl;
}else{
cout<<"Not found"<<endl;
}
if(pair1.second!=set1.end()){
cout<<"Upper limit:"<<*(pair1.second)<<endl;
}else{
cout<<"Not found"<<endl;
}
}
int main()
{
test();
return 0;
}
Output result: 
Tips: The emergence of multiset containers solves the problem that the key values of set containers cannot be repeated. In some special data storage and other issues, multiset containers are used, and it is even more common to use the two together.
The knowledge points of the article match the official knowledge archives, and you can further learn relevant knowledge. Cloud native entry-level skill treeContainer orchestration (production environment k8s)kubelet, kubectl, kubeadm three-piece set 17037 people Currently studying the system