auto merge of #20356 : Gankro/rust/stab, r=aturon

This stabilizes most of libcollections, carefully avoiding sections of API which are being managed in other PRs. APIs which are not stable are marked explicitly unstable with a reason.

Deprecates:

* DList
  * rotate_forward
  * rotate_backward
  * prepend
  * insert_when
  * insert_ordered
  * merge

* VecMap
  * update
  * update_with_key

* Renames and newtypes the Bitv and BitvSet iterators to match conventions.

* Removes the Copy impl from DList's Iter.

as such this is a

[breaking-change]

2 files changed, 83 insertions, 43 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 3bfe2009f8b..f6063df5434 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -296,6 +296,7 @@ fn test_resize_policy() {
 /// }
 /// ```
 #[deriving(Clone)]
+#[stable]
 pub struct HashMap<K, V, H = RandomSipHasher> {
     // All hashes are keyed on these values, to prevent hash collision attacks.
     hasher: H,
@@ -508,7 +509,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// let mut map: HashMap<&str, int> = HashMap::new();
     /// ```
     #[inline]
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn new() -> HashMap<K, V, RandomSipHasher> {
         let hasher = RandomSipHasher::new();
         HashMap::with_hasher(hasher)
@@ -523,7 +524,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"]
+    #[stable]
     pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
         let hasher = RandomSipHasher::new();
         HashMap::with_capacity_and_hasher(capacity, hasher)
@@ -546,6 +547,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// map.insert(1i, 2u);
     /// ```
     #[inline]
+    #[unstable = "hasher stuff is unclear"]
     pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
         HashMap {
             hasher:        hasher,
@@ -573,6 +575,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// map.insert(1i, 2u);
     /// ```
     #[inline]
+    #[unstable = "hasher stuff is unclear"]
     pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
         let resize_policy = DefaultResizePolicy::new();
         let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
@@ -595,7 +598,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert!(map.capacity() >= 100);
     /// ```
     #[inline]
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn capacity(&self) -> uint {
         self.resize_policy.usable_capacity(self.table.capacity())
     }
@@ -615,7 +618,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// let mut map: HashMap<&str, int> = HashMap::new();
     /// map.reserve(10);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn reserve(&mut self, additional: uint) {
         let new_size = self.len().checked_add(additional).expect("capacity overflow");
         let min_cap = self.resize_policy.min_capacity(new_size);
@@ -727,7 +730,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// map.shrink_to_fit();
     /// assert!(map.capacity() >= 2);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn shrink_to_fit(&mut self) {
         let min_capacity = self.resize_policy.min_capacity(self.len());
         let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
@@ -845,7 +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"]
+    #[stable]
     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
         fn first<A, B>((a, _): (A, B)) -> A { a }
         let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr
@@ -870,7 +873,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"]
+    #[stable]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
         fn second<A, B>((_, b): (A, B)) -> B { b }
         let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr
@@ -895,7 +898,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"]
+    #[stable]
     pub fn iter(&self) -> Iter<K, V> {
         Iter { inner: self.table.iter() }
     }
@@ -923,7 +926,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"]
+    #[stable]
     pub fn iter_mut(&mut self) -> IterMut<K, V> {
         IterMut { inner: self.table.iter_mut() }
     }
@@ -945,7 +948,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"]
+    #[stable]
     pub fn into_iter(self) -> IntoIter<K, V> {
         fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
         let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
@@ -976,7 +979,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"]
+    #[stable]
     pub fn len(&self) -> uint { self.table.size() }
 
     /// Return true if the map contains no elements.
@@ -992,7 +995,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"]
+    #[stable]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
     /// Clears the map, returning all key-value pairs as an iterator. Keeps the
@@ -1038,7 +1041,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"]
+    #[stable]
     #[inline]
     pub fn clear(&mut self) {
         self.drain();
@@ -1066,7 +1069,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(map.get(&1), Some(&"a"));
     /// assert_eq!(map.get(&2), None);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn get<Sized? Q>(&self, k: &Q) -> Option<&V>
         where Q: Hash<S> + Eq + BorrowFrom<K>
     {
@@ -1089,7 +1092,7 @@ 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"]
+    #[stable]
     pub fn contains_key<Sized? Q>(&self, k: &Q) -> bool
         where Q: Hash<S> + Eq + BorrowFrom<K>
     {
@@ -1121,7 +1124,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// }
     /// assert_eq!(map[1], "b");
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn get_mut<Sized? Q>(&mut self, k: &Q) -> Option<&mut V>
         where Q: Hash<S> + Eq + BorrowFrom<K>
     {
@@ -1150,7 +1153,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(map.insert(37, "c"), Some("b"));
     /// assert_eq!(map[37], "c");
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
         let hash = self.make_hash(&k);
         self.reserve(1);
@@ -1185,7 +1188,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(map.remove(&1), Some("a"));
     /// assert_eq!(map.remove(&1), None);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn remove<Sized? Q>(&mut self, k: &Q) -> Option<V>
         where Q: Hash<S> + Eq + BorrowFrom<K>
     {
@@ -1275,6 +1278,7 @@ impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V,
 #[stable]
 impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
 
+#[stable]
 impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "{{"));
@@ -1296,6 +1300,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H>
     }
 }
 
+#[stable]
 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> Index<Q, V> for HashMap<K, V, H>
     where Q: BorrowFrom<K> + Hash<S> + Eq
 {
@@ -1305,6 +1310,7 @@ impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> Index<Q, V> for HashMap<K, V
     }
 }
 
+#[stable]
 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K, V, H>
     where Q: BorrowFrom<K> + Hash<S> + Eq
 {
@@ -1315,6 +1321,7 @@ impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K
 }
 
 /// HashMap iterator
+#[stable]
 pub struct Iter<'a, K: 'a, V: 'a> {
     inner: table::Iter<'a, K, V>
 }
@@ -1329,11 +1336,13 @@ impl<'a, K, V> Clone for Iter<'a, K, V> {
 }
 
 /// HashMap mutable values iterator
+#[stable]
 pub struct IterMut<'a, K: 'a, V: 'a> {
     inner: table::IterMut<'a, K, V>
 }
 
 /// HashMap move iterator
+#[stable]
 pub struct IntoIter<K, V> {
     inner: iter::Map<
         (SafeHash, K, V),
@@ -1344,6 +1353,7 @@ pub struct IntoIter<K, V> {
 }
 
 /// HashMap keys iterator
+#[stable]
 pub struct Keys<'a, K: 'a, V: 'a> {
     inner: Map<(&'a K, &'a V), &'a K, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
 }
@@ -1358,6 +1368,7 @@ impl<'a, K, V> Clone for Keys<'a, K, V> {
 }
 
 /// HashMap values iterator
+#[stable]
 pub struct Values<'a, K: 'a, V: 'a> {
     inner: Map<(&'a K, &'a V), &'a V, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
 }
@@ -1372,6 +1383,7 @@ impl<'a, K, V> Clone for Values<'a, K, V> {
 }
 
 /// HashMap drain iterator
+#[unstable = "matches collection reform specification, waiting for dust to settle"]
 pub struct Drain<'a, K: 'a, V: 'a> {
     inner: iter::Map<
         (SafeHash, K, V),
@@ -1410,31 +1422,37 @@ enum VacantEntryState<K, V, M> {
     NoElem(EmptyBucket<K, V, M>),
 }
 
+#[stable]
 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Iter<'a, K, V> {
     #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
+#[stable]
 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for IterMut<'a, K, V> {
     #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
+#[stable]
 impl<K, V> Iterator<(K, V)> for IntoIter<K, V> {
     #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
+#[stable]
 impl<'a, K, V> Iterator<&'a K> for Keys<'a, K, V> {
     #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
+#[stable]
 impl<'a, K, V> Iterator<&'a V> for Values<'a, K, V> {
     #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
+#[stable]
 impl<'a, K: 'a, V: 'a> Iterator<(K, V)> for Drain<'a, K, V> {
     #[inline]
     fn next(&mut self) -> Option<(K, V)> {
@@ -1491,6 +1509,7 @@ impl<'a, K, V> VacantEntry<'a, K, V> {
     }
 }
 
+#[stable]
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
     fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
         let lower = iter.size_hint().0;
@@ -1500,6 +1519,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for Has
     }
 }
 
+#[stable]
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extend<(K, V)> for HashMap<K, V, H> {
     fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
         for (k, v) in iter {
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 93f6895f688..74fb63a7a9e 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -90,6 +90,7 @@ use super::map::{mod, HashMap, Keys, INITIAL_CAPACITY};
 /// }
 /// ```
 #[deriving(Clone)]
+#[stable]
 pub struct HashSet<T, H = RandomSipHasher> {
     map: HashMap<T, (), H>
 }
@@ -104,7 +105,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"]
+    #[stable]
     pub fn new() -> HashSet<T, RandomSipHasher> {
         HashSet::with_capacity(INITIAL_CAPACITY)
     }
@@ -119,7 +120,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"]
+    #[stable]
     pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
         HashSet { map: HashMap::with_capacity(capacity) }
     }
@@ -142,6 +143,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// set.insert(2u);
     /// ```
     #[inline]
+    #[unstable = "hasher stuff is unclear"]
     pub fn with_hasher(hasher: H) -> HashSet<T, H> {
         HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
     }
@@ -165,6 +167,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// set.insert(1i);
     /// ```
     #[inline]
+    #[unstable = "hasher stuff is unclear"]
     pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
         HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
     }
@@ -179,7 +182,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert!(set.capacity() >= 100);
     /// ```
     #[inline]
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn capacity(&self) -> uint {
         self.map.capacity()
     }
@@ -199,7 +202,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// let mut set: HashSet<int> = HashSet::new();
     /// set.reserve(10);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn reserve(&mut self, additional: uint) {
         self.map.reserve(additional)
     }
@@ -220,7 +223,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// set.shrink_to_fit();
     /// assert!(set.capacity() >= 2);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn shrink_to_fit(&mut self) {
         self.map.shrink_to_fit()
     }
