1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // <vector> 10 11 // iterator erase(const_iterator first, const_iterator last); 12 13 #include <vector> 14 #include <cassert> 15 #include <memory> 16 #include <string> 17 18 #include "asan_testing.h" 19 #include "common.h" 20 #include "min_allocator.h" 21 #include "MoveOnly.h" 22 #include "test_macros.h" 23 24 template <template <class> class Allocator, class T> 25 TEST_CONSTEXPR_CXX20 void tests() { 26 { 27 T arr[] = {T(1), T(2), T(3)}; 28 using Vector = std::vector<T, Allocator<T> >; 29 using Iterator = typename Vector::iterator; 30 using ConstIterator = typename Vector::const_iterator; 31 32 // Erase an empty range [first, last): last should be returned 33 { 34 { 35 Vector v; 36 Iterator i = v.erase(v.end(), v.end()); 37 assert(v.empty()); 38 assert(i == v.end()); 39 assert(is_contiguous_container_asan_correct(v)); 40 } 41 { 42 Vector v(arr, arr + 3); 43 ConstIterator first = v.cbegin(), last = v.cbegin(); 44 Iterator i = v.erase(first, last); 45 assert(v == Vector(arr, arr + 3)); 46 assert(i == last); 47 assert(is_contiguous_container_asan_correct(v)); 48 } 49 { 50 Vector v(arr, arr + 3); 51 ConstIterator first = v.cbegin() + 1, last = v.cbegin() + 1; 52 Iterator i = v.erase(first, last); 53 assert(v == Vector(arr, arr + 3)); 54 assert(i == last); 55 assert(is_contiguous_container_asan_correct(v)); 56 } 57 { 58 Vector v(arr, arr + 3); 59 ConstIterator first = v.cbegin(), last = v.cbegin(); 60 Iterator i = v.erase(first, last); 61 assert(v == Vector(arr, arr + 3)); 62 assert(i == last); 63 assert(is_contiguous_container_asan_correct(v)); 64 } 65 } 66 67 // Erase non-empty ranges 68 { 69 // Starting at begin() 70 { 71 { 72 Vector v(arr, arr + 3); 73 Iterator i = v.erase(v.cbegin(), v.cbegin() + 1); 74 assert(v == Vector(arr + 1, arr + 3)); 75 assert(i == v.begin()); 76 assert(is_contiguous_container_asan_correct(v)); 77 } 78 { 79 Vector v(arr, arr + 3); 80 Iterator i = v.erase(v.cbegin(), v.cbegin() + 2); 81 assert(v == Vector(arr + 2, arr + 3)); 82 assert(i == v.begin()); 83 assert(is_contiguous_container_asan_correct(v)); 84 } 85 { 86 Vector v(arr, arr + 3); 87 Iterator i = v.erase(v.cbegin(), v.end()); 88 assert(v.size() == 0); 89 assert(i == v.begin()); 90 assert(is_contiguous_container_asan_correct(v)); 91 } 92 } 93 { 94 Vector v(arr, arr + 3); 95 Iterator i = v.erase(v.cbegin() + 1, v.cbegin() + 2); 96 assert(v.size() == 2); 97 assert(v[0] == arr[0]); 98 assert(v[1] == arr[2]); 99 assert(i == v.begin() + 1); 100 assert(is_contiguous_container_asan_correct(v)); 101 } 102 { 103 Vector v(arr, arr + 3); 104 Iterator i = v.erase(v.cbegin() + 1, v.cend()); 105 assert(v == Vector(arr, arr + 1)); 106 assert(i == v.begin() + 1); 107 assert(is_contiguous_container_asan_correct(v)); 108 } 109 } 110 } 111 { 112 using InnerVector = std::vector<T, Allocator<T> >; 113 using Vector = std::vector<InnerVector, Allocator<InnerVector> >; 114 Vector outer(2, InnerVector(1)); 115 outer.erase(outer.begin(), outer.begin()); 116 assert(outer.size() == 2); 117 assert(outer[0].size() == 1); 118 assert(outer[1].size() == 1); 119 assert(is_contiguous_container_asan_correct(outer)); 120 assert(is_contiguous_container_asan_correct(outer[0])); 121 assert(is_contiguous_container_asan_correct(outer[1])); 122 } 123 124 // Make sure vector::erase works with move-only types 125 { 126 // When non-trivial 127 { 128 std::vector<MoveOnly, Allocator<MoveOnly> > v; 129 v.emplace_back(1); 130 v.emplace_back(2); 131 v.emplace_back(3); 132 v.erase(v.begin(), v.begin() + 2); 133 assert(v.size() == 1); 134 assert(v[0] == MoveOnly(3)); 135 } 136 // When trivial 137 { 138 std::vector<TrivialMoveOnly, Allocator<TrivialMoveOnly> > v; 139 v.emplace_back(1); 140 v.emplace_back(2); 141 v.emplace_back(3); 142 v.erase(v.begin(), v.begin() + 2); 143 assert(v.size() == 1); 144 assert(v[0] == TrivialMoveOnly(3)); 145 } 146 } 147 } 148 149 TEST_CONSTEXPR_CXX20 bool tests() { 150 tests<std::allocator, int>(); 151 tests<std::allocator, NonTriviallyRelocatable>(); 152 tests<min_allocator, int>(); 153 tests<min_allocator, NonTriviallyRelocatable>(); 154 return true; 155 } 156 157 int main(int, char**) { 158 tests(); 159 #if TEST_STD_VER >= 20 160 static_assert(tests()); 161 #endif 162 163 #ifndef TEST_HAS_NO_EXCEPTIONS 164 // Test for LWG2853: 165 // Throws: Nothing unless an exception is thrown by the assignment operator or move assignment operator of T. 166 { 167 Throws arr[] = {1, 2, 3}; 168 std::vector<Throws> v(arr, arr + 3); 169 Throws::sThrows = true; 170 v.erase(v.begin(), --v.end()); 171 assert(v.size() == 1); 172 v.erase(v.begin(), v.end()); 173 assert(v.size() == 0); 174 } 175 #endif 176 177 // Real world example with std::string, mostly intended to test trivial relocation 178 { 179 std::vector<std::string> v; 180 181 // fill the vector with half short string and half long strings 182 std::string short_string = "short"; 183 std::string long_string(256, 'x'); 184 for (int i = 0; i != 10; ++i) { 185 v.push_back(i % 2 == 0 ? short_string : long_string); 186 } 187 188 std::vector<std::string> original = v; 189 190 auto it = v.erase(v.cbegin() + 2, v.cbegin() + 8); 191 assert(v.size() == 4); 192 assert(v[0] == original[0]); 193 assert(v[1] == original[1]); 194 assert(v[2] == original[8]); 195 assert(v[3] == original[9]); 196 assert(it == v.begin() + 2); 197 } 198 199 // Make sure we satisfy the complexity requirement in terms of the number of times the assignment 200 // operator is called. 201 // 202 // There is currently ambiguity as to whether this is truly mandated by the Standard, so we only 203 // test it for libc++. 204 #ifdef _LIBCPP_VERSION 205 { 206 Tracker tracker; 207 std::vector<TrackedAssignment> v; 208 209 // Set up the vector with 5 elements. 210 for (int i = 0; i != 5; ++i) { 211 v.emplace_back(&tracker); 212 } 213 assert(tracker.copy_assignments == 0); 214 assert(tracker.move_assignments == 0); 215 216 // Erase elements [1] and [2] from it. Elements [3] [4] should be shifted, so we should 217 // see 2 move assignments (and nothing else). 218 v.erase(v.begin() + 1, v.begin() + 3); 219 assert(v.size() == 3); 220 assert(tracker.copy_assignments == 0); 221 assert(tracker.move_assignments == 2); 222 } 223 #endif 224 225 return 0; 226 } 227