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

STL map तथा multimap¶

map/multimap का अंतर्निहित स्ट्रक्चर rb_tree है, इसीलिए इनमें एलिमेंट्स स्वतः क्रमबद्ध होते हैं; क्रमबद्ध करने का आधार key है।

map/multimap "traversal" ऑपरेशन तथा iterators प्रदान करते हैं। सामान्य नियम (++iter) से पार करने पर क्रमबद्ध अवस्था प्राप्त होती है।

हम map/multimap के iterators से एलिमेंट की key नहीं बदल सकते (क्योंकि key के अपने कठोर क्रम-नियम हैं), परंतु उससे एलिमेंट का data बदल सकते हैं। इसीलिए map/multimap आंतरिक रूप से उपयोगकर्ता द्वारा निर्दिष्ट key type को स्वतः const सेट कर देते हैं, जिससे उपयोगकर्ता एलिमेंट की key को मान देने से रुक जाता है।

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

इस अनुभाग में हम निम्नलिखित विषयों पर चर्चा करेंगे:

map की key ही key है, value है key+data — यह set से भिन्न है, जिसमें key ही value है और value ही key।
map की key अपरिवर्तनीय है; map तथा multimap के इंसर्शन कॉल फंक्शन्स भिन्न हैं, जिससे उनकी key का value से संबंध प्रभावित होता है।
initializer_list का उपयोग
map में [] ऑपरेटर है, जबकि multimap में [] ऑपरेटर नहीं है।

1.map¶

key ही key है, value है key+data

नीचे map में हम देख सकते हैं कि value_type एक pair है।

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map
{
public:
    typedef _Key                                          key_type;
    typedef _Tp                                           mapped_type;
    typedef std::pair<const _Key, _Tp>                    value_type;
    typedef _Compare                                      key_compare;
    typedef _Alloc                                        allocator_type;
private:
    // key为key,value为key+data
    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
            key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;
};

उपरोक्त डिफ़ॉल्ट फंक्टर _Select1st है; stl_function में हमें इसका सोर्स कोड इस प्रकार मिलता है:

template<typename _Pair>
struct _Select1st
: public unary_function<_Pair, typename _Pair::first_type>
{
    typename _Pair::first_type&
    operator()(_Pair& __x) const
    { return __x.first; }
};

देखा कि उपरोक्त _Select1st एक struct है — फिर इसे फंक्टर कैसे कह सकते हैं? क्योंकि इसके भीतर () ऑपरेटर ओवरलोड किया गया है, हहा~

अब हम स्वयं एक कार्यान्वित करते हैं:

template<typename _T1>
struct mySelect1st
        : public unary_function<_T1, typename _T1::first_type>
{
    template<typename _T2>
    typename _T2::first_type&
    operator()(_T2& __x) const
    { return __x.first; }
};
int main() {
     typedef pair<const int,int> value_type;
    _Rb_tree<int, value_type, mySelect1st<value_type>, less<int>> it;
    it._M_insert_unique(make_pair(1,3));
    it._M_insert_unique(make_pair(3,6));
    for(auto each:it)
        cout<<each.first<<" "<<each.second<<endl;
}

key नहीं बदली जा सकती, data बदला जा सकता है

उपरोक्त सोर्स कोड में: key के लिए स्वतः एक const जोड़ा गया है, इसीलिए key नहीं बदली जा सकती।

typedef std::pair<const _Key, _Tp>                    value_type;

2.insert¶

insert में _M_insert_unique अपनाया गया है

insert के कुछ तरीके:

(1) pair इंसर्ट करना

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

map के भीतर

(2) निर्दिष्ट स्थिति पर pair इंसर्ट करना

iterator insert(iterator __position, const value_type& __x)
{ return _M_t._M_insert_equal_(__position, __x); }

(3) एक रेंज से इंसर्शन

template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_t._M_insert_equal(__first, __last); }

(4) list से इंसर्शन

void
insert(initializer_list<value_type> __l)
{ this->insert(__l.begin(), __l.end()); }

अंतिम insert में एक initializer_list है — एक उदाहरण से आप समझ जाएँगे।

3.initializer_list का उपयोग¶

वास्तविक प्रोग्रामिंग अभ्यास

vector<int> v={1,2,3};   // 底层调用vector的构造函数
v={2,5,6};               // 底层调用vector的=操作符
initializer_list<int> ll={4,5,6};
v.insert(v.begin(),ll);  // 底层调用下面insert函数
for(auto x:v) cout<<x<<" ";
cout<<endl;
vector<int> vv(ll);      // 底层调用vector的构造函数
vector<string> city{"Berlin", "New York", "London", "Cairo","Tokyo", "Cologne"};

इस vector आरंभीकरण से सभी भली-भाँति परिचित हैं — ऐसा आरंभीकरण कैसे संभव है? vector का सोर्स कोड देखिए:

 vector&
operator=(initializer_list<value_type> __l)
{
    this->assign(__l.begin(), __l.end());
    return *this;
}

iterator
insert(const_iterator __position, initializer_list<value_type> __l)
{ return this->insert(__position, __l.begin(), __l.end()); }

vector(initializer_list<value_type> __l,
const allocator_type& __a = allocator_type())
: _Base(__a)
{
_M_range_initialize(__l.begin(), __l.end(),
    random_access_iterator_tag());
}

