1 Basic concepts of set
Introduction:
- All elements are automatically sorted when inserted
Essence:
- set/multiset belongs to Associative Container, and the underlying structure is implemented using Binary Tree.
The difference between set and multiset:
- set does not allow duplicate elements in the container
- multiset allows duplicate elements in the container
2 set construction and assignment
Function description: Create set container and assign value
structure:
set//Default constructor:st; set(const set & amp;st);//Copy constructor
Assignment:
set & amp; operator=(const set & amp;st);//Overload the equal sign operator
Example:
#include <set>
void printSet(set<int> & s)
{<!-- -->
for (set<int>::iterator it = s.begin(); it != s.end(); it + + )
{<!-- -->
cout << *it << " ";
}
cout << endl;
}
//Construction and assignment
void test01()
{<!-- -->
set<int> s1;
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
printSet(s1);
//copy construction
set<int>s2(s1);
printSet(s2);
//assignment
set<int>s3;
s3 = s2;
printSet(s3);
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summarize:
- Use insert when inserting data into the set container
- The data inserted into the set container will be automatically sorted
3 set size and exchange
Function description:
- Count the size of set containers and exchange set containers
Function prototype:
size();//Returns the number of elements in the containerempty();//Determine whether the container is emptyswap(st);//Swap two collection containers
Example:
#include <set>
void printSet(set<int> & s)
{<!-- -->
for (set<int>::iterator it = s.begin(); it != s.end(); it + + )
{<!-- -->
cout << *it << " ";
}
cout << endl;
}
//size
void test01()
{<!-- -->
set<int> s1;
\t
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
if (s1.empty())
{<!-- -->
cout << "s1 is empty" << endl;
}
else
{<!-- -->
cout << "s1 is not empty" << endl;
cout << "The size of s1 is: " << s1.size() << endl;
}
}
//exchange
void test02()
{<!-- -->
set<int> s1;
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
set<int> s2;
s2.insert(100);
s2.insert(300);
s2.insert(200);
s2.insert(400);
cout << "Before exchange" << endl;
printSet(s1);
printSet(s2);
cout << endl;
cout << "After exchange" << endl;
s1.swap(s2);
printSet(s1);
printSet(s2);
}
int main() {<!-- -->
//test01();
test02();
system("pause");
return 0;
}
Summarize:
- Statistics size – size
- Determine whether it is empty – empty
- swap container – swap
4 set insertion and deletion
Function description:
- set container to insert data and delete data
Function prototype:
insert(elem);//Insert elements in the container.clear();//Clear all elementserase(pos);//Delete the element pointed to by the pos iterator and return the iterator of the next element.erase(beg, end);//Delete all elements in the interval [beg, end) and return the iterator of the next element.erase(elem);//Delete the element whose value is elem in the container.
Example:
#include <set>
void printSet(set<int> & s)
{<!-- -->
for (set<int>::iterator it = s.begin(); it != s.end(); it + + )
{<!-- -->
cout << *it << " ";
}
cout << endl;
}
//Insert and delete
void test01()
{<!-- -->
set<int> s1;
//Insert
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
printSet(s1);
\t//delete
s1.erase(s1.begin());
printSet(s1);
s1.erase(30);
printSet(s1);
//clear
//s1.erase(s1.begin(), s1.end());
s1.clear();
printSet(s1);
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summarize:
- insert – insert
- Delete – erase
- Clear – clear
5 set search and statistics
Function description:
- Search data and statistical data for set containers
Function prototype:
find(key);//Find whether the key exists. If it exists, return the iterator of the element of the key; if it does not exist, return set.end();count(key);//Count the number of elements in key
Example:
#include <set>
//Search and count
void test01()
{<!-- -->
set<int> s1;
//Insert
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
\t
//Find
set<int>::iterator pos = s1.find(30);
if (pos != s1.end())
{<!-- -->
cout << "Element found: " << *pos << endl;
}
else
{<!-- -->
cout << "Element not found" << endl;
}
//Statistics
int num = s1.count(30);
cout << "num = " << num << endl;
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summarize:
- Find – find (returns an iterator)
- Statistics – count (for set, the result is 0 or 1)
6 The difference between set and multiset
Learning Objectives:
- Master the difference between set and multiset
Difference:
- Set cannot insert duplicate data, but multiset can
- When set inserts data, it will return the insertion result, indicating whether the insertion is successful.
- multiset does not detect data so duplicate data can be inserted
Example:
#include <set>
//The difference between set and multiset
void test01()
{<!-- -->
set<int> s;
pair<set<int>::iterator, bool> ret = s.insert(10);
if (ret.second) {<!-- -->
cout << "First insertion successful!" << endl;
}
else {<!-- -->
cout << "First insertion failed!" << endl;
}
ret = s.insert(10);
if (ret.second) {<!-- -->
cout << "The second insertion was successful!" << endl;
}
else {<!-- -->
cout << "The second insertion failed!" << endl;
}
//multiset
multiset<int> ms;
ms.insert(10);
ms.insert(10);
for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it + + ) {<!-- -->
cout << *it << " ";
}
cout << endl;
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summarize:
- If inserting duplicate data is not allowed, you can use set
- If you need to insert duplicate data, use multiset
7 pair creation
Function description:
- Data appearing in pairs, using pairs to return two data
Two ways to create:
pairpair
Example:
#include <string>
//Pair creation
void test01()
{<!-- -->
pair<string, int> p(string("Tom"), 20);
cout << "Name: " << p.first << " Age: " << p.second << endl;
pair<string, int> p2 = make_pair("Jerry", 10);
cout << "Name: " << p2.first << " Age: " << p2.second << endl;
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summarize:
There are two ways to create pairs, just remember one.
8 set container sorting
learning target:
- The default sorting rules for set containers are from small to large. Learn how to change the sorting rules.
Main technical points:
- Using functors, you can change the sorting rules
Example 1 set stores built-in data types
#include <set>
classMyCompare
{<!-- -->
public:
bool operator()(int v1, int v2) {<!-- -->
return v1 > v2;
}
};
void test01()
{<!-- -->
set<int> s1;
s1.insert(10);
s1.insert(40);
s1.insert(20);
s1.insert(30);
s1.insert(50);
//Default from small to large
for (set<int>::iterator it = s1.begin(); it != s1.end(); it + + ) {<!-- -->
cout << *it << " ";
}
cout << endl;
//Specify sorting rules
set<int,MyCompare> s2;
s2.insert(10);
s2.insert(40);
s2.insert(20);
s2.insert(30);
s2.insert(50);
for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it + + ) {<!-- -->
cout << *it << " ";
}
cout << endl;
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summary: Use functors to specify the sorting rules of the set container
Example 2 set stores custom data types
#include <set>
#include <string>
class Person
{<!-- -->
public:
Person(string name, int age)
{<!-- -->
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
class comparePerson
{<!-- -->
public:
bool operator()(const Person & amp; p1, const Person & amp;p2)
{<!-- -->
//Sort by age in descending order
return p1.m_Age > p2.m_Age;
}
};
void test01()
{<!-- -->
set<Person, comparePerson> s;
Person p1("Liu Bei", 23);
Person p2("Guan Yu", 27);
Person p3("Zhang Fei", 25);
Person p4("Zhao Yun", 21);
s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);
for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it + + )
{<!-- -->
cout << "Name: " << it->m_Name << " Age: " << it->m_Age << endl;
}
}
int main() {<!-- -->
test01();
system("pause");
return 0;
}
Summarize:
For custom data types, set must specify a collation before it can insert data.