Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/experimental/functional
1 // <experimental/functional> -*- C++ -*- 2 3 // Copyright (C) 2014-2025 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 * @ingroup libfund-ts 28 */ 29 30 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 31 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1 32 33 #ifdef _GLIBCXX_SYSHDR 34 #pragma GCC system_header 35 #endif 36 37 #include <bits/requires_hosted.h> // experimental is currently omitted 38 39 #if __cplusplus >= 201402L 40 41 #include <functional> 42 #include <tuple> 43 #include <iterator> 44 #include <unordered_map> 45 #include <vector> 46 #include <array> 47 #include <bits/stl_algobase.h> // std::max, std::search 48 #include <experimental/bits/lfts_config.h> 49 50 namespace std _GLIBCXX_VISIBILITY(default) 51 { 52 _GLIBCXX_BEGIN_NAMESPACE_VERSION 53 54 namespace experimental 55 { 56 inline namespace fundamentals_v1 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{ std::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<std::array<_Tp, _Len>, _Pred> _M_bad_char; 160 }; 161 162 // Use __boyer_moore_array_base when pattern consists of narrow characters 163 // (or std::byte) and uses std::equal_to as the predicate. 164 template<typename _RAIter, typename _Hash, typename _Pred, 165 typename _Val = typename iterator_traits<_RAIter>::value_type, 166 typename _Diff = typename iterator_traits<_RAIter>::difference_type> 167 using __boyer_moore_base_t 168 = std::__conditional_t<std::__is_byte_like<_Val, _Pred>::value, 169 __boyer_moore_array_base<_Diff, 256, _Pred>, 170 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; 171 172 template<typename _RAIter, typename _Hash 173 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 174 typename _BinaryPredicate = std::equal_to<>> 175 class boyer_moore_searcher 176 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 177 { 178 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 179 using typename _Base::__diff_type; 180 181 public: 182 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 183 _Hash __hf = _Hash(), 184 _BinaryPredicate __pred = _BinaryPredicate()); 185 186 template<typename _RandomAccessIterator2> 187 _RandomAccessIterator2 188 operator()(_RandomAccessIterator2 __first, 189 _RandomAccessIterator2 __last) const; 190 191 private: 192 bool 193 _M_is_prefix(_RAIter __word, __diff_type __len, 194 __diff_type __pos) 195 { 196 const auto& __pred = this->_M_pred(); 197 __diff_type __suffixlen = __len - __pos; 198 for (__diff_type __i = 0; __i < __suffixlen; ++__i) 199 if (!__pred(__word[__i], __word[__pos + __i])) 200 return false; 201 return true; 202 } 203 204 __diff_type 205 _M_suffix_length(_RAIter __word, __diff_type __len, 206 __diff_type __pos) 207 { 208 const auto& __pred = this->_M_pred(); 209 __diff_type __i = 0; 210 while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) 211 && __i < __pos) 212 { 213 ++__i; 214 } 215 return __i; 216 } 217 218 template<typename _Tp> 219 __diff_type 220 _M_bad_char_shift(_Tp __c) const 221 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 222 223 _RAIter _M_pat; 224 _RAIter _M_pat_end; 225 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix; 226 }; 227 228 template<typename _RAIter, typename _Hash 229 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 230 typename _BinaryPredicate = std::equal_to<>> 231 class boyer_moore_horspool_searcher 232 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 233 { 234 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 235 using typename _Base::__diff_type; 236 237 public: 238 boyer_moore_horspool_searcher(_RAIter __pat, 239 _RAIter __pat_end, 240 _Hash __hf = _Hash(), 241 _BinaryPredicate __pred 242 = _BinaryPredicate()) 243 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 244 _M_pat(__pat), _M_pat_end(__pat_end) 245 { } 246 247 template<typename _RandomAccessIterator2> 248 _RandomAccessIterator2 249 operator()(_RandomAccessIterator2 __first, 250 _RandomAccessIterator2 __last) const 251 { 252 const auto& __pred = this->_M_pred(); 253 auto __patlen = _M_pat_end - _M_pat; 254 if (__patlen == 0) 255 return __first; 256 auto __len = __last - __first; 257 while (__len >= __patlen) 258 { 259 for (auto __scan = __patlen - 1; 260 __pred(__first[__scan], _M_pat[__scan]); --__scan) 261 if (__scan == 0) 262 return __first; 263 auto __shift = _M_bad_char_shift(__first[__patlen - 1]); 264 __len -= __shift; 265 __first += __shift; 266 } 267 return __last; 268 } 269 270 private: 271 template<typename _Tp> 272 __diff_type 273 _M_bad_char_shift(_Tp __c) const 274 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 275 276 _RAIter _M_pat; 277 _RAIter _M_pat_end; 278 }; 279 280 /// Generator function for default_searcher 281 template<typename _ForwardIterator, 282 typename _BinaryPredicate = std::equal_to<>> 283 inline default_searcher<_ForwardIterator, _BinaryPredicate> 284 make_default_searcher(_ForwardIterator __pat_first, 285 _ForwardIterator __pat_last, 286 _BinaryPredicate __pred = _BinaryPredicate()) 287 { return { __pat_first, __pat_last, __pred }; } 288 289 /// Generator function for boyer_moore_searcher 290 template<typename _RAIter, typename _Hash 291 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 292 typename _BinaryPredicate = equal_to<>> 293 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> 294 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 295 _Hash __hf = _Hash(), 296 _BinaryPredicate __pred = _BinaryPredicate()) 297 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 298 299 /// Generator function for boyer_moore_horspool_searcher 300 template<typename _RAIter, typename _Hash 301 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 302 typename _BinaryPredicate = equal_to<>> 303 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> 304 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, 305 _Hash __hf = _Hash(), 306 _BinaryPredicate __pred 307 = _BinaryPredicate()) 308 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 309 310 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 311 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 312 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, 313 _Hash __hf, _BinaryPredicate __pred) 314 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 315 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) 316 { 317 auto __patlen = __pat_end - __pat; 318 if (__patlen == 0) 319 return; 320 __diff_type __last_prefix = __patlen - 1; 321 for (__diff_type __p = __patlen - 1; __p >= 0; --__p) 322 { 323 if (_M_is_prefix(__pat, __patlen, __p + 1)) 324 __last_prefix = __p + 1; 325 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); 326 } 327 for (__diff_type __p = 0; __p < __patlen - 1; ++__p) 328 { 329 auto __slen = _M_suffix_length(__pat, __patlen, __p); 330 auto __pos = __patlen - 1 - __slen; 331 if (!__pred(__pat[__p - __slen], __pat[__pos])) 332 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; 333 } 334 } 335 336 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 337 template<typename _RandomAccessIterator2> 338 _RandomAccessIterator2 339 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 340 operator()(_RandomAccessIterator2 __first, 341 _RandomAccessIterator2 __last) const 342 { 343 auto __patlen = _M_pat_end - _M_pat; 344 if (__patlen == 0) 345 return __first; 346 const auto& __pred = this->_M_pred(); 347 __diff_type __i = __patlen - 1; 348 auto __stringlen = __last - __first; 349 while (__i < __stringlen) 350 { 351 __diff_type __j = __patlen - 1; 352 while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) 353 { 354 --__i; 355 --__j; 356 } 357 if (__j < 0) 358 return __first + __i + 1; 359 __i += std::max(_M_bad_char_shift(__first[__i]), 360 _M_good_suffix[__j]); 361 } 362 return __last; 363 } 364 } // namespace fundamentals_v1 365 366 inline namespace fundamentals_v2 367 { 368 #define __cpp_lib_experimental_not_fn 201406 369 370 /// [func.not_fn] Function template not_fn 371 template<typename _Fn> 372 inline auto 373 not_fn(_Fn&& __fn) 374 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value) 375 { 376 return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0}; 377 } 378 } // namespace fundamentals_v2 379 } // namespace experimental 380 381 _GLIBCXX_END_NAMESPACE_VERSION 382 } // namespace std 383 384 #endif // C++14 385 386 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