@@ -248,8 +251,8 @@ 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) -> Iter<'a, T> {
+    #[stable]
+    pub fn iter(&self) -> Iter<T> {
         Iter { iter: self.map.keys() }
     }
 
@@ -273,7 +276,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"]
+    #[stable]
     pub fn into_iter(self) -> IntoIter<T> {
         fn first<A, B>((a, _): (A, B)) -> A { a }
         let first: fn((T, ())) -> T = first;
@@ -303,7 +306,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"]
+    #[stable]
     pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> Difference<'a, T, H> {
         Difference {
             iter: self.iter(),
@@ -331,7 +334,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"]
+    #[stable]
     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
         -> SymmetricDifference<'a, T, H> {
         SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
@@ -354,7 +357,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"]
+    #[stable]
     pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>) -> Intersection<'a, T, H> {
         Intersection {
             iter: self.iter(),
@@ -379,7 +382,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"]
+    #[stable]
     pub fn union<'a>(&'a self, other: &'a HashSet<T, H>) -> Union<'a, T, H> {
         Union { iter: self.iter().chain(other.difference(self)) }
     }
@@ -396,7 +399,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"]
+    #[stable]
     pub fn len(&self) -> uint { self.map.len() }
 
     /// Returns true if the set contains no elements
@@ -411,7 +414,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"]
+    #[stable]
     pub fn is_empty(&self) -> bool { self.map.len() == 0 }
 
     /// Clears the set, returning all elements in an iterator.
@@ -436,7 +439,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"]
+    #[stable]
     pub fn clear(&mut self) { self.map.clear() }
 
     /// Returns `true` if the set contains a value.
@@ -454,7 +457,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"]
+    #[stable]
     pub fn contains<Sized? Q>(&self, value: &Q) -> bool
         where Q: BorrowFrom<T> + Hash<S> + Eq
     {
@@ -478,7 +481,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"]
+    #[stable]
     pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| !other.contains(v))
     }
@@ -499,7 +502,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"]
+    #[stable]
     pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| other.contains(v))
     }
