#include<iostream>
#include<vector>
#include<set>
#include<time.h>
#include<unordered_set>
using namespace std;

void test_unordered_set()
{
	vector<int> v;
	v.reserve(10000);//100000、1000000
	srand((unsigned int)time(NULL));

	for (int i = 0; i < 10000; i++)//100000、1000000
	{
		v.push_back(rand());
	}

	//插入
	set<int> s;
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();

	unordered_set<int> us;
	size_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();

	cout << "set insert time：" << end1 - begin1 << endl;
	cout << "unorder_set insert time：" << end2 - begin2 << endl;

	//查找
	size_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);//set自带的查找效率是O(logn)
	}
	size_t end3 = clock();

	size_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e); //unordered_set自带的查找，优点：使用哈希特性查找，效率高--O(1)
	}
	size_t end4 = clock();

	cout << "set find time：" << end3 - begin3 << endl;
	cout << "unorder_set find time：" << end4 - begin4 << endl;

	//删除
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();

	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();

	cout << "set erase time：" << end5 - begin5 << endl;
	cout << "unorder_set erase time：" << end6 - begin6 << endl;
}

int main()
{

	test_unordered_set();

	return 0;
}

10000个数据的时间：

100000个数据的时间：

?1000000个数据的时间：

?可以看到，当数据量越大时，unordered_set相比于set所消耗的时间越少，这是因为unordered_set的底层是哈希表，增删查的效率更高。

二、?unordered_set

1.特点?

（1） unordered_map是存储<value, value>键值对的关联式容器，对value进行快速索引。
（2）在unordered_set中，元素的值同时是其键，是唯一标识，键和映射值的类型相同，键不可修改。unordered_set中的元素在容器不可修改，但是可以插入和删除元素。
（3）unordered_set中的元素不按任何特定顺序排序，而是根据其哈希值组织到存储桶中，允许直接根据value快速访问各个元素（平均时间复杂度是一定的）。
（4）unordered_set比set通过键访问单个元素的速度更快，但它通常在遍历元素子集的范围迭代方面效率较低。
（5）容器中的迭代器至少有正向迭代器。

2.构造

?有以下几种构造方式：

explicit unordered_set ( size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );//构造空的unordered_set对象

template <class InputIterator>
         unordered_set ( InputIterator first, InputIterator last,
                         size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );//用迭代器范围构造unordered_set对象

unordered_set ( const unordered_set& ust );//拷贝构造一个unordered_set对象

（1）构造一个空的?unordered_set对象

    unordered_set<int> us1;

向里面插入元素：

	us1.insert(2);
	us1.insert(72);
	us1.insert(6);
	us1.insert(35);
	us1.insert(291);
	us1.insert(327);

（2）用迭代器范围构造unordered_set对象

用us1的迭代器范围构造us2：?

    unordered_set<int> us2(us1.begin(), us1.end());

（3）拷贝构造一个unordered_set对象

?用us2拷贝构造us3：

    unordered_set<int> us3(us2);

3.容量

（1）empty( )

判断unordered_set是否为空：

cout << us3.max_size() << endl;

判断us3是否为空：?

    cout << us3.empty() << endl;//判断us3是否为空

?不为空：

（2）size( )?

返回unordered_set中的元素个数

size_type size() const noexcept;

?求us3中的元素个数：

    cout << us3.size() << endl;

（3）max_size( )?

返回unordered_set可存储的最大元素个数：

size_type max_size() const noexcept;

求us3最大元素个数：

    cout << us3.max_size() << endl;

4.迭代器

（1）begin( )

返回迭代器开始：?

iterator begin() noexcept;

?返回us3迭代器开始：

    unordered_set<int>::iterator it = us3.begin();

（2）end( )

返回迭代器结尾：

iterator end() noexcept;

返回us3迭代器结尾：?

    us3.end();

5.查找

（1）find( )

如果找到元素就返回元素所在位置，否则返回元素结尾：

iterator find ( const key_type& k );

在us3中查找327：?

	unordered_set<int>::iterator ret = us3.find(327);
	if (ret != us3.end())
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "没找到" << endl;
	}

（2）count( )?

?统计容器中值为k的元素的个数：

size_type count ( const key_type& k ) const;

?统计us3中值为291的元素的个数：

    cout << us3.count(291) << endl;

6.元素修改

（1）insert( )

