C++STL学习2

发表于 更新于 分类于

主要内容：set multiset pair

https://blog.csdn.net/q5120192609/article/details/127587508

set & multiset

基本概念

二叉树，所有元素都会在插入时自动被排序

  • 本质: set/multiset属于关联式容器，底层结构是用二叉树实现
  • set和multiset区别：
    • set不允许容器中有重复的元素
    • multiset允许容器中有重复的元素

构造与赋值&大小与交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <set>

void printSet(set<int &s>)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        std::cout << *it << "\t";
    }
    std::cout << std::endl;
}

int main()
{
    set<int> s1;  // 构造
    
    s1.insert(10);  // 只有 insert
    s1.insert(40);
    s1.insert(30);
    s1.insert(20);
    s1.insert(30);

    // 遍历容器。自动排序且没有插入重复值
    printSet(s1);  // 输出 10 20 30 40

    set<int> s2(s1);  // 拷贝构造
    set<int> s3 = s2;  // 赋值
    
    // empty() 判断大小
    if (s1.empty())
    {
        cout << "s1为空" << endl;
    }
    else
    {
        cout << "s1不为空" << endl;
        // size() 获取大小
        cout << "s1的大小为" << s1.size() << endl;
    }

    // swap()交换
    s1.swap(s2);

    return 0;
}

插入与删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void test01()
{
    set<int>s1;
    s1.insert(40);  //没有push，只有insert方式
    s1.insert(20); s1.insert(30); s1.insert(10);
    printSet(s1);  //10 20 30 40

    //删除
    s1.erase(s1.begin()); // 删除了10
    printSet(s1);  //20 30 40

    //删除某个具体的值
    s1.erase(30);  //20 40

    //清空
    s1.erase(s1.begin(), s1.end());
    printSet(s1);  // 空的

    //清空
    s1.clear();
    printSet(s1);  // 空的
}

查找与统计

  • 查找 find(key)：找到则返回该元素的别带起，不存在则返回set.end()
  • 统计 count(key)：set的返回要么是0要么是1，multiset不一定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void test01()
{
    set<int>s1;
    s1.insert(40); s1.insert(20); s1.insert(10);
    s1.insert(30); s1.insert(30); s1.insert(30); 

    //查找
    set<int>::iterator pos = s1.find(30);
    if (pos != s1.end())
    {
        cout << "找到元素：" << *pos << endl;
    }
    else
    {
        cout << "没有找到" << endl;
    }

    //统计
    int num = s1.count(30);  //1
    int num300 = s1.count(300);  //0
    cout << "num = " << num << endl;
    cout << "num 300 = " << num300 << endl;
}

set和multiset的区别

multiset不会核查二叉树中是否含有该元素，而set会核查二叉树中是否含有该元素。

set会返回一个pair<iterator, bool>，可以通过判断bool来判断是否插入成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
#include<set>
 
void test01()
{
    set<int> s1;
    pair<set<int>::iterator, bool> ret = s1.insert(10);  //pair 对组
    if (ret.second)
    {
        cout << "第一次插入成功" << endl;  //这里
    }
    else
    {
        cout << "第一次插入失败" << endl;
    }
    ret = s1.insert(10);
    if (ret.second)
    {
        cout << "第二次插入成功" << endl;
    }
    else
    {
        cout << "第二次插入失败" << endl;  //这里
    }
    multiset<int> ms;
    ms.insert(10);
    ms.insert(10);
    for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
    {
        cout << (*it) << " ";
    }
    cout << endl;
}

改变内置数据类型的排序规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 仿函数本质上是个类，并且必须写在前面
class myCompare
{
public:
    bool operator()(int v1,int v2) const  // 后面记得加const
    {
        return v1 > v2;
    }
};
void test01()
{
    set<int> s1;
    s1.insert(10); s1.insert(30); s1.insert(20); s1.insert(50); s1.insert(40);
    // set在插入数据以后就无法更改其排序了
    printSet(s1);

    // 利用仿函数指定排序规则为从大到小
    set<int, myCompare> s2;
    s2.insert(10); s2.insert(30); s2.insert(20); s2.insert(50); s2.insert(40);

    for (set<int, myCompare>::iterator it = s2.begin(); it != s2.end(); it++)
    {
        cout << (*it) << " ";
    }
    cout << endl;
}

改变自定义数据类型的排序规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <set>
using namespace std;

class Person
{
public:
    string name;
    int age;
    Person(string n, int a)
    {
        name = n;
        age = a;
    }
};

class comparePerson
{
public:
    bool operator()(const Person &p1, const Person &p2) const
    {
        return p1.age > p2.age;
    }
};

void test01()
{
    // set<Person> s;  // 自定义的数据类型如果不指定排序规则就会报错，无法构造set
    set<Person, comparePerson> s;
    Person p1("刘备", 24); s.insert(p1); Person p2("关羽", 32); s.insert(p2);
    Person p3("张飞", 35); s.insert(p3); Person p4("赵云", 37); s.insert(p4);
    
    for (set<Person,comparePerson>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "姓名：" << it->name << " 年龄：" << it->age << endl;
    }
    cout << endl;
}

pair

即成对出现的数据

构造：

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

访问：.first .second

1
2
3
4
5
pair<string, int> p("Tom",18);
cout << "姓名：" << p.first << " 年龄：" << p.second << endl;

pair<string, int> p2 = make_pair("Jerry", 20);
cout << "姓名：" << p2.first << " 年龄：" << p2.second << endl;

map & multimap

高效率、高性能的哈希表，对应Python中的字典。

  • map中所有元素都是pair
  • pair中第一个元素为key (键值)，起到索引作用，第二个元素为value (实值)
  • 所有元素都会根据元素的键值自动排序、

本质：map和multimap均属于关联式容器，底层结构是用二叉树实现

map和multimap区别：

  • map不允许容器中有重复key值元素
  • multimap允许容器中有重复key值元素
  • value均可以重复

构造与赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;
#include<map>
void printMap(map<int, int>& m)
{
    for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    {
        cout << "key = " << (*it).first << " value = " << it->second << endl;
    }
    cout << endl;
}
void test01()
{
    map<int, int> m;
    m.insert(pair<int, int>(1, 10));  // pair<int, int>(1, 10)是一个匿名对象
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));
    m.insert(pair<int, int>(4, 40));
    printMap(m);

    map<int, int> m2(m);  //拷贝构造

    map<int, int> m3;
    m3 = m;  // 赋值
    printMap(m3);
}

大小与交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
map<int, int>m;
m.insert(pair<int, int>(1, 10)); m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30)); m.insert(pair<int, int>(4, 40));

if (m.empty())
{
    cout << "m为空" << endl;
}
else
{
    cout << "m不为空" << endl;
    cout << "m的大小为：" << m.size() << endl;  // 4
}

//交换
map<int, int>m2;
m.insert(pair<int, int>(5, 100)); m.insert(pair<int, int>(6, 200));
m.insert(pair<int, int>(7, 300)); m.insert(pair<int, int>(8, 400));
cout << "交换前：" << endl;
printMap(m); printMap(m2);
cout << "交换后：" << endl;
m.swap(m2);
printMap(m); printMap(m2);

插入和删除