@@ -524,7 +527,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"]
+    #[stable]
     pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
         other.is_subset(self)
     }
@@ -543,7 +546,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.insert(2), false);
     /// assert_eq!(set.len(), 1);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     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
@@ -564,7 +567,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.remove(&2), true);
     /// assert_eq!(set.remove(&2), false);
     /// ```
-    #[unstable = "matches collection reform specification, waiting for dust to settle"]
+    #[stable]
     pub fn remove<Sized? Q>(&mut self, value: &Q) -> bool
         where Q: BorrowFrom<T> + Hash<S> + Eq
     {
@@ -584,6 +587,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
 #[stable]
 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
 
+#[stable]
 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "{{"));
@@ -597,6 +601,7 @@ impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
     }
 }
 
+#[stable]
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
     fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
         let lower = iter.size_hint().0;
@@ -606,6 +611,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T,
     }
 }
 
+#[stable]
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extend<T> for HashSet<T, H> {
     fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
         for k in iter {
@@ -622,7 +628,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
     }
 }
 
-#[unstable = "matches collection reform specification, waiting for dust to settle"]
+#[stable]
 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 BitOr<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     /// Returns the union of `self` and `rhs` as a new `HashSet<T, H>`.
@@ -650,7 +656,7 @@ BitOr<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     }
 }
 
