[rust notes] 14 set (Part 2)

aggregate 14.3

14.3-VecDeque<T>

• Vec It can efficiently add and remove elements at both ends of the queue . If you want to save the value in the middle of the queue ,Vec The processing efficiency of is relatively slow .

• deque std::collections::VecDeque<T>： Implemented ring buffer , Support efficient addition and removal of front-end and back-end operations .

  • deque.push_front(value)： Add a value in front of the queue .
  • deque.push_back(value)： Add a value after the queue .
  • deque.pop_front()： Remove and return the value in front of the queue , return Option<T>, Returns when the queue is empty None.
  • deque.pop_back： Remove and return the value after the queue , return Option<T>, Returns when the queue is empty None.
  • deque.front() and deque.back()： Return the shared reference of the front-end and back-end elements of the queue , return Option<T>, Returns when the queue is empty None.
  • deque.front_mut() and deque.back_mut： Returns modifiable references to the front-end and back-end elements of the queue , return Option<&mut T>.

• Queues are not stored consecutively in memory , Not all methods of the inheriting slices . If you want to perform vector and slice operations on the queue data , Need to put VecDeque Convert to Vec, After the operation , Then switch back .

  • Vec<T> Realized From<VecDeque<T>>, therefore Vec::from(deque) You can convert queues into vectors .

  • VecDeque<T> Realized From<Vec<T>>, therefore VecDeque::from(vec) You can convert vectors into queues .

    //  The method of creating a queue by specifying elements 
    use std::collections::VecDeque;
    
    let v = VecDeque::from(vec![1, 2, 3, 4]);
    

14.4-LinkedList<T>

• Each value of the linked list is stored in a separate heap memory , Is a way to store sequence values .

• std::collections::LinkedList<T> It's a two-way list

• Support

  VecDeque
  

  Part of the way ：

  • The method of operating the front and back ends of the sequence ;
  • Iterator method ;
  • LinkedList::new() etc.

• Support the combination of two lists very quickly ：list1.append(&mut list2), hold list2 All elements in are transferred to list1 in .vec and VecDeque Also support append Method , But many values will be transferred from one heap array to another .

14.5-BinaryHeap<T>

• BinaryHeap<T> Used to store loose elements , The maximum value will always bubble to the front of the queue .

• Common methods ：

  • heap.push(value)： Add values to the heap .
  • heap.pop()： Remove from the heap and return the maximum . The return type is Option<T>, If the heap is empty, return None.
  • heap.peek()： Returns the reference of the maximum value in the heap . The return type is Option<&T>.

• Also support Vec Part of the way ：

  • BinaryHeap::new();
  • heap.len();
  • heap.is_empty();
  • heap.capacity();
  • heap.clear();
  • heap.append(&mut heap2).

• Realize the built-in special type Ord Any type of , Can be saved in BinaryHeap in .

• It is often used to make work queues ：

  • Define a task structure , Based on priority Ord, Make high priority tasks bigger than low priority tasks . then , Create a BinaryHeap Save all completed tasks . You can call .pop() Method always returns the most important task to do next .

  • have access to while Recycling consumption ：

    while let Some(task) = heap.pop() {
            
      handle(task);
    }
    

• BinaryHeap It's an iterative type , They have their own .iter() Method , The order of iterators is arbitrary .

14.6-HashMap<K, V> and BTreeMap<K, V>

• mapping （map） It's a key — It's worth it （ Called entry ） aggregate .

• HashMap<K, V> Save the keys and values in a hash table allocated on the heap , Therefore, the type of key is required K Implement standard hashing and equality features Hash and Eq.

• BTreeMap<K, V> Store entries in key order , The overall structure is tree , Therefore, the type of key is required K Realization Ord.

• Rust Standard library of B Trees , Instead of balancing binary trees . The number of times a binary tree must search , Than B Few trees ; But search B The domain of trees （locality） Better .B Trees can bring together memory accesses , Instead of spreading it all over the heap . such CPU Caching is rarely missed , So as to significantly improve the speed .

• How to create a map ：

  • HashMap::new() and BTreeMap::new() Create a new empty mapping ;
  • iter.collect()： For slave keys — Value pairs create and populate new HashMap or BTreeMap.iter Must be a Iterator<Item=(K, V)> The iterator .
  • HashMap::with_capacity(n)： You can create a new empty hash table , At least it can hold n Entries .
  • HashMap Support capacity related methods separately ：hash_map.capacity()、hash_map.reserve(additional) and hash_map.shrink_to_fit().

