SET容器 - 自定义排序和去重

std::set,是基于红黑树的平衡二叉树的数据结构实现的一种容器,因为其中所包含的元素的值是唯一的,因此主要用于排序和去重。

1.使用内置的比较函数less

定义内置类型的set对象,限制:

  • 用于比较内置类型,如intchar
  • 只能对一个内置类型进行排序或去重

示例排序(c++11):

#include <iostream>
#include <set>

int main() {
    std::set<int> testSet;
    testSet.insert(20);
    testSet.insert(10);
    for (auto i : testSet) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}

Microsoft Visual C++ 6.0(c++98):

#include <iostream>
#include <set>
using namespace std;

int main() {
    std::set<int> testSet;
    testSet.insert(20);
    testSet.insert(10);
    //iteratorz,迭代器,用于遍历容器内元素和元素数据类型
    for (set<int>::iterator i = testSet.begin(); i != testSet.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;
    return 0;
}

输出:

10 20

2.定义比较函数对自定义结构体(类)排序

2.1重载操作符 <

不能重载<=>=,几乎所有的方法或容器都需要排序来满足数学意义上的标准严格弱序化,否则这些方法或容器的行为将不可预知。

严格弱序化需要满足:

关系 说明
f(x,x) = false 相同为假
if f(x,y) then !f(y,x) 如果 x < y(x > y) 为真,则 x > y (x < y) 为假
if f(x,y) and f(y,z) then f(x,z) 如果 x > y (x < y) 且 y > z (y < z),则x > z(x < z)
if !f(x,y)&&!f(y,x) then x==y; if x==y and y==z then x==z 如果 x < y 为假且 x > y 为假,则 x = y

set容器在判定已有元素a和新插入元素b是否相等时:

  • 1.将a作为左操作数,b为右操作数,调用比较函数,得到返回值
  • 2.将b作为左操作数,a为右操作数,再调用一次比较函数,得到返回值
  • 3.如果前两步返回值都为false,则a=b,b不会被插入set容器;如果前两步返回值都为true,则可能得到不可预知的结果。

由上述,必须满足:比较函数对相同元素返回false

示例,对结构体Stu按照id排序,如果id相同,对name按照字典序排序,同时去重(c++11):

#include <cstring>
#include <iostream>
#include <set>

struct Stu {
    int id;
    const char *name;
    Stu(int d, const char *n) : id(d), name(n) {}
    Stu() {}
    //重载运算符'<'
    bool operator<(const Stu &right) const {
        if (id != right.id)
            return id < right.id;
        else {
            //id相同,根据name按照字典序排序,同时去重
            if (strcmp(this->name, right.name) == 0)
                return false;
            else
                return strcmp(this->name, right.name) < 0;
        }
    }
};

int main() {
    std::set<Stu> testSet;
    testSet.insert(Stu(2, "zhang"));
    testSet.insert(Stu(2, "li"));
    testSet.insert(Stu(2, "li")); //重复数据
    //对应insert,先调用存储对象构造函数,在内存中生成对象,然后拷贝至容器中,c++98不支持
    testSet.emplace(1, "wang");
    for (auto i : testSet) {
        std::cout << "id: " << i.id << " "
                  << "name: " << i.name << std::endl;
    }
    return 0;
}

Microsoft Visual C++ 6.0(c++98):

#include <string.h>
#include <iostream>
#include <set>
using namespace std;

struct Stu {
    int id;
    const char *name;
    Stu(int d, const char *n) : id(d), name(n) {}
    Stu() {}
    //重载运算符'<'
    bool operator<(const Stu &right) const {
        if (id != right.id)
            return id < right.id;
        else {
            //id相同,根据name按照字典序排序,同时去重
            if (strcmp(this->name, right.name) == 0)
                return false;
            else
                return strcmp(this->name, right.name) < 0;
        }
    }
};

int main() {
    set<Stu> testSet;
    testSet.insert(Stu(2, "zhang"));
    testSet.insert(Stu(2, "li"));
    testSet.insert(Stu(2, "li"));
    testSet.insert(Stu(1, "wang"));
    for (set<Stu>::iterator i = testSet.begin(); i != testSet.end(); i++) {
        cout << "id: " << i->id << " "
             << "name: " << i->name << endl;
    }
    return 0;
}

输出:

id: 1 name: wang
id: 2 name: li
id: 2 name: zhang

2.2重载操作符 ()

下一页