std:unorder_hash地图分析

std::unorder_hashmap分析

VS2010下是基于桶实现的；

下面就以operator []来看；

mapped_type & operator []( key_type&& _Keyval )

{ // find element matching _Keyval or insert with default mapped

iterator _Where = this-> lower_bound (_Keyval );

if (_Where == this-> end ())

_Where = this -> insert(

_STD pair < key_type, mapped_type >(

_STD move ( _Keyval),

mapped_type ())).first ;

return ((*_Where ). second);

}

先要根据key获取key可能所在的bucket：

iterator lower_bound ( const key_type & _Keyval )

{ // find leftmost not less than _Keyval in mutable hash table

size_type _Bucket = _Hashval( _Keyval );

for (iterator _Where = _Begin (_Bucket );

_Where != _End ( _Bucket); ++ _Where )

if (!this -> comp( this ->_Kfn (* _Where), _Keyval ))

return (this -> comp( _Keyval ,

this ->_Kfn (* _Where)) ? end () : _Where );

return (end ());

}

_Hashval获得所在的桶，里面会根据hashfun得出hashval并与桶的个数做与运算得到所在的桶；

然后遍历桶里的元素，桶其实是一个vector，comp这个比较函数，如果相等返回false，所以如果查到就返回_Where，查不到就返回end();

如果查找到不为空的话，就返回迭代器的val引用；

如果查找不到，就插入：插入的时候还用的move，暂时木有搞明白move语意的意义，下篇博文再分析下。

unordered_map的find方法是之前分析过的，因为[]的时候先会查找，都是用了lower_bound函数。

另外hashfun比较简单就不再分析了。