सी ++ में हैश मैप का उपयोग करने का सबसे अच्छा तरीका क्या है?

Question

मुझे पता है कि एसटीएल में हैश मैप एपीआई है, लेकिन मुझे इसके बारे में अच्छे उदाहरणों के साथ कोई अच्छा और पूर्ण दस्तावेज नहीं मिल रहा है।

किसी भी अच्छे उदाहरण की सराहना की जाएगी।

Answer 1

एसटीएल में आदेश दिया गया और अनियंत्रित नक्शा (std::map और std::unordered_map) कंटेनर शामिल हैं। आदेशित मानचित्र में तत्वों को कुंजी, सॉर्ट और एक्सेस द्वारा क्रमबद्ध किया जाता है O (लॉग n) में है)। आम तौर पर एसटीएल आदेशित नक्शे के लिए आंतरिक रूप से red black trees का उपयोग करता है। लेकिन यह सिर्फ एक कार्यान्वयन विस्तार है। एक unordered मानचित्र डालने और उपयोग में ओ (1) में है। यह हैशटेबल के लिए सिर्फ एक और नाम है।

साथ (आदेश दिया) std::map एक उदाहरण:

#include <map> 
#include <iostream> 
#include <cassert> 

int main(int argc, char **argv) 
{ 
    std::map<std::string, int> m; 
    m["hello"] = 23; 
    // check if key is present 
    if (m.find("world") != m.end()) 
    std::cout << "map contains key world!\n"; 
    // retrieve 
    std::cout << m["hello"] << '\n'; 
    std::map<std::string, int>::iterator i = m.find("hello"); 
    assert(i != m.end()); 
    std::cout << "Key: " << i->first << " Value: " << i->second << '\n'; 
    return 0; 
} 

आउटपुट:

 
23 
Key: hello Value: 23 

आप अपने कंटेनर में आदेश देने और ओ के साथ ठीक कर रहे हैं की जरूरत है (लॉग एन) क्रम फिर बस std::map का उपयोग ।

अन्यथा, यदि आप वास्तव में एक हैश तालिका (ओ (1) सम्मिलित/पहुँच) की जरूरत है, std::unordered_map की जाँच है, जो ऊपर के उदाहरण आप बस खोज और साथ map को बदलने के लिए में std::map एपीआई (जैसे एक समान है unordered_map)।

unordered_map कंटेनर C++11 standard संशोधन के साथ पेश किया गया था। इस प्रकार, आपके कंपाइलर के आधार पर, आपको सी ++ 11 फीचर्स को सक्षम करना होगा (उदाहरण के लिए जब जीसीसी 4.8 का उपयोग करते हैं तो आपको -std=c++11 को CXXFLAGS में जोड़ना होगा)।

सी ++ 11 रिलीज से पहले भी जीसीसी समर्थित unordered_map - नामस्थान std::tr1 में। यानी आप बेहतर पोर्टेबिलिटी के लिए इसी boost-header उपयोग कर सकते हैं

#include <tr1/unordered_map> 

std::tr1::unordered_map<std::string, int> m; 

यह भी बढ़ावा का हिस्सा है,: इस प्रकार, वर्ष जीसीसी compilers के लिए आप इस तरह इसका इस्तेमाल करने की कोशिश कर सकते हैं।

Answer 2

ए hash_map मानकीकरण उद्देश्यों के लिए unordered_map (वर्तमान में TR1 के हिस्से के रूप में उपलब्ध है, और सी ++ 0x में शामिल किया जाएगा) के पुराने, गैर-मानकीकृत संस्करण है। नाम से स्पष्ट है, यह मुख्य रूप से अव्यवस्थित होने में std::map से अलग है - अगर, उदाहरण के लिए, आप एक नक्शे के माध्यम से begin() से end() को पुनरावृति, आप कुंजी द्वारा क्रम में आइटम मिलता है, लेकिन आप begin() से एक unordered_map के माध्यम से पुनरावृति करता है, तो end() पर, आप वस्तुओं को अधिक या कम मनमाना क्रम में प्राप्त करते हैं।

एक unordered_map आमतौर पर निरंतर जटिलता होने की उम्मीद है। यही है, एक सम्मिलन, लुकअप इत्यादि, अनिवार्य रूप से निश्चित समय लेता है, इस पर ध्यान दिए बिना कि तालिका में कितनी वस्तुएं हैं। एक std::map में जटिलता है जो संग्रहीत वस्तुओं की संख्या पर लॉगरिदमिक है - जिसका मतलब है कि किसी आइटम को डालने या पुनर्प्राप्त करने का समय बढ़ता है, लेकिन धीरे-धीरे, जैसे नक्शा बड़ा हो जाता है। उदाहरण के लिए, यदि 1 मिलियन आइटमों में से किसी एक को देखने के लिए 1 माइक्रोसॉन्ड लेता है, तो आप उम्मीद कर सकते हैं कि 2 मिलियन आइटमों में से एक के लिए 3 माइक्रोसॉन्ड, 4 मिलियन आइटमों में से एक के लिए 3 माइक्रोसॉन्ड, 4 मिलियन में से एक के लिए 4 माइक्रोसॉन्ड वस्तुओं, आदि

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

जहां आप मानचित्र बनाते समय तीसरे टेम्पलेट पैरामीटर द्वारा ऑर्डर को परिभाषित किया जाता है, std::less<T> डिफ़ॉल्ट रूप से।

Answer 3

यहाँ एक अधिक पूर्ण और लचीला उदाहरण है कि आवश्यक छोड़ नहीं करता संकलन त्रुटियों उत्पन्न करने के लिए करती है:,

#include <iostream> 
#include <unordered_map> 

class Hashtable { 
    std::unordered_map<const void *, const void *> htmap; 

public: 
    void put(const void *key, const void *value) { 
      htmap[key] = value; 
    } 

    const void *get(const void *key) { 
      return htmap[key]; 
    } 

}; 

int main() { 
    Hashtable ht; 
    ht.put("Bob", "Dylan"); 
    int one = 1; 
    ht.put("one", &one); 
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one"); 
} 

फिर भी विशेष रूप से कुंजी के लिए उपयोगी नहीं जब तक कि वे संकेत के रूप में पूर्वनिर्धारित रहे हैं, क्योंकि उससे मिलते-जुलते मूल्य जीता ' टी करो! (हालांकि, बाद से मैं सामान्य रूप से चाबी के लिए तार के लिए "स्थिरांक शून्य *" कुंजी की घोषणा में उपयोग करते हैं, "स्ट्रिंग" प्रतिस्थापन इस समस्या को हल करना चाहिए।)

Answer 4

कैसे unordered_map के साथ एक कस्टम वर्ग और हैश समारोह का उपयोग करने के

इस उत्तर नाखून यह: C++ unordered_map using a custom class type as the key

अंश: समानता:

struct Key 
{ 
    std::string first; 
    std::string second; 
    int   third; 

    bool operator==(const Key &other) const 
    { return (first == other.first 
      && second == other.second 
      && third == other.third); 
    } 
}; 

हैश समारोह:

namespace std { 

    template <> 
    struct hash<Key> 
    { 
    std::size_t operator()(const Key& k) const 
    { 
     using std::size_t; 
     using std::hash; 
     using std::string; 

     // Compute individual hash values for first, 
     // second and third and combine them using XOR 
     // and bit shifting: 

     return ((hash<string>()(k.first) 
      ^(hash<string>()(k.second) << 1)) >> 1) 
      ^(hash<int>()(k.third) << 1); 
    } 
    }; 

}