इंडेक्स

Question

लागू किए बिना केवल इंडेक्समूट को कार्यान्वित करना मैं DefaultHashMap संरचना बनाने की कोशिश कर रहा हूं जो मूल रूप से HashMap के आसपास एक रैपर है, इस अंतर के साथ कि मानचित्र में कोई कुंजी नहीं होने पर डिफ़ॉल्ट मान उस कुंजी में डाल दिया जाता है और है लौटा हुआ।

मैंने get और get_mut विधि बनाई और यह ठीक काम करता है। अब मैं उन तरीकों के चारों ओर रैपर के रूप में Index और IndexMut को लागू करने की कोशिश कर रहा हूं। यहां मैं दो समस्याओं में भाग रहा हूं।

पहली समस्या इस तथ्य के कारण होती है कि get को कुंजी को मौजूद नहीं होने पर संरचना को म्यूट करना होगा, इसके लिए एक उत्परिवर्तनीय संदर्भ की आवश्यकता है। हालांकि, Index की विधि &self के बजाय &self के लिए हस्ताक्षर है, इसलिए मैं इसे कार्यान्वित नहीं कर सकता।

यह दूसरी समस्या का कारण बनता है, IndexMut को Index कार्यान्वयन की आवश्यकता होती है। तो भले ही IndexMut को लागू करने में कोई समस्या नहीं होगी, मैं ऐसा नहीं कर सकता क्योंकि Index लागू नहीं किया जा सकता है।

पहली समस्या परेशान लेकिन समझ में आता है। दूसरे के लिए, मुझे नहीं पता कि आवश्यकता क्यों है। मैं इसके चारों ओर काम करने का एक तरीका चाहता हूं। अभी मैं निम्नलिखित कर रहा हूँ, लेकिन मुझे आशा है कि किसी को एक बेहतर समाधान है:

impl<K: Eq + Hash, V: Clone> Index<K> for DefaultHashMap<K, V> { 
    type Output = V; 

    fn index(&self, _: K) -> &V { 
     panic!("DefautHashMap doesn't implement indexing without mutating") 
    } 
} 

impl<K: Eq + Hash, V: Clone> IndexMut<K> for DefaultHashMap<K, V> { 
    #[inline] 
    fn index_mut(&mut self, index: K) -> &mut V { 
     self.get_mut(index) 
    } 
} 

Answer 1

सबसे पहले, मुझे लगता है कि आपकी आवश्यकता "जब एक महत्वपूर्ण यह है कि नक्शा डिफ़ॉल्ट मान में डाल दिया जाता है में नहीं है हो रही है वह कुंजी "बिल्कुल जरूरी नहीं है!

एक अप्रत्याशित पहुंच let foo = default_hash_map[bar] + 123; पर विचार करें। जब तक आप मानचित्र के साथ आंतरिक परिवर्तनशीलता के साथ मूल्यों का उपयोग नहीं कर रहे हैं, तो यह असफल हो सकता है कि default_hash_map[bar] वास्तव में एक कुंजी बना रहा है या केवल एक डिफ़ॉल्ट मान का संदर्भ देता है।

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

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

अब, अपने सामान्य उपयोग पैटर्न शायद संशोधित नई प्रविष्टियां होने जा रहा है और उसके बाद नक्शा मौजूदा प्रविष्टियों तक पहुँचने। इस प्रकार Index::index में नई प्रविष्टियां बनाना एक अपवाद है और शेष मानचित्र को धीमा नहीं करना चाहिए। इसलिए Index::index पहुंच के लिए केवल मुक्केबाजी मूल्य का भुगतान करना समझ में आ सकता है। ऐसा करने के लिए हम दूसरी संरचना का उपयोग कर सकते हैं, जो केवल Index::index मानों को बॉक्स करता है।

यह जानते हुए कि मौजूदा V refereces अमान्य बिना कि HashMap<K, Box<V>> में डाला जा सकता हमें एक अस्थायी बफर के रूप में उपयोग करने के लिए, Index::index -created मूल्यों पकड़े जब तक हम उन्हें प्राथमिक HashMap के साथ सिंक्रनाइज़ करने का मौका मिलता है।