pair<iterator,bool> insert ( const value_type& val );//插入元素，成功返回的pair的第二个元素为true，失败则为false
iterator insert ( const_iterator hint, const value_type& val );//返回插入元素的位置
template <class InputIterator>
    void insert ( InputIterator first, InputIterator last );//插入一段区间
void insert ( initializer_list<value_type> il );//将列表作为元素插入容器中

①插入元素?

	cout << us2.insert(568).second << endl;//不存在，插入成功
	cout << us2.insert(291).second << endl;//已存在，插入失败

?②返回插入元素的位置

    cout << *us2.insert(us3.begin(), 65) << endl;

③?插入一段区间

    unordered_set<int> us2;
	us2.insert(us1.begin(), us1.end());
	unordered_set<int>::iterator it = us2.begin();
	while (it != us2.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

④将列表作为元素插入容器中

	unordered_set<string> us4;
	us4.insert({ "int", "string", "float" });
	unordered_set<string>::iterator it = us4.begin();
	while (it != us4.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

（2）erase( )

?删除元素：

iterator erase ( const_iterator position );//删除position位置的元素，并返回删除元素的位置
size_type erase ( const key_type& k );//返回删除值为k的元素的个数
iterator erase ( const_iterator first, const_iterator last );//删除从first到last区间的元素，并返回删除的last元素的位置

?①删除position位置的元素，并返回删除元素的位置

	unordered_set<int> us2;
	us2.insert(us1.begin(), us1.end());
	cout << *us2.erase(us2.find(6)) << endl;

②?删除值为k的元素的，k存在返回1，k不存在返回0

    cout << us2.erase(72) << endl;

③?删除从first到last区间的元素，并返回删除的last元素的位置

    cout << *us2.erase(us2.find(6), us2.find(291)) << endl;

（3）clear( )

?删除容器中所有元素

void clear() noexcept;

?清空us2中所有元素：

    us2.clear();

（4）swap( )

?交换两个同类型容器中的元素

unordered_set<int> us1;
	us1.insert(2);
	us1.insert(72);
	us1.insert(6);
	us1.insert(35);
	us1.insert(291);
	us1.insert(327);

	unordered_set<int> us5;
	us5.insert(56);
	us5.insert(57);
	us5.insert(58);
	us5.insert(59);
	us5.insert(60);
	us5.insert(61);

	us1.swap(us5);
	
	unordered_set<int>::iterator it1 = us1.begin();
	while (it1 != us1.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;

	unordered_set<int>::iterator it5 = us5.begin();
	while (it5 != us5.end())
	{
		cout << *it5 << " ";
		it5++;
	}
	cout << endl;

哈系桶和哈希策略的函数等介绍完哈希表之后才能理解。

三、?unordered_map

1.特点?

（1）unordered_map是存储<key, value>键值对的关联式容器，允许通过key快速的索引到与其对应的value。
（2）在unordered_map中，键值通常用于惟一地标识元素，而映射value是一个对象，其内容与key关联。键和映射值的类型可能不同。
（3）unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
（4）unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
（5）unordered_map实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
（6）容器中的迭代器至少有正向迭代器。

2.构造??

explicit unordered_map ( size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );//构造空的unordered_map对象

template <class InputIterator>
  unordered_map ( InputIterator first, InputIterator last,
                  size_type n = /* see below */,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& alloc = allocator_type() );//用迭代器范围构造unordered_map对象

unordered_map ( const unordered_map& ump );//拷贝构造一个unordered_map对象

（1）构造一个空的unordered_map对象

    unordered_map<string, int> um1;

向里面插入元素：

    um1.insert(make_pair<string, int>("自行车", 8));
	um1.insert(make_pair<string, int>("消防车", 1));
	um1.insert(make_pair<string, int>("洒水车", 6));
	um1.insert(make_pair<string, int>("搅拌车", 7));
	um1.insert(make_pair<string, int>("小汽车", 5));

（2）用迭代器范围构造unordered_set对象

用um1的迭代器范围构造um2:

    unordered_map<string, int> um2(um1.begin(), um1.end());

（3）拷贝构造一个unordered_set对象

用um2拷贝构造um3：

    unordered_map<string, int> um3(um2);

3.容量

（1）empty( )

判断unordered_map是否为空：?

bool empty() const noexcept;

?判断um1是否为空：?

    cout << um1.empty() << endl;

（2）size( )

?返回unordered_map中的元素个数：

size_type size() const noexcept;

求um1中元素的个数：

    cout << um1.size() << endl;

（3）max_size( )

返回?unordered_map可存储的最大元素个数：

size_type max_size() const noexcept;

求um1最大元素个数：?

    cout << um1.max_size() << endl;

4.迭代器

（1）begin( )

返回迭代器开始：?

iterator begin() noexcept;

?返回um1迭代器开始：

    unordered_map<string, int>::iterator it = um1.begin();

（2）end( )?

返回迭代器结尾：

iterator end() noexcept;

?返回um1迭代器结尾：

    um1.end();

5.元素操作符[ ]

访问key为k的元素，如果存在就返回value的引用：?

mapped_type& operator[] ( const key_type& k );

?访问key为小汽车的元素，并返回小汽车对应的value的引用：

    cout << um1["小汽车"] << endl;

6.查找

（1）find( )?

根据k返回k所在位置的迭代器，如果没找到就返回end

iterator find ( const key_type& k );

?查找洒水车：

    cout << um1.find("洒水车")->second << endl;

（2）count( )

?统计容器中key为k的元素的个数：

size_type count ( const key_type& k ) const;

?统计um1中key为"搅拌车"的元素个数：

    cout << um1.count("搅拌车") << endl;

7.元素修改

（1）insert( )

pair<iterator,bool> insert ( const value_type& val );//插入元素，成功返回的pair的第二个元素为true，失败则为false
iterator insert ( const_iterator hint, const value_type& val );//返回插入元素的位置
template <class InputIterator>
    void insert ( InputIterator first, InputIterator last );//插入一段区间
void insert ( initializer_list<value_type> il );//将列表作为元素插入容器中

?①插入元素

	cout << um1.insert(make_pair<string, int>("大货车", 9)).second << endl;//不存在，插入成功
	cout << um1.insert(make_pair<string, int>("搅拌车", 1)).second << endl;//已存在，插入失败

??②返回插入元素的位置

    cout << um1.insert(um1.begin(), make_pair<string, int>("扫地车", 10))->second << endl;

③?插入一段区间?

    unordered_map<string, int> um2(um1.begin(), um1.end());
	unordered_map<string, int>::iterator it2 = um2.begin();

	while (it2 != um2.end())
	{
		cout << it2->first << ":" << it2->second << endl;
		it2++;
	}
	cout << endl;

?④将列表作为元素插入容器中

    unordered_map<string, int> um3;    
    um3.insert({ { "摩托车",3 }, { "电动车",7 }});
	unordered_map<string, int>::iterator it3 = um3.begin();
	while (it3 != um3.end())
	{
		cout << it3->first << ":" << it3->second << endl;
		it3++;
	}
	cout << endl;

（2）erase( )

??删除元素：

iterator erase ( const_iterator position );//删除position位置的元素，并返回删除元素的位置
size_type erase ( const key_type& k );//返回删除值为k的元素的个数
iterator erase ( const_iterator first, const_iterator last );//删除从first到last区间的元素，并返回删除的last元素的位置

?①删除position位置的元素，并返回删除元素的位置

删除搅拌车：?

    cout << um1.erase(um1.find("搅拌车"))->first << endl;

②?删除值为k的元素的，k存在返回1，k不存在返回0：

    cout << um1.erase("自行车") << endl;

③?删除从first到last区间的元素，并返回删除的last元素的位置?

    cout << um1.erase(um1.find("消防车"), um1.find("扫地车"))->first << endl;

（3）clear( )

清空所有元素：?

void clear() noexcept;

?清空um1中所有元素：

    um1.clear();

（4）swap( )

交换两个同类型容器中的元素：

	unordered_map<string, string> um4;
	um4.insert(make_pair<string, string>("spring", "春天"));
	um4.insert(make_pair<string, string>("summer", "夏天"));
	um4.insert(make_pair<string, string>("autumn", "秋天"));
	um4.insert(make_pair<string, string>("winter", "冬天"));

	unordered_map<string, string> um5;
	um5.insert(make_pair<string, string>("east", "东"));
	um5.insert(make_pair<string, string>("south", "南"));
	um5.insert(make_pair<string, string>("west", "西"));
	um5.insert(make_pair<string, string>("north", "北"));

	um4.swap(um5);

	unordered_map<string, string>::iterator it4 = um4.begin();
	while (it4 != um4.end())
	{
		cout << it4->first << ":" << it4->second << endl;
		it4++;
	}
	cout << endl;

	unordered_map<string, string>::iterator it5 = um5.begin();
	while (it5 != um5.end())
	{
		cout << it5->first << ":" << it5->second << endl;
		it5++;
	}
	cout << endl;