विषय पर बढ़ें

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

STL set तथा multiset

set/multiset का अंतर्निहित स्ट्रक्चर rb_tree है, इसीलिए इनमें एलिमेंट्स का स्वतः क्रमबद्ध होने का गुण होता है। क्रमबद्ध करने का आधार key है, जबकि set/multiset के एलिमेंट्स में value तथा key एक ही हैं: value ही key है।

हम set/multiset के iterators से एलिमेंट का मान नहीं बदल सकते (क्योंकि key के अपने कठोर क्रम-नियम होते हैं)। set/multiset का iterator उसके अंतर्निहित RB tree का const-iterator ही है — इसका उद्देश्य उपयोगकर्ता को एलिमेंट को मान देने (assign) से रोकना है।

set के एलिमेंट की key अद्वितीय होनी चाहिए, इसलिए उसका insert rb_tree के _M_insert_unique() का उपयोग करता है; जबकि multiset के एलिमेंट की key दोहराई जा सकती है, इसलिए उसका insert rb_tree के _M_insert_equal() का उपयोग करता है।

1.set

set का सोर्स कोड अपेक्षाकृत सरल है, इसलिए नीचे के कुछ प्रश्नों से शुरुआत करते हैं।

पहला प्रश्न: key ही value है, value भी key ही है।

विशिष्ट कोड दूसरे प्रश्न में मिलेगा; यहाँ हम आम तौर पर कोड लिखने के बाद का आंतरिक तर्क देते हैं — इसमें एक रेड-ब्लैक ट्री दिखता है, और रेड-ब्लैक ट्री की परिभाषा में key तथा value एक ही हैं, इसीलिए यह प्रश्न उत्तरित हुआ। (सोर्स कोड में typedef सभी key से आते हैं)।

template<typename _Key, typename _Compare = std::less<_Key>,
    typename _Alloc = std::allocator<_Key> >
class set
{
    // concept requirements
    typedef typename _Alloc::value_type                   _Alloc_value_type;

public:
    // typedefs:
    //@{
    /// Public typedefs.
    typedef _Key     key_type;
    typedef _Key     value_type; // value也是key
    typedef _Compare key_compare;
    typedef _Compare value_compare;
    typedef _Alloc   allocator_type;
    //@}

private:

    typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
            key_compare, _Key_alloc_type> _Rep_type;
    _Rep_type _M_t;  // Red-black tree representing set.
};

set_key.png

दूसरा प्रश्न: इटरेटर से एलिमेंट का मान नहीं बदला जा सकता।

इटरेटर से एलिमेंट का मान क्यों नहीं बदला जा सकता — आगे का इटरेटर देखिए, सब जगह const_iterator ही उपयोग हुआ है, इसीलिए दूसरा प्रश्न भी उत्तरित हुआ।

template<typename _Key, typename _Compare = std::less<_Key>,
    typename _Alloc = std::allocator<_Key> >
class set
{
private:

    typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
            key_compare, _Key_alloc_type> _Rep_type;
    _Rep_type _M_t;  // Red-black tree representing set.

public:
    typedef typename _Rep_type::const_iterator            iterator;
    typedef typename _Rep_type::const_iterator            const_iterator;
    typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
    typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
};

पिछले विश्लेषण से हमें queue, priority_queue, stack का स्मरण होता है — ये सभी अंतर्निहित कंटेनर का उपयोग करते हैं, इसीलिए कंटेनर एडेप्टर कहलाते हैं; और set भी अंतर्निहित कंटेनर का उपयोग करता है, इसलिए वह भी container adapter यानी कंटेनर एडेप्टर कहला सकता है।

तीसरा प्रश्न: इंसर्शन में key अद्वितीय होती है।

अंतर्निहित स्तर पर _M_insert_unique कॉल होता है। 

template<typename _InputIterator>
set(_InputIterator __first, _InputIterator __last)
: _M_t()
{ _M_t._M_insert_unique(__first, __last); }

आइए इस फंक्शन के कार्यान्वयन पर संक्षेप में नज़र डालें: नीचे _M_get_insert_unique_pos जो लौटाता है वह एक pair है — यदि इंसर्ट की गई key पहले से मौजूद हो तो pair का second 0 होता है; 0 होने या न होने से key के दोहराए जाने का निर्णय होता है। नीचे के कोड की जाँच में, जब second 0 नहीं है — अर्थात् दोहराव नहीं है — तो सीधे इंसर्ट किया जा सकता है, और तब second के true वाला pair बनाया जाता है; अन्यथा second के false वाला।

