http://www.cplusplus.com/reference/set/set/insert/

顺序容器包括vector、deque、list、forward_list、array、string，所有顺序容器都提供了快速顺序访问元素的能力。

关联容器包括set、map

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器不支持顺序容器的位置相关的操作。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值得操作。

关联容器支持高效的关键字查找和访问。两个主要的关联容器(associative container)类型是map和set。map中的元素是一些关键字----值(key--value)对：关键字起到索引的作用，值则表示与索引相关联的数据。set中每个元素只包含一个关键字：set支持高效的关键字查询操作----检查一个给定关键字是否在set中。

标准库提供set关联容器分为：

1，按关键字有序保存元素：set(关键字即值，即只保存关键字的容器)；multiset(关键字可重复出现的set)；

2，无序集合：unordered_set(用哈希函数组织的set)；unordered_multiset(哈希组织的set，关键字可以重复出现)。

set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。

在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。

set具备的两个特点：

set中的元素都是排序好的
	
set中的元素都是唯一的，没有重复的
set用法：

begin();            // 返回指向第一个元素的迭代器
end();              // 返回指向迭代器的最末尾处（即最后一个元素的下一个位置）
clear();            // 清除所有元素
count();            // 返回某个值元素的个数

empty();            // 如果集合为空，返回true

equal_range();      //返回集合中与给定值相等的上下限的两个迭代器

erase()–删除集合中的元素

find()–返回一个指向被查找到元素的迭代器

get_allocator()–返回集合的分配器

insert()–在集合中插入元素

lower_bound()–返回指向大于（或等于）某值的第一个元素的迭代器

key_comp()–返回一个用于元素间值比较的函数

max_size()–返回集合能容纳的元素的最大限值

rbegin()–返回指向集合中最后一个元素的反向迭代器

rend()–返回指向集合中第一个元素的反向迭代器

size()–集合中元素的数目

swap()–交换两个集合变量

upper_bound()–返回大于某个值元素的迭代器

value_comp()–返回一个用于比较元素间的值的函数

begin() and end()

// set::begin/end
#include <iostream>
#include <set>

