2012-03-15 7 views
9

मुझे सम्मिलन के समय (या उससे कुछ और अधिक कुशल) के आधार पर std :: मानचित्र से तत्वों को मिटाना होगा।सम्मिलन के समय के आधार पर std :: मानचित्र से तत्व निकालें

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

क्या किसी के पास कोई अच्छा विचार है कि std :: मानचित्र से तत्वों को मिटाने के दौरान तत्वों को कैसे मिटाना है?

+1

आप को बढ़ावा देने बहु सूचकांक कंटेनर – PlasmaHH

+1

पुराने पर एक नजर है करने के लिए चाहते हो सकता है? आप कोई कार्रवाई करने के एक निश्चित मापदंड की जरूरत है, जब तक आप एक परिभाषित, क्यू काफी दिशाहीन है। –

+0

@PlasmaHH हाँ बूस्ट इस परियोजना में उपयोग करने के लिए संभव नहीं था, लेकिन – theAlse

उत्तर

6

std::map<> प्रकार में कोई तत्व डालने पर कोई धारणा नहीं है। यह केवल एक कुंजी/मूल्य जोड़ी मैपिंग आयोजित करता है। इसमें सम्मिलित आदेश की कोई धारणा नहीं है, इसलिए यह एक सापेक्ष प्रकार का सम्मिलन भी प्रदान नहीं कर सकता है।

जो भी आप चाहते हैं उसे करने के लिए आपको तत्वों और उनके द्वारा डाले गए समय के बीच एक संबंध जोड़ने की आवश्यकता होगी। यदि आप केवल इतना चाहते हैं रिश्तेदार आदेश है तो आप एक std::queue मानचित्र के साथ रखा इस्तेमाल कर सकते हैं। हर बार जब आप नक्शा आप के रूप में अच्छी std::queue में डालने में सम्मिलित करें। कतार के सामने तत्व पीछे की तुलना में पुराने होते हैं और आप इसका उपयोग सापेक्ष आयु

1

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

+0

इटरेटर पॉइंटर्स से अधिक उपयोगी हो सकते हैं, लेकिन न ही नक्शे पर सम्मिलन और त्रुटियों से प्रभावित होंगे: http://stackoverflow.com/a/6438087/5987 –

4

LRU Cache के बहुत करीब के लिए कर सकते हैं।

Boost.MultiIndex लाइब्रेरी MRU Cache (सबसे हाल ही में प्रयुक्त) का एक उदाहरण दिखाती है, इसलिए इसे एलआरयू में अपनाना तुच्छ होना चाहिए।

Basic कोड नक्शे में संदर्भ के साथ

  • एक deque में

      आइटम के साथ
    • एक map:

      मूल रूप से विचार समांतर में दो डाटा संरचनाओं को बनाए रखना है

      static double const EXPIRY = 3600; // seconds 
      
      std::map<Key, Value> map; 
      std::deque<std::pair<std::map<Key, Value>::iterator, time_t>> deque; 
      
      bool insert(Key const& k, Value const& v) { 
          std::pair<std::map<Key, Value>::iterator, bool> result = 
          map.insert(std::make_pair(k, v)); 
      
          if (result.second) { 
          deque.push_back(std::make_pair(result.first, time())); 
          } 
      
          return result.second; 
      } 
      
      // to be launched periodically 
      void clean() { 
          while (not deque.empty() and difftime(time(), deque.front().second) < EXPIRY) { 
          map.erase(deque.front().first); 
          deque.pop_front(); 
          } 
      } 
      
      बेशक

      , उन संरचनाओं ख की जरूरत है यदि मल्टी-थ्रेडेड कोड प्राप्त करना है तो ई सिंक्रनाइज़ किया गया है।

  • +0

    बहुत बहुत शुक्रिया, एक बहुत अच्छा आईडीई जो मैं बाहर की कोशिश करेंगे। – theAlse

     संबंधित मुद्दे

    • कोई संबंधित समस्या नहीं^_^