template<typename _Key, typename _Val, typename _KeyOfValue,
     typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
template<typename _Arg>
#endif
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
               _Compare, _Alloc>::iterator, bool>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_insert_unique( _Arg && __v )

{
    typedef pair<iterator, bool> _Res;
    pair<_Base_ptr, _Base_ptr> __res
        = _M_get_insert_unique_pos( _KeyOfValue() ( __v ) );

    if ( __res.second )
        return(_Res( _M_insert_( __res.first, __res.second,
                     _GLIBCXX_FORWARD( _Arg, __v ) ),
                 true ) );

    return(_Res( iterator( static_cast<_Link_type>(__res.first) ), false ) );
}

अब ऊपर उल्लिखित फंक्शन देखते हैं: 

template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,typename _Rb_tree<_Key, _Val, _KeyOfValue,Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_unique_pos(const key_type& __k)
{
    // typedef pair
    typedef pair<_Base_ptr, _Base_ptr> _Res;
    // _x表示当前节点,_y表示_x的父节点
    _Link_type __x = _M_begin();
    _Link_type __y = _M_end();
    bool __comp = true;

    // 寻找插入点
    while (__x != 0)
    {
        __y = __x;
        // __k<__x是否为true
        __comp = _M_impl._M_key_compare(__k, _S_key(__x));
        // __k<__x就往左孩子查找，否则右孩子查找
        __x = __comp ? _S_left(__x) : _S_right(__x);
    }
    iterator __j = iterator(__y);
    // __k<__y，往__y的左孩子插入节点即可，不是做插入，是找到位置即可。
    if (__comp)
    {
        // 特殊位置
        if (__j == begin())
        return _Res(__x, __y);
        else
        --__j;  // 左孩子 这里调用了--操作符
    }
    // __j<__k，返回当前节(__x=0)点与父节点
    if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
        return _Res(__x, __y);
    // _j>=__k,插入失败
    return _Res(__j._M_node, 0);
}

उपरोक्त pair के उपयोग ने मुझे एक बात सिखाई — कि इसे ऐसे भी इस्तेमाल किया जा सकता है! तो आइए सीखें: 

cout<<"flag: "<<itree._M_insert_unique(5).second<<endl;  // 学习返回值
typedef pair<int ,bool> _Res;    // 也来用一下typedef后的pair
cout<<_Res(1,true).first<<endl;  // 直接包裹
_Res r=make_pair(2,false);    // 定义新对象
cout<<r.first<<endl;   // 输出结果

2.multiset

इसी प्रकार, multiset की परिभाषा set जैसी ही है; अंतर इतना है कि इंसर्शन के लिए दूसरा फंक्शन उपयोग होता है — इसी से वह दोहराई जाने वाली key का इंसर्शन कर पाता है!

 template<typename _InputIterator>
multiset(_InputIterator __first, _InputIterator __last)
: _M_t()
{ _M_t._M_insert_equal(__first, __last); }
अब _M_insert_equal का विश्लेषण करते हैं:

typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_insert_equal(_Arg&& __v)
{
    pair<_Base_ptr, _Base_ptr> __res = _M_get_insert_equal_pos(_KeyOfValue()(__v));
    return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
}

हम उपरोक्त _M_get_insert_equal_pos फंक्शन का आगे पीछा करते हैं:

template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_equal_pos(const key_type& __k)
{
    typedef pair<_Base_ptr, _Base_ptr> _Res;
    _Link_type __x = _M_begin();
    _Link_type __y = _M_end();
    while (__x != 0)
    {
        __y = __x;
        __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
            _S_left(__x) : _S_right(__x);
    }
    return _Res(__x, __y);
}
multiset तथा set के इन फंक्शन्स की तुलना करने पर पाया कि लौटाए गए pair में स्पष्ट अंतर है — पहले वाले set को अंततः इंसर्शन सफल हुआ या नहीं, यह लौटाना आवश्यक था, क्योंकि key दोहराई नहीं जा सकती; जबकि multiset को इंसर्शन की सफलता लौटाने की आवश्यकता नहीं, इसलिए उसके pair में bool टाइप नहीं होता — वह सीधे इंसर्शन बिंदु से बना pair लौटा देता है। इसीलिए, पहले की तुलना में, आपकी कितनी भी key हों, कितना भी दोहराव हो, सब इंसर्ट हो सकती हैं।

संबंधित विषय

टिप्पणियाँ