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 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 73 #define PB_DS_CLASS_T_DEC \ 74 template<typename Key, typename Mapped, typename Cmp_Fn, \ 75 typename Node_And_It_Traits, typename _Alloc> 77 #define PB_DS_CLASS_C_DEC \ 78 PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 80 #define PB_DS_OV_TREE_TRAITS_BASE \ 81 types_traits<Key, Mapped, _Alloc, false> 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> 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> 96 #ifndef PB_DS_CHECK_KEY_EXISTS 97 # error Missing definition 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,
110 #ifdef PB_DS_TREE_TRACE 111 public PB_DS_TREE_TRACE_BASE_C_DEC,
114 public Node_And_It_Traits::node_update,
115 public PB_DS_OV_TREE_TRAITS_BASE
119 typedef Node_And_It_Traits traits_type;
121 typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
124 typedef typename value_alloc_traits::allocator_type value_allocator;
125 typedef typename value_alloc_traits::pointer value_vector;
127 #ifdef _GLIBCXX_DEBUG 128 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
131 #ifdef PB_DS_TREE_TRACE 132 typedef PB_DS_TREE_TRACE_BASE_C_DEC trace_base;
135 typedef typename traits_base::pointer mapped_pointer_;
136 typedef typename traits_base::const_pointer mapped_const_pointer_;
138 typedef typename traits_type::metadata_type metadata_type;
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;
146 typedef typename traits_type::null_node_update_pointer
147 null_node_update_pointer;
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;
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;
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;
172 typedef const_pointer point_const_iterator;
173 #ifdef PB_DS_DATA_TRUE_INDICATOR 174 typedef pointer point_iterator;
176 typedef point_const_iterator point_iterator;
179 typedef point_iterator iterator;
180 typedef point_const_iterator const_iterator;
183 template<
typename Size_Type>
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),
197 iterator it = m_a_vec;
198 while (it != m_r_last_it)
205 value_allocator().deallocate(m_a_vec, m_max_size);
210 { m_no_action =
true; }
213 value_vector m_a_vec;
214 iterator& m_r_last_it;
215 const Size_Type m_max_size;
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;
224 PB_DS_OV_TREE_NAME();
226 PB_DS_OV_TREE_NAME(
const Cmp_Fn&);
228 PB_DS_OV_TREE_NAME(
const Cmp_Fn&,
const node_update&);
230 PB_DS_OV_TREE_NAME(
const PB_DS_CLASS_C_DEC&);
232 ~PB_DS_OV_TREE_NAME();
235 swap(PB_DS_CLASS_C_DEC&);
237 template<
typename It>
239 copy_from_range(It, It);
244 _GLIBCXX_NODISCARD
inline bool 256 inline mapped_reference
257 operator[](key_const_reference r_key)
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)))
264 PB_DS_CHECK_KEY_EXISTS(r_key)
265 PB_DS_ASSERT_VALID((*
this))
268 return insert_new_val(it,
std::make_pair(r_key, mapped_type()))->second;
271 return traits_base::s_null_type;
276 insert(const_reference r_value)
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);
282 if (it !=
end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
284 PB_DS_ASSERT_VALID((*
this))
285 PB_DS_CHECK_KEY_EXISTS(r_key)
286 return
std::make_pair(it, false);
289 return
std::make_pair(insert_new_val(it, r_value), true);
292 inline point_iterator
293 lower_bound(key_const_reference r_key)
295 pointer it = m_a_values;
296 pointer e_it = m_a_values + m_size;
299 pointer mid_it = it + ((e_it - it) >> 1);
300 if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
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); }
312 inline point_iterator
313 upper_bound(key_const_reference r_key)
315 iterator pot_it = lower_bound(r_key);
316 if (pot_it !=
end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
318 PB_DS_CHECK_KEY_EXISTS(r_key)
322 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
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); }
330 inline point_iterator
331 find(key_const_reference r_key)
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)))
337 PB_DS_CHECK_KEY_EXISTS(r_key)
341 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
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)); }
350 erase(key_const_reference);
352 template<
typename Pred>
358 {
return erase_imp<iterator>(it); }
364 join(PB_DS_CLASS_C_DEC&);
367 split(key_const_reference, PB_DS_CLASS_C_DEC&);
371 {
return m_a_values; }
373 inline const_iterator
375 {
return m_a_values; }
381 inline const_iterator
387 inline node_const_iterator
397 inline node_const_iterator
408 update(node_iterator, null_node_update_pointer);
410 template<
typename Node_Update>
412 update(node_iterator, Node_Update*);
415 reallocate_metadata(null_node_update_pointer, size_type);
417 template<
typename Node_Update_>
419 reallocate_metadata(Node_Update_*, size_type);
421 template<
typename It>
423 copy_from_ordered_range(It, It);
426 value_swap(PB_DS_CLASS_C_DEC&);
428 template<
typename It>
430 copy_from_ordered_range(It, It, It, It);
432 template<
typename Ptr>
434 mid_pointer(Ptr p_begin, Ptr p_end)
436 _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
437 return (p_begin + (p_end - p_begin) / 2);
441 insert_new_val(iterator it, const_reference r_value)
443 #ifdef PB_DS_REGRESSION 444 typename _Alloc::group_adjustor adjust(m_size);
447 PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value))
449 value_vector a_values = s_value_alloc.allocate(m_size + 1);
451 iterator source_it =
begin();
452 iterator source_end_it =
end();
453 iterator target_it = a_values;
456 cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
457 while (source_it != it)
459 new (
const_cast<void*
>(
static_cast<const void*
>(target_it)))
460 value_type(*source_it++);
464 new (
const_cast<void*
>(
static_cast<const void*
>(ret_it = target_it)))
468 while (source_it != source_end_it)
470 new (
const_cast<void*
>(
static_cast<const void*
>(target_it)))
471 value_type(*source_it++);
475 reallocate_metadata((node_update*)
this, m_size + 1);
479 cond_dtor<size_type> cd1(m_a_values, m_end_it, 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))
491 #ifdef _GLIBCXX_DEBUG 493 assert_valid(
const char*,
int)
const;
496 assert_iterators(
const char*,
int)
const;
499 template<
typename It>
503 inline node_const_iterator
504 PB_DS_node_begin_imp()
const;
506 inline node_const_iterator
507 PB_DS_node_end_imp()
const;
510 PB_DS_node_begin_imp();
513 PB_DS_node_end_imp();
516 static value_allocator s_value_alloc;
517 static metadata_allocator s_metadata_alloc;
519 value_vector m_a_values;
520 metadata_pointer m_a_metadata;
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 542 #undef PB_DS_CONST_NODE_ITERATOR_NAME _Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Struct holding two objects of arbitrary type.
GNU extensions for policy-based data structures for public use.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
ISO C++ entities toplevel namespace is std.
Consistent API for accessing allocator-related types.