सहयोगी कंटेनर

कंप्यूटिंग में, सहयोगी कंटेनर C++ प्रोग्रामिंग भाषा के C++ मानक पुस्तकालय में वर्ग टेम्पलेट्स के समूह को संदर्भित करता है जो ऑर्डड ऍसोसियेटिव ऐरे को कार्यान्वित करता है। टेम्प्लेट (प्रोग्रामिंग) के कारण उनका उपयोग आर्बिटरी तत्वों जैसे इन्टिजर अथवा कस्टम क्लासेज को संग्रहीत करने के लिए किया जा सकता है। निम्नलिखित कंटेनरों को सी ++ मानक के वर्तमान संशोधन में परिभाषित किया गया है- set, map, multiset, multimap. इनमें से प्रत्येक कंटेनर मात्र उनके तत्वों पर रखी गई बाधाओं पर भिन्न होता है।

सहयोगी कंटेनर सी ++ मानक पुस्तकालय में अनऑर्डड ऍसोसियेटिव कंटेनर (सी ++) के समान होते हैं, मात्र अंतर यह है कि उनके नाम के रूप में अनऑर्डड ऍसोसियेटिव कंटेनर उनके तत्वों को व्यवस्थित नहीं करते हैं।

डिजाइन

विशेषताएं

• कुंजी की विशिष्टता- map और set में प्रत्येक कुंजी अद्वितीय होनी चाहिए। multimap और multiset पर यह प्रतिबंध नहीं होता है।
• एलिमेंट संघटन- map और multimap में प्रत्येक तत्व कुंजी और मैप किए गए मान से बने है। set और multiset में प्रत्येक तत्व कुंजी है; मैप किए गए मान नहीं हैं।
• एलिमेंट ऑर्डरिंग- एलिमेंट स्ट्रिक्ट वीक ऑर्डरिंग का पालन करते हैं

सहयोगी कंटेनरों को अनुक्रम कंटेनरों के विपरीत उनकी कुंजी द्वारा विशेष रूप से इसके एलिमेंट्स को एक्सेस करने के लिए डिज़ाइन किया गया है, जो तत्वों को उनकी स्थिति से एक्सेस करने में अधिक कुशल हैं। सहयोगी कंटेनरों को प्रविष्टि, विलोपन और परीक्षण के संचालन का आश्वासन दिया जाता है कि लॉगरिदमिक समय - ओ (लॉग एन) में कोई तत्व है अथवा नहीं है। इस प्रकार वे सामान्यतः सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग करके कार्यान्वित किए जाते हैं और द्विदिश पुनरावृत्ति का समर्थन करते हैं। इटरेटर्स और इरेज किये गए तत्वों के रिफरेन्सेस को छोड़कर, इन्सर्ट और इरेज के संचालन से इटरेटर और रिफरेन्स (सी ++) अमान्य नहीं होते हैं। सहयोगी कंटेनरों की परिभाषित विशेषता यह है कि तत्वों को पूर्व-निर्धारित क्रम में इन्सर्ट किया जाता है, जैसे सॉर्टेड असेंडिंग में इन्सर्ट किया जाता है।

सहयोगी कंटेनरों को दो उपसमूहों मैप और सेट में विभाजित किया जा सकता है। मैप को कभी-कभी डिक्शनरी के रूप में संदर्भित किया जाता है जिसमें की/ वैल्यू पेअर होते है। अनुक्रम को व्यवस्थित करने के लिए कुंजी का उपयोग किया जाता है और मान उस कुंजी से एसोसिएट होता है। सेट मात्र अद्वितीय तत्वों का आरोही कंटेनर होता है।

map और set मात्र कुंजी या तत्व के 1 उदाहरण को कंटेनर में इन्सर्ट करने की अनुमति प्रदान करते हैं। यदि तत्वों के एकाधिक उदाहरणों की आवश्यकता होती है तो multimap या multiset का उपयोग किया जाता है।

मैप और सेट दोनों द्विदिश इटरेटर्स का समर्थन करते हैं। इटरेटर्स के संबंध में अधिक जानकारी के लिए, इटरेटर्स देखें।

