扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
在C++98中，STL提供了以红黑树为底层结构的关联容器，在查找时的效率可以达到O(log_2(n))，当树的结点非常多的时候，查找的效率也不离校。因此在C++11，STL有提供了四个unordered系列的关联式容器，这些容器的底层是哈希桶，查找的效率可以达到常数级别。
unordered_map的参考文档
(operator [])运算符，通过将key作为下标访问对应的value值。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(); | 无参构造 |
2.2.2 unordered_map的迭代器
- 第一个是无参构造，构造一个空的unordered_map，传入的模板参数有key，value的类型，比较器的类型（默认是less）。
unordered_map不存在反向迭代器，因为存入到容器中的数据顺序是乱序的，因此没有办法从最后一个位置向前遍历。
| 迭代器的使用 | 使用说明 |
|---|---|
| begin() | 返回指向开始位置的迭代器 |
| end() | 返回指向末尾元素的下一个位置的迭代器 |
| cbegin() | 返回指向开始并且为常量的迭代器 |
| cend() | 返回指向末尾元素的下一个位置的并且为常量的迭代器 |
| 容量说明 | 接口说明 |
|---|---|
| size | 获取容器中实际的个数 |
| empty | 判断是否为空 |
| 函数 | 接口说明 |
|---|---|
| mapped_type& operator[](const key_type& k) | 获取key对应的value值，如果key存在，则无需插入到unordered_map中，直接返回key对应的value值，如果key不存在，会将对应的key和value值插入到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的元素 |
| 函数声明 | 功能介绍 |
|---|---|
| size_t bucket_count() const | 返回哈希桶中桶的总个数 |
| size_t bucket_size(size_t n) const | 返回n号桶中有效元素的总个数 |
| size_t bucket(const K& key) | 返回元素key所在的桶号 |
参考：
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;
}
}; 因为这两个容器底层用到了哈希桶的数据结构，参考数据结构之哈希（C++实现）。
5.1 哈希表的改造模板参数列表的改造
// K:关键码类型
// T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是
// unordered_set,T 为 K
// KeyOfValue: 因为T的类型不同，通过value取key的方式就不同，详细见
// unordered_map/set的实现
// Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
templateclass HashTable; 增加迭代器操作
// 前置声明
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;
}
};
增加通过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; // 存储有效数据个数
}; 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;
};
} #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元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网