merge.pass.cpp (14520B)
1 //===----------------------------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // REQUIRES: long_tests 11 12 // <algorithm> 13 14 // template<InputIterator InIter1, InputIterator InIter2, typename OutIter> 15 // requires OutputIterator<OutIter, InIter1::reference> 16 // && OutputIterator<OutIter, InIter2::reference> 17 // && HasLess<InIter2::value_type, InIter1::value_type> 18 // constexpr OutIter // constexpr after C++17 19 // merge(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); 20 21 #include <algorithm> 22 #include <random> 23 #include <cassert> 24 25 #include "test_macros.h" 26 #include "test_iterators.h" 27 28 29 // #if TEST_STD_VER > 17 30 // TEST_CONSTEXPR bool test_constexpr() { 31 // int ia[] = {0, 1, 2, 3, 4}; 32 // int ib[] = {2, 4, 6, 8}; 33 // int ic[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 34 // const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8}; 35 // 36 // auto it = std::merge(std::begin(ia), std::end(ia), std::begin(ib), std::end(ib), std::begin(ic)); 37 // return std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib)) 38 // && *it == 0 39 // && std::equal(std::begin(ic), it, std::begin(expected), std::end(expected)) 40 // ; 41 // } 42 // #endif 43 44 std::mt19937 randomness; 45 46 template <class InIter1, class InIter2, class OutIter> 47 void 48 test() 49 { 50 { 51 unsigned N = 100000; 52 int* ia = new int[N]; 53 int* ib = new int[N]; 54 int* ic = new int[2*N]; 55 for (unsigned i = 0; i < N; ++i) 56 ia[i] = 2*i; 57 for (unsigned i = 0; i < N; ++i) 58 ib[i] = 2*i+1; 59 OutIter r = std::merge(InIter1(ia), InIter1(ia+N), 60 InIter2(ib), InIter2(ib+N), OutIter(ic)); 61 assert(base(r) == ic+2*N); 62 assert(ic[0] == 0); 63 assert(ic[2*N-1] == static_cast<int>(2*N-1)); 64 assert(std::is_sorted(ic, ic+2*N)); 65 delete [] ic; 66 delete [] ib; 67 delete [] ia; 68 } 69 { 70 unsigned N = 100; 71 int* ia = new int[N]; 72 int* ib = new int[N]; 73 int* ic = new int[2*N]; 74 for (unsigned i = 0; i < 2*N; ++i) 75 ic[i] = i; 76 std::shuffle(ic, ic+2*N, randomness); 77 std::copy(ic, ic+N, ia); 78 std::copy(ic+N, ic+2*N, ib); 79 std::sort(ia, ia+N); 80 std::sort(ib, ib+N); 81 OutIter r = std::merge(InIter1(ia), InIter1(ia+N), 82 InIter2(ib), InIter2(ib+N), OutIter(ic)); 83 assert(base(r) == ic+2*N); 84 assert(ic[0] == 0); 85 assert(ic[2*N-1] == static_cast<int>(2*N-1)); 86 assert(std::is_sorted(ic, ic+2*N)); 87 delete [] ic; 88 delete [] ib; 89 delete [] ia; 90 } 91 } 92 93 int main() 94 { 95 test<input_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 96 test<input_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >(); 97 test<input_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 98 test<input_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 99 test<input_iterator<const int*>, input_iterator<const int*>, int*>(); 100 101 test<input_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 102 test<input_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 103 test<input_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 104 test<input_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 105 test<input_iterator<const int*>, forward_iterator<const int*>, int*>(); 106 107 test<input_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 108 test<input_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 109 test<input_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 110 test<input_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 111 test<input_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 112 113 test<input_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 114 test<input_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 115 test<input_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 116 test<input_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 117 test<input_iterator<const int*>, random_access_iterator<const int*>, int*>(); 118 119 test<input_iterator<const int*>, const int*, output_iterator<int*> >(); 120 test<input_iterator<const int*>, const int*, forward_iterator<int*> >(); 121 test<input_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 122 test<input_iterator<const int*>, const int*, random_access_iterator<int*> >(); 123 test<input_iterator<const int*>, const int*, int*>(); 124 125 test<forward_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 126 test<forward_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >(); 127 test<forward_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 128 test<forward_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 129 test<forward_iterator<const int*>, input_iterator<const int*>, int*>(); 130 131 test<forward_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 132 test<forward_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 133 test<forward_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 134 test<forward_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 135 test<forward_iterator<const int*>, forward_iterator<const int*>, int*>(); 136 137 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 138 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 139 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 140 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 141 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 142 143 test<forward_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 144 test<forward_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 145 test<forward_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 146 test<forward_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 147 test<forward_iterator<const int*>, random_access_iterator<const int*>, int*>(); 148 149 test<forward_iterator<const int*>, const int*, output_iterator<int*> >(); 150 test<forward_iterator<const int*>, const int*, forward_iterator<int*> >(); 151 test<forward_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 152 test<forward_iterator<const int*>, const int*, random_access_iterator<int*> >(); 153 test<forward_iterator<const int*>, const int*, int*>(); 154 155 test<bidirectional_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 156 test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 157 test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 158 test<bidirectional_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 159 test<bidirectional_iterator<const int*>, input_iterator<const int*>, int*>(); 160 161 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 162 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 163 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 164 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 165 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, int*>(); 166 167 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 168 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 169 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 170 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 171 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 172 173 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 174 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 175 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 176 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 177 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, int*>(); 178 179 test<bidirectional_iterator<const int*>, const int*, output_iterator<int*> >(); 180 test<bidirectional_iterator<const int*>, const int*, forward_iterator<int*> >(); 181 test<bidirectional_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 182 test<bidirectional_iterator<const int*>, const int*, random_access_iterator<int*> >(); 183 test<bidirectional_iterator<const int*>, const int*, int*>(); 184 185 test<random_access_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 186 test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 187 test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 188 test<random_access_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 189 test<random_access_iterator<const int*>, input_iterator<const int*>, int*>(); 190 191 test<random_access_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 192 test<random_access_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 193 test<random_access_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 194 test<random_access_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 195 test<random_access_iterator<const int*>, forward_iterator<const int*>, int*>(); 196 197 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 198 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 199 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 200 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 201 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 202 203 test<random_access_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 204 test<random_access_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 205 test<random_access_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 206 test<random_access_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 207 test<random_access_iterator<const int*>, random_access_iterator<const int*>, int*>(); 208 209 test<random_access_iterator<const int*>, const int*, output_iterator<int*> >(); 210 test<random_access_iterator<const int*>, const int*, forward_iterator<int*> >(); 211 test<random_access_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 212 test<random_access_iterator<const int*>, const int*, random_access_iterator<int*> >(); 213 test<random_access_iterator<const int*>, const int*, int*>(); 214 215 test<const int*, input_iterator<const int*>, output_iterator<int*> >(); 216 test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >(); 217 test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >(); 218 test<const int*, input_iterator<const int*>, random_access_iterator<int*> >(); 219 test<const int*, input_iterator<const int*>, int*>(); 220 221 test<const int*, forward_iterator<const int*>, output_iterator<int*> >(); 222 test<const int*, forward_iterator<const int*>, forward_iterator<int*> >(); 223 test<const int*, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 224 test<const int*, forward_iterator<const int*>, random_access_iterator<int*> >(); 225 test<const int*, forward_iterator<const int*>, int*>(); 226 227 test<const int*, bidirectional_iterator<const int*>, output_iterator<int*> >(); 228 test<const int*, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 229 test<const int*, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 230 test<const int*, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 231 test<const int*, bidirectional_iterator<const int*>, int*>(); 232 233 test<const int*, random_access_iterator<const int*>, output_iterator<int*> >(); 234 test<const int*, random_access_iterator<const int*>, forward_iterator<int*> >(); 235 test<const int*, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 236 test<const int*, random_access_iterator<const int*>, random_access_iterator<int*> >(); 237 test<const int*, random_access_iterator<const int*>, int*>(); 238 239 test<const int*, const int*, output_iterator<int*> >(); 240 test<const int*, const int*, forward_iterator<int*> >(); 241 test<const int*, const int*, bidirectional_iterator<int*> >(); 242 test<const int*, const int*, random_access_iterator<int*> >(); 243 test<const int*, const int*, int*>(); 244 245 #if TEST_STD_VER > 17 246 // Not yet - waiting on std::copy 247 // static_assert(test_constexpr()); 248 #endif 249 }