C++/Java set 容器简介

2022-12-18 13:14:47

C++/Java set 容器简介

原创作者信息

@ 邮箱: chronoschen1999@gmail.com

set 概述

set 作为比较经典的容器，有两个值得注意的特性，首先是不重复性，其次是无序性。不重复性即装入一个元素后，如果后面再次试图添加相同的元素，那么后面那个元素不会被添加成功；无序性可以理解为，加入元素后，内存中对各个对象存储顺序不是与添加顺序一致，而是会按照特定的要求来组织存放。

Java 中的常见 set

Java 中的 Set 种类比较多，但在操作上有统一的接口。每种 Set 有自己的元素排布规则，所以可以达到不同的效果，编程人员可以按照自己的实际需求选取。为了实现不重复性，最朴素的想法是，每次加入一个新元素，就把新元素和set中已存的所有元素比较，如果有相同的（Java 中的“相同”主要是由Object里面就继承下来的 equals 方法来定义），但如果已有元素的数量巨大，每添加一个元素，就需要跟所有的元素比对，时间复杂度是O(n)，无疑是巨大的耗费。因此不同类型set采用了不同的方式来减少这种消耗。下面主要介绍 HashSet 和 TreeSet。

HashSet

这个容器比较常用，也很实用。HashSet 的底层实现可以视作一个数组，每次添加元素时，会计算这个元素的哈希值，然后将哈希值映射成数组的某个索引，然后将元素存到算出来的这个索引的数组位置。

如果没有冲突，也就是通过哈希值算出来的索引位置没有元素，那么元素直接存进去，时间复杂度为O(1)；如果有冲突，即试图存进去的位置不为空，就需要先判断新元素(假设为a1)和当前位置的元素(假设为a2)是否相等(即a1.equals(a2))，因为哈希值相等的元素不一定相同。如果相同，则新元素舍弃掉，不加进去；如果不相等，说明新元素和老元素本质上还是不同的元素，那就在这个索引位置上拉一个链表，后面新的元素如果计算的索引也是这个位置，就需要跟链表上的所有元素比较一下，再决定是否加进来。

因此，HashSet 的时间复杂度可以做到 O(1)，如果哈希冲突很多时、单个位置链表过长时，会导致效率降低。JDK8之后，为了防止单个位置上链表过长，在满足一些条件时，会将链表重新组织为红黑树。

验证添加时是否调用了 equals 方法：

public class SetTest {
    public static void main(String[] args) {
				HashSet<Student> hashSet = new HashSet<>();
        System.out.println("第一次添加.........");
        hashSet.add(new Student(1,2));
        System.out.println("第二次添加相同元素.........");
        hashSet.add(new Student(1,2));
        System.out.println("第三次添加不相同元素.........");
        hashSet.add(new Student(11,99));
        System.out.println("第四次添加哈希值相同、但逻辑上不相同的元素.........");
        hashSet.add(new Student(2,1));
        System.out.println("集合大小为：" + hashSet.size());
    }
}

class Student {
    int age;
    int sno;

    Student(int age, int sno){
        this.age = age;
        this.sno = sno;
    }
    @Override
    public int hashCode() {
        int myHashCode = age + sno;
        return myHashCode;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("进入了Equals方法");
        return this.sno == ((Student) obj).sno;
    }
}

输出结果如下：

第一次添加.........
第二次添加相同元素.........
进入了Equals方法
第三次添加不相同元素.........
第四次添加哈希值相同、但逻辑上不相同的元素.........
进入了Equals方法
集合大小为：3

TreeSet

底层用的是红黑树来组织存储。红黑树的节点之间不存在相等不相等的说法，更重要的是定义大小，Java 中有两种方式可以自定义比较逻辑：

继承 Comparable 接口，实现 compareTo方法：

class Student implements Comparable<Student> {
    int age;
    int sno;

    Student(int age, int sno){
        this.age = age;
        this.sno = sno;
    }

