Struct std::collections::tree_map::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<Q: Ord + BorrowFrom<K>>(&self, key: &Q) -> Option<&V>
Returns a reference to the value corresponding to the key.
The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.
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<Q: Ord + BorrowFrom<K>>(&self, key: &Q) -> bool
Returns true if the map contains a value for the specified key.
The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.
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<Q: Ord + BorrowFrom<K>>(&mut self, key: &Q) -> Option<&mut V>
Returns a mutable reference to the value corresponding to the key.
The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.
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<Q: Ord + BorrowFrom<K>>(&mut self, key: &Q) -> Option<V>
Removes a key from the map, returning the value at the key if the key was previously in the map.
The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.
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"));