use core::fmt::Debug;
use core::hash::{Hash, Hasher};
use core::iter::FromIterator;
+use core::marker::PhantomData;
use core::ops::Index;
use core::{fmt, intrinsics, mem, ptr};
Found(handle) => {
Some(OccupiedEntry {
handle: handle,
- length: &mut self.length
+ length: &mut self.length,
+ _marker: PhantomData,
}.remove_kv().0)
},
GoDown(_) => None
VacantEntry {
key: key,
handle: handle,
- length: &mut self.length
+ length: &mut self.length,
+ _marker: PhantomData,
}.insert(());
None
}
/// A mutable iterator over a sub-range of BTreeMap's entries.
pub struct RangeMut<'a, K: 'a, V: 'a> {
front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
- back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>
+ back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+
+ // Be invariant in `K` and `V`
+ _marker: PhantomData<&'a mut (K, V)>,
}
/// A view into a single entry in a map, which may either be vacant or occupied.
pub struct VacantEntry<'a, K: 'a, V: 'a> {
key: K,
handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
- length: &'a mut usize
+ length: &'a mut usize,
+
+ // Be invariant in `K` and `V`
+ _marker: PhantomData<&'a mut (K, V)>,
}
/// An occupied Entry.
marker::LeafOrInternal
>, marker::KV>,
- length: &'a mut usize
+ length: &'a mut usize,
+
+ // Be invariant in `K` and `V`
+ _marker: PhantomData<&'a mut (K, V)>,
}
impl<K: Ord, V> BTreeMap<K, V> {
///
/// If the map did not have this key present, `None` is returned.
///
- /// If the map did have this key present, the key is not updated, the
- /// value is updated and the old value is returned.
- /// See the [module-level documentation] for more.
+ /// If the map did have this key present, the value is updated, and the old
+ /// value is returned. The key is not updated, though; this matters for
+ /// types that can be `==` without being identical. See the [module-level
+ /// documentation] for more.
///
/// [module-level documentation]: index.html#insert-and-complex-keys
///
Found(handle) => {
Some(OccupiedEntry {
handle: handle,
- length: &mut self.length
+ length: &mut self.length,
+ _marker: PhantomData,
}.remove())
},
GoDown(_) => None
RangeMut {
front: front,
- back: back
+ back: back,
+ _marker: PhantomData
}
}
match search::search_tree(self.root.as_mut(), &key) {
Found(handle) => Occupied(OccupiedEntry {
handle: handle,
- length: &mut self.length
+ length: &mut self.length,
+ _marker: PhantomData,
}),
GoDown(handle) => Vacant(VacantEntry {
key: key,
handle: handle,
- length: &mut self.length
+ length: &mut self.length,
+ _marker: PhantomData,
})
}
}
}
impl<K, V> BTreeMap<K, V> {
- /// Gets an iterator over the entries of the map.
+ /// Gets an iterator over the entries of the map, sorted by key.
///
/// # Examples
///
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
- /// map.insert(1, "a");
- /// map.insert(2, "b");
/// map.insert(3, "c");
+ /// map.insert(2, "b");
+ /// map.insert(1, "a");
///
/// for (key, value) in map.iter() {
/// println!("{}: {}", key, value);
}
}
- /// Gets a mutable iterator over the entries of the map.
+ /// Gets a mutable iterator over the entries of the map, sorted by key.
///
/// # Examples
///
range: RangeMut {
front: first_leaf_edge(root1),
back: last_leaf_edge(root2),
+ _marker: PhantomData,
},
length: self.length
}
}
- /// Gets an iterator over the keys of the map.
+ /// Gets an iterator over the keys of the map, in sorted order.
///
/// # Examples
///
/// use std::collections::BTreeMap;
///
/// let mut a = BTreeMap::new();
- /// a.insert(1, "a");
/// a.insert(2, "b");
+ /// a.insert(1, "a");
///
/// let keys: Vec<_> = a.keys().cloned().collect();
/// assert_eq!(keys, [1, 2]);
Keys { inner: self.iter() }
}
- /// Gets an iterator over the values of the map.
+ /// Gets an iterator over the values of the map, in order by key.
///
/// # Examples
///
/// use std::collections::BTreeMap;
///
/// let mut a = BTreeMap::new();
- /// a.insert(1, "a");
- /// a.insert(2, "b");
+ /// a.insert(1, "hello");
+ /// a.insert(2, "goodbye");
///
/// let values: Vec<&str> = a.values().cloned().collect();
- /// assert_eq!(values, ["a", "b"]);
+ /// assert_eq!(values, ["hello", "goodbye"]);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn values<'a>(&'a self) -> Values<'a, K, V> {