diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/collections/hash/map.rs | 465 | ||||
| -rw-r--r-- | src/libstd/collections/hash/set.rs | 232 |
2 files changed, 343 insertions, 354 deletions
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index a82b9498074..4fb0235539c 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -716,6 +716,232 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomState> { } } +impl<K, V, S> HashMap<K, V, S> { + /// Returns the number of elements the map can hold without reallocating. + /// + /// This number is a lower bound; the `HashMap<K, V>` might be able to hold + /// more, but is guaranteed to be able to hold at least this many. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// let map: HashMap<i32, i32> = HashMap::with_capacity(100); + /// assert!(map.capacity() >= 100); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn capacity(&self) -> usize { + self.resize_policy.capacity(self.raw_capacity()) + } + + /// Returns the hash map's raw capacity. + #[inline] + fn raw_capacity(&self) -> usize { + self.table.capacity() + } + + /// An iterator visiting all keys in arbitrary order. + /// The iterator element type is `&'a K`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert("a", 1); + /// map.insert("b", 2); + /// map.insert("c", 3); + /// + /// for key in map.keys() { + /// println!("{}", key); + /// } + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn keys(&self) -> Keys<K, V> { + Keys { inner: self.iter() } + } + + /// An iterator visiting all values in arbitrary order. + /// The iterator element type is `&'a V`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert("a", 1); + /// map.insert("b", 2); + /// map.insert("c", 3); + /// + /// for val in map.values() { + /// println!("{}", val); + /// } + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn values(&self) -> Values<K, V> { + Values { inner: self.iter() } + } + + /// An iterator visiting all values mutably in arbitrary order. + /// The iterator element type is `&'a mut V`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// + /// map.insert("a", 1); + /// map.insert("b", 2); + /// map.insert("c", 3); + /// + /// for val in map.values_mut() { + /// *val = *val + 10; + /// } + /// + /// for val in map.values() { + /// println!("{}", val); + /// } + /// ``` + #[stable(feature = "map_values_mut", since = "1.10.0")] + pub fn values_mut(&mut self) -> ValuesMut<K, V> { + ValuesMut { inner: self.iter_mut() } + } + + /// An iterator visiting all key-value pairs in arbitrary order. + /// The iterator element type is `(&'a K, &'a V)`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert("a", 1); + /// map.insert("b", 2); + /// map.insert("c", 3); + /// + /// for (key, val) in map.iter() { + /// println!("key: {} val: {}", key, val); + /// } + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn iter(&self) -> Iter<K, V> { + Iter { inner: self.table.iter() } + } + + /// An iterator visiting all key-value pairs in arbitrary order, + /// with mutable references to the values. + /// The iterator element type is `(&'a K, &'a mut V)`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert("a", 1); + /// map.insert("b", 2); + /// map.insert("c", 3); + /// + /// // Update all values + /// for (_, val) in map.iter_mut() { + /// *val *= 2; + /// } + /// + /// for (key, val) in &map { + /// println!("key: {} val: {}", key, val); + /// } + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn iter_mut(&mut self) -> IterMut<K, V> { + IterMut { inner: self.table.iter_mut() } + } + + /// Returns the number of elements in the map. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn len(&self) -> usize { + self.table.size() + } + + /// Returns `true` if the map contains no elements. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1, "a"); + /// assert!(!a.is_empty()); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Clears the map, returning all key-value pairs as an iterator. Keeps the + /// allocated memory for reuse. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// + /// for (k, v) in a.drain().take(1) { + /// assert!(k == 1 || k == 2); + /// assert!(v == "a" || v == "b"); + /// } + /// + /// assert!(a.is_empty()); + /// ``` + #[inline] + #[stable(feature = "drain", since = "1.6.0")] + pub fn drain(&mut self) -> Drain<K, V> { + Drain { inner: self.table.drain() } + } + + /// Clears the map, removing all key-value pairs. Keeps the allocated memory + /// for reuse. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// a.insert(1, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + #[inline] + pub fn clear(&mut self) { + self.drain(); + } +} + impl<K, V, S> HashMap<K, V, S> where K: Eq + Hash, S: BuildHasher @@ -802,30 +1028,6 @@ impl<K, V, S> HashMap<K, V, S> &self.hash_builder } - /// Returns the number of elements the map can hold without reallocating. - /// - /// This number is a lower bound; the `HashMap<K, V>` might be able to hold - /// more, but is guaranteed to be able to hold at least this many. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// let map: HashMap<i32, i32> = HashMap::with_capacity(100); - /// assert!(map.capacity() >= 100); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn capacity(&self) -> usize { - self.resize_policy.capacity(self.raw_capacity()) - } - - /// Returns the hash map's raw capacity. - #[inline] - fn raw_capacity(&self) -> usize { - self.table.capacity() - } - /// Reserves capacity for at least `additional` more elements to be inserted /// in the `HashMap`. The collection may reserve more space to avoid /// frequent reallocations. @@ -1048,127 +1250,6 @@ impl<K, V, S> HashMap<K, V, S> } } - /// An iterator visiting all keys in arbitrary order. - /// The iterator element type is `&'a K`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for key in map.keys() { - /// println!("{}", key); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn keys(&self) -> Keys<K, V> { - Keys { inner: self.iter() } - } - - /// An iterator visiting all values in arbitrary order. - /// The iterator element type is `&'a V`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for val in map.values() { - /// println!("{}", val); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn values(&self) -> Values<K, V> { - Values { inner: self.iter() } - } - - /// An iterator visiting all values mutably in arbitrary order. - /// The iterator element type is `&'a mut V`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for val in map.values_mut() { - /// *val = *val + 10; - /// } - /// - /// for val in map.values() { - /// println!("{}", val); - /// } - /// ``` - #[stable(feature = "map_values_mut", since = "1.10.0")] - pub fn values_mut(&mut self) -> ValuesMut<K, V> { - ValuesMut { inner: self.iter_mut() } - } - - /// An iterator visiting all key-value pairs in arbitrary order. - /// The iterator element type is `(&'a K, &'a V)`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for (key, val) in map.iter() { - /// println!("key: {} val: {}", key, val); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter(&self) -> Iter<K, V> { - Iter { inner: self.table.iter() } - } - - /// An iterator visiting all key-value pairs in arbitrary order, - /// with mutable references to the values. - /// The iterator element type is `(&'a K, &'a mut V)`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// // Update all values - /// for (_, val) in map.iter_mut() { - /// *val *= 2; - /// } - /// - /// for (key, val) in &map { - /// println!("key: {} val: {}", key, val); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter_mut(&mut self) -> IterMut<K, V> { - IterMut { inner: self.table.iter_mut() } - } - /// Gets the given key's corresponding entry in the map for in-place manipulation. /// /// # Examples @@ -1197,85 +1278,6 @@ impl<K, V, S> HashMap<K, V, S> .into_entry(key).expect("unreachable") } - /// Returns the number of elements in the map. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// assert_eq!(a.len(), 0); - /// a.insert(1, "a"); - /// assert_eq!(a.len(), 1); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { - self.table.size() - } - - /// Returns `true` if the map contains no elements. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// assert!(a.is_empty()); - /// a.insert(1, "a"); - /// assert!(!a.is_empty()); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { - self.len() == 0 - } - - /// Clears the map, returning all key-value pairs as an iterator. Keeps the - /// allocated memory for reuse. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// a.insert(1, "a"); - /// a.insert(2, "b"); - /// - /// for (k, v) in a.drain().take(1) { - /// assert!(k == 1 || k == 2); - /// assert!(v == "a" || v == "b"); - /// } - /// - /// assert!(a.is_empty()); - /// ``` - #[inline] - #[stable(feature = "drain", since = "1.6.0")] - pub fn drain(&mut self) -> Drain<K, V> { - Drain { inner: self.table.drain() } - } - - /// Clears the map, removing all key-value pairs. Keeps the allocated memory - /// for reuse. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// a.insert(1, "a"); - /// a.clear(); - /// assert!(a.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - #[inline] - pub fn clear(&mut self) { - self.drain(); - } - /// Returns a reference to the value corresponding to the key. /// /// The key may be any borrowed form of the map's key type, but @@ -2379,10 +2381,7 @@ enum VacantEntryState<K, V, M> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> - where K: Eq + Hash, - S: BuildHasher -{ +impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> { type Item = (&'a K, &'a V); type IntoIter = Iter<'a, K, V>; @@ -2392,10 +2391,7 @@ impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> - where K: Eq + Hash, - S: BuildHasher -{ +impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> { type Item = (&'a K, &'a mut V); type IntoIter = IterMut<'a, K, V>; @@ -2405,10 +2401,7 @@ impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> } #[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S> IntoIterator for HashMap<K, V, S> - where K: Eq + Hash, - S: BuildHasher -{ +impl<K, V, S> IntoIterator for HashMap<K, V, S> { type Item = (K, V); type IntoIter = IntoIter<K, V>; diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs index bfd36a84563..46a5f26df63 100644 --- a/src/libstd/collections/hash/set.rs +++ b/src/libstd/collections/hash/set.rs @@ -149,6 +149,118 @@ impl<T: Hash + Eq> HashSet<T, RandomState> { } } +impl<T, S> HashSet<T, S> { + /// Returns the number of elements the set can hold without reallocating. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// let set: HashSet<i32> = HashSet::with_capacity(100); + /// assert!(set.capacity() >= 100); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn capacity(&self) -> usize { + self.map.capacity() + } + + /// An iterator visiting all elements in arbitrary order. + /// The iterator element type is `&'a T`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// let mut set = HashSet::new(); + /// set.insert("a"); + /// set.insert("b"); + /// + /// // Will print in an arbitrary order. + /// for x in set.iter() { + /// println!("{}", x); + /// } + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn iter(&self) -> Iter<T> { + Iter { iter: self.map.keys() } + } + + /// Returns the number of elements in the set. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut v = HashSet::new(); + /// assert_eq!(v.len(), 0); + /// v.insert(1); + /// assert_eq!(v.len(), 1); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn len(&self) -> usize { + self.map.len() + } + + /// Returns `true` if the set contains no elements. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut v = HashSet::new(); + /// assert!(v.is_empty()); + /// v.insert(1); + /// assert!(!v.is_empty()); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn is_empty(&self) -> bool { + self.map.is_empty() + } + + /// Clears the set, returning all elements in an iterator. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// assert!(!set.is_empty()); + /// + /// // print 1, 2, 3 in an arbitrary order + /// for i in set.drain() { + /// println!("{}", i); + /// } + /// + /// assert!(set.is_empty()); + /// ``` + #[inline] + #[stable(feature = "drain", since = "1.6.0")] + pub fn drain(&mut self) -> Drain<T> { + Drain { iter: self.map.drain() } + } + + /// Clears the set, removing all values. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut v = HashSet::new(); + /// v.insert(1); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn clear(&mut self) { + self.map.clear() + } +} + impl<T, S> HashSet<T, S> where T: Eq + Hash, S: BuildHasher @@ -225,21 +337,6 @@ impl<T, S> HashSet<T, S> self.map.hasher() } - /// Returns the number of elements the set can hold without reallocating. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// let set: HashSet<i32> = HashSet::with_capacity(100); - /// assert!(set.capacity() >= 100); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn capacity(&self) -> usize { - self.map.capacity() - } - /// Reserves capacity for at least `additional` more elements to be inserted /// in the `HashSet`. The collection may reserve more space to avoid /// frequent reallocations. @@ -310,27 +407,6 @@ impl<T, S> HashSet<T, S> self.map.shrink_to(min_capacity) } - /// An iterator visiting all elements in arbitrary order. - /// The iterator element type is `&'a T`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// let mut set = HashSet::new(); - /// set.insert("a"); - /// set.insert("b"); - /// - /// // Will print in an arbitrary order. - /// for x in set.iter() { - /// println!("{}", x); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter(&self) -> Iter<T> { - Iter { iter: self.map.keys() } - } - /// Visits the values representing the difference, /// i.e., the values that are in `self` but not in `other`. /// @@ -454,80 +530,6 @@ impl<T, S> HashSet<T, S> } } - /// Returns the number of elements in the set. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut v = HashSet::new(); - /// assert_eq!(v.len(), 0); - /// v.insert(1); - /// assert_eq!(v.len(), 1); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { - self.map.len() - } - - /// Returns `true` if the set contains no elements. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut v = HashSet::new(); - /// assert!(v.is_empty()); - /// v.insert(1); - /// assert!(!v.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { - self.map.is_empty() - } - - /// Clears the set, returning all elements in an iterator. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// assert!(!set.is_empty()); - /// - /// // print 1, 2, 3 in an arbitrary order - /// for i in set.drain() { - /// println!("{}", i); - /// } - /// - /// assert!(set.is_empty()); - /// ``` - #[inline] - #[stable(feature = "drain", since = "1.6.0")] - pub fn drain(&mut self) -> Drain<T> { - Drain { iter: self.map.drain() } - } - - /// Clears the set, removing all values. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut v = HashSet::new(); - /// v.insert(1); - /// v.clear(); - /// assert!(v.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn clear(&mut self) { - self.map.clear() - } - /// Returns `true` if the set contains a value. /// /// The value may be any borrowed form of the set's value type, but @@ -1066,10 +1068,7 @@ pub struct Union<'a, T: 'a, S: 'a> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T, S> IntoIterator for &'a HashSet<T, S> - where T: Eq + Hash, - S: BuildHasher -{ +impl<'a, T, S> IntoIterator for &'a HashSet<T, S> { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -1079,10 +1078,7 @@ impl<'a, T, S> IntoIterator for &'a HashSet<T, S> } #[stable(feature = "rust1", since = "1.0.0")] -impl<T, S> IntoIterator for HashSet<T, S> - where T: Eq + Hash, - S: BuildHasher -{ +impl<T, S> IntoIterator for HashSet<T, S> { type Item = T; type IntoIter = IntoIter<T>; |