Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
$ cat -n /usr/include/c++/13/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp 1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2023 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 terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // 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 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** 37 * @file ov_tree_map_/ov_tree_map_.hpp 38 * Contains an implementation class for ov_tree. 39 */ 40 41 #include <map> 42 #include <set> 43 #include <ext/pb_ds/exception.hpp> 44 #include <ext/pb_ds/tree_policy.hpp> 45 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 46 #include <ext/pb_ds/detail/types_traits.hpp> 47 #include <ext/pb_ds/detail/type_utils.hpp> 48 #include <ext/pb_ds/detail/tree_trace_base.hpp> 49 #ifdef _GLIBCXX_DEBUG 50 #include <ext/pb_ds/detail/debug_map_base.hpp> 51 #endif 52 #include <utility> 53 #include <functional> 54 #include <algorithm> 55 #include <vector> 56 #include <assert.h> 57 #include <debug/debug.h> 58 59 namespace __gnu_pbds 60 { 61 namespace detail 62 { 63 #ifdef PB_DS_DATA_TRUE_INDICATOR 64 #define PB_DS_OV_TREE_NAME ov_tree_map 65 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_map 66 #endif 67 68 #ifdef PB_DS_DATA_FALSE_INDICATOR 69 #define PB_DS_OV_TREE_NAME ov_tree_set 70 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_set 71 #endif 72 73 #define PB_DS_CLASS_T_DEC \ 74 template<typename Key, typename Mapped, typename Cmp_Fn, \ 75 typename Node_And_It_Traits, typename _Alloc> 76 77 #define PB_DS_CLASS_C_DEC \ 78 PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 79 80 #define PB_DS_OV_TREE_TRAITS_BASE \ 81 types_traits<Key, Mapped, _Alloc, false> 82 83 #ifdef _GLIBCXX_DEBUG 84 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 85 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 86 typename rebind_traits<_Alloc, Key>::const_reference> 87 #endif 88 89 #ifdef PB_DS_TREE_TRACE 90 #define PB_DS_TREE_TRACE_BASE_C_DEC \ 91 tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \ 92 typename Node_And_It_Traits::node_iterator, \ 93 Cmp_Fn, false, _Alloc> 94 #endif 95 96 #ifndef PB_DS_CHECK_KEY_EXISTS 97 # error Missing definition 98 #endif 99 100 /** 101 * @brief Ordered-vector tree associative-container. 102 * @ingroup branch-detail 103 */ 104 template<typename Key, typename Mapped, typename Cmp_Fn, 105 typename Node_And_It_Traits, typename _Alloc> 106 class PB_DS_OV_TREE_NAME : 107 #ifdef _GLIBCXX_DEBUG 108 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 109 #endif 110 #ifdef PB_DS_TREE_TRACE 111 public PB_DS_TREE_TRACE_BASE_C_DEC, 112 #endif 113 public Cmp_Fn, 114 public Node_And_It_Traits::node_update, 115 public PB_DS_OV_TREE_TRAITS_BASE 116 { 117 private: 118 typedef PB_DS_OV_TREE_TRAITS_BASE traits_base; 119 typedef Node_And_It_Traits traits_type; 120 121 typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type; 122 123 typedef rebind_traits<_Alloc, non_const_value_type> value_alloc_traits; 124 typedef typename value_alloc_traits::allocator_type value_allocator; 125 typedef typename value_alloc_traits::pointer value_vector; 126 127 #ifdef _GLIBCXX_DEBUG 128 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 129 #endif 130 131 #ifdef PB_DS_TREE_TRACE 132 typedef PB_DS_TREE_TRACE_BASE_C_DEC trace_base; 133 #endif 134 135 typedef typename traits_base::pointer mapped_pointer_; 136 typedef typename traits_base::const_pointer mapped_const_pointer_; 137 138 typedef typename traits_type::metadata_type metadata_type; 139 140 typedef rebind_traits<_Alloc, metadata_type> metadata_alloc_traits; 141 typedef typename metadata_alloc_traits::allocator_type metadata_allocator; 142 typedef typename metadata_alloc_traits::pointer metadata_pointer; 143 typedef typename metadata_alloc_traits::const_reference metadata_const_reference; 144 typedef typename metadata_alloc_traits::reference metadata_reference; 145 146 typedef typename traits_type::null_node_update_pointer 147 null_node_update_pointer; 148 149 public: 150 typedef ov_tree_tag container_category; 151 typedef _Alloc allocator_type; 152 typedef typename _Alloc::size_type size_type; 153 typedef typename _Alloc::difference_type difference_type; 154 typedef Cmp_Fn cmp_fn; 155 156 typedef typename traits_base::key_type key_type; 157 typedef typename traits_base::key_pointer key_pointer; 158 typedef typename traits_base::key_const_pointer key_const_pointer; 159 typedef typename traits_base::key_reference key_reference; 160 typedef typename traits_base::key_const_reference key_const_reference; 161 typedef typename traits_base::mapped_type mapped_type; 162 typedef typename traits_base::mapped_pointer mapped_pointer; 163 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 164 typedef typename traits_base::mapped_reference mapped_reference; 165 typedef typename traits_base::mapped_const_reference mapped_const_reference; 166 typedef typename traits_base::value_type value_type; 167 typedef typename traits_base::pointer pointer; 168 typedef typename traits_base::const_pointer const_pointer; 169 typedef typename traits_base::reference reference; 170 typedef typename traits_base::const_reference const_reference; 171 172 typedef const_pointer point_const_iterator; 173 #ifdef PB_DS_DATA_TRUE_INDICATOR 174 typedef pointer point_iterator; 175 #else 176 typedef point_const_iterator point_iterator; 177 #endif 178 179 typedef point_iterator iterator; 180 typedef point_const_iterator const_iterator; 181 182 /// Conditional destructor. 183 template<typename Size_Type> 184 class cond_dtor 185 { 186 public: 187 cond_dtor(value_vector a_vec, iterator& r_last_it, 188 Size_Type total_size) 189 : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size), 190 m_no_action(false) 191 { } 192 193 ~cond_dtor() 194 { 195 if (m_no_action) 196 return; 197 iterator it = m_a_vec; 198 while (it != m_r_last_it) 199 { 200 it->~value_type(); 201 ++it; 202 } 203 204 if (m_max_size > 0) 205 value_allocator().deallocate(m_a_vec, m_max_size); 206 } 207 208 inline void 209 set_no_action() 210 { m_no_action = true; } 211 212 protected: 213 value_vector m_a_vec; 214 iterator& m_r_last_it; 215 const Size_Type m_max_size; 216 bool m_no_action; 217 }; 218 219 typedef typename traits_type::node_update node_update; 220 typedef typename traits_type::node_iterator node_iterator; 221 typedef typename traits_type::node_const_iterator node_const_iterator; 222 223 224 PB_DS_OV_TREE_NAME(); 225 226 PB_DS_OV_TREE_NAME(const Cmp_Fn&); 227 228 PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&); 229 230 PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&); 231 232 ~PB_DS_OV_TREE_NAME(); 233 234 void 235 swap(PB_DS_CLASS_C_DEC&); 236 237 template<typename It> 238 void 239 copy_from_range(It, It); 240 241 inline size_type 242 max_size() const; 243 244 _GLIBCXX_NODISCARD inline bool 245 empty() const; 246 247 inline size_type 248 size() const; 249 250 Cmp_Fn& 251 get_cmp_fn(); 252 253 const Cmp_Fn& 254 get_cmp_fn() const; 255 256 inline mapped_reference 257 operator[](key_const_reference r_key) 258 { 259 #ifdef PB_DS_DATA_TRUE_INDICATOR 260 PB_DS_ASSERT_VALID((*this)) 261 point_iterator it = lower_bound(r_key); 262 if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 263 { 264 PB_DS_CHECK_KEY_EXISTS(r_key) 265 PB_DS_ASSERT_VALID((*this)) 266 return it->second; 267 } 268 return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second; 269 #else 270 insert(r_key); 271 return traits_base::s_null_type; 272 #endif 273 } 274 275 inline std::pair<point_iterator, bool> 276 insert(const_reference r_value) 277 { 278 PB_DS_ASSERT_VALID((*this)) 279 key_const_reference r_key = PB_DS_V2F(r_value); 280 point_iterator it = lower_bound(r_key); 281 282 if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 283 { 284 PB_DS_ASSERT_VALID((*this)) 285 PB_DS_CHECK_KEY_EXISTS(r_key) 286 return std::make_pair(it, false); 287 } 288 289 return std::make_pair(insert_new_val(it, r_value), true); 290 } 291 292 inline point_iterator 293 lower_bound(key_const_reference r_key) 294 { 295 pointer it = m_a_values; 296 pointer e_it = m_a_values + m_size; 297 while (it != e_it) 298 { 299 pointer mid_it = it + ((e_it - it) >> 1); 300 if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key)) 301 it = ++mid_it; 302 else 303 e_it = mid_it; 304 } 305 return it; 306 } 307 308 inline point_const_iterator 309 lower_bound(key_const_reference r_key) const 310 { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); } 311 312 inline point_iterator 313 upper_bound(key_const_reference r_key) 314 { 315 iterator pot_it = lower_bound(r_key); 316 if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 317 { 318 PB_DS_CHECK_KEY_EXISTS(r_key) 319 return ++pot_it; 320 } 321 322 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 323 return pot_it; 324 } 325 326 inline point_const_iterator 327 upper_bound(key_const_reference r_key) const 328 { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); } 329 330 inline point_iterator 331 find(key_const_reference r_key) 332 { 333 PB_DS_ASSERT_VALID((*this)) 334 iterator pot_it = lower_bound(r_key); 335 if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 336 { 337 PB_DS_CHECK_KEY_EXISTS(r_key) 338 return pot_it; 339 } 340 341 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 342 return end(); 343 } 344 345 inline point_const_iterator 346 find(key_const_reference r_key) const 347 { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); } 348 349 bool 350 erase(key_const_reference); 351 352 template<typename Pred> 353 inline size_type 354 erase_if(Pred); 355 356 inline iterator 357 erase(iterator it) 358 { return erase_imp<iterator>(it); } 359 360 void 361 clear(); 362 363 void 364 join(PB_DS_CLASS_C_DEC&); 365 366 void 367 split(key_const_reference, PB_DS_CLASS_C_DEC&); 368 369 inline iterator 370 begin() 371 { return m_a_values; } 372 373 inline const_iterator 374 begin() const 375 { return m_a_values; } 376 377 inline iterator 378 end() 379 { return m_end_it; } 380 381 inline const_iterator 382 end() const 383 { return m_end_it; } 384 385 /// Returns a const node_iterator corresponding to the node at the 386 /// root of the tree. 387 inline node_const_iterator 388 node_begin() const; 389 390 /// Returns a node_iterator corresponding to the node at the 391 /// root of the tree. 392 inline node_iterator 393 node_begin(); 394 395 /// Returns a const node_iterator corresponding to a node just 396 /// after a leaf of the tree. 397 inline node_const_iterator 398 node_end() const; 399 400 /// Returns a node_iterator corresponding to a node just 401 /// after a leaf of the tree. 402 inline node_iterator 403 node_end(); 404 405 private: 406 407 inline void 408 update(node_iterator, null_node_update_pointer); 409 410 template<typename Node_Update> 411 void 412 update(node_iterator, Node_Update*); 413 414 void 415 reallocate_metadata(null_node_update_pointer, size_type); 416 417 template<typename Node_Update_> 418 void 419 reallocate_metadata(Node_Update_*, size_type); 420 421 template<typename It> 422 void 423 copy_from_ordered_range(It, It); 424 425 void 426 value_swap(PB_DS_CLASS_C_DEC&); 427 428 template<typename It> 429 void 430 copy_from_ordered_range(It, It, It, It); 431 432 template<typename Ptr> 433 inline static Ptr 434 mid_pointer(Ptr p_begin, Ptr p_end) 435 { 436 _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); 437 return (p_begin + (p_end - p_begin) / 2); 438 } 439 440 inline iterator 441 insert_new_val(iterator it, const_reference r_value) 442 { 443 #ifdef PB_DS_REGRESSION 444 typename _Alloc::group_adjustor adjust(m_size); 445 #endif 446 447 PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value)) 448 449 value_vector a_values = s_value_alloc.allocate(m_size + 1); 450 451 iterator source_it = begin(); 452 iterator source_end_it = end(); 453 iterator target_it = a_values; 454 iterator ret_it; 455 456 cond_dtor<size_type> cd(a_values, target_it, m_size + 1); 457 while (source_it != it) 458 { 459 new (const_cast<void*>(static_cast<const void*>(target_it))) 460 value_type(*source_it++); 461 ++target_it; 462 } 463 464 new (const_cast<void*>(static_cast<const void*>(ret_it = target_it))) 465 value_type(r_value); 466 ++target_it; 467 468 while (source_it != source_end_it) 469 { 470 new (const_cast<void*>(static_cast<const void*>(target_it))) 471 value_type(*source_it++); 472 ++target_it; 473 } 474 475 reallocate_metadata((node_update*)this, m_size + 1); 476 cd.set_no_action(); 477 if (m_size != 0) 478 { 479 cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); 480 } 481 482 ++m_size; 483 m_a_values = a_values; 484 m_end_it = m_a_values + m_size; 485 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value))); 486 update(node_begin(), (node_update* )this); 487 PB_DS_ASSERT_VALID((*this)) 488 return ret_it; 489 } 490 491 #ifdef _GLIBCXX_DEBUG 492 void 493 assert_valid(const char*, int) const; 494 495 void 496 assert_iterators(const char*, int) const; 497 #endif 498 499 template<typename It> 500 It 501 erase_imp(It); 502 503 inline node_const_iterator 504 PB_DS_node_begin_imp() const; 505 506 inline node_const_iterator 507 PB_DS_node_end_imp() const; 508 509 inline node_iterator 510 PB_DS_node_begin_imp(); 511 512 inline node_iterator 513 PB_DS_node_end_imp(); 514 515 private: 516 static value_allocator s_value_alloc; 517 static metadata_allocator s_metadata_alloc; 518 519 value_vector m_a_values; 520 metadata_pointer m_a_metadata; 521 iterator m_end_it; 522 size_type m_size; 523 }; 524 525 #include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp> 526 #include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp> 527 #include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp> 528 #include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp> 529 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp> 530 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp> 531 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp> 532 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 533 534 #undef PB_DS_CLASS_C_DEC 535 #undef PB_DS_CLASS_T_DEC 536 #undef PB_DS_OV_TREE_NAME 537 #undef PB_DS_OV_TREE_TRAITS_BASE 538 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 539 #ifdef PB_DS_TREE_TRACE 540 #undef PB_DS_TREE_TRACE_BASE_C_DEC 541 #endif 542 #undef PB_DS_CONST_NODE_ITERATOR_NAME 543 } // namespace detail 544 } // namespace __gnu_pbds
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