क्योंकि उसके कंस्ट्रक्टर में पैरामीटर के रूप में एक initializer_list है, इसीलिए हम इसे map पर भी उपयोग कर सकते हैं। परंतु map में ऐसा कोई समतुल्य कंस्ट्रक्टर नहीं — यह भी map के कंस्ट्रक्टर, insert तथा = पर लागू होता है; ऊपर की तरह ही तीन जगह, हहा~

initializer_list के उपयोग की तीन जगहें:

// map构造
map(initializer_list<value_type> __l, const allocator_type& __a)
: _M_t(_Compare(), _Pair_alloc_type(__a))
{ _M_t._M_insert_unique(__l.begin(), __l.end()); }
// =操作符重载
map&
operator=(initializer_list<value_type> __l)
{
    this->clear();
    this->insert(__l.begin(), __l.end());
    return *this;
}
// insert插入
void
insert(std::initializer_list<value_type> __list)
{ insert(__list.begin(), __list.end()); }

वास्तविक प्रोग्रामिंग अभ्यास

map में initializer_list का उपयोग (set में भी वैसा ही):

// 这里要注意，pair的first参数必[须是const
initializer_list<pair<const strin[g,int>> l = {{"hello", 1}, {"world", 2}};
map<string,int> mm(l);  // map构造函数
map<string, int> m2{{"hello", 1}, {"world", 2}}; // map构造函数
map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符
map<string, int> mp;
mp.insert(l);       // insert插入[

उपरोक्त से एक और प्रश्न उपजता है:

map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符

इन दोनों में एक कंस्ट्रक्टर क्यों कॉल होता है और दूसरा = ऑपरेटर?

आरंभीकरण के समय — परिभाषा के साथ मान देने पर — सीधे कंस्ट्रक्टर कॉल होता है; बाद में पुनः मान देने पर पहले कॉपी कंस्ट्रक्टर (जिसे कंपाइलर ऑप्टिमाइज़ कर सकता है) और फिर = ऑपरेटर कॉल होता है।

उदाहरण का विश्लेषण

नीचे एक ठोस उदाहरण से विश्लेषण करते हैं:

template <typename _Tp>
class Foo
{
public:
    Foo(initializer_list<_Tp> &list)
    {
        cout << "Foo(initializer_list<_Tp> &list)"<< endl;
    }

    Foo(int)
    {
        cout << "Foo(int )"<< endl;
    }

    Foo(const Foo& f)
    {
        cout << "调用了拷贝构造函数"<< endl;
    }
    Foo& operator=(initializer_list<_Tp> __l)
    {
        cout<<"调用了=操作符重载"<<endl;
        return *this;
    }

};

कॉल:

Foo<int> foo=ll;
foo={1,2};

कंपाइलर ऑप्टिमाइज़ेशन के बिना परिणाम:

Foo(initializer_list<_Tp> &list)
调用了=操作符重载

हम कंपाइलर ऑप्टिमाइज़ेशन अक्षम करके: g++ -o rb rbtree.cpp -std=c++11 -fno-elide-constructors

Foo(initializer_list<_Tp> &list)
调用了拷贝构造函数
调用了=操作符重载

4.multimap¶

map की तरह ही multimap भी key संशोधित करने की अनुमति नहीं देता। परंतु इंसर्शन के लिए _M_insert_equal उपयोग होता है।

template <typename _Key, typename _Tp,
typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class multimap
{
public:                                      
    typedef std::pair<const _Key, _Tp> value_type;   
}

नीचे multimap तथा rbtree — दोनों तरीकों से अभ्यास करते हैं।

multimap<int, string> c;
c.insert(make_pair(1,"asdqw"));
c.insert(make_pair(1,"qweq"));

for(auto each:c) cout<<each.first<<" "<<each.second<<endl;

typedef pair<const int,string> valueT;
_Rb_tree<int, valueT, _Select1st<valueT>, less<int>> mulm;
mulm._M_insert_equal(make_pair(2,"abc"));
mulm._M_insert_equal(make_pair(2,"cde"));
for(auto each:mulm)
cout<<each.first<<" "<<each.second<<endl;

आउटपुट:

1 asdqw
1 qweq
2 abc
2 cde

5.map तथा multimap के महत्वपूर्ण ऑपरेटर¶

map तथा multimap का [] ऑपरेटर — map का [] ऑपरेटर map को पास किए गए दूसरे पैरामीटर को लौटाता है।

[] को एक key पास करें — यदि मिल जाए तो value, अन्यथा डिफ़ॉल्ट मान 0।

mapped_type&
operator[](const key_type& __k)
{
    iterator __i = lower_bound(__k);// 找到__k第一个。
    // __i->first is greater than or equivalent to __k.
    if (__i == end() || key_comp()(__k, (*__i).first))
    #if __cplusplus >= 201103L
    __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
                    std::tuple<const key_type&>(__k),
                    std::tuple<>());
    #else
        __i = insert(__i, value_type(__k, mapped_type()));
    #endif
    return (*__i).second;  // 返回key的value，此value为传递进map的第二个参数。
}

परंतु multimap में [] ऑपरेटर नहीं है!!!

एक बार सोचिए — multimap में एक key के संगत कई value हो सकती हैं; यदि हम [] से उस key की value लेना चाहें, तो आख़िर कौन-सी value मिलेगी? इसीलिए STL सोर्स कोड में यह ऑपरेटर ओवरलोड ही नहीं किया गया!