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