STL 笔记（十二）：关联性容器——集合

#include 
#include 
#include 
#include 

using namespace std;

// 关联性容器 - 集合（有序） - set（数据唯一）、multiset（数据可以重复）
// 数据结构：红黑树 - 二叉排序树 - 中序遍历
// 迭代器：双向迭代器（只能自增、自减）

template 
void Display(T s)
{
    for (typename T::iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;
}

// 构造与初始化
void test1()
{
    set s1; // less，升序
    set > s2; // greater，降序

    int a[] = {5, 7, 2, 3, 5, 6, 2};
    set s3(a, a + 7);
    Display(s3); // 2 3 5 6 7

    multiset s4(a, a + 7);
    Display(s4); // 2 2 3 5 5 6 7
}

// 存取数据
void test2()
{
    int a[] = {5, 7, 2, 3, 5, 6, 2};
    set s(a, a + 7);
    Display(s);

    // 取数据
    cout << *s.begin() << endl; // 2
    set::iterator it = s.begin();
    advance(it, 2);
    cout << *it << endl; // 5

    // 存数据 - 集合在确定之后是不能修改的 - key - read-only
}

// 插入删除
void test3()
{
    // 插入 - insert - 返回类型：pair - iterator（值的迭代器），bool（成功插入与否）
    int a[] = {8, 1, 2, 6};
    set s(a, a + 4);
    Display(s); // 1 2 6 8

    s.insert(5);
    s.insert(0);
    Display(s); // 0 1 2 5 6 8

    pair::iterator, bool> p = s.insert(6);
    cout << *(p.first) << " " << p.second << endl; // 6 0

    int b[] = {9, 4};
    s.insert(b, b + 2);
    Display(s); // 0 1 2 4 5 6 8 9

    // 删除
    s.erase(5);
    Display(s); // 0 1 2 4 6 8 9

    set::iterator it = s.begin();
    advance(it, 4);
    s.erase(it);
    Display(s); // 0 1 2 4 8 9

    s.erase(s.begin(), s.end());
}

// 其它操作
void test4()
{
    // count
    int a[] = {6, 3, 4, 3, 5, 2, 3};
    multiset s(a, a + 7); // 2 3 3 3 4 5 6
    Display(s);

    cout << s.count(3) << endl;

    // find - 返回类型：迭代器，如果有多个则返回第一个
    multiset::iterator it;
    it = s.find(9); // 如果待查找值不存在，则返回end迭代器 - 可用于判定集合中是否查找成功
    cout << *it << endl; // 随机

    // lower_bound - 返回第一个大于等于3的迭代器 - 确定下界【闭】
    it = s.lower_bound(3);
    cout << *it << endl; // 3

    // upper_bound - 返回第一个大于3的迭代器 - 确定上界【开】
    it = s.upper_bound(3);
    cout << *it << endl; // 4

    // equal_range - lower_bound，upper_bound
    pair::iterator, multiset::iterator> p;
    p = s.equal_range(3);
    cout << *(p.first) << ' ' << *(p.second) << endl; // 3 4

    // distance - 迭代器函数：迭代器相减以求容器元素个数
    cout << distance(p.first, p.second) << endl; // 3
}

int main()
{
    // 初始化
    pair p1;
    pair p2;
    pair p3(6, "Reyn");
    pair p4(p3);
    // 赋值
    p2 = make_pair(8, "Morales");
    // 输出
    cout << p2.first << ' ' << p2.second << endl;
    // 比较运算符（==, !=, <, >, >=, <=）
    cout << (p2 == p3) << endl;
    cout << (p2 > p3) << endl;

    test1(); // 构造与初始化
    test2(); // 存取数据
    test3(); // 插入删除
    test4(); // 其它操作

    return 0;
}

#include 
#include 

using namespace std;

// set：交集，并集，补集

class Student
{
private:
    string stuNo;
    string stuName;
public:
    Student(string o, string n)
    {
        stuNo = o;
        stuName = n;
    }
    void showStudent() const
    {
        cout << stuNo << 't' << stuName << endl;
    }
    bool operator<(Student s) const
    {
        return stuNo < s.stuNo;
    }
};

class MySet
{
private:
    set s;
public:
    MySet(Student * first, Student * last):s(first, last) {}
    void Combine(MySet ms)
    {
        // 遍历另外一个集合，将容器中的元素放置调用对象中，【自动去重】
        set result = s;
        for (set::iterator it = ms.s.begin(); it != ms.s.end(); it++) {
            result.insert(*it);
        }
        cout << "NO" << 't' << "NAME" << endl;
        for (set::iterator it = result.begin(); it != result.end(); it++) {
            it->showStudent(); // 被存放于集合中的元素均为const类型，即为主码，不可修改
        }
        cout << endl;
    }
    void Interset(MySet ms)
    {
        // 遍历一个集合，查看元素是否在另一个集合中，如果存在（两个集合都有该元素），则放入结果集合中
        set result;
        for (set::iterator it = s.begin(); it != s.end(); it++) {
            if (ms.s.find(*it) != ms.s.end()) { // 元素存在
                result.insert(*it);
            }
        }
        cout << "NO" << 't' << "NAME" << endl;
        for (set::iterator it = result.begin(); it != result.end(); it++) {
            it->showStudent(); // 被存放于集合中的元素均为const类型，即为主码，不可修改
        }
        cout << endl;
    }
    void Differ(MySet ms)
    {
        // 遍历一个集合，查看元素是否在另一个集合中，如果不存在（只有一个集合都有该元素），则放入结果集合中
        set result;
        for (set::iterator it = s.begin(); it != s.end(); it++) {
            if (ms.s.find(*it) == ms.s.end()) { // 元素不存在
                result.insert(*it);
            }
        }
        cout << "NO" << 't' << "NAME" << endl;
        for (set::iterator it = result.begin(); it != result.end(); it++) {
            it->showStudent(); // 被存放于集合中的元素均为const类型，即为主码，不可修改
        }
        cout << endl;
    }
    void showMySet()
    {
        cout << "NO" << 't' << "NAME" << endl;
        for (set::iterator it = s.begin(); it != s.end(); it++) {
            it->showStudent(); // 被存放于集合中的元素均为const类型，即为主码，不可修改
        }
        cout << endl;
    }
};

int main()
{
    Student r[] = {
        Student("1001", "Reyn"),
        Student("1003", "Jhon"),
        Student("1002", "Lisa")
    };

    Student s[] = {
        Student("1004", "Lily"),
        Student("1001", "Reyn"),
        Student("1002", "Lisa")
    };

    MySet set01(r, r + 3), set02(s, s + 3);

    // 并集
    set01.Combine(set02);

    // 交集
    set01.Interset(set02);

    // 差集
    set01.Differ(set02);
    set02.Differ(set01);

    return 0;
}

• set，multiset 是关联型容器的一种，其数据结构使用的是红黑树（一种二叉排序树，对其中序遍历后可以得到一个有序序列），set，multiset 中的元素均为键，即其值是不可以修改的，set 中不能出现重复的键，而 multiset 则可以出现重复的键
• set，multiset 中的迭代器是双向迭代器，即不能进行一般的运算，只能进行自加或自减的操作，如果想要让迭代器指向容器允许的任意位置，则需要使用 advance 函数
• 在案例中，对于容器内的基本数据类型（此例中为 Student）来说，某些函数需要被标识为 const，其原因是 set，multiset 中的元素均为键，是只读的，不可修改，所以其类型是 const，而常对象只能调用常函数，所以相应的对象函数需要被声明为常函数

在下一篇文章，我们将介绍 C++ 中的关联性容器——映射

此文章主要用来作为课程学习过程中的总结，大家如果有什么问题也可以在评论区留言，我会尽力帮大家解决问题，如果觉得对大家有帮助的话，希望多多点赞、转发，谢谢！