Struct std::collections::TreeMapExperimental
[-]
[+]
[src]
pub struct TreeMap<K, V> {
// some fields omitted
}This is implemented as an AA tree, which is a simplified variation of a red-black tree where red (horizontal) nodes can only be added as a right child. The time complexity is the same, and re-balancing operations are more frequent but also cheaper.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "bar"); map.insert(1i, "foo"); map.insert(3i, "quux"); // In ascending order by keys for (key, value) in map.iter() { println!("{}: {}", key, value); } // Prints 1, 2, 3 for key in map.keys() { println!("{}", key); } // Prints `foo`, `bar`, `quux` for key in map.values() { println!("{}", key); } map.remove(&1); assert_eq!(map.len(), 2); if !map.contains_key(&1) { println!("1 is no more"); } for key in range(0, 4) { match map.get(&key) { Some(val) => println!("{} has a value: {}", key, val), None => println!("{} not in map", key), } } map.clear(); assert!(map.is_empty()); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "bar"); map.insert(1i, "foo"); map.insert(3i, "quux"); // In ascending order by keys for (key, value) in map.iter() { println!("{}: {}", key, value); } // Prints 1, 2, 3 for key in map.keys() { println!("{}", key); } // Prints `foo`, `bar`, `quux` for key in map.values() { println!("{}", key); } map.remove(&1); assert_eq!(map.len(), 2); if !map.contains_key(&1) { println!("1 is no more"); } for key in range(0, 4) { match map.get(&key) { Some(val) => println!("{} has a value: {}", key, val), None => println!("{} not in map", key), } } map.clear(); assert!(map.is_empty());
The easiest way to use TreeMap with a custom type as keys is to implement Ord.
We must also implement PartialEq, Eq and PartialOrd.
use std::collections::TreeMap; // We need `Eq` and `PartialEq`, these can be derived. #[deriving(Eq, PartialEq)] struct Troll<'a> { name: &'a str, level: uint, } // Implement `Ord` and sort trolls by level. impl<'a> Ord for Troll<'a> { fn cmp(&self, other: &Troll) -> Ordering { // If we swap `self` and `other`, we get descending ordering. self.level.cmp(&other.level) } } // `PartialOrd` needs to be implemented as well. impl<'a> PartialOrd for Troll<'a> { fn partial_cmp(&self, other: &Troll) -> Option<Ordering> { Some(self.cmp(other)) } } // Use a map to store trolls, sorted by level, and track a list of // heroes slain. let mut trolls = TreeMap::new(); trolls.insert(Troll { name: "Orgarr", level: 2 }, vec!["King Karl"]); trolls.insert(Troll { name: "Blargarr", level: 3 }, vec!["Odd"]); trolls.insert(Troll { name: "Kron the Smelly One", level: 4 }, vec!["Omar the Brave", "Peter: Slayer of Trolls"]); trolls.insert(Troll { name: "Wartilda", level: 1 }, vec![]); println!("You are facing {} trolls!", trolls.len()); // Print the trolls, ordered by level with smallest level first for (troll, heroes) in trolls.iter() { let what = if heroes.len() == 1u { "hero" } else { "heroes" }; println!("level {}: '{}' has slain {} {}", troll.level, troll.name, heroes.len(), what); } // Kill all trolls trolls.clear(); assert_eq!(trolls.len(), 0);
Methods
impl<K: Ord, V> TreeMap<K, V>
fn new() -> TreeMap<K, V>
Creates an empty TreeMap.
Example
fn main() { use std::collections::TreeMap; let mut map: TreeMap<&str, int> = TreeMap::new(); }use std::collections::TreeMap; let mut map: TreeMap<&str, int> = TreeMap::new();
fn keys(&'a self) -> Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>
Gets a lazy iterator over the keys in the map, in ascending order.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print "a", "b", "c" in order. for x in map.keys() { println!("{}", x); } }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print "a", "b", "c" in order. for x in map.keys() { println!("{}", x); }
fn values(&'a self) -> Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>
Gets a lazy iterator over the values in the map, in ascending order with respect to the corresponding keys.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print 1, 2, 3 ordered by keys. for x in map.values() { println!("{}", x); } }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print 1, 2, 3 ordered by keys. for x in map.values() { println!("{}", x); }
fn iter(&'a self) -> Entries<'a, K, V>
Gets a lazy iterator over the key-value pairs in the map, in ascending order.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print contents in ascending order for (key, value) in map.iter() { println!("{}: {}", key, value); } }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print contents in ascending order for (key, value) in map.iter() { println!("{}: {}", key, value); }
fn rev_iter(&'a self) -> RevEntries<'a, K, V>
Gets a lazy reverse iterator over the key-value pairs in the map, in descending order.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print contents in descending order for (key, value) in map.rev_iter() { println!("{}: {}", key, value); } }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Print contents in descending order for (key, value) in map.rev_iter() { println!("{}: {}", key, value); }
fn iter_mut(&'a mut self) -> MutEntries<'a, K, V>
Gets a lazy forward iterator over the key-value pairs in the map, with the values being mutable.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Add 10 until we find "b" for (key, value) in map.iter_mut() { *value += 10; if key == &"b" { break } } assert_eq!(map.get(&"a"), Some(&11)); assert_eq!(map.get(&"b"), Some(&12)); assert_eq!(map.get(&"c"), Some(&3)); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Add 10 until we find "b" for (key, value) in map.iter_mut() { *value += 10; if key == &"b" { break } } assert_eq!(map.get(&"a"), Some(&11)); assert_eq!(map.get(&"b"), Some(&12)); assert_eq!(map.get(&"c"), Some(&3));
fn rev_iter_mut(&'a mut self) -> RevMutEntries<'a, K, V>
Gets a lazy reverse iterator over the key-value pairs in the map, with the values being mutable.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Add 10 until we find "b" for (key, value) in map.rev_iter_mut() { *value += 10; if key == &"b" { break } } assert_eq!(map.get(&"a"), Some(&1)); assert_eq!(map.get(&"b"), Some(&12)); assert_eq!(map.get(&"c"), Some(&13)); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Add 10 until we find "b" for (key, value) in map.rev_iter_mut() { *value += 10; if key == &"b" { break } } assert_eq!(map.get(&"a"), Some(&1)); assert_eq!(map.get(&"b"), Some(&12)); assert_eq!(map.get(&"c"), Some(&13));
fn into_iter(self) -> MoveEntries<K, V>
Gets a lazy iterator that consumes the treemap.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Not possible with a regular `.iter()` let vec: Vec<(&str, int)> = map.into_iter().collect(); assert_eq!(vec, vec![("a", 1), ("b", 2), ("c", 3)]); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert("a", 1i); map.insert("c", 3i); map.insert("b", 2i); // Not possible with a regular `.iter()` let vec: Vec<(&str, int)> = map.into_iter().collect(); assert_eq!(vec, vec![("a", 1), ("b", 2), ("c", 3)]);
fn len(&self) -> uint
Return the number of elements in the map.
Example
fn main() { use std::collections::TreeMap; let mut a = TreeMap::new(); assert_eq!(a.len(), 0); a.insert(1u, "a"); assert_eq!(a.len(), 1); }use std::collections::TreeMap; let mut a = TreeMap::new(); assert_eq!(a.len(), 0); a.insert(1u, "a"); assert_eq!(a.len(), 1);
fn is_empty(&self) -> bool
Return true if the map contains no elements.
Example
fn main() { use std::collections::TreeMap; let mut a = TreeMap::new(); assert!(a.is_empty()); a.insert(1u, "a"); assert!(!a.is_empty()); }use std::collections::TreeMap; let mut a = TreeMap::new(); assert!(a.is_empty()); a.insert(1u, "a"); assert!(!a.is_empty());
fn clear(&mut self)
Clears the map, removing all values.
Example
fn main() { use std::collections::TreeMap; let mut a = TreeMap::new(); a.insert(1u, "a"); a.clear(); assert!(a.is_empty()); }use std::collections::TreeMap; let mut a = TreeMap::new(); a.insert(1u, "a"); a.clear(); assert!(a.is_empty());
fn find(&self, key: &K) -> Option<&V>
Deprecated: Renamed to get.
fn get(&self, key: &K) -> Option<&V>
Returns a reference to the value corresponding to the key.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); assert_eq!(map.get(&1), Some(&"a")); assert_eq!(map.get(&2), None); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); assert_eq!(map.get(&1), Some(&"a")); assert_eq!(map.get(&2), None);
fn contains_key(&self, key: &K) -> bool
Returns true if the map contains a value for the specified key.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); assert_eq!(map.contains_key(&1), true); assert_eq!(map.contains_key(&2), false); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); assert_eq!(map.contains_key(&1), true); assert_eq!(map.contains_key(&2), false);
fn find_mut(&mut self, key: &K) -> Option<&mut V>
Deprecated: Renamed to get_mut.
fn get_mut(&mut self, key: &K) -> Option<&mut V>
Returns a mutable reference to the value corresponding to the key.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); match map.get_mut(&1) { Some(x) => *x = "b", None => (), } assert_eq!(map[1], "b"); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); match map.get_mut(&1) { Some(x) => *x = "b", None => (), } assert_eq!(map[1], "b");
fn swap(&mut self, key: K, value: V) -> Option<V>
Deprecated: Renamed to insert.
fn insert(&mut self, key: K, value: V) -> Option<V>
Inserts a key-value pair from the map. If the key already had a value
present in the map, that value is returned. Otherwise, None is returned.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); assert_eq!(map.insert(37u, "a"), None); assert_eq!(map.is_empty(), false); map.insert(37, "b"); assert_eq!(map.insert(37, "c"), Some("b")); assert_eq!(map[37], "c"); }use std::collections::TreeMap; let mut map = TreeMap::new(); assert_eq!(map.insert(37u, "a"), None); assert_eq!(map.is_empty(), false); map.insert(37, "b"); assert_eq!(map.insert(37, "c"), Some("b")); assert_eq!(map[37], "c");
fn pop(&mut self, key: &K) -> Option<V>
Deprecated: Renamed to remove.
fn remove(&mut self, key: &K) -> Option<V>
Removes a key from the map, returning the value at the key if the key was previously in the map.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); assert_eq!(map.remove(&1), Some("a")); assert_eq!(map.remove(&1), None); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(1u, "a"); assert_eq!(map.remove(&1), Some("a")); assert_eq!(map.remove(&1), None);
impl<K, V> TreeMap<K, V>
fn find_with(&self, f: |&K| -> Ordering) -> Option<&V>
Returns the value for which f(key) returns Equal. f is invoked
with current key and guides tree navigation. That means f should
be aware of natural ordering of the tree.
Example
fn main() { use collections::tree_map::TreeMap; fn get_headers() -> TreeMap<String, String> { let mut result = TreeMap::new(); result.insert("Content-Type".to_string(), "application/xml".to_string()); result.insert("User-Agent".to_string(), "Curl-Rust/0.1".to_string()); result } let headers = get_headers(); let ua_key = "User-Agent"; let ua = headers.find_with(|k| { ua_key.cmp(k.as_slice()) }); assert_eq!((*ua.unwrap()).as_slice(), "Curl-Rust/0.1"); }use collections::tree_map::TreeMap; fn get_headers() -> TreeMap<String, String> { let mut result = TreeMap::new(); result.insert("Content-Type".to_string(), "application/xml".to_string()); result.insert("User-Agent".to_string(), "Curl-Rust/0.1".to_string()); result } let headers = get_headers(); let ua_key = "User-Agent"; let ua = headers.find_with(|k| { ua_key.cmp(k.as_slice()) }); assert_eq!((*ua.unwrap()).as_slice(), "Curl-Rust/0.1");
fn find_with_mut(&'a mut self, f: |&K| -> Ordering) -> Option<&'a mut V>
Returns the value for which f(key) returns Equal. f is invoked
with current key and guides tree navigation. That means f should
be aware of natural ordering of the tree.
Example
fn main() { let mut t = collections::tree_map::TreeMap::new(); t.insert("Content-Type", "application/xml"); t.insert("User-Agent", "Curl-Rust/0.1"); let new_ua = "Safari/156.0"; match t.find_with_mut(|&k| "User-Agent".cmp(k)) { Some(x) => *x = new_ua, None => panic!(), } assert_eq!(t.get(&"User-Agent"), Some(&new_ua)); }let mut t = collections::tree_map::TreeMap::new(); t.insert("Content-Type", "application/xml"); t.insert("User-Agent", "Curl-Rust/0.1"); let new_ua = "Safari/156.0"; match t.find_with_mut(|&k| "User-Agent".cmp(k)) { Some(x) => *x = new_ua, None => panic!(), } assert_eq!(t.get(&"User-Agent"), Some(&new_ua));
impl<K: Ord, V> TreeMap<K, V>
fn lower_bound(&'a self, k: &K) -> Entries<'a, K, V>
Returns a lazy iterator to the first key-value pair whose key is not less than k
If all keys in map are less than k an empty iterator is returned.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.lower_bound(&4).next(), Some((&4, &"b"))); assert_eq!(map.lower_bound(&5).next(), Some((&6, &"c"))); assert_eq!(map.lower_bound(&10).next(), None); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.lower_bound(&4).next(), Some((&4, &"b"))); assert_eq!(map.lower_bound(&5).next(), Some((&6, &"c"))); assert_eq!(map.lower_bound(&10).next(), None);
fn upper_bound(&'a self, k: &K) -> Entries<'a, K, V>
Returns a lazy iterator to the first key-value pair whose key is greater than k
If all keys in map are less than or equal to k an empty iterator is returned.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.upper_bound(&4).next(), Some((&6, &"c"))); assert_eq!(map.upper_bound(&5).next(), Some((&6, &"c"))); assert_eq!(map.upper_bound(&10).next(), None); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.upper_bound(&4).next(), Some((&6, &"c"))); assert_eq!(map.upper_bound(&5).next(), Some((&6, &"c"))); assert_eq!(map.upper_bound(&10).next(), None);
fn lower_bound_mut(&'a mut self, k: &K) -> MutEntries<'a, K, V>
Returns a lazy value iterator to the first key-value pair (with
the value being mutable) whose key is not less than k.
If all keys in map are less than k an empty iterator is
returned.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.lower_bound_mut(&4).next(), Some((&4, &mut "b"))); assert_eq!(map.lower_bound_mut(&5).next(), Some((&6, &mut "c"))); assert_eq!(map.lower_bound_mut(&10).next(), None); for (key, value) in map.lower_bound_mut(&4) { *value = "changed"; } assert_eq!(map.get(&2), Some(&"a")); assert_eq!(map.get(&4), Some(&"changed")); assert_eq!(map.get(&6), Some(&"changed")); assert_eq!(map.get(&8), Some(&"changed")); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.lower_bound_mut(&4).next(), Some((&4, &mut "b"))); assert_eq!(map.lower_bound_mut(&5).next(), Some((&6, &mut "c"))); assert_eq!(map.lower_bound_mut(&10).next(), None); for (key, value) in map.lower_bound_mut(&4) { *value = "changed"; } assert_eq!(map.get(&2), Some(&"a")); assert_eq!(map.get(&4), Some(&"changed")); assert_eq!(map.get(&6), Some(&"changed")); assert_eq!(map.get(&8), Some(&"changed"));
fn upper_bound_mut(&'a mut self, k: &K) -> MutEntries<'a, K, V>
Returns a lazy iterator to the first key-value pair (with the
value being mutable) whose key is greater than k.
If all keys in map are less than or equal to k an empty iterator
is returned.
Example
fn main() { use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.upper_bound_mut(&4).next(), Some((&6, &mut "c"))); assert_eq!(map.upper_bound_mut(&5).next(), Some((&6, &mut "c"))); assert_eq!(map.upper_bound_mut(&10).next(), None); for (key, value) in map.upper_bound_mut(&4) { *value = "changed"; } assert_eq!(map.get(&2), Some(&"a")); assert_eq!(map.get(&4), Some(&"b")); assert_eq!(map.get(&6), Some(&"changed")); assert_eq!(map.get(&8), Some(&"changed")); }use std::collections::TreeMap; let mut map = TreeMap::new(); map.insert(2i, "a"); map.insert(4, "b"); map.insert(6, "c"); map.insert(8, "d"); assert_eq!(map.upper_bound_mut(&4).next(), Some((&6, &mut "c"))); assert_eq!(map.upper_bound_mut(&5).next(), Some((&6, &mut "c"))); assert_eq!(map.upper_bound_mut(&10).next(), None); for (key, value) in map.upper_bound_mut(&4) { *value = "changed"; } assert_eq!(map.get(&2), Some(&"a")); assert_eq!(map.get(&4), Some(&"b")); assert_eq!(map.get(&6), Some(&"changed")); assert_eq!(map.get(&8), Some(&"changed"));