यद्यपि सामान्यतः एसटीएल मानक hash_map और hash_set का अंश नहीं है, सामान्यतः अन्वेषण समय सुधार के लिए उपयोग किया जाता है। ये कंटेनर अपने तत्वों को हैश तालिका के रूप में संग्रहीत करते हैं, प्रत्येक तालिका प्रविष्टि में तत्वों की द्विदिश लिंक्ड सूची होती है। अधिक तीव्र सर्च टाइम (O(1)) के लिए सुनिश्चित करें कि आपके तत्वों के लिए हैशिंग एल्गोरिथ्म समान रूप से वितरित हैश मान रिटर्न करता है।

प्रदर्शन

See also: बिग ओ नोटेशन and टाइम कम्प्लेक्सिटी

सहयोगी कंटेनरों पर प्रयुक्त किये जाने संचालन की एसिम्प्टोटिक कम्प्लेक्सिटी इस प्रकार है-

आपरेशन	कम्प्लेक्सिटी
एलिमेंट को सर्च करना	O(log n)
नए एलिमेंट को इन्सर्ट करना	O(log n)
इटरेटर को इंक्रीमेंट/डेक्रीमेंट करना	O(log n) (amortized O(1) if only increments or only decrements are done)
एलिमेंट को रिमूव करना	O(log n)

कार्यों का अवलोकन

कंटेनरों को हेडर में डिफाइन किया जाता है, उदाहरण के लिए set को हेडर <set> में डिफाइन किया गया है। सभी कंटेनर कांसेप्ट (जेनेरिक प्रोग्रामिंग) की आवश्यकताओं को पूर्ण करते हैं, जिसका अर्थ है कि उनके निकट begin(), end(), size(), max_size(), empty(), और swap() विधियाँ हैं।

	set	map	multiset	multimap	विवरण
	(constructor)	(constructor)	(constructor)	(constructor)	विभिन्न स्रोतों से कंटेनर का निर्माण करता है।
	(destructor)	(destructor)	(destructor)	(destructor)	सेट और निहित एलिमेंट्स को नष्ट कर देता है।
	operator=	operator=	operator=	operator=	कंटेनर को वैल्यू असाइन करता है।
	get_allocator	get_allocator	get_allocator	get_allocator	एलिमेंट्स को मेमोरी एलोकेट करने के लिए प्रयुक्त एलोकेटर रिटर्न करता है।
एलिमेंट एक्सेस	—	at	—	—	बाउंड चेकिंग के साथ निर्दिष्ट एलिमेंट्स को एक्सेस करता है।
	—	operator[]	—	—	बाउंड चेकिंग के अतिरिक्त निर्दिष्ट एलिमेंट्स को एक्सेस करता है।
इटरेटर	begin	begin	begin	begin	कंटेनर के प्रारम्भ में इटरेटर रिटर्न करता है।
	end	end	end	end	कंटेनर के अंत में इटरेटर रिटर्न करता है।
	rbegin	rbegin	rbegin	rbegin	कंटेनर की रिवर्स बिगनिंग के लिए रिवर्स इटरेटर रिटर्न करता है।
	rend	rend	rend	rend	कंटेनर के रिवर्स अंत के लिए रिवर्स इटरेटर रिटर्न करता है।
क्षमता	empty	empty	empty	empty	चेक करता है कि क्या कंटेनर रिक्त है।
	size	size	size	size	कंटेनर में एलिमेंट्स की संख्या रिटर्न करता है।
	max_size	max_size	max_size	max_size	class="wikitable"	कंटेनर में एलिमेंट्स की अधिकतम संभव संख्या रिटर्न करता है।

