pw_vector: Add missing modifier member functions
- Implement insert and erase functions.
Bug: b/234872989
Change-Id: I8a06daee877f7661f137451bb58aee310593eadd
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/126610
Reviewed-by: Wyatt Hepler <hepler@google.com>
Commit-Queue: Viktor Elizarov <elizarovv@google.com>
diff --git a/pw_containers/public/pw_containers/vector.h b/pw_containers/public/pw_containers/vector.h
index 853e1eb..62ebc8a 100644
--- a/pw_containers/public/pw_containers/vector.h
+++ b/pw_containers/public/pw_containers/vector.h
@@ -327,26 +327,28 @@
void clear() noexcept;
- // TODO(hepler): insert, emplace, and erase are not yet implemented.
- // Currently, items can only be added to or removed from the end.
- iterator insert(const_iterator index, const T& value);
+ iterator insert(const_iterator index, size_type count, const T& value);
+
+ iterator insert(const_iterator index, const T& value) {
+ return insert(index, 1, value);
+ }
iterator insert(const_iterator index, T&& value);
- iterator insert(const_iterator index, size_type count, const T& value);
-
template <typename Iterator>
iterator insert(const_iterator index, Iterator first, Iterator last);
- iterator insert(const_iterator index, std::initializer_list<T> list);
+ iterator insert(const_iterator index, std::initializer_list<T> list) {
+ return insert(index, list.begin(), list.end());
+ }
template <typename... Args>
iterator emplace(const_iterator index, Args&&... args);
- iterator erase(const_iterator index);
-
iterator erase(const_iterator first, const_iterator last);
+ iterator erase(const_iterator index) { return erase(index, index + 1); }
+
void push_back(const T& value) { emplace_back(value); }
void push_back(T&& value) { emplace_back(std::move(value)); }
@@ -446,8 +448,10 @@
template <typename T>
void Vector<T, vector_impl::kGeneric>::clear() noexcept {
- for (auto& item : *this) {
- item.~T();
+ if constexpr (!std::is_trivially_destructible_v<value_type>) {
+ for (auto& item : *this) {
+ item.~T();
+ }
}
size_ = 0;
}
@@ -464,7 +468,9 @@
template <typename T>
void Vector<T, vector_impl::kGeneric>::pop_back() {
if (!empty()) {
- back().~T();
+ if constexpr (!std::is_trivially_destructible_v<value_type>) {
+ back().~T();
+ }
size_ -= 1;
}
}
@@ -482,6 +488,110 @@
}
template <typename T>
+typename Vector<T>::iterator Vector<T>::insert(Vector<T>::const_iterator index,
+ T&& value) {
+ PW_DASSERT(index >= cbegin());
+ PW_DASSERT(index <= cend());
+ PW_DASSERT(!full());
+
+ iterator insertion_point = begin() + std::distance(cbegin(), index);
+ if (insertion_point == end()) {
+ emplace_back(std::move(value));
+ return insertion_point;
+ }
+
+ std::move_backward(insertion_point, end(), end() + 1);
+ *insertion_point = std::move(value);
+ ++size_;
+
+ // Return an iterator pointing to the inserted value.
+ return insertion_point;
+}
+
+template <typename T>
+template <typename Iterator>
+typename Vector<T>::iterator Vector<T>::insert(Vector<T>::const_iterator index,
+ Iterator first,
+ Iterator last) {
+ PW_DASSERT(index >= cbegin());
+ PW_DASSERT(index <= cend());
+ PW_DASSERT(!full());
+
+ iterator insertion_point = begin() + std::distance(cbegin(), index);
+
+ const size_t insertion_count = std::distance(first, last);
+ if (insertion_count == 0) {
+ return insertion_point;
+ }
+ PW_DASSERT(size() + insertion_count <= max_size());
+
+ iterator return_value = insertion_point;
+
+ if (insertion_point != end()) {
+ std::move_backward(insertion_point, end(), end() + insertion_count);
+ }
+
+ while (first != last) {
+ *insertion_point = *first;
+ ++first;
+ ++insertion_point;
+ }
+ size_ += insertion_count;
+
+ // Return an iterator pointing to the first element inserted.
+ return return_value;
+}
+
+template <typename T>
+typename Vector<T>::iterator Vector<T>::insert(Vector<T>::const_iterator index,
+ size_type count,
+ const T& value) {
+ PW_DASSERT(index >= cbegin());
+ PW_DASSERT(index <= cend());
+ PW_DASSERT(size() + count <= max_size());
+
+ iterator insertion_point = begin() + std::distance(cbegin(), index);
+ if (count == size_type{}) {
+ return insertion_point;
+ }
+
+ if (insertion_point != end()) {
+ std::move_backward(insertion_point, end(), end() + count);
+ }
+
+ iterator return_value = insertion_point;
+
+ for (size_type final_count = size_ + count; size_ != final_count; ++size_) {
+ *insertion_point = value;
+ ++insertion_point;
+ }
+
+ // Return an iterator pointing to the first element inserted.
+ return return_value;
+}
+
+template <typename T>
+typename Vector<T>::iterator Vector<T>::erase(Vector<T>::const_iterator first,
+ Vector<T>::const_iterator last) {
+ iterator source = begin() + std::distance(cbegin(), last);
+ if (first == last) {
+ return source;
+ }
+
+ if constexpr (!std::is_trivially_destructible_v<T>) {
+ std::destroy(first, last);
+ }
+
+ iterator destination = begin() + std::distance(cbegin(), first);
+ iterator new_end = std::move(source, end(), destination);
+
+ size_ = std::distance(begin(), new_end);
+
+ // Return an iterator following the last removed element.
+ return new_end;
+}
+
+template <typename T>
template <typename Iterator>
void Vector<T, vector_impl::kGeneric>::CopyFrom(Iterator first, Iterator last) {
while (first != last) {
diff --git a/pw_containers/vector_test.cc b/pw_containers/vector_test.cc
index e90da6f..4bde247 100644
--- a/pw_containers/vector_test.cc
+++ b/pw_containers/vector_test.cc
@@ -76,6 +76,19 @@
moved += 1;
}
+ Counter& operator=(const Counter& other) {
+ value = other.value;
+ created += 1;
+ return *this;
+ }
+
+ Counter& operator=(Counter&& other) {
+ value = other.value;
+ other.value = 0;
+ moved += 1;
+ return *this;
+ }
+
~Counter() { destroyed += 1; }
int value;
@@ -467,6 +480,212 @@
EXPECT_EQ(vector.size(), 0u);
}
+TEST(Vector, Modify_Erase_TrivialRangeBegin) {
+ Vector<size_t, 10> vector;
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ vector.emplace_back(i);
+ }
+
+ vector.erase(vector.begin() + 2, vector.end());
+ EXPECT_EQ(vector.size(), 2u);
+
+ for (size_t i = 0; i < vector.size(); ++i) {
+ EXPECT_EQ(vector[i], i);
+ }
+}
+
+TEST(Vector, Modify_Erase_TrivialRangeEnd) {
+ Vector<size_t, 10> vector;
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ vector.emplace_back(i);
+ }
+
+ vector.erase(vector.begin(), vector.end() - 2);
+ EXPECT_EQ(vector.size(), 2u);
+
+ for (size_t i = 0; i < vector.size(); ++i) {
+ EXPECT_EQ(vector[i], 8u + i);
+ }
+}
+
+TEST(Vector, Modify_Erase_TrivialSingleItem) {
+ Vector<size_t, 10> vector;
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ vector.emplace_back(i);
+ }
+
+ vector.erase(vector.begin() + 9);
+
+ EXPECT_EQ(vector.size(), 9u);
+ EXPECT_EQ(vector.at(8), 8u);
+ EXPECT_EQ(vector.at(0), 0u);
+
+ vector.erase(vector.begin());
+ EXPECT_EQ(vector.size(), 8u);
+ EXPECT_EQ(vector.at(0), 1u);
+}
+
+TEST(Vector, Modify_Erase_NonTrivialRangeBegin) {
+ Counter::Reset();
+ Vector<Counter, 10> vector;
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ vector.emplace_back(static_cast<int>(i));
+ }
+
+ for (size_t i = 0; i < vector.size(); ++i) {
+ EXPECT_EQ(vector[i].value, static_cast<int>(i));
+ }
+
+ vector.erase(vector.begin() + 2, vector.end());
+ EXPECT_EQ(vector.size(), 2u);
+
+ for (size_t i = 0; i < vector.size(); ++i) {
+ EXPECT_EQ(vector[i].value, static_cast<int>(i));
+ }
+
+ EXPECT_EQ(Counter::destroyed, 8);
+ EXPECT_EQ(Counter::moved, 0);
+}
+
+TEST(Vector, Modify_Erase_NonTrivialRangeEnd) {
+ Counter::Reset();
+ Vector<Counter, 10> vector;
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ vector.emplace_back(static_cast<int>(i));
+ }
+
+ vector.erase(vector.begin(), vector.end() - 2);
+ EXPECT_EQ(vector.size(), 2u);
+
+ for (size_t i = 0; i < vector.size(); ++i) {
+ EXPECT_EQ(vector[i].value, static_cast<int>(8u + i));
+ }
+
+ EXPECT_EQ(Counter::destroyed, 8);
+ EXPECT_EQ(Counter::moved, 2);
+}
+
+TEST(Vector, Modify_Erase_None) {
+ Counter::Reset();
+ Vector<Counter, 10> vector;
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ vector.emplace_back(static_cast<int>(i));
+ }
+
+ vector.erase(vector.begin() + 2, vector.begin() + 2);
+ EXPECT_EQ(vector.size(), 10u);
+
+ EXPECT_EQ(Counter::destroyed, 0);
+ EXPECT_EQ(Counter::moved, 0);
+ EXPECT_EQ(Counter::created, 10);
+}
+
+TEST(Vector, Modify_Insert_End) {
+ Counter::Reset();
+ Vector<Counter, 10> vector;
+
+ for (size_t i = 0; i < 8u; ++i) {
+ vector.emplace_back(static_cast<int>(i));
+ }
+
+ EXPECT_EQ(vector.size(), 8u);
+ EXPECT_EQ(Counter::created, 8);
+
+ decltype(vector)::iterator it = vector.insert(vector.cend(), 8);
+ EXPECT_EQ(it->value, 8);
+ EXPECT_EQ(vector.at(8).value, 8);
+
+ EXPECT_EQ(Counter::destroyed, 1);
+ EXPECT_EQ(Counter::moved, 1);
+ EXPECT_EQ(Counter::created, 9);
+}
+
+TEST(Vector, Modify_Insert_Begin) {
+ Counter::Reset();
+ Vector<Counter, 10> vector;
+
+ for (size_t i = 0; i < 8u; ++i) {
+ vector.emplace_back(static_cast<int>(i));
+ }
+
+ EXPECT_EQ(vector.size(), 8u);
+
+ decltype(vector)::iterator it = vector.insert(vector.cbegin(), 123);
+ EXPECT_EQ(it->value, 123);
+ EXPECT_EQ(vector.at(0).value, 123);
+ EXPECT_EQ(vector.at(8).value, 7);
+
+ EXPECT_EQ(Counter::moved, 9);
+}
+
+TEST(Vector, Modify_Insert_CountCopies) {
+ Counter::Reset();
+ Vector<Counter, 10> vector;
+
+ vector.emplace_back(123);
+ vector.insert(vector.cbegin() + 1, 8, Counter{421});
+ EXPECT_EQ(vector.at(0).value, 123);
+ EXPECT_EQ(vector.size(), 9u);
+
+ for (size_t i = 1; i < vector.size(); ++i) {
+ EXPECT_EQ(vector[i].value, 421);
+ }
+
+ EXPECT_EQ(Counter::moved, 0);
+ EXPECT_EQ(Counter::created, 10);
+}
+
+TEST(Vector, Modify_Insert_IteratorRange) {
+ std::array array_to_insert_first{0, 1, 2, 8, 9};
+ std::array array_to_insert_middle{3, 4, 5, 6, 7};
+
+ Vector<int, 10> vector(array_to_insert_first.begin(),
+ array_to_insert_first.end());
+
+ decltype(vector)::iterator it = vector.insert(vector.cbegin() + 3,
+ array_to_insert_middle.begin(),
+ array_to_insert_middle.end());
+ EXPECT_EQ(*it, array_to_insert_middle.front());
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ EXPECT_EQ(vector[i], static_cast<int>(i));
+ }
+}
+
+TEST(Vector, Modify_Insert_InitializerListRange) {
+ std::array array_to_insert_first{0, 1, 2, 8, 9};
+ Vector<int, 10> vector(array_to_insert_first.begin(),
+ array_to_insert_first.end());
+
+ decltype(vector)::iterator it =
+ vector.insert(vector.cbegin() + 3, {3, 4, 5, 6, 7});
+ EXPECT_EQ(*it, 3);
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ EXPECT_EQ(vector[i], static_cast<int>(i));
+ }
+}
+
+TEST(Vector, Modify_Insert_NonTrivial_InitializerListRange) {
+ std::array<Counter, 5> array_to_insert_first{0, 1, 2, 8, 9};
+ Vector<Counter, 10> vector(array_to_insert_first.begin(),
+ array_to_insert_first.end());
+
+ decltype(vector)::iterator it = vector.insert(
+ vector.cbegin() + 3, std::initializer_list<Counter>{3, 4, 5, 6, 7});
+ EXPECT_EQ(it->value, 3);
+
+ for (size_t i = 0; i < vector.max_size(); ++i) {
+ EXPECT_EQ(vector[i].value, static_cast<int>(i));
+ }
+}
+
TEST(Vector, Generic) {
Vector<int, 10> vector{1, 2, 3, 4, 5};
