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_FLAT_TREE_HPP
12#define BOOST_CONTAINER_FLAT_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
25#include <boost/container/container_fwd.hpp>
26
27#include <boost/move/utility_core.hpp>
28
29#include <boost/container/detail/pair.hpp>
30#include <boost/container/vector.hpp>
31#include <boost/container/allocator_traits.hpp>
32
33#include <boost/container/detail/value_init.hpp>
34#include <boost/container/detail/destroyers.hpp>
35#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
36#include <boost/container/detail/iterator.hpp>
37#include <boost/container/detail/is_sorted.hpp>
38#include <boost/container/detail/type_traits.hpp>
39#include <boost/container/detail/iterators.hpp>
40
41#ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
42#include <boost/intrusive/pointer_traits.hpp>
43#endif
44#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
45
46#include <boost/move/make_unique.hpp>
47#include <boost/move/iterator.hpp>
48#include <boost/move/adl_move_swap.hpp>
49#include <boost/move/algo/adaptive_sort.hpp>
50
51#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
52#include <boost/move/detail/fwd_macros.hpp>
53#endif
54
55
56namespace boost {
57namespace container {
58namespace container_detail {
59
60template<class Compare, class Value, class KeyOfValue>
61class flat_tree_value_compare
62 : private Compare
63{
64 typedef Value first_argument_type;
65 typedef Value second_argument_type;
66 typedef bool return_type;
67 public:
68 flat_tree_value_compare()
69 : Compare()
70 {}
71
72 flat_tree_value_compare(const Compare &pred)
73 : Compare(pred)
74 {}
75
76 bool operator()(const Value& lhs, const Value& rhs) const
77 {
78 KeyOfValue key_extract;
79 return Compare::operator()(key_extract(lhs), key_extract(rhs));
80 }
81
82 const Compare &get_comp() const
83 { return *this; }
84
85 Compare &get_comp()
86 { return *this; }
87};
88
89template<class Pointer>
90struct get_flat_tree_iterators
91{
92 #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
93 typedef Pointer iterator;
94 typedef typename boost::intrusive::
95 pointer_traits<Pointer>::element_type iterator_element_type;
96 typedef typename boost::intrusive::
97 pointer_traits<Pointer>:: template
98 rebind_pointer<const iterator_element_type>::type const_iterator;
99 #else //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
100 typedef typename boost::container::container_detail::
101 vec_iterator<Pointer, false> iterator;
102 typedef typename boost::container::container_detail::
103 vec_iterator<Pointer, true > const_iterator;
104 #endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
105 typedef boost::container::reverse_iterator<iterator> reverse_iterator;
106 typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator;
107};
108
109template <class Value, class KeyOfValue,
110 class Compare, class Allocator>
111class flat_tree
112{
113 public:
114 typedef boost::container::vector<Value, Allocator> sequence_type;
115
116 private:
117 typedef Allocator allocator_t;
118 typedef allocator_traits<Allocator> allocator_traits_type;
119
120 public:
121 typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
122
123 private:
124 struct Data
125 //Inherit from value_compare to do EBO
126 : public value_compare
127 {
128 BOOST_COPYABLE_AND_MOVABLE(Data)
129
130 public:
131 Data()
132 : value_compare(), m_seq()
133 {}
134
135 explicit Data(const allocator_t &alloc)
136 : value_compare(), m_seq(alloc)
137 {}
138
139 explicit Data(const Compare &comp)
140 : value_compare(comp), m_seq()
141 {}
142
143 Data(const Compare &comp, const allocator_t &alloc)
144 : value_compare(comp), m_seq(alloc)
145 {}
146
147 explicit Data(const Data &d)
148 : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq)
149 {}
150
151 Data(BOOST_RV_REF(Data) d)
152 : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
153 {}
154
155 Data(const Data &d, const Allocator &a)
156 : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
157 {}
158
159 Data(BOOST_RV_REF(Data) d, const Allocator &a)
160 : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
161 {}
162
163 Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
164 {
165 this->value_compare::operator=(d);
166 m_seq = d.m_seq;
167 return *this;
168 }
169
170 Data& operator=(BOOST_RV_REF(Data) d)
171 {
172 this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
173 m_seq = boost::move(d.m_seq);
174 return *this;
175 }
176
177 void swap(Data &d)
178 {
179 value_compare& mycomp = *this, & othercomp = d;
180 boost::adl_move_swap(mycomp, othercomp);
181 this->m_seq.swap(d.m_seq);
182 }
183
184 sequence_type m_seq;
185 };
186
187 Data m_data;
188 BOOST_COPYABLE_AND_MOVABLE(flat_tree)
189
190 public:
191
192 typedef typename sequence_type::value_type value_type;
193 typedef typename sequence_type::pointer pointer;
194 typedef typename sequence_type::const_pointer const_pointer;
195 typedef typename sequence_type::reference reference;
196 typedef typename sequence_type::const_reference const_reference;
197 typedef typename KeyOfValue::type key_type;
198 typedef Compare key_compare;
199 typedef typename sequence_type::allocator_type allocator_type;
200 typedef typename sequence_type::size_type size_type;
201 typedef typename sequence_type::difference_type difference_type;
202 typedef typename sequence_type::iterator iterator;
203 typedef typename sequence_type::const_iterator const_iterator;
204 typedef typename sequence_type::reverse_iterator reverse_iterator;
205 typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
206
207 //!Standard extension
208 typedef allocator_type stored_allocator_type;
209
210 private:
211 typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
212
213 public:
214 BOOST_CONTAINER_FORCEINLINE flat_tree()
215 : m_data()
216 { }
217
218 BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const Compare& comp)
219 : m_data(comp)
220 { }
221
222 BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const allocator_type& a)
223 : m_data(a)
224 { }
225
226 BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a)
227 : m_data(comp, a)
228 { }
229
230 BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x)
231 : m_data(x.m_data)
232 { }
233
234 BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x)
235 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
236 : m_data(boost::move(x.m_data))
237 { }
238
239 BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x, const allocator_type &a)
240 : m_data(x.m_data, a)
241 { }
242
243 BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
244 : m_data(boost::move(x.m_data), a)
245 { }
246
247 template <class InputIterator>
248 BOOST_CONTAINER_FORCEINLINE
249 flat_tree( ordered_range_t, InputIterator first, InputIterator last)
250 : m_data()
251 {
252 this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
253 BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
254 }
255
256 template <class InputIterator>
257 BOOST_CONTAINER_FORCEINLINE
258 flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
259 : m_data(comp)
260 {
261 this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
262 BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
263 }
264
265 template <class InputIterator>
266 BOOST_CONTAINER_FORCEINLINE
267 flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
268 : m_data(comp, a)
269 {
270 this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
271 BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
272 }
273
274 template <class InputIterator>
275 BOOST_CONTAINER_FORCEINLINE
276 flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last)
277 : m_data()
278 {
279 this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
280 BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
281 }
282
283 template <class InputIterator>
284 BOOST_CONTAINER_FORCEINLINE
285 flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
286 : m_data(comp)
287 {
288 this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
289 BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
290 }
291
292 template <class InputIterator>
293 BOOST_CONTAINER_FORCEINLINE
294 flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
295 : m_data(comp, a)
296 {
297 this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
298 BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
299 }
300
301 template <class InputIterator>
302 BOOST_CONTAINER_FORCEINLINE
303 flat_tree( bool unique_insertion, InputIterator first, InputIterator last)
304 : m_data()
305 {
306 this->priv_range_insertion_construct(unique_insertion, first, last);
307 }
308
309 template <class InputIterator>
310 BOOST_CONTAINER_FORCEINLINE
311 flat_tree( bool unique_insertion, InputIterator first, InputIterator last
312 , const Compare& comp)
313 : m_data(comp)
314 {
315 this->priv_range_insertion_construct(unique_insertion, first, last);
316 }
317
318 template <class InputIterator>
319 BOOST_CONTAINER_FORCEINLINE
320 flat_tree( bool unique_insertion, InputIterator first, InputIterator last
321 , const allocator_type& a)
322 : m_data(a)
323 {
324 this->priv_range_insertion_construct(unique_insertion, first, last);
325 }
326
327 template <class InputIterator>
328 BOOST_CONTAINER_FORCEINLINE
329 flat_tree( bool unique_insertion, InputIterator first, InputIterator last
330 , const Compare& comp, const allocator_type& a)
331 : m_data(comp, a)
332 {
333 this->priv_range_insertion_construct(unique_insertion, first, last);
334 }
335
336 BOOST_CONTAINER_FORCEINLINE ~flat_tree()
337 {}
338
339 BOOST_CONTAINER_FORCEINLINE flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
340 { m_data = x.m_data; return *this; }
341
342 BOOST_CONTAINER_FORCEINLINE flat_tree& operator=(BOOST_RV_REF(flat_tree) x)
343 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
344 allocator_traits_type::is_always_equal::value) &&
345 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
346 { m_data = boost::move(x.m_data); return *this; }
347
348 BOOST_CONTAINER_FORCEINLINE const value_compare &priv_value_comp() const
349 { return static_cast<const value_compare &>(this->m_data); }
350
351 BOOST_CONTAINER_FORCEINLINE value_compare &priv_value_comp()
352 { return static_cast<value_compare &>(this->m_data); }
353
354 BOOST_CONTAINER_FORCEINLINE const key_compare &priv_key_comp() const
355 { return this->priv_value_comp().get_comp(); }
356
357 BOOST_CONTAINER_FORCEINLINE key_compare &priv_key_comp()
358 { return this->priv_value_comp().get_comp(); }
359
360 public:
361 // accessors:
362 BOOST_CONTAINER_FORCEINLINE Compare key_comp() const
363 { return this->m_data.get_comp(); }
364
365 BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
366 { return this->m_data; }
367
368 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
369 { return this->m_data.m_seq.get_allocator(); }
370
371 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const
372 { return this->m_data.m_seq.get_stored_allocator(); }
373
374 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator()
375 { return this->m_data.m_seq.get_stored_allocator(); }
376
377 BOOST_CONTAINER_FORCEINLINE iterator begin()
378 { return this->m_data.m_seq.begin(); }
379
380 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
381 { return this->cbegin(); }
382
383 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
384 { return this->m_data.m_seq.begin(); }
385
386 BOOST_CONTAINER_FORCEINLINE iterator end()
387 { return this->m_data.m_seq.end(); }
388
389 BOOST_CONTAINER_FORCEINLINE const_iterator end() const
390 { return this->cend(); }
391
392 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
393 { return this->m_data.m_seq.end(); }
394
395 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
396 { return reverse_iterator(this->end()); }
397
398 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
399 { return this->crbegin(); }
400
401 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
402 { return const_reverse_iterator(this->cend()); }
403
404 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
405 { return reverse_iterator(this->begin()); }
406
407 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
408 { return this->crend(); }
409
410 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
411 { return const_reverse_iterator(this->cbegin()); }
412
413 BOOST_CONTAINER_FORCEINLINE bool empty() const
414 { return this->m_data.m_seq.empty(); }
415
416 BOOST_CONTAINER_FORCEINLINE size_type size() const
417 { return this->m_data.m_seq.size(); }
418
419 BOOST_CONTAINER_FORCEINLINE size_type max_size() const
420 { return this->m_data.m_seq.max_size(); }
421
422 BOOST_CONTAINER_FORCEINLINE void swap(flat_tree& other)
423 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
424 && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
425 { this->m_data.swap(other.m_data); }
426
427 public:
428 // insert/erase
429 std::pair<iterator,bool> insert_unique(const value_type& val)
430 {
431 std::pair<iterator,bool> ret;
432 insert_commit_data data;
433 ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
434 ret.first = ret.second ? this->priv_insert_commit(data, val)
435 : iterator(vector_iterator_get_ptr(data.position));
436 return ret;
437 }
438
439 std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
440 {
441 std::pair<iterator,bool> ret;
442 insert_commit_data data;
443 ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
444 ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
445 : iterator(vector_iterator_get_ptr(data.position));
446 return ret;
447 }
448
449 iterator insert_equal(const value_type& val)
450 {
451 iterator i = this->upper_bound(KeyOfValue()(val));
452 i = this->m_data.m_seq.insert(i, val);
453 return i;
454 }
455
456 iterator insert_equal(BOOST_RV_REF(value_type) mval)
457 {
458 iterator i = this->upper_bound(KeyOfValue()(mval));
459 i = this->m_data.m_seq.insert(i, boost::move(mval));
460 return i;
461 }
462
463 iterator insert_unique(const_iterator hint, const value_type& val)
464 {
465 BOOST_ASSERT(this->priv_in_range_or_end(hint));
466 insert_commit_data data;
467 return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
468 ? this->priv_insert_commit(data, val)
469 : iterator(vector_iterator_get_ptr(data.position));
470 }
471
472 iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val)
473 {
474 BOOST_ASSERT(this->priv_in_range_or_end(hint));
475 insert_commit_data data;
476 return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
477 ? this->priv_insert_commit(data, boost::move(val))
478 : iterator(vector_iterator_get_ptr(data.position));
479 }
480
481 iterator insert_equal(const_iterator hint, const value_type& val)
482 {
483 BOOST_ASSERT(this->priv_in_range_or_end(hint));
484 insert_commit_data data;
485 this->priv_insert_equal_prepare(hint, val, data);
486 return this->priv_insert_commit(data, val);
487 }
488
489 iterator insert_equal(const_iterator hint, BOOST_RV_REF(value_type) mval)
490 {
491 BOOST_ASSERT(this->priv_in_range_or_end(hint));
492 insert_commit_data data;
493 this->priv_insert_equal_prepare(hint, mval, data);
494 return this->priv_insert_commit(data, boost::move(mval));
495 }
496
497 template <class InIt>
498 void insert_unique(InIt first, InIt last)
499 {
500 for ( ; first != last; ++first){
501 this->insert_unique(*first);
502 }
503 }
504
505 template <class InIt>
506 void insert_equal(InIt first, InIt last
507 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
508 , typename container_detail::enable_if_c
509 < container_detail::is_input_iterator<InIt>::value
510 >::type * = 0
511 #endif
512 )
513 { this->priv_insert_equal_loop(first, last); }
514
515 template <class InIt>
516 void insert_equal(InIt first, InIt last
517 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
518 , typename container_detail::enable_if_c
519 < !container_detail::is_input_iterator<InIt>::value
520 >::type * = 0
521 #endif
522 )
523 {
524 const size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last));
525 this->reserve(this->size()+len);
526 this->priv_insert_equal_loop(first, last);
527 }
528
529 //Ordered
530
531 template <class InIt>
532 void insert_equal(ordered_range_t, InIt first, InIt last
533 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
534 , typename container_detail::enable_if_c
535 < container_detail::is_input_iterator<InIt>::value
536 >::type * = 0
537 #endif
538 )
539 { this->priv_insert_equal_loop_ordered(first, last); }
540
541 template <class FwdIt>
542 void insert_equal(ordered_range_t, FwdIt first, FwdIt last
543 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
544 , typename container_detail::enable_if_c
545 < !container_detail::is_input_iterator<FwdIt>::value &&
546 container_detail::is_forward_iterator<FwdIt>::value
547 >::type * = 0
548 #endif
549 )
550 {
551 const size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last));
552 this->reserve(this->size()+len);
553 this->priv_insert_equal_loop_ordered(first, last);
554 }
555
556 template <class BidirIt>
557 void insert_equal(ordered_range_t, BidirIt first, BidirIt last
558 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
559 , typename container_detail::disable_if_or
560 < void
561 , container_detail::is_input_iterator<BidirIt>
562 , container_detail::is_forward_iterator<BidirIt>
563 >::type * = 0
564 #endif
565 )
566 { this->m_data.m_seq.merge(first, last, static_cast<const value_compare &>(this->m_data)); }
567
568 template <class InIt>
569 void insert_unique(ordered_unique_range_t, InIt first, InIt last
570 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
571 , typename container_detail::enable_if_or
572 < void
573 , container_detail::is_input_iterator<InIt>
574 , container_detail::is_forward_iterator<InIt>
575 >::type * = 0
576 #endif
577 )
578 {
579 const_iterator pos(this->cend());
580 for ( ; first != last; ++first){
581 pos = this->insert_unique(pos, *first);
582 ++pos;
583 }
584 }
585
586 template <class BidirIt>
587 void insert_unique(ordered_unique_range_t, BidirIt first, BidirIt last
588 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
589 , typename container_detail::enable_if_c
590 < !(container_detail::is_input_iterator<BidirIt>::value ||
591 container_detail::is_forward_iterator<BidirIt>::value)
592 >::type * = 0
593 #endif
594 )
595 { this->m_data.m_seq.merge_unique(first, last, static_cast<const value_compare &>(this->m_data)); }
596
597 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
598
599 template <class... Args>
600 std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
601 {
602 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;
603 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
604 stored_allocator_type &a = this->get_stored_allocator();
605 stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
606 value_destructor<stored_allocator_type> d(a, val);
607 return this->insert_unique(::boost::move(val));
608 }
609
610 template <class... Args>
611 iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
612 {
613 //hint checked in insert_unique
614 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;
615 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
616 stored_allocator_type &a = this->get_stored_allocator();
617 stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
618 value_destructor<stored_allocator_type> d(a, val);
619 return this->insert_unique(hint, ::boost::move(val));
620 }
621
622 template <class... Args>
623 iterator emplace_equal(BOOST_FWD_REF(Args)... args)
624 {
625 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;
626 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
627 stored_allocator_type &a = this->get_stored_allocator();
628 stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
629 value_destructor<stored_allocator_type> d(a, val);
630 return this->insert_equal(::boost::move(val));
631 }
632
633 template <class... Args>
634 iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
635 {
636 //hint checked in insert_equal
637 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;
638 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
639 stored_allocator_type &a = this->get_stored_allocator();
640 stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
641 value_destructor<stored_allocator_type> d(a, val);
642 return this->insert_equal(hint, ::boost::move(val));
643 }
644
645 template <class KeyType, class... Args>
646 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace
647 (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
648 {
649 std::pair<iterator,bool> ret;
650 insert_commit_data data;
651 const key_type & k = key;
652 ret.second = hint == const_iterator()
653 ? this->priv_insert_unique_prepare(k, data)
654 : this->priv_insert_unique_prepare(hint, k, data);
655
656 if(!ret.second){
657 ret.first = this->nth(data.position - this->cbegin());
658 }
659 else{
660 typedef typename emplace_functor_type<try_emplace_t, KeyType, Args...>::type func_t;
661 typedef emplace_iterator<value_type, func_t, difference_type> it_t;
662 func_t func(try_emplace_t(), ::boost::forward<KeyType>(key), ::boost::forward<Args>(args)...);
663 ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
664 }
665 return ret;
666 }
667
668 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
669
670 #define BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE(N) \
671 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
672 std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
673 {\
674 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\
675 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
676 stored_allocator_type &a = this->get_stored_allocator();\
677 stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
678 value_destructor<stored_allocator_type> d(a, val);\
679 return this->insert_unique(::boost::move(val));\
680 }\
681 \
682 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
683 iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
684 {\
685 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\
686 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
687 stored_allocator_type &a = this->get_stored_allocator();\
688 stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
689 value_destructor<stored_allocator_type> d(a, val);\
690 return this->insert_unique(hint, ::boost::move(val));\
691 }\
692 \
693 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
694 iterator emplace_equal(BOOST_MOVE_UREF##N)\
695 {\
696 typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\
697 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
698 stored_allocator_type &a = this->get_stored_allocator();\
699 stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
700 value_destructor<stored_allocator_type> d(a, val);\
701 return this->insert_equal(::boost::move(val));\
702 }\
703 \
704 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
705 iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
706 {\
707 typename aligned_storage <sizeof(value_type), alignment_of<value_type>::value>::type v;\
708 value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
709 stored_allocator_type &a = this->get_stored_allocator();\
710 stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
711 value_destructor<stored_allocator_type> d(a, val);\
712 return this->insert_equal(hint, ::boost::move(val));\
713 }\
714 template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
715 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\
716 try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
717 {\
718 std::pair<iterator,bool> ret;\
719 insert_commit_data data;\
720 const key_type & k = key;\
721 ret.second = hint == const_iterator()\
722 ? this->priv_insert_unique_prepare(k, data)\
723 : this->priv_insert_unique_prepare(hint, k, data);\
724 \
725 if(!ret.second){\
726 ret.first = this->nth(data.position - this->cbegin());\
727 }\
728 else{\
729 typedef typename emplace_functor_type<try_emplace_t, KeyType BOOST_MOVE_I##N BOOST_MOVE_TARG##N>::type func_t;\
730 typedef emplace_iterator<value_type, func_t, difference_type> it_t;\
731 func_t func(try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
732 ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());\
733 }\
734 return ret;\
735 }\
736 //
737 BOOST_MOVE_ITERATE_0TO7(BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE)
738 #undef BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE
739
740 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
741
742 template<class KeyType, class M>
743 std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
744 {
745 const key_type& k = key;
746 std::pair<iterator,bool> ret;
747 insert_commit_data data;
748 ret.second = hint == const_iterator()
749 ? this->priv_insert_unique_prepare(k, data)
750 : this->priv_insert_unique_prepare(hint, k, data);
751 if(!ret.second){
752 ret.first = this->nth(data.position - this->cbegin());
753 ret.first->second = boost::forward<M>(obj);
754 }
755 else{
756 typedef typename emplace_functor_type<KeyType, M>::type func_t;
757 typedef emplace_iterator<value_type, func_t, difference_type> it_t;
758 func_t func(boost::forward<KeyType>(key), boost::forward<M>(obj));
759 ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
760 }
761 return ret;
762 }
763
764 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator position)
765 { return this->m_data.m_seq.erase(position); }
766
767 size_type erase(const key_type& k)
768 {
769 std::pair<iterator,iterator > itp = this->equal_range(k);
770 size_type ret = static_cast<size_type>(itp.second-itp.first);
771 if (ret){
772 this->m_data.m_seq.erase(itp.first, itp.second);
773 }
774 return ret;
775 }
776
777 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
778 { return this->m_data.m_seq.erase(first, last); }
779
780 BOOST_CONTAINER_FORCEINLINE void clear()
781 { this->m_data.m_seq.clear(); }
782
783 //! <b>Effects</b>: Tries to deallocate the excess of memory created
784 // with previous allocations. The size of the vector is unchanged
785 //!
786 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
787 //!
788 //! <b>Complexity</b>: Linear to size().
789 BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
790 { this->m_data.m_seq.shrink_to_fit(); }
791
792 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
793 { return this->m_data.m_seq.nth(n); }
794
795 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
796 { return this->m_data.m_seq.nth(n); }
797
798 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
799 { return this->m_data.m_seq.index_of(p); }
800
801 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
802 { return this->m_data.m_seq.index_of(p); }
803
804 // set operations:
805 iterator find(const key_type& k)
806 {
807 iterator i = this->lower_bound(k);
808 iterator end_it = this->end();
809 if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
810 i = end_it;
811 }
812 return i;
813 }
814
815 const_iterator find(const key_type& k) const
816 {
817 const_iterator i = this->lower_bound(k);
818
819 const_iterator end_it = this->cend();
820 if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
821 i = end_it;
822 }
823 return i;
824 }
825
826 // set operations:
827 size_type count(const key_type& k) const
828 {
829 std::pair<const_iterator, const_iterator> p = this->equal_range(k);
830 size_type n = p.second - p.first;
831 return n;
832 }
833
834 template<class C2>
835 void merge_unique(flat_tree<Value, KeyOfValue, C2, Allocator>& source)
836 {
837 this->insert( boost::make_move_iterator(source.begin())
838 , boost::make_move_iterator(source.end()));
839 }
840
841 template<class C2>
842 void merge_equal(flat_tree<Value, KeyOfValue, C2, Allocator>& source)
843 {
844 this->insert( boost::make_move_iterator(source.begin())
845 , boost::make_move_iterator(source.end()));
846 }
847
848 void merge_unique(flat_tree& source)
849 {
850 this->m_data.m_seq.merge_unique
851 ( boost::make_move_iterator(source.begin())
852 , boost::make_move_iterator(source.end())
853 , static_cast<const value_compare &>(this->m_data));
854 }
855
856 void merge_equal(flat_tree& source)
857 {
858 this->m_data.m_seq.merge
859 ( boost::make_move_iterator(source.begin())
860 , boost::make_move_iterator(source.end())
861 , static_cast<const value_compare &>(this->m_data));
862 }
863
864 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
865 { return this->priv_lower_bound(this->begin(), this->end(), k); }
866
867 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const
868 { return this->priv_lower_bound(this->cbegin(), this->cend(), k); }
869
870 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k)
871 { return this->priv_upper_bound(this->begin(), this->end(), k); }
872
873 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const
874 { return this->priv_upper_bound(this->cbegin(), this->cend(), k); }
875
876 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& k)
877 { return this->priv_equal_range(this->begin(), this->end(), k); }
878
879 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
880 { return this->priv_equal_range(this->cbegin(), this->cend(), k); }
881
882 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, iterator> lower_bound_range(const key_type& k)
883 { return this->priv_lower_bound_range(this->begin(), this->end(), k); }
884
885 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
886 { return this->priv_lower_bound_range(this->cbegin(), this->cend(), k); }
887
888 BOOST_CONTAINER_FORCEINLINE size_type capacity() const
889 { return this->m_data.m_seq.capacity(); }
890
891 BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
892 { this->m_data.m_seq.reserve(cnt); }
893
894 BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
895 {
896 return boost::move(m_data.m_seq);
897 }
898
899 BOOST_CONTAINER_FORCEINLINE sequence_type &get_sequence_ref()
900 {
901 return m_data.m_seq;
902 }
903
904 void adopt_sequence_equal(BOOST_RV_REF(sequence_type) seq)
905 {
906 sequence_type &tseq = m_data.m_seq;
907 boost::movelib::adaptive_sort
908 ( boost::movelib::iterator_to_raw_pointer(seq.begin())
909 , boost::movelib::iterator_to_raw_pointer(seq.end())
910 , this->priv_value_comp()
911 , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
912 , tseq.capacity() - tseq.size());
913 tseq = boost::move(seq);
914 }
915
916 void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
917 {
918 BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
919 sequence_type &tseq = m_data.m_seq;
920 tseq = boost::move(seq);
921 }
922
923 void adopt_sequence_unique(BOOST_RV_REF(sequence_type) seq)
924 {
925 sequence_type &tseq = m_data.m_seq;
926 boost::movelib::adaptive_sort
927 ( boost::movelib::iterator_to_raw_pointer(seq.begin())
928 , boost::movelib::iterator_to_raw_pointer(seq.end())
929 , this->priv_value_comp()
930 , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
931 , tseq.capacity() - tseq.size());
932 seq.erase( boost::movelib::unique
933 (seq.begin(), seq.end(), boost::movelib::negate<value_compare>(this->m_data.get_comp()))
934 , seq.cend());
935 tseq = boost::move(seq);
936 }
937
938 void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
939 {
940 BOOST_ASSERT((is_sorted_and_unique)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
941 sequence_type &tseq = m_data.m_seq;
942 tseq = boost::move(seq);
943 }
944
945 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_tree& x, const flat_tree& y)
946 {
947 return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());
948 }
949
950 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_tree& x, const flat_tree& y)
951 {
952 return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
953 }
954
955 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_tree& x, const flat_tree& y)
956 { return !(x == y); }
957
958 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_tree& x, const flat_tree& y)
959 { return y < x; }
960
961 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_tree& x, const flat_tree& y)
962 { return !(y < x); }
963
964 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_tree& x, const flat_tree& y)
965 { return !(x < y); }
966
967 BOOST_CONTAINER_FORCEINLINE friend void swap(flat_tree& x, flat_tree& y)
968 { x.swap(y); }
969
970 private:
971
972 template <class InputIterator>
973 void priv_range_insertion_construct( bool unique_insertion, InputIterator first, InputIterator last)
974 {
975 //Use cend() as hint to achieve linear time for
976 //ordered ranges as required by the standard
977 //for the constructor
978 //Call end() every iteration as reallocation might have invalidated iterators
979 if(unique_insertion){
980 for ( ; first != last; ++first){
981 this->insert_unique(this->cend(), *first);
982 }
983 }
984 else{
985 for ( ; first != last; ++first){
986 this->insert_equal(this->cend(), *first);
987 }
988 }
989 }
990
991 BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const
992 {
993 return (this->begin() <= pos) && (pos <= this->end());
994 }
995
996 struct insert_commit_data
997 {
998 const_iterator position;
999 };
1000
1001 // insert/erase
1002 void priv_insert_equal_prepare
1003 (const_iterator pos, const value_type& val, insert_commit_data &data)
1004 {
1005 // N1780
1006 // To insert val at pos:
1007 // if pos == end || val <= *pos
1008 // if pos == begin || val >= *(pos-1)
1009 // insert val before pos
1010 // else
1011 // insert val before upper_bound(val)
1012 // else
1013 // insert val before lower_bound(val)
1014 const value_compare &val_cmp = this->m_data;
1015
1016 if(pos == this->cend() || !val_cmp(*pos, val)){
1017 if (pos == this->cbegin() || !val_cmp(val, pos[-1])){
1018 data.position = pos;
1019 }
1020 else{
1021 data.position =
1022 this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val));
1023 }
1024 }
1025 else{
1026 data.position =
1027 this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val));
1028 }
1029 }
1030
1031 bool priv_insert_unique_prepare
1032 (const_iterator b, const_iterator e, const key_type& k, insert_commit_data &commit_data)
1033 {
1034 const key_compare &key_cmp = this->priv_key_comp();
1035 commit_data.position = this->priv_lower_bound(b, e, k);
1036 return commit_data.position == e || key_cmp(k, KeyOfValue()(*commit_data.position));
1037 }
1038
1039 BOOST_CONTAINER_FORCEINLINE bool priv_insert_unique_prepare
1040 (const key_type& k, insert_commit_data &commit_data)
1041 { return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), k, commit_data); }
1042
1043 bool priv_insert_unique_prepare
1044 (const_iterator pos, const key_type& k, insert_commit_data &commit_data)
1045 {
1046 //N1780. Props to Howard Hinnant!
1047 //To insert k at pos:
1048 //if pos == end || k <= *pos
1049 // if pos == begin || k >= *(pos-1)
1050 // insert k before pos
1051 // else
1052 // insert k before upper_bound(k)
1053 //else if pos+1 == end || k <= *(pos+1)
1054 // insert k after pos
1055 //else
1056 // insert k before lower_bound(k)
1057 const key_compare &key_cmp = this->priv_key_comp();
1058 const const_iterator cend_it = this->cend();
1059 if(pos == cend_it || key_cmp(k, KeyOfValue()(*pos))){ //Check if k should go before end
1060 const const_iterator cbeg = this->cbegin();
1061 commit_data.position = pos;
1062 if(pos == cbeg){ //If container is empty then insert it in the beginning
1063 return true;
1064 }
1065 const_iterator prev(pos);
1066 --prev;
1067 if(key_cmp(KeyOfValue()(*prev), k)){ //If previous element was less, then it should go between prev and pos
1068 return true;
1069 }
1070 else if(!key_cmp(k, KeyOfValue()(*prev))){ //If previous was equal then insertion should fail
1071 commit_data.position = prev;
1072 return false;
1073 }
1074 else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion
1075 //but reduce the search between beg and prev as prev is bigger than k
1076 return this->priv_insert_unique_prepare(cbeg, prev, k, commit_data);
1077 }
1078 }
1079 else{
1080 //The hint is before the insertion position, so insert it
1081 //in the remaining range [pos, end)
1082 return this->priv_insert_unique_prepare(pos, cend_it, k, commit_data);
1083 }
1084 }
1085
1086 template<class Convertible>
1087 BOOST_CONTAINER_FORCEINLINE iterator priv_insert_commit
1088 (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
1089 {
1090 return this->m_data.m_seq.insert
1091 ( commit_data.position
1092 , boost::forward<Convertible>(convertible));
1093 }
1094
1095 template <class RanIt>
1096 RanIt priv_lower_bound(RanIt first, const RanIt last,
1097 const key_type & key) const
1098 {
1099 const Compare &key_cmp = this->m_data.get_comp();
1100 KeyOfValue key_extract;
1101 size_type len = static_cast<size_type>(last - first);
1102 RanIt middle;
1103
1104 while (len) {
1105 size_type step = len >> 1;
1106 middle = first;
1107 middle += step;
1108
1109 if (key_cmp(key_extract(*middle), key)) {
1110 first = ++middle;
1111 len -= step + 1;
1112 }
1113 else{
1114 len = step;
1115 }
1116 }
1117 return first;
1118 }
1119
1120 template <class RanIt>
1121 RanIt priv_upper_bound
1122 (RanIt first, const RanIt last,const key_type & key) const
1123 {
1124 const Compare &key_cmp = this->m_data.get_comp();
1125 KeyOfValue key_extract;
1126 size_type len = static_cast<size_type>(last - first);
1127 RanIt middle;
1128
1129 while (len) {
1130 size_type step = len >> 1;
1131 middle = first;
1132 middle += step;
1133
1134 if (key_cmp(key, key_extract(*middle))) {
1135 len = step;
1136 }
1137 else{
1138 first = ++middle;
1139 len -= step + 1;
1140 }
1141 }
1142 return first;
1143 }
1144
1145 template <class RanIt>
1146 std::pair<RanIt, RanIt>
1147 priv_equal_range(RanIt first, RanIt last, const key_type& key) const
1148 {
1149 const Compare &key_cmp = this->m_data.get_comp();
1150 KeyOfValue key_extract;
1151 size_type len = static_cast<size_type>(last - first);
1152 RanIt middle;
1153
1154 while (len) {
1155 size_type step = len >> 1;
1156 middle = first;
1157 middle += step;
1158
1159 if (key_cmp(key_extract(*middle), key)){
1160 first = ++middle;
1161 len -= step + 1;
1162 }
1163 else if (key_cmp(key, key_extract(*middle))){
1164 len = step;
1165 }
1166 else {
1167 //Middle is equal to key
1168 last = first;
1169 last += len;
1170 RanIt const first_ret = this->priv_lower_bound(first, middle, key);
1171 return std::pair<RanIt, RanIt>
1172 ( first_ret, this->priv_upper_bound(++middle, last, key));
1173 }
1174 }
1175 return std::pair<RanIt, RanIt>(first, first);
1176 }
1177
1178 template<class RanIt>
1179 std::pair<RanIt, RanIt> priv_lower_bound_range(RanIt first, RanIt last, const key_type& k) const
1180 {
1181 const Compare &key_cmp = this->m_data.get_comp();
1182 KeyOfValue key_extract;
1183 RanIt lb(this->priv_lower_bound(first, last, k)), ub(lb);
1184 if(lb != last && static_cast<difference_type>(!key_cmp(k, key_extract(*lb)))){
1185 ++ub;
1186 }
1187 return std::pair<RanIt, RanIt>(lb, ub);
1188 }
1189
1190 template<class InIt>
1191 void priv_insert_equal_loop(InIt first, InIt last)
1192 {
1193 for ( ; first != last; ++first){
1194 this->insert_equal(*first);
1195 }
1196 }
1197
1198 template<class InIt>
1199 void priv_insert_equal_loop_ordered(InIt first, InIt last)
1200 {
1201 const_iterator pos(this->cend());
1202 for ( ; first != last; ++first){
1203 //If ordered, then try hint version
1204 //to achieve constant-time complexity per insertion
1205 //in some cases
1206 pos = this->insert_equal(pos, *first);
1207 ++pos;
1208 }
1209 }
1210};
1211
1212} //namespace container_detail {
1213
1214} //namespace container {
1215
1216//!has_trivial_destructor_after_move<> == true_type
1217//!specialization for optimizations
1218template <class T, class KeyOfValue,
1219class Compare, class Allocator>
1220struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<T, KeyOfValue, Compare, Allocator> >
1221{
1222 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1223 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1224 ::boost::has_trivial_destructor_after_move<pointer>::value;
1225};
1226
1227} //namespace boost {
1228
1229#include <boost/container/detail/config_end.hpp>
1230
1231#endif // BOOST_CONTAINER_FLAT_TREE_HPP
1232