Associative containers - overview of set, multiset, map, and multimap knowledge points
1. Associated container:
The underlying implementation uses a red black tree. Initialization, traversal, count, find and insert (set and map need to judge whether the insertion is successful). Custom types need to overwrite Compare (std::less, std::greater, function object).
2.set
1. You cannot store elements with the same keyword key. The keyword must be unique
2. By default, it is arranged in ascending order
3. The underlying implementation is a red black tree -- it does not support data modification and subscript access
4. STD:: greater < int >, STD:: less < int >, custom sorting, imitation function writing
5.insert successfully returns true or false, ret.second, the second parameter of pair
Five characteristics of red black tree:
1. Nodes are either red or black
2. The root node is black
3. Leaf nodes are also black
4. If a node is red, its left and right child nodes must be black
5. All paths from the root node to the leaf node should ensure the same number of black nodes
3.multiset
1. You can store elements with the same keyword key, but the keyword is not unique
2. By default, it is arranged in ascending order
3. The underlying implementation is red black tree
4. Different from set, insert must be successful in inserting data, and there is no return value
4.map
1. It stores key value pairs, that is, pairs, that is, pair < const key, value >, and the key value must be unique and cannot be repeated
2. By default, the keyword keys are arranged in ascending order
3. The underlying implementation is red black tree
Find:
auto it = numbers.lower_ bound(2);//>= First position of key
auto it2 = numbers.upper_ bound(2);//> First position of key
5.mutilmap
1. You can store elements with the same keyword key, but the keyword is not unique
2. By default, it is arranged in ascending order
3. The underlying implementation is red black tree
4. Difference from map: keywords are not unique. When inserting, it must be successful
6.insert reference interface
1.value_type. If set/multiset represents key,
If map/multimap represents pair < const key, value > STD:: pair < iterator, bool >
2.insert( const value_type& value ); // Insert lvalue
std::pair<iterator,bool>
3.insert( value_type&& value ); Iterator / / insert right value
4.insert( iterator hint, const value_type& value );// Get the iterator of a location and insert it into that location
5.iterator insert( const_iterator hint, const value_type& value );
6.iterator insert( const_iterator hint, value_type&& value );
7.template< class InputIt > void insert( InputIt first, InputIt last );
8.void insert( std::initializer_list<value_type> ilist );// Insert list
9.insert_return_type insert(node_type&& nh);
10.iterator insert(const_iterator hint, node_type&& nh);
set case
1.set finds the element find. If the element exists in set, it returns the iterator of the element. Otherwise, it returns set.end()
2.set container insert
2.1 the return result of insert is a pair of pairs, first is the position iterator of the current insertion value in set, and second represents whether the insertion is successful
2.2 insert data into the set in the form of list: both methods (iterator range and large list) return void
3. Delete erase of set: 1. Delete by iterator position 2. Delete by iterator range (closed on the left and open on the right)
3. The return value is the iterator corresponding to the last element deleted.
4. Subscript operation is not allowed in set. In order to protect the structural stability of the red black tree, the iterator content is not allowed to be modified, * it = 20 -- > error
#include <math.h>
#include <iostream>
#include <set>
#include <utility>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using std::ostream_iterator;
using std::cout;
using std::endl;
using std::set;
using std::pair;
using std::string;
using std::vector;
template <typename Container>
void display(const Container &con)
{
for(auto &elem : con)
{
cout << elem << " ";
}
cout << endl;
}
void test01()
{
set<int> number = {1,3,5,7,9,11,13,7,8,10,1};
display(number);//1 3 5 7 8 9 10 11 13
cout<<"1.set Find element find:"<<endl;
auto it = number.find(3);//If the element exists in the set, the iterator of the element is returned
if(it == number.end())
{
cout<<"The element is not in the set in"<<endl;
}
else
{
cout<<"The element is in set in"<<endl;
}
cout<<"2.set Container insertion operation insert:"<<endl;
//The return result of insert is a pair of pairs. The first is the position iterator of the current insertion value in set, and the second represents whether the insertion is successful
pair<set<int>::iterator, bool> ret = number.insert(2);
if(ret.second == true)
{
cout<<"Insert element succeeded"<<*ret.first<<endl;
cout<<ret.second<<endl;
}
else
{
cout<<"The element is in set Failed to insert because there is in"<<endl;
cout<<*ret.first<<endl;//10
cout<<ret.second<<endl;//0
}
//first is the corresponding iterator of 2 in set
copy(ret.first,number.end(),ostream_iterator<int>(cout," "));
//2 3 5 7 8 9 10 11 13
cout<<endl;
cout<<"3.In the form of a list set Insert data into:Both methods return void"<<endl;
cout<<"3.1 Insert as iterator:"<<endl;
vector<int> vec = {10,20,30};
number.insert(vec.begin(),vec.end());
display(number);//1 2 3 5 7 8 9 10 11 13 20 30
cout<<"3.2 Insert as braces"<<endl;
number.insert(std::initializer_list<int>({-9,100,200,300}));
//display(number);
copy(number.begin(),number.end(),ostream_iterator<int>(cout," "));//Output iterator mode
//-9 1 2 3 5 7 8 9 10 11 13 20 30 100 200 300
cout<<endl;
cout<<"4.set Deletion of erase:1.Delete 2 by iterator location.Delete by range:"<<endl;
cout<<"4.1 Delete by iterator location"<<endl;
it = number.begin();//-9
it++;//1
it++;//2. The bidirectionalitor bidirectional iterator used for the iterator in set can be used for + +--
it++;//3
it--;//2
number.erase(it);//Delete by iterator position, delete the second iterator, and the corresponding value is 2
display(number);//-9 1 3 5 7 8 9 10 11 13 20 30 100 200 300
cout<<"4.2 Delete by iterator range:Left closed right open"<<endl;
it=number.begin();
for(int idx = 0;idx<5;idx++)
{
++it;
}
cout<<*it<<endl;//8
number.erase(number.begin(),it);//Left closed right open
display(number);//8 9 10 11 13 20 30 100 200 300
}
int main()
{
test01();
return 0;
}
/*
1 3 5 7 8 9 10 11 13
1.set Find element find:
The element is in set
2.set Container insert operation insert:
Insert element succeeded 2
1
2 3 5 7 8 9 10 11 13
3.Insert data into the set as a list: void is returned in both methods
3.1 Insert as iterator:
1 2 3 5 7 8 9 10 11 13 20 30
3.2 Insert as braces
-9 1 2 3 5 7 8 9 10 11 13 20 30 100 200 300
4.set Delete erase:1. Delete by iterator location 2. Delete by range:
4.1 Delete by iterator location
-9 1 3 5 7 8 9 10 11 13 20 30 100 200 300
4.2 Delete by iterator range:
8
8 9 10 11 13 20 30 100 200 300
*/The set container implements custom type storage -- overriding the Compare function
Custom type Point
class Point
{
public:
Point(int ix=0,int iy=0)
:_ix(ix),_iy(iy)
{
}
float getDistance()const
{
return hypot(_ix,_iy);//Square the sum of the squares of two numbers to find the distance between the coordinates and O
}
~Point()
{
}
//Overload the shift left operator to print the object directly
friend std::ostream &operator<<(std::ostream &os,const Point &rhs);
friend bool operator<(const Point &lhs,const Point &rhs);
//friend bool operator>(const Point &lhs,const Point &rhs);
friend struct CompareSet;//Function object
private:
int _ix;
int _iy;
};
std::ostream& operator<<(std::ostream &os,const Point &rhs)
{
os << "(" << rhs._ix
<< ", " << rhs._iy
<< ")";
return os;
}
bool operator<(const Point &lhs,const Point &rhs)
{
if(lhs.getDistance() < rhs.getDistance())
{
return true;
}
else if(lhs.getDistance() == rhs.getDistance())//Equal cases need to be classified and discussed
{
if(lhs._ix < rhs._ix)
{
return true;
}
else if(lhs._ix == rhs._ix)
{
if(lhs._iy < rhs._iy)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
else//lhs.getDistance() > rhs.getDistance()
{
return false;
}
}
//Function object
struct CompareSet
{
bool operator()(const Point &lhs,const Point &rhs)const
{
if(lhs.getDistance() < rhs.getDistance())
{
return true;
}
else if(lhs.getDistance() == rhs.getDistance())//Equal cases need to be classified and discussed
{
if(lhs._ix < rhs._ix)
{
return true;
}
else if(lhs._ix == rhs._ix)
{
if(lhs._iy < rhs._iy)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
else//lhs.getDistance() > rhs.getDistance()
{
return false;
}
}
};
//For custom types, use of set
void test02()
{
Point p1(3,4);
cout<<p1.getDistance()<<endl;
cout<<p1<<endl;
set<Point,std::less<Point>> point={
Point(1,2),
Point(-1,-2),
Point(3,2),
Point(2,4),
Point(3,5)
} ;
// set<Point,CompareSet> point={
// Point(1,2),
// Point(-1,-2),
// Point(3,2),
// Point(2,4),
// Point(3,5)
// } ;
display(point);
}
/*test02 Operation results:
5
(3, 4)
(-1, -2) (1, 2) (3, 2) (2, 4) (3, 5)
*/The set container stores the custom type Person
class Person
{
public:
Person(int num=0, string name="hello world")
:_num(num),_name(name)
{
}
friend bool operator<(const Person &lhs,const Person &rhs);
friend std::ostream& operator<<(std::ostream &os,const Person &rhs);
friend struct MyPersonSet;//Function object form
private:
int _num;
string _name;
};
bool operator<(const Person &lhs,const Person &rhs)
{
if(lhs._num != rhs._num)
{
return lhs._num < rhs._num;
}
else
{
return lhs._name!=rhs._name;
}
}
std::ostream& operator<<(std::ostream &os,const Person &rhs)
{
os<<rhs._num<<":"<<rhs._name;
return os;
}
struct MyPersonSet
{
bool operator()(const Person &lhs, const Person &rhs)
{
if(lhs._num != rhs._num)
{
return lhs._num < rhs._num;
}
else
{
return lhs._name!=rhs._name;
}
}
};
//set custom type
void test03()
{
set<Person,std::less<Person>> person = {//Overload the < operator in the custom class Person
Person(1,"Sun WuKong"),
Person(2,"White dragon horse"),
Person(3,"Monk Sha"),
Person(3,"Tang Monk"),
Person(6,"Zhu Bajie"),
Person(9,"Baigujing"),
Person(1,"Sun WuKong"),
Person(9,"Baigujing")
};
display(person);
}
/*
1:Monkey King 2: white dragon horse 3: Tang Monk 3: sand monk 6: Pig Bajie 9: Baigujing
*/
//Function object form
void test04()
{
set<Person,MyPersonSet> person = {
Person(1,"Sun WuKong"),
Person(2,"White dragon horse"),
Person(3,"Monk Sha"),
Person(3,"Tang Monk"),
Person(6,"Zhu Bajie"),
Person(9,"Baigujing"),
Person(1,"Sun WuKong"),
Person(9,"Baigujing")
};
display(person);
}
/*
1:Monkey King 2: white dragon horse 3: Tang Monk 3: sand monk 6: Pig Bajie 9: Baigujing
*/map case code
1. The operation of map container is mostly the same as that of set
2.map allows subscript access. If the accessed key value does not exist, the key will be automatically added to the container with a default value
#include <iostream>
#include <math.h>
#include <iostream>
#include <map>
#include <utility>
#include <string>
using std::cout;
using std::endl;
using std::map;
using std::pair;
using std::string;
template <typename Container>
void display(const Container &con)
{
for(auto &elem : con)
{
cout << elem.first << " " << elem.second << endl;
}
}
void test01()
{
map<string, string> number={
{"021", "Beijing"},
{"027", "Wuhan"},
{"0755", "Shenzhen"},
{"022", "Tianjin"},
pair<string, string>("0653", "Beijing"),
pair<string, string>("021", "Nanjing"),
std::make_pair("0712", "Guangzhou"),
std::make_pair("022", "Guangzhou")
};
cout<<"1.map Insert operation for:"<<endl;
auto ret = number.insert(pair<string,string>("999", "Suzhou"));
if(ret.second)
{
cout << "The element is not in the map In, insert succeeded "
<< ret.first->first << " "
<< ret.first->second << endl;
}
else
{
cout << "The element does not exist, map Insert failed in" << endl;
}
display(number);
cout<<"2.map Subscript access operation:"<<endl;
cout << "number[\"1\"] = " << number["022"] << endl;
cout << "number[\"10\"] = " << number["10"] << endl;
display(number);
}
int main()
{
test01();
return 0;
}