C++容器——unordered_set和unordered_map容器 1. unordered系列关联式容器

在C++98中，STL提供了以红黑树为底层结构的关联容器，在查找时的效率可以达到O(log_2(n))，当树的结点非常多的时候，查找的效率也不离校。因此在C++11，STL有提供了四个unordered系列的关联式容器，这些容器的底层是哈希桶，查找的效率可以达到常数级别。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、雅安服务器托管、营销软件、网站建设、肇州网站维护、网站推广。2. unordered_map 2.1 unordered_map的介绍

unordered_map的参考文档

1. unordered_map是存储键值对的关联式容器，并允许通过key快速索引到对应的value值。
2. 在内部，unordered_map没有进行任何特定的顺序排序，这是因为底层的数据结构所导致的。
3. unordered_map通过key访问单个元素要比map快，它通常在遍历元素子集的范围迭代方面效率较低。
4. 它也是重载了(operator [])运算符，通过将key作为下标访问对应的value值。
5. 它的迭代器至少是前向迭代器。

2.2 unordered_map的使用

unordered_map必须包含头文件#include，并且属于std命名空间里面。

#include#include#includeusing namespace std;

int main()
{unordered_mapm;
    m[0] = "hello";
    m[1] = "world";
    m[2] = ".";

    auto it = m.begin();
    while (it != m.end())
    {cout<< it->first<< " : "<< it->second<< " "; // 0 : hello 1 : world 2 : .
        ++it;
    }
    cout<< endl;
}

其实unordered_map与map的区别并不大，主要是底层使用的数据结构的不同，导致效率和顺序性有所差异。

2.2.1 unordered_map的定义

构造函数	接口说明
unordered_map();	无参构造

• 第一个是无参构造，构造一个空的unordered_map，传入的模板参数有key，value的类型，比较器的类型（默认是less）。

2.2.2 unordered_map的迭代器

unordered_map不存在反向迭代器，因为存入到容器中的数据顺序是乱序的，因此没有办法从最后一个位置向前遍历。

迭代器的使用	使用说明
begin()	返回指向开始位置的迭代器
end()	返回指向末尾元素的下一个位置的迭代器
cbegin()	返回指向开始并且为常量的迭代器
cend()	返回指向末尾元素的下一个位置的并且为常量的迭代器

2.2.3 unordered_map的容量

容量说明	接口说明
size	获取容器中实际的个数
empty	判断是否为空

2.2.4 unordered_map的元素访问

函数	接口说明
mapped_type& operator[](const key_type& k)	获取key对应的value值，如果key存在，则无需插入到unordered_map中，直接返回key对应的value值，如果key不存在，会将对应的key和value值插入到unordered_map中。

2.2.5 unordered_map的修改和查询

增删改查	接口说明
pair insert(const value_type& x)	在unordered_map中插入键值对，如果成功，返回新插入位置的迭代器,true，否则返回，key对应位置的迭代器,false。
erase(iterator pos)	删除unordered_map中pos位置的元素。
erase(const value_type& x)	删除unordered_map中键值对为x的元素
swap(unordered_map& m)	交换unordered_map中的元素
find(const key_type& x)	在unordered_map中查找key为x的元素，找到返回该元素位置的迭代器，找不到返回end()
count(const key_type& x)	返回unordered_map中key值为x的元素的个数
clear	清除unordered_map的元素

2.2.6 unordered_map的桶操作

函数声明	功能介绍
size_t bucket_count() const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n) const	返回n号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素key所在的桶号

3. unordered_set

参考：

unordered_set的参考文档

4. 在线OJ

重复n次的元素

class Solution 
{public:
    int repeatedNTimes(vector& A) 
    {size_t N = A.size()/2;
        // 用unordered_map统计每个元素出现的次数
        unordered_mapm;
        for(auto e : A)
        m[e]++;
        // 找出出现次数为N的元素
        for(auto& e : m)
        {if(e.second == N)
            	return e.first;
        }
    }
};

两个数组的交集I

class Solution 
{public:
    vectorintersection(vector& nums1, vector& nums2) 
    {// 用unordered_set对nums1中的元素去重
        unordered_sets1;
        for (auto e : nums1)
        	s1.insert(e);
        // 用unordered_set对nums2中的元素去重
        unordered_sets2;
        for (auto e : nums2)
        	s2.insert(e);
        // 遍历s1，如果s1中某个元素在s2中出现过，即为交集
        vectorvRet;
        for (auto e : s1)
        {	if (s2.find(e) != s2.end())
        		vRet.push_back(e);
        }
        return vRet;
    }
};

