ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++ unordered_map [打印本页]

---

作者: 冬雨财经    时间: 2024-7-28 14:14
标题: C++ unordered_map
1. unordered系列关联式容器

   在C++98  中，  STL  提供了底层为红黑树布局的一系列关联式容器，在查询时效率可到达   

  ，即最差情况下必要比力红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比力次数就可以或许将元素找到，因此在C++11  中，  STL  又提供了  4  个unordered系列的关联式容器，这四个容器与红黑树布局的关联式容器利用方式根本雷同，只是其底层布局差别,该系列容器利用哈希表进行封装。     2. unordered_map的先容

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

  1. unordered_map的构造

  

函数声明	功能先容
unordered_map()	构造差别格式的       unordered_map       对象

  2. unordered_map的容量

  

函数声明	功能先容
bool empty() const	检测       unordered_map       是否为空
size_t size() const	获取       unordered_map       的有效元素个数

     3. unordered_map的迭代器

      

函数声明	功能先容
iterator  begin()	返回         unordered_map         第一个元素的迭代器
iterator end()	返回         unordered_map         末了一个元素下一个位置的迭代器
const_iterator cbegin() const	返回         unordered_map         第一个元素的         const         迭代器
const_iterator cend() const	返回         unordered_map         末了一个元素下一个位置的         const         迭代器

   
    4. unordered_map的元素访问

   

函数声明	功能先容
mapped_type& operator[ ] (const key_type& k)	返回与         key         对应的         value         ，没有返回一个默认值

         注意：该函数中现实调用哈希桶的插入利用，用参数     key     与     V()     构造一个默认值往底层哈希桶中插入，如果key     不在哈希桶中，插入乐成，返回     V()     ，插入失败，说明     key     已经在哈希桶中，将key     对应的     value     返回。        5. unordered_map的查询

   

函数声明	功能先容
iterator find(const K& key)	返回         key         在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为         key         的键值对的个数

         注意：     unordered_map     中     key     是不能重复的，因此     count     函数的返回值最大为     1        6. unordered_map的修改利用

   

函数声明	功能先容
pair<iterator,bool> insert (const value_type& x )	向容器中插入键值对
size_type erase ( const key_type& x )	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元

    7. unordered_map的桶利用

   