|- ! rowspan=6 | संशोधक | clear | clear | clear | clear | कंटेंट्स को क्लियर करता है।. |- | insert | insert | insert | insert | एलिमेंट्स को इन्सर्ट करता है। |- | emplace | emplace | emplace | emplace | Constructs elements in-place (C++11) |- | emplace_hint | emplace_hint | emplace_hint | emplace_hint | Constructs elements in-place using a hint (C++11) |- | erase | erase | erase | erase | एलिमेंट्स को इरेज करता है। |- | swap | swap | swap | swap | कंटेंट्स को दूसरे कंटेनर से स्वैप करता है। |- ! rowspan=5 | लुकउप | count | count | count | count | विशिष्ट कुंजी से युग्मित होने वाले एलिमेंट्स की संख्या रिटर्न करता है। |- | find | find | find | find | {| class="wikitable" |विशिष्ट कुंजी के साथ एलिमेंट को फाइंड करता है। |} |- | equal_range | equal_range | equal_range | equal_range | विशिष्ट कुंजी से युग्मित होने वाले एलिमेंट्स की श्रेणी रिटर्न करता है। |- | lower_bound | lower_bound | lower_bound | lower_bound | Returns an iterator to the first element with a key not less than the given value. |- | upper_bound | upper_bound | upper_bound | upper_bound | Returns an iterator to the first element with a key greater than a certain value. |- ! rowspan=2 | प्रेक्षक | key_comp | key_comp | key_comp | key_comp | Returns the key comparison function. |- | value_comp | value_comp | value_comp | value_comp | की कम्पेरिज़न फ़ंक्शन रिटर्न करता है। set और multiset में यह फ़ंक्शन key_comp के समतुल्य है, क्योंकि एलिमेंट केवल कुंजी से बने होते हैं। |}

उपयोग

निम्नलिखित कोड दर्शाता है कि map<string, int> का उपयोग किस प्रकार उपयोग करना है। यह शब्द को कुंजी के रूप में और वैल्यू के रूप में काउंट का उपयोग करता है।

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> wordcounts;
    std::string s;

    while (std::cin >> s && s != "end")
    {
        ++wordcounts[s];
    }
    
    while (std::cin >> s && s != "end")
    {
        std::cout << s << ' ' << wordcounts[s] << '\n';
    }
    
    return 0;
}

जब निष्पादित प्रोग्राम यूजर को स्पेस द्वारा पृथक शब्दों की श्रृंखला को टाइप करने देता है और इनपुट समापन को दर्शाने के लिए शब्द "एन्ड" का प्रयोग करता है। तब यूजर शब्द इनपुट कर सकता है।

उपरोक्त उदाहरण यह भी दर्शाता है कि यदि कुंजी के साथ कोई एसोसिएट नहीं है तो ऑपरेटर [] मैप में नए ऑब्जेक्ट्स को (डिफ़ॉल्ट निर्माता का उपयोग करके) इन्सर्ट करता है। तो इंटीग्रल टाइप्स शून्य-प्रारंभिक होते हैं जो स्ट्रिंग्स को एम्प्टी स्ट्रिंग्स आदि में प्रारंभ करते हैं।

निम्नलिखित उदाहरण इन्सर्ट फ़ंक्शन का उपयोग करके मैप में एलिमेंट्स को इन्सर्ट करता है और मैप इटरेटर एवं फाइंड फ़ंक्शन का उपयोग करके कुंजी को शोधित करता है-

#include <iostream>
#include <map>
#include <utility> // To use make_pair function

int main()
{
    typedef std::map<char, int> MapType;
    MapType my_map;

    // Insert elements using insert function
    my_map.insert(std::pair<char, int>('a', 1));
    my_map.insert(std::pair<char, int>('b', 2));
    my_map.insert(std::pair<char, int>('c', 3));
    
    // You can also insert elements in a different way like shown below
    // Using function value_type that is provided by all standart containers
    my_map.insert(MapType::value_type('d', 4));
    // Using the utility function make_pair
    my_map.insert(std::make_pair('e', 5));
    // Using C++11 initializer list
    my_map.insert({'f', 6});                    
    
    //map keys are sorted automatically from lower to higher. 
    //So, my_map.begin() points to the lowest key value not the key which was inserted first.
    MapType::iterator iter = my_map.begin();

    // Erase the first element using the erase function
    my_map.erase(iter);

    // Output the size of the map using size function
    std::cout << "Size of my_map: " << my_map.size() << '\n';

    std::cout << "Enter a key to search for: ";
    char c;
    std::cin >> c;

    // find will return an iterator to the matching element if it is found
    // or to the end of the map if the key is not found
    iter = my_map.find(c);
    if (iter != my_map.end()) 
    {
        std::cout << "Value is: " << iter->second << '\n';
    }
    else 
    {
        std::cout << "Key is not in my_map" << '\n';
    }

    // You can clear the entries in the map using clear function
    my_map.clear();
    
    return 0;
}

