functional revision 1.1.1.2
1 // <experimental/functional> -*- C++ -*- 2 3 // Copyright (C) 2014-2015 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 #include <experimental/lfts_config.h> 46 47 namespace std _GLIBCXX_VISIBILITY(default) 48 { 49 namespace experimental 50 { 51 inline namespace fundamentals_v1 52 { 53 _GLIBCXX_BEGIN_NAMESPACE_VERSION 54 55 // See C++14 20.9.9, Function object binders 56 57 /// Variable template for std::is_bind_expression 58 template<typename _Tp> 59 constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value; 60 61 /// Variable template for std::is_placeholder 62 template<typename _Tp> 63 constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value; 64 65 #define __cpp_lib_experimental_boyer_moore_searching 201411 66 67 // Searchers 68 69 template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>> 70 class default_searcher 71 { 72 public: 73 default_searcher(_ForwardIterator1 __pat_first, 74 _ForwardIterator1 __pat_last, 75 _BinaryPredicate __pred = _BinaryPredicate()) 76 : _M_m(__pat_first, __pat_last, std::move(__pred)) 77 { } 78 79 template<typename _ForwardIterator2> 80 _ForwardIterator2 81 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const 82 { 83 return std::search(__first, __last, 84 std::get<0>(_M_m), std::get<1>(_M_m), 85 std::get<2>(_M_m)); 86 } 87 88 private: 89 std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; 90 }; 91 92 template<typename _Key, typename _Tp, typename _Hash, typename _Pred> 93 struct __boyer_moore_map_base 94 { 95 template<typename _RAIter> 96 __boyer_moore_map_base(_RAIter __pat, size_t __patlen, 97 _Hash&& __hf, _Pred&& __pred) 98 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) } 99 { 100 if (__patlen > 0) 101 for (__diff_type __i = 0; __i < __patlen - 1; ++__i) 102 _M_bad_char[__pat[__i]] = __patlen - 1 - __i; 103 } 104 105 using __diff_type = _Tp; 106 107 __diff_type 108 _M_lookup(_Key __key, __diff_type __not_found) const 109 { 110 auto __iter = _M_bad_char.find(__key); 111 if (__iter == _M_bad_char.end()) 112 return __not_found; 113 return __iter->second; 114 } 115 116 _Pred 117 _M_pred() const { return _M_bad_char.key_eq(); } 118 119 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char; 120 }; 121 122 template<typename _Tp, size_t _Len, typename _Pred> 123 struct __boyer_moore_array_base 124 { 125 template<typename _RAIter, typename _Unused> 126 __boyer_moore_array_base(_RAIter __pat, size_t __patlen, 127 _Unused&&, _Pred&& __pred) 128 : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) } 129 { 130 std::get<0>(_M_bad_char).fill(__patlen); 131 if (__patlen > 0) 132 for (__diff_type __i = 0; __i < __patlen - 1; ++__i) 133 { 134 auto __ch = __pat[__i]; 135 using _UCh = std::make_unsigned_t<decltype(__ch)>; 136 auto __uch = static_cast<_UCh>(__ch); 137 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; 138 } 139 } 140 141 using __diff_type = _Tp; 142 143 template<typename _Key> 144 __diff_type 145 _M_lookup(_Key __key, __diff_type __not_found) const 146 { 147 auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key); 148 if (__ukey >= _Len) 149 return __not_found; 150 return std::get<0>(_M_bad_char)[__ukey]; 151 } 152 153 const _Pred& 154 _M_pred() const { return std::get<1>(_M_bad_char); } 155 156 std::tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char; 157 }; 158 159 template<typename _Pred> 160 struct __is_std_equal_to : std::false_type { }; 161 162 template<> 163 struct __is_std_equal_to<std::equal_to<void>> : std::true_type { }; 164 165 // Use __boyer_moore_array_base when pattern consists of narrow characters 166 // and uses std::equal_to as the predicate. 167 template<typename _RAIter, typename _Hash, typename _Pred, 168 typename _Val = typename iterator_traits<_RAIter>::value_type, 169 typename _Diff = typename iterator_traits<_RAIter>::difference_type> 170 using __boyer_moore_base_t 171 = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value 172 && __is_std_equal_to<_Pred>::value, 173 __boyer_moore_array_base<_Diff, 256, _Pred>, 174 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; 175 176 template<typename _RAIter, typename _Hash 177 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 178 typename _BinaryPredicate = std::equal_to<>> 179 class boyer_moore_searcher 180 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 181 { 182 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 183 using typename _Base::__diff_type; 184 185 public: 186 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 187 _Hash __hf = _Hash(), 188 _BinaryPredicate __pred = _BinaryPredicate()); 189 190 template<typename _RandomAccessIterator2> 191 _RandomAccessIterator2 192 operator()(_RandomAccessIterator2 __first, 193 _RandomAccessIterator2 __last) const; 194 195 private: 196 bool 197 _M_is_prefix(_RAIter __word, __diff_type __len, 198 __diff_type __pos) 199 { 200 const auto& __pred = this->_M_pred(); 201 __diff_type __suffixlen = __len - __pos; 202 for (__diff_type __i = 0; __i < __suffixlen; ++__i) 203 if (!__pred(__word[__i], __word[__pos + __i])) 204 return false; 205 return true; 206 } 207 208 __diff_type 209 _M_suffix_length(_RAIter __word, __diff_type __len, 210 __diff_type __pos) 211 { 212 const auto& __pred = this->_M_pred(); 213 __diff_type __i = 0; 214 while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) 215 && __i < __pos) 216 { 217 ++__i; 218 } 219 return __i; 220 } 221 222 template<typename _Tp> 223 __diff_type 224 _M_bad_char_shift(_Tp __c) const 225 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 226 227 _RAIter _M_pat; 228 _RAIter _M_pat_end; 229 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix; 230 }; 231 232 template<typename _RAIter, typename _Hash 233 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 234 typename _BinaryPredicate = std::equal_to<>> 235 class boyer_moore_horspool_searcher 236 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 237 { 238 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 239 using typename _Base::__diff_type; 240 241 public: 242 boyer_moore_horspool_searcher(_RAIter __pat, 243 _RAIter __pat_end, 244 _Hash __hf = _Hash(), 245 _BinaryPredicate __pred 246 = _BinaryPredicate()) 247 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 248 _M_pat(__pat), _M_pat_end(__pat_end) 249 { } 250 251 template<typename _RandomAccessIterator2> 252 _RandomAccessIterator2 253 operator()(_RandomAccessIterator2 __first, 254 _RandomAccessIterator2 __last) const 255 { 256 const auto& __pred = this->_M_pred(); 257 auto __patlen = _M_pat_end - _M_pat; 258 if (__patlen == 0) 259 return __first; 260 auto __len = __last - __first; 261 while (__len >= __patlen) 262 { 263 for (auto __scan = __patlen - 1; 264 __pred(__first[__scan], _M_pat[__scan]); --__scan) 265 if (__scan == 0) 266 return __first; 267 auto __shift = _M_bad_char_shift(__first[__patlen - 1]); 268 __len -= __shift; 269 __first += __shift; 270 } 271 return __last; 272 } 273 274 private: 275 template<typename _Tp> 276 __diff_type 277 _M_bad_char_shift(_Tp __c) const 278 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 279 280 _RAIter _M_pat; 281 _RAIter _M_pat_end; 282 }; 283 284 /// Generator function for default_searcher 285 template<typename _ForwardIterator, 286 typename _BinaryPredicate = std::equal_to<>> 287 inline default_searcher<_ForwardIterator, _BinaryPredicate> 288 make_default_searcher(_ForwardIterator __pat_first, 289 _ForwardIterator __pat_last, 290 _BinaryPredicate __pred = _BinaryPredicate()) 291 { return { __pat_first, __pat_last, __pred }; } 292 293 /// Generator function for boyer_moore_searcher 294 template<typename _RAIter, typename _Hash 295 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 296 typename _BinaryPredicate = equal_to<>> 297 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> 298 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 299 _Hash __hf = _Hash(), 300 _BinaryPredicate __pred = _BinaryPredicate()) 301 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 302 303 /// Generator function for boyer_moore_horspool_searcher 304 template<typename _RAIter, typename _Hash 305 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 306 typename _BinaryPredicate = equal_to<>> 307 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> 308 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, 309 _Hash __hf = _Hash(), 310 _BinaryPredicate __pred 311 = _BinaryPredicate()) 312 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 313 314 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 315 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 316 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, 317 _Hash __hf, _BinaryPredicate __pred) 318 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 319 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) 320 { 321 auto __patlen = __pat_end - __pat; 322 if (__patlen == 0) 323 return; 324 __diff_type __last_prefix = __patlen - 1; 325 for (__diff_type __p = __patlen - 1; __p >= 0; --__p) 326 { 327 if (_M_is_prefix(__pat, __patlen, __p + 1)) 328 __last_prefix = __p + 1; 329 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); 330 } 331 for (__diff_type __p = 0; __p < __patlen - 1; ++__p) 332 { 333 auto __slen = _M_suffix_length(__pat, __patlen, __p); 334 auto __pos = __patlen - 1 - __slen; 335 if (!__pred(__pat[__p - __slen], __pat[__pos])) 336 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; 337 } 338 } 339 340 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 341 template<typename _RandomAccessIterator2> 342 _RandomAccessIterator2 343 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 344 operator()(_RandomAccessIterator2 __first, 345 _RandomAccessIterator2 __last) const 346 { 347 auto __patlen = _M_pat_end - _M_pat; 348 if (__patlen == 0) 349 return __first; 350 const auto& __pred = this->_M_pred(); 351 __diff_type __i = __patlen - 1; 352 auto __stringlen = __last - __first; 353 while (__i < __stringlen) 354 { 355 __diff_type __j = __patlen - 1; 356 while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) 357 { 358 --__i; 359 --__j; 360 } 361 if (__j < 0) 362 return __first + __i + 1; 363 __i += std::max(_M_bad_char_shift(__first[__i]), 364 _M_good_suffix[__j]); 365 } 366 return __last; 367 } 368 369 _GLIBCXX_END_NAMESPACE_VERSION 370 } // namespace fundamentals_v1 371 372 inline namespace fundamentals_v2 373 { 374 _GLIBCXX_BEGIN_NAMESPACE_VERSION 375 376 #define __cpp_lib_experimental_not_fn 201406 377 378 /// Generalized negator. 379 template<typename _Fn> 380 class _Not_fn 381 { 382 _Fn _M_fn; 383 384 public: 385 template<typename _Fn2> 386 explicit 387 _Not_fn(_Fn2&& __fn, int) : _M_fn(std::forward<_Fn2>(__fn)) { } 388 389 _Not_fn(const _Not_fn& __fn) = default; 390 _Not_fn(_Not_fn&& __fn) = default; 391 _Not_fn& operator=(const _Not_fn& __fn) = default; 392 _Not_fn& operator=(_Not_fn&& __fn) = default; 393 ~_Not_fn() = default; 394 395 template<typename... _Args> 396 auto 397 operator()(_Args&&... __args) 398 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 399 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 400 { return !_M_fn(std::forward<_Args>(__args)...); } 401 402 template<typename... _Args> 403 auto 404 operator()(_Args&&... __args) const 405 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 406 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 407 { return !_M_fn(std::forward<_Args>(__args)...); } 408 409 template<typename... _Args> 410 auto 411 operator()(_Args&&... __args) volatile 412 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 413 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 414 { return !_M_fn(std::forward<_Args>(__args)...); } 415 416 template<typename... _Args> 417 auto 418 operator()(_Args&&... __args) const volatile 419 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...))) 420 -> decltype(!_M_fn(std::forward<_Args>(__args)...)) 421 { return !_M_fn(std::forward<_Args>(__args)...); } 422 }; 423 424 /// [func.not_fn] Function template not_fn 425 template<typename _Fn> 426 inline auto 427 not_fn(_Fn&& __fn) 428 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value) 429 { 430 using __maybe_type = _Maybe_wrap_member_pointer<std::decay_t<_Fn>>; 431 return _Not_fn<typename __maybe_type::type>{std::forward<_Fn>(__fn), 0}; 432 } 433 434 _GLIBCXX_END_NAMESPACE_VERSION 435 } // namespace fundamentals_v2 436 } // namespace experimental 437 } // namespace std 438 439 #endif // C++14 440 441 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 442
Indexes created Thu Sep 10 00:26:39 UTC 2026