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

कंप्यूटिंग में, सहयोगी कंटेनर 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 टाइम कम्प्लेक्सिटी

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

Operation	Complexity
Searching for an element	O(log n)
Inserting a new element	O(log n)
Incrementing/decrementing an iterator	O(log n) (amortized O(1) if only increments or only decrements are done)
Removing a single element	O(log n)

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

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

	set	map	multiset	multimap	Description
	(constructor)	(constructor)	(constructor)	(constructor)	Constructs the container from variety of sources
	(destructor)	(destructor)	(destructor)	(destructor)	Destructs the set and the contained elements
	operator=	operator=	operator=	operator=	Assigns values to the container
	get_allocator	get_allocator	get_allocator	get_allocator	Returns the allocator used to allocate memory for the elements
Element access	—	at	—	—	Accesses specified element with bounds checking.
	—	operator[]	—	—	Accesses specified element without bounds checking.
Iterators	begin	begin	begin	begin	Returns an iterator to the beginning of the container
	end	end	end	end	Returns an iterator to the end of the container
	rbegin	rbegin	rbegin	rbegin	Returns a reverse iterator to the reverse beginning of the container
	rend	rend	rend	rend	Returns a reverse iterator to the reverse end of the container
Capacity	empty	empty	empty	empty	Checks whether the container is empty
	size	size	size	size	Returns number of elements in the container.
	max_size	max_size	max_size	max_size	Returns the maximum possible number of elements in the container
Modifiers	clear	clear	clear	clear	Clears the contents.
	insert	insert	insert	insert	Inserts elements.
	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	Erases elements.
	swap	swap	swap	swap	Swaps the contents with another container.
Lookup	count	count	count	count	Returns the number of elements matching specific key.
	find	find	find	find	Finds an element with specific key.
	equal_range	equal_range	equal_range	equal_range	Returns a range of elements matching specific key.
	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.
Observers	key_comp	key_comp	key_comp	key_comp	Returns the key comparison function.
	value_comp	value_comp	value_comp	value_comp	Returns the value comparison function. In set and multiset this function is equivalent to key_comp, since the elements are composed from a key only.

उपयोग

निम्नलिखित कोड दर्शाता है कि 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++)|अक्रमित सहयोगी कंटेनर C++