• HashMap
  

  and

  BTreeMap
  

  Jointly support the following core methods ：

  • map.len()： Return the number of entries .
  • map.is_empty()： stay map Return when there is no entry true.
  • map.contains_key(&key)： In the mapping, the key of another entry is key When to return to true.
  • map.get(&key)： Search for map Has given key The entry of . If you find a matching entry , return Some(r), among r Is the corresponding reference . Otherwise return to None.
  • map.get_mut(&key)： The function is the same as above , But return a modifiable reference to a value . The value can be modified at will , But the key pike mapping itself , Do not modify .
  • map.insert(key, value)： towards map Insert entry in (key, value). If the mapping already exists as key The entry of , Then a new value will be inserted value, Overwrite the original value . If the original value is overwritten , Will return the original value , The return type is Option<V>.
  • map.extend(iterable)： iteration iterable Of (K, V) entry , And put each key — Value pair insertion map in .
  • map.append(&mut map2)： take map2 All entries of are transferred to map in ,map2 It's going to be empty .
  • map.remove(&key)： Find and remove map The middle key is key The entry of . If any value is removed , The removed value is returned . The return type is Option<V>.
  • map.clear()： Remove all entries .
  • map[&key]： Query the mapping with square bracket syntax . If it does not exist, it is key The entry of , Will be surprised , Similar to array access out of bounds .

• BTreeMap<K, V>
  

  Because you can sort and store entries by pressing the key , And support

  btree_map.split_off(key)
  

  ：

  • Can be btree_map Split in two ;
  • The key is less than key The entry of will be left in btree_map in .
  • Back to the new BTreeMap<K, V> Contains other entries .

14.6.1 - entry

