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

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

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

डिजाइन

विशेषताएं

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

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

सहयोगी कंटेनरों को दो उपसमूहों में बांटा जा सकता है: मानचित्र और सेट। एक नक्शा, जिसे कभी-कभी एक शब्दकोश के रूप में संदर्भित किया जाता है, में एक कुंजी/मान जोड़ी होती है। अनुक्रम को क्रमबद्ध करने के लिए कुंजी का उपयोग किया जाता है, और मान किसी तरह उस कुंजी से जुड़ा होता है। उदाहरण के लिए, एक मानचित्र में पाठ में प्रत्येक अद्वितीय शब्द का प्रतिनिधित्व करने वाली कुंजियाँ हो सकती हैं और पाठ में उस शब्द के प्रकट होने की संख्या का प्रतिनिधित्व करने वाले मान। एक सेट केवल अद्वितीय तत्वों का एक आरोही कंटेनर है।

जैसा कि पहले कहा गया है, map और set केवल एक कुंजी या तत्व के एक उदाहरण को कंटेनर में डालने की अनुमति दें। यदि तत्वों के एकाधिक उदाहरण आवश्यक हैं, तो उपयोग करें 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++