विषय पर बढ़ें

अंतिम अद्यतन：2026-10-12

STL unordered_map सोर्स कोड विश्लेषण

0.प्रस्तावना

पिछले अनुभाग में hashtable सीखा गया; यह अनुभाग hashtable का कंटेनर एडेप्टर है: unordered_map।

अतः अनऑर्डर्ड map का अंतर्निहित कंटेनर hashtable है।

unordered_map तथा unordered_multimap का सोर्स कोड unordered_map.h फ़ाइल में है।

1.unordered_map तथा unordered_multimap का मूल अंतर

पहले unordered_map के सोर्स कोड पर नज़र डालते हैं:

template<class _Key, class _Tp,
class _Hash = hash<_Key>,
class _Pred = std::equal_to<_Key>,
class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class unordered_map
{
    typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
    _Hashtable _M_h;
};

अंतर्निहित कंटेनर __umap_hashtable की घोषणा देखने जाते हैं:

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;

template<typename _Key,
    typename _Tp,
    typename _Hash = hash<_Key>,
    typename _Pred = std::equal_to<_Key>,
    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
    typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
_Alloc, __detail::_Select1st,
_Pred, _Hash,
__detail::_Mod_range_hashing,
__detail::_Default_ranged_hash,
__detail::_Prime_rehash_policy, _Tr>;
इससे निम्नलिखित निष्कर्ष मिलता है: hashtable के टेम्प्लेट पैरामीटर: 
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
typename _RehashPolicy, typename _Traits>
डिफ़ॉल्ट रूप से, unordered_map अपनाता है: - H1 है hash - H2 है _Mod_range_hashing - _Hash है _Default_ranged_hash - _RehashPolicy है _Prime_rehash_policy - _Traits है _Tr अंतिम _Tr बहुत महत्वपूर्ण है, क्योंकि इसी पैरामीटर के कारण unordered_multimap का अस्तित्व है। विस्तृत विश्लेषण नीचे देखिए:

_Tr इस प्रकार है:

typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
_Tr, __umap_traits का उपयोग करता है; आगे देखते हैं: 
template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
उपरोक्त दोनों की तुलना करने पर पाया जाता है कि __umap_traits के भीतर एक __cache_default श्रृंखला है। टेम्प्लेट पैरामीटर bool टाइप का है, अतः वह false है या true, प्रिंट किया जा सकता है — परीक्षण में यह false आया, अर्थात् hash code कैश नहीं होता।

template<typename _Tp, typename _Hash>
using __cache_default
=  __not_<__and_<__is_fast_hash<_Hash>,
__detail::__is_noexcept_hash<_Tp, _Hash>>>;
आगे __umap_traits देखते हैं — यह वास्तव में _Hashtable_traits को कॉल करता है; और नीचे बढ़ते हैं:

template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
struct _Hashtable_traits
{
    using __hash_cached = __bool_constant<_Cache_hash_code>;
    using __constant_iterators = __bool_constant<_Constant_iterators>;
    using __unique_keys = __bool_constant<_Unique_keys>;
};
यहाँ तीन using दिखे — इन्हें तीन typedef समझिए, जो क्रमशः दर्शाते हैं: hash code कैश होगा या नहीं, क्या इटरेटर constant है, क्या key अद्वितीय है। ऊपर वापस देखें तो पास किए गए तीन टेम्प्लेट पैरामीटर false, false, true हैं — इससे भी पुष्टि होती है कि unordered_map की key अद्वितीय है; तदनुसार unordered_multimap की key अद्वितीय नहीं होती, जिसका अंतिम पैरामीटर false है। संबंधित कोड इस प्रकार है:

/// Base types for unordered_multimap.
template<bool _Cache>
using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;

सारांश: उपरोक्त विश्लेषण से हम जान गए unordered_map तथा unordered_multimap का मूल अंतर, और यह भी पाया कि अंतर्निहित सोर्स कोड में एक ही कंटेनर से दो कंटेनर एडेप्टर कैसे कार्यान्वित किए जाते हैं!

2.unordered_set तथा unordered_multiset का मूल अंतर

विश्लेषण पहले की तरह ही है; पहले unordered_set देखिए:

template<class _Value,
    class _Hash = hash<_Value>,
    class _Pred = std::equal_to<_Value>,
    class _Alloc = std::allocator<_Value> >
class unordered_set
{
    typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
    _Hashtable _M_h;
}

template<bool _Cache>
using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;

template<typename _Value,
    typename _Hash = hash<_Value>,
    typename _Pred = std::equal_to<_Value>,
    typename _Alloc = std::allocator<_Value>,
    typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
                __detail::_Identity, _Pred, _Hash,
                __detail::_Mod_range_hashing,
                __detail::_Default_ranged_hash,
                __detail::_Prime_rehash_policy, _Tr>;
देखा जा सकता है कि _Hashtable_traits को पास होने वाले मान false, true, true हैं। unordered_set के लिए const iterator तथा अद्वितीय key उपयोग होती है; अब unordered_multiset देखिए:

template<bool _Cache>
using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
दोनों की फिर तुलना करें तो मूल भाव यह है: unordered_set key की पुनरावृत्ति (duplicate) की अनुमति नहीं देता, जबकि unordered_multiset देता है।

3.तीन प्रमुख निष्कर्ष

अब, पहले की समझ के आधार पर, उन चारों कंटेनर एडेप्टरों को क्रम से सूचीबद्ध करते हैं:

(1) unordered_map 

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
(2) unordered_multimap 
template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
(3) unordered_set

template<bool _Cache>
using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
(4) unordered_multiset

template<bool _Cache>
using __uset_traits = __detail::_Hashtable_traits<_Cache, true, false>;