    @Override
    public int compareTo(Student o) {
        return this.sno - o.sno;
    }
}

在外部继承实现 Comparator 接口，实现 compare 方法，并在构造 TreeSet 时将这个实现类的对象作为参数传入（使用匿名内部类简化操作）:

TreeSet<Student> treeSet = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.sno - o2.sno;
            }
        });

两种方法各有好处，Comparable 的方式比较直观，就像给这个类赋予了某种自然的属性；Comparator 较为灵活，面对不同的业务需求时，可以在不改变类的前提下实现不同的比较方案。

使用以上两种方式之后，TreeSet 会把加入的元素按照规则组织成红黑树，所以 TreeSet 有一个功能：遍历时可以按照自定义的大小顺序或逆序输出元素，示例如下：

//第一个参数年龄无关紧要，第二个参数是学号。自定义逻辑是按照学号比对大小
        treeSet.add(new Student(0,8));
        treeSet.add(new Student(0,1));
        treeSet.add(new Student(0,5));
        treeSet.add(new Student(0,3));
        treeSet.add(new Student(0,6));

        for (Student s: treeSet) {
            System.out.println(s.sno);
        }

输入对象的学号不是有序的，但装入 TreeSet 再输出时，输出结果：

但这并没有否认 set 在逻辑上的无序性，因为存储的顺序本来就不是使用者所指的，无序可以理解为 set 底层存储元素会用独特的方法，HashSet 是如此，TreeSet 也是如此。

实际上，Java 在实现 HashSet 或者 TreeSet 时，底层是新建了一个 HashMap 或者 TreeMap，因为 Map 的 Key 要求具有唯一性，这与 Set 的不可重复性要求不谋而合，所以底层是把 Set 装入的元素作为 Map 的 Key，但归根结底原理都是差不多的。

C++ STL 中的 set

C++ 的 set 思想和 Java 的 TreeSet 是一致的，自定义使用 set 的核心在于定义大小，而 C++ 的自定义比较往往是根据重载运算符实现的，因此 set 要求元素类不是内置类型时，也要重载对应的运算符，主要有三种方式：

重载 < 运算符

	bool operator < (const Student& otherStu) const {
		return sno < otherStu.sno;
	}

需要注意的是，set 底层对 < 的非对称性判断比较严格，也就是 a < b 为 true 时，b < a 必然为false，所以上面的比较不能写成 <=，不然就不满足非对称性的要求。这种直来直去的判断比较简单，但如果比较的逻辑比较复杂，涉及多个属性的组合判断，就容易出错，源码的 STL_VERIFY 函数会报错。

重载 () 运算符

bool operator()(const Student &s1,const Student &s2){
	return s1.sno < s2.sno;
}

函数指针

bool cmp(const Student &s1,const Student &s2){
    return s1.sno<s2.sno;
}
....
//初始化 set 时:
set<Students,decltype(cmp)*> s(cmp);

这种方法与 Java 中的 Comparator 比较类似。

以重载<运算符为例，查看 set 可按照定义的大小顺序，有序输出元素：

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

class Student {
public:
	int sno;
	int age;
	Student(const int &sno, const int &age) : age(age), sno(sno) {}
	bool operator < (const Student &otherStu) const {
		return sno < otherStu.sno;
	}
};

class Printer {
public:
	void operator() (const Student &stu) { cout << stu.sno << '\t' << endl; }
};

int main() {
	set<Student> s;
	s.insert(Student(9, 0));
	s.insert(Student(2, 0));
	s.insert(Student(5, 0));
	for_each(s.begin(), s.end(), Printer());
	return 0;
}

遍历运行结果：

2
5
9

码农公寓

C++/Java set 容器简介

原创作者信息

set 概述

Java 中的常见 set

HashSet

TreeSet

C++ STL 中的 set

重载 < 运算符

重载 () 运算符

函数指针

相关文章