技术标签: c++ unordered_set unordered_map STL 哈希
目录
STL标准模板库中的map、set的底层数据结构是红黑树,会在数据插入时自动排序,unordered_map、unordered_set的底层数据结构是哈希表,不做排序,根据哈希值进行映射。
哈希算法可见这篇文章:
unordered_map、unordered_set的特性与map、set基本一样,数据插入和删除的效率都差不多,但是unordered_map、unordered_set的查询效率远高于map、set。
unordered_map、unordered_set的封装与map、set的封装很相似。
封装细节、迭代器设计具体可见这篇文章:
【C++】STL之map、set类源码剖析_种花家de小红帽的博客-程序员宅基地
#pragma once
#include <iostream>
#include <vector>
// 仿函数
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 特化
template<>
struct HashFunc<std::string>
{
size_t operator()(const std::string& str)
{
size_t res = 0;
for (const auto& ch : str)
{
res *= 131; // 随机数取值,避免哈希冲突
res += ch;
}
return res;
}
};
// 节点
template<class T>
struct HashNode
{
T _data;
HashNode<T>* next;
HashNode(const T& data)
: _data(data), next(nullptr)
{}
};
// 前置声明
template<class K, class T, class Hash, class KofT>
class HashTable;
// 迭代器
template<class K, class T, class Ref, class Ptr, class Hash, class KofT>
struct Iterator
{
typedef HashNode<T> Node;
typedef Iterator<K, T, Ref, Ptr, Hash, KofT> Self;
typedef HashTable<K, T, Hash, KofT> HT;
Node* _node;
HT* _ht;
Iterator(Node* node, HT* ht)
: _node(node), _ht(ht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
Self& operator++()
{
if (_node->next)
{
_node = _node->next;
}
else
{
// 寻找下一个桶的第一个节点
KofT kot;
Hash hs;
size_t pos = hs(kot(_node->_data)) % _ht->_table.size();
++pos;
while (pos < _ht->_table.size())
{
if (_ht->_table[pos] == nullptr)
{
++pos;
}
else
{
_node = _ht->_table[pos];
break;
}
}
if (pos == _ht->_table.size())
{
_node = nullptr;
}
}
return *this;
}
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
};
// 哈希桶
template<class K, class T, class Hash, class KofT>
class HashTable
{
typedef HashNode<T> Node;
template<class K, class T, class Ref, class Ptr, class Hash, class KofT>
friend struct Iterator;
public:
typedef Iterator<K, T, T&, T*, Hash, KofT> iterator;
typedef Iterator<K, T, const T&, const T*, Hash, KofT> const_iterator;
iterator begin()
{
for (int i = 0; i < _table.size(); ++i)
{
if (_table[i] != nullptr)
{
return iterator(_table[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const
{
for (int i = 0; i < _table.size(); ++i)
{
if (_table[i] != nullptr)
{
return const_iterator(_table[i], this);
}
}
return const_iterator(nullptr, this);
}
const_iterator end()const
{
return const_iterator(nullptr, this);
}
// 迭代器拷贝构造
template<class InputIterator>
HashTable(InputIterator first, InputIterator last)
{
_n = 0;
_table.resize(10);
while (first != last)
{
insert(*first);
++first;
}
}
void swap(HashTable<K, T, Hash, KofT>& ht)
{
std::swap(_table, ht._table);
std::swap(_n, ht._n);
}
HashTable(const HashTable<K, T, Hash, KofT>& ht)
{
HashTable<K, T, Hash, KofT> tmp(ht.begin(), ht.end());
swap(tmp);
}
HashTable<K, T, Hash, KofT>& operator=(HashTable<K, T, Hash, KofT> ht)
{
swap(ht);
return *this;
}
HashTable()
: _n(0)
{
_table.resize(10, nullptr);
}
~HashTable()
{
for (int i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
std::pair<iterator, bool> insert(const T& data)
{
KofT koft;
iterator it = find(koft(data));
if (it != end())
{
return std::make_pair(it, false);
}
// 扩容, 平衡因子为 1
if (_n == _table.size())
{
std::vector<Node*> newTable;
newTable.resize(_table.size() * 2, nullptr);
for (int i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->next;
size_t pos = Hash()(koft(cur->_data)) % newTable.size();
if (newTable[pos] == nullptr)
{
newTable[pos] = cur;
cur->next = nullptr;
}
else
{
cur->next = newTable[pos];
newTable[pos] = cur;
}
cur = next;
}
}
_table.swap(newTable);
}
// 插入节点
Node* newNode = new Node(data);
size_t pos = Hash()(koft(data)) % _table.size();
newNode->next = _table[pos];
_table[pos] = newNode;
++_n;
return std::make_pair(iterator(newNode, this), true);
}
iterator find(const K& key)
{
size_t pos = Hash()(key) % _table.size();
Node* cur = _table[pos];
while (cur)
{
if (KofT()(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->next;
}
return iterator(nullptr, this);
}
bool erase(const K& key)
{
iterator it = find(key);
if (it != end())
{
size_t pos = Hash()(key) % _table.size();
Node* cur = _table[pos];
if (cur == it._node)
{
cur = it._node->next;
delete it._node;
it._node = nullptr;
}
else
{
while (cur->next != it._node)
{
cur = cur->next;
}
cur->next = it._node->next;
delete it._node;
it._node = nullptr;
}
--_n;
return true;
}
else
{
return false;
}
}
private:
std::vector<Node*> _table;
size_t _n;
};
#pragma once
#include "HashTable.h"
template<class K, class V, class Hash = HashFunc<K>>
class UnorderedMap
{
struct MapKofT
{
const K& operator()(const std::pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, std::pair<const K, V>, Hash, MapKofT>::iterator iterator;
typedef typename HashTable<K, std::pair<const K, V>, Hash, MapKofT>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
// 迭代器构造
template<class InputIterator>
UnorderedMap(InputIterator first, InputIterator last)
{
_ht = HashTable<K, std::pair<const K, V>, Hash, MapKofT>(first, last);
}
UnorderedMap(UnorderedMap<K, V>& uMap)
{
_ht = HashTable<K, std::pair<const K, V>, Hash, MapKofT>(uMap.begin(), uMap.end());
}
UnorderedMap<K, V>& operator=(UnorderedMap<K, V>& uMap)
{
_ht = HashTable<K, std::pair<const K, V>, Hash, MapKofT>(uMap.begin(), uMap.end());
return *this;
}
UnorderedMap()
: _ht(HashTable<K, std::pair<const K, V>, Hash, MapKofT>())
{}
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
return _ht.insert(kv);
}
iterator find(const K& key)
{
return _ht.find(key);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = _ht.insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, std::pair<const K, V>, Hash, MapKofT> _ht;
};
#pragma once
#include "HashTable.h"
template<class K, class Hash = HashFunc<K>>
class UnorderedSet
{
struct SetKofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, K, Hash, SetKofT>::iterator iterator;
typedef typename HashTable<K, K, Hash, SetKofT>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
// 迭代器构造
template<class InputIterator>
UnorderedSet(InputIterator first, InputIterator last)
{
_ht = HashTable<K, K, Hash, SetKofT>(first, last);
}
UnorderedSet(UnorderedSet<K>& uSet)
{
_ht = HashTable<K, K, Hash, SetKofT>(uSet.begin(), uSet.end());
}
UnorderedSet<K>& operator=(UnorderedSet<K>& uSet)
{
_ht = HashTable<K, K, Hash, SetKofT>(uSet.begin(), uSet.end());
return *this;
}
UnorderedSet()
: _ht(HashTable<K, K, Hash, SetKofT>())
{}
std::pair<iterator, bool> insert(const K& key)
{
std::pair<iterator, bool> ret = _ht.insert(key);
return std::make_pair(ret.first, ret.second);
}
iterator find(const K& key)
{
return _ht.find(key);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
private:
HashTable<K, K, Hash, SetKofT> _ht;
};
#include "UnorderedMap.h"
#include "UnorderedSet.h"
#include <iostream>
using namespace std;
void unordered_map_test1()
{
int arr[] = { 34, 36, 12, 54, 5, 22, 65, 32, 13, 4, 1, 52 };
cout << "uMap1:" << endl;
UnorderedMap<int, int> uMap1;
for (const auto& e : arr)
{
uMap1.insert(make_pair(e, e));
}
for (const auto& e : uMap1)
{
cout << e.first << ": " << e.second << endl;
}
cout << endl;
cout << uMap1.find(32)._node << endl;
cout << uMap1.find(42)._node << endl;
cout << uMap1.find(52)._node << endl;
uMap1.erase(32);
cout << uMap1.find(32)._node << endl;
cout << uMap1.find(42)._node << endl;
cout << uMap1.find(52)._node << endl;
UnorderedMap<int, int>::iterator it1 = uMap1.begin();
while (it1 != uMap1.end())
{
cout << it1._node->_data.first << ": " << it1._node->_data.second << endl;
++it1;
}
cout << endl;
// 迭代器构造
cout << "uMap2:" << endl;
UnorderedMap<int, int> uMap2(uMap1.begin(), uMap1.end());
UnorderedMap<int, int>::iterator it2 = uMap2.begin();
while (it2 != uMap2.end())
{
cout << (*it2).first << ": " << (*it2).second << endl;
++it2;
}
cout << endl;
// 拷贝构造
cout << "uMap3:" << endl;
UnorderedMap<int, int> uMap3(uMap2);
UnorderedMap<int, int>::iterator it3 = uMap3.begin();
while (it3 != uMap3.end())
{
cout << (*it3).first << ": " << (*it3).second << endl;
it3++;
}
cout << endl;
}
void unordered_map_test2()
{
std::vector<std::string> food = {
"蛋糕", "西瓜", "啤酒", "苹果", "香蕉", "蛋糕", "牛肉",
"西瓜", "苹果", "啤酒", "西瓜", "牛肉", "蛋糕", "蛋糕",
"西瓜", "西瓜", "牛肉", "苹果", "香蕉", "蛋糕", "西瓜"
};
UnorderedMap<std::string, int> foodMap;
for (auto& e : food)
{
foodMap[e]++;
}
for (auto& e : foodMap)
{
std::cout << e.first << ": " << e.second << std::endl;
}
std::cout << std::endl;
}
void unordered_set_test()
{
int arr[] = { 34, 36, 12, 54, 5, 22, 65, 32, 13, 4, 1, 52 };
cout << "uSet1:" << endl;
UnorderedSet<int> uSet1;
for (const auto& e : arr)
{
uSet1.insert(e);
}
for (auto& e : uSet1)
{
cout << e << ' ';
}
cout << endl;
cout << "uSet2:" << endl;
UnorderedSet<int> uSet2(uSet1.begin(), uSet1.end());
for (auto& e : uSet2)
{
cout << e << ' ';
}
cout << endl;
cout << "uSet3:" << endl;
UnorderedSet<int> uSet3(uSet2);
UnorderedSet<int>::iterator it3 = uSet3.begin();
while (it3 != uSet3.end())
{
cout << *it3 << ' ';
++it3;
}
cout << endl;
}
int main()
{
unordered_map_test1();
unordered_map_test2();
unordered_set_test();
return 0;
}
文章浏览阅读245次。MySQL数据库的主键和外键详解主键主键的定义主键:表中经常有一个列或多列的组合,其值能唯一地标识表中的每一行。这样的一列或多列称为表的主键,通过它可强制表的实体完整性。当创建或更改表时可通过定义 PRIMARY KEY 约束来创建主键。一个表只能有一个 PRIMARY KEY 约束,而且 PRIMARY KEY 约束中的列不能接受空值。由于 PRIMARY KEY 约束确保唯一数据,所以经常用来..._主键 外键 公共维度
文章浏览阅读889次,点赞20次,收藏9次。关节目标位置空间设为BCSBoneSpace时,用作关节目标位置的骨骼命名。执行器位置空间设为BCSBoneSpace时,用作执行器位置的骨骼命名。要应用IK解算器的骨骼命名。启用时,执行器(组件、父或骨骼)的旋转将应用到IK骨骼。肢体最大长度的比率,用于决定缩放骨骼的时间。在关节目标位置空间中指定位置关节目标的向量。XYZ组件在目标骨骼上的平移。XYZ组件在目标骨骼上的旋转。XYZ组件在目标骨骼上的缩放。XYZ组件在目标骨骼上的平移。XYZ组件在目标骨骼上的旋转。XYZ组件在目标骨骼上的缩放。
文章浏览阅读1.2k次。传送门 // 题意: 有k个怪物, 告诉每个怪物捕捉它需要的精灵球和皮卡丘收到的伤害, 给定精灵球的一共的数量和皮卡丘总的体力值, 问最多可以捕捉到多少个怪物, 然后如果能捕捉到的怪物相同则要消耗的体力值尽量的小….思路: 很明显的二维背包费用的题, 加了一维费用那么dp数组同时加一维即可……捡起一个物品所需要付出两种代价, 所以dp[i][u][v] 代表捕捉前i个怪物用掉精灵球u个, 体..._宠物小精灵之收服 百练
文章浏览阅读2k次。1.定义一个空的指针函数 指针函数的参数是uint8_t 类型chtypedef void (* usart_recv_callback)(uint8_t ch);2.声明这个类型usart_recv_callback usart1_recv_cb;3.串口配置时,一个形参为串口中断接收回调void Usart_Config(USART_TypeDef* USARTx, uint32_t bau..._stm32回调函数和中断服务函数
文章浏览阅读794次。对比文件,生成github diff报告_github文件对比
文章浏览阅读760次。Python 实现C、C++程序注释英文翻译插件。3.此文缺少访问超时等待续翻译代码段,暂时没空添加。2.安装核心功能包translators。1.参数3个,源文件、目标文件、翻译模式。4.编写正则表达式分析文本内容。3.编写文本输入输出函数。6.Keil实践提示。_针对c语言注释进行翻译
文章浏览阅读668次。这款VR研究工具可以用于心理学、消费者行为和人类表现等方面,是低成本、高效率的解决方案。 最近,Tobii Pro推出一款新的研究工具,可用于沉浸式VR研究。这种沉浸式VR研究与传统的研究方式大相径庭,可广泛应用于各类研究。据了解,Tobii Pro VR集成方案基于Tobii的眼动追踪技术和HTC Vive头显,并结..._vive unity vr 眼动数据
文章浏览阅读543次。 abort 中止 abstract class 抽象类 accelerator 快捷键 accelerator mapping 快捷键映射 accelerator table 快捷键对应表 access modifier 访问修饰符 Access Pack 访问包 access specifier 访问说明符 access violation 访问冲突 accessibili..._implementation 开发人员 setup
文章浏览阅读9.2w次,点赞108次,收藏95次。一位大四学长的实习体验,职场建议,经验分享,转型思考。_学长实习经验分享
文章浏览阅读2.3k次。C语言结构注释变量定义与赋值数据类型强制转换前言:我们都知道单片机要对其写指令、编程等就需要一种编程语言。在众多的编程语言中不可否认的是c语言是最适合成为单片机的编程语言的。我们在这里分享一下c语言的知识点。结构一般来说c语言的结构,一般都是包括若干个头文件(以#include" xxx ")和函数组合而成的。例:#include "stdio.h"int main(void){ printf("hello wold"); return 0;}在这里我们看到有两部分#include_单片机编程
文章浏览阅读326次。在一片漆黑的界面下,我们该如何查看和配置系统网卡、IP地址、路由等信息呢?最传统基本的网络命令,几乎所有旧的发行版都支持的配置命令:ifconfig查看系统的所有网卡及IP配置信息:ifconfig禁用网卡:ifconfig eth0 down,启用网卡:ifconfig eth0 up为网卡配置IP地址:ifconfig eth0 192.168.1.56 netmask 255.255.255.0Ifconfig命令的替代者,最新版本的linux发行版都支持:查看系统的所有...
文章浏览阅读1.7k次。文章目录1. Language to Logical Form with Neural Attention2. Abstract Syntax Networks for Code Generation and Semantic Parsing3. A Syntactic Neural Model for General-Purpose Code Generation4. Tree-structured Decoding with Doubly-recurrent Neural Network5. Seman_a syntactic neural model for general-purpose code generation,