std :: नक्शा डालने या std :: नक्शा ढूंढें?

Question

एक मानचित्र मानना ​​जहां आप मौजूदा प्रविष्टियों को संरक्षित करना चाहते हैं। 20% समय, जो प्रविष्टि आप डालने वाले हैं वह नया डेटा है। क्या std :: map :: करने के लिए कोई फायदा है तो std :: map :: वापस लौटाए गए इटरेटर का उपयोग करके सम्मिलित करें? या क्या यह सम्मिलित करने का प्रयास करने के लिए तेज़ है और फिर इस पर आधारित कार्य करता है कि क्या इटरेटर इंगित करता है कि रिकॉर्ड रिकॉर्ड किया गया था या नहीं डाला गया था?

Answer 1

उत्तर आप न तो करते हैं। इसके बजाय आप Scott Meyers द्वारा कुछ मद Effective STL 24 ने सुझाव दिया क्या करना चाहते हैं:

typedef map<int, int> MapType; // Your map type may vary, just change the typedef 

MapType mymap; 
// Add elements to map here 
int k = 4; // assume we're searching for keys equal to 4 
int v = 0; // assume we want the value 0 associated with the key of 4 

MapType::iterator lb = mymap.lower_bound(k); 

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first))) 
{ 
    // key already exists 
    // update lb->second if you care to 
} 
else 
{ 
    // the key does not exist in the map 
    // add it to the map 
    mymap.insert(lb, MapType::value_type(k, v)); // Use lb as a hint to insert, 
                // so it can avoid another lookup 
} 

Answer 2

2 के बीच की गति में मुश्किल से कोई अंतर नहीं होगा, खोजने के लिए एक इटरेटर वापस आ जाएगा, डालने वाला वही होगा और यह निर्धारित करने के लिए मानचित्र को खोजेगा कि प्रविष्टि पहले से मौजूद है या नहीं।

तो .. यह व्यक्तिगत वरीयता के लिए नीचे है। मैं हमेशा डालने का प्रयास करता हूं और फिर आवश्यक होने पर अपडेट करता हूं, लेकिन कुछ लोग लौटाए गए जोड़ी को संभालना पसंद नहीं करते हैं।

Answer 3

मानचित्र [कुंजी] - इसे हल करने दें। यह आपके इरादे को सबसे प्रभावी ढंग से संचारित कर रहा है।

हाँ, पर्याप्त मेला।

यदि आप कोई खोज करते हैं और फिर एक सम्मिलित करते हैं तो आप 2 एक्स ओ (लॉग एन) कर रहे होते हैं जब आपको याद आती है क्योंकि आपको केवल यह पता करने की सुविधा मिलती है कि आपको डालने की आवश्यकता है या नहीं (निचला_बाउंड वहां आपकी मदद करें)। बस एक सीधी डालने और फिर परिणाम की जांच करना जिस तरह से मैं जाऊंगा।

Answer 4

दक्षता के बारे में कोई भी जवाब आपके एसटीएल के सटीक कार्यान्वयन पर निर्भर करेगा। निश्चित रूप से जानने का एकमात्र तरीका यह है कि इसे दोनों तरीकों से बेंचमार्क करना है। मुझे लगता है कि अंतर महत्वपूर्ण होने की संभावना नहीं है, इसलिए अपनी पसंदीदा शैली के आधार पर निर्णय लें।

Answer 5

मुझे लगता है कि यदि आप कोई खोज करते हैं तो डालें, अतिरिक्त लागत तब होगी जब आपको कुंजी नहीं मिलती और बाद में सम्मिलित नहीं किया जाता है। यह वर्णमाला क्रम में पुस्तकों को देखने और पुस्तक को नहीं ढूंढने जैसा है, फिर पुस्तकों को फिर से देखना है कि इसे कहां डालना है। यह चाबियाँ कैसे लगाएगा कि आप चाबियाँ कैसे संभालेंगे और यदि वे लगातार बदल रहे हैं। अब इसमें कुछ लचीलापन है यदि आपको यह नहीं मिलता है, तो आप लॉग इन, अपवाद, जो भी चाहें कर सकते हैं ...

Answer 6

यदि आप दक्षता के बारे में चिंतित हैं, तो आप hash_map<> देख सकते हैं।

