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