Implementation of vector::erase.
Added std::copy, needed to shift the element down during an erase call.
Squashed commit of the following:
commit e534509bd709350e585f722e525eb2b63ade5831
Author: Nicolas Catania <niko@google.com>
Date: Mon Feb 1 10:38:21 2010 -0800
implementation of std::copy
commit f94dad514c54c66da85d9492452610285b5ee446
Author: Nicolas Catania <niko@google.com>
Date: Sun Jan 31 14:58:15 2010 -0800
Added support for erase.
Erase element and erase range of elements.
diff --git a/include/algorithm b/include/algorithm
index e1930a1..bfa1c0d 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -32,6 +32,7 @@
#include <cstddef>
#include <cstring>
+#include <iterator>
#include <type_traits.h>
#ifndef ANDROID_ASTL_TYPE_TRAITS_H__
#error "Wrong file included!"
@@ -45,6 +46,7 @@
// - swap
// - fill
// - fill_n
+// - copy
// - equal
template<typename _T> inline const _T& min(const _T& left, const _T& right)
@@ -66,6 +68,63 @@
right = tmp;
}
+
+// Basic iterators, loop over the elements, we don't know how many
+// elements we need to copy. See the random access specialization
+// below.
+template<typename _Category>
+struct copy_move {
+ template<typename _InputIterator, typename _OutputIterator>
+ static _OutputIterator
+ __copy_move(_InputIterator first, _InputIterator last, _OutputIterator res) {
+ for (; first != last; ++res, ++first) {
+ *res = *first;
+ }
+ return res;
+ }
+};
+
+// For random access iterators, we know how many elements we have to
+// copy (random iterators support operator-).
+template<>
+struct copy_move<random_access_iterator_tag> {
+ template<typename _InputIterator, typename _OutputIterator>
+ static _OutputIterator
+ __copy_move(_InputIterator first, _InputIterator last, _OutputIterator res) {
+ typedef typename iterator_traits<_InputIterator>::difference_type
+ difference_type;
+
+ for (difference_type n = last - first; n > 0; --n) {
+ *res = *first;
+ ++first;
+ ++res;
+ }
+ return res;
+ }
+};
+
+// TODO: for simple case and wrapper iterator, should degrade to memmove.
+
+// copy elements in the range [first, last) into the range [result,
+// result + (last - first)) starting from first and proceeding to
+// last.
+//
+// For each non negative n < (last - first) performs:
+// *(result + n) = *(first + n)
+// @require result should not be in the [first, last) range.
+// @return result + (last - first)
+template<typename _InputIterator, typename _OutputIterator>
+inline _OutputIterator
+copy(_InputIterator first, _InputIterator last, _OutputIterator res) {
+ typedef typename iterator_traits<_InputIterator>::iterator_category
+ _Category;
+
+ return copy_move<_Category>::__copy_move(
+ android::iter<_InputIterator>::base(first),
+ android::iter<_InputIterator>::base(last),
+ res);
+}
+
// fill the range [begin, end) with copies of value, return nothing.
// fill_n the range [begin, begin + n) with copies of value, return
// the pointer at begin + n.
@@ -73,7 +132,6 @@
// TODO: fill and fill_n should take forward and output iterators for
// begin and end params. Fix this when iterator are defined.
-
template<bool> struct __fill
{
template<typename _T> static void fill(_T *begin, const _T *end,
@@ -236,5 +294,4 @@
} // namespace std
-
#endif
diff --git a/include/iterator b/include/iterator
index 23d409f..2f02ae1 100644
--- a/include/iterator
+++ b/include/iterator
@@ -31,6 +31,7 @@
#define ANDROID_ASTL_ITERATOR__
#include <cstddef>
+#include <type_traits.h>
// Iterators are a generalization of pointers to allow programs to
// work with different data structures (containers) in a uniform
@@ -92,10 +93,12 @@
// Wrap an interator that is not a class (e.g pointer) into an
// iterator that is a class.
+// TODO: move this definition in the android ns.
template<typename _Iterator, typename _Container>
class __wrapper_iterator
{
public:
+ typedef _Iterator iterator_type;
typedef typename iterator_traits<_Iterator>::iterator_category
iterator_category;
typedef typename iterator_traits<_Iterator>::value_type value_type;
@@ -213,6 +216,32 @@
iterator_category(const _Iterator&)
{ return typename std::iterator_traits<_Iterator>::iterator_category(); }
+// Detect wrapper iterators.
+template<typename _T>
+struct is_wrapper_iterator: public std::false_type { };
+
+template<typename _Iterator, typename _Container>
+struct is_wrapper_iterator<std::__wrapper_iterator<_Iterator, _Container> >:
+ public std::true_type { };
+
+// iter::base
+//
+// For wrapper iterators, android::iter::base(it) returns a pointer
+// (it.base()) which is going to match implementation(s) that use
+// pointers (e.g memmove).
+template<typename _Iterator,
+ bool _IsWrapper = is_wrapper_iterator<_Iterator>::value>
+struct iter {
+ static _Iterator base(_Iterator it) { return it; }
+};
+
+template<typename _Iterator>
+struct iter<_Iterator, true> {
+ static typename _Iterator::iterator_type base(_Iterator it) {
+ return it.base();
+ }
+};
+
} // namespace android
namespace std {
diff --git a/include/vector b/include/vector
index bc9bbdd..051da1d 100644
--- a/include/vector
+++ b/include/vector
@@ -147,6 +147,18 @@
// the internal buffer: you need to call reserve() to recover it.
void pop_back();
+ // Remove the element pointed by the iterator.
+ // Expensive since the remaining elts must be shifted around.
+ // @param pos Iterator pointing to the elt to be removed.
+ // @return An iterator pointing to the next elt or end().
+ iterator erase(iterator pos);
+
+ // Remove a range of elements [first, last)
+ // @param first Iterator pointing to the first element to be removed.
+ // @param last Iterator pointing to one past the last element to be removed.
+ // @return An iterator pointing to the elt next to 'last' or end().
+ iterator erase(iterator first, iterator last);
+
// Empty the vector on return. Release the internal buffer. Length
// and capacity are both 0 on return. If you want to keep the
// internal buffer around for reuse, call 'resize'/'erase' instead.
@@ -328,6 +340,37 @@
}
template<typename _T>
+typename vector<_T>::iterator
+vector<_T>::erase(iterator pos) {
+ if (mLength) {
+ std::copy(pos + 1, end(), pos);
+ --mLength;
+ if (!is_pod<value_type>::value) {
+ end()->~_T();
+ }
+ }
+ return pos;
+}
+
+template<typename _T>
+typename vector<_T>::iterator
+vector<_T>::erase(iterator first, iterator last) {
+ difference_type len = std::distance(first, last);
+ if (len > 0) {
+ last = std::copy(last, end(), first);
+
+ if (!is_pod<value_type>::value) {
+ while (last != end()) {
+ last->~_T();
+ ++last;
+ }
+ }
+ mLength -= len;
+ }
+ return first;
+}
+
+template<typename _T>
void vector<_T>::clear()
{
if(mBegin)
diff --git a/tests/test_algorithm.cpp b/tests/test_algorithm.cpp
index e00bb67..8fd554d 100644
--- a/tests/test_algorithm.cpp
+++ b/tests/test_algorithm.cpp
@@ -134,6 +134,21 @@
return true;
}
+bool testCopy()
+{
+ {
+ int data[] = {1,2,3,4,5,6};
+ std::copy(data + 2, data + 5, data);
+ EXPECT_TRUE(data[0] == 3);
+ EXPECT_TRUE(data[1] == 4);
+ EXPECT_TRUE(data[2] == 5);
+ EXPECT_TRUE(data[3] == 4);
+ EXPECT_TRUE(data[4] == 5);
+ EXPECT_TRUE(data[5] == 6);
+ }
+ return true;
+}
+
} // namespace android
int main(int argc, char **argv)
@@ -144,5 +159,6 @@
FAIL_UNLESS(testFill);
FAIL_UNLESS(testFill_N);
FAIL_UNLESS(testEqual);
+ FAIL_UNLESS(testCopy);
return kPassed;
}
diff --git a/tests/test_iterator.cpp b/tests/test_iterator.cpp
index ed6e327..cc9c510 100644
--- a/tests/test_iterator.cpp
+++ b/tests/test_iterator.cpp
@@ -109,10 +109,21 @@
return true;
}
+typedef std::__wrapper_iterator<int *, int *> WrapperIterator;
+
+// Check we can distinguish wrapper iterators.
+bool testWrapperIterator()
+{
+ EXPECT_FALSE(android::is_wrapper_iterator<android::Random>::value);
+ EXPECT_TRUE(android::is_wrapper_iterator<android::WrapperIterator>::value);
+ return true;
+}
+
} // namespace android
int main(int argc, char **argv)
{
FAIL_UNLESS(testCategory);
+ FAIL_UNLESS(testWrapperIterator);
return kPassed;
}
diff --git a/tests/test_string.cpp b/tests/test_string.cpp
index 337d879..d06f88e 100644
--- a/tests/test_string.cpp
+++ b/tests/test_string.cpp
@@ -33,6 +33,7 @@
#endif
#include <climits>
#include <cstring>
+#include <algorithm>
#include "common.h"
@@ -615,6 +616,19 @@
return true;
}
+bool testCopy()
+{
+ string data[] = {"one", "two", "three", "four", "five", "six"};
+ std::copy(data + 2, data + 5, data);
+ EXPECT_TRUE(data[0] == "three");
+ EXPECT_TRUE(data[1] == "four");
+ EXPECT_TRUE(data[2] == "five");
+ EXPECT_TRUE(data[3] == "four");
+ EXPECT_TRUE(data[4] == "five");
+ EXPECT_TRUE(data[5] == "six");
+ return true;
+}
+
bool testConcat()
{
@@ -915,6 +929,7 @@
FAIL_UNLESS(testAppendOperator);
FAIL_UNLESS(testConcat);
FAIL_UNLESS(testAssignment);
+ FAIL_UNLESS(testCopy);
FAIL_UNLESS(testReserve);
FAIL_UNLESS(testCompare);
FAIL_UNLESS(testAccessor);
diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp
index 88dd466..6279e97 100644
--- a/tests/test_vector.cpp
+++ b/tests/test_vector.cpp
@@ -88,6 +88,7 @@
A() {mChunk = new T[2046];}
A(const A<T>& a) {mChunk = new T[2046];}
virtual ~A() {delete [] mChunk;}
+ A& operator=(const A& o) { return *this;}
T *mChunk;
};
@@ -96,6 +97,7 @@
B() {mChunk = new char[2046];}
B(const B& b) {mChunk = new char[2046];}
virtual ~B() {delete [] mChunk;}
+ B& operator=(const B& o) { return *this;}
char *mChunk;
};
@@ -512,6 +514,151 @@
EXPECT_TRUE(CtorDtorCounter::mDtorCount == 201);
return true;
}
+
+bool testEraseElt()
+{
+ {
+ vector<B> empty;
+ vector<B>::iterator res = empty.erase(empty.end());
+ EXPECT_TRUE(res == empty.end());
+ EXPECT_TRUE(empty.empty());
+ }
+ {
+ vector<B> one;
+ one.push_back(B());
+ EXPECT_TRUE(!one.empty());
+
+ vector<B>::iterator res = one.erase(one.begin());
+ EXPECT_TRUE(res == one.end());
+
+ EXPECT_TRUE(one.begin() == one.end());
+ EXPECT_TRUE(one.empty());
+ }
+ {
+ vector<B> two;
+ two.push_back(B());
+ two.push_back(B());
+
+ vector<B>::iterator res = two.erase(two.begin());
+
+ EXPECT_TRUE(res == two.begin());
+ EXPECT_TRUE(res != two.end());
+
+ EXPECT_TRUE(two.begin() != two.end());
+ EXPECT_TRUE(two.size() == 1);
+ }
+ {
+ vector<int> vec;
+ for (int i = 0; i < 20; ++i) vec.push_back(i);
+ vector<int>::iterator pos;
+
+ pos = vec.erase(vec.begin() + 2); // removes '2'
+ EXPECT_TRUE(*pos == 3); // returns '3'
+
+ pos = vec.erase(vec.begin() + 18); // removes '19' now @ pos 18
+ EXPECT_TRUE(pos == vec.end()); // returns end()
+ EXPECT_TRUE(*(--pos) == 18); // last one is now '18'
+ }
+ {
+ vector<std::string> vec;
+
+ vec.push_back("first");
+ vec.push_back("second");
+ vec.push_back("third");
+ vec.push_back("fourth");
+
+ vector<std::string>::iterator pos;
+ pos = vec.erase(vec.begin() + 1); // removes 'second'
+ EXPECT_TRUE(vec.size() == 3);
+ EXPECT_TRUE(*pos == "third");
+ EXPECT_TRUE(vec[0] == "first");
+ EXPECT_TRUE(vec[1] == "third");
+ EXPECT_TRUE(vec[2] == "fourth");
+ }
+ return true;
+}
+
+bool testEraseRange()
+{
+ {
+ vector<B> empty;
+ vector<B>::iterator res = empty.erase(empty.begin(), empty.end());
+ EXPECT_TRUE(res == empty.end());
+ EXPECT_TRUE(empty.empty());
+ EXPECT_TRUE(empty.size() == 0);
+ }
+ {
+ vector<B> one;
+ one.push_back(B());
+ EXPECT_TRUE(!one.empty());
+
+ vector<B>::iterator res = one.erase(one.begin(), one.end());
+ EXPECT_TRUE(res == one.end());
+
+ EXPECT_TRUE(one.begin() == one.end());
+ EXPECT_TRUE(one.empty());
+ }
+ {
+ vector<B> two;
+ two.push_back(B());
+ two.push_back(B());
+
+ // erase the 1st one.
+ vector<B>::iterator res = two.erase(two.begin(), two.begin() + 1);
+
+ EXPECT_TRUE(res == two.begin());
+ EXPECT_TRUE(res != two.end());
+
+ EXPECT_TRUE(two.begin() != two.end());
+ EXPECT_TRUE(two.size() == 1);
+ }
+ {
+ vector<B> two;
+ two.push_back(B());
+ two.push_back(B());
+
+ // erase range is empty.
+ vector<B>::iterator res = two.erase(two.begin(), two.begin());
+
+ EXPECT_TRUE(res == two.begin());
+ EXPECT_TRUE(res != two.end());
+
+ EXPECT_TRUE(two.begin() != two.end());
+ EXPECT_TRUE(two.size() == 2);
+ }
+
+ {
+ vector<int> vec;
+ for (int i = 0; i < 20; ++i) vec.push_back(i);
+ vector<int>::iterator pos;
+
+ pos = vec.erase(vec.begin() + 2, vec.begin() + 3); // removes '2'
+ EXPECT_TRUE(*pos == 3); // returns '3'
+
+ pos = vec.erase(vec.begin() + 18, vec.end()); // removes '19' now @ pos 18
+ EXPECT_TRUE(pos == vec.end()); // returns end()
+ EXPECT_TRUE(*(--pos) == 18); // last one is now '18'
+ }
+ {
+ vector<std::string> vec;
+
+ vec.push_back("first");
+ vec.push_back("second");
+ vec.push_back("third");
+ vec.push_back("fourth");
+
+ vector<std::string>::iterator pos;
+ pos = vec.erase(vec.begin() + 1, vec.begin() + 3); // removes 'second' and third.
+ EXPECT_TRUE(vec.size() == 2);
+ EXPECT_TRUE(*pos == "fourth");
+ EXPECT_TRUE(vec[0] == "first");
+ EXPECT_TRUE(vec[1] == "fourth");
+ pos = vec.erase(vec.begin(), vec.end()); // clears the vector
+ EXPECT_TRUE(vec.empty());
+ }
+ return true;
+}
+
} // namespace android
int main(int argc, char **argv)
@@ -519,17 +666,16 @@
FAIL_UNLESS(testConstructorInt);
FAIL_UNLESS(testConstructorString);
FAIL_UNLESS(testConstructorClass);
-
FAIL_UNLESS(testConstructorRepeat);
FAIL_UNLESS(testConstructorIterator);
FAIL_UNLESS(testReserve);
FAIL_UNLESS(testPushBack);
FAIL_UNLESS(testPopBack);
FAIL_UNLESS(testResize);
-#if(0)
FAIL_UNLESS(testSwap);
FAIL_UNLESS(testIterators);
FAIL_UNLESS(testCtorDtorForNonPod);
-#endif
+ FAIL_UNLESS(testEraseElt);
+ FAIL_UNLESS(testEraseRange);
return kPassed;
}