int main ()
{
  int myints[] = {75,23,65,42,13};
  std::set<int> myset (myints, myints+5);

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

Output:
myset contains: 13 23 42 65 75

 

 

 

 

 

 

 

“无意中发现了一个巨牛的人工智能教程，忍不住分享一下给大家。教程不仅是零基础，通俗易懂，而且非常风趣幽默，像看小说一样！觉得太牛了，所以分享给大家。点  这里  可以跳转到教程。”。
/**
 * Created by yuhui on 2017/7/11 0011.
 */
import java.util.HashSet;
import java.util.Set;

public class TestSet {

    public static void main(String[] args) {

        Set<String> result = new HashSet<String>();
        Set<String> set1 = new HashSet<String>() {
            {
                add("王者荣耀");
                add("英雄联盟");
                add("穿越火线");
                add("地下城与勇士");
            }   
        };

        Set<String> set2 = new HashSet<String>() {
            {
                add("王者荣耀");
                add("地下城与勇士");
                add("魔兽世界");
            }
        };

        result.clear();
        result.addAll(set1);
        result.retainAll(set2);
        System.out.println("交集：" + result);

        result.clear();
        result.addAll(set1);
        result.removeAll(set2);
        System.out.println("差集：" + result);

        result.clear();
        result.addAll(set1);
        result.addAll(set2);
        System.out.println("并集：" + result);

    }

}


结果如下：

交集：[王者荣耀, 地下城与勇士]

差集：[英雄联盟, 穿越火线]

并集：[王者荣耀, 英雄联盟, 魔兽世界, 地下城与勇士, 穿越火线]

北京小辉微信公众号

大数据资料分享请关注

     我们可以知道Set集合是没有重复数据的特性，那么对于元素为对象 的情况是否也同样奏效？可以看一下。举一个例子：

SetTest.java：

class VO {
    private String name;
    private String addr;

    public VO(String name, String addr) {
        this.name = name;
        this.addr = addr;
    }

    @Override
    public String toString() {
        return "name: " + name + " addr:" + addr;
    }
}

 @Test
 public void testSet() {

     Set<VO> vos = new HashSet<>();

     VO vo = new VO("wahaha", "sh");

     VO vo1 = new VO("wahaha", "bj");

     VO vo2 = new VO("wahaha", "sh");

     vos.add(vo);
     vos.add(vo1);
     vos.add(vo2);

     for (VO item : vos) {
         System.out.println(item.toString());
     }
 }

结果为：

name: wahaha addr:sh
name: wahaha addr:bj
name: wahaha addr:sh

可见，对于各个字段值都相同的对象，并没有做去重操作。为什么呢，看一下JDK1.8中HashSet的数据结构：

HashSet.java:

实例化对象：

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
 public HashSet() {
    map = new HashMap<>();
 }

可见new HashSet()操作实际上是new HashMap<>()，可见底层是以HashMap来实现的。

HashSet.add方法：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashMap.add方法：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

可以从上面的加粗字段看出，判断插入的key是否存在，要判断两点①hash值是否相同；②对应的值是否相同，前者要看hashCode()方法，后者要看equal()方法。下面我们来探索一下基本的数据类型和自定义类类型在计算hashCode和equal的区别，看一下如下代码：

class VO {
    private String name;
    private String addr;

    public VO(String name, String addr) {
        this.name = name;
        this.addr = addr;
    }

    @Override
    public String toString() {
        return "name: " + name + " addr:" + addr;
    }
}

@Test
public void testSet() {
    
   Set<VO> vos = new HashSet<>();

   VO vo = new VO("wahaha", "sh");
   VO vo1 = new VO("wahaha", "bj");
   VO vo2 = new VO("wahaha", "sh");

   Integer a = 2;
   Integer b = 2;

   String str1 = new String("abc");
   String str2 = new String("abc");

   System.out.println(a.equals(b));
   System.out.println(str1.equals(str2));
   System.out.println(vo.equals(vo2));
   
   System.out.println(a.hashCode() == b.hashCode());
   System.out.println(str1.hashCode() == str2.hashCode());
   System.out.println(vo.hashCode() == vo2.hashCode());

   vos.add(vo);
   vos.add(vo1);
   vos.add(vo2);

   for (VO item : vos) {
       System.out.println(item.toString());
   }
}

结果为：

true
true
false
true
true
false
name: wahaha addr:sh
name: wahaha addr:sh
name: wahaha addr:bj

java.lang.Integer.equals()：两个对象对应的值一致则返回true。

public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

java.lang.String.equals()：两个字符串对应的值一致则返回true：

public boolean equals(Object anObject) {
    if (this == anObject) {//同一个对象，必定是一致的
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {//对比每一个字符
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;//anObject不是String实例，那么返回false
}

java.lang.Object.equals()：两个对象的引用是否一致，即两个的对象是否是同一个。

 

public boolean equals(Object obj) {
    return (this == obj);
}

可见对于java.lang.Object.equals()来讲，两个new出来的对象肯定是不一致的，那么在HashMap数据结构中不会被判定成相同的对象（尽管值相同）。下面再看看hashCode的源码：

java.lang.Integer.hashCode():

@Override
public int hashCode() {
    return Integer.hashCode(value);
}

public static int hashCode(int value) {
    return value;
}

java.lang.String.hashCode():

 

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

java.lang.Object.hashCode():

public native int hashCode();

JDK8的默认hashCode的计算方法是通过和当前线程有关的一个随机数+三个确定值，运用Marsaglia's xorshift schema随机数算法得到的一个随机数。

因此，以上可以看到Integer和String也都是根据具体的value值来计算hashCode，那么尽管两个引用不同但是值相同的对象，依然是想等的，但是Object则不同了。

知道了原因，解决方法就简单了，那就是重载VO类的equals和hashCode方法，代码如下：

SetTest.java：

class VO {
    private String name;
    private String addr;

    public VO(String name, String addr) {
        this.name = name;
        this.addr = addr;
    }

    @Override
    public String toString() {
        return "name: " + name + " addr:" + addr;
    }

    /**
     * 如果对象类型是User,先比较hashcode，一致的场合再比较每个属性的值
     */
    @Override
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (this == obj)
            return true;
        if (obj instanceof VO) {
            VO vo = (VO) obj;

            // 比较每个属性的值一致时才返回true
            if (vo.name.equals(this.name) && vo.addr.equals(this.addr))
                return true;
        }
        return false;
    }

    /**
     * 重写hashcode方法，返回的hashCode一样才再去比较每个属性的值
     */
    @Override
    public int hashCode() {
        return name.hashCode() * addr.hashCode();
    }
} // class

@Test
public void testSet() {
    
   Set<VO> vos = new HashSet<>();

   VO vo = new VO("wahaha", "sh");
   VO vo1 = new VO("wahaha", "bj");
   VO vo2 = new VO("wahaha", "sh");

   vos.add(vo);
   vos.add(vo1);
   vos.add(vo2);

   for (VO item : vos) {
       System.out.println(item.toString());
   }

}

 

结果：

 

name: wahaha addr:sh
name: wahaha addr:bj

在阿里巴巴Java开发是手册的集合处理中需要强制遵循如下规则：

1)只要重写equals，就必须重写hashCode；

2)因为Set存储的是不重复的对象，依据hashCode和equals进行判断，所以Set存储的对象必须重写这两个方法。

3)如果自定义对象做为Map的键，那么必须重写hashCode和equals。

正例：String重写了hashCode和equals方法，所以我们可以非常愉快的使用String对象作为key来使用。

以上。

 

Author：忆之独秀

Email：leaguenew@qq.com

注明出处：https://blog.csdn.net/lavorange/article/details/80420087


 

 

类似于数组，但是成员的值都是唯一的，没有重复
const s = new Set();
[2,3,1,2,5,6,7].forEach(x => s.add(x));
console.log(s);
for(let sv of s){
	console.info(sv);
}
console.log([...s],s.size);

去除数组中的重复元素
因为向Setj加入值不会发生类型转换
所以5和'5'是l两个不同的值
Set内部判断是否相等是采用"Same-value equality"
类似于精确相等运算符"==="
主要的区别是NaN等于自身，而精确相等运算符认为NaN不等于自身

const arr1 = [1,"1",2,3,4,3,4,5,6,7,6,7,8,9];
console.log("数组去重方法1：",...new Set(arr1));

Set四个方法
add(value)
delete(value)
has(value)
clear()

Array.from()方法可以将Set结构转为数组
//数组去重
console.log("数组去重",Array.from(new Set(arr1)));

遍历操作
/*
	遍历操作
	键名和键值是同一个值
	keys(),values(),entries(),forEach()
 */
for(let x of s.entries()){
	console.log(x);
}

forEach
let set1 = new Set([1,2,3]);
set1.forEach((value,key) => console.log(value * 2));

遍历的应用
let set2 = new Set([1,1,2,3]);
console.log(...set2)

let set3 = new Set([...set2].map(x => x**2));
console.log("map",set3);

let set4 = new Set([...set2].filter( x => x > 2));
console.log("filter",set4);