set容器

关于set，必须说明的是set关联式容器。

set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

set容器即集合容器,在stl中并不显眼,相比于常用的map,vector,之类的容器,并不常用,只是只有在使用集合,这一个常用的数学工具,set才会显得有意义.

set有一个兄弟容器multiset,set和multiset的区别是：set插入的元素在相同时在保留一个，但是multiset着允许容器中有相同的元素。

set容器描述了一个控制变长元素序列的对象的模板类。对这个序列可以进行查找、插入、删除序列中的任意一个元素，而完成这些操作的时间同这个序列中元素个 数的对数成比例关系(即log n).原因在于set容器与map类似,采用红黑树作为数据结构,因此采用insert操作时,迭代器不失效.

有意思的是,虽然set看起来是单个元素的集合体,但实际上与map类似在set中有键(key)又有值(value),但是迭代器返回的是value,而key是用于比较的

与map类似,set必须是严格弱排序( strict weak ordering),在判断的时候会用"<"，而不是"<="，一旦"<"成立便认为存在"<"关系，返回ture，而忽略了"="关系和">"区别，把它们归结为false"。其存在下述性质

1、非对称，若A<B为真，则B<A为假。
2、可传递，若A<B,B<C，则A<C。
3、A<A永远为假。

在set(map)中有两个参数key_compare,value_compare值得就是返回key与value的比较器,使用key_comp,和value可以返回比较结果.

将迭代器返回到开头

返回引用set容器中第一个元素的迭代器。

因为set容器始终保持其元素的排序，所以开始指向容器排序标准之后的元素。

如果容器为空，则不应取消引用返回的迭代器值。

关于set有下面几个问题：

（1）为何map和set的插入删除效率比用其他序列容器高？

大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：

 

　　A
　  / \
　 B C
　/ \ / \
  D E F G

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？

iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

（3）当数据元素增多时，set的插入和搜索速度变化如何？

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

 Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true 

代码分析：

#include <set>
using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return nums.size() > set<int>(nums.begin(), nums.end()).size();        
    }
};

/* First attempt Success
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());   
        if(nums.size()==1)
            return false;
        else
        {
            for (int i=0; i != nums.size(); i++)
            {
            if(nums[i]==nums[i+1])
               return true;
             }
            return false;
        }
    }
};*/

/*Second attempt Success
class Solution {
  public:
    bool containsDuplicate(vector<int>& nums) {
        return set<int>(nums.begin(), nums.end()).size() < nums.size();
    }
};*/

/*Third attempt Fail——nums中可能为负数
class Solution {
public:
	bool containsDuplicate(vector<int>& nums) {
		//int nums_size = nums.size();
		int arr[150000];
		int judg = 0;
		for (int i = 0; i != 150000; i++)
			arr[i] = 0;
		for (int i = 0; i != nums.size(); i++)
		{
			arr[nums[i]]++;
		}
        for (int i = 0; i != nums.size(); i++)
		    if (arr[i] > 1)
			{
				judg++;
				break;
			}
        
		if (judg > 0)
			return true;
		else return false;
	}
};
*/

//每次插入一个数，判断容器内是否有这个数
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
    //vector<int> mySet;
    set<int> mySet;
    // unordered_set<int> mySet;
    // multiset<int> mySet;
    // unordered_multiset<int> mySet;
    for (auto& num: nums) {
       // if (mySet.find(myset.begin(),myset.end(),num) != mySet.end())
        if (mySet.find(num) != mySet.end())
            return true;
        mySet.insert(num);
    }
    return false;
 }
};