函数声明	功能先容
size_t bucket_count()const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const	返回         n         号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素         key         地点的桶号

   

    4.unordered_map的模拟实现

    首先我们要利用哈希表进行封装unordered_map即可，如下是HashTable.cpp的文件，有关哈希表的详细先容，可以点击了解C++哈希表。
   

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. namespace OpenHash
5. {
6.         template<class T>
7.         struct HashNode
8.         {
9.                 T _data;
10.                 HashNode* _next;
11.                 HashNode(const T& data)
12.                         :_data(data)
13.                         , _next(nullptr)
14.                 {}
15.         };
16.         //将key转换为整型方便取模
17.         template <class K>
18.         struct Hash
19.         {
20.                 size_t operator()(const K& key)
21.                 {
22.                         return key;
23.                 }
24.         };
25.         //模板特化,将string类型转换为整型
26.         template<>
27.         class Hash<string>
28.         {
29.                 size_t operator()(const string& s)
30.                 {
31.                         size_t ret = 0;
32.                         for (auto e : s)
33.                         {
34.                                 ret = ret * 31 + e;
35.                         }
36.                         return ret;
37.                 }
38.         };
39.         //实现迭代器
40.         //因为迭代器的实现需要借助HashTable，所以需要前置定义
41.         template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
42.         class HashTable;
43.         template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc = Hash<K>>
44.         struct HashTableIterator
45.         {
46.                 typedef typename HashNode<T> Node;
47.                 typedef typename HashTableIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
48.                 typedef typename HashTable<K, T, KeyOfT, HashFunc> HashTable;
50.                 HashTable* _ht;
51.                 Node* _node;
52.                 HashTableIterator() = default;
53.                 HashTableIterator(const Node*& node, const HashTable*& ht)
54.                         :_ht(ht)
55.                         , _node(node)
56.                 {}
57.                 Self& operator++()
58.                 {
59.                         //遍历当前桶
60.                         if (_node->_next)
61.                                 _node = _node->_next;
62.                         //找下一个桶
63.                         else
64.                         {
65.                                 KeyOfT kot;
66.                                 HashFunc hf;
67.                                 //获取索引值
68.                                 size_t index = hf(kot(_node->_data)) % _ht->_table.size();
69.                                 ++index;
70.                                 while (index < _ht->_table.size() && _ht->_table[index] == nullptr)
71.                                         ++index;
72.                                 if (index == _ht->_table.size())
73.                                         _node = nullptr;
74.                                 else
75.                                         _node = _ht->_table[index];
76.                         }
77.                         return *this;
78.                 }
79.                 Ref operator*()
80.                 {
81.                         return _node->_data;
82.                 }
83.                 Ptr operator->()
84.                 {
85.                         return &_node->_data;
86.                 }
87.                 bool operator==(const Self& s)
88.                 {
89.                         return _node == s._node;
90.                 }
91.                 bool operator!=(const Self& s)
92.                 {
93.                         return _node != s._node;
94.                 }
95.         };
97.         template <class K, class T, class KeyOfT, class HashFunc>
98.         class HashTable
99.         {
100.         public:
101.                 //友元(因为iterator需要用到_table)
102.                 template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
103.                 friend struct HashTableIterator;
104.                 typedef typename HashNode<T> Node;
105.                 typedef typename HashTableIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
106.                 //构造函数
107.                 HashTable()
108.                         :_table(vector<Node*>())
109.                         , _n(0)
110.                 {}
111.                 iterator begin()
112.                 {
113.                         for (size_t i = 0; i < _table.size(); i++)
114.                         {
115.                                 if (_table[i])
116.                                         return iterator(_table[i], this);
117.                         }
118.                         return iterator(nullptr, this);
119.                 }
120.                 iterator end()
121.                 {
122.                         return iterator(nullptr, this);
123.                 }
124.                 iterator find(const K& key)
125.                 {
126.                         if (_table.size() == 0)
127.                         {
128.                                 return iterator(nullptr, this);
129.                         }
130.                         KeyOfT kot;
131.                         HashFunc hf;
132.                         size_t index = hf(key) % _table.size();
133.                         Node* cur = _table[index];
134.                         while (cur)
135.                         {
136.                                 if (kot(cur->_data) == key)
137.                                         return iterator(cur, this);
138.                                 cur = cur->_next;
139.                         }
140.                         return iterator(nullptr, this);
141.                 }
142.                 pair<iterator, bool> insert(const K& key)
143.                 {
144.                         //第一次插入需要扩容
145.                         if (_table.size() == 0)
146.                                 _table.resize(10);
147.                         //不能出现重复数据
148.                         if (find(key) != iterator(nullptr, this))
149.                         {
150.                                 return make_pair(find(key), false);
151.                         }
152.                         KeyOfT kot;
153.                         HashFunc hf;
154.                         //桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，
155.                         //可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对
156.                         //哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个
157.                         //节点,再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数
158.                         //时，可以给哈希表增容。
159.                         //负载因子到1，需要扩容
160.                         if (_n == _table.size())
161.                         {
162.                                 vector<Node*> newtable;
163.                                 newtable.resize(_table.size() * 2);
164.                                 //重新映射到新表
165.                                 for (auto e : _table)
166.                                 {
167.                                         Node* cur = e;
168.                                         while (cur)
169.                                         {
170.                                                 size_t index = hf(kot(cur->_data)) % newtable.size();
171.                                                 cur->_next = newtable[index];
172.                                                 newtable[index] = cur;
173.                                                 cur = cur->_next;
174.                                         }
175.                                 }
176.                         }
177.                         size_t index = hf(key) % _table.size();
178.                         Node*& cur = _table[index];
179.                         while (cur)
180.                                 cur = cur->_next;
181.                         cur = new Node(key);
182.                         return make_pair(iterator(cur, this), true);
183.                 }
184.                 bool erase(const K& key)
185.                 {
186.                         KeyOfT kot;
187.                         HashFunc hf;
188.                         size_t index = hf(key) % _table.size();
189.                         Node* cur = _table[index], * pre = _table[index];
190.                         while (cur)
191.                         {
192.                                 if (kot(cur->_data) == key)
193.                                 {
194.                                         //要删除该位置第一个元素
195.                                         if (cur == pre)
196.                                                 _table[index] = cur->_next;
197.                                         else
198.                                                 pre->_next = cur->_next;
200.                                         delete cur;
201.                                         _n--;
202.                                         return true;
203.                                 }
204.                                 pre = cur;
205.                                 cur = cur->_next;
206.                         }
207.                         return false;
208.                 }
209.         private:
210.                 vector<Node*> _table;
211.                 size_t _n;//有效数据个数
212.         };
213. }

复制代码

   unordered_map.cpp文件如下
   

1. #include"HashTable.cpp"
2. namespace lbk
3. {
4.         template<class K,class Hash=OpenHash::Hash<K>>
5.         class unordered_set
6.         {
7.                 struct SetKeyOfT
8.                 {
9.                         const K& operator()(const K& key)
10.                         {
11.                                 return key;
12.                         }
13.                 };
14.         public:
15.                 typedef typename OpenHash::HashTable<K,K,SetKeyOfT,Hash>::iterator iterator;
16.                 iterator begin()
17.                 {
18.                         return _ht.begin();
19.                 }
20.                 iterator end()
21.                 {
22.                         return _ht.end();
23.                 }
24.                 iterator find(const K& key)
25.                 {
26.                         return _ht.find(key);
27.                 }
28.                 pair<iterator, bool> insert(const K& key)
29.                 {
30.                         return _ht.insert(key);
31.                 }
32.                 bool erase(const K& key)
33.                 {
34.                         return _ht.erase(key);
35.                 }
36.         private:
37.                 OpenHash::HashTable<K, K, SetKeyOfT, Hash> _ht;
38.         };
39. }

复制代码

   

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4