• Entry Item type ： Used to eliminate redundant mapping lookup .

  let record = student_map.entry(name.to_string()).or_insert_with(Student);
  

  • student_map.entry(name.to_string) Back to Entry Values are similar to modifiable references that point to a location in a map ;

  • If the reference is empty , be .or_insert_with() Method will insert a new Student.

  • Entry Is an enumerated type ：

    // std::collections::hash_map
    pub enum Entry<'a, K: 'a, V: 'a> {
            
      Occupied(OccupiedEntry<'a, K, V>),
      Vacant(VacantEntry<'a, K, V>)
    }
    

• establish Entry The method of value ：map.entry(key).

  • Return key is key Of Entry.

  • If there is no , Then return an empty Entry.

  • Receive your own modifiable references , Return life matched Entry：

    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
    

  • If the mapped key is String type , This method cannot be passed &str Type references . At this point, give .entry() Method to pass in the real String.

• Method of filling in empty entries ：

  • map.entry(key).or_insert(value)： Must ensure map The containing key is key The entry of , Default will be given if necessary value Insert new entry . Returns a modifiable reference to a new or existing value .

    //  give an example ： Count the votes 
    let mut vote_counts: HashMap<String, usize> = HashMap::new();
    for name in ballots {
            
      let count = vote_counts.entry(name).or_insert(0);
      *count += 1;   // count The type of &mut usize.
    }
    

  • map.entry(key).or_insert_with(default_fn)： The function is the same as above , But it will be called when a new entry needs to be created default_fn() function , To produce default values . If map Already exists in for key The entry of , Will not be used default_fn().

    let mut word_occurrence: HashMap<String, HashSet<String>> = Hashmap::new();
    for file in files {
            
      for word in read_words(file)? {
            
        let set = word_occurrence
            .entry(word)
            .or_insert_with(HashSet::new);
        set.insert(file.clone());
      }
    }
    

14.6.2 - Mapping iteration

• HashMap Iterators support accessing mapped entries in any order ;BTreeMap iterator , Entries must be accessed in key sequence .
• The iteration of mapping has the following ways ：
  • Iterate by value （for (k, v) in map）： produce (K, V) Yes . This will consume mapping .
  • Iterate by shared reference （for (k, v) in &map）： produce (&K, &V) Yes .
  • Press to modify the reference iteration （for (k, v) in &mut map）： produce (&K, &mut v) Yes .
• The iteration of mapping has the following common methods ：
  • .iter() and .iter_mut()： Methods that return iterators and generate value references ;
  • map.keys()： Returns the iterator that generates the key reference .
  • map.values()： Returns the iterator that generates the value reference .
  • map.values_mut()： Returns an iterator that produces a modifiable value reference .

14.7-HashSet<T> and BTreeSet<T>

• Set Set ： Support rapid testing of membership and organization of values . A set will never contain multiple copies of the same value .

  let b1 = large_vector.contains("needle");  //  Finding elements in vectors is slow , You need to check each element 
  let b2 = large_hash_set.contains("needle"); //  It is faster to find elements in the set , Support hash lookup 
  

• Sets are similar to key only mappings .HashSet<T> and BTreeSet<T> Are implemented in the form of packaging types ：

  • HashSet::new() and BTreeSet::new() Create a new set .
  • iter.collect() Can be used to create a new set from any iterator . If duplicate values are generated , Then the duplicate value will be cleared .
  • HashSet::with_capacity(n) Create empty HashSet, At least n It's worth .

• HashSet<T> and BTreeSet<T> The common method ：

  • set.len()： return set The number of median .
  • set.is_empty()： Return without element value in the set true.
  • set.contains(&value)： Include the given value in the set value When to return to true.
  • set.insert(value)： Add... To the set value. If the addition is successful, it will return true, If the same value already exists in the set, it returns false.
  • set.remove(&value)： Remove from the set value. If the removal is successful, return true. If it's not worth it , Then return to false.

• Similar to mapping , The method of querying values by reference is also general , As long as you can T Borrow to this type .

14.7.1 - Set iteration

• There are two ways to iterate a set ：
  • Iterate by value ：for v in set Generate members of the set , And consumption set .
  • Iterate by shared reference ：for v in &set Generate shared references to set members .
• Modifiable reference iteration sets are not supported . That is, modifiable references that cannot get values from the set .set.iter() Return iterator , produce set References to members .
• HashSet Iterators support accessing mapped entries in any order ;BTreeSet iterator , Entries must be accessed in key sequence .

14.7.2 - Equal values are different —— Store different locations in memory

The method of getting the actual value stored in the set ： These methods all return Option, If set Does not contain matching values , Then return to None.

• set.get(&value)： return set Medium is equal to value Shared references of members of , The return type is Option<&T>.
• set.take(&value)： Be similar to set.remove(&value), But return the removed value , The return type is Option<T>.
• set.replace(value)： Be similar to set.insert(value), But if set It already contains equal to value Value , Then return the original value . The return type is Option<T>

14.7.3 - Whole set operation

• Methods of operating on the entire set ：
  • set1.intersection(&set2)： The return is also contained in set1 and set2 Iterators for all values in .
  • &set1 & &set2： return set1 and set2 Intersection .
  • set1.union(&set2)： The return is also contained in set1 and set2 Kind of , Or only in set1 or set2 Iterator of the value of .
  • &set1 | &set2： Returns a new set containing all the values in these two sets .
  • set1.difference(&set2)： The return is contained in set1 But not included in set2 Iterator of values in .
  • &set1 - &set2： The return is contained in set1 But not included in set2 A new set of all these values .
  • set1.symmetric_difference(&set2)： The return is only contained in set1 in , Or only included in set2 in , But iterators that do not contain values in both sets .
  • &set1 ^ &set2： The return is only contained in set1 in , Or only included in set2 in , But a new set of values that are not included in both sets .
• Test the relationship between sets 3 Methods ：
  • set1.is_disjoint(set2)： If the intersection is empty , Then return to true.
  • set1.is_subset(set2)： If set1 yes set2 Subset , Then return to true.
  • set1.is_superset(set2)： If set1 yes set2 Superset , Then return to true.
• Set also supports == and != Equality test of ： The two packages have the same value , Then they are equal .

14.8 - hash

14.8.1 - summary

• std::hash::Hash It is a special type of hashable type in the standard library .

• No matter where a value is saved , Or how to point to it , All should have the same hash code .

  • The reference has the same hash code as the value it points to ;
  • Box The same hash code as the boxed value ;
  • vector vec With slices that contain all their data &ved[..] Have the same hash code ;
  • String With the same character as the reference &str Have the same hash code .

• Structure and enumeration are not implemented by default Hash, But you can derive an implementation ：

  #[derive(Clone, PartialEq, Eq, Hash)]
  enum MN {
        
    ...
  }
  

• If you manually implement for a type PartialEq, Then it must be realized Hash.

14.8.2 - Use a custom hash algorithm

• hash Methods are generic .

• Complete protocol for computing hash codes ：

  use std::hash::{
        Hash, Hasher, BuildHasher};
  
  fn compute_hash<B, T>(builder: &B, value: &T) -> u64
      where B: BuildHasher, T: Hash
  {
        
    let mut hasher = builder.build_hasher(); //  Algorithm start 
    value.hash(&mut hasher);                 //  Incoming data 
    hasher.finish()                          //  Algorithm complete , produce u64 value .
  }
  

• Rust By default SipHash-1-3 Algorithm as hash algorithm . As long as there are differences , Every hash table uses unpredictable keys . So it can prevent HashDoS Denial of service attacks on , That is, the attacker deliberately uses hash conflict to start the worst performance in the server .

• If you want faster hash implementation , At the expense of security , Then you can use fnv Package implementation Fowler-Noll-Vo Hash algorithm .

  //  stay Cargo.toml Add ：
  [dependencies]
  fnv = "1.0"
  
  //  Import mapping and hash types 
  extern crate fnv;
  use fnv::{
        FnvHashMap, FnvHashSet}; //  Instead of HashMap and HashSet.
  

14.9 - Other sets

Rust Support in unsafe Implementation in block C++ Data structure of ： Original pointer 、 Manual memory management 、 place new、 Show call destructors .

---

See 《Rust Programming 》（ Jim - Brandy 、 Jason, - By orendov , Translated by lisongfeng ） Chapter 16
Original address