两个数组的交集II

class Solution {public:
    vectorintersect(vector& nums1, vector& nums2) {unordered_mapcount{};
        vectorresult;
        for(auto num1 : nums1)
        {count[num1]++;
        }
        for(auto num2 : nums2)
        {if(count[num2] >0)
            {result.push_back(num2);
                count[num2]--;
            }
        }
        return result;
    }
};

存在重复元素

class Solution {public:
    bool containsDuplicate(vector& nums) {unordered_mapcount;
        for(auto num : nums)
        {++count[num];
            if(count[num] >= 2)
                return true;
        }

        return false;
    }
};

两句话中不常见的单词

class Solution {public:
    vectoruncommonFromSentences(string s1, string s2) {unordered_mapcount;
        vectorret;
        auto insert = [&](const string& s)
        {stringstream ss(s);
            string word;
            while(ss >>word)
            {++count[move(word)];
            }
        };

        insert(s1);
        insert(s2);

        for(const auto& [word,occ] : count)
        {if(occ == 1)
                ret.push_back(word);
        }
        return ret;
    }
};

5. 模拟实现

因为这两个容器底层用到了哈希桶的数据结构，参考数据结构之哈希（C++实现）。

5.1 哈希表的改造

1. 模板参数列表的改造

   // K:关键码类型
   // T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是
   // unordered_set,T 为 K
   // KeyOfValue: 因为T的类型不同，通过value取key的方式就不同，详细见
   // unordered_map/set的实现
   // Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
   templateclass HashTable;

2. 增加迭代器操作

   // 前置声明
   	templateclass HashTable;
   
   	templatestruct __HashIterator
       {typedef HashNodeNode;
           typedef HashTableHT;
           typedef __HashIteratorSelf;
   
           Node* _node;
           HT* _pht;
   
           __HashIterator(Node* node, HT* pht)
               :_node(node)
                   , _pht(pht)
               {}
   
           T& operator*()
           {return _node->_data;
           }
   
           T* operator->()
           {return &_node->_data;
           }
   
           Self& operator++()
           {if (_node->_next)
               {// 当前桶中迭代
                   _node = _node->_next;
               }
               else
               {// 找下一个桶
                   Hash hash;
                   KeyOfT kot;
                   size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
                   ++i;
                   for (; i< _pht->_tables.size(); ++i)
                   {if (_pht->_tables[i])
                       {_node = _pht->_tables[i];
                           break;
                       }
                   }
   
                   // 说明后面没有有数据的桶了
                   if (i == _pht->_tables.size())
                   {_node = nullptr;
                   }
               }
   
               return *this;
           }
   
           bool operator!=(Self& s) const
           {return _node != s._node;
           }
   
           bool operator==(Self& s) const
           {return _node == s._node;
           }
       };
   

