Implement low-hanging fruit of collection conventions

* Renames/deprecates the simplest and most obvious methods
* Adds FIXME(conventions)s for outstanding work
* Marks "handled" methods as unstable

NOTE: the semantics of reserve and reserve_exact have changed!
Other methods have had their semantics changed as well, but in a
way that should obviously not typecheck if used incorrectly.

Lots of work and breakage to come, but this handles most of the core
APIs and most eggregious breakage. Future changes should *mostly* focus on
niche collections, APIs, or simply back-compat additions.

[breaking-change]

21 files changed, 1386 insertions, 1062 deletions

diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs
index 8481111ae91..c9d60077449 100644
--- a/src/libcollections/binary_heap.rs
+++ b/src/libcollections/binary_heap.rs
@@ -162,6 +162,8 @@ use core::ptr;
 use slice;
 use vec::Vec;
 
+// FIXME(conventions): implement into_iter
+
 /// A priority queue implemented with a binary heap.
 ///
 /// This will be a max-heap.
@@ -184,6 +186,7 @@ impl<T: Ord> BinaryHeap<T> {
     /// use std::collections::BinaryHeap;
     /// let pq: BinaryHeap<uint> = BinaryHeap::new();
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> BinaryHeap<T> { BinaryHeap{data: vec!(),} }
 
     /// Creates an empty `BinaryHeap` with a specific capacity.
@@ -197,6 +200,7 @@ impl<T: Ord> BinaryHeap<T> {
     /// use std::collections::BinaryHeap;
     /// let pq: BinaryHeap<uint> = BinaryHeap::with_capacity(10u);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(capacity: uint) -> BinaryHeap<T> {
         BinaryHeap { data: Vec::with_capacity(capacity) }
     }
@@ -234,6 +238,7 @@ impl<T: Ord> BinaryHeap<T> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> Items<'a, T> {
         Items { iter: self.data.iter() }
     }
