文章目录

1. unordered系列关联式容器1.1 unordered_set1.2 unordered_map

2. unordered_set/map的封装2.1 基本接口2.2 迭代器2.2.1 迭代器的结构2.2.2 set迭代器的封装2.2.3 map迭代器的封装

3.完整代码3.1HashTable3.2unordered_set3.3unordered_map

1. unordered系列关联式容器

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

l

o

g

2

N

log_2 N

log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，

1.1 unordered_set

unordered_set是以不特定顺序存储唯一元素的容器，并允许根据其值快速检索单个元素。在unordered_set中，元素的值同时是其键，它唯一地标识它。键是不可变的，因此，unordered_set中的元素在容器中不能被修改，但是它们可以入和删除。在内部，unordered_set中的元素不按任何特定顺序排序，而是根据其哈希值放到桶中，以便直接通过其值快速访问各个元素（平均平均时间复杂度恒定）。unordered_set容器通过其键访问单个元素的速度比set容器更快，尽管它们在通过其元素子集进行范围迭代时通常效率较低。

1.2 unordered_map

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

2. unordered_set/map的封装

2.1 基本接口

上一篇文章我们模拟实现了哈希表，在这里我们直接对其进行改造，将其封装为unordered_set/map。

由于我们的unordered_map与unordered_set使用的是一个哈希表，所以我们首先对哈希表的模板参数进行改造。

由于map是k、v模型，set是k，所以在哈希表那一层我们统一处理成T。

在哈希表内部使用key进行比较时，需要使用一个函数获得map与set的key。

所以，在哈希表中所有涉及使用T类型的data计算位置与比较的地方都得改。

unordered_map与unordered_set框架对比

由于一般key都是不允许修改的，所以<code>这里set传递的是const K；map传的是pair<const K,V>

2.2 迭代器

2.2.1 迭代器的结构

对于哈希表而言，迭代器++应该指向当前桶的下一个元素，当前桶走完了就应该到下一个桶。

那如何弄清下一个桶在什么位置呢？

迭代器内部除了要有一个节点的指针，还应该有一个表的指针，在该表中可以找到桶的位置。

此时编译我们的代码，发现找不到node和table

Node和HashTable找不到是因为我们把它们的定义放在了HTIterator的后面，编译器只会向上找，所以我们可以把Node的定义放在它上面，但是HashTable的定义能放在它上面吗？

由于我们后期会在HashTable中使用HTIterator，它们两个是相互依赖的，谁定义在谁上面都不行。所以我们可以前置声明一下，同时注意声明与定义处的缺省参数不能同时有

operator++

迭代器++时，要知道当前桶中还有没有元素，如果有元素，则指向下一个元素；如果没有元素，则指向下一个桶的第一个元素。

由于HtIterator内部要访问哈希表成员_table，但由于哈希表的成员_table是私有的，在外部无法访问。所以我们可将HTIterator设置为HahTable的友元类

<code>Self& operator++()

{ -- -->

if (_node->_next)//当前桶还有元素

{

_node = _node->_next;

}

else

{

KeyOfT kot;

Hash hs;

size_t hashi = hs(kot(_node->_data)) % _pt->_table.size();

hashi++;//指向下一个桶

while (hashi < _pt->_table.size())

{

if (_pt->_table[hashi])//“下一个”桶有元素

{

break;

}

else

{

hashi++;

}

}

if (hashi == _pt->_table.size())//若后面没有桶了

{

_node = nullptr; //end()

}

else

{

_node = _pt->_table[hashi];

}

}

return *this;

}

-> 、*、!=

T& operator*()

{

return _node->_data;

}

T* operator->()

{

return &_node->_data;

}

bool operator !=(const Self& s)

{

_node != s._node;

}

2.2.2 set迭代器的封装

普通迭代器

先在哈希表内部封装迭代器

再封装set的迭代器

此时我们set的迭代器就可以跑起来了