use std::borrow::Borrow; 
use std::cell::UnsafeCell; 
use std::collections::HashMap; 
use std::hash::Hash; 
use std::ops::Index; 
use std::ops::IndexMut; 

struct DefaultHashMap<K, V>(HashMap<K, V>, UnsafeCell<HashMap<K, Box<V>>>, V); 

impl<K, V> DefaultHashMap<K, V> 
    where K: Eq + Hash 
{ 
    fn sync(&mut self) { 
     let buf_map = unsafe { &mut *self.1.get() }; 
     for (k, v) in buf_map.drain() { 
      self.0.insert(k, *v); 
     } 
    } 
} 

impl<'a, K, V, Q: ?Sized> Index<&'a Q> for DefaultHashMap<K, V> 
    where K: Eq + Hash + Clone, 
      K: Borrow<Q>, 
      K: From<&'a Q>, 
      Q: Eq + Hash, 
      V: Clone 
{ 
    type Output = V; 

    fn index(&self, key: &'a Q) -> &V { 
     if let Some(v) = self.0.get(key) { 
      v 
     } else { 
      let buf_map: &mut HashMap<K, Box<V>> = unsafe { &mut *self.1.get() }; 
      if !buf_map.contains_key(key) { 
       buf_map.insert(K::from(key), Box::new(self.2.clone())); 
      } 
      &*buf_map.get(key).unwrap() 
     } 
    } 
} 

impl<'a, K, V, Q: ?Sized> IndexMut<&'a Q> for DefaultHashMap<K, V> 
    where K: Eq + Hash + Clone, 
      K: Borrow<Q>, 
      K: From<&'a Q>, 
      Q: Eq + Hash, 
      V: Clone 
{ 
    fn index_mut(&mut self, key: &'a Q) -> &mut V { 
     self.sync(); 
     if self.0.contains_key(key) { 
      self.0.get_mut(key).unwrap() 
     } else { 
      self.0.insert(K::from(key), self.2.clone()); 
      self.0.get_mut(key).unwrap() 
     } 
    } 
} 

fn main() { 
    { 
     let mut dhm = DefaultHashMap::<String, String>(HashMap::new(), 
                 UnsafeCell::new(HashMap::new()), 
                 "bar".into()); 
     for i in 0..10000 { 
      dhm[&format!("{}", i % 1000)[..]].push('x') 
     } 
     println!("{:?}", dhm.0); 
    } 

    { 
     let mut dhm = DefaultHashMap::<String, String>(HashMap::new(), 
                 UnsafeCell::new(HashMap::new()), 
                 "bar".into()); 
     for i in 0..10000 { 
      let key = format!("{}", i % 1000); 
      assert!(dhm[&key].len() >= 3); 
      dhm[&key[..]].push('x'); 
     } 
     println!("{:?}", dhm.0); 
    } 

    { 
     #[derive(Eq, PartialEq, Clone, Copy, Hash, Debug)] 
     struct K(u32); 
     impl<'a> From<&'a u32> for K { 
      fn from(v: &u32) -> K { 
       K(*v) 
      } 
     } 
     impl<'a> Borrow<u32> for K { 
      fn borrow(&self) -> &u32 { 
       &self.0 
      } 
     } 
     let mut dhm = DefaultHashMap::<K, K>(HashMap::new(), 
              UnsafeCell::new(HashMap::new()), 
              K::from(&123)); 
     for i in 0..10000 { 
      let key = i % 1000; 
      assert!(dhm[&key].0 >= 123); 
      dhm[&key].0 += 1; 
     } 
     println!("{:?}", dhm.0); 
    } 
} 

(playground)

ध्यान दें कि मुक्केबाजी केवल नए प्रविष्टियों की प्रविष्टि स्थिर। को बॉक्स किए गए प्रविष्टियों को हटाएं जिन्हें आपको अभी भी म्यूटेबल (&mut self) DefaultHashMap तक पहुंच की आवश्यकता है।