341 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>12// requires ShuffleIterator<Iter>13// && CopyConstructible<Pred>14// constexpr Iter // constexpr since C++2615// stable_partition(Iter first, Iter last, Pred pred);16 17#include <algorithm>18#include <cassert>19#include <memory>20#include <vector>21 22#include "count_new.h"23#include "test_iterators.h"24#include "test_macros.h"25 26struct is_odd {27 TEST_CONSTEXPR_CXX26 bool operator()(const int& i) const { return i & 1; }28};29 30struct odd_first {31 TEST_CONSTEXPR_CXX26 bool operator()(const std::pair<int, int>& p) const { return p.first & 1; }32};33 34template <class Iter>35TEST_CONSTEXPR_CXX26 void test() {36 { // check mixed37 typedef std::pair<int,int> P;38 P array[] =39 {40 P(0, 1),41 P(0, 2),42 P(1, 1),43 P(1, 2),44 P(2, 1),45 P(2, 2),46 P(3, 1),47 P(3, 2),48 P(4, 1),49 P(4, 2)50 };51 const unsigned size = sizeof(array)/sizeof(array[0]);52 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());53 assert(base(r) == array + 4);54 assert(array[0] == P(1, 1));55 assert(array[1] == P(1, 2));56 assert(array[2] == P(3, 1));57 assert(array[3] == P(3, 2));58 assert(array[4] == P(0, 1));59 assert(array[5] == P(0, 2));60 assert(array[6] == P(2, 1));61 assert(array[7] == P(2, 2));62 assert(array[8] == P(4, 1));63 assert(array[9] == P(4, 2));64 }65 {66 typedef std::pair<int,int> P;67 P array[] =68 {69 P(0, 1),70 P(0, 2),71 P(1, 1),72 P(1, 2),73 P(2, 1),74 P(2, 2),75 P(3, 1),76 P(3, 2),77 P(4, 1),78 P(4, 2)79 };80 const unsigned size = sizeof(array)/sizeof(array[0]);81 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());82 assert(base(r) == array + 4);83 assert(array[0] == P(1, 1));84 assert(array[1] == P(1, 2));85 assert(array[2] == P(3, 1));86 assert(array[3] == P(3, 2));87 assert(array[4] == P(0, 1));88 assert(array[5] == P(0, 2));89 assert(array[6] == P(2, 1));90 assert(array[7] == P(2, 2));91 assert(array[8] == P(4, 1));92 assert(array[9] == P(4, 2));93 // check empty94 r = std::stable_partition(Iter(array), Iter(array), odd_first());95 assert(base(r) == array);96 // check one true97 r = std::stable_partition(Iter(array), Iter(array+1), odd_first());98 assert(base(r) == array+1);99 assert(array[0] == P(1, 1));100 // check one false101 r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first());102 assert(base(r) == array+4);103 assert(array[4] == P(0, 1));104 }105 { // check all false106 typedef std::pair<int,int> P;107 P array[] =108 {109 P(0, 1),110 P(0, 2),111 P(2, 1),112 P(2, 2),113 P(4, 1),114 P(4, 2),115 P(6, 1),116 P(6, 2),117 P(8, 1),118 P(8, 2)119 };120 const unsigned size = sizeof(array)/sizeof(array[0]);121 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());122 assert(base(r) == array);123 assert(array[0] == P(0, 1));124 assert(array[1] == P(0, 2));125 assert(array[2] == P(2, 1));126 assert(array[3] == P(2, 2));127 assert(array[4] == P(4, 1));128 assert(array[5] == P(4, 2));129 assert(array[6] == P(6, 1));130 assert(array[7] == P(6, 2));131 assert(array[8] == P(8, 1));132 assert(array[9] == P(8, 2));133 }134 { // check all true135 typedef std::pair<int,int> P;136 P array[] =137 {138 P(1, 1),139 P(1, 2),140 P(3, 1),141 P(3, 2),142 P(5, 1),143 P(5, 2),144 P(7, 1),145 P(7, 2),146 P(9, 1),147 P(9, 2)148 };149 const unsigned size = sizeof(array)/sizeof(array[0]);150 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());151 assert(base(r) == array + size);152 assert(array[0] == P(1, 1));153 assert(array[1] == P(1, 2));154 assert(array[2] == P(3, 1));155 assert(array[3] == P(3, 2));156 assert(array[4] == P(5, 1));157 assert(array[5] == P(5, 2));158 assert(array[6] == P(7, 1));159 assert(array[7] == P(7, 2));160 assert(array[8] == P(9, 1));161 assert(array[9] == P(9, 2));162 }163 { // check all false but first true164 typedef std::pair<int,int> P;165 P array[] =166 {167 P(1, 1),168 P(0, 2),169 P(2, 1),170 P(2, 2),171 P(4, 1),172 P(4, 2),173 P(6, 1),174 P(6, 2),175 P(8, 1),176 P(8, 2)177 };178 const unsigned size = sizeof(array)/sizeof(array[0]);179 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());180 assert(base(r) == array + 1);181 assert(array[0] == P(1, 1));182 assert(array[1] == P(0, 2));183 assert(array[2] == P(2, 1));184 assert(array[3] == P(2, 2));185 assert(array[4] == P(4, 1));186 assert(array[5] == P(4, 2));187 assert(array[6] == P(6, 1));188 assert(array[7] == P(6, 2));189 assert(array[8] == P(8, 1));190 assert(array[9] == P(8, 2));191 }192 { // check all false but last true193 typedef std::pair<int,int> P;194 P array[] =195 {196 P(0, 1),197 P(0, 2),198 P(2, 1),199 P(2, 2),200 P(4, 1),201 P(4, 2),202 P(6, 1),203 P(6, 2),204 P(8, 1),205 P(1, 2)206 };207 const unsigned size = sizeof(array)/sizeof(array[0]);208 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());209 assert(base(r) == array + 1);210 assert(array[0] == P(1, 2));211 assert(array[1] == P(0, 1));212 assert(array[2] == P(0, 2));213 assert(array[3] == P(2, 1));214 assert(array[4] == P(2, 2));215 assert(array[5] == P(4, 1));216 assert(array[6] == P(4, 2));217 assert(array[7] == P(6, 1));218 assert(array[8] == P(6, 2));219 assert(array[9] == P(8, 1));220 }221 { // check all true but first false222 typedef std::pair<int,int> P;223 P array[] =224 {225 P(0, 1),226 P(1, 2),227 P(3, 1),228 P(3, 2),229 P(5, 1),230 P(5, 2),231 P(7, 1),232 P(7, 2),233 P(9, 1),234 P(9, 2)235 };236 const unsigned size = sizeof(array)/sizeof(array[0]);237 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());238 assert(base(r) == array + size-1);239 assert(array[0] == P(1, 2));240 assert(array[1] == P(3, 1));241 assert(array[2] == P(3, 2));242 assert(array[3] == P(5, 1));243 assert(array[4] == P(5, 2));244 assert(array[5] == P(7, 1));245 assert(array[6] == P(7, 2));246 assert(array[7] == P(9, 1));247 assert(array[8] == P(9, 2));248 assert(array[9] == P(0, 1));249 }250 { // check all true but last false251 typedef std::pair<int,int> P;252 P array[] =253 {254 P(1, 1),255 P(1, 2),256 P(3, 1),257 P(3, 2),258 P(5, 1),259 P(5, 2),260 P(7, 1),261 P(7, 2),262 P(9, 1),263 P(0, 2)264 };265 const unsigned size = sizeof(array)/sizeof(array[0]);266 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());267 assert(base(r) == array + size-1);268 assert(array[0] == P(1, 1));269 assert(array[1] == P(1, 2));270 assert(array[2] == P(3, 1));271 assert(array[3] == P(3, 2));272 assert(array[4] == P(5, 1));273 assert(array[5] == P(5, 2));274 assert(array[6] == P(7, 1));275 assert(array[7] == P(7, 2));276 assert(array[8] == P(9, 1));277 assert(array[9] == P(0, 2));278 }279#if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)280 // TODO: Re-enable this test for GCC once we get recursive inlining fixed.281 // For now it trips up GCC due to the use of always_inline.282# if !defined(TEST_COMPILER_GCC)283 if (!TEST_IS_CONSTANT_EVALUATED) { // check that the algorithm still works when no memory is available284 std::vector<int> vec(150, 3);285 vec[5] = 6;286 getGlobalMemCounter()->throw_after = 0;287 std::stable_partition(vec.begin(), vec.end(), [](int i) { return i < 5; });288 assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; }));289 vec[5] = 6;290 getGlobalMemCounter()->throw_after = 0;291 std::stable_partition(292 bidirectional_iterator<int*>(vec.data()), bidirectional_iterator<int*>(vec.data() + vec.size()), [](int i) {293 return i < 5;294 });295 assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; }));296 getGlobalMemCounter()->reset();297 }298# endif // !defined(TEST_COMPILER_GCC)299#endif // TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)300}301 302#if TEST_STD_VER >= 11303 304struct is_null {305 template <class P>306 TEST_CONSTEXPR_CXX26 bool operator()(const P& p) {307 return p == 0;308 }309};310 311template <class Iter>312TEST_CONSTEXPR_CXX26 void test1() {313 const unsigned size = 5;314 std::unique_ptr<int> array[size];315 Iter r = std::stable_partition(Iter(array), Iter(array + size), is_null());316 assert(r == Iter(array + size));317}318 319#endif // TEST_STD_VER >= 11320 321TEST_CONSTEXPR_CXX26 bool test() {322 test<bidirectional_iterator<std::pair<int, int>*> >();323 test<random_access_iterator<std::pair<int, int>*> >();324 test<std::pair<int, int>*>();325 326#if TEST_STD_VER >= 11327 test1<bidirectional_iterator<std::unique_ptr<int>*> >();328#endif329 330 return true;331}332 333int main(int, char**) {334 test();335#if TEST_STD_VER >= 26336 static_assert(test());337#endif338 339 return 0;340}341