S T L 哈希算法详细剖析 1
由于太长，所以只剖析了一半，而且帖子也不允许贴超过10000个字符，所以只有分段贴。stl_hash_map.h
DarkSpy 2002/5/15
[code]
/*
* Copyright (c) 1996
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_HASH_MAP_H
#define __SGI_STL_INTERNAL_HASH_MAP_H
#include <concept_checks.h>
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#pragma set woff 1375
#endif
// Forward declaration of equality operator; needed for friend declaration.
template <class _Key, class _Tp,
class _HashFcn __STL_DEPENDENT_DEFAULT_TMPL(hash<_Key>),
class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Key>),
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map;
//__STL_DEPENDENT_DEFAULT_TMPL 是一个宏，意思是如果编译器不支持默认模板参数，则使用上一级模板参数
//__STL_DEFAULT_ALLOCATOR 等于 allocator <T>
//equal_to 的定义可以在 stl_function.h 找到
/*template <class _Tp>
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
//重载 (), 传回 _Tp 类型相等信息，相当于这样的更直观的代码:
// bool operator==(const _Tp &x, const _Tp &y) const
{ return x == y; }
};
这段定义相当于:
template <class _Key, class _Tp,
class _HashFcn = hash<_Key>,
class _EqualKey = equal_to<_Key>,
class _Alloc = allocator<_Tp> >
class hash_map;
前置类型定义
*/
template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
class _Alloc>
class hash_map
{
// requirements:
__STL_CLASS_REQUIRES(_Key, _Assignable);
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_UNARY_FUNCTION_CHECK(_HashFcn, size_t, _Key);
__STL_CLASS_BINARY_FUNCTION_CHECK(_EqualKey, bool, _Key, _Key);
/*
__STL_CLASS_REQUIRES 是一个宏，将第一句展开之后相当于
typedef void (* __func_Key_Assignable) ( _Key );
template <__func_Key_Assignable _Tp1>
struct __dummy_struct__Key_Assignable { };
static __dummy_struct__Key_Assignable< _Assignable_specification <Assignable>::_Key_requirement_violation> __dummy_ptr__Key_Assignable
__STL_CLASS_UNARY_FUNCTION_CHECK 是一个宏，将第三句展开之后相当于
typedef size_t (* __f__HashFcn_size_t_Key_unary_check)( _HashFcn&, const _Key& );
template <__f__HashFcn_size_t_Key_unary_check _Tp1>
struct __dummy_struct__HashFcn_size_t_Key_unary_check { };
static __dummy_struct__HashFcn_size_t_Key_unary_check< _STL_UNARY_FUNCTION_ERROR< _HashFcn, size_t, _Key>::__unary_function_requirement_violation>
__dummy_ptr__HashFcn_size_t_Key_unary_check
__STL_CLASS_BINARY_FUNCTION_CHECK 是一个宏，将第四句展开后相当于
typedef bool (* __f__EqualKey_bool_Key_Key_binary_check)( _EqualKey&, const _Key&, const _Key& );
template <__f__EqualKey_bool_Key_Key_binary_check _Tp1>
struct __dummy_struct__EqualKey_bool_Key_Key_binary_check { };
static __dummy_struct__EqualKey_bool_Key_Key_binary_check< _STL_BINARY_FUNCTION_ERROR<_EqualKey, bool, _Key, _Key>::__binary_function_requirement_violation>
__dummy_ptr__EqualKey_bool_Key_Key_binary_check
用很简洁的手法定义了模板内模板，是不是非常漂亮呢？
*/
.............略，待下回分解。:-)
[/code] 接下来，如果要看下面的代码，必须先知道 pair 模板类的细节，下面是 DarkSpy 对于 pair 模板类的剖析
DarkSpy 2002/5/16
[code]
/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_PAIR_H
#define __SGI_STL_INTERNAL_PAIR_H
__STL_BEGIN_NAMESPACE
template <class _T1, class _T2>
struct pair {
typedef _T1 first_type;
typedef _T2 second_type;
_T1 first;
_T2 second;
pair() : first(_T1()), second(_T2()) {} //将first 和 second 对象构造起来并初始化
pair(const _T1& __a, const _T2& __b) : first(__a), second(__b) {}
//拷贝构造，如果这样写pair<T1_Type, T2_Type> pair_object(T1, T2); 则保证构造
#ifdef __STL_MEMBER_TEMPLATES //如果编译器支持成员内模板，则
template <class _U1, class _U2>
pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
//拷贝构造，成员内模板，保证 first 和 second 能根据 pair 构造起来.
#endif
};
template <class _T1, class _T2>
inline bool operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{
return __x.first == __y.first && __x.second == __y.second;
} //重载==，返回 x 参数和 y 参数的两个模板参数相等.
template <class _T1, class _T2>
inline bool operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{
return __x.first < __y.first ||
(!(__y.first < __x.first) && __x.second < __y.second);
} //重载 <，返回 x 参数和 y 参数的两个模板参数小于判断
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
//如果编译器支持成员内模板局部特例化（偏特化）
template <class _T1, class _T2>
inline bool operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) {
return !(__x == __y);
} //重载!=，返回 _x 和 _y 参数 != 判断
template <class _T1, class _T2>
inline bool operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) {
return __y < __x;
} //重载 >，返回 _x > _y 判断
template <class _T1, class _T2>
inline bool operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) {
return !(__y < __x);
} //重载 <=，返回 _x < _y 判断
template <class _T1, class _T2>
inline bool operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) {
return !(__x < __y);
} //重载 >=，返回 _x > _y 判断
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
template <class _T1, class _T2>
inline pair<_T1, _T2> make_pair(const _T1& __x, const _T2& __y)
{
return pair<_T1, _T2>(__x, __y);
} //make_pair相当于利用 pair 的拷贝构造，构造并初始化出 _x 和 _y
//相当于这样写 pair<T1_Type, T2_Type> p_object(T1, T2);
//而用make_pair就可以直接这样写 make_pair(T1, T2);
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_PAIR_H */
// Local Variables:
// mode:C++
// End:
[/code]
页:
[1]