3. 增加通过key获取value的操作

   templateclass HashTable
   	{typedef HashNodeNode;
   		// 迭代器
   		templatefriend struct __HashIterator;
   	public:
   		typedef __HashIteratoriterator;
   
   		iterator begin()
   		{	for (size_t i = 0; i< _tables.size(); ++i)
   			{		if (_tables[i])
   				{return iterator(_tables[i], this);
   				}
   			}
   
   			return end();
   		}
   
   		iterator end()
   		{	return iterator(nullptr, this);
   		}
   
   		~HashTable()
   		{	for (size_t i = 0; i< _tables.size(); ++i)
   			{		Node* cur = _tables[i];
   				while (cur)
   				{Node* next = cur->_next;
   					delete cur;
   					cur = next;
   				}
   				_tables[i] = nullptr;
   			}
   		}
   
   		inline size_t __stl_next_prime(size_t n)
   		{	static const size_t __stl_num_primes = 28;
   			static const size_t __stl_prime_list[__stl_num_primes] =
   			{		53, 97, 193, 389, 769,
   				1543, 3079, 6151, 12289, 24593,
   				49157, 98317, 196613, 393241, 786433,
   				1572869, 3145739, 6291469, 12582917, 25165843,
   				50331653, 100663319, 201326611, 402653189, 805306457,
   				1610612741, 3221225473, 4294967291
   			};
   
   			for (size_t i = 0; i< __stl_num_primes; ++i)
   			{		if (__stl_prime_list[i] >n)
   				{return __stl_prime_list[i];
   				}
   			}
   
   			return -1;
   		}
   
   		std::pairInsert(const T& data)
   		{	Hash hash;
   			KeyOfT kot;
   
   			// 去重
   			iterator ret = Find(kot(data));
   			auto ret_end = end();
   			if (ret != ret_end)
   			{		return std::make_pair(ret, false);
   			}
   
   			// 负载因子到1就扩容
   			if (_size == _tables.size())
   			{		//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
   				vectornewTables;
   				//newTables.resize(newSize, nullptr);
   				newTables.resize(__stl_next_prime(_tables.size()), nullptr);
   				// 旧表中节点移动映射新表
   				for (size_t i = 0; i< _tables.size(); ++i)
   				{Node* cur = _tables[i];
   					while (cur)
   					{Node* next = cur->_next;
   
   						size_t hashi = hash(kot(cur->_data)) % newTables.size();
   						cur->_next = newTables[hashi];
   						newTables[hashi] = cur;
   
   						cur = next;
   					}
   
   					_tables[i] = nullptr;
   				}
   
   				_tables.swap(newTables);
   			}
   
   			size_t hashi = hash(kot(data)) % _tables.size();
   			// 头插
   			Node* newnode = new Node(data);
   			newnode->_next = _tables[hashi];
   			_tables[hashi] = newnode;
   			++_size;
   
   			return std::make_pair(iterator(newnode, this), true);
   		}
   
   		iterator Find(const K& key)
   		{	if (_tables.size() == 0)
   			{		return end();
   			}
   
   			Hash hash;
   			KeyOfT kot;
   			size_t hashi = hash(key) % _tables.size();
   			Node* cur = _tables[hashi];
   			while (cur)
   			{		if (kot(cur->_data) == key)
   				{return iterator(cur, this);
   				}
   
   				cur = cur->_next;
   			}
   
   			return end();
   		}
   
   		bool Erase(const K& key)
   		{	if (_tables.size() == 0)
   			{		return false;
   			}
   
   			Hash hash;
   			KeyOfT kot;
   			size_t hashi = hash(key) % _tables.size();
   			Node* prev = nullptr;
   			Node* cur = _tables[hashi];
   			while (cur)
   			{		if (kot(cur->_data) == key)
   				{// 1、头删
   					// 2、中间删
   					if (prev == nullptr)
   					{_tables[hashi] = cur->_next;
   					}
   					else
   					{prev->_next = cur->_next;
   					}
   
   					delete cur;
   					--_size;
   
   					return true;
   				}
   
   				prev = cur;
   				cur = cur->_next;
   			}
   
   			return false;
   		}
   
   		// ....
   
   	private:
   		std::vector_tables;
   		size_t _size = 0; // 存储有效数据个数
       };

5.2 unordered_map模拟实现

namespace ming
{template>class unordered_map
	{struct MapKeyOfT
		{	const K& operator()(const std::pair& kv)
			{		return kv.first;
			}
		};
	public:
		typedef typename HashBucket::HashTable, Hash, MapKeyOfT>::iterator iterator;

		iterator begin()
		{	return _ht.begin();
		}

		iterator end()
		{	return _ht.end();
		}

		pairInsert(const pair& kv)
		{	return _ht.Insert(kv);
		}

		V& operator[](const K& key)
		{	pairret = _ht.Insert(std::make_pair(key, V()));
			return ret.first->second;
		}

	private:
		HashBucket::HashTable, Hash, MapKeyOfT>_ht;
	};
}

5.3 unordered_set模拟实现

#pragma once
#include "HashTable.h"

namespace ming
{template>class unordered_set
    {struct SetKeyOfT
        {const K& operator()(const K& key)
            {return key;
            }
        };

    public:
        typedef typename HashBucket::HashTable::iterator iterator;

        iterator begin()
        {return _ht.begin();
        }

        iterator end()
        {return _ht.end();
        }

        pairinsert(const K& key)
        {return _ht.Insert(key);
        }

    private:
        HashBucket::HashTable_ht;
    };
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：C++容器篇，unordered-创新互联
文章链接：http://njwzjz.com/article/csigji.html