由于我们对模板参数进行传递时，K都使用了const修饰，所以key是不允许修改的。

2. const迭代器

首先我们要明白，const迭代器是不允许修改的，无论是K还是V。所以我们只需对迭代器的 -> 与 * 操作做修改即可。

所以我们要给底层迭代器增加两个模板参数，使用普通迭代器时可以对V进行修改；使用const迭代器不允许修改V。

哈希表中的const迭代器

set的const迭代器

2.2.3 map迭代器的封装

由于我们已经实现了set，所有哈希表内迭代器的坑已经被我们跳过了，这里我们只需简单的封装map即可。

普通迭代器

const迭代器

operator[ ]

对于map[key]而言，如果key已经存在，则插入失败，并且返回key所对应位置的迭代器。如果key不存在，则将key插入，value为类型的默认值，并返回其迭代器。

所以我们要改造find、insert函数，使其返回一个pair<iterator,bool>

map中operator的实现以及find和insert的更改

由于哈希表中的find与insert已经更改，所以我们set中的也得改

更改后的find与insert要这样使用：

3.完整代码

3.1HashTable

<code>//原模板

template<class K>

struct HashFunc

{ -- -->

size_t operator()(const K& key)

{

return key;

}

};

//特化

template<>

struct HashFunc<string>

{

size_t operator()(const string& key)

{

size_t sum = 0;

for (auto& e : key)

{

sum *= 31;//这里使用了直接地址法，避免字符串的key计算后相同

sum += e;

}

return sum;

}

};

namespace hash_bucket

{

template<class T>

struct HashNode//节点

{

T _data;//数据域

HashNode<T>* _next;//指针域

HashNode(const T& data)

:_data(data)

, _next(nullptr)

{ }

};

//前置声明

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>

class HashTable;

//迭代器

template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash = HashFunc<K>>

struct HTIterator

{

typedef HTIterator<K, T,Ref,Ptr, KeyOfT, Hash> Self;//重命名

typedef HashNode<T> Node;

HashNode<T>* _node;//指向节点的指针

const HashTable<K, T, KeyOfT, Hash>* _pt;//哈希表指针

HTIterator( Node* node, const HashTable<K,T,KeyOfT,Hash>* table)

:_node(node)

,_pt(table)

{ }

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

Self& operator++()

{

if (_node->_next)//当前桶还有元素

{

_node = _node->_next;

}

else

{

KeyOfT kot;

Hash hs;

size_t hashi = hs(kot(_node->_data)) % _pt->_table.size();

hashi++;//指向下一个桶

while (hashi < _pt->_table.size())

{

if (_pt->_table[hashi])//“下一个”桶有元素

{

break;

}

else

{

hashi++;

}

}

if (hashi == _pt->_table.size())//若后面没有桶了

{

_node = nullptr; //end()

}

else

{

_node = _pt->_table[hashi];

}

}

return *this;

}

bool operator !=(const Self& s)

{

return _node != s._node;

}

};

//哈希表

template<class K, class T,class KeyOfT,class Hash>

class HashTable

{

template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>

friend struct HTIterator;

typedef HashNode<T> Node;

public:

typedef HTIterator<K, T,T&,T*, KeyOfT, Hash> Iterator;//普通迭代器

typedef HTIterator<K, T,const T&,const T*, KeyOfT, Hash> ConstIterator;//const迭代器

Iterator begin()

{

if (_n == 0)//没有元素

return end();

else

{

for (size_t i = 0; i < _table.size(); i++)

{

if (_table[i])//找到第一个桶

{

return Iterator(_table[i], this);//使用当前节点和桶构造一个迭代器返回

}

}

}

return end();

}

Iterator end()

{

return Iterator(nullptr, this);

}

ConstIterator cbegin()const

{

if (_n == 0)//没有元素

return cend();

else

{

for (size_t i = 0; i < _table.size(); i++)

{

if (_table[i])//找到第一个桶

{

return ConstIterator(_table[i], this);//使用当前节点和桶构造一个迭代器返回

}

}

}

return cend();

}

ConstIterator cend() const

{

return ConstIterator(nullptr, this);

}

HashTable(size_t N = 10)

{

_table.resize(N,nullptr);

}

~HashTable()

{

for (size_t i = 0; i < _table.size(); i++)

{

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_table[i] = nullptr;

}

}

pair<Iterator,bool> insert(const T& data)

{

Hash hs;

KeyOfT kot;

Iterator it = find(kot(data));//如果已经存在

if ( it!= end())

{

return make_pair(it, false);

}

size_t size = _table.size();

//检查扩容

if (_n == size)//节点个数等于桶的数量时，进行扩容

{

//为了节省开销，不再重新开辟新节点，直接映射原来的节点，将原来的映射取消

vector<Node*> newtable(size * 2, nullptr);

size_t newsize = newtable.size();

for (size_t i = 0; i < size; i++)

{

Node* cur = _table[i];

while (cur)

{

size_t hashi = hs(kot(cur->_data)) % newsize;//元素对应的新表中的位置

Node* next = cur->_next;//记录当前桶的下一个元素

//头插连接到新桶

cur->_next = newtable[hashi];

newtable[hashi] = cur;

cur = next;

}

_table[i] = nullptr;

}

swap(_table, newtable);

}

size_t hashi = hs(kot(data)) % _table.size();

//头插连接

Node* newnode = new Node(data);

newnode->_next = _table[hashi];

_table[hashi] = newnode;

++_n;

return make_pair(Iterator(newnode, this), true);

}

Iterator find(const K& key)

{

Hash hs;

KeyOfT kot;

size_t hashi = hs(key) % _table.size();

Node* cur = _table[hashi];

while (cur)

{

if (kot(cur->_data) == key)

return Iterator(cur,this);

cur = cur->_next;

}

return end();

}

bool erase(const K& key)

{

Hash hs;

KeyOfT kot;

size_t hashi = hs(key) % _table.size();

Node* cur = _table[hashi];

Node* prev = nullptr;

while (cur)

{

if (kot(cur->_data) == key)

{

if (prev == nullptr)//桶中只有一个元素

{

_table[hashi] = nullptr;

}

else

{

prev->_next = cur->_next;

}

delete cur;

_n--;

return true;

}

else

{

prev = cur;

cur = cur->_next;

}

}

return false;

}

private:

vector<Node*> _table;

size_t _n;

};

}

