]>
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 { | |
64 | namespace container_detail { | |
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 | { | |
74 | typedef typename container_detail::bi::make_set_base_hook | |
75 | < container_detail::bi::void_pointer<VoidPointer> | |
76 | , container_detail::bi::link_mode<container_detail::bi::normal_link> | |
77 | , container_detail::bi::optimize_size<OptimizeSize> | |
78 | >::type type; | |
79 | }; | |
80 | ||
81 | template<class VoidPointer, bool OptimizeSize> | |
82 | struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize> | |
83 | { | |
84 | typedef typename container_detail::bi::make_avl_set_base_hook | |
85 | < container_detail::bi::void_pointer<VoidPointer> | |
86 | , container_detail::bi::link_mode<container_detail::bi::normal_link> | |
87 | , container_detail::bi::optimize_size<OptimizeSize> | |
88 | >::type type; | |
89 | }; | |
90 | ||
91 | template<class VoidPointer, bool OptimizeSize> | |
92 | struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize> | |
93 | { | |
94 | typedef typename container_detail::bi::make_bs_set_base_hook | |
95 | < container_detail::bi::void_pointer<VoidPointer> | |
96 | , container_detail::bi::link_mode<container_detail::bi::normal_link> | |
97 | >::type type; | |
98 | }; | |
99 | ||
100 | template<class VoidPointer, bool OptimizeSize> | |
101 | struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize> | |
102 | { | |
103 | typedef typename container_detail::bi::make_bs_set_base_hook | |
104 | < container_detail::bi::void_pointer<VoidPointer> | |
105 | , container_detail::bi::link_mode<container_detail::bi::normal_link> | |
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 | { | |
128 | private: | |
129 | //BOOST_COPYABLE_AND_MOVABLE(tree_node) | |
130 | tree_node(); | |
131 | ||
132 | public: | |
133 | typedef typename intrusive_tree_hook | |
134 | <VoidPointer, tree_type_value, OptimizeSize>::type hook_type; | |
135 | typedef T value_type; | |
136 | typedef typename tree_internal_data_type<T>::type internal_type; | |
137 | ||
138 | typedef tree_node< T, VoidPointer | |
139 | , tree_type_value, OptimizeSize> node_t; | |
140 | ||
141 | BOOST_CONTAINER_FORCEINLINE T &get_data() | |
142 | { | |
143 | T* ptr = reinterpret_cast<T*>(&this->m_data); | |
144 | return *ptr; | |
145 | } | |
146 | ||
147 | BOOST_CONTAINER_FORCEINLINE const T &get_data() const | |
148 | { | |
149 | const T* ptr = reinterpret_cast<const T*>(&this->m_data); | |
150 | return *ptr; | |
151 | } | |
152 | ||
153 | internal_type m_data; | |
154 | ||
155 | template<class T1, class T2> | |
156 | BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p) | |
157 | { | |
158 | const_cast<T1&>(m_data.first) = p.first; | |
159 | m_data.second = p.second; | |
160 | } | |
161 | ||
162 | template<class T1, class T2> | |
163 | BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p) | |
164 | { | |
165 | const_cast<T1&>(m_data.first) = p.first; | |
166 | m_data.second = p.second; | |
167 | } | |
168 | ||
169 | template<class V> | |
170 | BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v) | |
171 | { m_data = v; } | |
172 | ||
173 | template<class T1, class T2> | |
174 | BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p) | |
175 | { | |
176 | const_cast<T1&>(m_data.first) = ::boost::move(p.first); | |
177 | m_data.second = ::boost::move(p.second); | |
178 | } | |
179 | ||
180 | template<class T1, class T2> | |
181 | BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p) | |
182 | { | |
183 | const_cast<T1&>(m_data.first) = ::boost::move(p.first); | |
184 | m_data.second = ::boost::move(p.second); | |
185 | } | |
186 | ||
187 | template<class V> | |
188 | BOOST_CONTAINER_FORCEINLINE void do_move_assign(V &v) | |
189 | { m_data = ::boost::move(v); } | |
190 | }; | |
191 | ||
192 | template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
193 | struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > { | |
194 | typedef T type; | |
195 | }; | |
196 | ||
197 | template<class Node, class Icont> | |
198 | class insert_equal_end_hint_functor | |
199 | { | |
200 | Icont &icont_; | |
201 | ||
202 | public: | |
203 | BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont) | |
204 | : icont_(icont) | |
205 | {} | |
206 | ||
207 | BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) | |
208 | { this->icont_.insert_equal(this->icont_.cend(), n); } | |
209 | }; | |
210 | ||
211 | template<class Node, class Icont> | |
212 | class push_back_functor | |
213 | { | |
214 | Icont &icont_; | |
215 | ||
216 | public: | |
217 | BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont) | |
218 | : icont_(icont) | |
219 | {} | |
220 | ||
221 | BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) | |
222 | { this->icont_.push_back(n); } | |
223 | }; | |
224 | ||
225 | }//namespace container_detail { | |
226 | ||
227 | namespace container_detail { | |
228 | ||
229 | template< class NodeType, class NodeCompareType | |
230 | , class SizeType, class HookType | |
231 | , boost::container::tree_type_enum tree_type_value> | |
232 | struct intrusive_tree_dispatch; | |
233 | ||
234 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
235 | struct intrusive_tree_dispatch | |
236 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree> | |
237 | { | |
238 | typedef typename container_detail::bi::make_rbtree | |
239 | <NodeType | |
240 | ,container_detail::bi::compare<NodeCompareType> | |
241 | ,container_detail::bi::base_hook<HookType> | |
242 | ,container_detail::bi::constant_time_size<true> | |
243 | ,container_detail::bi::size_type<SizeType> | |
244 | >::type type; | |
245 | }; | |
246 | ||
247 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
248 | struct intrusive_tree_dispatch | |
249 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree> | |
250 | { | |
251 | typedef typename container_detail::bi::make_avltree | |
252 | <NodeType | |
253 | ,container_detail::bi::compare<NodeCompareType> | |
254 | ,container_detail::bi::base_hook<HookType> | |
255 | ,container_detail::bi::constant_time_size<true> | |
256 | ,container_detail::bi::size_type<SizeType> | |
257 | >::type type; | |
258 | }; | |
259 | ||
260 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
261 | struct intrusive_tree_dispatch | |
262 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree> | |
263 | { | |
264 | typedef typename container_detail::bi::make_sgtree | |
265 | <NodeType | |
266 | ,container_detail::bi::compare<NodeCompareType> | |
267 | ,container_detail::bi::base_hook<HookType> | |
268 | ,container_detail::bi::floating_point<true> | |
269 | ,container_detail::bi::size_type<SizeType> | |
270 | >::type type; | |
271 | }; | |
272 | ||
273 | template<class NodeType, class NodeCompareType, class SizeType, class HookType> | |
274 | struct intrusive_tree_dispatch | |
275 | <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree> | |
276 | { | |
277 | typedef typename container_detail::bi::make_splaytree | |
278 | <NodeType | |
279 | ,container_detail::bi::compare<NodeCompareType> | |
280 | ,container_detail::bi::base_hook<HookType> | |
281 | ,container_detail::bi::constant_time_size<true> | |
282 | ,container_detail::bi::size_type<SizeType> | |
283 | >::type type; | |
284 | }; | |
285 | ||
286 | template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> | |
287 | struct intrusive_tree_type | |
288 | { | |
289 | private: | |
290 | typedef typename boost::container:: | |
291 | allocator_traits<Allocator>::value_type value_type; | |
292 | typedef typename boost::container:: | |
293 | allocator_traits<Allocator>::void_pointer void_pointer; | |
294 | typedef typename boost::container:: | |
295 | allocator_traits<Allocator>::size_type size_type; | |
296 | typedef typename container_detail::tree_node | |
297 | < value_type, void_pointer | |
298 | , tree_type_value, OptimizeSize> node_t; | |
299 | typedef value_to_node_compare | |
300 | <node_t, ValueCompare> node_compare_type; | |
301 | //Deducing the hook type from node_t (e.g. node_t::hook_type) would | |
302 | //provoke an early instantiation of node_t that could ruin recursive | |
303 | //tree definitions, so retype the complete type to avoid any problem. | |
304 | typedef typename intrusive_tree_hook | |
305 | <void_pointer, tree_type_value | |
306 | , OptimizeSize>::type hook_type; | |
307 | public: | |
308 | typedef typename intrusive_tree_dispatch | |
309 | < node_t, node_compare_type | |
310 | , size_type, hook_type | |
311 | , tree_type_value>::type type; | |
312 | }; | |
313 | ||
314 | //Trait to detect manually rebalanceable tree types | |
315 | template<boost::container::tree_type_enum tree_type_value> | |
316 | struct is_manually_balanceable | |
317 | { static const bool value = true; }; | |
318 | ||
319 | template<> struct is_manually_balanceable<red_black_tree> | |
320 | { static const bool value = false; }; | |
321 | ||
322 | template<> struct is_manually_balanceable<avl_tree> | |
323 | { static const bool value = false; }; | |
324 | ||
325 | //Proxy traits to implement different operations depending on the | |
326 | //is_manually_balanceable<>::value | |
327 | template< boost::container::tree_type_enum tree_type_value | |
328 | , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value> | |
329 | struct intrusive_tree_proxy | |
330 | { | |
331 | template<class Icont> | |
332 | BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &) {} | |
333 | }; | |
334 | ||
335 | template<boost::container::tree_type_enum tree_type_value> | |
336 | struct intrusive_tree_proxy<tree_type_value, true> | |
337 | { | |
338 | template<class Icont> | |
339 | BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c) | |
340 | { c.rebalance(); } | |
341 | }; | |
342 | ||
343 | } //namespace container_detail { | |
344 | ||
345 | namespace container_detail { | |
346 | ||
347 | //This functor will be used with Intrusive clone functions to obtain | |
348 | //already allocated nodes from a intrusive container instead of | |
349 | //allocating new ones. When the intrusive container runs out of nodes | |
350 | //the node holder is used instead. | |
351 | template<class AllocHolder, bool DoMove> | |
352 | class RecyclingCloner | |
353 | { | |
354 | typedef typename AllocHolder::intrusive_container intrusive_container; | |
355 | typedef typename AllocHolder::Node node_t; | |
356 | typedef typename AllocHolder::NodePtr node_ptr_type; | |
357 | ||
358 | public: | |
359 | RecyclingCloner(AllocHolder &holder, intrusive_container &itree) | |
360 | : m_holder(holder), m_icont(itree) | |
361 | {} | |
362 | ||
363 | BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>) | |
364 | { p->do_move_assign(const_cast<node_t &>(other).m_data); } | |
365 | ||
366 | BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>) | |
367 | { p->do_assign(other.m_data); } | |
368 | ||
369 | node_ptr_type operator()(const node_t &other) const | |
370 | { | |
371 | if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ | |
372 | //First recycle a node (this can't throw) | |
373 | BOOST_TRY{ | |
374 | //This can throw | |
375 | this->do_assign(p, other, bool_<DoMove>()); | |
376 | return p; | |
377 | } | |
378 | BOOST_CATCH(...){ | |
379 | //If there is an exception destroy the whole source | |
380 | m_holder.destroy_node(p); | |
381 | while((p = m_icont.unlink_leftmost_without_rebalance())){ | |
382 | m_holder.destroy_node(p); | |
383 | } | |
384 | BOOST_RETHROW | |
385 | } | |
386 | BOOST_CATCH_END | |
387 | } | |
388 | else{ | |
389 | return m_holder.create_node(other.m_data); | |
390 | } | |
391 | } | |
392 | ||
393 | AllocHolder &m_holder; | |
394 | intrusive_container &m_icont; | |
395 | }; | |
396 | ||
397 | template<class KeyCompare, class KeyOfValue> | |
398 | struct key_node_compare | |
399 | : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> | |
400 | { | |
401 | BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp) | |
402 | : base_t(comp) | |
403 | {} | |
404 | ||
405 | typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t; | |
406 | typedef KeyCompare key_compare; | |
407 | typedef KeyOfValue key_of_value; | |
408 | typedef typename KeyOfValue::type key_type; | |
409 | ||
410 | BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const | |
411 | { return static_cast<const key_compare &>(*this); } | |
412 | ||
413 | BOOST_CONTAINER_FORCEINLINE key_compare &key_comp() | |
414 | { return static_cast<key_compare &>(*this); } | |
415 | ||
416 | BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const | |
417 | { return this->key_comp()(key1, key2); } | |
418 | ||
419 | template<class U> | |
420 | BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const | |
421 | { return this->key_comp()(key1, key_of_value()(nonkey2.get_data())); } | |
422 | ||
423 | template<class U> | |
424 | BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const | |
425 | { return this->key_comp()(key_of_value()(nonkey1.get_data()), key2); } | |
426 | ||
427 | template<class U, class V> | |
428 | BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const | |
429 | { return this->key_comp()(key_of_value()(nonkey1.get_data()), key_of_value()(nonkey2.get_data())); } | |
430 | }; | |
431 | ||
432 | template <class T, class KeyOfValue, | |
433 | class Compare, class Allocator, | |
434 | class Options = tree_assoc_defaults> | |
435 | class tree | |
436 | : public container_detail::node_alloc_holder | |
437 | < Allocator | |
438 | , typename container_detail::intrusive_tree_type | |
439 | < Allocator, tree_value_compare | |
440 | <typename allocator_traits<Allocator>::pointer, Compare, KeyOfValue> | |
441 | , Options::tree_type, Options::optimize_size>::type | |
442 | > | |
443 | { | |
444 | typedef tree_value_compare | |
445 | < typename allocator_traits<Allocator>::pointer | |
446 | , Compare, KeyOfValue> ValComp; | |
447 | typedef typename container_detail::intrusive_tree_type | |
448 | < Allocator, ValComp, Options::tree_type | |
449 | , Options::optimize_size>::type Icont; | |
450 | typedef container_detail::node_alloc_holder | |
451 | <Allocator, Icont> AllocHolder; | |
452 | typedef typename AllocHolder::NodePtr NodePtr; | |
453 | typedef tree < T, KeyOfValue | |
454 | , Compare, Allocator, Options> ThisType; | |
455 | typedef typename AllocHolder::NodeAlloc NodeAlloc; | |
456 | typedef boost::container:: | |
457 | allocator_traits<NodeAlloc> allocator_traits_type; | |
458 | typedef typename AllocHolder::ValAlloc ValAlloc; | |
459 | typedef typename AllocHolder::Node Node; | |
460 | typedef typename Icont::iterator iiterator; | |
461 | typedef typename Icont::const_iterator iconst_iterator; | |
462 | typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer; | |
463 | typedef typename AllocHolder::alloc_version alloc_version; | |
464 | typedef intrusive_tree_proxy<Options::tree_type> intrusive_tree_proxy_t; | |
465 | ||
466 | BOOST_COPYABLE_AND_MOVABLE(tree) | |
467 | ||
468 | public: | |
469 | ||
470 | typedef typename KeyOfValue::type key_type; | |
471 | typedef T value_type; | |
472 | typedef Allocator allocator_type; | |
473 | typedef Compare key_compare; | |
474 | typedef ValComp value_compare; | |
475 | typedef typename boost::container:: | |
476 | allocator_traits<Allocator>::pointer pointer; | |
477 | typedef typename boost::container:: | |
478 | allocator_traits<Allocator>::const_pointer const_pointer; | |
479 | typedef typename boost::container:: | |
480 | allocator_traits<Allocator>::reference reference; | |
481 | typedef typename boost::container:: | |
482 | allocator_traits<Allocator>::const_reference const_reference; | |
483 | typedef typename boost::container:: | |
484 | allocator_traits<Allocator>::size_type size_type; | |
485 | typedef typename boost::container:: | |
486 | allocator_traits<Allocator>::difference_type difference_type; | |
487 | typedef container_detail::iterator_from_iiterator | |
488 | <iiterator, false> iterator; | |
489 | typedef container_detail::iterator_from_iiterator | |
490 | <iiterator, true > const_iterator; | |
491 | typedef boost::container::reverse_iterator | |
492 | <iterator> reverse_iterator; | |
493 | typedef boost::container::reverse_iterator | |
494 | <const_iterator> const_reverse_iterator; | |
495 | typedef node_handle | |
496 | < Node, value_type, allocator_type, void> node_type; | |
497 | typedef insert_return_type_base | |
498 | <iterator, node_type> insert_return_type; | |
499 | ||
500 | typedef NodeAlloc stored_allocator_type; | |
501 | ||
502 | private: | |
503 | ||
504 | typedef key_node_compare<key_compare, KeyOfValue> KeyNodeCompare; | |
505 | ||
506 | public: | |
507 | ||
508 | BOOST_CONTAINER_FORCEINLINE tree() | |
509 | : AllocHolder() | |
510 | {} | |
511 | ||
512 | BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a = allocator_type()) | |
513 | : AllocHolder(ValComp(comp), a) | |
514 | {} | |
515 | ||
516 | BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a) | |
517 | : AllocHolder(a) | |
518 | {} | |
519 | ||
520 | template <class InputIterator> | |
521 | tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, | |
522 | const allocator_type& a | |
523 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
524 | , typename container_detail::enable_if_or | |
525 | < void | |
526 | , container_detail::is_same<alloc_version, version_1> | |
527 | , container_detail::is_input_iterator<InputIterator> | |
528 | >::type * = 0 | |
529 | #endif | |
530 | ) | |
531 | : AllocHolder(value_compare(comp), a) | |
532 | { | |
533 | //Use cend() as hint to achieve linear time for | |
534 | //ordered ranges as required by the standard | |
535 | //for the constructor | |
536 | const const_iterator end_it(this->cend()); | |
537 | if(unique_insertion){ | |
538 | for ( ; first != last; ++first){ | |
539 | this->insert_unique_convertible(end_it, *first); | |
540 | } | |
541 | } | |
542 | else{ | |
543 | for ( ; first != last; ++first){ | |
544 | this->insert_equal_convertible(end_it, *first); | |
545 | } | |
546 | } | |
547 | } | |
548 | ||
549 | template <class InputIterator> | |
550 | tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, | |
551 | const allocator_type& a | |
552 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
553 | , typename container_detail::disable_if_or | |
554 | < void | |
555 | , container_detail::is_same<alloc_version, version_1> | |
556 | , container_detail::is_input_iterator<InputIterator> | |
557 | >::type * = 0 | |
558 | #endif | |
559 | ) | |
560 | : AllocHolder(value_compare(comp), a) | |
561 | { | |
562 | if(unique_insertion){ | |
563 | //Use cend() as hint to achieve linear time for | |
564 | //ordered ranges as required by the standard | |
565 | //for the constructor | |
566 | const const_iterator end_it(this->cend()); | |
567 | for ( ; first != last; ++first){ | |
568 | this->insert_unique_convertible(end_it, *first); | |
569 | } | |
570 | } | |
571 | else{ | |
572 | //Optimized allocation and construction | |
573 | this->allocate_many_and_construct | |
574 | ( first, boost::container::iterator_distance(first, last) | |
575 | , insert_equal_end_hint_functor<Node, Icont>(this->icont())); | |
576 | } | |
577 | } | |
578 | ||
579 | template <class InputIterator> | |
580 | tree( ordered_range_t, InputIterator first, InputIterator last | |
581 | , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type() | |
582 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
583 | , typename container_detail::enable_if_or | |
584 | < void | |
585 | , container_detail::is_same<alloc_version, version_1> | |
586 | , container_detail::is_input_iterator<InputIterator> | |
587 | >::type * = 0 | |
588 | #endif | |
589 | ) | |
590 | : AllocHolder(value_compare(comp), a) | |
591 | { | |
592 | for ( ; first != last; ++first){ | |
593 | this->push_back_impl(*first); | |
594 | } | |
595 | } | |
596 | ||
597 | template <class InputIterator> | |
598 | tree( ordered_range_t, InputIterator first, InputIterator last | |
599 | , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type() | |
600 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
601 | , typename container_detail::disable_if_or | |
602 | < void | |
603 | , container_detail::is_same<alloc_version, version_1> | |
604 | , container_detail::is_input_iterator<InputIterator> | |
605 | >::type * = 0 | |
606 | #endif | |
607 | ) | |
608 | : AllocHolder(value_compare(comp), a) | |
609 | { | |
610 | //Optimized allocation and construction | |
611 | this->allocate_many_and_construct | |
612 | ( first, boost::container::iterator_distance(first, last) | |
613 | , container_detail::push_back_functor<Node, Icont>(this->icont())); | |
614 | } | |
615 | ||
616 | BOOST_CONTAINER_FORCEINLINE tree(const tree& x) | |
617 | : AllocHolder(x.value_comp(), x) | |
618 | { | |
619 | this->icont().clone_from | |
620 | (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); | |
621 | } | |
622 | ||
623 | BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x) | |
624 | BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value) | |
625 | : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) | |
626 | {} | |
627 | ||
628 | BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a) | |
629 | : AllocHolder(x.value_comp(), a) | |
630 | { | |
631 | this->icont().clone_from | |
632 | (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); | |
633 | } | |
634 | ||
635 | tree(BOOST_RV_REF(tree) x, const allocator_type &a) | |
636 | : AllocHolder(x.value_comp(), a) | |
637 | { | |
638 | if(this->node_alloc() == x.node_alloc()){ | |
639 | this->icont().swap(x.icont()); | |
640 | } | |
641 | else{ | |
642 | this->icont().clone_from | |
643 | (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); | |
644 | } | |
645 | } | |
646 | ||
647 | BOOST_CONTAINER_FORCEINLINE ~tree() | |
648 | {} //AllocHolder clears the tree | |
649 | ||
650 | tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) | |
651 | { | |
652 | if (&x != this){ | |
653 | NodeAlloc &this_alloc = this->get_stored_allocator(); | |
654 | const NodeAlloc &x_alloc = x.get_stored_allocator(); | |
655 | container_detail::bool_<allocator_traits<NodeAlloc>:: | |
656 | propagate_on_container_copy_assignment::value> flag; | |
657 | if(flag && this_alloc != x_alloc){ | |
658 | this->clear(); | |
659 | } | |
660 | this->AllocHolder::copy_assign_alloc(x); | |
661 | //Transfer all the nodes to a temporary tree | |
662 | //If anything goes wrong, all the nodes will be destroyed | |
663 | //automatically | |
664 | Icont other_tree(::boost::move(this->icont())); | |
665 | ||
666 | //Now recreate the source tree reusing nodes stored by other_tree | |
667 | this->icont().clone_from | |
668 | (x.icont() | |
669 | , RecyclingCloner<AllocHolder, false>(*this, other_tree) | |
670 | , Destroyer(this->node_alloc())); | |
671 | ||
672 | //If there are remaining nodes, destroy them | |
673 | NodePtr p; | |
674 | while((p = other_tree.unlink_leftmost_without_rebalance())){ | |
675 | AllocHolder::destroy_node(p); | |
676 | } | |
677 | } | |
678 | return *this; | |
679 | } | |
680 | ||
681 | tree& operator=(BOOST_RV_REF(tree) x) | |
682 | BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || | |
683 | allocator_traits_type::is_always_equal::value) && | |
684 | boost::container::container_detail::is_nothrow_move_assignable<Compare>::value) | |
685 | { | |
686 | BOOST_ASSERT(this != &x); | |
687 | NodeAlloc &this_alloc = this->node_alloc(); | |
688 | NodeAlloc &x_alloc = x.node_alloc(); | |
689 | const bool propagate_alloc = allocator_traits<NodeAlloc>:: | |
690 | propagate_on_container_move_assignment::value; | |
691 | const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; | |
692 | //Resources can be transferred if both allocators are | |
693 | //going to be equal after this function (either propagated or already equal) | |
694 | if(propagate_alloc || allocators_equal){ | |
695 | //Destroy | |
696 | this->clear(); | |
697 | //Move allocator if needed | |
698 | this->AllocHolder::move_assign_alloc(x); | |
699 | //Obtain resources | |
700 | this->icont() = boost::move(x.icont()); | |
701 | } | |
702 | //Else do a one by one move | |
703 | else{ | |
704 | //Transfer all the nodes to a temporary tree | |
705 | //If anything goes wrong, all the nodes will be destroyed | |
706 | //automatically | |
707 | Icont other_tree(::boost::move(this->icont())); | |
708 | ||
709 | //Now recreate the source tree reusing nodes stored by other_tree | |
710 | this->icont().clone_from | |
711 | (::boost::move(x.icont()) | |
712 | , RecyclingCloner<AllocHolder, true>(*this, other_tree) | |
713 | , Destroyer(this->node_alloc())); | |
714 | ||
715 | //If there are remaining nodes, destroy them | |
716 | NodePtr p; | |
717 | while((p = other_tree.unlink_leftmost_without_rebalance())){ | |
718 | AllocHolder::destroy_node(p); | |
719 | } | |
720 | } | |
721 | return *this; | |
722 | } | |
723 | ||
724 | public: | |
725 | // accessors: | |
726 | BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const | |
727 | { return this->icont().value_comp().predicate(); } | |
728 | ||
729 | BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const | |
730 | { return this->icont().value_comp().predicate().key_comp(); } | |
731 | ||
732 | BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const | |
733 | { return allocator_type(this->node_alloc()); } | |
734 | ||
735 | BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const | |
736 | { return this->node_alloc(); } | |
737 | ||
738 | BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() | |
739 | { return this->node_alloc(); } | |
740 | ||
741 | BOOST_CONTAINER_FORCEINLINE iterator begin() | |
742 | { return iterator(this->icont().begin()); } | |
743 | ||
744 | BOOST_CONTAINER_FORCEINLINE const_iterator begin() const | |
745 | { return this->cbegin(); } | |
746 | ||
747 | BOOST_CONTAINER_FORCEINLINE iterator end() | |
748 | { return iterator(this->icont().end()); } | |
749 | ||
750 | BOOST_CONTAINER_FORCEINLINE const_iterator end() const | |
751 | { return this->cend(); } | |
752 | ||
753 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() | |
754 | { return reverse_iterator(end()); } | |
755 | ||
756 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const | |
757 | { return this->crbegin(); } | |
758 | ||
759 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() | |
760 | { return reverse_iterator(begin()); } | |
761 | ||
762 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const | |
763 | { return this->crend(); } | |
764 | ||
765 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. | |
766 | //! | |
767 | //! <b>Throws</b>: Nothing. | |
768 | //! | |
769 | //! <b>Complexity</b>: Constant. | |
770 | BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const | |
771 | { return const_iterator(this->non_const_icont().begin()); } | |
772 | ||
773 | //! <b>Effects</b>: Returns a const_iterator to the end of the container. | |
774 | //! | |
775 | //! <b>Throws</b>: Nothing. | |
776 | //! | |
777 | //! <b>Complexity</b>: Constant. | |
778 | BOOST_CONTAINER_FORCEINLINE const_iterator cend() const | |
779 | { return const_iterator(this->non_const_icont().end()); } | |
780 | ||
781 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
782 | //! of the reversed container. | |
783 | //! | |
784 | //! <b>Throws</b>: Nothing. | |
785 | //! | |
786 | //! <b>Complexity</b>: Constant. | |
787 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const | |
788 | { return const_reverse_iterator(cend()); } | |
789 | ||
790 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
791 | //! of the reversed container. | |
792 | //! | |
793 | //! <b>Throws</b>: Nothing. | |
794 | //! | |
795 | //! <b>Complexity</b>: Constant. | |
796 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const | |
797 | { return const_reverse_iterator(cbegin()); } | |
798 | ||
799 | BOOST_CONTAINER_FORCEINLINE bool empty() const | |
800 | { return !this->size(); } | |
801 | ||
802 | BOOST_CONTAINER_FORCEINLINE size_type size() const | |
803 | { return this->icont().size(); } | |
804 | ||
805 | BOOST_CONTAINER_FORCEINLINE size_type max_size() const | |
806 | { return AllocHolder::max_size(); } | |
807 | ||
808 | BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x) | |
809 | BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value | |
810 | && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) | |
811 | { AllocHolder::swap(x); } | |
812 | ||
813 | public: | |
814 | ||
815 | typedef typename Icont::insert_commit_data insert_commit_data; | |
816 | ||
817 | // insert/erase | |
818 | std::pair<iterator,bool> insert_unique_check | |
819 | (const key_type& key, insert_commit_data &data) | |
820 | { | |
821 | std::pair<iiterator, bool> ret = | |
822 | this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data); | |
823 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
824 | } | |
825 | ||
826 | std::pair<iterator,bool> insert_unique_check | |
827 | (const_iterator hint, const key_type& key, insert_commit_data &data) | |
828 | { | |
829 | BOOST_ASSERT((priv_is_linked)(hint)); | |
830 | std::pair<iiterator, bool> ret = | |
831 | this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data); | |
832 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
833 | } | |
834 | ||
835 | template<class MovableConvertible> | |
836 | iterator insert_unique_commit | |
837 | (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) | |
838 | { | |
839 | NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v)); | |
840 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
841 | iterator ret(this->icont().insert_unique_commit(*tmp, data)); | |
842 | destroy_deallocator.release(); | |
843 | return ret; | |
844 | } | |
845 | ||
846 | template<class MovableConvertible> | |
847 | std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v) | |
848 | { | |
849 | insert_commit_data data; | |
850 | std::pair<iterator,bool> ret = | |
851 | this->insert_unique_check(KeyOfValue()(v), data); | |
852 | if(ret.second){ | |
853 | ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); | |
854 | } | |
855 | return ret; | |
856 | } | |
857 | ||
858 | private: | |
859 | ||
860 | template<class KeyConvertible, class M> | |
861 | iiterator priv_insert_or_assign_commit | |
862 | (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data) | |
863 | { | |
864 | NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj)); | |
865 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
866 | iiterator ret(this->icont().insert_unique_commit(*tmp, data)); | |
867 | destroy_deallocator.release(); | |
868 | return ret; | |
869 | } | |
870 | ||
871 | bool priv_is_linked(const_iterator const position) const | |
872 | { | |
873 | iiterator const cur(position.get()); | |
874 | return cur == this->icont().end() || | |
875 | cur == this->icont().root() || | |
876 | iiterator(cur).go_parent().go_left() == cur || | |
877 | iiterator(cur).go_parent().go_right() == cur; | |
878 | } | |
879 | ||
880 | template<class MovableConvertible> | |
881 | void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) | |
882 | { | |
883 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
884 | //push_back has no-throw guarantee so avoid any deallocator/destroyer | |
885 | this->icont().push_back(*tmp); | |
886 | } | |
887 | ||
888 | std::pair<iterator, bool> emplace_unique_impl(NodePtr p) | |
889 | { | |
890 | value_type &v = p->get_data(); | |
891 | insert_commit_data data; | |
892 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); | |
893 | std::pair<iterator,bool> ret = | |
894 | this->insert_unique_check(KeyOfValue()(v), data); | |
895 | if(!ret.second){ | |
896 | return ret; | |
897 | } | |
898 | //No throw insertion part, release rollback | |
899 | destroy_deallocator.release(); | |
900 | return std::pair<iterator,bool> | |
901 | ( iterator(this->icont().insert_unique_commit(*p, data)) | |
902 | , true ); | |
903 | } | |
904 | ||
905 | iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p) | |
906 | { | |
907 | BOOST_ASSERT((priv_is_linked)(hint)); | |
908 | value_type &v = p->get_data(); | |
909 | insert_commit_data data; | |
910 | std::pair<iterator,bool> ret = | |
911 | this->insert_unique_check(hint, KeyOfValue()(v), data); | |
912 | if(!ret.second){ | |
913 | Destroyer(this->node_alloc())(p); | |
914 | return ret.first; | |
915 | } | |
916 | return iterator(this->icont().insert_unique_commit(*p, data)); | |
917 | } | |
918 | ||
919 | public: | |
920 | ||
921 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
922 | ||
923 | template <class... Args> | |
924 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) | |
925 | { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } | |
926 | ||
927 | template <class... Args> | |
928 | BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
929 | { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } | |
930 | ||
931 | template <class... Args> | |
932 | iterator emplace_equal(BOOST_FWD_REF(Args)... args) | |
933 | { | |
934 | NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); | |
935 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
936 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
937 | destroy_deallocator.release(); | |
938 | return ret; | |
939 | } | |
940 | ||
941 | template <class... Args> | |
942 | iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) | |
943 | { | |
944 | BOOST_ASSERT((priv_is_linked)(hint)); | |
945 | NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); | |
946 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
947 | iterator ret(this->icont().insert_equal(hint.get(), *tmp)); | |
948 | destroy_deallocator.release(); | |
949 | return ret; | |
950 | } | |
951 | ||
952 | template <class KeyType, class... Args> | |
953 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace | |
954 | (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) | |
955 | { | |
956 | insert_commit_data data; | |
957 | const key_type & k = key; //Support emulated rvalue references | |
958 | std::pair<iiterator, bool> ret = | |
959 | hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data) | |
960 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); | |
961 | if(ret.second){ | |
962 | ret.first = this->icont().insert_unique_commit | |
963 | (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data); | |
964 | } | |
965 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
966 | } | |
967 | ||
968 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
969 | ||
970 | #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ | |
971 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
972 | std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ | |
973 | { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ | |
974 | \ | |
975 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
976 | iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
977 | { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ | |
978 | \ | |
979 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
980 | iterator emplace_equal(BOOST_MOVE_UREF##N)\ | |
981 | {\ | |
982 | NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ | |
983 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ | |
984 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\ | |
985 | destroy_deallocator.release();\ | |
986 | return ret;\ | |
987 | }\ | |
988 | \ | |
989 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
990 | iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
991 | {\ | |
992 | BOOST_ASSERT((priv_is_linked)(hint));\ | |
993 | NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ | |
994 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ | |
995 | iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ | |
996 | destroy_deallocator.release();\ | |
997 | return ret;\ | |
998 | }\ | |
999 | \ | |
1000 | template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ | |
1001 | BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ | |
1002 | try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1003 | {\ | |
1004 | insert_commit_data data;\ | |
1005 | const key_type & k = key;\ | |
1006 | std::pair<iiterator, bool> ret =\ | |
1007 | hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\ | |
1008 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\ | |
1009 | if(ret.second){\ | |
1010 | ret.first = this->icont().insert_unique_commit\ | |
1011 | (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\ | |
1012 | }\ | |
1013 | return std::pair<iterator, bool>(iterator(ret.first), ret.second);\ | |
1014 | }\ | |
1015 | // | |
1016 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) | |
1017 | #undef BOOST_CONTAINER_TREE_EMPLACE_CODE | |
1018 | ||
1019 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1020 | ||
1021 | template<class MovableConvertible> | |
1022 | iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) | |
1023 | { | |
1024 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1025 | insert_commit_data data; | |
1026 | std::pair<iterator,bool> ret = | |
1027 | this->insert_unique_check(hint, KeyOfValue()(v), data); | |
1028 | if(!ret.second) | |
1029 | return ret.first; | |
1030 | return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); | |
1031 | } | |
1032 | ||
1033 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator) | |
1034 | ||
1035 | template <class InputIterator> | |
1036 | void insert_unique(InputIterator first, InputIterator last) | |
1037 | { | |
1038 | for( ; first != last; ++first) | |
1039 | this->insert_unique(*first); | |
1040 | } | |
1041 | ||
1042 | iterator insert_equal(const value_type& v) | |
1043 | { | |
1044 | NodePtr tmp(AllocHolder::create_node(v)); | |
1045 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1046 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1047 | destroy_deallocator.release(); | |
1048 | return ret; | |
1049 | } | |
1050 | ||
1051 | template<class MovableConvertible> | |
1052 | iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v) | |
1053 | { | |
1054 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1055 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1056 | iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); | |
1057 | destroy_deallocator.release(); | |
1058 | return ret; | |
1059 | } | |
1060 | ||
1061 | template<class MovableConvertible> | |
1062 | iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) | |
1063 | { | |
1064 | BOOST_ASSERT((priv_is_linked)(hint)); | |
1065 | NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); | |
1066 | scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); | |
1067 | iterator ret(this->icont().insert_equal(hint.get(), *tmp)); | |
1068 | destroy_deallocator.release(); | |
1069 | return ret; | |
1070 | } | |
1071 | ||
1072 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator) | |
1073 | ||
1074 | template <class InputIterator> | |
1075 | void insert_equal(InputIterator first, InputIterator last) | |
1076 | { | |
1077 | for( ; first != last; ++first) | |
1078 | this->insert_equal(*first); | |
1079 | } | |
1080 | ||
1081 | template<class KeyType, class M> | |
1082 | std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) | |
1083 | { | |
1084 | insert_commit_data data; | |
1085 | const key_type & k = key; //Support emulated rvalue references | |
1086 | std::pair<iiterator, bool> ret = | |
1087 | hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data) | |
1088 | : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); | |
1089 | if(ret.second){ | |
1090 | ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data); | |
1091 | } | |
1092 | else{ | |
1093 | ret.first->get_data().second = boost::forward<M>(obj); | |
1094 | } | |
1095 | return std::pair<iterator, bool>(iterator(ret.first), ret.second); | |
1096 | } | |
1097 | ||
1098 | iterator erase(const_iterator position) | |
1099 | { | |
1100 | BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); | |
1101 | return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); | |
1102 | } | |
1103 | ||
1104 | BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k) | |
1105 | { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); } | |
1106 | ||
1107 | iterator erase(const_iterator first, const_iterator last) | |
1108 | { | |
1109 | BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); | |
1110 | BOOST_ASSERT(first == last || (priv_is_linked)(last)); | |
1111 | return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); | |
1112 | } | |
1113 | ||
1114 | node_type extract(const key_type& k) | |
1115 | { | |
1116 | iterator const it = this->find(k); | |
1117 | if(this->end() != it){ | |
1118 | return this->extract(it); | |
1119 | } | |
1120 | return node_type(); | |
1121 | } | |
1122 | ||
1123 | node_type extract(const_iterator position) | |
1124 | { | |
1125 | BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); | |
1126 | iiterator const iit(position.get()); | |
1127 | this->icont().erase(iit); | |
1128 | return node_type(iit.operator->(), this->node_alloc()); | |
1129 | } | |
1130 | ||
1131 | insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1132 | { | |
1133 | return this->insert_unique_node(this->end(), boost::move(nh)); | |
1134 | } | |
1135 | ||
1136 | insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1137 | { | |
1138 | insert_return_type irt; //inserted == false, node.empty() | |
1139 | if(!nh.empty()){ | |
1140 | insert_commit_data data; | |
1141 | std::pair<iterator,bool> ret = | |
1142 | this->insert_unique_check(hint, KeyOfValue()(nh.value()), data); | |
1143 | if(ret.second){ | |
1144 | irt.inserted = true; | |
1145 | irt.position = iterator(this->icont().insert_unique_commit(*nh.get_node_pointer(), data)); | |
1146 | nh.release(); | |
1147 | } | |
1148 | else{ | |
1149 | irt.position = ret.first; | |
1150 | irt.node = boost::move(nh); | |
1151 | } | |
1152 | } | |
1153 | else{ | |
1154 | irt.position = this->end(); | |
1155 | } | |
1156 | return BOOST_MOVE_RET(insert_return_type, irt); | |
1157 | } | |
1158 | ||
1159 | iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1160 | { | |
1161 | if(nh.empty()){ | |
1162 | return this->end(); | |
1163 | } | |
1164 | else{ | |
1165 | NodePtr const p(nh.release()); | |
1166 | return iterator(this->icont().insert_equal(*p)); | |
1167 | } | |
1168 | } | |
1169 | ||
1170 | iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) | |
1171 | { | |
1172 | if(nh.empty()){ | |
1173 | return this->end(); | |
1174 | } | |
1175 | else{ | |
1176 | NodePtr const p(nh.release()); | |
1177 | return iterator(this->icont().insert_equal(hint.get(), *p)); | |
1178 | } | |
1179 | } | |
1180 | ||
1181 | template<class C2> | |
1182 | BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source) | |
1183 | { return this->icont().merge_unique(source.icont()); } | |
1184 | ||
1185 | template<class C2> | |
1186 | BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source) | |
1187 | { return this->icont().merge_equal(source.icont()); } | |
1188 | BOOST_CONTAINER_FORCEINLINE void clear() | |
1189 | { AllocHolder::clear(alloc_version()); } | |
1190 | ||
1191 | // search operations. Const and non-const overloads even if no iterator is returned | |
1192 | // so splay implementations can to their rebalancing when searching in non-const versions | |
1193 | BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k) | |
1194 | { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } | |
1195 | ||
1196 | BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const | |
1197 | { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } | |
1198 | ||
1199 | BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const | |
1200 | { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } | |
1201 | ||
1202 | BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k) | |
1203 | { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1204 | ||
1205 | BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const | |
1206 | { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } | |
1207 | ||
1208 | BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k) | |
1209 | { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1210 | ||
1211 | BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const | |
1212 | { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } | |
1213 | ||
1214 | std::pair<iterator,iterator> equal_range(const key_type& k) | |
1215 | { | |
1216 | std::pair<iiterator, iiterator> ret = | |
1217 | this->icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1218 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1219 | } | |
1220 | ||
1221 | std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const | |
1222 | { | |
1223 | std::pair<iiterator, iiterator> ret = | |
1224 | this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); | |
1225 | return std::pair<const_iterator,const_iterator> | |
1226 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1227 | } | |
1228 | ||
1229 | std::pair<iterator,iterator> lower_bound_range(const key_type& k) | |
1230 | { | |
1231 | std::pair<iiterator, iiterator> ret = | |
1232 | this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1233 | return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); | |
1234 | } | |
1235 | ||
1236 | std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const | |
1237 | { | |
1238 | std::pair<iiterator, iiterator> ret = | |
1239 | this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); | |
1240 | return std::pair<const_iterator,const_iterator> | |
1241 | (const_iterator(ret.first), const_iterator(ret.second)); | |
1242 | } | |
1243 | ||
1244 | BOOST_CONTAINER_FORCEINLINE void rebalance() | |
1245 | { intrusive_tree_proxy_t::rebalance(this->icont()); } | |
1246 | ||
1247 | BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y) | |
1248 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
1249 | ||
1250 | BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y) | |
1251 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
1252 | ||
1253 | BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y) | |
1254 | { return !(x == y); } | |
1255 | ||
1256 | BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y) | |
1257 | { return y < x; } | |
1258 | ||
1259 | BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y) | |
1260 | { return !(y < x); } | |
1261 | ||
1262 | BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y) | |
1263 | { return !(x < y); } | |
1264 | ||
1265 | BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y) | |
1266 | { x.swap(y); } | |
1267 | }; | |
1268 | ||
1269 | } //namespace container_detail { | |
1270 | } //namespace container { | |
1271 | ||
1272 | template <class T> | |
1273 | struct has_trivial_destructor_after_move; | |
1274 | ||
1275 | //!has_trivial_destructor_after_move<> == true_type | |
1276 | //!specialization for optimizations | |
1277 | template <class T, class KeyOfValue, class Compare, class Allocator, class Options> | |
1278 | struct has_trivial_destructor_after_move | |
1279 | < | |
1280 | ::boost::container::container_detail::tree | |
1281 | <T, KeyOfValue, Compare, Allocator, Options> | |
1282 | > | |
1283 | { | |
1284 | typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; | |
1285 | static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && | |
1286 | ::boost::has_trivial_destructor_after_move<pointer>::value && | |
1287 | ::boost::has_trivial_destructor_after_move<Compare>::value; | |
1288 | }; | |
1289 | ||
1290 | } //namespace boost { | |
1291 | ||
1292 | #include <boost/container/detail/config_end.hpp> | |
1293 | ||
1294 | #endif //BOOST_CONTAINER_TREE_HPP |