तुलना के बाद, निष्कर्ष:

  • निष्कर्ष 1: unordered_map तथा unordered_set key की पुनरावृत्ति की अनुमति नहीं देते, जबकि multi वाले देते हैं;
  • निष्कर्ष 2: unordered_map तथा unordered_multimap में उपयोग होने वाला इटरेटर iterator है, जबकि unordered_set तथा unordered_multiset में const_iterator।
  • निष्कर्ष 3: unordered_map तथा unordered_multimap में key ही key है और value है key+value; जबकि unordered_set तथा unordered_multiset में key ही Value है, और Value भी Key ही है।

अंतिम निष्कर्ष की तुलना नीचे देखिए (हम hashtable को पास होने वाले पहले तथा दूसरे पैरामीटर देखते हैं):

unordered_map तथा unordered_multimap: 

using __umap_hashtable = _Hashtable<_Key, 
std::pair<const _Key, _Tp>,
_Alloc, __detail::_Select1st,
_Pred, _Hash,
__detail::_Mod_range_hashing,
__detail::_Default_ranged_hash,
__detail::_Prime_rehash_policy, _Tr>;
unordered_set तथा unordered_multiset: 
template<typename _Value,
typename _Hash = hash<_Value>,
typename _Pred = std::equal_to<_Value>,
typename _Alloc = std::allocator<_Value>,
typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
__detail::_Identity, _Pred, _Hash,
__detail::_Mod_range_hashing,
__detail::_Default_ranged_hash,
__detail::_Prime_rehash_policy, _Tr>;

4.unordered_map के महत्वपूर्ण फंक्शन्स

आरंभीकरण

नीचे के कंस्ट्रक्टर में देखा जा सकता है कि unordered_map के डिफ़ॉल्ट बकेट्स की संख्या 10 है।

unordered_map के अंतर्निहित स्तर पर डिफ़ॉल्ट रूप से hasher() अपनाया जाता है, अर्थात् H1, अर्थात् std::hash

unordered_map(size_type __n = 10,
    const hasher& __hf = hasher(),
    const key_equal& __eql = key_equal(),
    const allocator_type& __a = allocator_type())
: _M_h(__n, __hf, __eql, __a)
{ }
अब परीक्षण करते हैं कि डिफ़ॉल्ट hash ही अपनाया जाता है या नहीं:

unordered_map<string,int> um;
hash<string> h;
cout<<um.hash_function()("hhhhhawq")<<endl;
cout<<h("hhhhhawq")<<endl;
आउटपुट:

9074142923776869151
9074142923776869151
इससे और पुष्टि हुई कि डिफ़ॉल्ट hash ही उपयोग होता है।

खाली है या नहीं, आकार, अधिकतम आकार

bool
empty() const noexcept
{ return _M_h.empty(); }
///  Returns the size of the %unordered_map.
size_type
size() const noexcept
{ return _M_h.size(); }

///  Returns the maximum size of the %unordered_map.
size_type
max_size() const noexcept
{ return _M_h.max_size(); }

begin तथा end

iterator
begin() noexcept
{ return _M_h.begin(); }
iterator
end() noexcept
{ return _M_h.end(); }

insert इंसर्शन के पाँच तरीके

// value
std::pair<iterator, bool>
insert(const value_type& __x)
{ return _M_h.insert(__x); }

// pair 
std::pair<iterator, bool>
insert(_Pair&& __x)
{ return _M_h.insert(std::forward<_Pair>(__x)); }

// iterator+value
iterator
insert(const_iterator __hint, const value_type& __x)
{ return _M_h.insert(__hint, __x); }


// first到last范围插入
template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_h.insert(__first, __last); }

// 初始化列表插入

void
insert(initializer_list<value_type> __l)
{ _M_h.insert(__l); }

डिलीशन

डिलीशन के तीन तरीके

// iterator
iterator
erase(iterator __position)
{ return _M_h.erase(__position); }

// key
size_type
erase(const key_type& __x)
{ return _M_h.erase(__x); }

// first到last范围

iterator
erase(const_iterator __first, const_iterator __last)
{ return _M_h.erase(__first, __last);

सम्पूर्ण सफ़ाई (clear)

void
clear() noexcept
{ _M_h.clear(); }

hash_function

इस unordered_map का hash_function प्राप्त करना 

hasher
hash_function() const
{ return _M_h.hash_function(); }
उपयोग: 
unordered_map<string,int> um;
cout<<um.hash_function()("hhhhhawq")<<endl; //传递的内容要与上面key类型一致。

key_eq key_eq जो लौटाता है वह std::equal_to है उपयोग इस प्रकार: 

unordered_map<string,int> um;
cout<<um.key_eq()("1","2")<<endl;
खोज तथा value प्राप्त करना

iterator
find(const key_type& __x)
{ return _M_h.find(__x); }
mapped_type&
operator[](const key_type& __k)
{ return _M_h[__k]; }
mapped_type&
at(const key_type& __k)
{ return _M_h.at(__k); }
इन फंक्शन्स के अतिरिक्त बकेट प्राप्त करना, अधिकतम बकेट संख्या, लोड फैक्टर, rehash इत्यादि भी हैं — बस क्रमबद्ध करना (sorting) नहीं है, क्योंकि hashtable क्रमबद्ध करने की सुविधा प्रदान नहीं करता। hashtable में नोड की खोज, डिलीशन तथा इंसर्शन निरंतर समय (constant time) में होते हैं, जिसमें वह RB-Tree (रेड-ब्लैक ट्री) से बेहतर है।

इसी प्रकार, unordered_set, unordered_multiset तथा unordered_multimap में भी unordered_map जैसे ही फंक्शन्स हैं, इसलिए उनका विवरण नहीं दिया जाता।

संबंधित विषय

टिप्पणियाँ