]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost | |
4 | // Software License, Version 1.0. (See accompanying file | |
5 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | // | |
7 | // See http://www.boost.org/libs/container for documentation. | |
8 | // | |
9 | ////////////////////////////////////////////////////////////////////////////// | |
10 | ||
11 | #ifndef BOOST_CONTAINER_TREE_HPP | |
12 | #define BOOST_CONTAINER_TREE_HPP | |
13 | ||
14 | #ifndef BOOST_CONFIG_HPP | |
15 | # include <boost/config.hpp> | |
16 | #endif | |
17 | ||
18 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
19 | # pragma once | |
20 | #endif | |
21 | ||
22 | #include <boost/container/detail/config_begin.hpp> | |
23 | #include <boost/container/detail/workaround.hpp> | |
24 | // container | |
25 | #include <boost/container/allocator_traits.hpp> | |
26 | #include <boost/container/container_fwd.hpp> | |
27 | #include <boost/container/options.hpp> | |
28 | #include <boost/container/node_handle.hpp> | |
29 | ||
30 | // container/detail | |
31 | #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare | |
32 | #include <boost/container/detail/compare_functors.hpp> | |
33 | #include <boost/container/detail/destroyers.hpp> | |
34 | #include <boost/container/detail/iterator.hpp> | |
35 | #include <boost/container/detail/iterators.hpp> | |
36 | #include <boost/container/detail/node_alloc_holder.hpp> | |
37 | #include <boost/container/detail/pair.hpp> | |
38 | #include <boost/container/detail/type_traits.hpp> | |
39 | // intrusive | |
40 | #include <boost/intrusive/pointer_traits.hpp> | |
41 | #include <boost/intrusive/rbtree.hpp> | |
42 | #include <boost/intrusive/avltree.hpp> | |
43 | #include <boost/intrusive/splaytree.hpp> | |
44 | #include <boost/intrusive/sgtree.hpp> | |
45 | // intrusive/detail | |
46 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair | |
47 | #include <boost/intrusive/detail/tree_value_compare.hpp> //tree_value_compare | |
48 | // move | |
49 | #include <boost/move/utility_core.hpp> | |
50 | // move/detail | |
51 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
52 | #include <boost/move/detail/fwd_macros.hpp> | |
53 | #endif | |
54 | #include <boost/move/detail/move_helpers.hpp> | |
55 | // other | |
56 | #include <boost/core/no_exceptions_support.hpp> | |
57 | ||
58 | ||
59 | ||
60 | #include <boost/container/detail/std_fwd.hpp> | |
61 | ||
62 | namespace boost { | |
63 | namespace container { | |
11fdf7f2 | 64 | namespace dtl { |
7c673cae FG |
65 | |
66 | using boost::intrusive::tree_value_compare; | |
67 | ||
68 | template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
69 | struct intrusive_tree_hook; | |
70 | ||
71 | template<class VoidPointer, bool OptimizeSize> | |
72 | struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize> | |
73 | { | |
11fdf7f2 TL |
74 | typedef typename dtl::bi::make_set_base_hook |
75 | < dtl::bi::void_pointer<VoidPointer> | |
76 | , dtl::bi::link_mode<dtl::bi::normal_link> | |
77 | , dtl::bi::optimize_size<OptimizeSize> | |
7c673cae FG |
78 | >::type type; |
79 | }; | |
80 | ||
81 | template<class VoidPointer, bool OptimizeSize> | |
82 | struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize> | |
83 | { | |
11fdf7f2 TL |
84 | typedef typename dtl::bi::make_avl_set_base_hook |
85 | < dtl::bi::void_pointer<VoidPointer> | |
86 | , dtl::bi::link_mode<dtl::bi::normal_link> | |
87 | , dtl::bi::optimize_size<OptimizeSize> | |
7c673cae FG |
88 | >::type type; |
89 | }; | |
90 | ||
91 | template<class VoidPointer, bool OptimizeSize> | |
92 | struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize> | |
93 | { | |
11fdf7f2 TL |
94 | typedef typename dtl::bi::make_bs_set_base_hook |
95 | < dtl::bi::void_pointer<VoidPointer> | |
96 | , dtl::bi::link_mode<dtl::bi::normal_link> | |
7c673cae FG |
97 | >::type type; |
98 | }; | |
99 | ||
100 | template<class VoidPointer, bool OptimizeSize> | |
101 | struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize> | |
102 | { | |
11fdf7f2 TL |
103 | typedef typename dtl::bi::make_bs_set_base_hook |
104 | < dtl::bi::void_pointer<VoidPointer> | |
105 | , dtl::bi::link_mode<dtl::bi::normal_link> | |
7c673cae FG |
106 | >::type type; |
107 | }; | |
108 | ||
109 | //This trait is used to type-pun std::pair because in C++03 | |
110 | //compilers std::pair is useless for C++11 features | |
111 | template<class T> | |
112 | struct tree_internal_data_type | |
113 | { | |
114 | typedef T type; | |
115 | }; | |
116 | ||
117 | template<class T1, class T2> | |
118 | struct tree_internal_data_type< std::pair<T1, T2> > | |
119 | { | |
120 | typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type; | |
121 | }; | |
122 | ||
123 | //The node to be store in the tree | |
124 | template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
125 | struct tree_node | |
126 | : public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type | |
127 | { | |
7c673cae FG |
128 | public: |
129 | typedef typename intrusive_tree_hook | |
130 | <VoidPointer, tree_type_value, OptimizeSize>::type hook_type; | |
131 | typedef T value_type; | |
132 | typedef typename tree_internal_data_type<T>::type internal_type; | |
133 | ||
134 | typedef tree_node< T, VoidPointer | |
135 | , tree_type_value, OptimizeSize> node_t; | |
136 | ||
92f5a8d4 TL |
137 | typedef typename boost::container::dtl::aligned_storage |
138 | <sizeof(T), boost::container::dtl::alignment_of<T>::value>::type storage_t; | |
139 | storage_t m_storage; | |
140 | ||
141 | #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000) | |
142 | #pragma GCC diagnostic push | |
143 | #pragma GCC diagnostic ignored "-Wstrict-aliasing" | |
144 | #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING | |
145 | # endif | |
146 | ||
7c673cae | 147 | BOOST_CONTAINER_FORCEINLINE T &get_data() |
92f5a8d4 | 148 | { return *reinterpret_cast<T*>(this->m_storage.data); } |
7c673cae FG |
149 | |
150 | BOOST_CONTAINER_FORCEINLINE const T &get_data() const | |
92f5a8d4 TL |
151 | { return *reinterpret_cast<const T*>(this->m_storage.data); } |
152 | ||
153 | BOOST_CONTAINER_FORCEINLINE T *get_data_ptr() | |
154 | { return reinterpret_cast<T*>(this->m_storage.data); } | |
155 | ||
156 | BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const | |
157 | { return reinterpret_cast<T*>(this->m_storage.data); } | |
158 | ||
159 | BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data() | |
160 | { return *reinterpret_cast<internal_type*>(this->m_storage.data); } | |
161 | ||
162 | BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const | |
163 | { return *reinterpret_cast<const internal_type*>(this->m_storage.data); } | |
164 | ||
165 | BOOST_CONTAINER_FORCEINLINE internal_type *get_real_data_ptr() | |
166 | { return reinterpret_cast<internal_type*>(this->m_storage.data); } | |
167 | ||
168 | BOOST_CONTAINER_FORCEINLINE const internal_type *get_real_data_ptr() const | |
169 | { return reinterpret_cast<internal_type*>(this->m_storage.data); } | |
7c673cae | 170 | |
92f5a8d4 TL |
171 | BOOST_CONTAINER_FORCEINLINE ~tree_node() |
172 | { reinterpret_cast<internal_type*>(this->m_storage.data)->~internal_type(); } | |
173 | ||
174 | #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING) | |
175 | #pragma GCC diagnostic pop | |
176 | #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING | |
177 | # endif | |
178 | ||
179 | BOOST_CONTAINER_FORCEINLINE void destroy_header() | |
180 | { static_cast<hook_type*>(this)->~hook_type(); } | |
7c673cae FG |
181 | |
182 | template<class T1, class T2> | |
183 | BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p) | |
184 | { | |
92f5a8d4 TL |
185 | const_cast<T1&>(this->get_real_data().first) = p.first; |
186 | this->get_real_data().second = p.second; | |
7c673cae FG |
187 | } |
188 | ||
189 | template<class T1, class T2> | |
190 | BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p) | |
191 | { | |
92f5a8d4 TL |
192 | const_cast<T1&>(this->get_real_data().first) = p.first; |
193 | this->get_real_data().second = p.second; | |
7c673cae FG |
194 | } |
195 | ||
196 | template<class V> | |
197 | BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v) | |
92f5a8d4 | 198 | { this->get_real_data() = v; } |
7c673cae FG |
199 | |
200 | template<class T1, class T2> | |
201 | BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p) | |
202 | { | |
92f5a8d4 TL |
203 | const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first); |
204 | this->get_real_data().second = ::boost::move(p.second); | |
7c673cae FG |
205 | } |
206 | ||
207 | template<class T1, class T2> | |
208 | BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p) | |
209 | { | |
92f5a8d4 TL |
210 | const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first); |
211 | this->get_real_data().second = ::boost::move(p.second); | |
7c673cae FG |
212 | } |
213 | ||
214 | template<class V> | |
215 | BOOST_CONTAINER_FORCEINLINE void do_move_assign(V &v) | |
92f5a8d4 | 216 | { this->get_real_data() = ::boost::move(v); } |
7c673cae FG |
217 | }; |
218 | ||
219 | template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
220 | struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > { | |
221 | typedef T type; | |
222 | }; | |
223 | ||
224 | template<class Node, class Icont> | |
225 | class insert_equal_end_hint_functor | |
226 | { | |
227 | Icont &icont_; | |
228 | ||
229 | public: | |
230 | BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont) | |
231 | : icont_(icont) | |
232 | {} | |
233 | ||
234 | BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) | |
235 | { this->icont_.insert_equal(this->icont_.cend(), n); } | |
236 | }; | |
237 | ||
238 | template<class Node, class Icont> | |
239 | class push_back_functor | |
240 | { | |
241 | Icont &icont_; | |
242 | ||
243 | public: | |
244 | BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont) | |
245 | : icont_(icont) | |
246 | {} | |
247 | ||
248 | BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) | |
249 | { this->icont_.push_back(n); } | |
250 | }; | |
251 | ||
11fdf7f2 | 252 | }//namespace dtl { |
7c673cae | 253 | |
11fdf7f2 | 254 | namespace dtl { |
7c673cae FG |
255 | |
256 | template< class NodeType, class NodeCompareType | |
257 | , class SizeType, class HookType | |
258 | , boost::container::tree_type_enum tree_type_value> | |
259 | struct intrusive_tree_dispatch; | |
260 | ||
261 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
262 | struct intrusive_tree_dispatch | |
263 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree> | |
264 | { | |
11fdf7f2 | 265 | typedef typename dtl::bi::make_rbtree |
7c673cae | 266 | <NodeType |
11fdf7f2 TL |
267 | ,dtl::bi::compare<NodeCompareType> |
268 | ,dtl::bi::base_hook<HookType> | |
269 | ,dtl::bi::constant_time_size<true> | |
270 | ,dtl::bi::size_type<SizeType> | |
7c673cae FG |
271 | >::type type; |
272 | }; | |
273 | ||
274 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
275 | struct intrusive_tree_dispatch | |
276 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree> | |
277 | { | |
11fdf7f2 | 278 | typedef typename dtl::bi::make_avltree |
7c673cae | 279 | <NodeType |
11fdf7f2 TL |
280 | ,dtl::bi::compare<NodeCompareType> |
281 | ,dtl::bi::base_hook<HookType> | |
282 | ,dtl::bi::constant_time_size<true> | |
283 | ,dtl::bi::size_type<SizeType> | |
7c673cae FG |
284 | >::type type; |
285 | }; | |
286 | ||
287 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
288 | struct intrusive_tree_dispatch | |
289 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree> | |
290 | { | |
11fdf7f2 | 291 | typedef typename dtl::bi::make_sgtree |
7c673cae | 292 | <NodeType |
11fdf7f2 TL |
293 | ,dtl::bi::compare<NodeCompareType> |
294 | ,dtl::bi::base_hook<HookType> | |
295 | ,dtl::bi::floating_point<true> | |
296 | ,dtl::bi::size_type<SizeType> | |
7c673cae FG |
297 | >::type type; |
298 | }; | |
299 | ||
300 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
301 | struct intrusive_tree_dispatch | |
302 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree> | |
303 | { | |
11fdf7f2 | 304 | typedef typename dtl::bi::make_splaytree |
7c673cae | 305 | <NodeType |
11fdf7f2 TL |
306 | ,dtl::bi::compare<NodeCompareType> |
307 | ,dtl::bi::base_hook<HookType> | |
308 | ,dtl::bi::constant_time_size<true> | |
309 | ,dtl::bi::size_type<SizeType> | |
7c673cae FG |
310 | >::type type; |
311 | }; | |
312 | ||
313 | template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
314 | struct intrusive_tree_type | |
315 | { | |
316 | private: | |
317 | typedef typename boost::container:: | |
318 | allocator_traits<Allocator>::value_type value_type; | |
319 | typedef typename boost::container:: | |
320 | allocator_traits<Allocator>::void_pointer void_pointer; | |
321 | typedef typename boost::container:: | |
322 | allocator_traits<Allocator>::size_type size_type; | |
11fdf7f2 | 323 | typedef typename dtl::tree_node |
7c673cae FG |
324 | < value_type, void_pointer |
325 | , tree_type_value, OptimizeSize> node_t; | |
326 | typedef value_to_node_compare | |
327 | <node_t, ValueCompare> node_compare_type; | |
328 | //Deducing the hook type from node_t (e.g. node_t::hook_type) would | |
329 | //provoke an early instantiation of node_t that could ruin recursive | |
330 | //tree definitions, so retype the complete type to avoid any problem. | |
331 | typedef typename intrusive_tree_hook | |
332 | <void_pointer, tree_type_value | |
333 | , OptimizeSize>::type hook_type; | |
334 | public: | |
335 | typedef typename intrusive_tree_dispatch | |
336 | < node_t, node_compare_type | |
337 | , size_type, hook_type | |
338 | , tree_type_value>::type type; | |
339 | }; | |
340 | ||
341 | //Trait to detect manually rebalanceable tree types | |
342 | template<boost::container::tree_type_enum tree_type_value> | |
343 | struct is_manually_balanceable | |
344 | { static const bool value = true; }; | |
345 | ||
346 | template<> struct is_manually_balanceable<red_black_tree> | |
347 | { static const bool value = false; }; | |
348 | ||
349 | template<> struct is_manually_balanceable<avl_tree> | |
350 | { static const bool value = false; }; | |
351 | ||
352 | //Proxy traits to implement different operations depending on the | |
353 | //is_manually_balanceable<>::value | |
354 | template< boost::container::tree_type_enum tree_type_value | |
355 | , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value> | |
356 | struct intrusive_tree_proxy | |
357 | { | |
358 | template<class Icont> | |
359 | BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &) {} | |
360 | }; | |
361 | ||
362 | template<boost::container::tree_type_enum tree_type_value> | |
363 | struct intrusive_tree_proxy<tree_type_value, true> | |
364 | { | |
365 | template<class Icont> | |
366 | BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c) | |
367 | { c.rebalance(); } | |
368 | }; | |
369 | ||
11fdf7f2 | 370 | } //namespace dtl { |
7c673cae | 371 | |
11fdf7f2 | 372 | namespace dtl { |
7c673cae FG |
373 | |
374 | //This functor will be used with Intrusive clone functions to obtain | |
375 | //already allocated nodes from a intrusive container instead of | |
376 | //allocating new ones. When the intrusive container runs out of nodes | |
377 | //the node holder is used instead. | |
378 | template<class AllocHolder, bool DoMove> | |
379 | class RecyclingCloner | |
380 | { | |
381 | typedef typename AllocHolder::intrusive_container intrusive_container; | |
382 | typedef typename AllocHolder::Node node_t; | |
383 | typedef typename AllocHolder::NodePtr node_ptr_type; | |
384 | ||
385 | public: | |
386 | RecyclingCloner(AllocHolder &holder, intrusive_container &itree) | |
387 | : m_holder(holder), m_icont(itree) | |
388 | {} | |
389 | ||
390 | BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>) | |
92f5a8d4 | 391 | { p->do_move_assign(const_cast<node_t &>(other).get_real_data()); } |
7c673cae FG |
392 | |
393 | BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>) | |
92f5a8d4 | 394 | { p->do_assign(other.get_real_data()); } |
7c673cae FG |
395 | |
396 | node_ptr_type operator()(const node_t &other) const | |
397 | { | |
398 | if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ | |
399 | //First recycle a node (this can't throw) | |
400 | BOOST_TRY{ | |
401 | //This can throw | |
402 | this->do_assign(p, other, bool_<DoMove>()); | |
403 | return p; | |
404 | } | |
405 | BOOST_CATCH(...){ | |
406 | //If there is an exception destroy the whole source | |
407 | m_holder.destroy_node(p); | |
408 | while((p = m_icont.unlink_leftmost_without_rebalance())){ | |
409 | m_holder.destroy_node(p); | |
410 | } | |
411 | BOOST_RETHROW | |
412 | } | |
413 | BOOST_CATCH_END | |
414 | } | |
415 | else{ | |
92f5a8d4 | 416 | return m_holder.create_node(other.get_real_data()); |
7c673cae FG |
417 | } |
418 | } | |
419 | ||
420 | AllocHolder &m_holder; | |
421 | intrusive_container &m_icont; | |
422 | }; | |
423 | ||
92f5a8d4 | 424 | |
7c673cae FG |
425 | template<class KeyCompare, class KeyOfValue> |
426 | struct key_node_compare | |
427 | : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> | |
428 | { | |
429 | BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp) | |
430 | : base_t(comp) | |
431 | {} | |
432 | ||
433 | typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t; | |
434 | typedef KeyCompare key_compare; | |
435 | typedef KeyOfValue key_of_value; | |
436 | typedef typename KeyOfValue::type key_type; | |
437 | ||
92f5a8d4 TL |
438 | |
439 | template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
440 | BOOST_CONTAINER_FORCEINLINE static const key_type & | |
441 | key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n) | |
442 | { | |
443 | return key_of_value()(n.get_data()); | |
444 | } | |
445 | ||
446 | template <class T> | |
447 | BOOST_CONTAINER_FORCEINLINE static const T & | |
448 | key_from(const T &t) | |
449 | { | |
450 | return t; | |
451 | } | |
452 | ||
7c673cae FG |
453 | BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const |
454 | { return static_cast<const key_compare &>(*this); } | |
455 | ||
456 | BOOST_CONTAINER_FORCEINLINE key_compare &key_comp() | |
457 | { return static_cast<key_compare &>(*this); } | |
458 | ||
459 | BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const | |
460 | { return this->key_comp()(key1, key2); } | |
461 | ||
462 | template<class U> | |
463 | BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const | |
92f5a8d4 | 464 | { return this->key_comp()(key1, this->key_from(nonkey2)); } |
7c673cae FG |
465 | |
466 | template<class U> | |
467 | BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const | |
92f5a8d4 | 468 | { return this->key_comp()(this->key_from(nonkey1), key2); } |
7c673cae FG |
469 | |
470 | template<class U, class V> | |
471 | BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const | |
92f5a8d4 | 472 | { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); } |
7c673cae FG |
473 | }; |
474 | ||
11fdf7f2 TL |
475 | template<class Options> |
476 | struct get_tree_opt | |
477 | { | |
478 | typedef Options type; | |
479 | }; | |
480 | ||
481 | template<> | |
482 | struct get_tree_opt<void> | |
483 | { | |
484 | typedef tree_assoc_defaults type; | |
485 | }; | |
486 | ||
92f5a8d4 TL |
487 | template<class, class KeyOfValue> |
488 | struct real_key_of_value | |
489 | { | |
490 | typedef KeyOfValue type; | |
491 | }; | |
492 | ||
493 | template<class T> | |
494 | struct real_key_of_value<T, void> | |
495 | { | |
496 | typedef dtl::identity<T> type; | |
497 | }; | |
498 | ||
499 | template<class T1, class T2> | |
500 | struct real_key_of_value<std::pair<T1, T2>, int> | |
501 | { | |
502 | typedef dtl::select1st<T1> type; | |
503 | }; | |
504 | ||
505 | template<class T1, class T2> | |
506 | struct real_key_of_value<boost::container::pair<T1, T2>, int> | |
507 | { | |
508 | typedef dtl::select1st<T1> type; | |
509 | }; | |
510 | ||
11fdf7f2 | 511 | template <class T, class KeyOfValue, class Compare, class Allocator, class Options> |
7c673cae | 512 | class tree |
11fdf7f2 | 513 | : public dtl::node_alloc_holder |
92f5a8d4 | 514 | < typename real_allocator<T, Allocator>::type |
11fdf7f2 | 515 | , typename dtl::intrusive_tree_type |
92f5a8d4 TL |
516 | < typename real_allocator<T, Allocator>::type |
517 | , tree_value_compare | |
518 | <typename allocator_traits<typename real_allocator<T, Allocator>::type>::pointer, Compare, typename real_key_of_value<T, KeyOfValue>::type> | |
11fdf7f2 TL |
519 | , get_tree_opt<Options>::type::tree_type |
520 | , get_tree_opt<Options>::type::optimize_size | |
521 | >::type | |
7c673cae FG |
522 | > |
523 | { | |
92f5a8d4 TL |
524 | typedef tree < T, KeyOfValue |
525 | , Compare, Allocator, Options> ThisType; | |
526 | public: | |
527 | typedef typename real_allocator<T, Allocator>::type allocator_type; | |
528 | ||
529 | private: | |
530 | typedef allocator_traits<allocator_type> allocator_traits_t; | |
531 | typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t; | |
7c673cae | 532 | typedef tree_value_compare |
92f5a8d4 TL |
533 | < typename allocator_traits_t::pointer |
534 | , Compare | |
535 | , key_of_value_t> ValComp; | |
11fdf7f2 TL |
536 | typedef typename get_tree_opt<Options>::type options_type; |
537 | typedef typename dtl::intrusive_tree_type | |
92f5a8d4 | 538 | < allocator_type, ValComp |
11fdf7f2 TL |
539 | , options_type::tree_type |
540 | , options_type::optimize_size | |
541 | >::type Icont; | |
542 | typedef dtl::node_alloc_holder | |
92f5a8d4 | 543 | <allocator_type, Icont> AllocHolder; |
7c673cae | 544 | typedef typename AllocHolder::NodePtr NodePtr; |
92f5a8d4 | 545 | |
7c673cae FG |
546 | typedef typename AllocHolder::NodeAlloc NodeAlloc; |
547 | typedef boost::container:: | |
548 | allocator_traits<NodeAlloc> allocator_traits_type; | |
549 | typedef typename AllocHolder::ValAlloc ValAlloc; | |
550 | typedef typename AllocHolder::Node Node; | |
551 | typedef typename Icont::iterator iiterator; | |
552 | typedef typename Icont::const_iterator iconst_iterator; | |
11fdf7f2 | 553 | typedef dtl::allocator_destroyer<NodeAlloc> Destroyer; |
7c673cae | 554 | typedef typename AllocHolder::alloc_version alloc_version; |
11fdf7f2 | 555 | typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t; |
7c673cae FG |
556 | |
557 | BOOST_COPYABLE_AND_MOVABLE(tree) | |
558 | ||
559 | public: | |
560 | ||
92f5a8d4 TL |
561 | typedef typename key_of_value_t::type key_type; |
562 | typedef T value_type; | |
563 | typedef Compare key_compare; | |
564 | typedef ValComp value_compare; | |
7c673cae | 565 | typedef typename boost::container:: |
92f5a8d4 | 566 | allocator_traits<allocator_type>::pointer pointer; |
7c673cae | 567 | typedef typename boost::container:: |
92f5a8d4 | 568 | allocator_traits<allocator_type>::const_pointer const_pointer; |
7c673cae | 569 | typedef typename boost::container:: |
92f5a8d4 | 570 | allocator_traits<allocator_type>::reference reference; |
7c673cae | 571 | typedef typename boost::container:: |
92f5a8d4 | 572 | allocator_traits<allocator_type>::const_reference const_reference; |
7c673cae | 573 | typedef typename boost::container:: |
92f5a8d4 | 574 | allocator_traits<allocator_type>::size_type size_type; |
7c673cae | 575 | typedef typename boost::container:: |
92f5a8d4 | 576 | allocator_traits<allocator_type>::difference_type difference_type; |
11fdf7f2 | 577 | typedef dtl::iterator_from_iiterator |
92f5a8d4 | 578 | <iiterator, false> iterator; |
11fdf7f2 | 579 | typedef dtl::iterator_from_iiterator |
92f5a8d4 | 580 | <iiterator, true > const_iterator; |
7c673cae | 581 | typedef boost::container::reverse_iterator |
92f5a8d4 | 582 | <iterator> reverse_iterator; |
7c673cae | 583 | typedef boost::container::reverse_iterator |
92f5a8d4 | 584 | <const_iterator> const_reverse_iterator; |
7c673cae | 585 | typedef node_handle |
92f5a8d4 | 586 | < NodeAlloc, void> node_type; |
7c673cae | 587 | typedef insert_return_type_base |
92f5a8d4 | 588 | <iterator, node_type> insert_return_type; |
7c673cae | 589 | |
92f5a8d4 | 590 | typedef NodeAlloc stored_allocator_type; |
7c673cae FG |
591 | |
592 | private: | |
593 | ||
92f5a8d4 | 594 | typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare; |
7c673cae FG |
595 | |
596 | public: | |
597 | ||
598 | BOOST_CONTAINER_FORCEINLINE tree() | |
599 | : AllocHolder() | |
600 | {} | |
601 | ||
b32b8144 FG |
602 | BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp) |
603 | : AllocHolder(ValComp(comp)) | |
604 | {} | |
605 | ||
606 | BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a) | |
7c673cae FG |
607 | : AllocHolder(ValComp(comp), a) |
608 | {} | |
609 | ||
610 | BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a) | |
611 | : AllocHolder(a) | |
612 | {} | |
613 | ||
614 | template <class InputIterator> | |
b32b8144 FG |
615 | tree(bool unique_insertion, InputIterator first, InputIterator last) |
616 | : AllocHolder(value_compare(key_compare())) | |
617 | { | |
618 | this->tree_construct(unique_insertion, first, last); | |
619 | //AllocHolder clears in case of exception | |
620 | } | |
621 | ||
622 | template <class InputIterator> | |
623 | tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp) | |
624 | : AllocHolder(value_compare(comp)) | |
625 | { | |
626 | this->tree_construct(unique_insertion, first, last); | |
627 | //AllocHolder clears in case of exception | |
628 | } | |
629 | ||
630 | template <class InputIterator> | |
631 | tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a) | |
7c673cae | 632 | : AllocHolder(value_compare(comp), a) |
b32b8144 FG |
633 | { |
634 | this->tree_construct(unique_insertion, first, last); | |
635 | //AllocHolder clears in case of exception | |
636 | } | |
637 | ||
638 | //construct with ordered range | |
639 | template <class InputIterator> | |
640 | tree( ordered_range_t, InputIterator first, InputIterator last) | |
641 | : AllocHolder(value_compare(key_compare())) | |
642 | { | |
643 | this->tree_construct(ordered_range_t(), first, last); | |
644 | } | |
645 | ||
646 | template <class InputIterator> | |
647 | tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp) | |
648 | : AllocHolder(value_compare(comp)) | |
649 | { | |
650 | this->tree_construct(ordered_range_t(), first, last); | |
651 | } | |
652 | ||
653 | template <class InputIterator> | |
654 | tree( ordered_range_t, InputIterator first, InputIterator last | |
655 | , const key_compare& comp, const allocator_type& a) | |
656 | : AllocHolder(value_compare(comp), a) | |
657 | { | |
658 | this->tree_construct(ordered_range_t(), first, last); | |
659 | } | |
660 | ||
661 | private: | |
662 | ||
663 | template <class InputIterator> | |
664 | void tree_construct(bool unique_insertion, InputIterator first, InputIterator last) | |
7c673cae FG |
665 | { |
666 | //Use cend() as hint to achieve linear time for | |
667 | //ordered ranges as required by the standard | |
668 | //for the constructor | |
7c673cae | 669 | if(unique_insertion){ |
b32b8144 | 670 | const const_iterator end_it(this->cend()); |
7c673cae FG |
671 | for ( ; first != last; ++first){ |
672 | this->insert_unique_convertible(end_it, *first); | |
673 | } | |
674 | } | |
675 | else{ | |
b32b8144 | 676 | this->tree_construct_non_unique(first, last); |
7c673cae FG |
677 | } |
678 | } | |
679 | ||
680 | template <class InputIterator> | |
b32b8144 | 681 | void tree_construct_non_unique(InputIterator first, InputIterator last |
7c673cae | 682 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
11fdf7f2 | 683 | , typename dtl::enable_if_or |
7c673cae | 684 | < void |
11fdf7f2 TL |
685 | , dtl::is_same<alloc_version, version_1> |
686 | , dtl::is_input_iterator<InputIterator> | |
7c673cae FG |
687 | >::type * = 0 |
688 | #endif | |
689 | ) | |
7c673cae | 690 | { |
b32b8144 FG |
691 | //Use cend() as hint to achieve linear time for |
692 | //ordered ranges as required by the standard | |
693 | //for the constructor | |
694 | const const_iterator end_it(this->cend()); | |
695 | for ( ; first != last; ++first){ | |
696 | this->insert_equal_convertible(end_it, *first); | |
7c673cae FG |
697 | } |
698 | } | |
699 | ||
700 | template <class InputIterator> | |
b32b8144 FG |
701 | void tree_construct_non_unique(InputIterator first, InputIterator last |
702 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
11fdf7f2 | 703 | , typename dtl::disable_if_or |
7c673cae | 704 | < void |
11fdf7f2 TL |
705 | , dtl::is_same<alloc_version, version_1> |
706 | , dtl::is_input_iterator<InputIterator> | |
7c673cae | 707 | >::type * = 0 |
b32b8144 | 708 | #endif |
7c673cae | 709 | ) |
7c673cae | 710 | { |
b32b8144 FG |
711 | //Optimized allocation and construction |
712 | this->allocate_many_and_construct | |
713 | ( first, boost::container::iterator_distance(first, last) | |
714 | , insert_equal_end_hint_functor<Node, Icont>(this->icont())); | |
7c673cae FG |
715 | } |
716 | ||
717 | template <class InputIterator> | |
b32b8144 | 718 | void tree_construct( ordered_range_t, InputIterator first, InputIterator last |
7c673cae | 719 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
11fdf7f2 | 720 | , typename dtl::disable_if_or |
7c673cae | 721 | < void |
11fdf7f2 TL |
722 | , dtl::is_same<alloc_version, version_1> |
723 | , dtl::is_input_iterator<InputIterator> | |
7c673cae FG |
724 | >::type * = 0 |
725 | #endif | |
726 | ) | |
7c673cae FG |
727 | { |
728 | //Optimized allocation and construction | |
729 | this->allocate_many_and_construct | |
730 | ( first, boost::container::iterator_distance(first, last) | |
11fdf7f2 | 731 | , dtl::push_back_functor<Node, Icont>(this->icont())); |
b32b8144 FG |
732 | //AllocHolder clears in case of exception |
733 | } | |
734 | ||
735 | template <class InputIterator> | |
736 | void tree_construct( ordered_range_t, InputIterator first, InputIterator last | |
737 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
11fdf7f2 | 738 | , typename dtl::enable_if_or |
b32b8144 | 739 | < void |
11fdf7f2 TL |
740 | , dtl::is_same<alloc_version, version_1> |
741 | , dtl::is_input_iterator<InputIterator> | |
b32b8144 FG |
742 | >::type * = 0 |
743 | #endif | |
744 | ) | |
745 | { | |
746 | for ( ; first != last; ++first){ | |
747 | this->push_back_impl(*first); | |
748 | } | |
7c673cae FG |
749 | } |
750 | ||
b32b8144 FG |
751 | public: |
752 | ||
7c673cae | 753 | BOOST_CONTAINER_FORCEINLINE tree(const tree& x) |
b32b8144 | 754 | : AllocHolder(x, x.value_comp()) |
7c673cae FG |
755 | { |
756 | this->icont().clone_from | |
757 | (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); | |
758 | } | |
759 | ||
760 | BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x) | |
11fdf7f2 | 761 | BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) |
7c673cae FG |
762 | : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) |
763 | {} | |
764 | ||
765 | BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a) | |
766 | : AllocHolder(x.value_comp(), a) | |
767 | { | |
768 | this->icont().clone_from | |
769 | (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); | |
b32b8144 | 770 | //AllocHolder clears in case of exception |
7c673cae FG |
771 | } |
772 | ||
773 | tree(BOOST_RV_REF(tree) x, const allocator_type &a) | |
774 | : AllocHolder(x.value_comp(), a) | |
775 | { | |
776 | if(this->node_alloc() == x.node_alloc()){ | |
777 | this->icont().swap(x.icont()); | |
778 | } | |
779 | else{ | |
780 | this->icont().clone_from | |
781 | (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); | |
782 | } | |
b32b8144 | 783 | //AllocHolder clears in case of exception |
7c673cae FG |
784 | } |
785 | ||
786 | BOOST_CONTAINER_FORCEINLINE ~tree() | |
787 | {} //AllocHolder clears the tree | |
788 | ||
789 | tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) | |
790 | { | |
92f5a8d4 | 791 | if (BOOST_LIKELY(this != &x)) { |
7c673cae FG |
792 | NodeAlloc &this_alloc = this->get_stored_allocator(); |
793 | const NodeAlloc &x_alloc = x.get_stored_allocator(); | |
11fdf7f2 | 794 | dtl::bool_<allocator_traits<NodeAlloc>:: |
7c673cae FG |
795 | propagate_on_container_copy_assignment::value> flag; |
796 | if(flag && this_alloc != x_alloc){ | |
797 | this->clear(); | |
798 | } | |
799 | this->AllocHolder::copy_assign_alloc(x); | |
800 | //Transfer all the nodes to a temporary tree | |
801 | //If anything goes wrong, all the nodes will be destroyed | |
802 | //automatically | |
803 | Icont other_tree(::boost::move(this->icont())); | |
804 | ||
805 | //Now recreate the source tree reusing nodes stored by other_tree | |
806 | this->icont().clone_from | |
807 | (x.icont() | |
808 | , RecyclingCloner<AllocHolder, false>(*this, other_tree) | |
809 | , Destroyer(this->node_alloc())); | |
810 | ||
811 | //If there are remaining nodes, destroy them | |
812 | NodePtr p; | |
813 | while((p = other_tree.unlink_leftmost_without_rebalance())){ | |
814 | AllocHolder::destroy_node(p); | |
815 | } | |
816 | } | |
817 | return *this; | |
818 | } | |
819 | ||
820 | tree& operator=(BOOST_RV_REF(tree) x) | |
821 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || | |
822 | allocator_traits_type::is_always_equal::value) && | |
11fdf7f2 | 823 | boost::container::dtl::is_nothrow_move_assignable<Compare>::value) |
7c673cae | 824 | { |
92f5a8d4 TL |
825 | if (BOOST_LIKELY(this != &x)) { |
826 | NodeAlloc &this_alloc = this->node_alloc(); | |
827 | NodeAlloc &x_alloc = x.node_alloc(); | |
828 | const bool propagate_alloc = allocator_traits<NodeAlloc>:: | |
829 | propagate_on_container_move_assignment::value; | |
830 | const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; | |
831 | //Resources can be transferred if both allocators are | |
832 | //going to be equal after this function (either propagated or already equal) | |
833 | if(propagate_alloc || allocators_equal){ | |
834 | //Destroy | |
835 | this->clear(); | |
836 | //Move allocator if needed | |
837 | this->AllocHolder::move_assign_alloc(x); | |
838 | //Obtain resources | |
839 | this->icont() = boost::move(x.icont()); | |
840 | } | |
841 | //Else do a one by one move | |
842 | else{ | |
843 | //Transfer all the nodes to a temporary tree | |
844 | //If anything goes wrong, all the nodes will be destroyed | |
845 | //automatically | |
846 | Icont other_tree(::boost::move(this->icont())); | |
847 | ||
848 | //Now recreate the source tree reusing nodes stored by other_tree | |
849 | this->icont().clone_from | |
850 | (::boost::move(x.icont()) | |
851 | , RecyclingCloner<AllocHolder, true>(*this, other_tree) | |
852 | , Destroyer(this->node_alloc())); | |
853 | ||
854 | //If there are remaining nodes, destroy them | |
855 | NodePtr p; | |
856 | while((p = other_tree.unlink_leftmost_without_rebalance())){ | |
857 | AllocHolder::destroy_node(p); | |
858 | } | |
7c673cae FG |
859 | } |
860 | } | |
861 | return *this; | |
862 | } | |
863 | ||
864 | public: | |
865 | // accessors: | |
866 | BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const | |
867 | { return this->icont().value_comp().predicate(); } | |
868 | ||
869 | BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const | |
870 | { return this->icont().value_comp().predicate().key_comp(); } | |
871 | ||
872 | BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const | |
873 | { return allocator_type(this->node_alloc()); } | |
874 | ||
875 | BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const | |
876 | { return this->node_alloc(); } | |
877 | ||
878 | BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() | |
879 | { return this->node_alloc(); } | |
880 | ||
881 | BOOST_CONTAINER_FORCEINLINE iterator begin() | |
882 | { return iterator(this->icont().begin()); } | |
883 | ||
884 | BOOST_CONTAINER_FORCEINLINE const_iterator begin() const | |
885 | { return this->cbegin(); } | |
886 | ||
887 | BOOST_CONTAINER_FORCEINLINE iterator end() | |
888 | { return iterator(this->icont().end()); } | |
889 | ||
890 | BOOST_CONTAINER_FORCEINLINE const_iterator end() const | |
891 | { return this->cend(); } | |
892 | ||
893 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() | |
894 | { return reverse_iterator(end()); } | |
895 | ||
896 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const | |
897 | { return this->crbegin(); } | |
898 | ||
899 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() | |
900 | { return reverse_iterator(begin()); } | |
901 | ||
902 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const | |
903 | { return this->crend(); } | |
904 | ||
905 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
906 | //! | |
907 | //! <b>Throws</b>: Nothing. | |
908 | //! | |
909 | //! <b>Complexity</b>: Constant. | |
910 | BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const | |
911 | { return const_iterator(this->non_const_icont().begin()); } | |
912 | ||
913 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
914 | //! | |
915 | //! <b>Throws</b>: Nothing. | |
916 | //! | |
917 | //! <b>Complexity</b>: Constant. | |
918 | BOOST_CONTAINER_FORCEINLINE const_iterator cend() const | |
919 | { return const_iterator(this->non_const_icont().end()); } | |
920 | ||
921 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
922 | //! of the reversed container. | |
923 | //! | |
924 | //! <b>Throws</b>: Nothing. | |
925 | //! | |
926 | //! <b>Complexity</b>: Constant. | |
927 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const | |
928 | { return const_reverse_iterator(cend()); } | |
929 | ||
930 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
931 | //! of the reversed container. | |
932 | //! | |
933 | //! <b>Throws</b>: Nothing. | |
934 | //! | |
935 | //! <b>Complexity</b>: Constant. | |
936 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const | |
937 | { return const_reverse_iterator(cbegin()); } | |
938 | ||
939 | BOOST_CONTAINER_FORCEINLINE bool empty() const | |
940 | { return !this->size(); } | |
941 | ||
942 | BOOST_CONTAINER_FORCEINLINE size_type size() const | |
943 | { return this->icont().size(); } | |
944 | ||
945 | BOOST_CONTAINER_FORCEINLINE size_type max_size() const | |
946 | { return AllocHolder::max_size(); } | |
947 | ||
948 | BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x) | |
949 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value | |
11fdf7f2 | 950 | && boost::container::dtl::is_nothrow_swappable<Compare>::value ) |
7c673cae FG |
951 | { AllocHolder::swap(x); } |
952 | ||
953 | public: | |
954 | ||
955 | typedef typename Icont::insert_commit_data insert_commit_data; | |
956 | ||
957 | // insert/erase | |
958 | std::pair<iterator,bool> insert_unique_check | |
959 | (const key_type& key, insert_commit_data &data) | |
960 | { | |
961 | std::pair<iiterator, bool> ret = | |
962 | this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data); | |
963 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
964 | } | |
965 | ||
966 | std::pair<iterator,bool> insert_unique_check | |
967 | (const_iterator hint, const key_type& key, insert_commit_data &data) | |
968 | { | |
969 | BOOST_ASSERT((priv_is_linked)(hint)); | |
970 | std::pair<iiterator, bool> ret = | |
971 | this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data); | |
972 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
973 | } | |
974 | ||
975 | template<class MovableConvertible> | |
976 | iterator insert_unique_commit | |
977 | (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) | |
978 | { | |
979 | NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v)); | |
980 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
981 | iterator ret(this->icont().insert_unique_commit(*tmp, data)); | |
982 | destroy_deallocator.release(); | |
983 | return ret; | |
984 | } | |
985 | ||
986 | template<class MovableConvertible> | |
987 | std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v) | |
988 | { | |
989 | insert_commit_data data; | |
990 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 991 | this->insert_unique_check(key_of_value_t()(v), data); |
7c673cae FG |
992 | if(ret.second){ |
993 | ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); | |
994 | } | |
995 | return ret; | |
996 | } | |
997 | ||
998 | private: | |
999 | ||
1000 | template<class KeyConvertible, class M> | |
1001 | iiterator priv_insert_or_assign_commit | |
1002 | (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data) | |
1003 | { | |
1004 | NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj)); | |
1005 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1006 | iiterator ret(this->icont().insert_unique_commit(*tmp, data)); | |
1007 | destroy_deallocator.release(); | |
1008 | return ret; | |
1009 | } | |
1010 | ||
1011 | bool priv_is_linked(const_iterator const position) const | |
1012 | { | |
1013 | iiterator const cur(position.get()); | |
1014 | return cur == this->icont().end() || | |
1015 | cur == this->icont().root() || | |
1016 | iiterator(cur).go_parent().go_left() == cur || | |
1017 | iiterator(cur).go_parent().go_right() == cur; | |
1018 | } | |
1019 | ||
1020 | template<class MovableConvertible> | |
1021 | void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) | |
1022 | { | |
1023 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1024 | //push_back has no-throw guarantee so avoid any deallocator/destroyer | |
1025 | this->icont().push_back(*tmp); | |
1026 | } | |
1027 | ||
1028 | std::pair<iterator, bool> emplace_unique_impl(NodePtr p) | |
1029 | { | |
1030 | value_type &v = p->get_data(); | |
1031 | insert_commit_data data; | |
1032 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); | |
1033 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1034 | this->insert_unique_check(key_of_value_t()(v), data); |
7c673cae FG |
1035 | if(!ret.second){ |
1036 | return ret; | |
1037 | } | |
1038 | //No throw insertion part, release rollback | |
1039 | destroy_deallocator.release(); | |
1040 | return std::pair<iterator,bool> | |
1041 | ( iterator(this->icont().insert_unique_commit(*p, data)) | |
1042 | , true ); | |
1043 | } | |
1044 | ||
1045 | iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p) | |
1046 | { | |
1047 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1048 | value_type &v = p->get_data(); | |
1049 | insert_commit_data data; | |
1050 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1051 | this->insert_unique_check(hint, key_of_value_t()(v), data); |
7c673cae FG |
1052 | if(!ret.second){ |
1053 | Destroyer(this->node_alloc())(p); | |
1054 | return ret.first; | |
1055 | } | |
1056 | return iterator(this->icont().insert_unique_commit(*p, data)); | |
1057 | } | |
1058 | ||
1059 | public: | |
1060 | ||
1061 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1062 | ||
1063 | template <class... Args> | |
1064 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) | |
1065 | { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } | |
1066 | ||
1067 | template <class... Args> | |
1068 | BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
1069 | { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } | |
1070 | ||
1071 | template <class... Args> | |
1072 | iterator emplace_equal(BOOST_FWD_REF(Args)... args) | |
1073 | { | |
1074 | NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); | |
1075 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1076 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1077 | destroy_deallocator.release(); | |
1078 | return ret; | |
1079 | } | |
1080 | ||
1081 | template <class... Args> | |
1082 | iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
1083 | { | |
1084 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1085 | NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); | |
1086 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1087 | iterator ret(this->icont().insert_equal(hint.get(), *tmp)); | |
1088 | destroy_deallocator.release(); | |
1089 | return ret; | |
1090 | } | |
1091 | ||
1092 | template <class KeyType, class... Args> | |
1093 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace | |
1094 | (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) | |
1095 | { | |
1096 | insert_commit_data data; | |
1097 | const key_type & k = key; //Support emulated rvalue references | |
1098 | std::pair<iiterator, bool> ret = | |
1099 | hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data) | |
1100 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); | |
1101 | if(ret.second){ | |
1102 | ret.first = this->icont().insert_unique_commit | |
1103 | (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data); | |
1104 | } | |
1105 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
1106 | } | |
1107 | ||
1108 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1109 | ||
1110 | #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ | |
1111 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1112 | std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ | |
1113 | { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ | |
1114 | \ | |
1115 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1116 | iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1117 | { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ | |
1118 | \ | |
1119 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1120 | iterator emplace_equal(BOOST_MOVE_UREF##N)\ | |
1121 | {\ | |
1122 | NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ | |
1123 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ | |
1124 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\ | |
1125 | destroy_deallocator.release();\ | |
1126 | return ret;\ | |
1127 | }\ | |
1128 | \ | |
1129 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1130 | iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1131 | {\ | |
1132 | BOOST_ASSERT((priv_is_linked)(hint));\ | |
1133 | NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ | |
1134 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ | |
1135 | iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ | |
1136 | destroy_deallocator.release();\ | |
1137 | return ret;\ | |
1138 | }\ | |
1139 | \ | |
1140 | template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ | |
1141 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ | |
1142 | try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1143 | {\ | |
1144 | insert_commit_data data;\ | |
1145 | const key_type & k = key;\ | |
1146 | std::pair<iiterator, bool> ret =\ | |
1147 | hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\ | |
1148 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\ | |
1149 | if(ret.second){\ | |
1150 | ret.first = this->icont().insert_unique_commit\ | |
1151 | (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\ | |
1152 | }\ | |
1153 | return std::pair<iterator, bool>(iterator(ret.first), ret.second);\ | |
1154 | }\ | |
1155 | // | |
1156 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) | |
1157 | #undef BOOST_CONTAINER_TREE_EMPLACE_CODE | |
1158 | ||
1159 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1160 | ||
1161 | template<class MovableConvertible> | |
1162 | iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) | |
1163 | { | |
1164 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1165 | insert_commit_data data; | |
1166 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1167 | this->insert_unique_check(hint, key_of_value_t()(v), data); |
7c673cae FG |
1168 | if(!ret.second) |
1169 | return ret.first; | |
1170 | return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); | |
1171 | } | |
1172 | ||
1173 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator) | |
1174 | ||
1175 | template <class InputIterator> | |
1176 | void insert_unique(InputIterator first, InputIterator last) | |
1177 | { | |
1178 | for( ; first != last; ++first) | |
1179 | this->insert_unique(*first); | |
1180 | } | |
1181 | ||
1182 | iterator insert_equal(const value_type& v) | |
1183 | { | |
1184 | NodePtr tmp(AllocHolder::create_node(v)); | |
1185 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1186 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1187 | destroy_deallocator.release(); | |
1188 | return ret; | |
1189 | } | |
1190 | ||
1191 | template<class MovableConvertible> | |
1192 | iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v) | |
1193 | { | |
1194 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1195 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1196 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1197 | destroy_deallocator.release(); | |
1198 | return ret; | |
1199 | } | |
1200 | ||
1201 | template<class MovableConvertible> | |
1202 | iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) | |
1203 | { | |
1204 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1205 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1206 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1207 | iterator ret(this->icont().insert_equal(hint.get(), *tmp)); | |
1208 | destroy_deallocator.release(); | |
1209 | return ret; | |
1210 | } | |
1211 | ||
1212 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator) | |
1213 | ||
1214 | template <class InputIterator> | |
1215 | void insert_equal(InputIterator first, InputIterator last) | |
1216 | { | |
1217 | for( ; first != last; ++first) | |
1218 | this->insert_equal(*first); | |
1219 | } | |
1220 | ||
1221 | template<class KeyType, class M> | |
1222 | std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) | |
1223 | { | |
1224 | insert_commit_data data; | |
1225 | const key_type & k = key; //Support emulated rvalue references | |
1226 | std::pair<iiterator, bool> ret = | |
1227 | hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data) | |
1228 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); | |
1229 | if(ret.second){ | |
1230 | ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data); | |
1231 | } | |
1232 | else{ | |
1233 | ret.first->get_data().second = boost::forward<M>(obj); | |
1234 | } | |
1235 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
1236 | } | |
1237 | ||
1238 | iterator erase(const_iterator position) | |
1239 | { | |
1240 | BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); | |
1241 | return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); | |
1242 | } | |
1243 | ||
1244 | BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k) | |
1245 | { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); } | |
1246 | ||
1247 | iterator erase(const_iterator first, const_iterator last) | |
1248 | { | |
1249 | BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); | |
1250 | BOOST_ASSERT(first == last || (priv_is_linked)(last)); | |
1251 | return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); | |
1252 | } | |
1253 | ||
1254 | node_type extract(const key_type& k) | |
1255 | { | |
1256 | iterator const it = this->find(k); | |
1257 | if(this->end() != it){ | |
1258 | return this->extract(it); | |
1259 | } | |
1260 | return node_type(); | |
1261 | } | |
1262 | ||
1263 | node_type extract(const_iterator position) | |
1264 | { | |
1265 | BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); | |
1266 | iiterator const iit(position.get()); | |
1267 | this->icont().erase(iit); | |
1268 | return node_type(iit.operator->(), this->node_alloc()); | |
1269 | } | |
1270 | ||
1271 | insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1272 | { | |
1273 | return this->insert_unique_node(this->end(), boost::move(nh)); | |
1274 | } | |
1275 | ||
1276 | insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1277 | { | |
1278 | insert_return_type irt; //inserted == false, node.empty() | |
1279 | if(!nh.empty()){ | |
1280 | insert_commit_data data; | |
1281 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1282 | this->insert_unique_check(hint, key_of_value_t()(nh.value()), data); |
7c673cae FG |
1283 | if(ret.second){ |
1284 | irt.inserted = true; | |
b32b8144 | 1285 | irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data)); |
7c673cae FG |
1286 | nh.release(); |
1287 | } | |
1288 | else{ | |
1289 | irt.position = ret.first; | |
1290 | irt.node = boost::move(nh); | |
1291 | } | |
1292 | } | |
1293 | else{ | |
1294 | irt.position = this->end(); | |
1295 | } | |
1296 | return BOOST_MOVE_RET(insert_return_type, irt); | |
1297 | } | |
1298 | ||
1299 | iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1300 | { | |
1301 | if(nh.empty()){ | |
1302 | return this->end(); | |
1303 | } | |
1304 | else{ | |
1305 | NodePtr const p(nh.release()); | |
1306 | return iterator(this->icont().insert_equal(*p)); | |
1307 | } | |
1308 | } | |
1309 | ||
1310 | iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1311 | { | |
1312 | if(nh.empty()){ | |
1313 | return this->end(); | |
1314 | } | |
1315 | else{ | |
1316 | NodePtr const p(nh.release()); | |
1317 | return iterator(this->icont().insert_equal(hint.get(), *p)); | |
1318 | } | |
1319 | } | |
1320 | ||
1321 | template<class C2> | |
1322 | BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source) | |
1323 | { return this->icont().merge_unique(source.icont()); } | |
1324 | ||
1325 | template<class C2> | |
1326 | BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source) | |
1327 | { return this->icont().merge_equal(source.icont()); } | |
1328 | BOOST_CONTAINER_FORCEINLINE void clear() | |
1329 | { AllocHolder::clear(alloc_version()); } | |
1330 | ||
1331 | // search operations. Const and non-const overloads even if no iterator is returned | |
1332 | // so splay implementations can to their rebalancing when searching in non-const versions | |
1333 | BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k) | |
1334 | { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } | |
1335 | ||
1336 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const | |
1337 | { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } | |
1338 | ||
92f5a8d4 TL |
1339 | template <class K> |
1340 | BOOST_CONTAINER_FORCEINLINE | |
1341 | typename dtl::enable_if_transparent<key_compare, K, iterator>::type | |
1342 | find(const K& k) | |
1343 | { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } | |
1344 | ||
1345 | template <class K> | |
1346 | BOOST_CONTAINER_FORCEINLINE | |
1347 | typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type | |
1348 | find(const K& k) const | |
1349 | { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } | |
1350 | ||
7c673cae FG |
1351 | BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const |
1352 | { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } | |
1353 | ||
92f5a8d4 TL |
1354 | template <class K> |
1355 | BOOST_CONTAINER_FORCEINLINE | |
1356 | typename dtl::enable_if_transparent<key_compare, K, size_type>::type | |
1357 | count(const K& k) const | |
1358 | { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } | |
1359 | ||
1360 | BOOST_CONTAINER_FORCEINLINE bool contains(const key_type& x) const | |
1361 | { return this->find(x) != this->cend(); } | |
1362 | ||
1363 | template<typename K> | |
1364 | BOOST_CONTAINER_FORCEINLINE | |
1365 | typename dtl::enable_if_transparent<key_compare, K, bool>::type | |
1366 | contains(const K& x) const | |
1367 | { return this->find(x) != this->cend(); } | |
1368 | ||
7c673cae FG |
1369 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k) |
1370 | { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1371 | ||
1372 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const | |
1373 | { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1374 | ||
92f5a8d4 TL |
1375 | template <class K> |
1376 | BOOST_CONTAINER_FORCEINLINE | |
1377 | typename dtl::enable_if_transparent<key_compare, K, iterator>::type | |
1378 | lower_bound(const K& k) | |
1379 | { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1380 | ||
1381 | template <class K> | |
1382 | BOOST_CONTAINER_FORCEINLINE | |
1383 | typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type | |
1384 | lower_bound(const K& k) const | |
1385 | { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1386 | ||
7c673cae FG |
1387 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k) |
1388 | { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1389 | ||
1390 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const | |
1391 | { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1392 | ||
92f5a8d4 TL |
1393 | template <class K> |
1394 | BOOST_CONTAINER_FORCEINLINE | |
1395 | typename dtl::enable_if_transparent<key_compare, K, iterator>::type | |
1396 | upper_bound(const K& k) | |
1397 | { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1398 | ||
1399 | template <class K> | |
1400 | BOOST_CONTAINER_FORCEINLINE | |
1401 | typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type | |
1402 | upper_bound(const K& k) const | |
1403 | { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1404 | ||
7c673cae FG |
1405 | std::pair<iterator,iterator> equal_range(const key_type& k) |
1406 | { | |
1407 | std::pair<iiterator, iiterator> ret = | |
1408 | this->icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1409 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1410 | } | |
1411 | ||
1412 | std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const | |
1413 | { | |
1414 | std::pair<iiterator, iiterator> ret = | |
1415 | this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1416 | return std::pair<const_iterator,const_iterator> | |
1417 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1418 | } | |
1419 | ||
92f5a8d4 TL |
1420 | template <class K> |
1421 | BOOST_CONTAINER_FORCEINLINE | |
1422 | typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type | |
1423 | equal_range(const K& k) | |
1424 | { | |
1425 | std::pair<iiterator, iiterator> ret = | |
1426 | this->icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1427 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1428 | } | |
1429 | ||
1430 | template <class K> | |
1431 | BOOST_CONTAINER_FORCEINLINE | |
1432 | typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type | |
1433 | equal_range(const K& k) const | |
1434 | { | |
1435 | std::pair<iiterator, iiterator> ret = | |
1436 | this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1437 | return std::pair<const_iterator,const_iterator> | |
1438 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1439 | } | |
1440 | ||
7c673cae FG |
1441 | std::pair<iterator,iterator> lower_bound_range(const key_type& k) |
1442 | { | |
1443 | std::pair<iiterator, iiterator> ret = | |
1444 | this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1445 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1446 | } | |
1447 | ||
1448 | std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const | |
1449 | { | |
1450 | std::pair<iiterator, iiterator> ret = | |
1451 | this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1452 | return std::pair<const_iterator,const_iterator> | |
1453 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1454 | } | |
1455 | ||
92f5a8d4 TL |
1456 | template <class K> |
1457 | BOOST_CONTAINER_FORCEINLINE | |
1458 | typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type | |
1459 | lower_bound_range(const K& k) | |
1460 | { | |
1461 | std::pair<iiterator, iiterator> ret = | |
1462 | this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1463 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1464 | } | |
1465 | ||
1466 | template <class K> | |
1467 | BOOST_CONTAINER_FORCEINLINE | |
1468 | typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type | |
1469 | lower_bound_range(const K& k) const | |
1470 | { | |
1471 | std::pair<iiterator, iiterator> ret = | |
1472 | this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1473 | return std::pair<const_iterator,const_iterator> | |
1474 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1475 | } | |
1476 | ||
7c673cae FG |
1477 | BOOST_CONTAINER_FORCEINLINE void rebalance() |
1478 | { intrusive_tree_proxy_t::rebalance(this->icont()); } | |
1479 | ||
1480 | BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y) | |
1481 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
1482 | ||
1483 | BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y) | |
1484 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
1485 | ||
1486 | BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y) | |
1487 | { return !(x == y); } | |
1488 | ||
1489 | BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y) | |
1490 | { return y < x; } | |
1491 | ||
1492 | BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y) | |
1493 | { return !(y < x); } | |
1494 | ||
1495 | BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y) | |
1496 | { return !(x < y); } | |
1497 | ||
1498 | BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y) | |
92f5a8d4 TL |
1499 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value |
1500 | && boost::container::dtl::is_nothrow_swappable<Compare>::value ) | |
7c673cae FG |
1501 | { x.swap(y); } |
1502 | }; | |
1503 | ||
11fdf7f2 | 1504 | } //namespace dtl { |
7c673cae FG |
1505 | } //namespace container { |
1506 | ||
1507 | template <class T> | |
1508 | struct has_trivial_destructor_after_move; | |
1509 | ||
1510 | //!has_trivial_destructor_after_move<> == true_type | |
1511 | //!specialization for optimizations | |
1512 | template <class T, class KeyOfValue, class Compare, class Allocator, class Options> | |
1513 | struct has_trivial_destructor_after_move | |
1514 | < | |
11fdf7f2 | 1515 | ::boost::container::dtl::tree |
7c673cae FG |
1516 | <T, KeyOfValue, Compare, Allocator, Options> |
1517 | > | |
1518 | { | |
92f5a8d4 TL |
1519 | typedef typename ::boost::container::dtl::tree<T, KeyOfValue, Compare, Allocator, Options>::allocator_type allocator_type; |
1520 | typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer; | |
1521 | static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value && | |
7c673cae FG |
1522 | ::boost::has_trivial_destructor_after_move<pointer>::value && |
1523 | ::boost::has_trivial_destructor_after_move<Compare>::value; | |
1524 | }; | |
1525 | ||
1526 | } //namespace boost { | |
1527 | ||
1528 | #include <boost/container/detail/config_end.hpp> | |
1529 | ||
1530 | #endif //BOOST_CONTAINER_TREE_HPP |