// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
+//
+// ignore-lexer-test FIXME #15883
//! Unordered containers, implemented as hash-tables (`HashSet` and `HashMap` types)
/// Hood bucket stealing.
///
/// The hashes are all keyed by the task-local random number generator
-/// on creation by default, this means the ordering of the keys is
+/// on creation by default. This means that the ordering of the keys is
/// randomized, but makes the tables more resistant to
/// denial-of-service attacks (Hash DoS). This behaviour can be
/// overridden with one of the constructors.
///
/// # Example
///
-/// ```rust
+/// ```
/// use std::collections::HashMap;
///
/// // type inference lets us omit an explicit type signature (which
/// println!("{}: \"{}\"", *book, *review);
/// }
/// ```
+///
+/// The easiest way to use `HashMap` with a custom type is to derive `Eq` and `Hash`.
+/// We must also derive `PartialEq`.
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// #[deriving(Hash, Eq, PartialEq, Show)]
+/// struct Viking<'a> {
+/// name: &'a str,
+/// power: uint,
+/// }
+///
+/// let mut vikings = HashMap::new();
+///
+/// vikings.insert("Norway", Viking { name: "Einar", power: 9u });
+/// vikings.insert("Denmark", Viking { name: "Olaf", power: 4u });
+/// vikings.insert("Iceland", Viking { name: "Harald", power: 8u });
+///
+/// // Use derived implementation to print the vikings.
+/// for (land, viking) in vikings.iter() {
+/// println!("{} at {}", viking, land);
+/// }
+/// ```
#[deriving(Clone)]
pub struct HashMap<K, V, H = RandomSipHasher> {
// All hashes are keyed on these values, to prevent hash collision attacks.
// earlier.
return Some(retval);
}
-
- /// Like `pop`, but can operate on any type that is equivalent to a key.
- #[experimental]
- pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
- if self.table.size() == 0 {
- return None
- }
-
- let potential_new_size = self.table.size() - 1;
- self.make_some_room(potential_new_size);
-
- let starting_index = match self.search_equiv(k) {
- Some(idx) => idx,
- None => return None,
- };
-
- self.pop_internal(starting_index)
- }
}
impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H> {
- /// Return the number of elements in the map
+ /// Return the number of elements in the map.
fn len(&self) -> uint { self.table.size() }
}
impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
/// Create an empty HashMap.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map: HashMap<&str, int> = HashMap::new();
+ /// ```
#[inline]
pub fn new() -> HashMap<K, V, RandomSipHasher> {
HashMap::with_capacity(INITIAL_CAPACITY)
}
/// Creates an empty hash map with the given initial capacity.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
+ /// ```
#[inline]
pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
let hasher = RandomSipHasher::new();
/// Creates an empty hashmap which will use the given hasher to hash keys.
///
/// The creates map has the default initial capacity.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::hash::sip::SipHasher;
+ ///
+ /// let h = SipHasher::new();
+ /// let mut map = HashMap::with_hasher(h);
+ /// map.insert(1i, 2u);
+ /// ```
#[inline]
pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
HashMap::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
/// is designed to allow HashMaps to be resistant to attacks that
/// cause many collisions and very poor performance. Setting it
/// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::hash::sip::SipHasher;
+ ///
+ /// let h = SipHasher::new();
+ /// let mut map = HashMap::with_capacity_and_hasher(10, h);
+ /// map.insert(1i, 2u);
+ /// ```
#[inline]
pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
let cap = num::next_power_of_two(max(INITIAL_CAPACITY, capacity));
///
/// This function has no effect on the operational semantics of the
/// hashtable, only on performance.
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map: HashMap<&str, int> = HashMap::new();
+ /// map.reserve(10);
+ /// ```
pub fn reserve(&mut self, new_minimum_capacity: uint) {
let cap = num::next_power_of_two(
max(INITIAL_CAPACITY, new_minimum_capacity));
/// Return the value corresponding to the key in the map, or insert
/// and return the value if it doesn't exist.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map = HashMap::new();
+ ///
+ /// // Insert 1i with key "a"
+ /// assert_eq!(*map.find_or_insert("a", 1i), 1);
+ ///
+ /// // Find the existing key
+ /// assert_eq!(*map.find_or_insert("a", -2), 1);
+ /// ```
pub fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V {
self.find_with_or_insert_with(k, v, |_k, _v, _a| (), |_k, a| a)
}
/// Return the value corresponding to the key in the map, or create,
/// insert, and return a new value if it doesn't exist.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map = HashMap::new();
+ ///
+ /// // Insert 10 with key 2
+ /// assert_eq!(*map.find_or_insert_with(2i, |&key| 5 * key as uint), 10u);
+ ///
+ /// // Find the existing key
+ /// assert_eq!(*map.find_or_insert_with(2, |&key| key as uint), 10);
+ /// ```
pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&K| -> V)
-> &'a mut V {
self.find_with_or_insert_with(k, (), |_k, _v, _a| (), |k, _a| f(k))
/// Insert a key-value pair into the map if the key is not already present.
/// Otherwise, modify the existing value for the key.
/// Returns the new or modified value for the key.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map = HashMap::new();
+ ///
+ /// // Insert 2 with key "a"
+ /// assert_eq!(*map.insert_or_update_with("a", 2u, |_key, val| *val = 3), 2);
+ ///
+ /// // Update and return the existing value
+ /// assert_eq!(*map.insert_or_update_with("a", 9, |_key, val| *val = 7), 7);
+ /// assert_eq!(map.get(&"a"), &7);
+ /// ```
pub fn insert_or_update_with<'a>(
&'a mut self,
k: K,
/// insert and return a new value if it doesn't exist.
///
/// This method allows for all insertion behaviours of a hashmap;
- /// see methods like `insert`, `find_or_insert` and
- /// `insert_or_update_with` for less general and more friendly
- /// variations of this.
+ /// see methods like
+ /// [`insert`](../trait.MutableMap.html#tymethod.insert),
+ /// [`find_or_insert`](#method.find_or_insert) and
+ /// [`insert_or_update_with`](#method.insert_or_update_with)
+ /// for less general and more friendly variations of this.
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashMap;
///
/// // map some strings to vectors of strings
/// // new value based on the first letter of the key.
/// |key, already, new| {
/// if key.as_slice().starts_with("z") {
- /// already.unshift(new);
+ /// already.insert(0, new);
/// } else {
/// already.push(new);
/// }
}
}
- /// Retrieves a value for the given key, failing if the key is not present.
+ /// Retrieves a value for the given key.
+ /// See [`find`](../trait.Map.html#tymethod.find) for a non-failing alternative.
+ ///
+ /// # Failure
+ ///
+ /// Fails if the key is not present.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// assert_eq!(map.get(&"a"), &1);
+ /// ```
pub fn get<'a>(&'a self, k: &K) -> &'a V {
match self.find(k) {
Some(v) => v,
}
}
- /// Retrieves a (mutable) value for the given key, failing if the key is not present.
+ /// Retrieves a mutable value for the given key.
+ /// See [`find_mut`](../trait.MutableMap.html#tymethod.find_mut) for a non-failing alternative.
+ ///
+ /// # Failure
+ ///
+ /// Fails if the key is not present.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// {
+ /// // val will freeze map to prevent usage during its lifetime
+ /// let val = map.get_mut(&"a");
+ /// *val = 40;
+ /// }
+ /// assert_eq!(map.get(&"a"), &40);
+ ///
+ /// // A more direct way could be:
+ /// *map.get_mut(&"a") = -2;
+ /// assert_eq!(map.get(&"a"), &-2);
+ /// ```
pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
match self.find_mut(k) {
Some(v) => v,
/// Return true if the map contains a value for the specified key,
/// using equivalence.
+ ///
+ /// See [pop_equiv](#method.pop_equiv) for an extended example.
pub fn contains_key_equiv<Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
self.search_equiv(key).is_some()
}
/// Return the value corresponding to the key in the map, using
/// equivalence.
+ ///
+ /// See [pop_equiv](#method.pop_equiv) for an extended example.
pub fn find_equiv<'a, Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
match self.search_equiv(k) {
None => None,
}
}
+ /// Remove an equivalent key from the map, returning the value at the
+ /// key if the key was previously in the map.
+ ///
+ /// # Example
+ ///
+ /// This is a slightly silly example where we define the number's parity as
+ /// the equivalence class. It is important that the values hash the same,
+ /// which is why we override `Hash`.
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::hash::Hash;
+ /// use std::hash::sip::SipState;
+ ///
+ /// #[deriving(Eq, PartialEq)]
+ /// struct EvenOrOdd {
+ /// num: uint
+ /// };
+ ///
+ /// impl Hash for EvenOrOdd {
+ /// fn hash(&self, state: &mut SipState) {
+ /// let parity = self.num % 2;
+ /// parity.hash(state);
+ /// }
+ /// }
+ ///
+ /// impl Equiv<EvenOrOdd> for EvenOrOdd {
+ /// fn equiv(&self, other: &EvenOrOdd) -> bool {
+ /// self.num % 2 == other.num % 2
+ /// }
+ /// }
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(EvenOrOdd { num: 3 }, "foo");
+ ///
+ /// assert!(map.contains_key_equiv(&EvenOrOdd { num: 1 }));
+ /// assert!(!map.contains_key_equiv(&EvenOrOdd { num: 4 }));
+ ///
+ /// assert_eq!(map.find_equiv(&EvenOrOdd { num: 5 }), Some(&"foo"));
+ /// assert_eq!(map.find_equiv(&EvenOrOdd { num: 2 }), None);
+ ///
+ /// assert_eq!(map.pop_equiv(&EvenOrOdd { num: 1 }), Some("foo"));
+ /// assert_eq!(map.pop_equiv(&EvenOrOdd { num: 2 }), None);
+ ///
+ /// ```
+ #[experimental]
+ pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
+ if self.table.size() == 0 {
+ return None
+ }
+
+ let potential_new_size = self.table.size() - 1;
+ self.make_some_room(potential_new_size);
+
+ let starting_index = match self.search_equiv(k) {
+ Some(idx) => idx,
+ None => return None,
+ };
+
+ self.pop_internal(starting_index)
+ }
+
/// An iterator visiting all keys in arbitrary order.
- /// Iterator element type is &'a K.
+ /// Iterator element type is `&'a K`.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// map.insert("b", 2);
+ /// map.insert("c", 3);
+ ///
+ /// for key in map.keys() {
+ /// println!("{}", key);
+ /// }
+ /// ```
pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
self.iter().map(|(k, _v)| k)
}
/// An iterator visiting all values in arbitrary order.
- /// Iterator element type is &'a V.
+ /// Iterator element type is `&'a V`.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// map.insert("b", 2);
+ /// map.insert("c", 3);
+ ///
+ /// for key in map.values() {
+ /// println!("{}", key);
+ /// }
+ /// ```
pub fn values<'a>(&'a self) -> Values<'a, K, V> {
self.iter().map(|(_k, v)| v)
}
/// An iterator visiting all key-value pairs in arbitrary order.
- /// Iterator element type is (&'a K, &'a V).
+ /// Iterator element type is `(&'a K, &'a V)`.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// map.insert("b", 2);
+ /// map.insert("c", 3);
+ ///
+ /// for (key, val) in map.iter() {
+ /// println!("key: {} val: {}", key, val);
+ /// }
+ /// ```
pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
self.table.iter()
}
/// An iterator visiting all key-value pairs in arbitrary order,
/// with mutable references to the values.
- /// Iterator element type is (&'a K, &'a mut V).
+ /// Iterator element type is `(&'a K, &'a mut V)`.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// map.insert("b", 2);
+ /// map.insert("c", 3);
+ ///
+ /// // Update all values
+ /// for (_, val) in map.mut_iter() {
+ /// *val *= 2;
+ /// }
+ ///
+ /// for (key, val) in map.iter() {
+ /// println!("key: {} val: {}", key, val);
+ /// }
+ /// ```
pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
self.table.mut_iter()
}
/// Creates a consuming iterator, that is, one that moves each key-value
/// pair out of the map in arbitrary order. The map cannot be used after
/// calling this.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert("a", 1i);
+ /// map.insert("b", 2);
+ /// map.insert("c", 3);
+ ///
+ /// // Not possible with .iter()
+ /// let vec: Vec<(&str, int)> = map.move_iter().collect();
+ /// ```
pub fn move_iter(self) -> MoveEntries<K, V> {
self.table.move_iter().map(|(_, k, v)| (k, v))
}
}
impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
- /// Like `find`, but returns a copy of the value.
+ /// Return a copy of the value corresponding to the key.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<uint, String> = HashMap::new();
+ /// map.insert(1u, "foo".to_string());
+ /// let s: String = map.find_copy(&1).unwrap();
+ /// ```
pub fn find_copy(&self, k: &K) -> Option<V> {
self.find(k).map(|v| (*v).clone())
}
- /// Like `get`, but returns a copy of the value.
+ /// Return a copy of the value corresponding to the key.
+ ///
+ /// # Failure
+ ///
+ /// Fails if the key is not present.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<uint, String> = HashMap::new();
+ /// map.insert(1u, "foo".to_string());
+ /// let s: String = map.get_copy(&1);
+ /// ```
pub fn get_copy(&self, k: &K) -> V {
(*self.get(k)).clone()
}
///
/// # Example
///
-/// ```rust
+/// ```
/// use std::collections::HashSet;
///
/// // Type inference lets us omit an explicit type signature (which
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
/// let mut set: HashSet<int> = HashSet::new();
/// ```
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
/// let mut set: HashSet<int> = HashSet::with_capacity(10);
/// ```
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
/// let mut set: HashSet<int> = HashSet::new();
/// set.reserve(10);
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
- ///
/// let mut set = HashSet::new();
/// set.insert("a");
/// set.insert("b");
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
- ///
/// let mut set = HashSet::new();
/// set.insert("a".to_string());
/// set.insert("b".to_string());
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
- ///
/// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
/// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
///
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
- ///
/// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
/// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
///
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
- ///
/// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
/// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
///
///
/// # Example
///
- /// ```rust
+ /// ```
/// use std::collections::HashSet;
- ///
/// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
/// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
///
projects / rust.git / blobdiff