functional revision 1.1.1.3
1 // <experimental/functional> -*- C++ -*- 2 3 // Copyright (C) 2014-2016 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file experimental/functional 26 * This is a TS C++ Library header. 27 */ 28 29 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 30 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1 31 32 #pragma GCC system_header 33 34 #if __cplusplus <= 201103L 35 # include <bits/c++14_warning.h> 36 #else 37 38 #include <functional> 39 #include <tuple> 40 #include <iterator> 41 #include <unordered_map> 42 #include <vector> 43 #include <array> 44 #include <bits/stl_algo.h> 45 #ifdef _GLIBCXX_PARALLEL 46 # include <parallel/algorithm> // For std::__parallel::search 47 #endif 48 #include <experimental/bits/lfts_config.h> 49 50 namespace std _GLIBCXX_VISIBILITY(default) 51 { 52 namespace experimental 53 { 54 inline namespace fundamentals_v1 55 { 56 _GLIBCXX_BEGIN_NAMESPACE_VERSION 57 58 // See C++14 20.9.9, Function object binders 59 60 /// Variable template for std::is_bind_expression 61 template<typename _Tp> 62 constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value; 63 64 /// Variable template for std::is_placeholder 65 template<typename _Tp> 66 constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value; 67 68 #define __cpp_lib_experimental_boyer_moore_searching 201411 69 70 // Searchers 71 72 template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>> 73 class default_searcher 74 { 75 public: 76 default_searcher(_ForwardIterator1 __pat_first, 77 _ForwardIterator1 __pat_last, 78 _BinaryPredicate __pred = _BinaryPredicate()) 79 : _M_m(__pat_first, __pat_last, std::move(__pred)) 80 { } 81 82 template<typename _ForwardIterator2> 83 _ForwardIterator2 84 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const 85 { 86 return std::search(__first, __last, 87 std::get<0>(_M_m), std::get<1>(_M_m), 88 std::get<2>(_M_m)); 89 } 90 91 private: 92 std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; 93 }; 94 95 template<typename _Key, typename _Tp, typename _Hash, typename _Pred> 96 struct __boyer_moore_map_base 97 { 98 template<typename _RAIter> 99 __boyer_moore_map_base(_RAIter __pat, size_t __patlen, 100 _Hash&& __hf, _Pred&& __pred) 101 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) } 102 { 103 if (__patlen > 0) 104 for (__diff_type __i = 0; __i < __patlen - 1; ++__i) 105 _M_bad_char[__pat[__i]] = __patlen - 1 - __i; 106 } 107 108 using __diff_type = _Tp; 109 110 __diff_type 111 _M_lookup(_Key __key, __diff_type __not_found) const 112 { 113 auto __iter = _M_bad_char.find(__key); 114 if (__iter == _M_bad_char.end()) 115 return __not_found; 116 return __iter->second; 117 } 118 119 _Pred 120 _M_pred() const { return _M_bad_char.key_eq(); } 121 122 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char; 123 }; 124 125 template<typename _Tp, size_t _Len, typename _Pred> 126 struct __boyer_moore_array_base 127 { 128 template<typename _RAIter, typename _Unused> 129 __boyer_moore_array_base(_RAIter __pat, size_t __patlen, 130 _Unused&&, _Pred&& __pred) 131 : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) } 132 { 133 std::get<0>(_M_bad_char).fill(__patlen); 134 if (__patlen > 0) 135 for (__diff_type __i = 0; __i < __patlen - 1; ++__i) 136 { 137 auto __ch = __pat[__i]; 138 using _UCh = std::make_unsigned_t<decltype(__ch)>; 139 auto __uch = static_cast<_UCh>(__ch); 140 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; 141 } 142 } 143 144 using __diff_type = _Tp; 145 146 template<typename _Key> 147 __diff_type 148 _M_lookup(_Key __key, __diff_type __not_found) const 149 { 150 auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key); 151 if (__ukey >= _Len) 152 return __not_found; 153 return std::get<0>(_M_bad_char)[__ukey]; 154 } 155 156 const _Pred& 157 _M_pred() const { return std::get<1>(_M_bad_char); } 158 159 std::tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char; 160 }; 161 162 template<typename _Pred> 163 struct __is_std_equal_to : std::false_type { }; 164 165 template<> 166 struct __is_std_equal_to<std::equal_to<void>> : std::true_type { }; 167 168 // Use __boyer_moore_array_base when pattern consists of narrow characters 169 // and uses std::equal_to as the predicate. 170 template<typename _RAIter, typename _Hash, typename _Pred, 171 typename _Val = typename iterator_traits<_RAIter>::value_type, 172 typename _Diff = typename iterator_traits<_RAIter>::difference_type> 173 using __boyer_moore_base_t 174 = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value 175 && __is_std_equal_to<_Pred>::value, 176 __boyer_moore_array_base<_Diff, 256, _Pred>, 177 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; 178 179 template<typename _RAIter, typename _Hash 180 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 181 typename _BinaryPredicate = std::equal_to<>> 182 class boyer_moore_searcher 183 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 184 { 185 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 186 using typename _Base::__diff_type; 187 188 public: 189 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 190 _Hash __hf = _Hash(), 191 _BinaryPredicate __pred = _BinaryPredicate()); 192 193 template<typename _RandomAccessIterator2> 194 _RandomAccessIterator2 195 operator()(_RandomAccessIterator2 __first, 196 _RandomAccessIterator2 __last) const; 197 198 private: 199 bool 200 _M_is_prefix(_RAIter __word, __diff_type __len, 201 __diff_type __pos) 202 { 203 const auto& __pred = this->_M_pred(); 204 __diff_type __suffixlen = __len - __pos; 205 for (__diff_type __i = 0; __i < __suffixlen; ++__i) 206 if (!__pred(__word[__i], __word[__pos + __i])) 207 return false; 208 return true; 209 } 210 211 __diff_type 212 _M_suffix_length(_RAIter __word, __diff_type __len, 213 __diff_type __pos) 214 { 215 const auto& __pred = this->_M_pred(); 216 __diff_type __i = 0; 217 while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) 218 && __i < __pos) 219 { 220 ++__i; 221 } 222 return __i; 223 } 224 225 template<typename _Tp> 226 __diff_type 227 _M_bad_char_shift(_Tp __c) const 228 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 229 230 _RAIter _M_pat; 231 _RAIter _M_pat_end; 232 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix; 233 }; 234 235 template<typename _RAIter, typename _Hash 236 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 237 typename _BinaryPredicate = std::equal_to<>> 238 class boyer_moore_horspool_searcher 239 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 240 { 241 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 242 using typename _Base::__diff_type; 243 244 public: 245 boyer_moore_horspool_searcher(_RAIter __pat, 246 _RAIter __pat_end, 247 _Hash __hf = _Hash(), 248 _BinaryPredicate __pred 249 = _BinaryPredicate()) 250 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 251 _M_pat(__pat), _M_pat_end(__pat_end) 252 { } 253 254 template<typename _RandomAccessIterator2> 255 _RandomAccessIterator2 256 operator()(_RandomAccessIterator2 __first, 257 _RandomAccessIterator2 __last) const 258 { 259 const auto& __pred = this->_M_pred(); 260 auto __patlen = _M_pat_end - _M_pat; 261 if (__patlen == 0) 262 return __first; 263 auto __len = __last - __first; 264 while (__len >= __patlen) 265 { 266 for (auto __scan = __patlen - 1; 267 __pred(__first[__scan], _M_pat[__scan]); --__scan) 268 if (__scan == 0) 269 return __first; 270 auto __shift = _M_bad_char_shift(__first[__patlen - 1]); 271 __len -= __shift; 272 __first += __shift; 273 } 274 return __last; 275 } 276 277 private: 278 template<typename _Tp> 279 __diff_type 280 _M_bad_char_shift(_Tp __c) const 281 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 282 283 _RAIter _M_pat; 284 _RAIter _M_pat_end; 285 }; 286 287 /// Generator function for default_searcher 288 template<typename _ForwardIterator, 289 typename _BinaryPredicate = std::equal_to<>> 290 inline default_searcher<_ForwardIterator, _BinaryPredicate> 291 make_default_searcher(_ForwardIterator __pat_first, 292 _ForwardIterator __pat_last, 293 _BinaryPredicate __pred = _BinaryPredicate()) 294 { return { __pat_first, __pat_last, __pred }; } 295 296 /// Generator function for boyer_moore_searcher 297 template<typename _RAIter, typename _Hash 298 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 299 typename _BinaryPredicate = equal_to<>> 300 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> 301 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 302 _Hash __hf = _Hash(), 303 _BinaryPredicate __pred = _BinaryPredicate()) 304 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 305 306 /// Generator function for boyer_moore_horspool_searcher 307 template<typename _RAIter, typename _Hash 308 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 309 typename _BinaryPredicate = equal_to<>> 310 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> 311 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, 312 _Hash __hf = _Hash(), 313 _BinaryPredicate __pred 314 = _BinaryPredicate()) 315 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 316 317 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 318 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 319 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, 320 _Hash __hf, _BinaryPredicate __pred) 321 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 322 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) 323 { 324 auto __patlen = __pat_end - __pat; 325 if (__patlen == 0) 326 return; 327 __diff_type __last_prefix = __patlen - 1; 328 for (__diff_type __p = __patlen - 1; __p >= 0; --__p) 329 { 330 if (_M_is_prefix(__pat, __patlen, __p + 1)) 331 __last_prefix = __p + 1; 332 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); 333 } 334 for (__diff_type __p = 0; __p < __patlen - 1; ++__p) 335 { 336 auto __slen = _M_suffix_length(__pat, __patlen, __p); 337 auto __pos = __patlen - 1 - __slen; 338 if (!__pred(__pat[__p - __slen], __pat[__pos])) 339 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; 340 } 341 } 342 343 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 344 template<typename _RandomAccessIterator2> 345 _RandomAccessIterator2 346 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 347 operator()(_RandomAccessIterator2 __first, 348 _RandomAccessIterator2 __last) const 349 { 350 auto __patlen = _M_pat_end - _M_pat; 351 if (__patlen == 0) 352 return __first; 353 const auto& __pred = this->_M_pred(); 354 __diff_type __i = __patlen - 1; 355 auto __stringlen = __last - __first; 356 while (__i < __stringlen) 357 { 358 __diff_type __j = __patlen - 1; 359 while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) 360 { 361 --__i; 362 --__j; 363 } 364 if (__j < 0) 365 return __first + __i + 1; 366 __i += std::max(_M_bad_char_shift(__first[__i]), 367 _M_good_suffix[__j]); 368 } 369 return __last; 370 } 371 372 _GLIBCXX_END_NAMESPACE_VERSION 373 } // namespace fundamentals_v1 374 375 inline namespace fundamentals_v2 376 { 377 _GLIBCXX_BEGIN_NAMESPACE_VERSION 378 379 #define __cpp_lib_experimental_not_fn 201406 380 381 /// Generalized negator. 382 template<typename _Fn> 383 class _Not_fn 384 { 385 _Fn _M_fn; 386 387 public: 388 template<typename _Fn2> 389 explicit 390 _Not_fn(_Fn2&& __fn, int) : _M_fn(std::forward<_Fn2>(__fn)) { } 391 392 _Not_fn(const _Not_fn& __fn) = default; 393 _Not_fn(_Not_fn&& __fn) = default; 394 _Not_fn& operator=(const _Not_fn& __fn) = default; 395 _Not_fn& operator=(_Not_fn&& __fn) = default; 396 ~_Not_fn() = default; 397 398 template<typename... _Args> 399 auto 400 operator()(_Args&&... __args) 401 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 402 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 403 { return !_M_fn(std::forward<_Args>(__args)...); } 404 405 template<typename... _Args> 406 auto 407 operator()(_Args&&... __args) const 408 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 409 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 410 { return !_M_fn(std::forward<_Args>(__args)...); } 411 412 template<typename... _Args> 413 auto 414 operator()(_Args&&... __args) volatile 415 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 416 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 417 { return !_M_fn(std::forward<_Args>(__args)...); } 418 419 template<typename... _Args> 420 auto 421 operator()(_Args&&... __args) const volatile 422 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 423 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 424 { return !_M_fn(std::forward<_Args>(__args)...); } 425 }; 426 427 /// [func.not_fn] Function template not_fn 428 template<typename _Fn> 429 inline auto 430 not_fn(_Fn&& __fn) 431 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value) 432 { 433 using __maybe_type = _Maybe_wrap_member_pointer<std::decay_t<_Fn>>; 434 return _Not_fn<typename __maybe_type::type>{std::forward<_Fn>(__fn), 0}; 435 } 436 437 _GLIBCXX_END_NAMESPACE_VERSION 438 } // namespace fundamentals_v2 439 } // namespace experimental 440 } // namespace std 441 442 #endif // C++14 443 444 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 445
Indexes created Thu Sep 10 00:26:39 UTC 2026