-#[unstable = "matches collection reform specification, waiting for dust to settle"]
+#[stable]
 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 BitAnd<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, H>`.
@@ -678,7 +684,7 @@ BitAnd<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     }
 }
 
-#[unstable = "matches collection reform specification, waiting for dust to settle"]
+#[stable]
 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 BitXor<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, H>`.
@@ -706,7 +712,7 @@ BitXor<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     }
 }
 
-#[unstable = "matches collection reform specification, waiting for dust to settle"]
+#[stable]
 impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
 Sub<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
     /// Returns the difference of `self` and `rhs` as a new `HashSet<T, H>`.
@@ -735,21 +741,25 @@ Sub<&'b HashSet<T, H>, HashSet<T, H>> for &'a HashSet<T, H> {
 }
 
 /// HashSet iterator
+#[stable]
 pub struct Iter<'a, K: 'a> {
     iter: Keys<'a, K, ()>
 }
 
 /// HashSet move iterator
+#[stable]
 pub struct IntoIter<K> {
     iter: Map<(K, ()), K, map::IntoIter<K, ()>, fn((K, ())) -> K>
 }
 
 /// HashSet drain iterator
+#[stable]
 pub struct Drain<'a, K: 'a> {
     iter: Map<(K, ()), K, map::Drain<'a, K, ()>, fn((K, ())) -> K>,
 }
 
 /// Intersection iterator
+#[stable]
 pub struct Intersection<'a, T: 'a, H: 'a> {
     // iterator of the first set
     iter: Iter<'a, T>,
@@ -758,6 +768,7 @@ pub struct Intersection<'a, T: 'a, H: 'a> {
 }
 
 /// Difference iterator
+#[stable]
 pub struct Difference<'a, T: 'a, H: 'a> {
     // iterator of the first set
     iter: Iter<'a, T>,
@@ -766,30 +777,36 @@ pub struct Difference<'a, T: 'a, H: 'a> {
 }
 
 /// Symmetric difference iterator.
+#[stable]
 pub struct SymmetricDifference<'a, T: 'a, H: 'a> {
     iter: Chain<Difference<'a, T, H>, Difference<'a, T, H>>
 }
 
 /// Set union iterator.
+#[stable]
 pub struct Union<'a, T: 'a, H: 'a> {
     iter: Chain<Iter<'a, T>, Difference<'a, T, H>>
 }
 
+#[stable]
 impl<'a, K> Iterator<&'a K> for Iter<'a, K> {
     fn next(&mut self) -> Option<&'a K> { self.iter.next() }
     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
+#[stable]
 impl<K> Iterator<K> for IntoIter<K> {
     fn next(&mut self) -> Option<K> { self.iter.next() }
     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
+#[stable]
 impl<'a, K: 'a> Iterator<K> for Drain<'a, K> {
     fn next(&mut self) -> Option<K> { self.iter.next() }
     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
+#[stable]
 impl<'a, T, S, H> Iterator<&'a T> for Intersection<'a, T, H>
     where T: Eq + Hash<S>, H: Hasher<S>
 {
@@ -810,6 +827,7 @@ impl<'a, T, S, H> Iterator<&'a T> for Intersection<'a, T, H>
     }
 }
 
+#[stable]
 impl<'a, T, S, H> Iterator<&'a T> for Difference<'a, T, H>
     where T: Eq + Hash<S>, H: Hasher<S>
 {
@@ -830,6 +848,7 @@ impl<'a, T, S, H> Iterator<&'a T> for Difference<'a, T, H>
     }
 }
 
+#[stable]
 impl<'a, T, S, H> Iterator<&'a T> for SymmetricDifference<'a, T, H>
     where T: Eq + Hash<S>, H: Hasher<S>
 {
@@ -837,6 +856,7 @@ impl<'a, T, S, H> Iterator<&'a T> for SymmetricDifference<'a, T, H>
     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
+#[stable]
 impl<'a, T, S, H> Iterator<&'a T> for Union<'a, T, H>
     where T: Eq + Hash<S>, H: Hasher<S>
 {