std: Add Vec.reserve for rounding-up reservation.

`.reserve_exact` can cause pathological O(n^2) behaviour, so providing a
`.reserve` that ensures that capacity doubles (if you step 1, 2, ..., n)
is more efficient.

cc #11949

1 files changed, 8 insertions, 1 deletions

diff --git a/src/libstd/vec_ng.rs b/src/libstd/vec_ng.rs
index 2f39adc25d3..52d3405f8c1 100644
--- a/src/libstd/vec_ng.rs
+++ b/src/libstd/vec_ng.rs
@@ -18,6 +18,7 @@ use container::Container;
 use iter::{DoubleEndedIterator, FromIterator, Iterator};
 use libc::{free, c_void};
 use mem::{size_of, move_val_init};
+use num;
 use num::CheckedMul;
 use ops::Drop;
 use option::{None, Option, Some};
@@ -136,6 +137,12 @@ impl<T> Vec<T> {
         self.cap
     }
 
+    pub fn reserve(&mut self, capacity: uint) {
+        if capacity >= self.len {
+            self.reserve_exact(num::next_power_of_two(capacity))
+        }
+    }
+
     pub fn reserve_exact(&mut self, capacity: uint) {
         if capacity >= self.len {
             let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
@@ -296,7 +303,7 @@ impl<T> Vec<T> {
         let len = self.len();
         assert!(index <= len);
         // space for the new element
-        self.reserve_exact(len + 1);
+        self.reserve(len + 1);
 
         unsafe { // infallible
             // The spot to put the new value