平武建站

C++容器篇，unordered-创新互联

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://pwwzsj.com/article/csigji.html

其他资讯