Content reference: https://www.bilibili.com/video/BV1et411b73Z?p=231

set / multiset container

set container

Basic concepts

Introduction: all elements are automatically sorted when inserted
Essence: set / multiset is an associative container, and the underlying structure is implemented by binary tree

Difference between set and multiset

• set does not allow duplicate elements in the container, and multiset allows the container to
• set will return the insertion result when inserting data, indicating whether the insertion is successful
• multiset does not detect data, so duplicate data can be inserted

set construction and assignment

structure

• set<T> st; // Default constructor;
• set(const set& st); // copy constructor
  assignment
• ` set& operator=(const set &st); // Overloaded equal sign operator

case

void prt(set<int>& st)
{
    for (auto i : st)
        cout << i << " ";
    cout << endl;
}

void test1()
{
    set<int> s1;
    s1.insert(10);
    s1.insert(30);
    s1.insert(20);
    s1.insert(30);
    s1.insert(10);
    prt(s1);	// Output 10 20 30

	set<int> s2;
    s2.insert(10);
    s2.insert(20);
    s2.insert(30);
    prt(s2);	// Also output 10 20 30
}

summary

• When all elements of the set container are inserted, they are automatically sorted
• Duplicate values are not allowed to be inserted in the set container

set size and swap

• size();
• empty();
• swap(st);

set insert and delete

• insert(elem);
• clear();
• erase(pos);
• erase(beg, end);
• erase(elem); // Delete the element with element in the container

set lookup and statistics

• find(key); // If the key exists, it returns the iterator of the key element. If it does not exist, it returns set end()
• count(key); // Count the number of key elements. Because there are no duplicate elements in set, 1 is always returned

pair group creation

The implementation of insert operation of set is pair < iterator, bool >, and the implementation of insert operation of multiset is < iterator >

• pair<type, type> pr(value1, value2);
• pair<type, type> pr = make_pair(value1, value2);

case

void test1()
{
    pair<string, int> p("Tom", 23);
    cout << p.first << " " << p.second << endl;
    
    pair<string, int> p2 = make_pair("Bob", 33);
    cout << p2.first << " " << p2.second << endl;
}

set container sort

Using the imitation function, the sorting rules can be changed

Case 1 - built in data types

class Cmp {	// Specify a functor to sort in descending order
public:
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

void sprt(set<int, Cmp>& st)
{
    for (auto i : st)
        cout << i << " ";
    cout << endl;
}

void test2()
{
    // Specifies that the collation is from large to small
    set<int, Cmp> s1;
    s1.insert(11);
    s1.insert(18);
    s1.insert(12);
    s1.insert(15);
    s1.insert(14);
    s1.insert(11);
    sprt(s1);	// Output 18 15 14 12 11
}

Case 2 - custom data types

For custom data types, you must specify a collation

class Person {	// Custom data type
public:
    Person(string name, int age)
    {
        this->name_ = name;
        this->age_ = age;
    }

    string name_;
    int age_;
};

class CpmPers {	// User defined imitation function to sort in descending order
public:
    bool operator()(const Person& a, const Person& b)
    {
        // In descending order of age
        return a.age_ > b.age_;
    }
};

void test3()
{
    set<Person, CpmPers> s1;
    Person p1("Lucy", 22);
    Person p2("Mary", 24);
    Person p3("Jack", 23);
    Person p4("Tomi", 25);
	// The default insertion sort order is by string, so an error occurs
    s1.insert(p1);
    s1.insert(p2);
    s1.insert(p3);
    s1.insert(p4);

    for (set<Person, CpmPers>::iterator it = s1.begin();
    	 it != s1.end(); ++it) {
        cout << "Name: " << it->name_ 
        	 << ", Age: " << it->age_ << endl;
    }
    /* Output results:
	    Name: Tomi, Age: 25
		Name: Mary, Age: 24
		Name: Jack, Age: 23
		Name: Lucy, Age: 22
	*/
}

map / multimap container

map

concept

• All elements in the map are pair
• The first element in pair is key (key value), which serves as an index, and the second element is value (real value)
• All elements are automatically sorted according to the key value of the element
• map / multimap belongs to association container, and the underlying structure is implemented by binary tree.
• You can quickly find the value value according to the key value

The difference between map and multimap

• Duplicate key value elements in containers are not allowed in map
• multimap allows duplicate key value elements in the container

map construction and assignment

• map<T1, T2> mp; // Default constructor
• map<const map& mp); // copy constructor
• map& operator=(const map& mp); // Overload equal sign assignment operator

map size and swap

• size(); // Returns the number of elements in the container
• empty(); // Determine whether the container is empty
• swap(); // Swap two collection containers

map insert and delete

• insert(elem); // Insert element in container
• clear();
• erase(pos); // Delete the element at the POS position and return to the next iterator
• erase(beg, end);
• erase(key); // Delete the element with key in the container

map lookup and statistics

• find(key);
• count(key); // Count the number of key elements. There are no duplicate keys in the map. The count of the multimap may be greater than 1

map container sorting

The default collation for map s is ascending
Like set, you can change the sorting rule to descending order by using imitation function

case

class CmpMap {
public:
    bool operator()(int a, int b)
    {
        return a > b;
    }
};

void PrtMap(map<int, int, CmpMap>& m)
{
    for (map<int, int, CmpMap>::iterator it = m.begin(); it != m.end(); ++it) {
        cout << "key: " << it->first << " Second: " << it->second << endl;
    }
    cout << endl;
}

void test06()
{
    map<int, int, CmpMap> m;
    m.insert(pair<int, int>(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(make_pair(3, 30));
    m.insert(make_pair(4, 40));
    m.insert(make_pair(5, 50));
    PrtMap(m);
}