]>
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 | ||
20effc67 TL |
390 | BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, node_t &other, bool_<true>) |
391 | { p->do_move_assign(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 | 395 | |
20effc67 TL |
396 | node_ptr_type operator() |
397 | (typename dtl::if_c<DoMove, node_t &, const node_t&>::type other) const | |
7c673cae FG |
398 | { |
399 | if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ | |
400 | //First recycle a node (this can't throw) | |
401 | BOOST_TRY{ | |
402 | //This can throw | |
403 | this->do_assign(p, other, bool_<DoMove>()); | |
404 | return p; | |
405 | } | |
406 | BOOST_CATCH(...){ | |
407 | //If there is an exception destroy the whole source | |
408 | m_holder.destroy_node(p); | |
409 | while((p = m_icont.unlink_leftmost_without_rebalance())){ | |
410 | m_holder.destroy_node(p); | |
411 | } | |
412 | BOOST_RETHROW | |
413 | } | |
414 | BOOST_CATCH_END | |
415 | } | |
416 | else{ | |
20effc67 | 417 | return m_holder.create_node(boost::move(other.get_real_data())); |
7c673cae FG |
418 | } |
419 | } | |
420 | ||
421 | AllocHolder &m_holder; | |
422 | intrusive_container &m_icont; | |
423 | }; | |
424 | ||
92f5a8d4 | 425 | |
7c673cae FG |
426 | template<class KeyCompare, class KeyOfValue> |
427 | struct key_node_compare | |
428 | : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> | |
429 | { | |
430 | BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp) | |
431 | : base_t(comp) | |
432 | {} | |
433 | ||
434 | typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t; | |
435 | typedef KeyCompare key_compare; | |
436 | typedef KeyOfValue key_of_value; | |
437 | typedef typename KeyOfValue::type key_type; | |
438 | ||
92f5a8d4 TL |
439 | |
440 | template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
441 | BOOST_CONTAINER_FORCEINLINE static const key_type & | |
442 | key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n) | |
443 | { | |
444 | return key_of_value()(n.get_data()); | |
445 | } | |
446 | ||
447 | template <class T> | |
448 | BOOST_CONTAINER_FORCEINLINE static const T & | |
449 | key_from(const T &t) | |
450 | { | |
451 | return t; | |
452 | } | |
453 | ||
7c673cae FG |
454 | BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const |
455 | { return static_cast<const key_compare &>(*this); } | |
456 | ||
457 | BOOST_CONTAINER_FORCEINLINE key_compare &key_comp() | |
458 | { return static_cast<key_compare &>(*this); } | |
459 | ||
460 | BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const | |
461 | { return this->key_comp()(key1, key2); } | |
462 | ||
463 | template<class U> | |
464 | BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const | |
92f5a8d4 | 465 | { return this->key_comp()(key1, this->key_from(nonkey2)); } |
7c673cae FG |
466 | |
467 | template<class U> | |
468 | BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const | |
92f5a8d4 | 469 | { return this->key_comp()(this->key_from(nonkey1), key2); } |
7c673cae FG |
470 | |
471 | template<class U, class V> | |
472 | BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const | |
92f5a8d4 | 473 | { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); } |
7c673cae FG |
474 | }; |
475 | ||
11fdf7f2 TL |
476 | template<class Options> |
477 | struct get_tree_opt | |
478 | { | |
479 | typedef Options type; | |
480 | }; | |
481 | ||
482 | template<> | |
483 | struct get_tree_opt<void> | |
484 | { | |
485 | typedef tree_assoc_defaults type; | |
486 | }; | |
487 | ||
92f5a8d4 TL |
488 | template<class, class KeyOfValue> |
489 | struct real_key_of_value | |
490 | { | |
491 | typedef KeyOfValue type; | |
492 | }; | |
493 | ||
494 | template<class T> | |
495 | struct real_key_of_value<T, void> | |
496 | { | |
497 | typedef dtl::identity<T> type; | |
498 | }; | |
499 | ||
500 | template<class T1, class T2> | |
501 | struct real_key_of_value<std::pair<T1, T2>, int> | |
502 | { | |
503 | typedef dtl::select1st<T1> type; | |
504 | }; | |
505 | ||
506 | template<class T1, class T2> | |
507 | struct real_key_of_value<boost::container::pair<T1, T2>, int> | |
508 | { | |
509 | typedef dtl::select1st<T1> type; | |
510 | }; | |
511 | ||
11fdf7f2 | 512 | template <class T, class KeyOfValue, class Compare, class Allocator, class Options> |
7c673cae | 513 | class tree |
11fdf7f2 | 514 | : public dtl::node_alloc_holder |
92f5a8d4 | 515 | < typename real_allocator<T, Allocator>::type |
11fdf7f2 | 516 | , typename dtl::intrusive_tree_type |
92f5a8d4 TL |
517 | < typename real_allocator<T, Allocator>::type |
518 | , tree_value_compare | |
519 | <typename allocator_traits<typename real_allocator<T, Allocator>::type>::pointer, Compare, typename real_key_of_value<T, KeyOfValue>::type> | |
11fdf7f2 TL |
520 | , get_tree_opt<Options>::type::tree_type |
521 | , get_tree_opt<Options>::type::optimize_size | |
522 | >::type | |
7c673cae FG |
523 | > |
524 | { | |
92f5a8d4 TL |
525 | typedef tree < T, KeyOfValue |
526 | , Compare, Allocator, Options> ThisType; | |
527 | public: | |
528 | typedef typename real_allocator<T, Allocator>::type allocator_type; | |
529 | ||
530 | private: | |
531 | typedef allocator_traits<allocator_type> allocator_traits_t; | |
532 | typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t; | |
7c673cae | 533 | typedef tree_value_compare |
92f5a8d4 TL |
534 | < typename allocator_traits_t::pointer |
535 | , Compare | |
536 | , key_of_value_t> ValComp; | |
11fdf7f2 TL |
537 | typedef typename get_tree_opt<Options>::type options_type; |
538 | typedef typename dtl::intrusive_tree_type | |
92f5a8d4 | 539 | < allocator_type, ValComp |
11fdf7f2 TL |
540 | , options_type::tree_type |
541 | , options_type::optimize_size | |
542 | >::type Icont; | |
543 | typedef dtl::node_alloc_holder | |
92f5a8d4 | 544 | <allocator_type, Icont> AllocHolder; |
7c673cae | 545 | typedef typename AllocHolder::NodePtr NodePtr; |
92f5a8d4 | 546 | |
7c673cae FG |
547 | typedef typename AllocHolder::NodeAlloc NodeAlloc; |
548 | typedef boost::container:: | |
549 | allocator_traits<NodeAlloc> allocator_traits_type; | |
550 | typedef typename AllocHolder::ValAlloc ValAlloc; | |
551 | typedef typename AllocHolder::Node Node; | |
552 | typedef typename Icont::iterator iiterator; | |
553 | typedef typename Icont::const_iterator iconst_iterator; | |
11fdf7f2 | 554 | typedef dtl::allocator_destroyer<NodeAlloc> Destroyer; |
7c673cae | 555 | typedef typename AllocHolder::alloc_version alloc_version; |
11fdf7f2 | 556 | typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t; |
7c673cae FG |
557 | |
558 | BOOST_COPYABLE_AND_MOVABLE(tree) | |
559 | ||
560 | public: | |
561 | ||
92f5a8d4 TL |
562 | typedef typename key_of_value_t::type key_type; |
563 | typedef T value_type; | |
564 | typedef Compare key_compare; | |
565 | typedef ValComp value_compare; | |
7c673cae | 566 | typedef typename boost::container:: |
92f5a8d4 | 567 | allocator_traits<allocator_type>::pointer pointer; |
7c673cae | 568 | typedef typename boost::container:: |
92f5a8d4 | 569 | allocator_traits<allocator_type>::const_pointer const_pointer; |
7c673cae | 570 | typedef typename boost::container:: |
92f5a8d4 | 571 | allocator_traits<allocator_type>::reference reference; |
7c673cae | 572 | typedef typename boost::container:: |
92f5a8d4 | 573 | allocator_traits<allocator_type>::const_reference const_reference; |
7c673cae | 574 | typedef typename boost::container:: |
92f5a8d4 | 575 | allocator_traits<allocator_type>::size_type size_type; |
7c673cae | 576 | typedef typename boost::container:: |
92f5a8d4 | 577 | allocator_traits<allocator_type>::difference_type difference_type; |
11fdf7f2 | 578 | typedef dtl::iterator_from_iiterator |
92f5a8d4 | 579 | <iiterator, false> iterator; |
11fdf7f2 | 580 | typedef dtl::iterator_from_iiterator |
92f5a8d4 | 581 | <iiterator, true > const_iterator; |
7c673cae | 582 | typedef boost::container::reverse_iterator |
92f5a8d4 | 583 | <iterator> reverse_iterator; |
7c673cae | 584 | typedef boost::container::reverse_iterator |
92f5a8d4 | 585 | <const_iterator> const_reverse_iterator; |
7c673cae | 586 | typedef node_handle |
92f5a8d4 | 587 | < NodeAlloc, void> node_type; |
7c673cae | 588 | typedef insert_return_type_base |
92f5a8d4 | 589 | <iterator, node_type> insert_return_type; |
7c673cae | 590 | |
92f5a8d4 | 591 | typedef NodeAlloc stored_allocator_type; |
7c673cae FG |
592 | |
593 | private: | |
594 | ||
92f5a8d4 | 595 | typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare; |
7c673cae FG |
596 | |
597 | public: | |
598 | ||
599 | BOOST_CONTAINER_FORCEINLINE tree() | |
600 | : AllocHolder() | |
601 | {} | |
602 | ||
b32b8144 FG |
603 | BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp) |
604 | : AllocHolder(ValComp(comp)) | |
605 | {} | |
606 | ||
607 | BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a) | |
7c673cae FG |
608 | : AllocHolder(ValComp(comp), a) |
609 | {} | |
610 | ||
611 | BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a) | |
612 | : AllocHolder(a) | |
613 | {} | |
614 | ||
615 | template <class InputIterator> | |
b32b8144 FG |
616 | tree(bool unique_insertion, InputIterator first, InputIterator last) |
617 | : AllocHolder(value_compare(key_compare())) | |
618 | { | |
619 | this->tree_construct(unique_insertion, first, last); | |
620 | //AllocHolder clears in case of exception | |
621 | } | |
622 | ||
623 | template <class InputIterator> | |
624 | tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp) | |
625 | : AllocHolder(value_compare(comp)) | |
626 | { | |
627 | this->tree_construct(unique_insertion, first, last); | |
628 | //AllocHolder clears in case of exception | |
629 | } | |
630 | ||
631 | template <class InputIterator> | |
632 | tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a) | |
7c673cae | 633 | : AllocHolder(value_compare(comp), a) |
b32b8144 FG |
634 | { |
635 | this->tree_construct(unique_insertion, first, last); | |
636 | //AllocHolder clears in case of exception | |
637 | } | |
638 | ||
639 | //construct with ordered range | |
640 | template <class InputIterator> | |
641 | tree( ordered_range_t, InputIterator first, InputIterator last) | |
642 | : AllocHolder(value_compare(key_compare())) | |
643 | { | |
644 | this->tree_construct(ordered_range_t(), first, last); | |
645 | } | |
646 | ||
647 | template <class InputIterator> | |
648 | tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp) | |
649 | : AllocHolder(value_compare(comp)) | |
650 | { | |
651 | this->tree_construct(ordered_range_t(), first, last); | |
652 | } | |
653 | ||
654 | template <class InputIterator> | |
655 | tree( ordered_range_t, InputIterator first, InputIterator last | |
656 | , const key_compare& comp, const allocator_type& a) | |
657 | : AllocHolder(value_compare(comp), a) | |
658 | { | |
659 | this->tree_construct(ordered_range_t(), first, last); | |
660 | } | |
661 | ||
662 | private: | |
663 | ||
664 | template <class InputIterator> | |
665 | void tree_construct(bool unique_insertion, InputIterator first, InputIterator last) | |
7c673cae FG |
666 | { |
667 | //Use cend() as hint to achieve linear time for | |
668 | //ordered ranges as required by the standard | |
669 | //for the constructor | |
7c673cae | 670 | if(unique_insertion){ |
b32b8144 | 671 | const const_iterator end_it(this->cend()); |
7c673cae FG |
672 | for ( ; first != last; ++first){ |
673 | this->insert_unique_convertible(end_it, *first); | |
674 | } | |
675 | } | |
676 | else{ | |
b32b8144 | 677 | this->tree_construct_non_unique(first, last); |
7c673cae FG |
678 | } |
679 | } | |
680 | ||
681 | template <class InputIterator> | |
b32b8144 | 682 | void tree_construct_non_unique(InputIterator first, InputIterator last |
7c673cae | 683 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
11fdf7f2 | 684 | , typename dtl::enable_if_or |
7c673cae | 685 | < void |
11fdf7f2 TL |
686 | , dtl::is_same<alloc_version, version_1> |
687 | , dtl::is_input_iterator<InputIterator> | |
7c673cae FG |
688 | >::type * = 0 |
689 | #endif | |
690 | ) | |
7c673cae | 691 | { |
b32b8144 FG |
692 | //Use cend() as hint to achieve linear time for |
693 | //ordered ranges as required by the standard | |
694 | //for the constructor | |
695 | const const_iterator end_it(this->cend()); | |
696 | for ( ; first != last; ++first){ | |
697 | this->insert_equal_convertible(end_it, *first); | |
7c673cae FG |
698 | } |
699 | } | |
700 | ||
701 | template <class InputIterator> | |
b32b8144 FG |
702 | void tree_construct_non_unique(InputIterator first, InputIterator last |
703 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
11fdf7f2 | 704 | , typename dtl::disable_if_or |
7c673cae | 705 | < void |
11fdf7f2 TL |
706 | , dtl::is_same<alloc_version, version_1> |
707 | , dtl::is_input_iterator<InputIterator> | |
7c673cae | 708 | >::type * = 0 |
b32b8144 | 709 | #endif |
7c673cae | 710 | ) |
7c673cae | 711 | { |
b32b8144 FG |
712 | //Optimized allocation and construction |
713 | this->allocate_many_and_construct | |
714 | ( first, boost::container::iterator_distance(first, last) | |
715 | , insert_equal_end_hint_functor<Node, Icont>(this->icont())); | |
7c673cae FG |
716 | } |
717 | ||
718 | template <class InputIterator> | |
b32b8144 | 719 | void tree_construct( ordered_range_t, InputIterator first, InputIterator last |
7c673cae | 720 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
11fdf7f2 | 721 | , typename dtl::disable_if_or |
7c673cae | 722 | < void |
11fdf7f2 TL |
723 | , dtl::is_same<alloc_version, version_1> |
724 | , dtl::is_input_iterator<InputIterator> | |
7c673cae FG |
725 | >::type * = 0 |
726 | #endif | |
727 | ) | |
7c673cae FG |
728 | { |
729 | //Optimized allocation and construction | |
730 | this->allocate_many_and_construct | |
731 | ( first, boost::container::iterator_distance(first, last) | |
11fdf7f2 | 732 | , dtl::push_back_functor<Node, Icont>(this->icont())); |
b32b8144 FG |
733 | //AllocHolder clears in case of exception |
734 | } | |
735 | ||
736 | template <class InputIterator> | |
737 | void tree_construct( ordered_range_t, InputIterator first, InputIterator last | |
738 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
11fdf7f2 | 739 | , typename dtl::enable_if_or |
b32b8144 | 740 | < void |
11fdf7f2 TL |
741 | , dtl::is_same<alloc_version, version_1> |
742 | , dtl::is_input_iterator<InputIterator> | |
b32b8144 FG |
743 | >::type * = 0 |
744 | #endif | |
745 | ) | |
746 | { | |
747 | for ( ; first != last; ++first){ | |
748 | this->push_back_impl(*first); | |
749 | } | |
7c673cae FG |
750 | } |
751 | ||
b32b8144 FG |
752 | public: |
753 | ||
7c673cae | 754 | BOOST_CONTAINER_FORCEINLINE tree(const tree& x) |
b32b8144 | 755 | : AllocHolder(x, x.value_comp()) |
7c673cae FG |
756 | { |
757 | this->icont().clone_from | |
758 | (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); | |
759 | } | |
760 | ||
761 | BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x) | |
11fdf7f2 | 762 | BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) |
7c673cae FG |
763 | : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) |
764 | {} | |
765 | ||
766 | BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a) | |
767 | : AllocHolder(x.value_comp(), a) | |
768 | { | |
769 | this->icont().clone_from | |
770 | (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); | |
b32b8144 | 771 | //AllocHolder clears in case of exception |
7c673cae FG |
772 | } |
773 | ||
774 | tree(BOOST_RV_REF(tree) x, const allocator_type &a) | |
775 | : AllocHolder(x.value_comp(), a) | |
776 | { | |
777 | if(this->node_alloc() == x.node_alloc()){ | |
778 | this->icont().swap(x.icont()); | |
779 | } | |
780 | else{ | |
781 | this->icont().clone_from | |
782 | (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); | |
783 | } | |
b32b8144 | 784 | //AllocHolder clears in case of exception |
7c673cae FG |
785 | } |
786 | ||
787 | BOOST_CONTAINER_FORCEINLINE ~tree() | |
788 | {} //AllocHolder clears the tree | |
789 | ||
790 | tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) | |
791 | { | |
92f5a8d4 | 792 | if (BOOST_LIKELY(this != &x)) { |
7c673cae FG |
793 | NodeAlloc &this_alloc = this->get_stored_allocator(); |
794 | const NodeAlloc &x_alloc = x.get_stored_allocator(); | |
11fdf7f2 | 795 | dtl::bool_<allocator_traits<NodeAlloc>:: |
7c673cae FG |
796 | propagate_on_container_copy_assignment::value> flag; |
797 | if(flag && this_alloc != x_alloc){ | |
798 | this->clear(); | |
799 | } | |
800 | this->AllocHolder::copy_assign_alloc(x); | |
801 | //Transfer all the nodes to a temporary tree | |
802 | //If anything goes wrong, all the nodes will be destroyed | |
803 | //automatically | |
804 | Icont other_tree(::boost::move(this->icont())); | |
805 | ||
806 | //Now recreate the source tree reusing nodes stored by other_tree | |
807 | this->icont().clone_from | |
808 | (x.icont() | |
809 | , RecyclingCloner<AllocHolder, false>(*this, other_tree) | |
810 | , Destroyer(this->node_alloc())); | |
811 | ||
812 | //If there are remaining nodes, destroy them | |
813 | NodePtr p; | |
814 | while((p = other_tree.unlink_leftmost_without_rebalance())){ | |
815 | AllocHolder::destroy_node(p); | |
816 | } | |
817 | } | |
818 | return *this; | |
819 | } | |
820 | ||
821 | tree& operator=(BOOST_RV_REF(tree) x) | |
822 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || | |
823 | allocator_traits_type::is_always_equal::value) && | |
11fdf7f2 | 824 | boost::container::dtl::is_nothrow_move_assignable<Compare>::value) |
7c673cae | 825 | { |
92f5a8d4 TL |
826 | if (BOOST_LIKELY(this != &x)) { |
827 | NodeAlloc &this_alloc = this->node_alloc(); | |
828 | NodeAlloc &x_alloc = x.node_alloc(); | |
829 | const bool propagate_alloc = allocator_traits<NodeAlloc>:: | |
830 | propagate_on_container_move_assignment::value; | |
831 | const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; | |
832 | //Resources can be transferred if both allocators are | |
833 | //going to be equal after this function (either propagated or already equal) | |
834 | if(propagate_alloc || allocators_equal){ | |
835 | //Destroy | |
836 | this->clear(); | |
837 | //Move allocator if needed | |
838 | this->AllocHolder::move_assign_alloc(x); | |
839 | //Obtain resources | |
840 | this->icont() = boost::move(x.icont()); | |
841 | } | |
842 | //Else do a one by one move | |
843 | else{ | |
844 | //Transfer all the nodes to a temporary tree | |
845 | //If anything goes wrong, all the nodes will be destroyed | |
846 | //automatically | |
847 | Icont other_tree(::boost::move(this->icont())); | |
848 | ||
849 | //Now recreate the source tree reusing nodes stored by other_tree | |
850 | this->icont().clone_from | |
851 | (::boost::move(x.icont()) | |
852 | , RecyclingCloner<AllocHolder, true>(*this, other_tree) | |
853 | , Destroyer(this->node_alloc())); | |
854 | ||
855 | //If there are remaining nodes, destroy them | |
856 | NodePtr p; | |
857 | while((p = other_tree.unlink_leftmost_without_rebalance())){ | |
858 | AllocHolder::destroy_node(p); | |
859 | } | |
7c673cae FG |
860 | } |
861 | } | |
862 | return *this; | |
863 | } | |
864 | ||
865 | public: | |
866 | // accessors: | |
867 | BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const | |
868 | { return this->icont().value_comp().predicate(); } | |
869 | ||
870 | BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const | |
871 | { return this->icont().value_comp().predicate().key_comp(); } | |
872 | ||
873 | BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const | |
874 | { return allocator_type(this->node_alloc()); } | |
875 | ||
876 | BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const | |
877 | { return this->node_alloc(); } | |
878 | ||
879 | BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() | |
880 | { return this->node_alloc(); } | |
881 | ||
882 | BOOST_CONTAINER_FORCEINLINE iterator begin() | |
883 | { return iterator(this->icont().begin()); } | |
884 | ||
885 | BOOST_CONTAINER_FORCEINLINE const_iterator begin() const | |
886 | { return this->cbegin(); } | |
887 | ||
888 | BOOST_CONTAINER_FORCEINLINE iterator end() | |
889 | { return iterator(this->icont().end()); } | |
890 | ||
891 | BOOST_CONTAINER_FORCEINLINE const_iterator end() const | |
892 | { return this->cend(); } | |
893 | ||
894 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() | |
895 | { return reverse_iterator(end()); } | |
896 | ||
897 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const | |
898 | { return this->crbegin(); } | |
899 | ||
900 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() | |
901 | { return reverse_iterator(begin()); } | |
902 | ||
903 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const | |
904 | { return this->crend(); } | |
905 | ||
906 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
907 | //! | |
908 | //! <b>Throws</b>: Nothing. | |
909 | //! | |
910 | //! <b>Complexity</b>: Constant. | |
911 | BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const | |
912 | { return const_iterator(this->non_const_icont().begin()); } | |
913 | ||
914 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
915 | //! | |
916 | //! <b>Throws</b>: Nothing. | |
917 | //! | |
918 | //! <b>Complexity</b>: Constant. | |
919 | BOOST_CONTAINER_FORCEINLINE const_iterator cend() const | |
920 | { return const_iterator(this->non_const_icont().end()); } | |
921 | ||
922 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
923 | //! of the reversed container. | |
924 | //! | |
925 | //! <b>Throws</b>: Nothing. | |
926 | //! | |
927 | //! <b>Complexity</b>: Constant. | |
928 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const | |
929 | { return const_reverse_iterator(cend()); } | |
930 | ||
931 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
932 | //! of the reversed container. | |
933 | //! | |
934 | //! <b>Throws</b>: Nothing. | |
935 | //! | |
936 | //! <b>Complexity</b>: Constant. | |
937 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const | |
938 | { return const_reverse_iterator(cbegin()); } | |
939 | ||
940 | BOOST_CONTAINER_FORCEINLINE bool empty() const | |
941 | { return !this->size(); } | |
942 | ||
943 | BOOST_CONTAINER_FORCEINLINE size_type size() const | |
944 | { return this->icont().size(); } | |
945 | ||
946 | BOOST_CONTAINER_FORCEINLINE size_type max_size() const | |
947 | { return AllocHolder::max_size(); } | |
948 | ||
949 | BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x) | |
950 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value | |
11fdf7f2 | 951 | && boost::container::dtl::is_nothrow_swappable<Compare>::value ) |
7c673cae FG |
952 | { AllocHolder::swap(x); } |
953 | ||
954 | public: | |
955 | ||
956 | typedef typename Icont::insert_commit_data insert_commit_data; | |
957 | ||
958 | // insert/erase | |
959 | std::pair<iterator,bool> insert_unique_check | |
960 | (const key_type& key, insert_commit_data &data) | |
961 | { | |
962 | std::pair<iiterator, bool> ret = | |
963 | this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data); | |
964 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
965 | } | |
966 | ||
967 | std::pair<iterator,bool> insert_unique_check | |
968 | (const_iterator hint, const key_type& key, insert_commit_data &data) | |
969 | { | |
970 | BOOST_ASSERT((priv_is_linked)(hint)); | |
971 | std::pair<iiterator, bool> ret = | |
972 | this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data); | |
973 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
974 | } | |
975 | ||
976 | template<class MovableConvertible> | |
977 | iterator insert_unique_commit | |
978 | (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) | |
979 | { | |
980 | NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v)); | |
981 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
982 | iterator ret(this->icont().insert_unique_commit(*tmp, data)); | |
983 | destroy_deallocator.release(); | |
984 | return ret; | |
985 | } | |
986 | ||
987 | template<class MovableConvertible> | |
988 | std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v) | |
989 | { | |
990 | insert_commit_data data; | |
991 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 992 | this->insert_unique_check(key_of_value_t()(v), data); |
7c673cae FG |
993 | if(ret.second){ |
994 | ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); | |
995 | } | |
996 | return ret; | |
997 | } | |
998 | ||
999 | private: | |
1000 | ||
1001 | template<class KeyConvertible, class M> | |
1002 | iiterator priv_insert_or_assign_commit | |
1003 | (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data) | |
1004 | { | |
1005 | NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj)); | |
1006 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1007 | iiterator ret(this->icont().insert_unique_commit(*tmp, data)); | |
1008 | destroy_deallocator.release(); | |
1009 | return ret; | |
1010 | } | |
1011 | ||
1012 | bool priv_is_linked(const_iterator const position) const | |
1013 | { | |
1014 | iiterator const cur(position.get()); | |
1015 | return cur == this->icont().end() || | |
1016 | cur == this->icont().root() || | |
1017 | iiterator(cur).go_parent().go_left() == cur || | |
1018 | iiterator(cur).go_parent().go_right() == cur; | |
1019 | } | |
1020 | ||
1021 | template<class MovableConvertible> | |
1022 | void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) | |
1023 | { | |
1024 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1025 | //push_back has no-throw guarantee so avoid any deallocator/destroyer | |
1026 | this->icont().push_back(*tmp); | |
1027 | } | |
1028 | ||
1029 | std::pair<iterator, bool> emplace_unique_impl(NodePtr p) | |
1030 | { | |
1031 | value_type &v = p->get_data(); | |
1032 | insert_commit_data data; | |
1033 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); | |
1034 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1035 | this->insert_unique_check(key_of_value_t()(v), data); |
7c673cae FG |
1036 | if(!ret.second){ |
1037 | return ret; | |
1038 | } | |
1039 | //No throw insertion part, release rollback | |
1040 | destroy_deallocator.release(); | |
1041 | return std::pair<iterator,bool> | |
1042 | ( iterator(this->icont().insert_unique_commit(*p, data)) | |
1043 | , true ); | |
1044 | } | |
1045 | ||
1046 | iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p) | |
1047 | { | |
1048 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1049 | value_type &v = p->get_data(); | |
1050 | insert_commit_data data; | |
1051 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1052 | this->insert_unique_check(hint, key_of_value_t()(v), data); |
7c673cae FG |
1053 | if(!ret.second){ |
1054 | Destroyer(this->node_alloc())(p); | |
1055 | return ret.first; | |
1056 | } | |
1057 | return iterator(this->icont().insert_unique_commit(*p, data)); | |
1058 | } | |
1059 | ||
1060 | public: | |
1061 | ||
1062 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1063 | ||
1064 | template <class... Args> | |
1065 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) | |
1066 | { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } | |
1067 | ||
1068 | template <class... Args> | |
1069 | BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
1070 | { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } | |
1071 | ||
1072 | template <class... Args> | |
1073 | iterator emplace_equal(BOOST_FWD_REF(Args)... args) | |
1074 | { | |
1075 | NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); | |
1076 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1077 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1078 | destroy_deallocator.release(); | |
1079 | return ret; | |
1080 | } | |
1081 | ||
1082 | template <class... Args> | |
1083 | iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
1084 | { | |
1085 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1086 | NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); | |
1087 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1088 | iterator ret(this->icont().insert_equal(hint.get(), *tmp)); | |
1089 | destroy_deallocator.release(); | |
1090 | return ret; | |
1091 | } | |
1092 | ||
1093 | template <class KeyType, class... Args> | |
1094 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace | |
1095 | (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) | |
1096 | { | |
1097 | insert_commit_data data; | |
1098 | const key_type & k = key; //Support emulated rvalue references | |
1099 | std::pair<iiterator, bool> ret = | |
1100 | hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data) | |
1101 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); | |
1102 | if(ret.second){ | |
1103 | ret.first = this->icont().insert_unique_commit | |
1104 | (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data); | |
1105 | } | |
1106 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
1107 | } | |
1108 | ||
1109 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1110 | ||
1111 | #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ | |
1112 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1113 | std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ | |
1114 | { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ | |
1115 | \ | |
1116 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1117 | iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1118 | { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ | |
1119 | \ | |
1120 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1121 | iterator emplace_equal(BOOST_MOVE_UREF##N)\ | |
1122 | {\ | |
1123 | NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ | |
1124 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ | |
1125 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\ | |
1126 | destroy_deallocator.release();\ | |
1127 | return ret;\ | |
1128 | }\ | |
1129 | \ | |
1130 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1131 | iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1132 | {\ | |
1133 | BOOST_ASSERT((priv_is_linked)(hint));\ | |
1134 | NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ | |
1135 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ | |
1136 | iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ | |
1137 | destroy_deallocator.release();\ | |
1138 | return ret;\ | |
1139 | }\ | |
1140 | \ | |
1141 | template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ | |
1142 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ | |
1143 | try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1144 | {\ | |
1145 | insert_commit_data data;\ | |
1146 | const key_type & k = key;\ | |
1147 | std::pair<iiterator, bool> ret =\ | |
1148 | hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\ | |
1149 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\ | |
1150 | if(ret.second){\ | |
1151 | ret.first = this->icont().insert_unique_commit\ | |
1152 | (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\ | |
1153 | }\ | |
1154 | return std::pair<iterator, bool>(iterator(ret.first), ret.second);\ | |
1155 | }\ | |
1156 | // | |
1157 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) | |
1158 | #undef BOOST_CONTAINER_TREE_EMPLACE_CODE | |
1159 | ||
1160 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1161 | ||
1162 | template<class MovableConvertible> | |
1163 | iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) | |
1164 | { | |
1165 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1166 | insert_commit_data data; | |
1167 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1168 | this->insert_unique_check(hint, key_of_value_t()(v), data); |
7c673cae FG |
1169 | if(!ret.second) |
1170 | return ret.first; | |
1171 | return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); | |
1172 | } | |
1173 | ||
1174 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator) | |
1175 | ||
1176 | template <class InputIterator> | |
1177 | void insert_unique(InputIterator first, InputIterator last) | |
1178 | { | |
1179 | for( ; first != last; ++first) | |
1180 | this->insert_unique(*first); | |
1181 | } | |
1182 | ||
1183 | iterator insert_equal(const value_type& v) | |
1184 | { | |
1185 | NodePtr tmp(AllocHolder::create_node(v)); | |
1186 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1187 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1188 | destroy_deallocator.release(); | |
1189 | return ret; | |
1190 | } | |
1191 | ||
1192 | template<class MovableConvertible> | |
1193 | iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v) | |
1194 | { | |
1195 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1196 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1197 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1198 | destroy_deallocator.release(); | |
1199 | return ret; | |
1200 | } | |
1201 | ||
1202 | template<class MovableConvertible> | |
1203 | iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) | |
1204 | { | |
1205 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1206 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1207 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1208 | iterator ret(this->icont().insert_equal(hint.get(), *tmp)); | |
1209 | destroy_deallocator.release(); | |
1210 | return ret; | |
1211 | } | |
1212 | ||
1213 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator) | |
1214 | ||
1215 | template <class InputIterator> | |
1216 | void insert_equal(InputIterator first, InputIterator last) | |
1217 | { | |
1218 | for( ; first != last; ++first) | |
1219 | this->insert_equal(*first); | |
1220 | } | |
1221 | ||
1222 | template<class KeyType, class M> | |
1223 | std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) | |
1224 | { | |
1225 | insert_commit_data data; | |
1226 | const key_type & k = key; //Support emulated rvalue references | |
1227 | std::pair<iiterator, bool> ret = | |
1228 | hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data) | |
1229 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); | |
1230 | if(ret.second){ | |
1231 | ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data); | |
1232 | } | |
1233 | else{ | |
1234 | ret.first->get_data().second = boost::forward<M>(obj); | |
1235 | } | |
1236 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
1237 | } | |
1238 | ||
1239 | iterator erase(const_iterator position) | |
1240 | { | |
1241 | BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); | |
1242 | return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); | |
1243 | } | |
1244 | ||
1245 | BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k) | |
1246 | { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); } | |
1247 | ||
1248 | iterator erase(const_iterator first, const_iterator last) | |
1249 | { | |
1250 | BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); | |
1251 | BOOST_ASSERT(first == last || (priv_is_linked)(last)); | |
1252 | return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); | |
1253 | } | |
1254 | ||
1255 | node_type extract(const key_type& k) | |
1256 | { | |
1257 | iterator const it = this->find(k); | |
1258 | if(this->end() != it){ | |
1259 | return this->extract(it); | |
1260 | } | |
1261 | return node_type(); | |
1262 | } | |
1263 | ||
1264 | node_type extract(const_iterator position) | |
1265 | { | |
1266 | BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); | |
1267 | iiterator const iit(position.get()); | |
1268 | this->icont().erase(iit); | |
1269 | return node_type(iit.operator->(), this->node_alloc()); | |
1270 | } | |
1271 | ||
1272 | insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1273 | { | |
1274 | return this->insert_unique_node(this->end(), boost::move(nh)); | |
1275 | } | |
1276 | ||
1277 | insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1278 | { | |
1279 | insert_return_type irt; //inserted == false, node.empty() | |
1280 | if(!nh.empty()){ | |
1281 | insert_commit_data data; | |
1282 | std::pair<iterator,bool> ret = | |
92f5a8d4 | 1283 | this->insert_unique_check(hint, key_of_value_t()(nh.value()), data); |
7c673cae FG |
1284 | if(ret.second){ |
1285 | irt.inserted = true; | |
b32b8144 | 1286 | irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data)); |
7c673cae FG |
1287 | nh.release(); |
1288 | } | |
1289 | else{ | |
1290 | irt.position = ret.first; | |
1291 | irt.node = boost::move(nh); | |
1292 | } | |
1293 | } | |
1294 | else{ | |
1295 | irt.position = this->end(); | |
1296 | } | |
1297 | return BOOST_MOVE_RET(insert_return_type, irt); | |
1298 | } | |
1299 | ||
1300 | iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1301 | { | |
1302 | if(nh.empty()){ | |
1303 | return this->end(); | |
1304 | } | |
1305 | else{ | |
1306 | NodePtr const p(nh.release()); | |
1307 | return iterator(this->icont().insert_equal(*p)); | |
1308 | } | |
1309 | } | |
1310 | ||
1311 | iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1312 | { | |
1313 | if(nh.empty()){ | |
1314 | return this->end(); | |
1315 | } | |
1316 | else{ | |
1317 | NodePtr const p(nh.release()); | |
1318 | return iterator(this->icont().insert_equal(hint.get(), *p)); | |
1319 | } | |
1320 | } | |
1321 | ||
1322 | template<class C2> | |
1323 | BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source) | |
1324 | { return this->icont().merge_unique(source.icont()); } | |
1325 | ||
1326 | template<class C2> | |
1327 | BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source) | |
1328 | { return this->icont().merge_equal(source.icont()); } | |
1329 | BOOST_CONTAINER_FORCEINLINE void clear() | |
1330 | { AllocHolder::clear(alloc_version()); } | |
1331 | ||
1332 | // search operations. Const and non-const overloads even if no iterator is returned | |
1333 | // so splay implementations can to their rebalancing when searching in non-const versions | |
1334 | BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k) | |
1335 | { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } | |
1336 | ||
1337 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const | |
1338 | { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } | |
1339 | ||
92f5a8d4 TL |
1340 | template <class K> |
1341 | BOOST_CONTAINER_FORCEINLINE | |
1342 | typename dtl::enable_if_transparent<key_compare, K, iterator>::type | |
1343 | find(const K& k) | |
1344 | { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } | |
1345 | ||
1346 | template <class K> | |
1347 | BOOST_CONTAINER_FORCEINLINE | |
1348 | typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type | |
1349 | find(const K& k) const | |
1350 | { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } | |
1351 | ||
7c673cae FG |
1352 | BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const |
1353 | { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } | |
1354 | ||
92f5a8d4 TL |
1355 | template <class K> |
1356 | BOOST_CONTAINER_FORCEINLINE | |
1357 | typename dtl::enable_if_transparent<key_compare, K, size_type>::type | |
1358 | count(const K& k) const | |
1359 | { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } | |
1360 | ||
1361 | BOOST_CONTAINER_FORCEINLINE bool contains(const key_type& x) const | |
1362 | { return this->find(x) != this->cend(); } | |
1363 | ||
1364 | template<typename K> | |
1365 | BOOST_CONTAINER_FORCEINLINE | |
1366 | typename dtl::enable_if_transparent<key_compare, K, bool>::type | |
1367 | contains(const K& x) const | |
1368 | { return this->find(x) != this->cend(); } | |
1369 | ||
7c673cae FG |
1370 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k) |
1371 | { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1372 | ||
1373 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const | |
1374 | { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1375 | ||
92f5a8d4 TL |
1376 | template <class K> |
1377 | BOOST_CONTAINER_FORCEINLINE | |
1378 | typename dtl::enable_if_transparent<key_compare, K, iterator>::type | |
1379 | lower_bound(const K& k) | |
1380 | { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1381 | ||
1382 | template <class K> | |
1383 | BOOST_CONTAINER_FORCEINLINE | |
1384 | typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type | |
1385 | lower_bound(const K& k) const | |
1386 | { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1387 | ||
7c673cae FG |
1388 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k) |
1389 | { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1390 | ||
1391 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const | |
1392 | { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1393 | ||
92f5a8d4 TL |
1394 | template <class K> |
1395 | BOOST_CONTAINER_FORCEINLINE | |
1396 | typename dtl::enable_if_transparent<key_compare, K, iterator>::type | |
1397 | upper_bound(const K& k) | |
1398 | { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1399 | ||
1400 | template <class K> | |
1401 | BOOST_CONTAINER_FORCEINLINE | |
1402 | typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type | |
1403 | upper_bound(const K& k) const | |
1404 | { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1405 | ||
7c673cae FG |
1406 | std::pair<iterator,iterator> equal_range(const key_type& k) |
1407 | { | |
1408 | std::pair<iiterator, iiterator> ret = | |
1409 | this->icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1410 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1411 | } | |
1412 | ||
1413 | std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const | |
1414 | { | |
1415 | std::pair<iiterator, iiterator> ret = | |
1416 | this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1417 | return std::pair<const_iterator,const_iterator> | |
1418 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1419 | } | |
1420 | ||
92f5a8d4 TL |
1421 | template <class K> |
1422 | BOOST_CONTAINER_FORCEINLINE | |
1423 | typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type | |
1424 | equal_range(const K& k) | |
1425 | { | |
1426 | std::pair<iiterator, iiterator> ret = | |
1427 | this->icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1428 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1429 | } | |
1430 | ||
1431 | template <class K> | |
1432 | BOOST_CONTAINER_FORCEINLINE | |
1433 | typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type | |
1434 | equal_range(const K& k) const | |
1435 | { | |
1436 | std::pair<iiterator, iiterator> ret = | |
1437 | this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1438 | return std::pair<const_iterator,const_iterator> | |
1439 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1440 | } | |
1441 | ||
7c673cae FG |
1442 | std::pair<iterator,iterator> lower_bound_range(const key_type& k) |
1443 | { | |
1444 | std::pair<iiterator, iiterator> ret = | |
1445 | this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1446 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1447 | } | |
1448 | ||
1449 | std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const | |
1450 | { | |
1451 | std::pair<iiterator, iiterator> ret = | |
1452 | this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1453 | return std::pair<const_iterator,const_iterator> | |
1454 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1455 | } | |
1456 | ||
92f5a8d4 TL |
1457 | template <class K> |
1458 | BOOST_CONTAINER_FORCEINLINE | |
1459 | typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type | |
1460 | lower_bound_range(const K& k) | |
1461 | { | |
1462 | std::pair<iiterator, iiterator> ret = | |
1463 | this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1464 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1465 | } | |
1466 | ||
1467 | template <class K> | |
1468 | BOOST_CONTAINER_FORCEINLINE | |
1469 | typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type | |
1470 | lower_bound_range(const K& k) const | |
1471 | { | |
1472 | std::pair<iiterator, iiterator> ret = | |
1473 | this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1474 | return std::pair<const_iterator,const_iterator> | |
1475 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1476 | } | |
1477 | ||
7c673cae FG |
1478 | BOOST_CONTAINER_FORCEINLINE void rebalance() |
1479 | { intrusive_tree_proxy_t::rebalance(this->icont()); } | |
1480 | ||
1481 | BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y) | |
1482 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
1483 | ||
1484 | BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y) | |
1485 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
1486 | ||
1487 | BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y) | |
1488 | { return !(x == y); } | |
1489 | ||
1490 | BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y) | |
1491 | { return y < x; } | |
1492 | ||
1493 | BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y) | |
1494 | { return !(y < x); } | |
1495 | ||
1496 | BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y) | |
1497 | { return !(x < y); } | |
1498 | ||
1499 | BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y) | |
92f5a8d4 TL |
1500 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value |
1501 | && boost::container::dtl::is_nothrow_swappable<Compare>::value ) | |
7c673cae FG |
1502 | { x.swap(y); } |
1503 | }; | |
1504 | ||
11fdf7f2 | 1505 | } //namespace dtl { |
7c673cae FG |
1506 | } //namespace container { |
1507 | ||
1508 | template <class T> | |
1509 | struct has_trivial_destructor_after_move; | |
1510 | ||
1511 | //!has_trivial_destructor_after_move<> == true_type | |
1512 | //!specialization for optimizations | |
1513 | template <class T, class KeyOfValue, class Compare, class Allocator, class Options> | |
1514 | struct has_trivial_destructor_after_move | |
1515 | < | |
11fdf7f2 | 1516 | ::boost::container::dtl::tree |
7c673cae FG |
1517 | <T, KeyOfValue, Compare, Allocator, Options> |
1518 | > | |
1519 | { | |
92f5a8d4 TL |
1520 | typedef typename ::boost::container::dtl::tree<T, KeyOfValue, Compare, Allocator, Options>::allocator_type allocator_type; |
1521 | typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer; | |
1522 | static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value && | |
7c673cae FG |
1523 | ::boost::has_trivial_destructor_after_move<pointer>::value && |
1524 | ::boost::has_trivial_destructor_after_move<Compare>::value; | |
1525 | }; | |
1526 | ||
1527 | } //namespace boost { | |
1528 | ||
1529 | #include <boost/container/detail/config_end.hpp> | |
1530 | ||
1531 | #endif //BOOST_CONTAINER_TREE_HPP |