|
ed long __stl_next_prime(unsigned long __n) { const unsigned long* __first = __stl_prime_list; const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes; const unsigned long* pos = lower_bound(__first, __last, __n); return pos == __last ? *(__last - 1) : *pos; } /// Forward declaration of operator==. template
class hashtable; template
bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2); /// Hashtables handle allocators a bit differently than other containers /// do. If we're using standard-conforming allocators, then a hashtable /// unconditionally has a member variable to hold its allocator, even if /// it so happens that all instances of the allocator type are identical. /// This is because, for hashtables, this extra storage is negligible. /// Additionally, a base class wouldn't serve any other purposes; it /// wouldn't, for example, simplify the exception-handling code. template
class hashtable { public: typedef _Key key_type; typedef _Val value_type; typedef _HashFcn hasher; typedef _EqualKey key_equal; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; hasher hash_funct() const { return _M_hash; } key_equal key_eq() const { return _M_equals; } private: typedef _Hashtable_node<_Val> _Node; public: typedef _Alloc allocator_type; allocator_type get_allocator() const { return allocator_type(); } private: typedef simple_alloc<_Node, _Alloc> _M_node_allocator_type; ///分配和回收桶中的一个节点 _Node* _M_get_node() { return _M_node_allocator_type::allocate(1); } void _M_put_node(_Node* __p) { _M_node_allocator_type::deallocate(__p, 1); } private: hasher _M_hash; key_equal _M_equals; _ExtractKey _M_get_key; vector<_Node*,_Alloc> _M_buckets; size_type _M_num_elements; public: typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> iterator; typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey, _Alloc> const_iterator; friend struct _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; friend struct _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; public: hashtable(size_type __n, const _HashFcn& __hf, const _EqualKey& __eql, const _ExtractKey& __ext, const allocator_type& __a = allocator_type()) : _M_hash(__hf), _M_equals(__eql), _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) { _M_initialize_buckets(__n); } hashtable(size_type __n, const _HashFcn& __hf, const _EqualKey& __eql, const allocator_type& __a = allocator_type()) :_M_hash(__hf), _M_equals(__eql), _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) { _M_initialize_buckets(__n); } hashtable(const hashtable& __ht) : _M_hash(__ht._M_hash), _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), _M_buckets(__ht.get_allocator()), _M_num_elements(0) { _M_copy_from(__ht); } hashtable& operator= (const hashtable& __ht) { if (&__ht != this) { clear(); _M_hash = __ht._M_hash; _M_equals = __ht._M_equals; _M_get_key = __ht._M_get_key; _M_copy_from(__ht); } return *this; } ~hashtable() { clear(); } size_type size() const { return _M_num_elements; } size_type max_size() const { return size_type(-1); } bool empty() const { return size() == 0; } ///STL容器自身的swap成员函数一般都比较高效,HashTable也不例外 void swap(hashtable& __ht) { __STD::swap(_M_hash, __ht._M_hash); __STD::swap(_M_equals, __ht._M_equals); __STD::swap(_M_get_key, __ht._M_get_key); _M_buckets.swap(__ht._M_buckets); __STD::swap(_M_num_elements, __ht._M_num_elements); } iterato |