आमतौर पर <> को बाइनरी पेड़ के रूप में लागू किया गया है। आपकी जरूरतों के आधार पर, हैश_मैप अधिक कुशल हो सकता है।

Answer 7

इस सवाल का जवाब भी कैसे महंगा यह मान प्रकार आप नक्शे में भंडारण कर रहे हैं बनाने के लिए है पर निर्भर करता है:

typedef std::map <int, int> MapOfInts; 
typedef std::pair <MapOfInts::iterator, bool> IResult; 

void foo (MapOfInts & m, int k, int v) { 
    IResult ir = m.insert (std::make_pair (k, v)); 
    if (ir.second) { 
    // insertion took place (ie. new entry) 
    } 
    else if (replaceEntry (ir.first->first)) { 
    ir.second->second = v; 
    } 
} 

एक मूल्य के प्रकार के लिए इस तरह के एक पूर्णांक के रूप में, ऊपर होगा और अधिक कुशल एक डालने के बाद एक खोज से (कंपाइलर अनुकूलन की अनुपस्थिति में)। जैसा ऊपर बताया गया है, ऐसा इसलिए है क्योंकि मानचित्र के माध्यम से खोज केवल एक बार होती है।

हालांकि, सम्मिलित करने के लिए कॉल की आवश्यकता है कि आप पहले से ही नया "मूल्य" का निर्माण किया है:

class LargeDataType { /* ... */ }; 
typedef std::map <int, LargeDataType> MapOfLargeDataType; 
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult; 

void foo (MapOfLargeDataType & m, int k) { 

    // This call is more expensive than a find through the map: 
    LargeDataType const & v = VeryExpensiveCall (/* ... */); 

    IResult ir = m.insert (std::make_pair (k, v)); 
    if (ir.second) { 
    // insertion took place (ie. new entry) 
    } 
    else if (replaceEntry (ir.first->first)) { 
    ir.second->second = v; 
    } 
} 

आदेश में 'सम्मिलित करें' हम महंगा कॉल के लिए भुगतान कर रहे हैं कॉल करने के लिए हमारे मान प्रकार के निर्माण के लिए - और इस सवाल में आपने जो कहा है उससे आप इस नए मूल्य का 20% समय का उपयोग नहीं करेंगे। उपरोक्त मामले में, यदि मैप मान प्रकार बदलने एक विकल्प नहीं है तो यह और अधिक कुशल पहले प्रदर्शन करने के लिए 'खोज' की जाँच करने के अगर हम तत्व का निर्माण करने की जरूरत है।

वैकल्पिक रूप से, नक्शे के मान प्रकार की दुकान में बदला जा सकता है डेटा अपने पसंदीदा स्मार्ट सूचक प्रकार का उपयोग करने के लिए संभालती है।सम्मिलित करने के लिए कॉल एक शून्य सूचक (निर्माण के लिए बहुत सस्ता) का उपयोग करता है और केवल तभी आवश्यक है जब नया डेटा प्रकार बनाया गया हो।

Answer 8

मैं शीर्ष जवाब पर खो रहा हूँ।

रिटर्न map.end (खोजें) यह कुछ भी करता है, तो आप के रूप में के रूप में धीमी गति से

map.insert 

किसी भी तत्व के लिए

नहीं है तो नई चीजें जोड़ रहे हैं

iter = map.find(); 
if (iter == map.end()) { 
    map.insert(..) or map[key] = value 
} else { 
    // do nothing. You said you did not want to effect existing stuff. 
} 

दो बार जिसका अर्थ है नहीं मिल रहा है, तो पहले ही मानचित्र में है क्योंकि इसे दो बार खोजना होगा। एक बार यह देखने के लिए कि क्या यह वहां है, फिर नई चीज़ डालने के लिए जगह ढूंढने के लिए।

Answer 9

मुझे लगता है कि मुझे कोई टिप्पणी छोड़ने के लिए पर्याप्त अंक नहीं दिखते हैं, लेकिन चुने गए उत्तर को मेरे लिए लंबे समय तक घुमाया जाता है - जब आप मानते हैं कि डालने वाला यह भी इटरेटर वापस लौटाता है, तो क्यों कम_बाउंड खोजते हैं, जब आप बस उपयोग कर सकते हैं इटरेटर वापस आ गया। अजीब।