Added iterator based vector constructor.

The new range based constructors degrades to one reserve
 and one memmove call for pod types referenced using random
access iterators.

There is an extra step to disambiguate between range and repeat
initializers. Basically for some type combination, the range
form can be called when the repeat form was the one targetted.
We check if the type is an integer to find out which one was called.

2 files changed, 128 insertions, 0 deletions

diff --git a/include/vector b/include/vector
index a068bc3..d9e4642 100644
--- a/include/vector
+++ b/include/vector
@@ -81,6 +81,22 @@ class vector
     // @param init_value The element to copy.
     explicit vector(const size_type num, const value_type& init_value = value_type());
 
+    // Create a vector by copying the elements from [first, last).
+    //
+    // If the iterators are random-access, the constructor will be
+    // able to reserve the memory in a single call before copying the
+    // elements. If the elements are POD, the constructor uses memmove.
+    template<typename _Iterator>
+    vector(_Iterator first, _Iterator last) {
+        // Because of template matching, vector<int>(int n, int val)
+        // will now match this constructor (int != size_type) instead
+        // of the repeat one above. In this case, the _Iterator
+        // template parameter is an integral type and not an iterator,
+        // we use that to call the correct initialize impl.
+        typedef typename is_integral<_Iterator>::type integral;
+        initialize(first, last, integral());
+    }
+
     ~vector() { clear(); }
 
     // @return true if the vector is empty, false otherwise.
@@ -137,6 +153,39 @@ class vector
 
     void swap(vector& other);
   private:
+    // See the 2 'initialize' methods first. They desambiguate between
+    // repeat and range initialize. For range initialize, there is
+    // another desambiguation based on the nature of the iterators.
+
+    // Repeat constructor implementation.
+    void repeat_initialize(const size_type num,
+                           const value_type& init_value);
+
+    // Initialize from a random access iterator.
+    template<typename _Iterator>
+    void range_initialize(_Iterator first, _Iterator last,
+                          random_access_iterator_tag);
+
+    // Initialize from an input iterator.
+    template<typename _InputIterator>
+    void range_initialize(_InputIterator first, _InputIterator last,
+                          input_iterator_tag);
+
+    // Repeat constructor that matched the templatized constructor for iterator.
+    // The last parameter true_type is used by the caller to target this method.
+    template<typename _Integral>
+    void initialize(_Integral num, _Integral init_value, true_type) {
+        repeat_initialize((size_type)num, init_value);
+    }
+
+    // Not a repeat constructor (last param type is false_type). first
+    // and last are really iterators. Dispatch the call depending on
+    // the iterators' category.
+    template<typename _InputIterator>
+    void initialize(_InputIterator first, _InputIterator last, false_type) {
+        range_initialize(first, last, android::iterator_category(first));
+    }
+
     // @return New internal buffer size when it is adjusted automatically.
     size_type grow() const;
 
@@ -171,6 +220,13 @@ vector<_T>::vector()
 template<typename _T>
 vector<_T>::vector(const size_type num, const value_type& init_value)
 {
+    repeat_initialize(num, init_value);
+}
+
+template<typename _T>
+void vector<_T>::repeat_initialize(const size_type num,
+                                   const value_type& init_value)
+{
     if (num < max_size())
     {
         mBegin = static_cast<pointer>(malloc(num * sizeof(value_type)));
@@ -289,6 +345,39 @@ void vector<_T>::swap(vector& other)
     std::swap(mLength, other.mLength);
 }
 
+template<typename _T>
+template<typename _InputIterator>
+void vector<_T>::range_initialize(_InputIterator first, _InputIterator last,
+                                  input_iterator_tag) {
+    // There is no way to know how many elements we are going to
+    // insert, call push_back which will alloc/realloc as needed.
+    mBegin = NULL;
+    mLength = mCapacity =  0;
+    for (; first != last; ++first) {
+        push_back(*first);
+    }
+}
+
+template<typename _T>
+template<typename _Iterator>
+void vector<_T>::range_initialize(_Iterator first, _Iterator last,
+                                  random_access_iterator_tag) {
+    typedef typename iterator_traits<_Iterator>::difference_type difference_type;
+    const difference_type num = std::distance(first, last);
+
+    if (0 <= num && static_cast<size_type>(num) < max_size()) {
+        mBegin = static_cast<pointer>(malloc(num * sizeof(value_type)));
+        if (mBegin) {
+            mLength = mCapacity =  num;
+            std::uninitialized_copy(first, last, iterator(mBegin));
+            return;
+        }
+    }
+    mBegin = NULL;
+    mLength = mCapacity =  0;
+}
+
+
 // Grow the capacity. Use exponential until kExponentialLimit then
 // linear until it reaches max_size().
 template<typename _T>
diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp
index 122557b..304b114 100644
--- a/tests/test_vector.cpp
+++ b/tests/test_vector.cpp
@@ -122,6 +122,44 @@ bool testConstructorRepeat()
     return true;
 }
 
+bool testConstructorIterator()
+{
+    {
+        vector<string> src;
+        EXPECT_TRUE(src.empty());
+        vector<string> dst(src.begin(), src.end());
+        EXPECT_TRUE(dst.empty());
+    }
+    {
+        vector<int> src;
+        EXPECT_TRUE(src.empty());
+        vector<int> dst(src.begin(), src.end());
+        EXPECT_TRUE(dst.empty());
+    }
+    {
+        vector<int> src;
+        src.push_back(10);
+        src.push_back(20);
+        src.push_back(30);
+        vector<int> dst(src.begin(), src.end());
+        EXPECT_TRUE(dst.size() == 3);
+        EXPECT_TRUE(dst[0] == 10);
+        EXPECT_TRUE(dst[1] == 20);
+        EXPECT_TRUE(dst[2] == 30);
+    }
+    {
+        vector<string> src;
+        src.push_back("str1");
+        src.push_back("str2");
+        src.push_back("str3");
+        vector<string> dst(src.begin(), src.end());
+        EXPECT_TRUE(dst.size() == 3);
+        EXPECT_TRUE(dst[0] == "str1");
+        EXPECT_TRUE(dst[1] == "str2");
+        EXPECT_TRUE(dst[2] == "str3");
+    }
+    return true;
+}
 
 bool testReserve()
 {
@@ -390,6 +428,7 @@ int main(int argc, char **argv)
     FAIL_UNLESS(testConstructorInt);
     FAIL_UNLESS(testConstructorString);
     FAIL_UNLESS(testConstructorRepeat);
+    FAIL_UNLESS(testConstructorIterator);
     FAIL_UNLESS(testReserve);
     FAIL_UNLESS(testPushBack);
     FAIL_UNLESS(testPopBack);