@@ -268,10 +273,19 @@ impl<T: Ord> BinaryHeap<T> {
     /// let pq: BinaryHeap<uint> = BinaryHeap::with_capacity(100u);
     /// assert!(pq.capacity() >= 100u);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn capacity(&self) -> uint { self.data.capacity() }
 
-    /// Reserves capacity for exactly `n` elements in the `BinaryHeap`.
-    /// Do nothing if the capacity is already sufficient.
+    /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
+    /// given `BinaryHeap`. Does nothing if the capacity is already sufficient.
+    ///
+    /// Note that the allocator may give the collection more space than it requests. Therefore
+    /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
+    /// insertions are expected.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
     ///
     /// # Example
     ///
@@ -280,12 +294,17 @@ impl<T: Ord> BinaryHeap<T> {
     ///
     /// let mut pq: BinaryHeap<uint> = BinaryHeap::new();
     /// pq.reserve_exact(100u);
-    /// assert!(pq.capacity() == 100u);
+    /// assert!(pq.capacity() >= 100u);
     /// ```
-    pub fn reserve_exact(&mut self, n: uint) { self.data.reserve_exact(n) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve_exact(&mut self, additional: uint) { self.data.reserve_exact(additional) }
 
-    /// Reserves capacity for at least `n` elements in the `BinaryHeap`.
-    /// Do nothing if the capacity is already sufficient.
+    /// Reserves capacity for at least `additional` more elements to be inserted in the
+    /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
     ///
     /// # Example
     ///
@@ -296,8 +315,15 @@ impl<T: Ord> BinaryHeap<T> {
     /// pq.reserve(100u);
     /// assert!(pq.capacity() >= 100u);
     /// ```
-    pub fn reserve(&mut self, n: uint) {
-        self.data.reserve(n)
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve(&mut self, additional: uint) {
+        self.data.reserve(additional)
+    }
+
+    /// Discards as much additional capacity as possible.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn shrink_to_fit(&mut self) {
+        self.data.shrink_to_fit()
     }
 
     /// Removes the greatest item from a queue and returns it, or `None` if it
@@ -314,6 +340,7 @@ impl<T: Ord> BinaryHeap<T> {
     /// assert_eq!(pq.pop(), Some(1i));
     /// assert_eq!(pq.pop(), None);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn pop(&mut self) -> Option<T> {
         match self.data.pop() {
             None           => { None }
@@ -342,6 +369,7 @@ impl<T: Ord> BinaryHeap<T> {
     /// assert_eq!(pq.len(), 3);
     /// assert_eq!(pq.top(), Some(&5i));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn push(&mut self, item: T) {
         self.data.push(item);
         let new_len = self.len() - 1;
@@ -495,12 +523,15 @@ impl<T: Ord> BinaryHeap<T> {
     }
 
     /// Returns the length of the queue.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.data.len() }
 
     /// Returns true if the queue contains no elements
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Drops all items from the queue.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.data.truncate(0) }
 }
 
@@ -528,8 +559,7 @@ impl<T: Ord> Extendable<T> for BinaryHeap<T> {
     fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) {
         let (lower, _) = iter.size_hint();
 
-        let len = self.capacity();
-        self.reserve(len + lower);
+        self.reserve(lower);
 
         for elem in iter {
             self.push(elem);
diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs
index b7085c96aed..833cfc04c55 100644
--- a/src/libcollections/bit.rs
+++ b/src/libcollections/bit.rs
@@ -75,6 +75,8 @@ use std::hash;
 
 use vec::Vec;
 
+// FIXME(conventions): look, we just need to refactor this whole thing. Inside and out.
+
 type MatchWords<'a> = Chain<MaskWords<'a>, Skip<Take<Enumerate<Repeat<u32>>>>>;
 // Take two BitV's, and return iterators of their words, where the shorter one
 // has been padded with 0's
@@ -216,6 +218,7 @@ impl Bitv {
     /// use std::collections::Bitv;
     /// let mut bv = Bitv::new();
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> Bitv {
         Bitv { storage: Vec::new(), nbits: 0 }
     }
@@ -613,6 +616,7 @@ impl Bitv {
     /// bv.truncate(2);
     /// assert!(bv.eq_vec([false, true]));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn truncate(&mut self, len: uint) {
         if len < self.len() {
             self.nbits = len;
@@ -760,14 +764,17 @@ impl Bitv {
 
     /// Return the total number of bits in this vector
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.nbits }
 
     /// Returns true if there are no bits in this vector
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears all bits in this vector.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         for w in self.storage.iter_mut() { *w = 0u32; }
     }
@@ -849,8 +856,7 @@ impl Clone for Bitv {
     #[inline]
     fn clone_from(&mut self, source: &Bitv) {
         self.nbits = source.nbits;
-        self.storage.reserve(source.storage.len());
-        for (i, w) in self.storage.iter_mut().enumerate() { *w = source.storage[i]; }
+        self.storage.clone_from(&source.storage);
     }
 }
 
@@ -1052,6 +1058,7 @@ impl BitvSet {
     /// let mut s = BitvSet::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> BitvSet {
         BitvSet(Bitv::new())
     }
@@ -1067,6 +1074,7 @@ impl BitvSet {
     /// assert!(s.capacity() >= 100);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(nbits: uint) -> BitvSet {
         let bitv = Bitv::with_capacity(nbits, false);
         BitvSet::from_bitv(bitv)
@@ -1106,6 +1114,7 @@ impl BitvSet {
     /// assert!(s.capacity() >= 100);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn capacity(&self) -> uint {
         let &BitvSet(ref bitv) = self;
         bitv.capacity()
@@ -1212,6 +1221,7 @@ impl BitvSet {
     /// println!("new capacity: {}", s.capacity());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn shrink_to_fit(&mut self) {
         let &BitvSet(ref mut bitv) = self;
         // Obtain original length
@@ -1240,6 +1250,7 @@ impl BitvSet {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> BitPositions<'a> {
         BitPositions {set: self, next_idx: 0u}
     }
@@ -1262,6 +1273,7 @@ impl BitvSet {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
         TwoBitPositions {
             set: self,
@@ -1290,6 +1302,7 @@ impl BitvSet {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> {
         let min = cmp::min(self.capacity(), other.capacity());
         TwoBitPositions {
@@ -1326,6 +1339,7 @@ impl BitvSet {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
         TwoBitPositions {
             set: self,
@@ -1355,6 +1369,7 @@ impl BitvSet {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
         TwoBitPositions {
             set: self,
@@ -1473,6 +1488,7 @@ impl BitvSet {
 
     /// Return the number of set bits in this set.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint  {
         let &BitvSet(ref bitv) = self;
         bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones())
@@ -1480,6 +1496,7 @@ impl BitvSet {
 
     /// Returns whether there are no bits set in this set
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool {
         let &BitvSet(ref bitv) = self;
         bitv.storage.iter().all(|&n| n == 0)
@@ -1487,6 +1504,7 @@ impl BitvSet {
 
     /// Clears all bits in this set
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         let &BitvSet(ref mut bitv) = self;
         bitv.clear();
@@ -1494,6 +1512,7 @@ impl BitvSet {
 
     /// Returns `true` if this set contains the specified integer.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains(&self, value: &uint) -> bool {
         let &BitvSet(ref bitv) = self;
         *value < bitv.nbits && bitv.get(*value)
@@ -1502,12 +1521,14 @@ impl BitvSet {
     /// Returns `true` if the set has no elements in common with `other`.
     /// This is equivalent to checking for an empty intersection.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_disjoint(&self, other: &BitvSet) -> bool {
         self.intersection(other).next().is_none()
     }
 
     /// Returns `true` if the set is a subset of another.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_subset(&self, other: &BitvSet) -> bool {
         let &BitvSet(ref self_bitv) = self;
         let &BitvSet(ref other_bitv) = other;
@@ -1521,12 +1542,14 @@ impl BitvSet {
 
     /// Returns `true` if the set is a superset of another.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_superset(&self, other: &BitvSet) -> bool {
         other.is_subset(self)
     }
 
     /// Adds a value to the set. Returns `true` if the value was not already
     /// present in the set.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn insert(&mut self, value: uint) -> bool {
         if self.contains(&value) {
             return false;
@@ -1545,6 +1568,7 @@ impl BitvSet {
 
     /// Removes a value from the set. Returns `true` if the value was
     /// present in the set.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn remove(&mut self, value: &uint) -> bool {
         if !self.contains(value) {
             return false;
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index e3dfabfa295..9b644115f30 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -25,6 +25,8 @@ use core::fmt::Show;
 
 use ring_buf::RingBuf;
 
+// FIXME(conventions): implement bounded iterators
+
 /// A map based on a B-Tree.
 ///
 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
@@ -125,6 +127,7 @@ pub struct OccupiedEntry<'a, K:'a, V:'a> {
 
 impl<K: Ord, V> BTreeMap<K, V> {
     /// Makes a new empty BTreeMap with a reasonable choice for B.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> BTreeMap<K, V> {
         //FIXME(Gankro): Tune this as a function of size_of<K/V>?
         BTreeMap::with_b(6)
@@ -155,12 +158,19 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// a.clear();
     /// assert!(a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         let b = self.b;
         // avoid recursive destructors by manually traversing the tree
         for _ in mem::replace(self, BTreeMap::with_b(b)).into_iter() {};
     }
 
+    /// Deprecated: renamed to `get`.
+    #[deprecated = "renamed to `get`"]
+    pub fn find(&self, key: &K) -> Option<&V> {
+        self.get(key)
+    }
+
     // Searching in a B-Tree is pretty straightforward.
     //
     // Start at the root. Try to find the key in the current node. If we find it, return it.
@@ -178,10 +188,11 @@ impl<K: Ord, V> BTreeMap<K, V> {
     ///
     /// let mut map = BTreeMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.find(&1), Some(&"a"));
-    /// assert_eq!(map.find(&2), None);
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
     /// ```
-    pub fn find(&self, key: &K) -> Option<&V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, key: &K) -> Option<&V> {
         let mut cur_node = &self.root;
         loop {
             match cur_node.search(key) {
@@ -209,9 +220,15 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.contains_key(&1), true);
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
-    #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains_key(&self, key: &K) -> bool {
-        self.find(key).is_some()
+        self.get(key).is_some()
+    }
+
+    /// Deprecated: renamed to `get_mut`.
+    #[deprecated = "renamed to `get_mut`"]
+    pub fn find_mut(&mut self, key: &K) -> Option<&mut V> {
+        self.get_mut(key)
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
@@ -223,14 +240,15 @@ impl<K: Ord, V> BTreeMap<K, V> {
     ///
     /// let mut map = BTreeMap::new();
     /// map.insert(1u, "a");
-    /// match map.find_mut(&1) {
+    /// match map.get_mut(&1) {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
-    // See `find` for implementation notes, this is basically a copy-paste with mut's added
-    pub fn find_mut(&mut self, key: &K) -> Option<&mut V> {
+    // See `get` for implementation notes, this is basically a copy-paste with mut's added
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
         // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
         let mut temp_node = &mut self.root;
         loop {
@@ -248,6 +266,12 @@ impl<K: Ord, V> BTreeMap<K, V> {
         }
     }
 
+    /// Deprecated: renamed to `insert`.
+    #[deprecated = "renamed to `insert`"]
+    pub fn swap(&mut self, key: K, value: V) -> Option<V> {
+        self.insert(key, value)
+    }
+
     // Insertion in a B-Tree is a bit complicated.
     //
     // First we do the same kind of search described in `find`. But we need to maintain a stack of
@@ -283,14 +307,15 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// use std::collections::BTreeMap;
     ///
     /// let mut map = BTreeMap::new();
-    /// assert_eq!(map.swap(37u, "a"), None);
+    /// assert_eq!(map.insert(37u, "a"), None);
     /// assert_eq!(map.is_empty(), false);
     ///
     /// map.insert(37, "b");
-    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    pub fn swap(&mut self, key: K, mut value: V) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
         // This is a stack of rawptrs to nodes paired with indices, respectively
         // representing the nodes and edges of our search path. We have to store rawptrs
         // because as far as Rust is concerned, we can mutate aliased data with such a
@@ -338,25 +363,6 @@ impl<K: Ord, V> BTreeMap<K, V> {
         }
     }
 
-    /// Inserts a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Returns `true` if the key did
-    /// not already exist in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::BTreeMap;
-    ///
-    /// let mut map = BTreeMap::new();
-    /// assert_eq!(map.insert(2u, "value"), true);
-    /// assert_eq!(map.insert(2, "value2"), false);
-    /// assert_eq!(map[2], "value2");
-    /// ```
-    #[inline]
-    pub fn insert(&mut self, key: K, value: V) -> bool {
-        self.swap(key, value).is_none()
-    }
-
     // Deletion is the most complicated operation for a B-Tree.
     //
     // First we do the same kind of search described in
@@ -392,6 +398,12 @@ impl<K: Ord, V> BTreeMap<K, V> {
     //      the underflow handling process on the parent. If merging merges the last two children
     //      of the root, then we replace the root with the merged node.
 
+    /// Deprecated: renamed to `remove`.
+    #[deprecated = "renamed to `remove`"]
+    pub fn pop(&mut self, key: &K) -> Option<V> {
+        self.remove(key)
+    }
+
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     ///
@@ -402,10 +414,11 @@ impl<K: Ord, V> BTreeMap<K, V> {
     ///
     /// let mut map = BTreeMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.pop(&1), Some("a"));
-    /// assert_eq!(map.pop(&1), None);
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
     /// ```
-    pub fn pop(&mut self, key: &K) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, key: &K) -> Option<V> {
         // See `swap` for a more thorough description of the stuff going on in here
         let mut stack = stack::PartialSearchStack::new(self);
         loop {
@@ -426,24 +439,6 @@ impl<K: Ord, V> BTreeMap<K, V> {
             }
         }
     }
-
-    /// Removes a key-value pair from the map. Returns `true` if the key
-    /// was present in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::BTreeMap;
-    ///
-    /// let mut map = BTreeMap::new();
-    /// assert_eq!(map.remove(&1u), false);
-    /// map.insert(1, "a");
-    /// assert_eq!(map.remove(&1), true);
-    /// ```
-    #[inline]
-    pub fn remove(&mut self, key: &K) -> bool {
-        self.pop(key).is_some()
-    }
 }
 
 /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
@@ -793,13 +788,13 @@ impl<K: Show, V: Show> Show for BTreeMap<K, V> {
 
 impl<K: Ord, V> Index<K, V> for BTreeMap<K, V> {
     fn index(&self, key: &K) -> &V {
-        self.find(key).expect("no entry found for key")
+        self.get(key).expect("no entry found for key")
     }
 }
 
 impl<K: Ord, V> IndexMut<K, V> for BTreeMap<K, V> {
     fn index_mut(&mut self, key: &K) -> &mut V {
-        self.find_mut(key).expect("no entry found for key")
+        self.get_mut(key).expect("no entry found for key")
     }
 }
 
@@ -891,8 +886,8 @@ impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>>
 
             // Handle any operation on the left stack as necessary
             match op {
-                Push(item) => { self.left.push(item); },
-                Pop => { self.left.pop(); },
+                Push(item) => { self.left.push_back(item); },
+                Pop => { self.left.pop_back(); },
             }
         }
     }
@@ -933,8 +928,8 @@ impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>>
             };
 
             match op {
-                Push(item) => { self.right.push(item); },
-                Pop => { self.right.pop(); }
+                Push(item) => { self.right.push_back(item); },
+                Pop => { self.right.pop_back(); }
             }
         }
     }
@@ -1010,6 +1005,7 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
 
 impl<K, V> BTreeMap<K, V> {
     /// Gets an iterator over the entries of the map.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
         let len = self.len();
         Entries {
@@ -1023,6 +1019,7 @@ impl<K, V> BTreeMap<K, V> {
     }
 
     /// Gets a mutable iterator over the entries of the map.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, K, V> {
         let len = self.len();
         MutEntries {
@@ -1036,6 +1033,7 @@ impl<K, V> BTreeMap<K, V> {
     }
 
     /// Gets an owning iterator over the entries of the map.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveEntries<K, V> {
         let len = self.len();
         MoveEntries {
@@ -1049,11 +1047,13 @@ impl<K, V> BTreeMap<K, V> {
     }
 
     /// Gets an iterator over the keys of the map.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
         self.iter().map(|(k, _)| k)
     }
 
     /// Gets an iterator over the values of the map.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
         self.iter().map(|(_, v)| v)
     }
@@ -1070,6 +1070,7 @@ impl<K, V> BTreeMap<K, V> {
     /// a.insert(1u, "a");
     /// assert_eq!(a.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.length }
 
     /// Return true if the map contains no elements.
@@ -1084,6 +1085,7 @@ impl<K, V> BTreeMap<K, V> {
     /// a.insert(1u, "a");
     /// assert!(!a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 }
 
@@ -1137,40 +1139,40 @@ mod test {
         assert_eq!(map.len(), 0);
 
         for i in range(0, size) {
-            assert_eq!(map.swap(i, 10*i), None);
+            assert_eq!(map.insert(i, 10*i), None);
             assert_eq!(map.len(), i + 1);
         }
 
         for i in range(0, size) {
-            assert_eq!(map.find(&i).unwrap(), &(i*10));
+            assert_eq!(map.get(&i).unwrap(), &(i*10));
         }
 
         for i in range(size, size*2) {
-            assert_eq!(map.find(&i), None);
+            assert_eq!(map.get(&i), None);
         }
 
         for i in range(0, size) {
-            assert_eq!(map.swap(i, 100*i), Some(10*i));
+            assert_eq!(map.insert(i, 100*i), Some(10*i));
             assert_eq!(map.len(), size);
         }
 
         for i in range(0, size) {
-            assert_eq!(map.find(&i).unwrap(), &(i*100));
+            assert_eq!(map.get(&i).unwrap(), &(i*100));
         }
 
         for i in range(0, size/2) {
-            assert_eq!(map.pop(&(i*2)), Some(i*200));
+            assert_eq!(map.remove(&(i*2)), Some(i*200));
             assert_eq!(map.len(), size - i - 1);
         }
 
         for i in range(0, size/2) {
-            assert_eq!(map.find(&(2*i)), None);
-            assert_eq!(map.find(&(2*i+1)).unwrap(), &(i*200 + 100));
+            assert_eq!(map.get(&(2*i)), None);
+            assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
         }
 
         for i in range(0, size/2) {
-            assert_eq!(map.pop(&(2*i)), None);
-            assert_eq!(map.pop(&(2*i+1)), Some(i*200 + 100));
+            assert_eq!(map.remove(&(2*i)), None);
+            assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
             assert_eq!(map.len(), size/2 - i - 1);
         }
     }
@@ -1178,17 +1180,17 @@ mod test {
     #[test]
     fn test_basic_small() {
         let mut map = BTreeMap::new();
-        assert_eq!(map.pop(&1), None);
-        assert_eq!(map.find(&1), None);
-        assert_eq!(map.swap(1u, 1u), None);
-        assert_eq!(map.find(&1), Some(&1));
-        assert_eq!(map.swap(1, 2), Some(1));
-        assert_eq!(map.find(&1), Some(&2));
-        assert_eq!(map.swap(2, 4), None);
-        assert_eq!(map.find(&2), Some(&4));
-        assert_eq!(map.pop(&1), Some(2));
-        assert_eq!(map.pop(&2), Some(4));
-        assert_eq!(map.pop(&1), None);
+        assert_eq!(map.remove(&1), None);
+        assert_eq!(map.get(&1), None);
+        assert_eq!(map.insert(1u, 1u), None);
+        assert_eq!(map.get(&1), Some(&1));
+        assert_eq!(map.insert(1, 2), Some(1));
+        assert_eq!(map.get(&1), Some(&2));
+        assert_eq!(map.insert(2, 4), None);
+        assert_eq!(map.get(&2), Some(&4));
+        assert_eq!(map.remove(&1), Some(2));
+        assert_eq!(map.remove(&2), Some(4));
+        assert_eq!(map.remove(&1), None);
     }
 
     #[test]
@@ -1283,7 +1285,7 @@ mod test {
                 assert_eq!(view.set(100), 10);
             }
         }
-        assert_eq!(map.find(&1).unwrap(), &100);
+        assert_eq!(map.get(&1).unwrap(), &100);
         assert_eq!(map.len(), 6);
 
 
@@ -1295,7 +1297,7 @@ mod test {
                 *v *= 10;
             }
         }
-        assert_eq!(map.find(&2).unwrap(), &200);
+        assert_eq!(map.get(&2).unwrap(), &200);
         assert_eq!(map.len(), 6);
 
         // Existing key (take)
@@ -1305,7 +1307,7 @@ mod test {
                 assert_eq!(view.take(), 30);
             }
         }
-        assert_eq!(map.find(&3), None);
+        assert_eq!(map.get(&3), None);
         assert_eq!(map.len(), 5);
 
 
@@ -1316,7 +1318,7 @@ mod test {
                 assert_eq!(*view.set(1000), 1000);
             }
         }
-        assert_eq!(map.find(&10).unwrap(), &1000);
+        assert_eq!(map.get(&10).unwrap(), &1000);
         assert_eq!(map.len(), 6);
     }
 }
@@ -1374,7 +1376,7 @@ mod bench {
         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
         find_rand_n(100, &mut m, b,
                     |m, i| { m.insert(i, 1); },
-                    |m, i| { m.find(&i); });
+                    |m, i| { m.get(&i); });
     }
 
     #[bench]
@@ -1382,7 +1384,7 @@ mod bench {
         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
         find_rand_n(10_000, &mut m, b,
                     |m, i| { m.insert(i, 1); },
-                    |m, i| { m.find(&i); });
+                    |m, i| { m.get(&i); });
     }
 
     // Find seq
@@ -1391,7 +1393,7 @@ mod bench {
         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
         find_seq_n(100, &mut m, b,
                    |m, i| { m.insert(i, 1); },
-                   |m, i| { m.find(&i); });
+                   |m, i| { m.get(&i); });
     }
 
     #[bench]
@@ -1399,7 +1401,7 @@ mod bench {
         let mut m : BTreeMap<uint,uint> = BTreeMap::new();
         find_seq_n(10_000, &mut m, b,
                    |m, i| { m.insert(i, 1); },
-                   |m, i| { m.find(&i); });
+                   |m, i| { m.get(&i); });
     }
 
     fn bench_iter(b: &mut Bencher, size: uint) {
@@ -1407,7 +1409,7 @@ mod bench {
         let mut rng = weak_rng();
 
         for _ in range(0, size) {
-            map.swap(rng.gen(), rng.gen());
+            map.insert(rng.gen(), rng.gen());
         }
 
         b.iter(|| {
diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs
index 27752207b97..f6a3de11d13 100644
--- a/src/libcollections/btree/set.rs
+++ b/src/libcollections/btree/set.rs
@@ -20,6 +20,9 @@ use core::{iter, fmt};
 use core::iter::Peekable;
 use core::fmt::Show;
 
+// FIXME(conventions): implement bounded iterators
+// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
+
 /// A set based on a B-Tree.
 ///
 /// See BTreeMap's documentation for a detailed discussion of this collection's performance
@@ -61,6 +64,7 @@ pub struct UnionItems<'a, T:'a> {
 
 impl<T: Ord> BTreeSet<T> {
     /// Makes a new BTreeSet with a reasonable choice of B.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> BTreeSet<T> {
         BTreeSet { map: BTreeMap::new() }
     }
@@ -75,11 +79,13 @@ impl<T: Ord> BTreeSet<T> {
 
 impl<T> BTreeSet<T> {
     /// Gets an iterator over the BTreeSet's contents.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> Items<'a, T> {
         self.map.keys()
     }
 
     /// Gets an iterator for moving out the BtreeSet's contents.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveItems<T> {
         self.map.into_iter().map(|(k, _)| k)
     }
@@ -87,23 +93,27 @@ impl<T> BTreeSet<T> {
 
 impl<T: Ord> BTreeSet<T> {
     /// Visits the values representing the difference, in ascending order.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> DifferenceItems<'a, T> {
         DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
     }
 
     /// Visits the values representing the symmetric difference, in ascending order.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a BTreeSet<T>)
         -> SymDifferenceItems<'a, T> {
         SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
     }
 
     /// Visits the values representing the intersection, in ascending order.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>)
         -> IntersectionItems<'a, T> {
         IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()}
     }
 
     /// Visits the values representing the union, in ascending order.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> UnionItems<'a, T> {
         UnionItems{a: self.iter().peekable(), b: other.iter().peekable()}
     }
@@ -120,6 +130,7 @@ impl<T: Ord> BTreeSet<T> {
     /// v.insert(1i);
     /// assert_eq!(v.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns true if the set contains no elements
@@ -134,6 +145,7 @@ impl<T: Ord> BTreeSet<T> {
     /// v.insert(1i);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the set, removing all values.
@@ -148,6 +160,7 @@ impl<T: Ord> BTreeSet<T> {
     /// v.clear();
     /// assert!(v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         self.map.clear()
     }
@@ -163,8 +176,9 @@ impl<T: Ord> BTreeSet<T> {
     /// assert_eq!(set.contains(&1), true);
     /// assert_eq!(set.contains(&4), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains(&self, value: &T) -> bool {
-        self.map.find(value).is_some()
+        self.map.contains_key(value)
     }
 
     /// Returns `true` if the set has no elements in common with `other`.
@@ -184,6 +198,7 @@ impl<T: Ord> BTreeSet<T> {
     /// b.insert(1);
     /// assert_eq!(a.is_disjoint(&b), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool {
         self.intersection(other).next().is_none()
     }
@@ -204,6 +219,7 @@ impl<T: Ord> BTreeSet<T> {
     /// set.insert(4);
     /// assert_eq!(set.is_subset(&sup), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_subset(&self, other: &BTreeSet<T>) -> bool {
         // Stolen from TreeMap
         let mut x = self.iter();
@@ -248,6 +264,7 @@ impl<T: Ord> BTreeSet<T> {
     /// set.insert(2);
     /// assert_eq!(set.is_superset(&sub), true);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_superset(&self, other: &BTreeSet<T>) -> bool {
         other.is_subset(self)
     }
@@ -266,8 +283,9 @@ impl<T: Ord> BTreeSet<T> {
     /// assert_eq!(set.insert(2i), false);
     /// assert_eq!(set.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn insert(&mut self, value: T) -> bool {
-        self.map.insert(value, ())
+        self.map.insert(value, ()).is_none()
     }
 
     /// Removes a value from the set. Returns `true` if the value was
@@ -284,8 +302,9 @@ impl<T: Ord> BTreeSet<T> {
     /// assert_eq!(set.remove(&2), true);
     /// assert_eq!(set.remove(&2), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn remove(&mut self, value: &T) -> bool {
-        self.map.remove(value)
+        self.map.remove(value).is_some()
     }
 }
 
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index a1e286d1245..9d9955141df 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -195,6 +195,7 @@ impl<T> Default for DList<T> {
 impl<T> DList<T> {
     /// Creates an empty `DList`.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> DList<T> {
         DList{list_head: None, list_tail: Rawlink::none(), length: 0}
     }
@@ -209,9 +210,9 @@ impl<T> DList<T> {
     /// use std::collections::DList;
     ///
     /// let mut dl = DList::new();
-    /// dl.push(1i);
-    /// dl.push(2);
-    /// dl.push(3);
+    /// dl.push_back(1i);
+    /// dl.push_back(2);
+    /// dl.push_back(3);
     ///
     /// dl.rotate_forward();
     ///
@@ -236,9 +237,9 @@ impl<T> DList<T> {
     /// use std::collections::DList;
     ///
     /// let mut dl = DList::new();
-    /// dl.push(1i);
-    /// dl.push(2);
-    /// dl.push(3);
+    /// dl.push_back(1i);
+    /// dl.push_back(2);
+    /// dl.push_back(3);
     ///
     /// dl.rotate_backward();
     ///
@@ -264,10 +265,10 @@ impl<T> DList<T> {
     ///
     /// let mut a = DList::new();
     /// let mut b = DList::new();
-    /// a.push(1i);
-    /// a.push(2);
-    /// b.push(3i);
-    /// b.push(4);
+    /// a.push_back(1i);
+    /// a.push_back(2);
+    /// b.push_back(3i);
+    /// b.push_back(4);
     ///
     /// a.append(b);
     ///
@@ -305,10 +306,10 @@ impl<T> DList<T> {
     ///
     /// let mut a = DList::new();
     /// let mut b = DList::new();
-    /// a.push(1i);
-    /// a.push(2);
-    /// b.push(3i);
-    /// b.push(4);
+    /// a.push_back(1i);
+    /// a.push_back(2);
+    /// b.push_back(3i);
+    /// b.push_back(4);
     ///
     /// a.prepend(b);
     ///
@@ -333,10 +334,10 @@ impl<T> DList<T> {
     /// use std::collections::DList;
     ///
     /// let mut a: DList<int> = DList::new();
-    /// a.push(2i);
-    /// a.push(4);
-    /// a.push(7);
-    /// a.push(8);
+    /// a.push_back(2i);
+    /// a.push_back(4);
+    /// a.push_back(7);
+    /// a.push_back(8);
     ///
     /// // insert 11 before the first odd number in the list
     /// a.insert_when(11, |&e, _| e % 2 == 1);
@@ -387,12 +388,14 @@ impl<T> DList<T> {
 
     /// Provides a forward iterator.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> Items<'a, T> {
         Items{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
     }
 
     /// Provides a forward iterator with mutable references.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> {
         let head_raw = match self.list_head {
             Some(ref mut h) => Rawlink::some(&mut **h),
@@ -408,6 +411,7 @@ impl<T> DList<T> {
 
     /// Consumes the list into an iterator yielding elements by value.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveItems<T> {
         MoveItems{list: self}
     }
@@ -416,6 +420,7 @@ impl<T> DList<T> {
     ///
     /// This operation should compute in O(1) time.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool {
         self.list_head.is_none()
     }
@@ -424,6 +429,7 @@ impl<T> DList<T> {
     ///
     /// This operation should compute in O(1) time.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint {
         self.length
     }
@@ -432,6 +438,7 @@ impl<T> DList<T> {
     ///
     /// This operation should compute in O(n) time.
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         *self = DList::new()
     }
@@ -439,34 +446,39 @@ impl<T> DList<T> {
     /// Provides a reference to the front element, or `None` if the list is
     /// empty.
     #[inline]
-    pub fn front<'a>(&'a self) -> Option<&'a T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn front(&self) -> Option<&T> {
         self.list_head.as_ref().map(|head| &head.value)
     }
 
     /// Provides a mutable reference to the front element, or `None` if the list
     /// is empty.
     #[inline]
-    pub fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn front_mut(&mut self) -> Option<&mut T> {
         self.list_head.as_mut().map(|head| &mut head.value)
     }
 
     /// Provides a reference to the back element, or `None` if the list is
     /// empty.
     #[inline]
-    pub fn back<'a>(&'a self) -> Option<&'a T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn back(&self) -> Option<&T> {
         self.list_tail.resolve_immut().as_ref().map(|tail| &tail.value)
     }
 
     /// Provides a mutable reference to the back element, or `None` if the list
     /// is empty.
     #[inline]
-    pub fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn back_mut(&mut self) -> Option<&mut T> {
         self.list_tail.resolve().map(|tail| &mut tail.value)
     }
 
     /// Adds an element first in the list.
     ///
     /// This operation should compute in O(1) time.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn push_front(&mut self, elt: T) {
         self.push_front_node(box Node::new(elt))
     }
@@ -475,10 +487,17 @@ impl<T> DList<T> {
     /// empty.
     ///
     /// This operation should compute in O(1) time.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn pop_front(&mut self) -> Option<T> {
         self.pop_front_node().map(|box Node{value, ..}| value)
     }
 
+    /// Deprecated: Renamed to `push_back`.
+    #[deprecated = "Renamed to `push_back`"]
+    pub fn push(&mut self, elt: T) {
+        self.push_back(elt)
+    }
+
     /// Appends an element to the back of a list
     ///
     /// # Example
@@ -487,14 +506,21 @@ impl<T> DList<T> {
     /// use std::collections::DList;
     ///
     /// let mut d = DList::new();
-    /// d.push(1i);
-    /// d.push(3);
+    /// d.push_back(1i);
+    /// d.push_back(3);
     /// assert_eq!(3, *d.back().unwrap());
     /// ```
-    pub fn push(&mut self, elt: T) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn push_back(&mut self, elt: T) {
         self.push_back_node(box Node::new(elt))
     }
 
+    /// Deprecated: Renamed to `pop_back`.
+    #[deprecated = "Renamed to `pop_back`"]
+    pub fn pop(&mut self) -> Option<T> {
+        self.pop_back()
+    }
+
     /// Removes the last element from a list and returns it, or `None` if
     /// it is empty.
     ///
@@ -504,12 +530,13 @@ impl<T> DList<T> {
     /// use std::collections::DList;
     ///
     /// let mut d = DList::new();
-    /// assert_eq!(d.pop(), None);
-    /// d.push(1i);
-    /// d.push(3);
-    /// assert_eq!(d.pop(), Some(3));
+    /// assert_eq!(d.pop_back(), None);
+    /// d.push_back(1i);
+    /// d.push_back(3);
+    /// assert_eq!(d.pop_back(), Some(3));
     /// ```
-    pub fn pop(&mut self) -> Option<T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn pop_back(&mut self) -> Option<T> {
         self.pop_back_node().map(|box Node{value, ..}| value)
     }
 }
@@ -682,7 +709,7 @@ impl<A> Iterator<A> for MoveItems<A> {
 
 impl<A> DoubleEndedIterator<A> for MoveItems<A> {
     #[inline]
-    fn next_back(&mut self) -> Option<A> { self.list.pop() }
+    fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
 }
 
 impl<A> FromIterator<A> for DList<A> {
@@ -695,7 +722,7 @@ impl<A> FromIterator<A> for DList<A> {
 
 impl<A> Extendable<A> for DList<A> {
     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
-        for elt in iterator { self.push(elt); }
+        for elt in iterator { self.push_back(elt); }
     }
 }
 
@@ -801,21 +828,21 @@ mod tests {
     fn test_basic() {
         let mut m: DList<Box<int>> = DList::new();
         assert_eq!(m.pop_front(), None);
-        assert_eq!(m.pop(), None);
+        assert_eq!(m.pop_back(), None);
         assert_eq!(m.pop_front(), None);
         m.push_front(box 1);
         assert_eq!(m.pop_front(), Some(box 1));
-        m.push(box 2);
-        m.push(box 3);
+        m.push_back(box 2);
+        m.push_back(box 3);
         assert_eq!(m.len(), 2);
         assert_eq!(m.pop_front(), Some(box 2));
         assert_eq!(m.pop_front(), Some(box 3));
         assert_eq!(m.len(), 0);
         assert_eq!(m.pop_front(), None);
-        m.push(box 1);
-        m.push(box 3);
-        m.push(box 5);
-        m.push(box 7);
+        m.push_back(box 1);
+        m.push_back(box 3);
+        m.push_back(box 5);
+        m.push_back(box 7);
         assert_eq!(m.pop_front(), Some(box 1));
 
         let mut n = DList::new();
@@ -853,19 +880,19 @@ mod tests {
         {
             let mut m = DList::new();
             let mut n = DList::new();
-            n.push(2i);
+            n.push_back(2i);
             m.append(n);
             assert_eq!(m.len(), 1);
-            assert_eq!(m.pop(), Some(2));
+            assert_eq!(m.pop_back(), Some(2));
             check_links(&m);
         }
         {
             let mut m = DList::new();
             let n = DList::new();
-            m.push(2i);
+            m.push_back(2i);
             m.append(n);
             assert_eq!(m.len(), 1);
-            assert_eq!(m.pop(), Some(2));
+            assert_eq!(m.pop_back(), Some(2));
             check_links(&m);
         }
 
@@ -887,10 +914,10 @@ mod tests {
         {
             let mut m = DList::new();
             let mut n = DList::new();
-            n.push(2i);
+            n.push_back(2i);
             m.prepend(n);
             assert_eq!(m.len(), 1);
-            assert_eq!(m.pop(), Some(2));
+            assert_eq!(m.pop_back(), Some(2));
             check_links(&m);
         }
 
@@ -948,9 +975,9 @@ mod tests {
     #[test]
     fn test_iterator_clone() {
         let mut n = DList::new();
-        n.push(2i);
-        n.push(3);
-        n.push(4);
+        n.push_back(2i);
+        n.push_back(3);
+        n.push_back(4);
         let mut it = n.iter();
         it.next();
         let mut jt = it.clone();
@@ -1005,7 +1032,7 @@ mod tests {
         let mut n = DList::new();
         assert!(n.iter_mut().next().is_none());
         n.push_front(4i);
-        n.push(5);
+        n.push_back(5);
         let mut it = n.iter_mut();
         assert_eq!(it.size_hint(), (2, Some(2)));
         assert!(it.next().is_some());
@@ -1079,8 +1106,8 @@ mod tests {
         assert_eq!(n.pop_front(), Some(1));
 
         let mut m = DList::new();
-        m.push(2i);
-        m.push(4);
+        m.push_back(2i);
+        m.push_back(4);
         m.insert_ordered(3);
         check_links(&m);
         assert_eq!(vec![2,3,4], m.into_iter().collect::<Vec<int>>());
@@ -1117,7 +1144,7 @@ mod tests {
         assert!(n == m);
         n.push_front(1);
         assert!(n != m);
-        m.push(1);
+        m.push_back(1);
         assert!(n == m);
 
         let n = list_from([2i,3,4]);
@@ -1132,9 +1159,9 @@ mod tests {
 
       assert!(hash::hash(&x) == hash::hash(&y));
 
-      x.push(1i);
-      x.push(2);
-      x.push(3);
+      x.push_back(1i);
+      x.push_back(2);
+      x.push_back(3);
 
       y.push_front(3i);
       y.push_front(2);
@@ -1214,7 +1241,7 @@ mod tests {
             let r: u8 = rand::random();
             match r % 6 {
                 0 => {
-                    m.pop();
+                    m.pop_back();
                     v.pop();
                 }
                 1 => {
@@ -1226,7 +1253,7 @@ mod tests {
                     v.insert(0, -i);
                 }
                 3 | 5 | _ => {
-                    m.push(i);
+                    m.push_back(i);
                     v.push(i);
                 }
             }
@@ -1262,7 +1289,7 @@ mod tests {
     fn bench_push_back(b: &mut test::Bencher) {
         let mut m: DList<int> = DList::new();
         b.iter(|| {
-            m.push(0);
+            m.push_back(0);
         })
     }
 
@@ -1270,8 +1297,8 @@ mod tests {
     fn bench_push_back_pop_back(b: &mut test::Bencher) {
         let mut m: DList<int> = DList::new();
         b.iter(|| {
-            m.push(0);
-            m.pop();
+            m.push_back(0);
+            m.pop_back();
         })
     }
 
diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs
index bcae4fe68c9..454d4f1ca87 100644
--- a/src/libcollections/enum_set.rs
+++ b/src/libcollections/enum_set.rs
@@ -16,6 +16,10 @@
 use core::prelude::*;
 use core::fmt;
 
+// FIXME(conventions): implement BitXor
+// FIXME(contentions): implement union family of methods? (general design may be wrong here)
+// FIXME(conventions): implement len
+
 #[deriving(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 /// A specialized `Set` implementation to use enum types.
 pub struct EnumSet<E> {
@@ -47,34 +51,56 @@ pub trait CLike {
     fn from_uint(uint) -> Self;
 }
 
-fn bit<E:CLike>(e: E) -> uint {
+fn bit<E:CLike>(e: &E) -> uint {
     1 << e.to_uint()
 }
 
 impl<E:CLike> EnumSet<E> {
-    /// Returns an empty `EnumSet`.
+    /// Deprecated: Renamed to `new`.
+    #[deprecated = "Renamed to `new`"]
     pub fn empty() -> EnumSet<E> {
+        EnumSet::new()
+    }
+
+    /// Returns an empty `EnumSet`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn new() -> EnumSet<E> {
         EnumSet {bits: 0}
     }
 
     /// Returns true if the `EnumSet` is empty.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool {
         self.bits == 0
     }
 
+    pub fn clear(&mut self) {
+        self.bits = 0;
+    }
+
     /// Returns `true` if the `EnumSet` contains any enum of the given `EnumSet`.
+    /// Deprecated: Use `is_disjoint`.
+    #[deprecated = "Use `is_disjoint`"]
     pub fn intersects(&self, e: EnumSet<E>) -> bool {
-        (self.bits & e.bits) != 0
+        !self.is_disjoint(&e)
     }
 
-    /// Returns the intersection of both `EnumSets`.
-    pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
-        EnumSet {bits: self.bits & e.bits}
+    /// Returns `false` if the `EnumSet` contains any enum of the given `EnumSet`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn is_disjoint(&self, other: &EnumSet<E>) -> bool {
+        (self.bits & other.bits) == 0
     }
 
-    /// Returns `true` if a given `EnumSet` is included in an `EnumSet`.
-    pub fn contains(&self, e: EnumSet<E>) -> bool {
-        (self.bits & e.bits) == e.bits
+    /// Returns `true` if a given `EnumSet` is included in this `EnumSet`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn is_superset(&self, other: &EnumSet<E>) -> bool {
+        (self.bits & other.bits) == other.bits
+    }
+
+    /// Returns `true` if this `EnumSet` is included in the given `EnumSet`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn is_subset(&self, other: &EnumSet<E>) -> bool {
+        other.is_subset(self)
     }
 
     /// Returns the union of both `EnumSets`.
@@ -82,17 +108,47 @@ impl<E:CLike> EnumSet<E> {
         EnumSet {bits: self.bits | e.bits}
     }
 
-    /// Adds an enum to an `EnumSet`.
+    /// Returns the intersection of both `EnumSets`.
+    pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
+        EnumSet {bits: self.bits & e.bits}
+    }
+
+    /// Deprecated: Use `insert`.
+    #[deprecated = "Use `insert`"]
     pub fn add(&mut self, e: E) {
-        self.bits |= bit(e);
+        self.insert(e);
     }
 
-    /// Returns `true` if an `EnumSet` contains a given enum.
+    /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, e: E) -> bool {
+        let result = !self.contains(&e);
+        self.bits |= bit(&e);
+        result
+    }
+
+    /// Removes an enum from the EnumSet
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, e: &E) -> bool {
+        let result = self.contains(e);
+        self.bits &= !bit(e);
+        result
+    }
+
+    /// Deprecated: use `contains`.
+    #[deprecated = "use `contains"]
     pub fn contains_elem(&self, e: E) -> bool {
+        self.contains(&e)
+    }
+
+    /// Returns `true` if an `EnumSet` contains a given enum.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn contains(&self, e: &E) -> bool {
         (self.bits & bit(e)) != 0
     }
 
     /// Returns an iterator over an `EnumSet`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter(&self) -> Items<E> {
         Items::new(self.bits)
     }
@@ -174,18 +230,18 @@ mod test {
     }
 
     #[test]
-    fn test_empty() {
-        let e: EnumSet<Foo> = EnumSet::empty();
+    fn test_new() {
+        let e: EnumSet<Foo> = EnumSet::new();
         assert!(e.is_empty());
     }
 
     #[test]
     fn test_show() {
-        let mut e = EnumSet::empty();
+        let mut e = EnumSet::new();
         assert_eq!("{}", e.to_string().as_slice());
-        e.add(A);
+        e.insert(A);
         assert_eq!("{A}", e.to_string().as_slice());
-        e.add(C);
+        e.insert(C);
         assert_eq!("{A, C}", e.to_string().as_slice());
     }
 
@@ -194,75 +250,75 @@ mod test {
 
     #[test]
     fn test_two_empties_do_not_intersect() {
-        let e1: EnumSet<Foo> = EnumSet::empty();
-        let e2: EnumSet<Foo> = EnumSet::empty();
-        assert!(!e1.intersects(e2));
+        let e1: EnumSet<Foo> = EnumSet::new();
+        let e2: EnumSet<Foo> = EnumSet::new();
+        assert!(e1.is_disjoint(&e2));
     }
 
     #[test]
     fn test_empty_does_not_intersect_with_full() {
-        let e1: EnumSet<Foo> = EnumSet::empty();
+        let e1: EnumSet<Foo> = EnumSet::new();
 
-        let mut e2: EnumSet<Foo> = EnumSet::empty();
-        e2.add(A);
-        e2.add(B);
-        e2.add(C);
+        let mut e2: EnumSet<Foo> = EnumSet::new();
+        e2.insert(A);
+        e2.insert(B);
+        e2.insert(C);
 
-        assert!(!e1.intersects(e2));
+        assert!(e1.is_disjoint(&e2));
     }
 
     #[test]
     fn test_disjoint_intersects() {
-        let mut e1: EnumSet<Foo> = EnumSet::empty();
-        e1.add(A);
+        let mut e1: EnumSet<Foo> = EnumSet::new();
+        e1.insert(A);
 
-        let mut e2: EnumSet<Foo> = EnumSet::empty();
-        e2.add(B);
+        let mut e2: EnumSet<Foo> = EnumSet::new();
+        e2.insert(B);
 
-        assert!(!e1.intersects(e2));
+        assert!(e1.is_disjoint(&e2));
     }
 
     #[test]
     fn test_overlapping_intersects() {
-        let mut e1: EnumSet<Foo> = EnumSet::empty();
-        e1.add(A);
+        let mut e1: EnumSet<Foo> = EnumSet::new();
+        e1.insert(A);
 
-        let mut e2: EnumSet<Foo> = EnumSet::empty();
-        e2.add(A);
-        e2.add(B);
+        let mut e2: EnumSet<Foo> = EnumSet::new();
+        e2.insert(A);
+        e2.insert(B);
 
-        assert!(e1.intersects(e2));
+        assert!(!e1.is_disjoint(&e2));
     }
 
     ///////////////////////////////////////////////////////////////////////////
     // contains and contains_elem
 
     #[test]
-    fn test_contains() {
-        let mut e1: EnumSet<Foo> = EnumSet::empty();
-        e1.add(A);
+    fn test_superset() {
+        let mut e1: EnumSet<Foo> = EnumSet::new();
+        e1.insert(A);
 
-        let mut e2: EnumSet<Foo> = EnumSet::empty();
-        e2.add(A);
-        e2.add(B);
+        let mut e2: EnumSet<Foo> = EnumSet::new();
+        e2.insert(A);
+        e2.insert(B);
 
-        assert!(!e1.contains(e2));
-        assert!(e2.contains(e1));
+        assert!(!e1.is_superset(&e2));
+        assert!(e2.is_superset(&e1));
     }
 
     #[test]
-    fn test_contains_elem() {
-        let mut e1: EnumSet<Foo> = EnumSet::empty();
-        e1.add(A);
-        assert!(e1.contains_elem(A));
-        assert!(!e1.contains_elem(B));
-        assert!(!e1.contains_elem(C));
-
-        e1.add(A);
-        e1.add(B);
-        assert!(e1.contains_elem(A));
-        assert!(e1.contains_elem(B));
-        assert!(!e1.contains_elem(C));
+    fn test_contains() {
+        let mut e1: EnumSet<Foo> = EnumSet::new();
+        e1.insert(A);
+        assert!(e1.contains(&A));
+        assert!(!e1.contains(&B));
+        assert!(!e1.contains(&C));
+
+        e1.insert(A);
+        e1.insert(B);
+        assert!(e1.contains(&A));
+        assert!(e1.contains(&B));
+        assert!(!e1.contains(&C));
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -270,24 +326,24 @@ mod test {
 
     #[test]
     fn test_iterator() {
-        let mut e1: EnumSet<Foo> = EnumSet::empty();
+        let mut e1: EnumSet<Foo> = EnumSet::new();
 
         let elems: Vec<Foo> = e1.iter().collect();
         assert!(elems.is_empty())
 
-        e1.add(A);
+        e1.insert(A);
         let elems = e1.iter().collect();
         assert_eq!(vec![A], elems)
 
-        e1.add(C);
+        e1.insert(C);
         let elems = e1.iter().collect();
         assert_eq!(vec![A,C], elems)
 
-        e1.add(C);
+        e1.insert(C);
         let elems = e1.iter().collect();
         assert_eq!(vec![A,C], elems)
 
-        e1.add(B);
+        e1.insert(B);
         let elems = e1.iter().collect();
         assert_eq!(vec![A,B,C], elems)
     }
@@ -297,13 +353,13 @@ mod test {
 
     #[test]
     fn test_operators() {
-        let mut e1: EnumSet<Foo> = EnumSet::empty();
-        e1.add(A);
-        e1.add(C);
+        let mut e1: EnumSet<Foo> = EnumSet::new();
+        e1.insert(A);
+        e1.insert(C);
 
-        let mut e2: EnumSet<Foo> = EnumSet::empty();
-        e2.add(B);
-        e2.add(C);
+        let mut e2: EnumSet<Foo> = EnumSet::new();
+        e2.insert(B);
+        e2.insert(C);
 
         let e_union = e1 | e2;
         let elems = e_union.iter().collect();
diff --git a/src/libcollections/ring_buf.rs b/src/libcollections/ring_buf.rs
index 3c4c3fce61d..549ebb14b3e 100644
--- a/src/libcollections/ring_buf.rs
+++ b/src/libcollections/ring_buf.rs
@@ -27,6 +27,11 @@ use vec::Vec;
 static INITIAL_CAPACITY: uint = 8u; // 2^3
 static MINIMUM_CAPACITY: uint = 2u;
 
+// FIXME(conventions): implement shrink_to_fit. Awkward with the current design, but it should
+// be scrapped anyway. Defer to rewrite?
+// FIXME(conventions): implement into_iter
+
+
 /// `RingBuf` is a circular buffer that implements `Deque`.
 #[deriving(Clone)]
 pub struct RingBuf<T> {
@@ -42,11 +47,13 @@ impl<T> Default for RingBuf<T> {
 
 impl<T> RingBuf<T> {
     /// Creates an empty `RingBuf`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> RingBuf<T> {
         RingBuf::with_capacity(INITIAL_CAPACITY)
     }
 
     /// Creates an empty `RingBuf` with space for at least `n` elements.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(n: uint) -> RingBuf<T> {
         RingBuf{nelts: 0, lo: 0,
               elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)}
@@ -54,24 +61,51 @@ impl<T> RingBuf<T> {
 
     /// Retrieves an element in the `RingBuf` by index.
     ///
-    /// Fails if there is no element with the given index.
+    /// # Example
+    ///
+    /// ```rust
+    /// use std::collections::RingBuf;
+    ///
+    /// let mut buf = RingBuf::new();
+    /// buf.push_back(3i);
+    /// buf.push_back(4);
+    /// buf.push_back(5);
+    /// assert_eq!(buf.get(1).unwrap(), &4);
+    /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, i: uint) -> Option<&T> {
+        match self.elts.get(i) {
+            None => None,
+            Some(opt) => opt.as_ref(),
+        }
+    }
+
+    /// Retrieves an element in the `RingBuf` mutably by index.
     ///
     /// # Example
     ///
     /// ```rust
-    /// # #![allow(deprecated)]
     /// use std::collections::RingBuf;
     ///
     /// let mut buf = RingBuf::new();
-    /// buf.push(3i);
-    /// buf.push(4);
-    /// buf.push(5);
-    /// *buf.get_mut(1) = 7;
+    /// buf.push_back(3i);
+    /// buf.push_back(4);
+    /// buf.push_back(5);
+    /// match buf.get_mut(1) {
+    ///     None => {}
+    ///     Some(elem) => {
+    ///         *elem = 7;
+    ///     }
+    /// }
+    ///
     /// assert_eq!(buf[1], 7);
     /// ```
-    #[deprecated = "use indexing instead: `buf[index] = value`"]
-    pub fn get_mut(&mut self, i: uint) -> &mut T {
-        &mut self[i]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut(&mut self, i: uint) -> Option<&mut T> {
+        match self.elts.get_mut(i) {
+            None => None,
+            Some(opt) => opt.as_mut(),
+        }
     }
 
     /// Swaps elements at indices `i` and `j`.
@@ -86,9 +120,9 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut buf = RingBuf::new();
-    /// buf.push(3i);
-    /// buf.push(4);
-    /// buf.push(5);
+    /// buf.push_back(3i);
+    /// buf.push_back(4);
+    /// buf.push_back(5);
     /// buf.swap(0, 2);
     /// assert_eq!(buf[0], 5);
     /// assert_eq!(buf[2], 3);
@@ -107,21 +141,70 @@ impl<T> RingBuf<T> {
         raw_index(self.lo, self.elts.len(), idx)
     }
 
-    /// Reserves capacity for exactly `n` elements in the given `RingBuf`,
-    /// doing nothing if `self`'s capacity is already equal to or greater
-    /// than the requested capacity.
-    pub fn reserve_exact(&mut self, n: uint) {
-        self.elts.reserve_exact(n);
+    /// Returns the number of elements the `RingBuf` can hold without
+    /// reallocating.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::RingBuf;
+    ///
+    /// let buf: RingBuf<int> = RingBuf::with_capacity(10);
+    /// assert_eq!(buf.capacity(), 10);
+    /// ```
+    #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn capacity(&self) -> uint {
+        // FXIME(Gankro): not the actual usable capacity if you use reserve/reserve_exact
+        self.elts.capacity()
     }
 
-    /// Reserves capacity for at least `n` elements in the given `RingBuf`,
-    /// over-allocating in case the caller needs to reserve additional
-    /// space.
+    /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
+    /// given `RingBuf`. Does nothing if the capacity is already sufficient.
+    ///
+    /// Note that the allocator may give the collection more space than it requests. Therefore
+    /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
+    /// insertions are expected.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
     ///
-    /// Do nothing if `self`'s capacity is already equal to or greater
-    /// than the requested capacity.
-    pub fn reserve(&mut self, n: uint) {
-        self.elts.reserve(n);
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::RingBuf;
+    ///
+    /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
+    /// buf.reserve_exact(10);
+    /// assert!(buf.capacity() >= 11);
+    /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve_exact(&mut self, additional: uint) {
+        // FIXME(Gankro): this is just wrong. The ringbuf won't actually use this space
+        self.elts.reserve_exact(additional);
+    }
+
+    /// Reserves capacity for at least `additional` more elements to be inserted in the given
+    /// `Ringbuf`. The collection may reserve more space to avoid frequent reallocations.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::RingBuf;
+    ///
+    /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
+    /// buf.reserve(10);
+    /// assert!(buf.capacity() >= 11);
+    /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve(&mut self, additional: uint) {
+        // FIXME(Gankro): this is just wrong. The ringbuf won't actually use this space
+        self.elts.reserve(additional);
     }
 
     /// Returns a front-to-back iterator.
@@ -132,12 +215,13 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut buf = RingBuf::new();
-    /// buf.push(5i);
-    /// buf.push(3);
-    /// buf.push(4);
+    /// buf.push_back(5i);
+    /// buf.push_back(3);
+    /// buf.push_back(4);
     /// let b: &[_] = &[&5, &3, &4];
     /// assert_eq!(buf.iter().collect::<Vec<&int>>().as_slice(), b);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter(&self) -> Items<T> {
         Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()}
     }
@@ -150,15 +234,16 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut buf = RingBuf::new();
-    /// buf.push(5i);
-    /// buf.push(3);
-    /// buf.push(4);
+    /// buf.push_back(5i);
+    /// buf.push_back(3);
+    /// buf.push_back(4);
     /// for num in buf.iter_mut() {
     ///     *num = *num - 2;
     /// }
     /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
     /// assert_eq!(buf.iter_mut().collect::<Vec<&mut int>>()[], b);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut(&mut self) -> MutItems<T> {
         let start_index = raw_index(self.lo, self.elts.len(), 0);
         let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
@@ -197,9 +282,10 @@ impl<T> RingBuf<T> {
     ///
     /// let mut v = RingBuf::new();
     /// assert_eq!(v.len(), 0);
-    /// v.push(1i);
+    /// v.push_back(1i);
     /// assert_eq!(v.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.nelts }
 
     /// Returns true if the buffer contains no elements
@@ -214,6 +300,7 @@ impl<T> RingBuf<T> {
     /// v.push_front(1i);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the buffer, removing all values.
@@ -224,10 +311,11 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut v = RingBuf::new();
-    /// v.push(1i);
+    /// v.push_back(1i);
     /// v.clear();
     /// assert!(v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         for x in self.elts.iter_mut() { *x = None }
         self.nelts = 0;
@@ -245,10 +333,11 @@ impl<T> RingBuf<T> {
     /// let mut d = RingBuf::new();
     /// assert_eq!(d.front(), None);
     ///
-    /// d.push(1i);
-    /// d.push(2i);
+    /// d.push_back(1i);
+    /// d.push_back(2i);
     /// assert_eq!(d.front(), Some(&1i));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn front(&self) -> Option<&T> {
         if self.nelts > 0 { Some(&self[0]) } else { None }
     }
@@ -264,14 +353,15 @@ impl<T> RingBuf<T> {
     /// let mut d = RingBuf::new();
     /// assert_eq!(d.front_mut(), None);
     ///
-    /// d.push(1i);
-    /// d.push(2i);
+    /// d.push_back(1i);
+    /// d.push_back(2i);
     /// match d.front_mut() {
     ///     Some(x) => *x = 9i,
     ///     None => (),
     /// }
     /// assert_eq!(d.front(), Some(&9i));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn front_mut(&mut self) -> Option<&mut T> {
         if self.nelts > 0 { Some(&mut self[0]) } else { None }
     }
@@ -287,10 +377,11 @@ impl<T> RingBuf<T> {
     /// let mut d = RingBuf::new();
     /// assert_eq!(d.back(), None);
     ///
-    /// d.push(1i);
-    /// d.push(2i);
+    /// d.push_back(1i);
+    /// d.push_back(2i);
     /// assert_eq!(d.back(), Some(&2i));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn back(&self) -> Option<&T> {
         if self.nelts > 0 { Some(&self[self.nelts - 1]) } else { None }
     }
@@ -306,14 +397,15 @@ impl<T> RingBuf<T> {
     /// let mut d = RingBuf::new();
     /// assert_eq!(d.back(), None);
     ///
-    /// d.push(1i);
-    /// d.push(2i);
+    /// d.push_back(1i);
+    /// d.push_back(2i);
     /// match d.back_mut() {
     ///     Some(x) => *x = 9i,
     ///     None => (),
     /// }
     /// assert_eq!(d.back(), Some(&9i));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn back_mut(&mut self) -> Option<&mut T> {
         let nelts = self.nelts;
         if nelts > 0 { Some(&mut self[nelts - 1]) } else { None }
@@ -328,13 +420,14 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut d = RingBuf::new();
-    /// d.push(1i);
-    /// d.push(2i);
+    /// d.push_back(1i);
+    /// d.push_back(2i);
     ///
     /// assert_eq!(d.pop_front(), Some(1i));
     /// assert_eq!(d.pop_front(), Some(2i));
     /// assert_eq!(d.pop_front(), None);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn pop_front(&mut self) -> Option<T> {
         let result = self.elts[self.lo].take();
         if result.is_some() {
@@ -356,6 +449,7 @@ impl<T> RingBuf<T> {
     /// d.push_front(2i);
     /// assert_eq!(d.front(), Some(&2i));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn push_front(&mut self, t: T) {
         if self.nelts == self.elts.len() {
             grow(self.nelts, &mut self.lo, &mut self.elts);
@@ -367,6 +461,12 @@ impl<T> RingBuf<T> {
         self.nelts += 1u;
     }
 
+    /// Deprecated: Renamed to `push_back`.
+    #[deprecated = "Renamed to `push_back`"]
+    pub fn push(&mut self, t: T) {
+        self.push_back(t)
+    }
+
     /// Appends an element to the back of a buffer
     ///
     /// # Example
@@ -375,11 +475,12 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut buf = RingBuf::new();
-    /// buf.push(1i);
-    /// buf.push(3);
+    /// buf.push_back(1i);
+    /// buf.push_back(3);
     /// assert_eq!(3, *buf.back().unwrap());
     /// ```
-    pub fn push(&mut self, t: T) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn push_back(&mut self, t: T) {
         if self.nelts == self.elts.len() {
             grow(self.nelts, &mut self.lo, &mut self.elts);
         }
@@ -388,6 +489,12 @@ impl<T> RingBuf<T> {
         self.nelts += 1u;
     }
 
+    /// Deprecated: Renamed to `pop_back`.
+    #[deprecated = "Renamed to `pop_back`"]
+    pub fn pop(&mut self) -> Option<T> {
+        self.pop_back()
+    }
+
     /// Removes the last element from a buffer and returns it, or `None` if
     /// it is empty.
     ///
@@ -397,12 +504,13 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let mut buf = RingBuf::new();
-    /// assert_eq!(buf.pop(), None);
-    /// buf.push(1i);
-    /// buf.push(3);
-    /// assert_eq!(buf.pop(), Some(3));
+    /// assert_eq!(buf.pop_back(), None);
+    /// buf.push_back(1i);
+    /// buf.push_back(3);
+    /// assert_eq!(buf.pop_back(), Some(3));
     /// ```
-    pub fn pop(&mut self) -> Option<T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn pop_back(&mut self) -> Option<T> {
         if self.nelts > 0 {
             self.nelts -= 1;
             let hi = self.raw_index(self.nelts);
@@ -523,7 +631,7 @@ impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
 fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
     assert_eq!(nelts, elts.len());
     let lo = *loptr;
-    elts.reserve(nelts * 2);
+    elts.reserve_exact(nelts);
     let newlen = elts.capacity();
 
     /* fill with None */
@@ -630,7 +738,7 @@ impl<A> FromIterator<A> for RingBuf<A> {
 impl<A> Extendable<A> for RingBuf<A> {
     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
         for elt in iterator {
-            self.push(elt);
+            self.push_back(elt);
         }
     }
 }
@@ -666,9 +774,9 @@ mod tests {
         assert_eq!(d.len(), 0u);
         d.push_front(17i);
         d.push_front(42i);
-        d.push(137);
+        d.push_back(137);
         assert_eq!(d.len(), 3u);
-        d.push(137);
+        d.push_back(137);
         assert_eq!(d.len(), 4u);
         debug!("{}", d.front());
         assert_eq!(*d.front().unwrap(), 42);
@@ -677,21 +785,21 @@ mod tests {
         let mut i = d.pop_front();
         debug!("{}", i);
         assert_eq!(i, Some(42));
-        i = d.pop();
+        i = d.pop_back();
         debug!("{}", i);
         assert_eq!(i, Some(137));
-        i = d.pop();
+        i = d.pop_back();
         debug!("{}", i);
         assert_eq!(i, Some(137));
-        i = d.pop();
+        i = d.pop_back();
         debug!("{}", i);
         assert_eq!(i, Some(17));
         assert_eq!(d.len(), 0u);
-        d.push(3);
+        d.push_back(3);
         assert_eq!(d.len(), 1u);
         d.push_front(2);
         assert_eq!(d.len(), 2u);
-        d.push(4);
+        d.push_back(4);
         assert_eq!(d.len(), 3u);
         d.push_front(1);
         assert_eq!(d.len(), 4u);
@@ -711,22 +819,22 @@ mod tests {
         assert_eq!(deq.len(), 0);
         deq.push_front(a.clone());
         deq.push_front(b.clone());
-        deq.push(c.clone());
+        deq.push_back(c.clone());
         assert_eq!(deq.len(), 3);
-        deq.push(d.clone());
+        deq.push_back(d.clone());
         assert_eq!(deq.len(), 4);
         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
         assert_eq!(deq.pop_front().unwrap(), b.clone());
-        assert_eq!(deq.pop().unwrap(), d.clone());
-        assert_eq!(deq.pop().unwrap(), c.clone());
-        assert_eq!(deq.pop().unwrap(), a.clone());
+        assert_eq!(deq.pop_back().unwrap(), d.clone());
+        assert_eq!(deq.pop_back().unwrap(), c.clone());
+        assert_eq!(deq.pop_back().unwrap(), a.clone());
         assert_eq!(deq.len(), 0);
-        deq.push(c.clone());
+        deq.push_back(c.clone());
         assert_eq!(deq.len(), 1);
         deq.push_front(b.clone());
         assert_eq!(deq.len(), 2);
-        deq.push(d.clone());
+        deq.push_back(d.clone());
         assert_eq!(deq.len(), 3);
         deq.push_front(a.clone());
         assert_eq!(deq.len(), 4);
@@ -750,7 +858,7 @@ mod tests {
 
         let mut deq = RingBuf::new();
         for i in range(0u, 66) {
-            deq.push(i);
+            deq.push_back(i);
         }
 
         for i in range(0u, 66) {
@@ -788,7 +896,7 @@ mod tests {
     fn bench_push_back(b: &mut test::Bencher) {
         let mut deq = RingBuf::new();
         b.iter(|| {
-            deq.push(0i);
+            deq.push_back(0i);
         })
     }
 
@@ -861,17 +969,17 @@ mod tests {
     #[test]
     fn test_with_capacity() {
         let mut d = RingBuf::with_capacity(0);
-        d.push(1i);
+        d.push_back(1i);
         assert_eq!(d.len(), 1);
         let mut d = RingBuf::with_capacity(50);
-        d.push(1i);
+        d.push_back(1i);
         assert_eq!(d.len(), 1);
     }
 
     #[test]
     fn test_with_capacity_non_power_two() {
         let mut d3 = RingBuf::with_capacity(3);
-        d3.push(1i);
+        d3.push_back(1i);
 
         // X = None, | = lo
         // [|1, X, X]
@@ -880,20 +988,20 @@ mod tests {
         assert_eq!(d3.front(), None);
 
         // [X, |3, X]
-        d3.push(3);
+        d3.push_back(3);
         // [X, |3, 6]
-        d3.push(6);
+        d3.push_back(6);
         // [X, X, |6]
         assert_eq!(d3.pop_front(), Some(3));
 
         // Pushing the lo past half way point to trigger
         // the 'B' scenario for growth
         // [9, X, |6]
-        d3.push(9);
+        d3.push_back(9);
         // [9, 12, |6]
-        d3.push(12);
+        d3.push_back(12);
 
-        d3.push(15);
+        d3.push_back(15);
         // There used to be a bug here about how the
         // RingBuf made growth assumptions about the
         // underlying Vec which didn't hold and lead
@@ -912,25 +1020,25 @@ mod tests {
     #[test]
     fn test_reserve_exact() {
         let mut d = RingBuf::new();
-        d.push(0u64);
+        d.push_back(0u64);
         d.reserve_exact(50);
-        assert_eq!(d.elts.capacity(), 50);
+        assert!(d.capacity() >= 51);
         let mut d = RingBuf::new();
-        d.push(0u32);
+        d.push_back(0u32);
         d.reserve_exact(50);
-        assert_eq!(d.elts.capacity(), 50);
+        assert!(d.capacity() >= 51);
     }
 
     #[test]
     fn test_reserve() {
         let mut d = RingBuf::new();
-        d.push(0u64);
+        d.push_back(0u64);
         d.reserve(50);
-        assert_eq!(d.elts.capacity(), 64);
+        assert!(d.capacity() >= 64);
         let mut d = RingBuf::new();
-        d.push(0u32);
+        d.push_back(0u32);
         d.reserve(50);
-        assert_eq!(d.elts.capacity(), 64);
+        assert!(d.capacity() >= 64);
     }
 
     #[test]
@@ -948,7 +1056,7 @@ mod tests {
         assert_eq!(d.iter().size_hint(), (0, Some(0)));
 
         for i in range(0i, 5) {
-            d.push(i);
+            d.push_back(i);
         }
         {
             let b: &[_] = &[&0,&1,&2,&3,&4];
@@ -979,7 +1087,7 @@ mod tests {
         assert_eq!(d.iter().rev().next(), None);
 
         for i in range(0i, 5) {
-            d.push(i);
+            d.push_back(i);
         }
         {
             let b: &[_] = &[&4,&3,&2,&1,&0];
@@ -998,11 +1106,11 @@ mod tests {
         let mut d = RingBuf::with_capacity(3);
         assert!(d.iter_mut().rev().next().is_none());
 
-        d.push(1i);
-        d.push(2);
-        d.push(3);
+        d.push_back(1i);
+        d.push_back(2);
+        d.push_back(3);
         assert_eq!(d.pop_front(), Some(1));
-        d.push(4);
+        d.push_back(4);
 
         assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(),
                    vec!(4, 3, 2));
@@ -1075,13 +1183,13 @@ mod tests {
         let mut d = RingBuf::new();
         d.push_front(17i);
         d.push_front(42);
-        d.push(137);
-        d.push(137);
+        d.push_back(137);
+        d.push_back(137);
         assert_eq!(d.len(), 4u);
         let mut e = d.clone();
         assert_eq!(e.len(), 4u);
         while !d.is_empty() {
-            assert_eq!(d.pop(), e.pop());
+            assert_eq!(d.pop_back(), e.pop_back());
         }
         assert_eq!(d.len(), 0u);
         assert_eq!(e.len(), 0u);
@@ -1094,15 +1202,15 @@ mod tests {
         d.push_front(137i);
         d.push_front(17);
         d.push_front(42);
-        d.push(137);
+        d.push_back(137);
         let mut e = RingBuf::with_capacity(0);
-        e.push(42);
-        e.push(17);
-        e.push(137);
-        e.push(137);
+        e.push_back(42);
+        e.push_back(17);
+        e.push_back(137);
+        e.push_back(137);
         assert!(&e == &d);
-        e.pop();
-        e.push(0);
+        e.pop_back();
+        e.push_back(0);
         assert!(e != d);
         e.clear();
         assert!(e == RingBuf::new());
@@ -1113,15 +1221,15 @@ mod tests {
       let mut x = RingBuf::new();
       let mut y = RingBuf::new();
 
-      x.push(1i);
-      x.push(2);
-      x.push(3);
+      x.push_back(1i);
+      x.push_back(2);
+      x.push_back(3);
 
-      y.push(0i);
-      y.push(1i);
+      y.push_back(0i);
+      y.push_back(1i);
       y.pop_front();
-      y.push(2);
-      y.push(3);
+      y.push_back(2);
+      y.push_back(3);
 
       assert!(hash::hash(&x) == hash::hash(&y));
     }
@@ -1130,9 +1238,9 @@ mod tests {
     fn test_ord() {
         let x = RingBuf::new();
         let mut y = RingBuf::new();
-        y.push(1i);
-        y.push(2);
-        y.push(3);
+        y.push_back(1i);
+        y.push_back(2);
+        y.push_back(3);
         assert!(x < y);
         assert!(y > x);
         assert!(x <= x);
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index e4af5795e1c..13703d6fe95 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -1523,10 +1523,10 @@ mod tests {
     fn test_capacity() {
         let mut v = vec![0u64];
         v.reserve_exact(10u);
-        assert_eq!(v.capacity(), 10u);
+        assert!(v.capacity() >= 11u);
         let mut v = vec![0u32];
         v.reserve_exact(10u);
-        assert_eq!(v.capacity(), 10u);
+        assert!(v.capacity() >= 11u);
     }
 
     #[test]
@@ -2318,7 +2318,7 @@ mod bench {
                 v.set_len(1024);
             }
             for i in range(0u, 1024) {
-                *v.get_mut(i) = 0;
+                v[i] = 0;
             }
         });
     }
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index cdca0d10eed..bed14e933bf 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -76,6 +76,8 @@ pub use core::str::{truncate_utf16_at_nul, utf8_char_width, CharRange};
 pub use core::str::{Str, StrSlice};
 pub use unicode::str::{UnicodeStrSlice, Words, Graphemes, GraphemeIndices};
 
+// FIXME(conventions): ensure bit/char conventions are followed by str's API
+
 /*
 Section: Creating a string
 */
@@ -308,7 +310,7 @@ impl<'a> Iterator<char> for Recompositions<'a> {
                                             self.composee = Some(ch);
                                             return Some(k);
                                         }
-                                        self.buffer.push(ch);
+                                        self.buffer.push_back(ch);
                                         self.last_ccc = Some(ch_class);
                                     }
                                 }
@@ -322,7 +324,7 @@ impl<'a> Iterator<char> for Recompositions<'a> {
                                         self.state = Purging;
                                         return Some(k);
                                     }
-                                    self.buffer.push(ch);
+                                    self.buffer.push_back(ch);
                                     self.last_ccc = Some(ch_class);
                                     continue;
                                 }
@@ -332,7 +334,7 @@ impl<'a> Iterator<char> for Recompositions<'a> {
                                         continue;
                                     }
                                     None => {
-                                        self.buffer.push(ch);
+                                        self.buffer.push_back(ch);
                                         self.last_ccc = Some(ch_class);
                                     }
                                 }
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index b3c83ba5559..ff9bd039a7d 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -330,8 +330,8 @@ impl String {
 
         let mut buf = String::new();
         buf.push(ch);
-        let size = buf.len() * length;
-        buf.reserve(size);
+        let size = buf.len() * (length - 1);
+        buf.reserve_exact(size);
         for _ in range(1, length) {
             buf.push(ch)
         }
@@ -379,27 +379,23 @@ impl String {
     /// assert!(s.capacity() >= 10);
     /// ```
     #[inline]
-    #[unstable = "just implemented, needs to prove itself"]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn capacity(&self) -> uint {
         self.vec.capacity()
     }
 
-    /// Reserves capacity for at least `extra` additional bytes in this string buffer.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// let mut s = String::with_capacity(10);
-    /// let before = s.capacity();
-    /// s.reserve_additional(100);
-    /// assert!(s.capacity() - before >= 100);
-    /// ```
-    #[inline]
+    /// Deprecated: Renamed to `reserve`.
+    #[deprecated = "Renamed to `reserve`"]
     pub fn reserve_additional(&mut self, extra: uint) {
-        self.vec.reserve_additional(extra)
+        self.vec.reserve(extra)
     }
 
-    /// Reserves capacity for at least `capacity` bytes in this string buffer.
+    /// Reserves capacity for at least `additional` more bytes to be inserted in the given
+    /// `String`. The collection may reserve more space to avoid frequent reallocations.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
     ///
     /// # Example
     ///
@@ -409,22 +405,33 @@ impl String {
     /// assert!(s.capacity() >= 10);
     /// ```
     #[inline]
-    pub fn reserve(&mut self, capacity: uint) {
-        self.vec.reserve(capacity)
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve(&mut self, additional: uint) {
+        self.vec.reserve(additional)
     }
 
-    /// Reserves capacity for exactly `capacity` bytes in this string buffer.
+    /// Reserves the minimum capacity for exactly `additional` more bytes to be inserted in the
+    /// given `String`. Does nothing if the capacity is already sufficient.
+    ///
+    /// Note that the allocator may give the collection more space than it requests. Therefore
+    /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
+    /// insertions are expected.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
     ///
     /// # Example
     ///
     /// ```
     /// let mut s = String::new();
-    /// s.reserve_exact(10);
-    /// assert_eq!(s.capacity(), 10);
+    /// s.reserve(10);
+    /// assert!(s.capacity() >= 10);
     /// ```
     #[inline]
-    pub fn reserve_exact(&mut self, capacity: uint) {
-        self.vec.reserve_exact(capacity)
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve_exact(&mut self, additional: uint) {
+        self.vec.reserve_exact(additional)
     }
 
     /// Shrinks the capacity of this string buffer to match its length.
@@ -439,6 +446,7 @@ impl String {
     /// assert_eq!(s.capacity(), 3);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn shrink_to_fit(&mut self) {
         self.vec.shrink_to_fit()
     }
@@ -459,7 +467,7 @@ impl String {
     pub fn push(&mut self, ch: char) {
         let cur_len = self.len();
         // This may use up to 4 bytes.
-        self.vec.reserve_additional(4);
+        self.vec.reserve(4);
 
         unsafe {
             // Attempt to not use an intermediate buffer by just pushing bytes
@@ -590,7 +598,7 @@ impl String {
         let len = self.len();
         assert!(idx <= len);
         assert!(self.as_slice().is_char_boundary(idx));
-        self.vec.reserve_additional(4);
+        self.vec.reserve(4);
         let mut bits = [0, ..4];
         let amt = ch.encode_utf8(bits).unwrap();
 
diff --git a/src/libcollections/tree/map.rs b/src/libcollections/tree/map.rs
index 8e24eabfccf..ea1c37d036a 100644
--- a/src/libcollections/tree/map.rs
+++ b/src/libcollections/tree/map.rs
@@ -21,6 +21,9 @@ use std::hash::{Writer, Hash};
 
 use vec::Vec;
 
+// FIXME(conventions): implement bounded iterators
+// FIXME(conventions): replace rev_iter(_mut) by making iter(_mut) DoubleEnded
+
 /// 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
@@ -60,7 +63,7 @@ use vec::Vec;
 /// }
 ///
 /// for key in range(0, 4) {
-///     match map.find(&key) {
+///     match map.get(&key) {
 ///         Some(val) => println!("{} has a value: {}", key, val),
 ///         None => println!("{} not in map", key),
 ///     }
@@ -188,14 +191,14 @@ impl<K: Ord, V> Default for TreeMap<K,V> {
 impl<K: Ord, V> Index<K, V> for TreeMap<K, V> {
     #[inline]
     fn index<'a>(&'a self, i: &K) -> &'a V {
-        self.find(i).expect("no entry found for key")
+        self.get(i).expect("no entry found for key")
     }
 }
 
 impl<K: Ord, V> IndexMut<K, V> for TreeMap<K, V> {
     #[inline]
     fn index_mut<'a>(&'a mut self, i: &K) -> &'a mut V {
-        self.find_mut(i).expect("no entry found for key")
+        self.get_mut(i).expect("no entry found for key")
     }
 }
 
@@ -208,6 +211,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// use std::collections::TreeMap;
     /// let mut map: TreeMap<&str, int> = TreeMap::new();
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
 
     /// Gets a lazy iterator over the keys in the map, in ascending order.
@@ -226,6 +230,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
         self.iter().map(|(k, _v)| k)
     }
@@ -247,6 +252,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
         self.iter().map(|(_k, v)| v)
     }
@@ -267,6 +273,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     println!("{}: {}", key, value);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
         Entries {
             stack: vec!(),
@@ -314,10 +321,11 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     if key == &"b" { break }
     /// }
     ///
-    /// assert_eq!(map.find(&"a"), Some(&11));
-    /// assert_eq!(map.find(&"b"), Some(&12));
-    /// assert_eq!(map.find(&"c"), Some(&3));
+    /// assert_eq!(map.get(&"a"), Some(&11));
+    /// assert_eq!(map.get(&"b"), Some(&12));
+    /// assert_eq!(map.get(&"c"), Some(&3));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, K, V> {
         MutEntries {
             stack: vec!(),
@@ -345,15 +353,15 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     if key == &"b" { break }
     /// }
     ///
-    /// assert_eq!(map.find(&"a"), Some(&1));
-    /// assert_eq!(map.find(&"b"), Some(&12));
-    /// assert_eq!(map.find(&"c"), Some(&13));
+    /// assert_eq!(map.get(&"a"), Some(&1));
+    /// assert_eq!(map.get(&"b"), Some(&12));
+    /// assert_eq!(map.get(&"c"), Some(&13));
     /// ```
     pub fn rev_iter_mut<'a>(&'a mut self) -> RevMutEntries<'a, K, V> {
         RevMutEntries{iter: self.iter_mut()}
     }
 
-    /// Gets a lazy iterator that consumes the TreeMap.
+    /// Gets a lazy iterator that consumes the treemap.
     ///
     /// # Example
     ///
@@ -368,6 +376,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// let vec: Vec<(&str, int)> = map.into_iter().collect();
     /// assert_eq!(vec, vec![("a", 1), ("b", 2), ("c", 3)]);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveEntries<K, V> {
         let TreeMap { root, length } = self;
         let stk = match root {
@@ -392,6 +401,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// a.insert(1u, "a");
     /// assert_eq!(a.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.length }
 
     /// Return true if the map contains no elements.
@@ -406,6 +416,7 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// a.insert(1u, "a");
     /// assert!(!a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     #[inline]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
@@ -421,11 +432,18 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// a.clear();
     /// assert!(a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         self.root = None;
         self.length = 0
     }
 
+    /// Deprecated: Renamed to `get`.
+    #[deprecated = "Renamed to `get`"]
+    pub fn find(&self, key: &K) -> Option<&V> {
+        self.get(key)
+    }
+
     /// Returns a reference to the value corresponding to the key.
     ///
     /// # Example
@@ -435,11 +453,12 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///
     /// let mut map = TreeMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.find(&1), Some(&"a"));
-    /// assert_eq!(map.find(&2), None);
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
     /// ```
     #[inline]
-    pub fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, key: &K) -> Option<&V> {
         tree_find_with(&self.root, |k2| key.cmp(k2))
     }
 
@@ -456,8 +475,15 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains_key(&self, key: &K) -> bool {
-        self.find(key).is_some()
+        self.get(key).is_some()
+    }
+
+    /// Deprecated: Renamed to `get_mut`.
+    #[deprecated = "Renamed to `get_mut`"]
+    pub fn find_mut(&mut self, key: &K) -> Option<&mut V> {
+        self.get_mut(key)
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
@@ -469,52 +495,22 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///
     /// let mut map = TreeMap::new();
     /// map.insert(1u, "a");
-    /// match map.find_mut(&1) {
+    /// match map.get_mut(&1) {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
     #[inline]
-    pub fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
         tree_find_with_mut(&mut self.root, |x| key.cmp(x))
     }
 
-    /// Inserts a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Returns `true` if the key did
-    /// not already exist in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::TreeMap;
-    ///
-    /// let mut map = TreeMap::new();
-    /// assert_eq!(map.insert(2u, "value"), true);
-    /// assert_eq!(map.insert(2, "value2"), false);
-    /// assert_eq!(map[2], "value2");
-    /// ```
-    #[inline]
-    pub fn insert(&mut self, key: K, value: V) -> bool {
-        self.swap(key, value).is_none()
-    }
-
-    /// Removes a key-value pair from the map. Returns `true` if the key
-    /// was present in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::TreeMap;
-    ///
-    /// let mut map = TreeMap::new();
-    /// assert_eq!(map.remove(&1u), false);
-    /// map.insert(1, "a");
-    /// assert_eq!(map.remove(&1), true);
-    /// ```
-    #[inline]
-    pub fn remove(&mut self, key: &K) -> bool {
-        self.pop(key).is_some()
+    /// Deprecated: Renamed to `insert`.
+    #[deprecated = "Renamed to `insert`"]
+    pub fn swap(&mut self, key: K, value: V) -> Option<V> {
+        self.insert(key, value)
     }
 
     /// Inserts a key-value pair from the map. If the key already had a value
@@ -526,19 +522,26 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// use std::collections::TreeMap;
     ///
     /// let mut map = TreeMap::new();
-    /// assert_eq!(map.swap(37u, "a"), None);
+    /// assert_eq!(map.insert(37u, "a"), None);
     /// assert_eq!(map.is_empty(), false);
     ///
     /// map.insert(37, "b");
-    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    pub fn swap(&mut self, key: K, value: V) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
         let ret = insert(&mut self.root, key, value);
         if ret.is_none() { self.length += 1 }
         ret
     }
 
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, key: &K) -> Option<V> {
+        self.remove(key)
+    }
+
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     ///
@@ -549,10 +552,11 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///
     /// let mut map = TreeMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.pop(&1), Some("a"));
-    /// assert_eq!(map.pop(&1), None);
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
     /// ```
-    pub fn pop(&mut self, key: &K) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, key: &K) -> Option<V> {
         let ret = remove(&mut self.root, key);
         if ret.is_some() { self.length -= 1 }
         ret
@@ -567,7 +571,7 @@ impl<K, V> TreeMap<K, V> {
     /// # Example
     ///
     /// ```
-    /// use std::collections::TreeMap;
+    /// use collections::tree_map::TreeMap;
     ///
     /// fn get_headers() -> TreeMap<String, String> {
     ///     let mut result = TreeMap::new();
@@ -585,7 +589,7 @@ impl<K, V> TreeMap<K, V> {
     /// assert_eq!((*ua.unwrap()).as_slice(), "Curl-Rust/0.1");
     /// ```
     #[inline]
-    pub fn find_with<'a>(&'a self, f:|&K| -> Ordering) -> Option<&'a V> {
+    pub fn find_with(&self, f:|&K| -> Ordering) -> Option<&V> {
         tree_find_with(&self.root, f)
     }
 
@@ -596,9 +600,7 @@ impl<K, V> TreeMap<K, V> {
     /// # Example
     ///
     /// ```
-    /// use std::collections::TreeMap;
-    ///
-    /// let mut t = TreeMap::new();
+    /// let mut t = collections::tree_map::TreeMap::new();
     /// t.insert("Content-Type", "application/xml");
     /// t.insert("User-Agent", "Curl-Rust/0.1");
     ///
@@ -608,7 +610,7 @@ impl<K, V> TreeMap<K, V> {
     ///    None => panic!(),
     /// }
     ///
-    /// assert_eq!(t.find(&"User-Agent"), Some(&new_ua));
+    /// assert_eq!(t.get(&"User-Agent"), Some(&new_ua));
     /// ```
     #[inline]
     pub fn find_with_mut<'a>(&'a mut self, f:|&K| -> Ordering) -> Option<&'a mut V> {
@@ -742,10 +744,10 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     *value = "changed";
     /// }
     ///
-    /// assert_eq!(map.find(&2), Some(&"a"));
-    /// assert_eq!(map.find(&4), Some(&"changed"));
-    /// assert_eq!(map.find(&6), Some(&"changed"));
-    /// assert_eq!(map.find(&8), Some(&"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"));
     /// ```
     pub fn lower_bound_mut<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
         bound_setup!(self.iter_mut_for_traversal(), k, true)
@@ -776,10 +778,10 @@ impl<K: Ord, V> TreeMap<K, V> {
     ///     *value = "changed";
     /// }
     ///
-    /// assert_eq!(map.find(&2), Some(&"a"));
-    /// assert_eq!(map.find(&4), Some(&"b"));
-    /// assert_eq!(map.find(&6), Some(&"changed"));
-    /// assert_eq!(map.find(&8), Some(&"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"));
     /// ```
     pub fn upper_bound_mut<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> {
         bound_setup!(self.iter_mut_for_traversal(), k, false)
@@ -1287,16 +1289,16 @@ mod test_treemap {
     #[test]
     fn find_empty() {
         let m: TreeMap<int,int> = TreeMap::new();
-        assert!(m.find(&5) == None);
+        assert!(m.get(&5) == None);
     }
 
     #[test]
     fn find_not_found() {
         let mut m = TreeMap::new();
-        assert!(m.insert(1i, 2i));
-        assert!(m.insert(5i, 3i));
-        assert!(m.insert(9i, 3i));
-        assert_eq!(m.find(&2), None);
+        assert!(m.insert(1i, 2i).is_none());
+        assert!(m.insert(5i, 3i).is_none());
+        assert!(m.insert(9i, 3i).is_none());
+        assert_eq!(m.get(&2), None);
     }
 
     #[test]
@@ -1308,41 +1310,42 @@ mod test_treemap {
     #[test]
     fn find_with_not_found() {
         let mut m = TreeMap::new();
-        assert!(m.insert("test1", 2i));
-        assert!(m.insert("test2", 3i));
-        assert!(m.insert("test3", 3i));
+        assert!(m.insert("test1", 2i).is_none());
+        assert!(m.insert("test2", 3i).is_none());
+        assert!(m.insert("test3", 3i).is_none());
         assert_eq!(m.find_with(|&k| "test4".cmp(k)), None);
     }
 
     #[test]
     fn find_with_found() {
         let mut m = TreeMap::new();
-        assert!(m.insert("test1", 2i));
-        assert!(m.insert("test2", 3i));
-        assert!(m.insert("test3", 4i));
+        assert!(m.insert("test1", 2i).is_none());
+        assert!(m.insert("test2", 3i).is_none());
+        assert!(m.insert("test3", 4i).is_none());
         assert_eq!(m.find_with(|&k| "test2".cmp(k)), Some(&3i));
     }
 
     #[test]
     fn test_find_mut() {
         let mut m = TreeMap::new();
-        assert!(m.insert(1i, 12i));
-        assert!(m.insert(2, 8));
-        assert!(m.insert(5, 14));
+        assert!(m.insert(1i, 12i).is_none());
+        assert!(m.insert(2, 8).is_none());
+        assert!(m.insert(5, 14).is_none());
         let new = 100;
-        match m.find_mut(&5) {
+        match m.get_mut(&5) {
           None => panic!(), Some(x) => *x = new
         }
-        assert_eq!(m.find(&5), Some(&new));
+        assert_eq!(m.get(&5), Some(&new));
     }
 
     #[test]
     fn test_find_with_mut() {
         let mut m = TreeMap::new();
-        assert!(m.insert("t1", 12i));
-        assert!(m.insert("t2", 8));
-        assert!(m.insert("t5", 14));
+        assert!(m.insert("t1", 12i).is_none());
+        assert!(m.insert("t2", 8).is_none());
+        assert!(m.insert("t5", 14).is_none());
         let new = 100;
+
         match m.find_with_mut(|&k| "t5".cmp(k)) {
           None => panic!(), Some(x) => *x = new
         }
@@ -1352,23 +1355,23 @@ mod test_treemap {
     #[test]
     fn insert_replace() {
         let mut m = TreeMap::new();
-        assert!(m.insert(5i, 2i));
-        assert!(m.insert(2, 9));
-        assert!(!m.insert(2, 11));
-        assert_eq!(m.find(&2).unwrap(), &11);
+        assert!(m.insert(5i, 2i).is_none());
+        assert!(m.insert(2, 9).is_none());
+        assert!(!m.insert(2, 11).is_none());
+        assert_eq!(m.get(&2).unwrap(), &11);
     }
 
     #[test]
     fn test_clear() {
         let mut m = TreeMap::new();
         m.clear();
-        assert!(m.insert(5i, 11i));
-        assert!(m.insert(12, -3));
-        assert!(m.insert(19, 2));
+        assert!(m.insert(5i, 11i).is_none());
+        assert!(m.insert(12, -3).is_none());
+        assert!(m.insert(19, 2).is_none());
         m.clear();
-        assert!(m.find(&5).is_none());
-        assert!(m.find(&12).is_none());
-        assert!(m.find(&19).is_none());
+        assert!(m.get(&5).is_none());
+        assert!(m.get(&12).is_none());
+        assert!(m.get(&19).is_none());
         assert!(m.is_empty());
     }
 
@@ -1384,8 +1387,8 @@ mod test_treemap {
         m.insert(k1.clone(), v1.clone());
         m.insert(k2.clone(), v2.clone());
 
-        assert_eq!(m.find(&k2), Some(&v2));
-        assert_eq!(m.find(&k1), Some(&v1));
+        assert_eq!(m.get(&k2), Some(&v2));
+        assert_eq!(m.get(&k1), Some(&v1));
     }
 
     fn check_equal<K: PartialEq + Ord, V: PartialEq>(ctrl: &[(K, V)],
@@ -1393,7 +1396,7 @@ mod test_treemap {
         assert_eq!(ctrl.is_empty(), map.is_empty());
         for x in ctrl.iter() {
             let &(ref k, ref v) = x;
-            assert!(map.find(k).unwrap() == v)
+            assert!(map.get(k).unwrap() == v)
         }
         for (map_k, map_v) in map.iter() {
             let mut found = false;
@@ -1455,7 +1458,7 @@ mod test_treemap {
         let mut ctrl = vec![];
 
         check_equal(ctrl.as_slice(), &map);
-        assert!(map.find(&5).is_none());
+        assert!(map.get(&5).is_none());
 
         let seed: &[_] = &[42];
         let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed);
@@ -1465,7 +1468,7 @@ mod test_treemap {
                 let k = rng.gen();
                 let v = rng.gen();
                 if !ctrl.iter().any(|x| x == &(k, v)) {
-                    assert!(map.insert(k, v));
+                    assert!(map.insert(k, v).is_none());
                     ctrl.push((k, v));
                     check_structure(&map);
                     check_equal(ctrl.as_slice(), &map);
@@ -1475,7 +1478,7 @@ mod test_treemap {
             for _ in range(0u, 30) {
                 let r = rng.gen_range(0, ctrl.len());
                 let (key, _) = ctrl.remove(r).unwrap();
-                assert!(map.remove(&key));
+                assert!(map.remove(&key).is_some());
                 check_structure(&map);
                 check_equal(ctrl.as_slice(), &map);
             }
@@ -1485,19 +1488,19 @@ mod test_treemap {
     #[test]
     fn test_len() {
         let mut m = TreeMap::new();
-        assert!(m.insert(3i, 6i));
+        assert!(m.insert(3i, 6i).is_none());
         assert_eq!(m.len(), 1);
-        assert!(m.insert(0, 0));
+        assert!(m.insert(0, 0).is_none());
         assert_eq!(m.len(), 2);
-        assert!(m.insert(4, 8));
+        assert!(m.insert(4, 8).is_none());
         assert_eq!(m.len(), 3);
-        assert!(m.remove(&3));
+        assert!(m.remove(&3).is_some());
         assert_eq!(m.len(), 2);
-        assert!(!m.remove(&5));
+        assert!(!m.remove(&5).is_some());
         assert_eq!(m.len(), 2);
-        assert!(m.insert(2, 4));
+        assert!(m.insert(2, 4).is_none());
         assert_eq!(m.len(), 3);
-        assert!(m.insert(1, 2));
+        assert!(m.insert(1, 2).is_none());
         assert_eq!(m.len(), 4);
     }
 
@@ -1505,11 +1508,11 @@ mod test_treemap {
     fn test_iterator() {
         let mut m = TreeMap::new();
 
-        assert!(m.insert(3i, 6i));
-        assert!(m.insert(0, 0));
-        assert!(m.insert(4, 8));
-        assert!(m.insert(2, 4));
-        assert!(m.insert(1, 2));
+        assert!(m.insert(3i, 6i).is_none());
+        assert!(m.insert(0, 0).is_none());
+        assert!(m.insert(4, 8).is_none());
+        assert!(m.insert(2, 4).is_none());
+        assert!(m.insert(1, 2).is_none());
 
         let mut n = 0;
         for (k, v) in m.iter() {
@@ -1524,7 +1527,7 @@ mod test_treemap {
     fn test_interval_iteration() {
         let mut m = TreeMap::new();
         for i in range(1i, 100i) {
-            assert!(m.insert(i * 2, i * 4));
+            assert!(m.insert(i * 2, i * 4).is_none());
         }
 
         for i in range(1i, 198i) {
@@ -1548,11 +1551,11 @@ mod test_treemap {
     fn test_rev_iter() {
         let mut m = TreeMap::new();
 
-        assert!(m.insert(3i, 6i));
-        assert!(m.insert(0, 0));
-        assert!(m.insert(4, 8));
-        assert!(m.insert(2, 4));
-        assert!(m.insert(1, 2));
+        assert!(m.insert(3i, 6i).is_none());
+        assert!(m.insert(0, 0).is_none());
+        assert!(m.insert(4, 8).is_none());
+        assert!(m.insert(2, 4).is_none());
+        assert!(m.insert(1, 2).is_none());
 
         let mut n = 4;
         for (k, v) in m.rev_iter() {
@@ -1566,7 +1569,7 @@ mod test_treemap {
     fn test_mut_iter() {
         let mut m = TreeMap::new();
         for i in range(0u, 10) {
-            assert!(m.insert(i, 100 * i));
+            assert!(m.insert(i, 100 * i).is_none());
         }
 
         for (i, (&k, v)) in m.iter_mut().enumerate() {
@@ -1581,7 +1584,7 @@ mod test_treemap {
     fn test_mut_rev_iter() {
         let mut m = TreeMap::new();
         for i in range(0u, 10) {
-            assert!(m.insert(i, 100 * i));
+            assert!(m.insert(i, 100 * i).is_none());
         }
 
         for (i, (&k, v)) in m.rev_iter_mut().enumerate() {
@@ -1598,8 +1601,8 @@ mod test_treemap {
         let mut m_lower = TreeMap::new();
         let mut m_upper = TreeMap::new();
         for i in range(1i, 100i) {
-            assert!(m_lower.insert(i * 2, i * 4));
-            assert!(m_upper.insert(i * 2, i * 4));
+            assert!(m_lower.insert(i * 2, i * 4).is_none());
+            assert!(m_upper.insert(i * 2, i * 4).is_none());
         }
 
         for i in range(1i, 199) {
@@ -1653,15 +1656,15 @@ mod test_treemap {
         let mut b = TreeMap::new();
 
         assert!(a == b);
-        assert!(a.insert(0i, 5i));
+        assert!(a.insert(0i, 5i).is_none());
         assert!(a != b);
-        assert!(b.insert(0, 4));
+        assert!(b.insert(0, 4).is_none());
         assert!(a != b);
-        assert!(a.insert(5, 19));
+        assert!(a.insert(5, 19).is_none());
         assert!(a != b);
-        assert!(!b.insert(0, 5));
+        assert!(!b.insert(0, 5).is_none());
         assert!(a != b);
-        assert!(b.insert(5, 19));
+        assert!(b.insert(5, 19).is_none());
         assert!(a == b);
     }
 
@@ -1671,15 +1674,15 @@ mod test_treemap {
         let mut b = TreeMap::new();
 
         assert!(!(a < b) && !(b < a));
-        assert!(b.insert(0i, 5i));
+        assert!(b.insert(0i, 5i).is_none());
         assert!(a < b);
-        assert!(a.insert(0, 7));
+        assert!(a.insert(0, 7).is_none());
         assert!(!(a < b) && b < a);
-        assert!(b.insert(-2, 0));
+        assert!(b.insert(-2, 0).is_none());
         assert!(b < a);
-        assert!(a.insert(-5, 2));
+        assert!(a.insert(-5, 2).is_none());
         assert!(a < b);
-        assert!(a.insert(6, 2));
+        assert!(a.insert(6, 2).is_none());
         assert!(a < b && !(b < a));
     }
 
@@ -1689,10 +1692,10 @@ mod test_treemap {
         let mut b = TreeMap::new();
 
         assert!(a <= b && a >= b);
-        assert!(a.insert(1i, 1i));
+        assert!(a.insert(1i, 1i).is_none());
         assert!(a > b && a >= b);
         assert!(b < a && b <= a);
-        assert!(b.insert(2, 2));
+        assert!(b.insert(2, 2).is_none());
         assert!(b > a && b >= a);
         assert!(a < b && a <= b);
     }
@@ -1720,11 +1723,11 @@ mod test_treemap {
         let (x4, y4) = (29, 5);
         let (x5, y5) = (103, 3);
 
-        assert!(m.insert(x1, y1));
-        assert!(m.insert(x2, y2));
-        assert!(m.insert(x3, y3));
-        assert!(m.insert(x4, y4));
-        assert!(m.insert(x5, y5));
+        assert!(m.insert(x1, y1).is_none());
+        assert!(m.insert(x2, y2).is_none());
+        assert!(m.insert(x3, y3).is_none());
+        assert!(m.insert(x4, y4).is_none());
+        assert!(m.insert(x5, y5).is_none());
 
         let m = m;
         let mut a = m.iter();
@@ -1765,7 +1768,7 @@ mod test_treemap {
         let map: TreeMap<int, int> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
-            assert_eq!(map.find(&k), Some(&v));
+            assert_eq!(map.get(&k), Some(&v));
         }
     }
 
@@ -1795,17 +1798,17 @@ mod test_treemap {
     #[test]
     fn test_swap() {
         let mut m = TreeMap::new();
-        assert_eq!(m.swap(1u, 2i), None);
-        assert_eq!(m.swap(1u, 3i), Some(2));
-        assert_eq!(m.swap(1u, 4i), Some(3));
+        assert_eq!(m.insert(1u, 2i), None);
+        assert_eq!(m.insert(1u, 3i), Some(2));
+        assert_eq!(m.insert(1u, 4i), Some(3));
     }
 
     #[test]
     fn test_pop() {
         let mut m = TreeMap::new();
         m.insert(1u, 2i);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
+        assert_eq!(m.remove(&1), Some(2));
+        assert_eq!(m.remove(&1), None);
     }
 }
 
@@ -1857,7 +1860,7 @@ mod bench {
         let mut m : TreeMap<uint,uint> = TreeMap::new();
         find_rand_n(100, &mut m, b,
                     |m, i| { m.insert(i, 1); },
-                    |m, i| { m.find(&i); });
+                    |m, i| { m.get(&i); });
     }
 
     #[bench]
@@ -1865,7 +1868,7 @@ mod bench {
         let mut m : TreeMap<uint,uint> = TreeMap::new();
         find_rand_n(10_000, &mut m, b,
                     |m, i| { m.insert(i, 1); },
-                    |m, i| { m.find(&i); });
+                    |m, i| { m.get(&i); });
     }
 
     // Find seq
@@ -1874,7 +1877,7 @@ mod bench {
         let mut m : TreeMap<uint,uint> = TreeMap::new();
         find_seq_n(100, &mut m, b,
                    |m, i| { m.insert(i, 1); },
-                   |m, i| { m.find(&i); });
+                   |m, i| { m.get(&i); });
     }
 
     #[bench]
@@ -1882,7 +1885,7 @@ mod bench {
         let mut m : TreeMap<uint,uint> = TreeMap::new();
         find_seq_n(10_000, &mut m, b,
                    |m, i| { m.insert(i, 1); },
-                   |m, i| { m.find(&i); });
+                   |m, i| { m.get(&i); });
     }
 
     fn bench_iter(b: &mut Bencher, size: uint) {
@@ -1890,7 +1893,7 @@ mod bench {
         let mut rng = weak_rng();
 
         for _ in range(0, size) {
-            map.swap(rng.gen(), rng.gen());
+            map.insert(rng.gen(), rng.gen());
         }
 
         b.iter(|| {
diff --git a/src/libcollections/tree/set.rs b/src/libcollections/tree/set.rs
index d24a8234b20..22307a5d376 100644
--- a/src/libcollections/tree/set.rs
+++ b/src/libcollections/tree/set.rs
@@ -19,6 +19,10 @@ use std::hash::{Writer, Hash};
 
 use tree_map::{TreeMap, Entries, RevEntries, MoveEntries};
 
+// FIXME(conventions): implement bounded iterators
+// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
+// FIXME(conventions): replace rev_iter(_mut) by making iter(_mut) DoubleEnded
+
 /// An implementation of the `Set` trait on top of the `TreeMap` container. The
 /// only requirement is that the type of the elements contained ascribes to the
 /// `Ord` trait.
@@ -145,6 +149,7 @@ impl<T: Ord> TreeSet<T> {
     /// let mut set: TreeSet<int> = TreeSet::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} }
 
     /// Gets a lazy iterator over the values in the set, in ascending order.
@@ -161,6 +166,7 @@ impl<T: Ord> TreeSet<T> {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
         SetItems{iter: self.map.iter()}
     }
@@ -197,6 +203,7 @@ impl<T: Ord> TreeSet<T> {
     /// assert_eq!(v, vec![1, 2, 3, 4, 5]);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveSetItems<T> {
         self.map.into_iter().map(|(value, _)| value)
     }
@@ -261,6 +268,7 @@ impl<T: Ord> TreeSet<T> {
     /// let diff: TreeSet<int> = b.difference(&a).map(|&x| x).collect();
     /// assert_eq!(diff, [4, 5].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn difference<'a>(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T> {
         DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
     }
@@ -286,6 +294,7 @@ impl<T: Ord> TreeSet<T> {
     /// assert_eq!(diff1, diff2);
     /// assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a TreeSet<T>)
         -> SymDifferenceItems<'a, T> {
         SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()}
@@ -309,6 +318,7 @@ impl<T: Ord> TreeSet<T> {
     /// let diff: TreeSet<int> = a.intersection(&b).map(|&x| x).collect();
     /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn intersection<'a>(&'a self, other: &'a TreeSet<T>)
         -> IntersectionItems<'a, T> {
         IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()}
@@ -332,6 +342,7 @@ impl<T: Ord> TreeSet<T> {
     /// let diff: TreeSet<int> = a.union(&b).map(|&x| x).collect();
     /// assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> {
         UnionItems{a: self.iter().peekable(), b: other.iter().peekable()}
     }
@@ -349,6 +360,7 @@ impl<T: Ord> TreeSet<T> {
     /// assert_eq!(v.len(), 1);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns true if the set contains no elements
@@ -363,6 +375,7 @@ impl<T: Ord> TreeSet<T> {
     /// v.insert(1i);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the set, removing all values.
@@ -378,6 +391,7 @@ impl<T: Ord> TreeSet<T> {
     /// assert!(v.is_empty());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.map.clear() }
 
     /// Returns `true` if the set contains a value.
@@ -392,6 +406,7 @@ impl<T: Ord> TreeSet<T> {
     /// assert_eq!(set.contains(&4), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains(&self, value: &T) -> bool {
         self.map.contains_key(value)
     }
@@ -413,6 +428,7 @@ impl<T: Ord> TreeSet<T> {
     /// b.insert(1);
     /// assert_eq!(a.is_disjoint(&b), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_disjoint(&self, other: &TreeSet<T>) -> bool {
         self.intersection(other).next().is_none()
     }
@@ -433,6 +449,7 @@ impl<T: Ord> TreeSet<T> {
     /// set.insert(4);
     /// assert_eq!(set.is_subset(&sup), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_subset(&self, other: &TreeSet<T>) -> bool {
         let mut x = self.iter();
         let mut y = other.iter();
@@ -476,6 +493,7 @@ impl<T: Ord> TreeSet<T> {
     /// set.insert(2);
     /// assert_eq!(set.is_superset(&sub), true);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_superset(&self, other: &TreeSet<T>) -> bool {
         other.is_subset(self)
     }
@@ -495,7 +513,8 @@ impl<T: Ord> TreeSet<T> {
     /// assert_eq!(set.len(), 1);
     /// ```
     #[inline]
-    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 
     /// Removes a value from the set. Returns `true` if the value was
     /// present in the set.
@@ -512,7 +531,8 @@ impl<T: Ord> TreeSet<T> {
     /// assert_eq!(set.remove(&2), false);
     /// ```
     #[inline]
-    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value).is_some() }
 }
 
 /// A lazy forward iterator over a set.
diff --git a/src/libcollections/trie/map.rs b/src/libcollections/trie/map.rs
index 27486de6f19..d604e176a67 100644
--- a/src/libcollections/trie/map.rs
+++ b/src/libcollections/trie/map.rs
@@ -32,6 +32,10 @@ use std::hash::{Writer, Hash};
 use slice::{Items, MutItems};
 use slice;
 
+// FIXME(conventions): implement bounded iterators
+// FIXME(conventions): implement into_iter
+// FIXME(conventions): replace each_reverse by making iter DoubleEnded
+
 // FIXME: #5244: need to manually update the TrieNode constructor
 const SHIFT: uint = 4;
 const SIZE: uint = 1 << SHIFT;
@@ -59,14 +63,14 @@ enum Child<T> {
 /// map.insert(1, "Martin");
 ///
 /// assert_eq!(map.len(), 3);
-/// assert_eq!(map.find(&1), Some(&"Martin"));
+/// assert_eq!(map.get(&1), Some(&"Martin"));
 ///
 /// if !map.contains_key(&90) {
 ///     println!("Nobody is keyed 90");
 /// }
 ///
 /// // Update a key
-/// match map.find_mut(&1) {
+/// match map.get_mut(&1) {
 ///     Some(value) => *value = "Olga",
 ///     None => (),
 /// }
@@ -140,6 +144,7 @@ impl<T> TrieMap<T> {
     /// let mut map: TrieMap<&str> = TrieMap::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> TrieMap<T> {
         TrieMap{root: TrieNode::new(), length: 0}
     }
@@ -169,12 +174,14 @@ impl<T> TrieMap<T> {
 
     /// Gets an iterator visiting all keys in ascending order by the keys.
     /// The iterator's element type is `uint`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'r>(&'r self) -> Keys<'r, T> {
         self.iter().map(|(k, _v)| k)
     }
 
     /// Gets an iterator visiting all values in ascending order by the keys.
     /// The iterator's element type is `&'r T`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'r>(&'r self) -> Values<'r, T> {
         self.iter().map(|(_k, v)| v)
     }
@@ -191,6 +198,7 @@ impl<T> TrieMap<T> {
     ///     println!("{}: {}", key, value);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> Entries<'a, T> {
         let mut iter = unsafe {Entries::new()};
         iter.stack[0] = self.root.children.iter();
@@ -214,10 +222,11 @@ impl<T> TrieMap<T> {
     ///     *value = -(key as int);
     /// }
     ///
-    /// assert_eq!(map.find(&1), Some(&-1));
-    /// assert_eq!(map.find(&2), Some(&-2));
-    /// assert_eq!(map.find(&3), Some(&-3));
+    /// assert_eq!(map.get(&1), Some(&-1));
+    /// assert_eq!(map.get(&2), Some(&-2));
+    /// assert_eq!(map.get(&3), Some(&-3));
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, T> {
         let mut iter = unsafe {MutEntries::new()};
         iter.stack[0] = self.root.children.iter_mut();
@@ -241,6 +250,7 @@ impl<T> TrieMap<T> {
     /// assert_eq!(a.len(), 1);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.length }
 
     /// Return true if the map contains no elements.
@@ -256,6 +266,7 @@ impl<T> TrieMap<T> {
     /// assert!(!a.is_empty());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the map, removing all values.
@@ -271,11 +282,18 @@ impl<T> TrieMap<T> {
     /// assert!(a.is_empty());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         self.root = TrieNode::new();
         self.length = 0;
     }
 
+    /// Deprecated: renamed to `get`.
+    #[deprecated = "renamed to `get`"]
+    pub fn find(&self, key: &uint) -> Option<&T> {
+        self.get(key)
+    }
+
     /// Returns a reference to the value corresponding to the key.
     ///
     /// # Example
@@ -285,12 +303,13 @@ impl<T> TrieMap<T> {
     ///
     /// let mut map = TrieMap::new();
     /// map.insert(1, "a");
-    /// assert_eq!(map.find(&1), Some(&"a"));
-    /// assert_eq!(map.find(&2), None);
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
     /// ```
     #[inline]
-    pub fn find<'a>(&'a self, key: &uint) -> Option<&'a T> {
-        let mut node: &'a TrieNode<T> = &self.root;
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, key: &uint) -> Option<&T> {
+        let mut node = &self.root;
         let mut idx = 0;
         loop {
             match node.children[chunk(*key, idx)] {
@@ -321,8 +340,15 @@ impl<T> TrieMap<T> {
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains_key(&self, key: &uint) -> bool {
-        self.find(key).is_some()
+        self.get(key).is_some()
+    }
+
+    /// Deprecated: renamed to `get_mut`.
+    #[deprecated = "renamed to `get_mut`"]
+    pub fn find_mut(&mut self, key: &uint) -> Option<&mut T> {
+        self.get_mut(key)
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
@@ -334,52 +360,22 @@ impl<T> TrieMap<T> {
     ///
     /// let mut map = TrieMap::new();
     /// map.insert(1, "a");
-    /// match map.find_mut(&1) {
+    /// match map.get_mut(&1) {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
     #[inline]
-    pub fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
         find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
     }
 
-    /// Inserts a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Returns `true` if the key did
-    /// not already exist in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::TrieMap;
-    ///
-    /// let mut map = TrieMap::new();
-    /// assert_eq!(map.insert(2, "value"), true);
-    /// assert_eq!(map.insert(2, "value2"), false);
-    /// assert_eq!(map[2], "value2");
-    /// ```
-    #[inline]
-    pub fn insert(&mut self, key: uint, value: T) -> bool {
-        self.swap(key, value).is_none()
-    }
-
-    /// Removes a key-value pair from the map. Returns `true` if the key
-    /// was present in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::TrieMap;
-    ///
-    /// let mut map = TrieMap::new();
-    /// assert_eq!(map.remove(&1), false);
-    /// map.insert(1, "a");
-    /// assert_eq!(map.remove(&1), true);
-    /// ```
-    #[inline]
-    pub fn remove(&mut self, key: &uint) -> bool {
-        self.pop(key).is_some()
+    /// Deprecated: Renamed to `insert`.
+    #[deprecated = "Renamed to `insert`"]
+    pub fn swap(&mut self, key: uint, value: T) -> Option<T> {
+        self.insert(key, value)
     }
 
     /// Inserts a key-value pair from the map. If the key already had a value
@@ -391,14 +387,15 @@ impl<T> TrieMap<T> {
     /// use std::collections::TrieMap;
     ///
     /// let mut map = TrieMap::new();
-    /// assert_eq!(map.swap(37, "a"), None);
+    /// assert_eq!(map.insert(37, "a"), None);
     /// assert_eq!(map.is_empty(), false);
     ///
     /// map.insert(37, "b");
-    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    pub fn swap(&mut self, key: uint, value: T) -> Option<T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, key: uint, value: T) -> Option<T> {
         let ret = insert(&mut self.root.count,
                          &mut self.root.children[chunk(key, 0)],
                          key, value, 1);
@@ -406,6 +403,12 @@ impl<T> TrieMap<T> {
         ret
     }
 
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, key: &uint) -> Option<T> {
+        self.remove(key)
+    }
+
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     ///
@@ -416,10 +419,11 @@ impl<T> TrieMap<T> {
     ///
     /// let mut map = TrieMap::new();
     /// map.insert(1, "a");
-    /// assert_eq!(map.pop(&1), Some("a"));
-    /// assert_eq!(map.pop(&1), None);
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
     /// ```
-    pub fn pop(&mut self, key: &uint) -> Option<T> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, key: &uint) -> Option<T> {
         let ret = remove(&mut self.root.count,
                          &mut self.root.children[chunk(*key, 0)],
                          *key, 1);
@@ -582,9 +586,9 @@ impl<T> TrieMap<T> {
     ///     *value = "changed";
     /// }
     ///
-    /// assert_eq!(map.find(&2), Some(&"a"));
-    /// assert_eq!(map.find(&4), Some(&"changed"));
-    /// assert_eq!(map.find(&6), Some(&"changed"));
+    /// assert_eq!(map.get(&2), Some(&"a"));
+    /// assert_eq!(map.get(&4), Some(&"changed"));
+    /// assert_eq!(map.get(&6), Some(&"changed"));
     /// ```
     pub fn lower_bound_mut<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
         self.bound_mut(key, false)
@@ -607,9 +611,9 @@ impl<T> TrieMap<T> {
     ///     *value = "changed";
     /// }
     ///
-    /// assert_eq!(map.find(&2), Some(&"a"));
-    /// assert_eq!(map.find(&4), Some(&"b"));
-    /// assert_eq!(map.find(&6), Some(&"changed"));
+    /// assert_eq!(map.get(&2), Some(&"a"));
+    /// assert_eq!(map.get(&4), Some(&"b"));
+    /// assert_eq!(map.get(&6), Some(&"changed"));
     /// ```
     pub fn upper_bound_mut<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> {
         self.bound_mut(key, true)
@@ -643,14 +647,14 @@ impl<S: Writer, T: Hash<S>> Hash<S> for TrieMap<T> {
 impl<T> Index<uint, T> for TrieMap<T> {
     #[inline]
     fn index<'a>(&'a self, i: &uint) -> &'a T {
-        self.find(i).expect("key not present")
+        self.get(i).expect("key not present")
     }
 }
 
 impl<T> IndexMut<uint, T> for TrieMap<T> {
     #[inline]
     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut T {
-        self.find_mut(i).expect("key not present")
+        self.get_mut(i).expect("key not present")
     }
 }
 
@@ -957,24 +961,24 @@ mod test {
     #[test]
     fn test_find_mut() {
         let mut m = TrieMap::new();
-        assert!(m.insert(1u, 12i));
-        assert!(m.insert(2u, 8i));
-        assert!(m.insert(5u, 14i));
+        assert!(m.insert(1u, 12i).is_none());
+        assert!(m.insert(2u, 8i).is_none());
+        assert!(m.insert(5u, 14i).is_none());
         let new = 100;
-        match m.find_mut(&5) {
+        match m.get_mut(&5) {
             None => panic!(), Some(x) => *x = new
         }
-        assert_eq!(m.find(&5), Some(&new));
+        assert_eq!(m.get(&5), Some(&new));
     }
 
     #[test]
     fn test_find_mut_missing() {
         let mut m = TrieMap::new();
-        assert!(m.find_mut(&0).is_none());
-        assert!(m.insert(1u, 12i));
-        assert!(m.find_mut(&0).is_none());
-        assert!(m.insert(2, 8));
-        assert!(m.find_mut(&0).is_none());
+        assert!(m.get_mut(&0).is_none());
+        assert!(m.insert(1u, 12i).is_none());
+        assert!(m.get_mut(&0).is_none());
+        assert!(m.insert(2, 8).is_none());
+        assert!(m.get_mut(&0).is_none());
     }
 
     #[test]
@@ -983,32 +987,32 @@ mod test {
         let n = 300u;
 
         for x in range_step(1u, n, 2) {
-            assert!(trie.insert(x, x + 1));
+            assert!(trie.insert(x, x + 1).is_none());
             assert!(trie.contains_key(&x));
             check_integrity(&trie.root);
         }
 
         for x in range_step(0u, n, 2) {
             assert!(!trie.contains_key(&x));
-            assert!(trie.insert(x, x + 1));
+            assert!(trie.insert(x, x + 1).is_none());
             check_integrity(&trie.root);
         }
 
         for x in range(0u, n) {
             assert!(trie.contains_key(&x));
-            assert!(!trie.insert(x, x + 1));
+            assert!(!trie.insert(x, x + 1).is_none());
             check_integrity(&trie.root);
         }
 
         for x in range_step(1u, n, 2) {
-            assert!(trie.remove(&x));
+            assert!(trie.remove(&x).is_some());
             assert!(!trie.contains_key(&x));
             check_integrity(&trie.root);
         }
 
         for x in range_step(0u, n, 2) {
             assert!(trie.contains_key(&x));
-            assert!(!trie.insert(x, x + 1));
+            assert!(!trie.insert(x, x + 1).is_none());
             check_integrity(&trie.root);
         }
     }
@@ -1017,11 +1021,11 @@ mod test {
     fn test_each_reverse() {
         let mut m = TrieMap::new();
 
-        assert!(m.insert(3, 6));
-        assert!(m.insert(0, 0));
-        assert!(m.insert(4, 8));
-        assert!(m.insert(2, 4));
-        assert!(m.insert(1, 2));
+        assert!(m.insert(3, 6).is_none());
+        assert!(m.insert(0, 0).is_none());
+        assert!(m.insert(4, 8).is_none());
+        assert!(m.insert(2, 4).is_none());
+        assert!(m.insert(1, 2).is_none());
 
         let mut n = 4;
         m.each_reverse(|k, v| {
@@ -1054,19 +1058,19 @@ mod test {
     }
 
     #[test]
-    fn test_swap() {
+    fn test_insert() {
         let mut m = TrieMap::new();
-        assert_eq!(m.swap(1u, 2i), None);
-        assert_eq!(m.swap(1u, 3i), Some(2));
-        assert_eq!(m.swap(1u, 4i), Some(3));
+        assert_eq!(m.insert(1u, 2i), None);
+        assert_eq!(m.insert(1u, 3i), Some(2));
+        assert_eq!(m.insert(1u, 4i), Some(3));
     }
 
     #[test]
-    fn test_pop() {
+    fn test_remove() {
         let mut m = TrieMap::new();
         m.insert(1u, 2i);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
+        assert_eq!(m.remove(&1), Some(2));
+        assert_eq!(m.remove(&1), None);
     }
 
     #[test]
@@ -1076,7 +1080,7 @@ mod test {
         let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
-            assert_eq!(map.find(&k), Some(&v));
+            assert_eq!(map.get(&k), Some(&v));
         }
     }
 
@@ -1243,15 +1247,15 @@ mod test {
         let mut b = TrieMap::new();
 
         assert!(a == b);
-        assert!(a.insert(0, 5i));
+        assert!(a.insert(0, 5i).is_none());
         assert!(a != b);
-        assert!(b.insert(0, 4i));
+        assert!(b.insert(0, 4i).is_none());
         assert!(a != b);
-        assert!(a.insert(5, 19));
+        assert!(a.insert(5, 19).is_none());
         assert!(a != b);
-        assert!(!b.insert(0, 5));
+        assert!(!b.insert(0, 5).is_none());
         assert!(a != b);
-        assert!(b.insert(5, 19));
+        assert!(b.insert(5, 19).is_none());
         assert!(a == b);
     }
 
@@ -1261,15 +1265,15 @@ mod test {
         let mut b = TrieMap::new();
 
         assert!(!(a < b) && !(b < a));
-        assert!(b.insert(2u, 5i));
+        assert!(b.insert(2u, 5i).is_none());
         assert!(a < b);
-        assert!(a.insert(2, 7));
+        assert!(a.insert(2, 7).is_none());
         assert!(!(a < b) && b < a);
-        assert!(b.insert(1, 0));
+        assert!(b.insert(1, 0).is_none());
         assert!(b < a);
-        assert!(a.insert(0, 6));
+        assert!(a.insert(0, 6).is_none());
         assert!(a < b);
-        assert!(a.insert(6, 2));
+        assert!(a.insert(6, 2).is_none());
         assert!(a < b && !(b < a));
     }
 
@@ -1279,10 +1283,10 @@ mod test {
         let mut b = TrieMap::new();
 
         assert!(a <= b && a >= b);
-        assert!(a.insert(1u, 1i));
+        assert!(a.insert(1u, 1i).is_none());
         assert!(a > b && a >= b);
         assert!(b < a && b <= a);
-        assert!(b.insert(2, 2));
+        assert!(b.insert(2, 2).is_none());
         assert!(b > a && b >= a);
         assert!(a < b && a <= b);
     }
@@ -1355,7 +1359,7 @@ mod bench {
         let mut rng = weak_rng();
 
         for _ in range(0, size) {
-            map.swap(rng.gen(), rng.gen());
+            map.insert(rng.gen(), rng.gen());
         }
 
         b.iter(|| {
diff --git a/src/libcollections/trie/set.rs b/src/libcollections/trie/set.rs
index ddddd279b04..dd5a81fe96e 100644
--- a/src/libcollections/trie/set.rs
+++ b/src/libcollections/trie/set.rs
@@ -8,6 +8,12 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// FIXME(conventions): implement bounded iterators
+// FIXME(conventions): implement union family of fns
+// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
+// FIXME(conventions): replace each_reverse by making iter DoubleEnded
+// FIXME(conventions): implement iter_mut and into_iter
+
 use core::prelude::*;
 
 use core::default::Default;
@@ -79,6 +85,7 @@ impl TrieSet {
     /// let mut set = TrieSet::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> TrieSet {
         TrieSet{map: TrieMap::new()}
     }
@@ -126,6 +133,7 @@ impl TrieSet {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> SetItems<'a> {
         SetItems{iter: self.map.iter()}
     }
@@ -177,6 +185,7 @@ impl TrieSet {
     /// assert_eq!(v.len(), 1);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns true if the set contains no elements
@@ -191,6 +200,7 @@ impl TrieSet {
     /// v.insert(1);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the set, removing all values.
@@ -206,6 +216,7 @@ impl TrieSet {
     /// assert!(v.is_empty());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.map.clear() }
 
     /// Returns `true` if the set contains a value.
@@ -220,6 +231,7 @@ impl TrieSet {
     /// assert_eq!(set.contains(&4), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains(&self, value: &uint) -> bool {
         self.map.contains_key(value)
     }
@@ -242,6 +254,7 @@ impl TrieSet {
     /// assert_eq!(a.is_disjoint(&b), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_disjoint(&self, other: &TrieSet) -> bool {
         self.iter().all(|v| !other.contains(&v))
     }
@@ -263,6 +276,7 @@ impl TrieSet {
     /// assert_eq!(set.is_subset(&sup), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_subset(&self, other: &TrieSet) -> bool {
         self.iter().all(|v| other.contains(&v))
     }
@@ -287,6 +301,7 @@ impl TrieSet {
     /// assert_eq!(set.is_superset(&sub), true);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_superset(&self, other: &TrieSet) -> bool {
         other.is_subset(self)
     }
@@ -306,8 +321,9 @@ impl TrieSet {
     /// assert_eq!(set.len(), 1);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn insert(&mut self, value: uint) -> bool {
-        self.map.insert(value, ())
+        self.map.insert(value, ()).is_none()
     }
 
     /// Removes a value from the set. Returns `true` if the value was
@@ -325,8 +341,9 @@ impl TrieSet {
     /// assert_eq!(set.remove(&2), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn remove(&mut self, value: &uint) -> bool {
-        self.map.remove(value)
+        self.map.remove(value).is_some()
     }
 }
 
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 4b6921ed0c0..707084d9c70 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -312,7 +312,7 @@ impl<T: Clone> Vec<T> {
     #[inline]
     #[experimental]
     pub fn push_all(&mut self, other: &[T]) {
-        self.reserve_additional(other.len());
+        self.reserve(other.len());
 
         for i in range(0, other.len()) {
             let len = self.len();
@@ -342,7 +342,7 @@ impl<T: Clone> Vec<T> {
     /// ```
     #[stable]
     pub fn grow(&mut self, n: uint, value: T) {
-        self.reserve_additional(n);
+        self.reserve(n);
         let mut i: uint = 0u;
 
         while i < n {
@@ -489,7 +489,7 @@ impl<T> Extendable<T> for Vec<T> {
     #[inline]
     fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {
         let (lower, _) = iterator.size_hint();
-        self.reserve_additional(lower);
+        self.reserve(lower);
         for element in iterator {
             self.push(element)
         }
@@ -578,74 +578,70 @@ impl<T> Vec<T> {
         self.cap
     }
 
-     /// Reserves capacity for at least `n` additional elements in the given
-     /// vector.
-     ///
-     /// # Failure
-     ///
-     /// Fails if the new capacity overflows `uint`.
-     ///
-     /// # Example
-     ///
-     /// ```
-     /// let mut vec: Vec<int> = vec![1i];
-     /// vec.reserve_additional(10);
-     /// assert!(vec.capacity() >= 11);
-     /// ```
+    /// Deprecated: Renamed to `reserve`.
+    #[deprecated = "Renamed to `reserve`"]
     pub fn reserve_additional(&mut self, extra: uint) {
-        if self.cap - self.len < extra {
-            match self.len.checked_add(&extra) {
-                None => panic!("Vec::reserve_additional: `uint` overflow"),
-                Some(new_cap) => self.reserve(new_cap)
-            }
-        }
+        self.reserve(extra)
     }
 
-    /// Reserves capacity for at least `n` elements in the given vector.
+    /// Reserves capacity for at least `additional` more elements to be inserted in the given
+    /// `Vec`. The collection may reserve more space to avoid frequent reallocations.
     ///
-    /// This function will over-allocate in order to amortize the allocation
-    /// costs in scenarios where the caller may need to repeatedly reserve
-    /// additional space.
+    /// # Panics
     ///
-    /// If the capacity for `self` is already equal to or greater than the
-    /// requested capacity, then no action is taken.
+    /// Panics if the new capacity overflows `uint`.
     ///
     /// # Example
     ///
     /// ```
-    /// let mut vec = vec![1i, 2, 3];
+    /// let mut vec: Vec<int> = vec![1];
     /// vec.reserve(10);
-    /// assert!(vec.capacity() >= 10);
+    /// assert!(vec.capacity() >= 11);
     /// ```
-    pub fn reserve(&mut self, capacity: uint) {
-        if capacity > self.cap {
-            self.reserve_exact(num::next_power_of_two(capacity))
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve(&mut self, additional: uint) {
+        if self.cap - self.len < additional {
+            match self.len.checked_add(&additional) {
+                None => panic!("Vec::reserve: `uint` overflow"),
+                // if the checked_add
+                Some(new_cap) => {
+                    let amort_cap = num::next_power_of_two(new_cap);
+                    // next_power_of_two will overflow to exactly 0 for really big capacities
+                    if amort_cap == 0 {
+                        self.grow_capacity(new_cap);
+                    } else {
+                        self.grow_capacity(amort_cap);
+                    }
+                }
+            }
         }
     }
 
-    /// Reserves capacity for exactly `capacity` elements in the given vector.
+    /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
+    /// given `Vec`. Does nothing if the capacity is already sufficient.
     ///
-    /// If the capacity for `self` is already equal to or greater than the
-    /// requested capacity, then no action is taken.
+    /// Note that the allocator may give the collection more space than it requests. Therefore
+    /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
+    /// insertions are expected.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `uint`.
     ///
     /// # Example
     ///
     /// ```
-    /// let mut vec: Vec<int> = Vec::with_capacity(10);
-    /// vec.reserve_exact(11);
-    /// assert_eq!(vec.capacity(), 11);
+    /// let mut vec: Vec<int> = vec![1];
+    /// vec.reserve_exact(10);
+    /// assert!(vec.capacity() >= 11);
     /// ```
-    pub fn reserve_exact(&mut self, capacity: uint) {
-        if mem::size_of::<T>() == 0 { return }
-
-        if capacity > self.cap {
-            let size = capacity.checked_mul(&mem::size_of::<T>())
-                               .expect("capacity overflow");
-            unsafe {
-                self.ptr = alloc_or_realloc(self.ptr, self.cap * mem::size_of::<T>(), size);
-                if self.ptr.is_null() { ::alloc::oom() }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn reserve_exact(&mut self, additional: uint) {
+        if self.cap - self.len < additional {
+            match self.len.checked_add(&additional) {
+                None => panic!("Vec::reserve: `uint` overflow"),
+                Some(new_cap) => self.grow_capacity(new_cap)
             }
-            self.cap = capacity;
         }
     }
 
@@ -663,6 +659,7 @@ impl<T> Vec<T> {
     /// assert!(vec.capacity() >= 3);
     /// ```
     #[stable]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn shrink_to_fit(&mut self) {
         if mem::size_of::<T>() == 0 { return }
 
@@ -713,7 +710,7 @@ impl<T> Vec<T> {
     /// vec.truncate(2);
     /// assert_eq!(vec, vec![1, 2]);
     /// ```
-    #[unstable = "waiting on panic semantics"]
+    #[unstable = "matches collection reform specification; waiting on panic semantics"]
     pub fn truncate(&mut self, len: uint) {
         unsafe {
             // drop any extra elements
@@ -761,6 +758,7 @@ impl<T> Vec<T> {
     /// }
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveItems<T> {
         unsafe {
             let ptr = self.ptr;
@@ -796,26 +794,6 @@ impl<T> Vec<T> {
         self.len = len;
     }
 
-    /// Returns a mutable reference to the value at index `index`.
-    ///
-    /// # Failure
-    ///
-    /// Fails if `index` is out of bounds
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// # #![allow(deprecated)]
-    /// let mut vec = vec![1i, 2, 3];
-    /// *vec.get_mut(1) = 4;
-    /// assert_eq!(vec, vec![1i, 4, 3]);
-    /// ```
-    #[inline]
-    #[deprecated = "use `foo[index] = bar` instead"]
-    pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
-        &mut self.as_mut_slice()[index]
-    }
-
     /// Removes an element from anywhere in the vector and return it, replacing
     /// it with the last element. This does not preserve ordering, but is O(1).
     ///
@@ -868,7 +846,7 @@ impl<T> Vec<T> {
         let len = self.len();
         assert!(index <= len);
         // space for the new element
-        self.reserve(len + 1);
+        self.reserve(1);
 
         unsafe { // infallible
             // The spot to put the new value
@@ -970,7 +948,7 @@ impl<T> Vec<T> {
     /// ```
     #[unstable = "this function may be renamed or change to unboxed closures"]
     pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
-        self.reserve_additional(n);
+        self.reserve(n);
         for i in range(0u, n) {
             self.push(f(i));
         }
@@ -1076,7 +1054,26 @@ impl<T> Vec<T> {
     /// v.push(1i);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
+
+    /// Reserves capacity for exactly `capacity` elements in the given vector.
+    ///
+    /// If the capacity for `self` is already equal to or greater than the
+    /// requested capacity, then no action is taken.
+    fn grow_capacity(&mut self, capacity: uint) {
+        if mem::size_of::<T>() == 0 { return }
+
+        if capacity > self.cap {
+            let size = capacity.checked_mul(&mem::size_of::<T>())
+                               .expect("capacity overflow");
+            unsafe {
+                self.ptr = alloc_or_realloc(self.ptr, self.cap * mem::size_of::<T>(), size);
+                if self.ptr.is_null() { ::alloc::oom() }
+            }
+            self.cap = capacity;
+        }
+    }
 }
 
 impl<T: PartialEq> Vec<T> {
@@ -1742,11 +1739,11 @@ mod tests {
     }
 
     #[test]
-    fn test_reserve_additional() {
+    fn test_reserve() {
         let mut v = Vec::new();
         assert_eq!(v.capacity(), 0);
 
-        v.reserve_additional(2);
+        v.reserve(2);
         assert!(v.capacity() >= 2);
 
         for i in range(0i, 16) {
@@ -1754,12 +1751,12 @@ mod tests {
         }
 
         assert!(v.capacity() >= 16);
-        v.reserve_additional(16);
+        v.reserve(16);
         assert!(v.capacity() >= 32);
 
         v.push(16);
 
-        v.reserve_additional(16);
+        v.reserve(16);
         assert!(v.capacity() >= 33)
     }
 
diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs
index c0bc785126c..38a345272b0 100644
--- a/src/libcollections/vec_map.rs
+++ b/src/libcollections/vec_map.rs
@@ -26,6 +26,8 @@ use vec::Vec;
 use hash;
 use hash::Hash;
 
+// FIXME(conventions): capacity management???
+
 /// A map optimized for small integer keys.
 ///
 /// # Example
@@ -42,14 +44,14 @@ use hash::Hash;
 ///     println!("The end is near!");
 /// }
 ///
-/// assert_eq!(months.find(&1), Some(&"Jan"));
+/// assert_eq!(months.get(&1), Some(&"Jan"));
 ///
-/// match months.find_mut(&3) {
+/// match months.get_mut(&3) {
 ///     Some(value) => *value = "Venus",
 ///     None => (),
 /// }
 ///
-/// assert_eq!(months.find(&3), Some(&"Venus"));
+/// assert_eq!(months.get(&3), Some(&"Venus"));
 ///
 /// // Print out all months
 /// for (key, value) in months.iter() {
@@ -77,10 +79,7 @@ impl<V:Clone> Clone for VecMap<V> {
 
     #[inline]
     fn clone_from(&mut self, source: &VecMap<V>) {
-        self.v.reserve(source.v.len());
-        for (i, w) in self.v.iter_mut().enumerate() {
-            *w = source.v[i].clone();
-        }
+        self.v.clone_from(&source.v);
     }
 }
 
@@ -99,6 +98,7 @@ impl<V> VecMap<V> {
     /// use std::collections::VecMap;
     /// let mut map: VecMap<&str> = VecMap::new();
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> VecMap<V> { VecMap{v: vec!()} }
 
     /// Creates an empty `VecMap` with space for at least `capacity`
@@ -110,18 +110,21 @@ impl<V> VecMap<V> {
     /// use std::collections::VecMap;
     /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(capacity: uint) -> VecMap<V> {
         VecMap { v: Vec::with_capacity(capacity) }
     }
 
     /// Returns an iterator visiting all keys in ascending order by the keys.
     /// The iterator's element type is `uint`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'r>(&'r self) -> Keys<'r, V> {
         self.iter().map(|(k, _v)| k)
     }
 
     /// Returns an iterator visiting all values in ascending order by the keys.
     /// The iterator's element type is `&'r V`.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'r>(&'r self) -> Values<'r, V> {
         self.iter().map(|(_k, v)| v)
     }
@@ -144,6 +147,7 @@ impl<V> VecMap<V> {
     ///     println!("{}: {}", key, value);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'r>(&'r self) -> Entries<'r, V> {
         Entries {
             front: 0,
@@ -174,6 +178,7 @@ impl<V> VecMap<V> {
     ///     assert_eq!(value, &"x");
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut<'r>(&'r mut self) -> MutEntries<'r, V> {
         MutEntries {
             front: 0,
@@ -201,6 +206,7 @@ impl<V> VecMap<V> {
     ///
     /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(&mut self)
         -> FilterMap<(uint, Option<V>), (uint, V),
                 Enumerate<vec::MoveItems<Option<V>>>>
@@ -223,6 +229,7 @@ impl<V> VecMap<V> {
     /// a.insert(1, "a");
     /// assert_eq!(a.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint {
         self.v.iter().filter(|elt| elt.is_some()).count()
     }
@@ -239,6 +246,7 @@ impl<V> VecMap<V> {
     /// a.insert(1, "a");
     /// assert!(!a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool {
         self.v.iter().all(|elt| elt.is_none())
     }
@@ -255,8 +263,15 @@ impl<V> VecMap<V> {
     /// a.clear();
     /// assert!(a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.v.clear() }
 
+    /// Deprecated: Renamed to `get`.
+    #[deprecated = "Renamed to `get`"]
+    pub fn find(&self, key: &uint) -> Option<&V> {
+        self.get(key)
+    }
+
     /// Returns a reference to the value corresponding to the key.
     ///
     /// # Example
@@ -266,10 +281,11 @@ impl<V> VecMap<V> {
     ///
     /// let mut map = VecMap::new();
     /// map.insert(1, "a");
-    /// assert_eq!(map.find(&1), Some(&"a"));
-    /// assert_eq!(map.find(&2), None);
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
     /// ```
-    pub fn find<'a>(&'a self, key: &uint) -> Option<&'a V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, key: &uint) -> Option<&V> {
         if *key < self.v.len() {
             match self.v[*key] {
               Some(ref value) => Some(value),
@@ -293,8 +309,15 @@ impl<V> VecMap<V> {
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains_key(&self, key: &uint) -> bool {
-        self.find(key).is_some()
+        self.get(key).is_some()
+    }
+
+    /// Deprecated: Renamed to `get_mut`.
+    #[deprecated = "Renamed to `get_mut`"]
+    pub fn find_mut(&mut self, key: &uint) -> Option<&mut V> {
+        self.get_mut(key)
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
@@ -306,13 +329,14 @@ impl<V> VecMap<V> {
     ///
     /// let mut map = VecMap::new();
     /// map.insert(1, "a");
-    /// match map.find_mut(&1) {
+    /// match map.get_mut(&1) {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
-    pub fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut(&mut self, key: &uint) -> Option<&mut V> {
         if *key < self.v.len() {
             match *(&mut self.v[*key]) {
               Some(ref mut value) => Some(value),
@@ -323,45 +347,10 @@ impl<V> VecMap<V> {
         }
     }
 
-    /// Inserts a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Returns `true` if the key did
-    /// not already exist in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::VecMap;
-    ///
-    /// let mut map = VecMap::new();
-    /// assert_eq!(map.insert(2, "value"), true);
-    /// assert_eq!(map.insert(2, "value2"), false);
-    /// assert_eq!(map[2], "value2");
-    /// ```
-    pub fn insert(&mut self, key: uint, value: V) -> bool {
-        let exists = self.contains_key(&key);
-        let len = self.v.len();
-        if len <= key {
-            self.v.grow_fn(key - len + 1, |_| None);
-        }
-        self.v[key] = Some(value);
-        !exists
-    }
-
-    /// Removes a key-value pair from the map. Returns `true` if the key
-    /// was present in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::VecMap;
-    ///
-    /// let mut map = VecMap::new();
-    /// assert_eq!(map.remove(&1), false);
-    /// map.insert(1, "a");
-    /// assert_eq!(map.remove(&1), true);
-    /// ```
-    pub fn remove(&mut self, key: &uint) -> bool {
-        self.pop(key).is_some()
+    /// Deprecated: Renamed to `insert`.
+    #[deprecated = "Renamed to `insert`"]
+    pub fn swap(&mut self, key: uint, value: V) -> Option<V> {
+        self.insert(key, value)
     }
 
     /// Inserts a key-value pair from the map. If the key already had a value
@@ -373,20 +362,26 @@ impl<V> VecMap<V> {
     /// use std::collections::VecMap;
     ///
     /// let mut map = VecMap::new();
-    /// assert_eq!(map.swap(37, "a"), None);
+    /// assert_eq!(map.insert(37, "a"), None);
     /// assert_eq!(map.is_empty(), false);
     ///
     /// map.insert(37, "b");
-    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    pub fn swap(&mut self, key: uint, value: V) -> Option<V> {
-        match self.find_mut(&key) {
-            Some(loc) => { return Some(replace(loc, value)); }
-            None => ()
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, key: uint, value: V) -> Option<V> {
+        let len = self.v.len();
+        if len <= key {
+            self.v.grow_fn(key - len + 1, |_| None);
         }
-        self.insert(key, value);
-        return None;
+        replace(&mut self.v[key], Some(value))
+    }
+
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, key: &uint) -> Option<V> {
+        self.remove(key)
     }
 
     /// Removes a key from the map, returning the value at the key if the key
@@ -399,10 +394,11 @@ impl<V> VecMap<V> {
     ///
     /// let mut map = VecMap::new();
     /// map.insert(1, "a");
-    /// assert_eq!(map.pop(&1), Some("a"));
-    /// assert_eq!(map.pop(&1), None);
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
     /// ```
-    pub fn pop(&mut self, key: &uint) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, key: &uint) -> Option<V> {
         if *key >= self.v.len() {
             return None;
         }
@@ -460,11 +456,11 @@ impl<V:Clone> VecMap<V> {
                            val: V,
                            ff: |uint, V, V| -> V)
                            -> bool {
-        let new_val = match self.find(&key) {
+        let new_val = match self.get(&key) {
             None => val,
             Some(orig) => ff(key, (*orig).clone(), val)
         };
-        self.insert(key, new_val)
+        self.insert(key, new_val).is_none()
     }
 }
 
@@ -514,14 +510,14 @@ impl<V> Extendable<(uint, V)> for VecMap<V> {
 impl<V> Index<uint, V> for VecMap<V> {
     #[inline]
     fn index<'a>(&'a self, i: &uint) -> &'a V {
-        self.find(i).expect("key not present")
+        self.get(i).expect("key not present")
     }
 }
 
 impl<V> IndexMut<uint, V> for VecMap<V> {
     #[inline]
     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut V {
-        self.find_mut(i).expect("key not present")
+        self.get_mut(i).expect("key not present")
     }
 }
 
@@ -615,16 +611,16 @@ mod test_map {
     use super::VecMap;
 
     #[test]
-    fn test_find_mut() {
+    fn test_get_mut() {
         let mut m = VecMap::new();
-        assert!(m.insert(1, 12i));
-        assert!(m.insert(2, 8));
-        assert!(m.insert(5, 14));
+        assert!(m.insert(1, 12i).is_none());
+        assert!(m.insert(2, 8).is_none());
+        assert!(m.insert(5, 14).is_none());
         let new = 100;
-        match m.find_mut(&5) {
+        match m.get_mut(&5) {
             None => panic!(), Some(x) => *x = new
         }
-        assert_eq!(m.find(&5), Some(&new));
+        assert_eq!(m.get(&5), Some(&new));
     }
 
     #[test]
@@ -632,13 +628,13 @@ mod test_map {
         let mut map = VecMap::new();
         assert_eq!(map.len(), 0);
         assert!(map.is_empty());
-        assert!(map.insert(5, 20i));
+        assert!(map.insert(5, 20i).is_none());
         assert_eq!(map.len(), 1);
         assert!(!map.is_empty());
-        assert!(map.insert(11, 12));
+        assert!(map.insert(11, 12).is_none());
         assert_eq!(map.len(), 2);
         assert!(!map.is_empty());
-        assert!(map.insert(14, 22));
+        assert!(map.insert(14, 22).is_none());
         assert_eq!(map.len(), 3);
         assert!(!map.is_empty());
     }
@@ -646,14 +642,14 @@ mod test_map {
     #[test]
     fn test_clear() {
         let mut map = VecMap::new();
-        assert!(map.insert(5, 20i));
-        assert!(map.insert(11, 12));
-        assert!(map.insert(14, 22));
+        assert!(map.insert(5, 20i).is_none());
+        assert!(map.insert(11, 12).is_none());
+        assert!(map.insert(14, 22).is_none());
         map.clear();
         assert!(map.is_empty());
-        assert!(map.find(&5).is_none());
-        assert!(map.find(&11).is_none());
-        assert!(map.find(&14).is_none());
+        assert!(map.get(&5).is_none());
+        assert!(map.get(&11).is_none());
+        assert!(map.get(&14).is_none());
     }
 
     #[test]
@@ -678,28 +674,28 @@ mod test_map {
         map.update_with_key(3, 2, add_more_to_count);
 
         // check the total counts
-        assert_eq!(map.find(&3).unwrap(), &10);
-        assert_eq!(map.find(&5).unwrap(), &3);
-        assert_eq!(map.find(&9).unwrap(), &1);
+        assert_eq!(map.get(&3).unwrap(), &10);
+        assert_eq!(map.get(&5).unwrap(), &3);
+        assert_eq!(map.get(&9).unwrap(), &1);
 
         // sadly, no sevens were counted
-        assert!(map.find(&7).is_none());
+        assert!(map.get(&7).is_none());
     }
 
     #[test]
-    fn test_swap() {
+    fn test_insert() {
         let mut m = VecMap::new();
-        assert_eq!(m.swap(1, 2i), None);
-        assert_eq!(m.swap(1, 3i), Some(2));
-        assert_eq!(m.swap(1, 4i), Some(3));
+        assert_eq!(m.insert(1, 2i), None);
+        assert_eq!(m.insert(1, 3i), Some(2));
+        assert_eq!(m.insert(1, 4i), Some(3));
     }
 
     #[test]
-    fn test_pop() {
+    fn test_remove() {
         let mut m = VecMap::new();
         m.insert(1, 2i);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
+        assert_eq!(m.remove(&1), Some(2));
+        assert_eq!(m.remove(&1), None);
     }
 
     #[test]
@@ -732,11 +728,11 @@ mod test_map {
     fn test_iterator() {
         let mut m = VecMap::new();
 
-        assert!(m.insert(0, 1i));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
+        assert!(m.insert(0, 1i).is_none());
+        assert!(m.insert(1, 2).is_none());
+        assert!(m.insert(3, 5).is_none());
+        assert!(m.insert(6, 10).is_none());
+        assert!(m.insert(10, 11).is_none());
 
         let mut it = m.iter();
         assert_eq!(it.size_hint(), (0, Some(11)));
@@ -757,11 +753,11 @@ mod test_map {
     fn test_iterator_size_hints() {
         let mut m = VecMap::new();
 
-        assert!(m.insert(0, 1i));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
+        assert!(m.insert(0, 1i).is_none());
+        assert!(m.insert(1, 2).is_none());
+        assert!(m.insert(3, 5).is_none());
+        assert!(m.insert(6, 10).is_none());
+        assert!(m.insert(10, 11).is_none());
 
         assert_eq!(m.iter().size_hint(), (0, Some(11)));
         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
@@ -773,11 +769,11 @@ mod test_map {
     fn test_mut_iterator() {
         let mut m = VecMap::new();
 
-        assert!(m.insert(0, 1i));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
+        assert!(m.insert(0, 1i).is_none());
+        assert!(m.insert(1, 2).is_none());
+        assert!(m.insert(3, 5).is_none());
+        assert!(m.insert(6, 10).is_none());
+        assert!(m.insert(10, 11).is_none());
 
         for (k, v) in m.iter_mut() {
             *v += k as int;
@@ -796,11 +792,11 @@ mod test_map {
     fn test_rev_iterator() {
         let mut m = VecMap::new();
 
-        assert!(m.insert(0, 1i));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
+        assert!(m.insert(0, 1i).is_none());
+        assert!(m.insert(1, 2).is_none());
+        assert!(m.insert(3, 5).is_none());
+        assert!(m.insert(6, 10).is_none());
+        assert!(m.insert(10, 11).is_none());
 
         let mut it = m.iter().rev();
         assert_eq!(it.next().unwrap(), (10, &11));
@@ -815,11 +811,11 @@ mod test_map {
     fn test_mut_rev_iterator() {
         let mut m = VecMap::new();
 
-        assert!(m.insert(0, 1i));
-        assert!(m.insert(1, 2));
-        assert!(m.insert(3, 5));
-        assert!(m.insert(6, 10));
-        assert!(m.insert(10, 11));
+        assert!(m.insert(0, 1i).is_none());
+        assert!(m.insert(1, 2).is_none());
+        assert!(m.insert(3, 5).is_none());
+        assert!(m.insert(6, 10).is_none());
+        assert!(m.insert(10, 11).is_none());
 
         for (k, v) in m.iter_mut().rev() {
             *v += k as int;
@@ -880,15 +876,15 @@ mod test_map {
         let mut b = VecMap::new();
 
         assert!(a == b);
-        assert!(a.insert(0, 5i));
+        assert!(a.insert(0, 5i).is_none());
         assert!(a != b);
-        assert!(b.insert(0, 4i));
+        assert!(b.insert(0, 4i).is_none());
         assert!(a != b);
-        assert!(a.insert(5, 19));
+        assert!(a.insert(5, 19).is_none());
         assert!(a != b);
-        assert!(!b.insert(0, 5));
+        assert!(!b.insert(0, 5).is_none());
         assert!(a != b);
-        assert!(b.insert(5, 19));
+        assert!(b.insert(5, 19).is_none());
         assert!(a == b);
     }
 
@@ -898,15 +894,15 @@ mod test_map {
         let mut b = VecMap::new();
 
         assert!(!(a < b) && !(b < a));
-        assert!(b.insert(2u, 5i));
+        assert!(b.insert(2u, 5i).is_none());
         assert!(a < b);
-        assert!(a.insert(2, 7));
+        assert!(a.insert(2, 7).is_none());
         assert!(!(a < b) && b < a);
-        assert!(b.insert(1, 0));
+        assert!(b.insert(1, 0).is_none());
         assert!(b < a);
-        assert!(a.insert(0, 6));
+        assert!(a.insert(0, 6).is_none());
         assert!(a < b);
-        assert!(a.insert(6, 2));
+        assert!(a.insert(6, 2).is_none());
         assert!(a < b && !(b < a));
     }
 
@@ -916,10 +912,10 @@ mod test_map {
         let mut b = VecMap::new();
 
         assert!(a <= b && a >= b);
-        assert!(a.insert(1u, 1i));
+        assert!(a.insert(1u, 1i).is_none());
         assert!(a > b && a >= b);
         assert!(b < a && b <= a);
-        assert!(b.insert(2, 2));
+        assert!(b.insert(2, 2).is_none());
         assert!(b > a && b >= a);
         assert!(a < b && a <= b);
     }
@@ -948,7 +944,7 @@ mod test_map {
         let map: VecMap<char> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
-            assert_eq!(map.find(&k), Some(&v));
+            assert_eq!(map.get(&k), Some(&v));
         }
     }
 
@@ -1022,7 +1018,7 @@ mod bench {
         let mut m : VecMap<uint> = VecMap::new();
         find_rand_n(100, &mut m, b,
                     |m, i| { m.insert(i, 1); },
-                    |m, i| { m.find(&i); });
+                    |m, i| { m.get(&i); });
     }
 
     #[bench]
@@ -1030,7 +1026,7 @@ mod bench {
         let mut m : VecMap<uint> = VecMap::new();
         find_rand_n(10_000, &mut m, b,
                     |m, i| { m.insert(i, 1); },
-                    |m, i| { m.find(&i); });
+                    |m, i| { m.get(&i); });
     }
 
     // Find seq
@@ -1039,7 +1035,7 @@ mod bench {
         let mut m : VecMap<uint> = VecMap::new();
         find_seq_n(100, &mut m, b,
                    |m, i| { m.insert(i, 1); },
-                   |m, i| { m.find(&i); });
+                   |m, i| { m.get(&i); });
     }
 
     #[bench]
@@ -1047,6 +1043,6 @@ mod bench {
         let mut m : VecMap<uint> = VecMap::new();
         find_seq_n(10_000, &mut m, b,
                    |m, i| { m.insert(i, 1); },
-                   |m, i| { m.find(&i); });
+                   |m, i| { m.get(&i); });
     }
 }
diff --git a/src/libstd/collections/hash/bench.rs b/src/libstd/collections/hash/bench.rs
index 62b93336a34..87aebb24f98 100644
--- a/src/libstd/collections/hash/bench.rs
+++ b/src/libstd/collections/hash/bench.rs
@@ -102,14 +102,14 @@ fn hashmap_as_queue(b: &mut Bencher) {
     let mut k = 1i;
 
     b.iter(|| {
-        m.pop(&k);
+        m.remove(&k);
         m.insert(k + 1000, k + 1000);
         k += 1;
     });
 }
 
 #[bench]
-fn find_pop_insert(b: &mut Bencher) {
+fn get_remove_insert(b: &mut Bencher) {
     use super::map::HashMap;
 
     let mut m = HashMap::new();
@@ -121,9 +121,9 @@ fn find_pop_insert(b: &mut Bencher) {
     let mut k = 1i;
 
     b.iter(|| {
-        m.find(&(k + 400));
-        m.find(&(k + 2000));
-        m.pop(&k);
+        m.get(&(k + 400));
+        m.get(&(k + 2000));
+        m.remove(&k);
         m.insert(k + 1000, k + 1000);
         k += 1;
     })
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 596e483c2f6..7ff332c295c 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -36,6 +36,9 @@ use super::table::{
     SafeHash
 };
 
+// FIXME(conventions): update capacity management to match other collections (no auto-shrink)
+// FIXME(conventions): axe find_copy/get_copy in favour of Option.cloned (also implement that)
+
 const INITIAL_LOG2_CAP: uint = 5;
 pub const INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5
 
@@ -233,7 +236,7 @@ impl DefaultResizePolicy {
 /// // look up the values associated with some keys.
 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
 /// for book in to_find.iter() {
-///     match book_reviews.find(book) {
+///     match book_reviews.get(book) {
 ///         Some(review) => println!("{}: {}", *book, *review),
 ///         None => println!("{} is unreviewed.", *book)
 ///     }
@@ -480,6 +483,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> HashMap<K, V, RandomSipHasher> {
         let hasher = RandomSipHasher::new();
         HashMap::with_hasher(hasher)
@@ -494,6 +498,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
         let hasher = RandomSipHasher::new();
         HashMap::with_capacity_and_hasher(capacity, hasher)
@@ -741,38 +746,6 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
-    /// Retrieves a mutable value for the given key.
-    /// See [`find_mut`](../trait.MutableMap.html#tymethod.find_mut) for a non-panicking
-    /// alternative.
-    ///
-    /// # Failure
-    ///
-    /// Fails if the key is not present.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// # #![allow(deprecated)]
-    /// 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["a"], 40);
-    ///
-    /// // A more direct way could be:
-    /// *map.get_mut(&"a") = -2;
-    /// assert_eq!(map["a"], -2);
-    /// ```
-    #[deprecated = "use indexing instead: `&mut map[key]`"]
-    pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
-        &mut self[*k]
-    }
-
     /// Return true if the map contains a value for the specified key,
     /// using equivalence.
     ///
@@ -875,6 +848,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("{}", key);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys(&self) -> Keys<K, V> {
         self.iter().map(|(k, _v)| k)
     }
@@ -896,6 +870,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("{}", key);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values(&self) -> Values<K, V> {
         self.iter().map(|(_k, v)| v)
     }
@@ -917,6 +892,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("key: {} val: {}", key, val);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter(&self) -> Entries<K, V> {
         Entries { inner: self.table.iter() }
     }
@@ -944,6 +920,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///     println!("key: {} val: {}", key, val);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter_mut(&mut self) -> MutEntries<K, V> {
         MutEntries { inner: self.table.iter_mut() }
     }
@@ -965,6 +942,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// // Not possible with .iter()
     /// let vec: Vec<(&str, int)> = map.into_iter().collect();
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveEntries<K, V> {
         MoveEntries {
             inner: self.table.into_iter().map(|(_, k, v)| (k, v))
@@ -996,6 +974,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// a.insert(1u, "a");
     /// assert_eq!(a.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.table.size() }
 
     /// Return true if the map contains no elements.
@@ -1011,6 +990,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert!(!a.is_empty());
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the map, removing all key-value pairs. Keeps the allocated memory
@@ -1026,6 +1006,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// a.clear();
     /// assert!(a.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
         // Prevent reallocations from happening from now on. Makes it possible
         // for the map to be reused but has a downside: reserves permanently.
@@ -1045,6 +1026,12 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
+    /// Deprecated: Renamed to `get`.
+    #[deprecated = "Renamed to `get`"]
+    pub fn find(&self, k: &K) -> Option<&V> {
+        self.get(k)
+    }
+
     /// Returns a reference to the value corresponding to the key.
     ///
     /// # Example
@@ -1054,10 +1041,11 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// let mut map = HashMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.find(&1), Some(&"a"));
-    /// assert_eq!(map.find(&2), None);
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
     /// ```
-    pub fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&self, k: &K) -> Option<&V> {
         self.search(k).map(|bucket| {
             let (_, v) = bucket.into_refs();
             v
@@ -1076,10 +1064,17 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(map.contains_key(&1), true);
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains_key(&self, k: &K) -> bool {
         self.search(k).is_some()
     }
 
+    /// Deprecated: Renamed to `get_mut`.
+    #[deprecated = "Renamed to `get_mut`"]
+    pub fn find_mut(&mut self, k: &K) -> Option<&mut V> {
+        self.get_mut(k)
+    }
+
     /// Returns a mutable reference to the value corresponding to the key.
     ///
     /// # Example
@@ -1089,13 +1084,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// let mut map = HashMap::new();
     /// map.insert(1u, "a");
-    /// match map.find_mut(&1) {
+    /// match map.get_mut(&1) {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
-    pub fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
         match self.search_mut(k) {
             Some(bucket) => {
                 let (_, v) = bucket.into_mut_refs();
@@ -1105,41 +1101,10 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         }
     }
 
-    /// Inserts a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Returns `true` if the key did
-    /// not already exist in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    ///
-    /// let mut map = HashMap::new();
-    /// assert_eq!(map.insert(2u, "value"), true);
-    /// assert_eq!(map.insert(2, "value2"), false);
-    /// assert_eq!(map[2], "value2");
-    /// ```
-    #[inline]
-    pub fn insert(&mut self, key: K, value: V) -> bool {
-        self.swap(key, value).is_none()
-    }
-
-    /// Removes a key-value pair from the map. Returns `true` if the key
-    /// was present in the map.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    ///
-    /// let mut map = HashMap::new();
-    /// assert_eq!(map.remove(&1u), false);
-    /// map.insert(1, "a");
-    /// assert_eq!(map.remove(&1), true);
-    /// ```
-    #[inline]
-    pub fn remove(&mut self, key: &K) -> bool {
-        self.pop(key).is_some()
+    /// Deprecated: Renamed to `insert`.
+    #[deprecated = "Renamed to `insert`"]
+    pub fn swap(&mut self, k: K, v: V) -> Option<V> {
+        self.insert(k, v)
     }
 
     /// Inserts a key-value pair from the map. If the key already had a value
@@ -1151,14 +1116,15 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// use std::collections::HashMap;
     ///
     /// let mut map = HashMap::new();
-    /// assert_eq!(map.swap(37u, "a"), None);
+    /// assert_eq!(map.insert(37u, "a"), None);
     /// assert_eq!(map.is_empty(), false);
     ///
     /// map.insert(37, "b");
-    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    pub fn swap(&mut self, k: K, v: V) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
         let hash = self.make_hash(&k);
         let potential_new_size = self.table.size() + 1;
         self.make_some_room(potential_new_size);
@@ -1170,6 +1136,12 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         retval
     }
 
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, k: &K) -> Option<V> {
+        self.remove(k)
+    }
+
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     ///
@@ -1180,10 +1152,11 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// let mut map = HashMap::new();
     /// map.insert(1u, "a");
-    /// assert_eq!(map.pop(&1), Some("a"));
-    /// assert_eq!(map.pop(&1), None);
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
     /// ```
-    pub fn pop(&mut self, k: &K) -> Option<V> {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, k: &K) -> Option<V> {
         if self.table.size() == 0 {
             return None
         }
@@ -1260,7 +1233,7 @@ impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
     /// let s: String = map.find_copy(&1).unwrap();
     /// ```
     pub fn find_copy(&self, k: &K) -> Option<V> {
-        self.find(k).map(|v| (*v).clone())
+        self.get(k).map(|v| (*v).clone())
     }
 
     /// Return a copy of the value corresponding to the key.
@@ -1288,7 +1261,7 @@ impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V,
         if self.len() != other.len() { return false; }
 
         self.iter().all(|(key, value)|
-            other.find(key).map_or(false, |v| *value == *v)
+            other.get(key).map_or(false, |v| *value == *v)
         )
     }
 }
@@ -1317,14 +1290,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H>
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Index<K, V> for HashMap<K, V, H> {
     #[inline]
     fn index<'a>(&'a self, index: &K) -> &'a V {
-        self.find(index).expect("no entry found for key")
+        self.get(index).expect("no entry found for key")
     }
 }
 
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> IndexMut<K, V> for HashMap<K, V, H> {
     #[inline]
     fn index_mut<'a>(&'a mut self, index: &K) -> &'a mut V {
-        match self.find_mut(index) {
+        match self.get_mut(index) {
             Some(v) => v,
             None => panic!("no entry found for key")
         }
@@ -1514,7 +1487,7 @@ mod test_map {
     fn test_create_capacity_zero() {
         let mut m = HashMap::with_capacity(0);
 
-        assert!(m.insert(1i, 1i));
+        assert!(m.insert(1i, 1i).is_none());
 
         assert!(m.contains_key(&1));
         assert!(!m.contains_key(&0));
@@ -1524,12 +1497,12 @@ mod test_map {
     fn test_insert() {
         let mut m = HashMap::new();
         assert_eq!(m.len(), 0);
-        assert!(m.insert(1i, 2i));
+        assert!(m.insert(1i, 2i).is_none());
         assert_eq!(m.len(), 1);
-        assert!(m.insert(2i, 4i));
+        assert!(m.insert(2i, 4i).is_none());
         assert_eq!(m.len(), 2);
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert_eq!(*m.find(&2).unwrap(), 4);
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert_eq!(*m.get(&2).unwrap(), 4);
     }
 
     local_data_key!(drop_vector: RefCell<Vec<int>>)
@@ -1588,7 +1561,7 @@ mod test_map {
 
             for i in range(0u, 50) {
                 let k = Dropable::new(i);
-                let v = m.pop(&k);
+                let v = m.remove(&k);
 
                 assert!(v.is_some());
 
@@ -1679,7 +1652,7 @@ mod test_map {
     #[test]
     fn test_empty_pop() {
         let mut m: HashMap<int, bool> = HashMap::new();
-        assert_eq!(m.pop(&0), None);
+        assert_eq!(m.remove(&0), None);
     }
 
     #[test]
@@ -1692,15 +1665,15 @@ mod test_map {
             assert!(m.is_empty());
 
             for i in range_inclusive(1i, 1000) {
-                assert!(m.insert(i, i));
+                assert!(m.insert(i, i).is_none());
 
                 for j in range_inclusive(1, i) {
-                    let r = m.find(&j);
+                    let r = m.get(&j);
                     assert_eq!(r, Some(&j));
                 }
 
                 for j in range_inclusive(i+1, 1000) {
-                    let r = m.find(&j);
+                    let r = m.get(&j);
                     assert_eq!(r, None);
                 }
             }
@@ -1711,7 +1684,7 @@ mod test_map {
 
             // remove forwards
             for i in range_inclusive(1i, 1000) {
-                assert!(m.remove(&i));
+                assert!(m.remove(&i).is_some());
 
                 for j in range_inclusive(1, i) {
                     assert!(!m.contains_key(&j));
@@ -1727,12 +1700,12 @@ mod test_map {
             }
 
             for i in range_inclusive(1i, 1000) {
-                assert!(m.insert(i, i));
+                assert!(m.insert(i, i).is_none());
             }
 
             // remove backwards
             for i in range_step_inclusive(1000i, 1, -1) {
-                assert!(m.remove(&i));
+                assert!(m.remove(&i).is_some());
 
                 for j in range_inclusive(i, 1000) {
                     assert!(!m.contains_key(&j));
@@ -1748,59 +1721,59 @@ mod test_map {
     #[test]
     fn test_find_mut() {
         let mut m = HashMap::new();
-        assert!(m.insert(1i, 12i));
-        assert!(m.insert(2i, 8i));
-        assert!(m.insert(5i, 14i));
+        assert!(m.insert(1i, 12i).is_none());
+        assert!(m.insert(2i, 8i).is_none());
+        assert!(m.insert(5i, 14i).is_none());
         let new = 100;
-        match m.find_mut(&5) {
+        match m.get_mut(&5) {
             None => panic!(), Some(x) => *x = new
         }
-        assert_eq!(m.find(&5), Some(&new));
+        assert_eq!(m.get(&5), Some(&new));
     }
 
     #[test]
     fn test_insert_overwrite() {
         let mut m = HashMap::new();
-        assert!(m.insert(1i, 2i));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert!(!m.insert(1i, 3i));
-        assert_eq!(*m.find(&1).unwrap(), 3);
+        assert!(m.insert(1i, 2i).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert!(!m.insert(1i, 3i).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 3);
     }
 
     #[test]
     fn test_insert_conflicts() {
         let mut m = HashMap::with_capacity(4);
-        assert!(m.insert(1i, 2i));
-        assert!(m.insert(5i, 3i));
-        assert!(m.insert(9i, 4i));
-        assert_eq!(*m.find(&9).unwrap(), 4);
-        assert_eq!(*m.find(&5).unwrap(), 3);
-        assert_eq!(*m.find(&1).unwrap(), 2);
+        assert!(m.insert(1i, 2i).is_none());
+        assert!(m.insert(5i, 3i).is_none());
+        assert!(m.insert(9i, 4i).is_none());
+        assert_eq!(*m.get(&9).unwrap(), 4);
+        assert_eq!(*m.get(&5).unwrap(), 3);
+        assert_eq!(*m.get(&1).unwrap(), 2);
     }
 
     #[test]
     fn test_conflict_remove() {
         let mut m = HashMap::with_capacity(4);
-        assert!(m.insert(1i, 2i));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert!(m.insert(5, 3));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert_eq!(*m.find(&5).unwrap(), 3);
-        assert!(m.insert(9, 4));
-        assert_eq!(*m.find(&1).unwrap(), 2);
-        assert_eq!(*m.find(&5).unwrap(), 3);
-        assert_eq!(*m.find(&9).unwrap(), 4);
-        assert!(m.remove(&1));
-        assert_eq!(*m.find(&9).unwrap(), 4);
-        assert_eq!(*m.find(&5).unwrap(), 3);
+        assert!(m.insert(1i, 2i).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert!(m.insert(5, 3).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert_eq!(*m.get(&5).unwrap(), 3);
+        assert!(m.insert(9, 4).is_none());
+        assert_eq!(*m.get(&1).unwrap(), 2);
+        assert_eq!(*m.get(&5).unwrap(), 3);
+        assert_eq!(*m.get(&9).unwrap(), 4);
+        assert!(m.remove(&1).is_some());
+        assert_eq!(*m.get(&9).unwrap(), 4);
+        assert_eq!(*m.get(&5).unwrap(), 3);
     }
 
     #[test]
     fn test_is_empty() {
         let mut m = HashMap::with_capacity(4);
-        assert!(m.insert(1i, 2i));
+        assert!(m.insert(1i, 2i).is_none());
         assert!(!m.is_empty());
-        assert!(m.remove(&1));
+        assert!(m.remove(&1).is_some());
         assert!(m.is_empty());
     }
 
@@ -1808,8 +1781,8 @@ mod test_map {
     fn test_pop() {
         let mut m = HashMap::new();
         m.insert(1i, 2i);
-        assert_eq!(m.pop(&1), Some(2));
-        assert_eq!(m.pop(&1), None);
+        assert_eq!(m.remove(&1), Some(2));
+        assert_eq!(m.remove(&1), None);
     }
 
     #[test]
@@ -1822,18 +1795,10 @@ mod test_map {
     }
 
     #[test]
-    fn test_swap() {
-        let mut m = HashMap::new();
-        assert_eq!(m.swap(1i, 2i), None);
-        assert_eq!(m.swap(1i, 3i), Some(2));
-        assert_eq!(m.swap(1i, 4i), Some(3));
-    }
-
-    #[test]
     fn test_iterate() {
         let mut m = HashMap::with_capacity(4);
         for i in range(0u, 32) {
-            assert!(m.insert(i, i*2));
+            assert!(m.insert(i, i*2).is_none());
         }
         assert_eq!(m.len(), 32);
 
@@ -1871,9 +1836,9 @@ mod test_map {
     #[test]
     fn test_find() {
         let mut m = HashMap::new();
-        assert!(m.find(&1i).is_none());
+        assert!(m.get(&1i).is_none());
         m.insert(1i, 2i);
-        match m.find(&1) {
+        match m.get(&1) {
             None => panic!(),
             Some(v) => assert_eq!(*v, 2)
         }
@@ -1882,7 +1847,7 @@ mod test_map {
     #[test]
     fn test_find_copy() {
         let mut m = HashMap::new();
-        assert!(m.find(&1i).is_none());
+        assert!(m.get(&1i).is_none());
 
         for i in range(1i, 10000) {
             m.insert(i, i + 7);
@@ -2026,7 +1991,7 @@ mod test_map {
         let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
-            assert_eq!(map.find(&k), Some(&v));
+            assert_eq!(map.get(&k), Some(&v));
         }
     }
 
@@ -2093,7 +2058,7 @@ mod test_map {
                 assert_eq!(view.set(100), 10);
             }
         }
-        assert_eq!(map.find(&1).unwrap(), &100);
+        assert_eq!(map.get(&1).unwrap(), &100);
         assert_eq!(map.len(), 6);
 
 
@@ -2106,7 +2071,7 @@ mod test_map {
                 *v = new_v;
             }
         }
-        assert_eq!(map.find(&2).unwrap(), &200);
+        assert_eq!(map.get(&2).unwrap(), &200);
         assert_eq!(map.len(), 6);
 
         // Existing key (take)
@@ -2116,7 +2081,7 @@ mod test_map {
                 assert_eq!(view.take(), 30);
             }
         }
-        assert_eq!(map.find(&3), None);
+        assert_eq!(map.get(&3), None);
         assert_eq!(map.len(), 5);
 
 
@@ -2127,7 +2092,7 @@ mod test_map {
                 assert_eq!(*view.set(1000), 1000);
             }
         }
-        assert_eq!(map.find(&10).unwrap(), &1000);
+        assert_eq!(map.get(&10).unwrap(), &1000);
         assert_eq!(map.len(), 6);
     }
 }
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 688036d22dd..45574deec41 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -23,6 +23,9 @@ use result::{Ok, Err};
 
 use super::map::{HashMap, Entries, MoveEntries, INITIAL_CAPACITY};
 
+// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
+// FIXME(conventions): update capacity management to match other collections (no auto-shrink)
+
 
 // Future Optimization (FIXME!)
 // =============================
@@ -103,6 +106,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
     /// let mut set: HashSet<int> = HashSet::new();
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> HashSet<T, RandomSipHasher> {
         HashSet::with_capacity(INITIAL_CAPACITY)
     }
@@ -117,6 +121,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
     /// let mut set: HashSet<int> = HashSet::with_capacity(10);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
         HashSet { map: HashMap::with_capacity(capacity) }
     }
@@ -240,16 +245,11 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
         self.map.keys()
     }
 
-    /// Deprecated: use `into_iter`.
-    #[deprecated = "use into_iter"]
-    pub fn move_iter(self) -> SetMoveItems<T> {
-        self.into_iter()
-    }
-
     /// Creates a consuming iterator, that is, one that moves each value out
     /// of the set in arbitrary order. The set cannot be used after calling
     /// this.
@@ -270,6 +270,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     ///     println!("{}", x);
     /// }
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> SetMoveItems<T> {
         self.map.into_iter().map(|(k, _)| k)
     }
@@ -296,6 +297,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect();
     /// assert_eq!(diff, [4i].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> SetAlgebraItems<'a, T, H> {
         Repeat::new(other).zip(self.iter())
             .filter_map(|(other, elt)| {
@@ -323,6 +325,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff1, diff2);
     /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
         -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> {
         self.difference(other).chain(other.difference(self))
@@ -345,6 +348,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect();
     /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>)
         -> SetAlgebraItems<'a, T, H> {
         Repeat::new(other).zip(self.iter())
@@ -370,6 +374,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect();
     /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn union<'a>(&'a self, other: &'a HashSet<T, H>)
         -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
         self.iter().chain(other.difference(self))
@@ -387,6 +392,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// v.insert(1u);
     /// assert_eq!(v.len(), 1);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns true if the set contains no elements
@@ -401,6 +407,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// v.insert(1u);
     /// assert!(!v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.map.len() == 0 }
 
     /// Clears the set, removing all values.
@@ -415,6 +422,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// v.clear();
     /// assert!(v.is_empty());
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.map.clear() }
 
     /// Returns `true` if the set contains a value.
@@ -428,6 +436,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.contains(&1), true);
     /// assert_eq!(set.contains(&4), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
 
     /// Returns `true` if the set has no elements in common with `other`.
@@ -447,6 +456,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// b.insert(1);
     /// assert_eq!(a.is_disjoint(&b), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| !other.contains(v))
     }
@@ -467,6 +477,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// set.insert(4);
     /// assert_eq!(set.is_subset(&sup), false);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| other.contains(v))
     }
@@ -491,6 +502,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.is_superset(&sub), true);
     /// ```
     #[inline]
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
         other.is_subset(self)
     }
@@ -509,7 +521,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.insert(2), false);
     /// assert_eq!(set.len(), 1);
     /// ```
-    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
 
     /// Removes a value from the set. Returns `true` if the value was
     /// present in the set.
@@ -525,7 +538,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.remove(&2), true);
     /// assert_eq!(set.remove(&2), false);
     /// ```
-    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value).is_some() }
 }
 
 impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
diff --git a/src/libstd/collections/lru_cache.rs b/src/libstd/collections/lru_cache.rs
index 93e649f9355..aab0924e7e4 100644
--- a/src/libstd/collections/lru_cache.rs
+++ b/src/libstd/collections/lru_cache.rs
@@ -20,20 +20,20 @@
 //! use std::collections::LruCache;
 //!
 //! let mut cache: LruCache<int, int> = LruCache::new(2);
-//! cache.put(1, 10);
-//! cache.put(2, 20);
-//! cache.put(3, 30);
+//! cache.insert(1, 10);
+//! cache.insert(2, 20);
+//! cache.insert(3, 30);
 //! assert!(cache.get(&1).is_none());
 //! assert_eq!(*cache.get(&2).unwrap(), 20);
 //! assert_eq!(*cache.get(&3).unwrap(), 30);
 //!
-//! cache.put(2, 22);
+//! cache.insert(2, 22);
 //! assert_eq!(*cache.get(&2).unwrap(), 22);
 //!
-//! cache.put(6, 60);
+//! cache.insert(6, 60);
 //! assert!(cache.get(&3).is_none());
 //!
-//! cache.change_capacity(1);
+//! cache.set_capacity(1);
 //! assert!(cache.get(&2).is_none());
 //! ```
 
@@ -49,6 +49,9 @@ use boxed::Box;
 use ptr;
 use result::{Ok, Err};
 
+// FIXME(conventions): implement iterators?
+// FIXME(conventions): implement indexing?
+
 struct KeyRef<K> { k: *const K }
 
 struct LruEntry<K, V> {
@@ -99,6 +102,7 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache: LruCache<int, &str> = LruCache::new(10);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new(capacity: uint) -> LruCache<K, V> {
         let cache = LruCache {
             map: HashMap::new(),
@@ -112,7 +116,14 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
         return cache;
     }
 
-    /// Put a key-value pair into cache.
+    /// Deprecated: Replaced with `insert`.
+    #[deprecated = "Replaced with `insert`"]
+    pub fn put(&mut self, k: K, v: V) {
+        self.insert(k, v);
+    }
+
+    /// Inserts a key-value pair into the cache. If the key already existed, the old value is
+    /// returned.
     ///
     /// # Example
     ///
@@ -120,22 +131,23 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
     /// assert_eq!(cache.get(&1), Some(&"a"));
     /// assert_eq!(cache.get(&2), Some(&"b"));
     /// ```
-    pub fn put(&mut self, k: K, v: V) {
-        let (node_ptr, node_opt) = match self.map.find_mut(&KeyRef{k: &k}) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
+        let (node_ptr, node_opt, old_val) = match self.map.get_mut(&KeyRef{k: &k}) {
             Some(node) => {
-                node.value = v;
+                let old_val = mem::replace(&mut node.value, v);
                 let node_ptr: *mut LruEntry<K, V> = &mut **node;
-                (node_ptr, None)
+                (node_ptr, None, Some(old_val))
             }
             None => {
                 let mut node = box LruEntry::new(k, v);
                 let node_ptr: *mut LruEntry<K, V> = &mut *node;
-                (node_ptr, Some(node))
+                (node_ptr, Some(node), None)
             }
         };
         match node_opt {
@@ -146,13 +158,14 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
             }
             Some(node) => {
                 let keyref = unsafe { &(*node_ptr).key };
-                self.map.swap(KeyRef{k: keyref}, node);
+                self.map.insert(KeyRef{k: keyref}, node);
                 self.attach(node_ptr);
                 if self.len() > self.capacity() {
                     self.remove_lru();
                 }
             }
         }
+        old_val
     }
 
     /// Return a value corresponding to the key in the cache.
@@ -163,16 +176,17 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
-    /// cache.put(2, "c");
-    /// cache.put(3, "d");
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
+    /// cache.insert(2, "c");
+    /// cache.insert(3, "d");
     ///
     /// assert_eq!(cache.get(&1), None);
     /// assert_eq!(cache.get(&2), Some(&"c"));
     /// ```
-    pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
-        let (value, node_ptr_opt) = match self.map.find_mut(&KeyRef{k: k}) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn get(&mut self, k: &K) -> Option<&V> {
+        let (value, node_ptr_opt) = match self.map.get_mut(&KeyRef{k: k}) {
             None => (None, None),
             Some(node) => {
                 let node_ptr: *mut LruEntry<K, V> = &mut **node;
@@ -189,6 +203,12 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
         return value;
     }
 
+    /// Deprecated: Renamed to `remove`.
+    #[deprecated = "Renamed to `remove`"]
+    pub fn pop(&mut self, k: &K) -> Option<V> {
+        self.remove(k)
+    }
+
     /// Remove and return a value corresponding to the key from the cache.
     ///
     /// # Example
@@ -197,15 +217,16 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(2i, "a");
+    /// cache.insert(2i, "a");
     ///
-    /// assert_eq!(cache.pop(&1), None);
-    /// assert_eq!(cache.pop(&2), Some("a"));
-    /// assert_eq!(cache.pop(&2), None);
+    /// assert_eq!(cache.remove(&1), None);
+    /// assert_eq!(cache.remove(&2), Some("a"));
+    /// assert_eq!(cache.remove(&2), None);
     /// assert_eq!(cache.len(), 0);
     /// ```
-    pub fn pop(&mut self, k: &K) -> Option<V> {
-        match self.map.pop(&KeyRef{k: k}) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn remove(&mut self, k: &K) -> Option<V> {
+        match self.map.remove(&KeyRef{k: k}) {
             None => None,
             Some(lru_entry) => Some(lru_entry.value)
         }
@@ -220,10 +241,17 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// let mut cache: LruCache<int, &str> = LruCache::new(2);
     /// assert_eq!(cache.capacity(), 2);
     /// ```
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn capacity(&self) -> uint {
         self.max_size
     }
 
+    /// Deprecated: Renamed to `set_capacity`.
+    #[deprecated = "Renamed to `set_capacity`"]
+    pub fn change_capacity(&mut self, capacity: uint) {
+        self.set_capacity(capacity)
+    }
+
     /// Change the number of key-value pairs the cache can hold. Remove
     /// least-recently-used key-value pairs if necessary.
     ///
@@ -233,29 +261,30 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     /// use std::collections::LruCache;
     /// let mut cache = LruCache::new(2);
     ///
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
-    /// cache.put(3, "c");
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
+    /// cache.insert(3, "c");
     ///
     /// assert_eq!(cache.get(&1), None);
     /// assert_eq!(cache.get(&2), Some(&"b"));
     /// assert_eq!(cache.get(&3), Some(&"c"));
     ///
-    /// cache.change_capacity(3);
-    /// cache.put(1i, "a");
-    /// cache.put(2, "b");
+    /// cache.set_capacity(3);
+    /// cache.insert(1i, "a");
+    /// cache.insert(2, "b");
     ///
     /// assert_eq!(cache.get(&1), Some(&"a"));
     /// assert_eq!(cache.get(&2), Some(&"b"));
     /// assert_eq!(cache.get(&3), Some(&"c"));
     ///
-    /// cache.change_capacity(1);
+    /// cache.set_capacity(1);
     ///
     /// assert_eq!(cache.get(&1), None);
     /// assert_eq!(cache.get(&2), None);
     /// assert_eq!(cache.get(&3), Some(&"c"));
     /// ```
-    pub fn change_capacity(&mut self, capacity: uint) {
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    pub fn set_capacity(&mut self, capacity: uint) {
         for _ in range(capacity, self.len()) {
             self.remove_lru();
         }
@@ -267,7 +296,7 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
         if self.len() > 0 {
             let lru = unsafe { (*self.head).prev };
             self.detach(lru);
-            self.map.pop(&KeyRef{k: unsafe { &(*lru).key }});
+            self.map.remove(&KeyRef{k: unsafe { &(*lru).key }});
         }
     }
 
@@ -290,12 +319,15 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
     }
 
     /// Return the number of key-value pairs in the cache.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns whether the cache is currently empty.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clear the cache of all key-value pairs.
+    #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) { self.map.clear(); }
 }
 
@@ -347,8 +379,8 @@ mod tests {
     #[test]
     fn test_put_and_get() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
         assert_opt_eq(cache.get(&1), 10);
         assert_opt_eq(cache.get(&2), 20);
         assert_eq!(cache.len(), 2);
@@ -357,8 +389,8 @@ mod tests {
     #[test]
     fn test_put_update() {
         let mut cache: LruCache<String, Vec<u8>> = LruCache::new(1);
-        cache.put("1".to_string(), vec![10, 10]);
-        cache.put("1".to_string(), vec![10, 19]);
+        cache.insert("1".to_string(), vec![10, 10]);
+        cache.insert("1".to_string(), vec![10, 19]);
         assert_opt_eq(cache.get(&"1".to_string()), vec![10, 19]);
         assert_eq!(cache.len(), 1);
     }
@@ -366,22 +398,22 @@ mod tests {
     #[test]
     fn test_expire_lru() {
         let mut cache: LruCache<String, String> = LruCache::new(2);
-        cache.put("foo1".to_string(), "bar1".to_string());
-        cache.put("foo2".to_string(), "bar2".to_string());
-        cache.put("foo3".to_string(), "bar3".to_string());
+        cache.insert("foo1".to_string(), "bar1".to_string());
+        cache.insert("foo2".to_string(), "bar2".to_string());
+        cache.insert("foo3".to_string(), "bar3".to_string());
         assert!(cache.get(&"foo1".to_string()).is_none());
-        cache.put("foo2".to_string(), "bar2update".to_string());
-        cache.put("foo4".to_string(), "bar4".to_string());
+        cache.insert("foo2".to_string(), "bar2update".to_string());
+        cache.insert("foo4".to_string(), "bar4".to_string());
         assert!(cache.get(&"foo3".to_string()).is_none());
     }
 
     #[test]
     fn test_pop() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
         assert_eq!(cache.len(), 2);
-        let opt1 = cache.pop(&1);
+        let opt1 = cache.remove(&1);
         assert!(opt1.is_some());
         assert_eq!(opt1.unwrap(), 10);
         assert!(cache.get(&1).is_none());
@@ -392,9 +424,9 @@ mod tests {
     fn test_change_capacity() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
         assert_eq!(cache.capacity(), 2);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.change_capacity(1);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
+        cache.set_capacity(1);
         assert!(cache.get(&1).is_none());
         assert_eq!(cache.capacity(), 1);
     }
@@ -402,25 +434,25 @@ mod tests {
     #[test]
     fn test_to_string() {
         let mut cache: LruCache<int, int> = LruCache::new(3);
-        cache.put(1, 10);
-        cache.put(2, 20);
-        cache.put(3, 30);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
+        cache.insert(3, 30);
         assert_eq!(cache.to_string(), "{3: 30, 2: 20, 1: 10}".to_string());
-        cache.put(2, 22);
+        cache.insert(2, 22);
         assert_eq!(cache.to_string(), "{2: 22, 3: 30, 1: 10}".to_string());
-        cache.put(6, 60);
+        cache.insert(6, 60);
         assert_eq!(cache.to_string(), "{6: 60, 2: 22, 3: 30}".to_string());
         cache.get(&3);
         assert_eq!(cache.to_string(), "{3: 30, 6: 60, 2: 22}".to_string());
-        cache.change_capacity(2);
+        cache.set_capacity(2);
         assert_eq!(cache.to_string(), "{3: 30, 6: 60}".to_string());
     }
 
     #[test]
     fn test_clear() {
         let mut cache: LruCache<int, int> = LruCache::new(2);
-        cache.put(1, 10);
-        cache.put(2, 20);
+        cache.insert(1, 10);
+        cache.insert(2, 20);
         cache.clear();
         assert!(cache.get(&1).is_none());
         assert!(cache.get(&2).is_none());
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 13486d4b8f8..3419a3d98a1 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -278,7 +278,7 @@
 //!     }
 //! }
 //!
-//! assert_eq!(count.find(&'s'), Some(&8));
+//! assert_eq!(count.get(&'s'), Some(&8));
 //!
 //! println!("Number of occurences of each character");
 //! for (char, count) in count.iter() {