3.2unordered_set

namespace my

{

template<class K,class Hash = HashFunc<K>>

class unordered_set

{

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

typedef typename hash_bucket::HashTable<K,const K,SetKeyOfT, Hash>::Iterator iterator;

typedef typename hash_bucket::HashTable<K,const K,SetKeyOfT, Hash>::ConstIterator const_iterator;

const_iterator cbegin() const

{

return _ht.cbegin();

}

const_iterator cend() const

{

return _ht.cend();

}

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

pair<iterator,bool> insert(const K& key)

{

return _ht.insert(key);

}

iterator find(const K& key)

{

return _ht.find(key);

}

bool erase(const K& key)

{

return _ht.erase(key);

}

private:

hash_bucket::HashTable<K, const K,SetKeyOfT, Hash> _ht;

};

}

3.3unordered_map

namespace my

{

template<class K, class V,class Hash = HashFunc<K>>

class unordered_map

{

struct MapKeyOfT

{

const K& operator()(const pair< K,V>& kv)

{

return kv.first;

}

};

public:

typedef typename hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash>::Iterator iterator;

typedef typename hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

const_iterator cbegin()const

{

return _ht.cbegin();

}

const_iterator cend()const

{

return _ht.cend();

}

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

V& operator[](const K& key)

{

pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));

//将其对应的值返回

//如果插入前已经存在，则返回其值；否则则返回一个V()

return ret.first->second;

}

pair<iterator,bool> insert(const 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);

}

private:

hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash> _ht;

};

}