From 9bf9b2a29e7da59f45b86a800665ad72dafe3f72 Mon Sep 17 00:00:00 2001 From: Nicolas Catania Date: Sun, 24 Jan 2010 15:01:04 -0800 Subject: 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. --- include/vector | 89 +++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test_vector.cpp | 39 ++++++++++++++++++++++ 2 files changed, 128 insertions(+) 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 + vector(_Iterator first, _Iterator last) { + // Because of template matching, vector(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 + void range_initialize(_Iterator first, _Iterator last, + random_access_iterator_tag); + + // Initialize from an input iterator. + template + 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 + 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 + 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; @@ -170,6 +219,13 @@ vector<_T>::vector() template vector<_T>::vector(const size_type num, const value_type& init_value) +{ + repeat_initialize(num, init_value); +} + +template +void vector<_T>::repeat_initialize(const size_type num, + const value_type& init_value) { if (num < max_size()) { @@ -289,6 +345,39 @@ void vector<_T>::swap(vector& other) std::swap(mLength, other.mLength); } +template +template +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 +template +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(num) < max_size()) { + mBegin = static_cast(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 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 src; + EXPECT_TRUE(src.empty()); + vector dst(src.begin(), src.end()); + EXPECT_TRUE(dst.empty()); + } + { + vector src; + EXPECT_TRUE(src.empty()); + vector dst(src.begin(), src.end()); + EXPECT_TRUE(dst.empty()); + } + { + vector src; + src.push_back(10); + src.push_back(20); + src.push_back(30); + vector 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 src; + src.push_back("str1"); + src.push_back("str2"); + src.push_back("str3"); + vector 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); -- cgit v1.2.3