उपर्युक्त उदाहरण map द्वारा प्रदान किए गए कुछ फंक्शन्स के उपयोग को प्रदर्शित करता है, जैसे insert() (एलिमेंट को मैप में इन्सर्ट करता है), erase() (मैप से एलिमेंट को रिमूव करता है), find() (कंटेनर में एलिमेंट की उपस्थिति का अन्वेषण करता है), आदि।

जब प्रोग्राम निष्पादित किया जाता है, तो insert() फ़ंक्शन का उपयोग करके छह एलिमेंट्स इन्सर्ट किये जाते हैं, फिर erase() फ़ंक्शन का उपयोग करके प्रथम एलिमेंट को डिलीट कर दिया जाता है और मैप का आकार आउटपुट हो जाता है। इसके पश्चात्, यूजर को मैप में कुंजी को सर्च के लिए कहा जाता है। पूर्व निर्मित इटरेटर का उपयोग करके, find() फ़ंक्शन दिए गए कुंजी वाले एलिमेंट को सर्च करता है। यदि यह कुंजी प्राप्त कर लेता है, तो प्रोग्राम एलिमेंट के मान को प्रिंट करता है। अंत में ट्री के सभी एलिमेंट्स को clear() का उपयोग करके इरेज़ कर दिया जाता है।

इटरेटर

मैप कंटेनर में विशिष्ट एलिमेंट्स को दर्शाने करने के लिए इटरेटर का उपयोग कर सकता है। इटरेटर एलिमेंट की कुंजी और मैप किए गए मान दोनों को एक्सेस कर सकता है-

// Declares a map iterator
std::map<Key, Value>::iterator it;

// Accesses the Key value 
it->first;

// Accesses the mapped value
it->second;

// The "value" of the iterator, which is of type std::pair<const Key, Value>
(*it);

इटरेटर का उपयोग करके सभी कुंजियों और मानों को प्रदर्शित करने के लिए मैप के माध्यम से लूपिंग का उदाहरण दिया गया है-

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> data 
    {
     { "Bobs score", 10    },
     { "Martys score", 15  },
     { "Mehmets score", 34 },
     { "Rockys score", 22  },
     // The next values are ignored because elements with the same keys are already in the map
     { "Rockys score", 23  }, 
     { "Mehmets score", 33 } 
    };
    
    // Iterate over the map and print out all key/value pairs.
    for (const auto& element : data)
    {
        std::cout << "Who(key = first): " << element.first;
        std::cout << " Score(value = second): " << element.second << '\n';
    }
    
    // If needed you can iterate over the map with the use of iterator,
    // Note that the long typename of the iterator in this case can be replaced with auto keyword
    for (std::map<std::string, int>::iterator iter = data.begin(); iter != data.end(); ++iter) 
    {
        std::cout << "Who(key = first): " << iter->first;
        std::cout << " Score(value = second): " << iter->second << '\n';
    }

    return 0;
}

जीसीसी कंपाइलर पर उपरोक्त प्रारूप को संकलित करने के लिए, विशिष्ट मानक चयनित फ्लैग का उपयोग करना चाहिए।

g++ -std=c++11 source.cpp -o src

यह मैप की कुंजी और मान का आउटपुट देता है।

यह भी देखें

• कंटेनर (एब्स्ट्रैक्ट डेटा प्रकार)
• मानक टेम्प्लेट लाइब्रेरी#कंटेनर
• अनऑर्डड ऍसोसियेटिव कंटेनर (C++)