1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2005-2013. 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 #ifndef BOOST_CONTAINER_FLAT_MAP_HPP
11 #define BOOST_CONTAINER_FLAT_MAP_HPP
12
13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
15 #endif
16
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
18 # pragma once
19 #endif
20
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
23 // container
24 #include <boost/container/allocator_traits.hpp>
25 #include <boost/container/container_fwd.hpp>
26 #include <boost/container/new_allocator.hpp> //new_allocator
27 #include <boost/container/throw_exception.hpp>
28 // container/detail
29 #include <boost/container/detail/flat_tree.hpp>
30 #include <boost/container/detail/type_traits.hpp>
31 #include <boost/container/detail/mpl.hpp>
32 #include <boost/container/detail/algorithm.hpp> //equal()
33 #include <boost/container/detail/container_or_allocator_rebind.hpp>
34 // move
35 #include <boost/move/utility_core.hpp>
36 #include <boost/move/traits.hpp>
37 // move/detail
38 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
39 #include <boost/move/detail/fwd_macros.hpp>
40 #endif
41 #include <boost/move/detail/move_helpers.hpp>
42 // intrusive
43 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
44 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
45 //others
46 #include <boost/core/no_exceptions_support.hpp>
47
48 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
49 #include <initializer_list>
50 #endif
51
52 namespace boost {
53 namespace container {
54
55 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
56
57 template <class Key, class T, class Compare, class AllocatorOrContainer>
58 class flat_multimap;
59
60 namespace dtl{
61
62 template<class D, class S>
force(S & s)63 BOOST_CONTAINER_FORCEINLINE static D &force(S &s)
64 { return *reinterpret_cast<D*>(&s); }
65
66 template<class D, class S>
force_copy(const S & s)67 BOOST_CONTAINER_FORCEINLINE static D force_copy(const S &s)
68 {
69 const D *const vp = reinterpret_cast<const D *>(&s);
70 D ret_val(*vp);
71 return ret_val;
72 }
73
74 } //namespace dtl{
75
76 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
77
78 //! A flat_map is a kind of associative container that supports unique keys (contains at
79 //! most one of each key value) and provides for fast retrieval of values of another
80 //! type T based on the keys.
81 //!
82 //! A flat_map satisfies all of the requirements of a container, a reversible
83 //! container and an associative container. A flat_map also provides
84 //! most operations described for unique keys. For a
85 //! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
86 //! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
87 //!
88 //! flat_map is similar to std::map but it's implemented by as an ordered sequence container.
89 //! The underlying sequence container is by default <i>vector</i> but it can also work
90 //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
91 //!
92 //! Using vector-like sequence containers means that inserting a new element into a flat_map might invalidate
93 //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
94 //! container that offers stable pointers and references). Similarly, erasing an element might invalidate
95 //! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
96 //!
97 //! This container provides random-access iterators.
98 //!
99 //! \tparam Key is the key_type of the map
100 //! \tparam Value is the <code>mapped_type</code>
101 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
102 //! \tparam AllocatorOrContainer is either:
103 //! - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
104 //! (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
105 //! - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
106 //! sequence container with random-access iterators..
107 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
108 template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > >
109 #else
110 template <class Key, class T, class Compare, class AllocatorOrContainer>
111 #endif
112 class flat_map
113 {
114 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
115 private:
116 BOOST_COPYABLE_AND_MOVABLE(flat_map)
117 //This is the tree that we should store if pair was movable
118 typedef dtl::flat_tree<
119 std::pair<Key, T>,
120 dtl::select1st<Key>,
121 Compare,
122 AllocatorOrContainer> tree_t;
123
124 //This is the real tree stored here. It's based on a movable pair
125 typedef dtl::flat_tree<
126 dtl::pair<Key, T>,
127 dtl::select1st<Key>,
128 Compare,
129 typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type
130 > impl_tree_t;
131 impl_tree_t m_flat_tree; // flat tree representing flat_map
132
133 typedef typename impl_tree_t::value_type impl_value_type;
134 typedef typename impl_tree_t::const_iterator impl_const_iterator;
135 typedef typename impl_tree_t::iterator impl_iterator;
136 typedef typename impl_tree_t::allocator_type impl_allocator_type;
137 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
138 typedef std::initializer_list<impl_value_type> impl_initializer_list;
139 #endif
140
141 typedef dtl::flat_tree_value_compare
142 < Compare
143 , dtl::select1st<Key>
144 , std::pair<Key, T> > value_compare_t;
145 typedef typename tree_t::iterator iterator_t;
146 typedef typename tree_t::const_iterator const_iterator_t;
147 typedef typename tree_t::reverse_iterator reverse_iterator_t;
148 typedef typename tree_t::const_reverse_iterator const_reverse_iterator_t;
149
150 public:
151 typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type;
152 typedef typename impl_tree_t::sequence_type impl_sequence_type;
153
tree()154 BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree()
155 { return m_flat_tree; }
156
tree() const157 BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const
158 { return m_flat_tree; }
159
160 private:
161 typedef typename tree_t::get_stored_allocator_const_return_t get_stored_allocator_const_return_t;
162 typedef typename tree_t::get_stored_allocator_noconst_return_t get_stored_allocator_noconst_return_t;
163 typedef typename impl_tree_t::get_stored_allocator_const_return_t impl_get_stored_allocator_const_return_t;
164 typedef typename impl_tree_t::get_stored_allocator_noconst_return_t impl_get_stored_allocator_noconst_return_t;
165
166 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
167
168 public:
169
170 //////////////////////////////////////////////
171 //
172 // types
173 //
174 //////////////////////////////////////////////
175 typedef Key key_type;
176 typedef T mapped_type;
177 typedef Compare key_compare;
178 typedef std::pair<Key, T> value_type;
179 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type) sequence_type;
180 typedef typename sequence_type::allocator_type allocator_type;
181 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
182 typedef typename sequence_type::pointer pointer;
183 typedef typename sequence_type::const_pointer const_pointer;
184 typedef typename sequence_type::reference reference;
185 typedef typename sequence_type::const_reference const_reference;
186 typedef typename sequence_type::size_type size_type;
187 typedef typename sequence_type::difference_type difference_type;
188 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
189 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare) value_compare;
190
191 typedef typename sequence_type::iterator iterator;
192 typedef typename sequence_type::const_iterator const_iterator;
193 typedef typename sequence_type::reverse_iterator reverse_iterator;
194 typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
195 typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type;
196
197 //AllocatorOrContainer::value_type must be std::pair<Key, T>
198 BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, value_type>::value));
199
200 //////////////////////////////////////////////
201 //
202 // construct/copy/destroy
203 //
204 //////////////////////////////////////////////
205
206 //! <b>Effects</b>: Default constructs an empty flat_map.
207 //!
208 //! <b>Complexity</b>: Constant.
flat_map()209 BOOST_CONTAINER_FORCEINLINE flat_map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value &&
210 dtl::is_nothrow_default_constructible<Compare>::value)
211 : m_flat_tree()
212 {}
213
214 //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator.
215 //!
216 //! <b>Complexity</b>: Constant.
flat_map(const allocator_type & a)217 BOOST_CONTAINER_FORCEINLINE explicit flat_map(const allocator_type& a)
218 : m_flat_tree(dtl::force<const impl_allocator_type>(a))
219 {}
220
221 //! <b>Effects</b>: Constructs an empty flat_map using the specified
222 //! comparison object.
223 //!
224 //! <b>Complexity</b>: Constant.
flat_map(const Compare & comp)225 BOOST_CONTAINER_FORCEINLINE explicit flat_map(const Compare& comp)
226 : m_flat_tree(comp)
227 {}
228
229 //! <b>Effects</b>: Constructs an empty flat_map using the specified
230 //! comparison object and allocator.
231 //!
232 //! <b>Complexity</b>: Constant.
flat_map(const Compare & comp,const allocator_type & a)233 BOOST_CONTAINER_FORCEINLINE flat_map(const Compare& comp, const allocator_type& a)
234 : m_flat_tree(comp, dtl::force<const impl_allocator_type>(a))
235 {}
236
237 //! <b>Effects</b>: Constructs an empty flat_map and
238 //! and inserts elements from the range [first ,last ).
239 //!
240 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
241 //! the predicate and otherwise N logN, where N is last - first.
242 template <class InputIterator>
flat_map(InputIterator first,InputIterator last)243 BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last)
244 : m_flat_tree(true, first, last)
245 {}
246
247 //! <b>Effects</b>: Constructs an empty flat_map using the specified
248 //! allocator, and inserts elements from the range [first ,last ).
249 //!
250 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
251 //! the predicate and otherwise N logN, where N is last - first.
252 template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const allocator_type & a)253 BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const allocator_type& a)
254 : m_flat_tree(true, first, last, dtl::force<const impl_allocator_type>(a))
255 {}
256
257 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
258 //! and inserts elements from the range [first ,last ).
259 //!
260 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
261 //! the predicate and otherwise N logN, where N is last - first.
262 template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const Compare & comp)263 BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const Compare& comp)
264 : m_flat_tree(true, first, last, comp)
265 {}
266
267 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
268 //! allocator, and inserts elements from the range [first ,last ).
269 //!
270 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
271 //! the predicate and otherwise N logN, where N is last - first.
272 template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)273 BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
274 : m_flat_tree(true, first, last, comp, dtl::force<const impl_allocator_type>(a))
275 {}
276
277 //! <b>Effects</b>: Constructs an empty flat_map
278 //! and inserts elements from the ordered range [first ,last). This function
279 //! is more efficient than the normal range creation for ordered ranges.
280 //!
281 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
282 //!
283 //! <b>Complexity</b>: Linear in N.
284 //!
285 //! <b>Note</b>: Non-standard extension.
286 template <class InputIterator>
287 BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last)288 flat_map(ordered_unique_range_t, InputIterator first, InputIterator last)
289 : m_flat_tree(ordered_range, first, last)
290 {}
291
292 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
293 //! inserts elements from the ordered range [first ,last). This function
294 //! is more efficient than the normal range creation for ordered ranges.
295 //!
296 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
297 //!
298 //! <b>Complexity</b>: Linear in N.
299 //!
300 //! <b>Note</b>: Non-standard extension.
301 template <class InputIterator>
302 BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp)303 flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
304 : m_flat_tree(ordered_range, first, last, comp)
305 {}
306
307 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
308 //! allocator, and inserts elements from the ordered range [first ,last). This function
309 //! is more efficient than the normal range creation for ordered ranges.
310 //!
311 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
312 //!
313 //! <b>Complexity</b>: Linear in N.
314 //!
315 //! <b>Note</b>: Non-standard extension.
316 template <class InputIterator>
317 BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)318 flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
319 : m_flat_tree(ordered_range, first, last, comp, dtl::force<const impl_allocator_type>(a))
320 {}
321
322 //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator and
323 //! inserts elements from the ordered range [first ,last). This function
324 //! is more efficient than the normal range creation for ordered ranges.
325 //!
326 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
327 //!
328 //! <b>Complexity</b>: Linear in N.
329 //!
330 //! <b>Note</b>: Non-standard extension.
331 template <class InputIterator>
332 BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const allocator_type & a)333 flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
334 : m_flat_tree(ordered_range, first, last, Compare(), a)
335 {}
336
337 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
338 //! <b>Effects</b>: Constructs an empty flat_map and
339 //! inserts elements from the range [il.begin() ,il.end()).
340 //!
341 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
342 //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il)343 BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il)
344 : m_flat_tree( true
345 , dtl::force<impl_initializer_list>(il).begin()
346 , dtl::force<impl_initializer_list>(il).end())
347 {}
348
349 //! <b>Effects</b>: Constructs an empty flat_map using the specified
350 //! allocator, and inserts elements from the range [il.begin() ,il.end()).
351 //!
352 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
353 //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const allocator_type & a)354 BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const allocator_type& a)
355 : m_flat_tree( true
356 , dtl::force<impl_initializer_list>(il).begin()
357 , dtl::force<impl_initializer_list>(il).end()
358 , dtl::force<const impl_allocator_type>(a))
359 {}
360
361 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
362 //! inserts elements from the range [il.begin() ,il.end()).
363 //!
364 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
365 //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const Compare & comp)366 BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const Compare& comp)
367 : m_flat_tree(true
368 , dtl::force<impl_initializer_list>(il).begin()
369 , dtl::force<impl_initializer_list>(il).end()
370 , comp)
371 {}
372
373 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
374 //! allocator, and inserts elements from the range [il.begin() ,il.end()).
375 //!
376 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
377 //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)378 BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
379 : m_flat_tree(true
380 , dtl::force<impl_initializer_list>(il).begin()
381 , dtl::force<impl_initializer_list>(il).end()
382 , comp
383 , dtl::force<const impl_allocator_type>(a))
384 {}
385
386 //! <b>Effects</b>: Constructs an empty flat_map using and
387 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
388 //! is more efficient than the normal range creation for ordered ranges.
389 //!
390 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
391 //! unique values.
392 //!
393 //! <b>Complexity</b>: Linear in N.
394 //!
395 //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il)396 BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il)
397 : m_flat_tree(ordered_unique_range
398 , dtl::force<impl_initializer_list>(il).begin()
399 , dtl::force<impl_initializer_list>(il).end())
400 {}
401
402 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
403 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
404 //! is more efficient than the normal range creation for ordered ranges.
405 //!
406 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
407 //! unique values.
408 //!
409 //! <b>Complexity</b>: Linear in N.
410 //!
411 //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp)412 BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
413 : m_flat_tree(ordered_unique_range
414 , dtl::force<impl_initializer_list>(il).begin()
415 , dtl::force<impl_initializer_list>(il).end()
416 , comp)
417 {}
418
419 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
420 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
421 //! is more efficient than the normal range creation for ordered ranges.
422 //!
423 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
424 //! unique values.
425 //!
426 //! <b>Complexity</b>: Linear in N.
427 //!
428 //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)429 BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
430 : m_flat_tree( ordered_unique_range
431 , dtl::force<impl_initializer_list>(il).begin()
432 , dtl::force<impl_initializer_list>(il).end()
433 , comp
434 , dtl::force<const impl_allocator_type>(a))
435 {}
436 #endif
437
438 //! <b>Effects</b>: Copy constructs a flat_map.
439 //!
440 //! <b>Complexity</b>: Linear in x.size().
flat_map(const flat_map & x)441 BOOST_CONTAINER_FORCEINLINE flat_map(const flat_map& x)
442 : m_flat_tree(x.m_flat_tree)
443 {}
444
445 //! <b>Effects</b>: Move constructs a flat_map.
446 //! Constructs *this using x's resources.
447 //!
448 //! <b>Complexity</b>: Constant.
449 //!
450 //! <b>Postcondition</b>: x is emptied.
flat_map(BOOST_RV_REF (flat_map)x)451 BOOST_CONTAINER_FORCEINLINE flat_map(BOOST_RV_REF(flat_map) x)
452 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
453 : m_flat_tree(boost::move(x.m_flat_tree))
454 {}
455
456 //! <b>Effects</b>: Copy constructs a flat_map using the specified allocator.
457 //!
458 //! <b>Complexity</b>: Linear in x.size().
flat_map(const flat_map & x,const allocator_type & a)459 BOOST_CONTAINER_FORCEINLINE flat_map(const flat_map& x, const allocator_type &a)
460 : m_flat_tree(x.m_flat_tree, dtl::force<const impl_allocator_type>(a))
461 {}
462
463 //! <b>Effects</b>: Move constructs a flat_map using the specified allocator.
464 //! Constructs *this using x's resources.
465 //!
466 //! <b>Complexity</b>: Constant if x.get_allocator() == a, linear otherwise.
flat_map(BOOST_RV_REF (flat_map)x,const allocator_type & a)467 BOOST_CONTAINER_FORCEINLINE flat_map(BOOST_RV_REF(flat_map) x, const allocator_type &a)
468 : m_flat_tree(boost::move(x.m_flat_tree), dtl::force<const impl_allocator_type>(a))
469 {}
470
471 //! <b>Effects</b>: Makes *this a copy of x.
472 //!
473 //! <b>Complexity</b>: Linear in x.size().
operator =(BOOST_COPY_ASSIGN_REF (flat_map)x)474 BOOST_CONTAINER_FORCEINLINE flat_map& operator=(BOOST_COPY_ASSIGN_REF(flat_map) x)
475 { m_flat_tree = x.m_flat_tree; return *this; }
476
477 //! <b>Effects</b>: Move constructs a flat_map.
478 //! Constructs *this using x's resources.
479 //!
480 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
481 //! is false and (allocation throws or value_type's move constructor throws)
482 //!
483 //! <b>Complexity</b>: Constant if allocator_traits_type::
484 //! propagate_on_container_move_assignment is true or
485 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
operator =(BOOST_RV_REF (flat_map)x)486 BOOST_CONTAINER_FORCEINLINE flat_map& operator=(BOOST_RV_REF(flat_map) x)
487 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
488 allocator_traits_type::is_always_equal::value) &&
489 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
490 { m_flat_tree = boost::move(x.m_flat_tree); return *this; }
491
492 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
493 //! <b>Effects</b>: Assign elements from il to *this
operator =(std::initializer_list<value_type> il)494 flat_map& operator=(std::initializer_list<value_type> il)
495 {
496 this->clear();
497 this->insert(il.begin(), il.end());
498 return *this;
499 }
500 #endif
501
502 //! <b>Effects</b>: Returns a copy of the allocator that
503 //! was passed to the object's constructor.
504 //!
505 //! <b>Complexity</b>: Constant.
get_allocator() const506 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
507 { return dtl::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
508
509 //! <b>Effects</b>: Returns a reference to the internal allocator.
510 //!
511 //! <b>Throws</b>: Nothing
512 //!
513 //! <b>Complexity</b>: Constant.
514 //!
515 //! <b>Note</b>: Non-standard extension.
get_stored_allocator()516 BOOST_CONTAINER_FORCEINLINE get_stored_allocator_noconst_return_t get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
517 {
518 impl_get_stored_allocator_noconst_return_t r = m_flat_tree.get_stored_allocator();
519 return dtl::force<stored_allocator_type>(r);
520 }
521
522 //! <b>Effects</b>: Returns a reference to the internal allocator.
523 //!
524 //! <b>Throws</b>: Nothing
525 //!
526 //! <b>Complexity</b>: Constant.
527 //!
528 //! <b>Note</b>: Non-standard extension.
get_stored_allocator() const529 BOOST_CONTAINER_FORCEINLINE get_stored_allocator_const_return_t get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
530 {
531 impl_get_stored_allocator_const_return_t r = m_flat_tree.get_stored_allocator();
532 return dtl::force<const stored_allocator_type>(r);
533 }
534
535 //////////////////////////////////////////////
536 //
537 // iterators
538 //
539 //////////////////////////////////////////////
540
541 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
542 //!
543 //! <b>Throws</b>: Nothing.
544 //!
545 //! <b>Complexity</b>: Constant.
begin()546 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
547 { return dtl::force_copy<iterator>(m_flat_tree.begin()); }
548
549 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
550 //!
551 //! <b>Throws</b>: Nothing.
552 //!
553 //! <b>Complexity</b>: Constant.
begin() const554 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
555 { return dtl::force_copy<const_iterator>(m_flat_tree.begin()); }
556
557 //! <b>Effects</b>: Returns an iterator to the end of the container.
558 //!
559 //! <b>Throws</b>: Nothing.
560 //!
561 //! <b>Complexity</b>: Constant.
end()562 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW
563 { return dtl::force_copy<iterator>(m_flat_tree.end()); }
564
565 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
566 //!
567 //! <b>Throws</b>: Nothing.
568 //!
569 //! <b>Complexity</b>: Constant.
end() const570 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
571 { return dtl::force_copy<const_iterator>(m_flat_tree.end()); }
572
573 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
574 //! of the reversed container.
575 //!
576 //! <b>Throws</b>: Nothing.
577 //!
578 //! <b>Complexity</b>: Constant.
rbegin()579 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
580 { return dtl::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
581
582 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
583 //! of the reversed container.
584 //!
585 //! <b>Throws</b>: Nothing.
586 //!
587 //! <b>Complexity</b>: Constant.
rbegin() const588 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
589 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
590
591 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
592 //! of the reversed container.
593 //!
594 //! <b>Throws</b>: Nothing.
595 //!
596 //! <b>Complexity</b>: Constant.
rend()597 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
598 { return dtl::force_copy<reverse_iterator>(m_flat_tree.rend()); }
599
600 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
601 //! of the reversed container.
602 //!
603 //! <b>Throws</b>: Nothing.
604 //!
605 //! <b>Complexity</b>: Constant.
rend() const606 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
607 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
608
609 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
610 //!
611 //! <b>Throws</b>: Nothing.
612 //!
613 //! <b>Complexity</b>: Constant.
cbegin() const614 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
615 { return dtl::force_copy<const_iterator>(m_flat_tree.cbegin()); }
616
617 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
618 //!
619 //! <b>Throws</b>: Nothing.
620 //!
621 //! <b>Complexity</b>: Constant.
cend() const622 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
623 { return dtl::force_copy<const_iterator>(m_flat_tree.cend()); }
624
625 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
626 //! of the reversed container.
627 //!
628 //! <b>Throws</b>: Nothing.
629 //!
630 //! <b>Complexity</b>: Constant.
crbegin() const631 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
632 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
633
634 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
635 //! of the reversed container.
636 //!
637 //! <b>Throws</b>: Nothing.
638 //!
639 //! <b>Complexity</b>: Constant.
crend() const640 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
641 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
642
643 //////////////////////////////////////////////
644 //
645 // capacity
646 //
647 //////////////////////////////////////////////
648
649 //! <b>Effects</b>: Returns true if the container contains no elements.
650 //!
651 //! <b>Throws</b>: Nothing.
652 //!
653 //! <b>Complexity</b>: Constant.
empty() const654 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
655 { return m_flat_tree.empty(); }
656
657 //! <b>Effects</b>: Returns the number of the elements contained in the container.
658 //!
659 //! <b>Throws</b>: Nothing.
660 //!
661 //! <b>Complexity</b>: Constant.
size() const662 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
663 { return m_flat_tree.size(); }
664
665 //! <b>Effects</b>: Returns the largest possible size of the container.
666 //!
667 //! <b>Throws</b>: Nothing.
668 //!
669 //! <b>Complexity</b>: Constant.
max_size() const670 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
671 { return m_flat_tree.max_size(); }
672
673 //! <b>Effects</b>: Number of elements for which memory has been allocated.
674 //! capacity() is always greater than or equal to size().
675 //!
676 //! <b>Throws</b>: Nothing.
677 //!
678 //! <b>Complexity</b>: Constant.
capacity() const679 BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
680 { return m_flat_tree.capacity(); }
681
682 //! <b>Effects</b>: If n is less than or equal to capacity(), or the
683 //! underlying container has no `reserve` member, this call has no
684 //! effect. Otherwise, it is a request for allocation of additional memory.
685 //! If the request is successful, then capacity() is greater than or equal to
686 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
687 //!
688 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
689 //!
690 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
691 //! to values might be invalidated.
reserve(size_type cnt)692 BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
693 { m_flat_tree.reserve(cnt); }
694
695 //! <b>Effects</b>: Tries to deallocate the excess of memory created
696 // with previous allocations. The size of the vector is unchanged
697 //!
698 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
699 //!
700 //! <b>Complexity</b>: Linear to size().
shrink_to_fit()701 BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
702 { m_flat_tree.shrink_to_fit(); }
703
704 //////////////////////////////////////////////
705 //
706 // element access
707 //
708 //////////////////////////////////////////////
709
710 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
711 //! Effects: If there is no key equivalent to x in the flat_map, inserts
712 //! value_type(x, T()) into the flat_map.
713 //!
714 //! Returns: A reference to the mapped_type corresponding to x in *this.
715 //!
716 //! Complexity: Logarithmic.
717 mapped_type &operator[](const key_type& k);
718
719 //! Effects: If there is no key equivalent to x in the flat_map, inserts
720 //! value_type(move(x), T()) into the flat_map (the key is move-constructed)
721 //!
722 //! Returns: A reference to the mapped_type corresponding to x in *this.
723 //!
724 //! Complexity: Logarithmic.
725 mapped_type &operator[](key_type &&k) ;
726 #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
727 //in compilers like GCC 3.4, we can't catch temporaries
operator [](const key_type & k)728 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); }
operator [](BOOST_RV_REF (key_type)k)729 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); }
730 #else
731 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
732 #endif
733
734 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
735 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
736 //! as if by insert, constructing it from value_type(k, forward<M>(obj)).
737 //!
738 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
739 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
740 //! references obtained to that element before it was extracted become valid.
741 //!
742 //! Returns: The bool component is true if the insertion took place and false if the assignment
743 //! took place. The iterator component is pointing at the element that was inserted or updated.
744 //!
745 //! Complexity: Logarithmic in the size of the container.
746 template <class M>
insert_or_assign(const key_type & k,BOOST_FWD_REF (M)obj)747 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj)
748 {
749 return dtl::force_copy< std::pair<iterator, bool> >
750 (this->m_flat_tree.insert_or_assign
751 ( impl_const_iterator(), k, ::boost::forward<M>(obj))
752 );
753 }
754
755 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
756 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
757 //! as if by insert, constructing it from value_type(k, move(obj)).
758 //!
759 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
760 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
761 //! references obtained to that element before it was extracted become valid.
762 //!
763 //! Returns: The bool component is true if the insertion took place and false if the assignment
764 //! took place. The iterator component is pointing at the element that was inserted or updated.
765 //!
766 //! Complexity: Logarithmic in the size of the container.
767 template <class M>
insert_or_assign(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)768 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
769 {
770 return dtl::force_copy< std::pair<iterator, bool> >
771 (this->m_flat_tree.insert_or_assign
772 ( impl_const_iterator(), ::boost::move(k), ::boost::forward<M>(obj))
773 );
774 }
775
776 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
777 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
778 //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element
779 //! to the container as close as possible to the position just before hint.
780 //!
781 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
782 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
783 //! references obtained to that element before it was extracted become valid.
784 //!
785 //! Returns: The bool component is true if the insertion took place and false if the assignment
786 //! took place. The iterator component is pointing at the element that was inserted or updated.
787 //!
788 //! Complexity: Logarithmic in the size of the container in general, but amortized constant if
789 //! the new element is inserted just before hint.
790 template <class M>
insert_or_assign(const_iterator hint,const key_type & k,BOOST_FWD_REF (M)obj)791 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
792 {
793 return dtl::force_copy< std::pair<iterator, bool> >
794 (this->m_flat_tree.insert_or_assign
795 ( dtl::force_copy<impl_const_iterator>(hint)
796 , k, ::boost::forward<M>(obj))
797 );
798 }
799
800 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
801 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
802 //! as if by insert, constructing it from value_type(k, move(obj)) and the new element
803 //! to the container as close as possible to the position just before hint.
804 //!
805 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
806 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
807 //! references obtained to that element before it was extracted become valid.
808 //!
809 //! Returns: The bool component is true if the insertion took place and false if the assignment
810 //! took place. The iterator component is pointing at the element that was inserted or updated.
811 //!
812 //! Complexity: Logarithmic in the size of the container in general, but amortized constant if
813 //! the new element is inserted just before hint.
814 template <class M>
insert_or_assign(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)815 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
816 {
817 return dtl::force_copy< std::pair<iterator, bool> >
818 (this->m_flat_tree.insert_or_assign
819 ( dtl::force_copy<impl_const_iterator>(hint)
820 , ::boost::move(k), ::boost::forward<M>(obj))
821 );
822 }
823
824 //! @copydoc ::boost::container::flat_set::nth(size_type)
nth(size_type n)825 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
826 { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); }
827
828 //! @copydoc ::boost::container::flat_set::nth(size_type) const
nth(size_type n) const829 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
830 { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); }
831
832 //! @copydoc ::boost::container::flat_set::index_of(iterator)
index_of(iterator p)833 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
834 { return m_flat_tree.index_of(dtl::force_copy<impl_iterator>(p)); }
835
836 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
index_of(const_iterator p) const837 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
838 { return m_flat_tree.index_of(dtl::force_copy<impl_const_iterator>(p)); }
839
840 //! Returns: A reference to the element whose key is equivalent to x.
841 //!
842 //! Throws: An exception object of type out_of_range if no such element is present.
843 //!
844 //! Complexity: logarithmic.
at(const key_type & k)845 T& at(const key_type& k)
846 {
847 iterator i = this->find(k);
848 if(i == this->end()){
849 throw_out_of_range("flat_map::at key not found");
850 }
851 return i->second;
852 }
853
854 //! Returns: A reference to the element whose key is equivalent to x.
855 //!
856 //! Throws: An exception object of type out_of_range if no such element is present.
857 //!
858 //! Complexity: logarithmic.
at(const key_type & k) const859 const T& at(const key_type& k) const
860 {
861 const_iterator i = this->find(k);
862 if(i == this->end()){
863 throw_out_of_range("flat_map::at key not found");
864 }
865 return i->second;
866 }
867
868 //////////////////////////////////////////////
869 //
870 // modifiers
871 //
872 //////////////////////////////////////////////
873
874 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
875
876 //! <b>Effects</b>: Inserts an object x of type T constructed with
877 //! std::forward<Args>(args)... if and only if there is no element in the container
878 //! with key equivalent to the key of x.
879 //!
880 //! <b>Returns</b>: The bool component of the returned pair is true if and only
881 //! if the insertion takes place, and the iterator component of the pair
882 //! points to the element with key equivalent to the key of x.
883 //!
884 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
885 //! to the elements with bigger keys than x.
886 //!
887 //! <b>Note</b>: If an element is inserted it might invalidate elements.
888 template <class... Args>
emplace(BOOST_FWD_REF (Args)...args)889 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
890 { return dtl::force_copy< std::pair<iterator, bool> >(m_flat_tree.emplace_unique(boost::forward<Args>(args)...)); }
891
892 //! <b>Effects</b>: Inserts an object of type T constructed with
893 //! std::forward<Args>(args)... in the container if and only if there is
894 //! no element in the container with key equivalent to the key of x.
895 //! p is a hint pointing to where the insert should start to search.
896 //!
897 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
898 //! to the key of x.
899 //!
900 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
901 //! right before p) plus insertion linear to the elements with bigger keys than x.
902 //!
903 //! <b>Note</b>: If an element is inserted it might invalidate elements.
904 template <class... Args>
emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)905 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
906 {
907 return dtl::force_copy<iterator>
908 (m_flat_tree.emplace_hint_unique( dtl::force_copy<impl_const_iterator>(hint)
909 , boost::forward<Args>(args)...));
910 }
911
912 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
913 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
914 //!
915 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
916 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
917 //! forward_as_tuple(forward<Args>(args)...).
918 //!
919 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
920 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
921 //!
922 //! <b>Complexity</b>: Logarithmic.
923 template <class... Args>
try_emplace(const key_type & k,BOOST_FWD_REF (Args)...args)924 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args)
925 {
926 return dtl::force_copy< std::pair<iterator, bool> >(
927 m_flat_tree.try_emplace(impl_const_iterator(), k, boost::forward<Args>(args)...));
928 }
929
930 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
931 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
932 //!
933 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
934 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
935 //! forward_as_tuple(forward<Args>(args)...).
936 //!
937 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
938 //!
939 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
940 //! is inserted right before p.
941 template <class... Args>
try_emplace(const_iterator hint,const key_type & k,BOOST_FWD_REF (Args)...args)942 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args)
943 {
944 return dtl::force_copy<iterator>(m_flat_tree.try_emplace
945 (dtl::force_copy<impl_const_iterator>(hint), k, boost::forward<Args>(args)...).first);
946 }
947
948 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
949 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
950 //!
951 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
952 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
953 //! forward_as_tuple(forward<Args>(args)...).
954 //!
955 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
956 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
957 //!
958 //! <b>Complexity</b>: Logarithmic.
959 template <class... Args>
try_emplace(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)960 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
961 {
962 return dtl::force_copy< std::pair<iterator, bool> >
963 (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k), boost::forward<Args>(args)...));
964 }
965
966 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
967 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
968 //!
969 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
970 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
971 //! forward_as_tuple(forward<Args>(args)...).
972 //!
973 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
974 //!
975 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
976 //! is inserted right before p.
977 template <class... Args>
try_emplace(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)978 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
979 {
980 return dtl::force_copy<iterator>
981 (m_flat_tree.try_emplace(dtl::force_copy
982 <impl_const_iterator>(hint), boost::move(k), boost::forward<Args>(args)...).first);
983 }
984
985 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
986
987 #define BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE(N) \
988 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
989 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
990 {\
991 return dtl::force_copy< std::pair<iterator, bool> >\
992 (m_flat_tree.emplace_unique(BOOST_MOVE_FWD##N));\
993 }\
994 \
995 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
996 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
997 {\
998 return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_unique\
999 (dtl::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1000 }\
1001 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1002 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1003 {\
1004 return dtl::force_copy< std::pair<iterator, bool> >\
1005 (m_flat_tree.try_emplace(impl_const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1006 }\
1007 \
1008 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1009 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1010 { return dtl::force_copy<iterator>(m_flat_tree.try_emplace\
1011 (dtl::force_copy<impl_const_iterator>(hint), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\
1012 \
1013 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1014 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1015 {\
1016 return dtl::force_copy< std::pair<iterator, bool> >\
1017 (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1018 }\
1019 \
1020 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1021 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1022 { return dtl::force_copy<iterator>(m_flat_tree.try_emplace\
1023 (dtl::force_copy<impl_const_iterator>(hint), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\
1024 //
BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)1025 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)
1026 #undef BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE
1027
1028 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1029
1030 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
1031 //! with key equivalent to the key of x.
1032 //!
1033 //! <b>Returns</b>: The bool component of the returned pair is true if and only
1034 //! if the insertion takes place, and the iterator component of the pair
1035 //! points to the element with key equivalent to the key of x.
1036 //!
1037 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1038 //! to the elements with bigger keys than x.
1039 //!
1040 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1041 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x)
1042 { return dtl::force_copy<std::pair<iterator,bool> >(
1043 m_flat_tree.insert_unique(dtl::force<const impl_value_type>(x))); }
1044
1045 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
1046 //! only if there is no element in the container with key equivalent to the key of x.
1047 //!
1048 //! <b>Returns</b>: The bool component of the returned pair is true if and only
1049 //! if the insertion takes place, and the iterator component of the pair
1050 //! points to the element with key equivalent to the key of x.
1051 //!
1052 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1053 //! to the elements with bigger keys than x.
1054 //!
1055 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (value_type)x)1056 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
1057 { return dtl::force_copy<std::pair<iterator,bool> >(
1058 m_flat_tree.insert_unique(boost::move(dtl::force<impl_value_type>(x)))); }
1059
1060 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
1061 //! only if there is no element in the container with key equivalent to the key of x.
1062 //!
1063 //! <b>Returns</b>: The bool component of the returned pair is true if and only
1064 //! if the insertion takes place, and the iterator component of the pair
1065 //! points to the element with key equivalent to the key of x.
1066 //!
1067 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1068 //! to the elements with bigger keys than x.
1069 //!
1070 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (movable_value_type)x)1071 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
1072 {
1073 return dtl::force_copy<std::pair<iterator,bool> >
1074 (m_flat_tree.insert_unique(boost::move(x)));
1075 }
1076
1077 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
1078 //! no element in the container with key equivalent to the key of x.
1079 //! p is a hint pointing to where the insert should start to search.
1080 //!
1081 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1082 //! to the key of x.
1083 //!
1084 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1085 //! right before p) plus insertion linear to the elements with bigger keys than x.
1086 //!
1087 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,const value_type & x)1088 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
1089 {
1090 return dtl::force_copy<iterator>(
1091 m_flat_tree.insert_unique( dtl::force_copy<impl_const_iterator>(p)
1092 , dtl::force<const impl_value_type>(x)));
1093 }
1094
1095 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
1096 //! p is a hint pointing to where the insert should start to search.
1097 //!
1098 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
1099 //!
1100 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1101 //! right before p) plus insertion linear to the elements with bigger keys than x.
1102 //!
1103 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (value_type)x)1104 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
1105 {
1106 return dtl::force_copy<iterator>
1107 (m_flat_tree.insert_unique( dtl::force_copy<impl_const_iterator>(p)
1108 , boost::move(dtl::force<impl_value_type>(x))));
1109 }
1110
1111 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
1112 //! p is a hint pointing to where the insert should start to search.
1113 //!
1114 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
1115 //!
1116 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1117 //! right before p) plus insertion linear to the elements with bigger keys than x.
1118 //!
1119 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)1120 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
1121 {
1122 return dtl::force_copy<iterator>(
1123 m_flat_tree.insert_unique(dtl::force_copy<impl_const_iterator>(p), boost::move(x)));
1124 }
1125
1126 //! <b>Requires</b>: first, last are not iterators into *this.
1127 //!
1128 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1129 //! if there is no element with key equivalent to the key of that element.
1130 //!
1131 //! <b>Complexity</b>: N log(size()+N).
1132 //!
1133 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1134 template <class InputIterator>
insert(InputIterator first,InputIterator last)1135 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1136 { m_flat_tree.insert_unique(first, last); }
1137
1138 //! <b>Requires</b>: first, last are not iterators into *this.
1139 //!
1140 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
1141 //! unique values.
1142 //!
1143 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1144 //! if there is no element with key equivalent to the key of that element. This
1145 //! function is more efficient than the normal range creation for ordered ranges.
1146 //!
1147 //! <b>Complexity</b>: Linear.
1148 //!
1149 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1150 //!
1151 //! <b>Note</b>: Non-standard extension.
1152 template <class InputIterator>
insert(ordered_unique_range_t,InputIterator first,InputIterator last)1153 BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
1154 { m_flat_tree.insert_unique(ordered_unique_range, first, last); }
1155
1156 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1157 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1158 //! if there is no element with key equivalent to the key of that element.
1159 //!
1160 //! <b>Complexity</b>: N log(N).
1161 //!
1162 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(std::initializer_list<value_type> il)1163 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1164 {
1165 m_flat_tree.insert_unique( dtl::force<impl_initializer_list>(il).begin()
1166 , dtl::force<impl_initializer_list>(il).end());
1167 }
1168
1169 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
1170 //! unique values.
1171 //!
1172 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1173 //! if there is no element with key equivalent to the key of that element. This
1174 //! function is more efficient than the normal range creation for ordered ranges.
1175 //!
1176 //! <b>Complexity</b>: Linear.
1177 //!
1178 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1179 //!
1180 //! <b>Note</b>: Non-standard extension.
insert(ordered_unique_range_t,std::initializer_list<value_type> il)1181 BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
1182 {
1183 m_flat_tree.insert_unique(ordered_unique_range
1184 , dtl::force<impl_initializer_list>(il).begin()
1185 , dtl::force<impl_initializer_list>(il).end());
1186 }
1187 #endif
1188
1189 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1190 //!
1191 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
1192 //! the comparison object of *this. If there is an element in a with key equivalent to the
1193 //! key of an element from source, then that element is not extracted from source.
1194 //!
1195 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1196 //! to those same elements but as members of *this. Iterators referring to the transferred
1197 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
1198 //! not into source.
1199 //!
1200 //! <b>Throws</b>: Nothing unless the comparison object throws.
1201 //!
1202 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
1203 template<class C2>
merge(flat_map<Key,T,C2,AllocatorOrContainer> & source)1204 BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, AllocatorOrContainer>& source)
1205 { m_flat_tree.merge_unique(source.tree()); }
1206
1207 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1208 template<class C2>
merge(BOOST_RV_REF_BEG flat_map<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)1209 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
1210 { return this->merge(static_cast<flat_map<Key, T, C2, AllocatorOrContainer>&>(source)); }
1211
1212 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1213 template<class C2>
merge(flat_multimap<Key,T,C2,AllocatorOrContainer> & source)1214 BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, AllocatorOrContainer>& source)
1215 { m_flat_tree.merge_unique(source.tree()); }
1216
1217 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1218 template<class C2>
merge(BOOST_RV_REF_BEG flat_multimap<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)1219 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
1220 { return this->merge(static_cast<flat_multimap<Key, T, C2, AllocatorOrContainer>&>(source)); }
1221
1222 //! <b>Effects</b>: Erases the element pointed to by p.
1223 //!
1224 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1225 //! following q prior to the element being erased. If no such element exists,
1226 //! returns end().
1227 //!
1228 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
1229 //!
1230 //! <b>Note</b>: Invalidates elements with keys
1231 //! not less than the erased element.
erase(const_iterator p)1232 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p)
1233 {
1234 return dtl::force_copy<iterator>
1235 (m_flat_tree.erase(dtl::force_copy<impl_const_iterator>(p)));
1236 }
1237
1238 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1239 //!
1240 //! <b>Returns</b>: Returns the number of erased elements.
1241 //!
1242 //! <b>Complexity</b>: Logarithmic search time plus erasure time
1243 //! linear to the elements with bigger keys.
erase(const key_type & x)1244 BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x)
1245 { return m_flat_tree.erase(x); }
1246
1247 //! <b>Effects</b>: Erases all the elements in the range [first, last).
1248 //!
1249 //! <b>Returns</b>: Returns last.
1250 //!
1251 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
1252 //!
1253 //! <b>Complexity</b>: Logarithmic search time plus erasure time
1254 //! linear to the elements with bigger keys.
erase(const_iterator first,const_iterator last)1255 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
1256 {
1257 return dtl::force_copy<iterator>(
1258 m_flat_tree.erase( dtl::force_copy<impl_const_iterator>(first)
1259 , dtl::force_copy<impl_const_iterator>(last)));
1260 }
1261
1262 //! <b>Effects</b>: Swaps the contents of *this and x.
1263 //!
1264 //! <b>Throws</b>: Nothing.
1265 //!
1266 //! <b>Complexity</b>: Constant.
swap(flat_map & x)1267 BOOST_CONTAINER_FORCEINLINE void swap(flat_map& x)
1268 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1269 && boost::container::dtl::is_nothrow_swappable<Compare>::value )
1270 { m_flat_tree.swap(x.m_flat_tree); }
1271
1272 //! <b>Effects</b>: erase(a.begin(),a.end()).
1273 //!
1274 //! <b>Postcondition</b>: size() == 0.
1275 //!
1276 //! <b>Complexity</b>: linear in size().
clear()1277 BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW
1278 { m_flat_tree.clear(); }
1279
1280 //////////////////////////////////////////////
1281 //
1282 // observers
1283 //
1284 //////////////////////////////////////////////
1285
1286 //! <b>Effects</b>: Returns the comparison object out
1287 //! of which a was constructed.
1288 //!
1289 //! <b>Complexity</b>: Constant.
key_comp() const1290 BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
1291 { return dtl::force_copy<key_compare>(m_flat_tree.key_comp()); }
1292
1293 //! <b>Effects</b>: Returns an object of value_compare constructed out
1294 //! of the comparison object.
1295 //!
1296 //! <b>Complexity</b>: Constant.
value_comp() const1297 BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
1298 { return value_compare(dtl::force_copy<key_compare>(m_flat_tree.key_comp())); }
1299
1300 //////////////////////////////////////////////
1301 //
1302 // map operations
1303 //
1304 //////////////////////////////////////////////
1305
1306 //! <b>Returns</b>: An iterator pointing to an element with the key
1307 //! equivalent to x, or end() if such an element is not found.
1308 //!
1309 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)1310 BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& x)
1311 { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
1312
1313 //! <b>Returns</b>: A const_iterator pointing to an element with the key
1314 //! equivalent to x, or end() if such an element is not found.
1315 //!
1316 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const1317 BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const
1318 { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
1319
1320 //! <b>Requires</b>: This overload is available only if
1321 //! key_compare::is_transparent exists.
1322 //!
1323 //! <b>Returns</b>: An iterator pointing to an element with the key
1324 //! equivalent to x, or end() if such an element is not found.
1325 //!
1326 //! <b>Complexity</b>: Logarithmic.
1327 template<class K>
find(const K & x)1328 BOOST_CONTAINER_FORCEINLINE iterator find(const K& x)
1329 { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
1330
1331 //! <b>Requires</b>: This overload is available only if
1332 //! key_compare::is_transparent exists.
1333 //!
1334 //! <b>Returns</b>: A const_iterator pointing to an element with the key
1335 //! equivalent to x, or end() if such an element is not found.
1336 //!
1337 //! <b>Complexity</b>: Logarithmic.
1338 template<class K>
find(const K & x) const1339 BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const
1340 { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
1341
1342 //! <b>Returns</b>: The number of elements with key equivalent to x.
1343 //!
1344 //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const1345 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
1346 { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }
1347
1348 //! <b>Requires</b>: This overload is available only if
1349 //! key_compare::is_transparent exists.
1350 //!
1351 //! <b>Returns</b>: The number of elements with key equivalent to x.
1352 //!
1353 //! <b>Complexity</b>: log(size())+count(k)
1354 template<class K>
count(const K & x) const1355 BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
1356 { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }
1357
1358 //! <b>Returns</b>: Returns true if there is an element with key
1359 //! equivalent to key in the container, otherwise false.
1360 //!
1361 //! <b>Complexity</b>: log(size()).
contains(const key_type & x) const1362 bool contains(const key_type& x) const
1363 { return m_flat_tree.find(x) != m_flat_tree.end(); }
1364
1365 //! <b>Requires</b>: This overload is available only if
1366 //! key_compare::is_transparent exists.
1367 //!
1368 //! <b>Returns</b>: Returns true if there is an element with key
1369 //! equivalent to key in the container, otherwise false.
1370 //!
1371 //! <b>Complexity</b>: log(size()).
1372 template<typename K>
contains(const K & x) const1373 bool contains(const K& x) const
1374 { return m_flat_tree.find(x) != m_flat_tree.end(); }
1375
1376 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1377 //! than k, or a.end() if such an element is not found.
1378 //!
1379 //! <b>Complexity</b>: Logarithmic.
lower_bound(const key_type & x)1380 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x)
1381 { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
1382
1383 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1384 //! less than k, or a.end() if such an element is not found.
1385 //!
1386 //! <b>Complexity</b>: Logarithmic.
lower_bound(const key_type & x) const1387 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const
1388 { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
1389
1390 //! <b>Requires</b>: This overload is available only if
1391 //! key_compare::is_transparent exists.
1392 //!
1393 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1394 //! than k, or a.end() if such an element is not found.
1395 //!
1396 //! <b>Complexity</b>: Logarithmic.
1397 template<class K>
lower_bound(const K & x)1398 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x)
1399 { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
1400
1401 //! <b>Requires</b>: This overload is available only if
1402 //! key_compare::is_transparent exists.
1403 //!
1404 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1405 //! less than k, or a.end() if such an element is not found.
1406 //!
1407 //! <b>Complexity</b>: Logarithmic.
1408 template<class K>
lower_bound(const K & x) const1409 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const
1410 { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
1411
1412 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1413 //! than x, or end() if such an element is not found.
1414 //!
1415 //! <b>Complexity</b>: Logarithmic.
upper_bound(const key_type & x)1416 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& x)
1417 { return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
1418
1419 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1420 //! less than x, or end() if such an element is not found.
1421 //!
1422 //! <b>Complexity</b>: Logarithmic.
upper_bound(const key_type & x) const1423 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const
1424 { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
1425
1426 //! <b>Requires</b>: This overload is available only if
1427 //! key_compare::is_transparent exists.
1428 //!
1429 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1430 //! than x, or end() if such an element is not found.
1431 //!
1432 //! <b>Complexity</b>: Logarithmic.
1433 template<class K>
upper_bound(const K & x)1434 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x)
1435 { return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
1436
1437 //! <b>Requires</b>: This overload is available only if
1438 //! key_compare::is_transparent exists.
1439 //!
1440 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1441 //! less than x, or end() if such an element is not found.
1442 //!
1443 //! <b>Complexity</b>: Logarithmic.
1444 template<class K>
upper_bound(const K & x) const1445 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const
1446 { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
1447
1448 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1449 //!
1450 //! <b>Complexity</b>: Logarithmic.
equal_range(const key_type & x)1451 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
1452 { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); }
1453
1454 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1455 //!
1456 //! <b>Complexity</b>: Logarithmic.
equal_range(const key_type & x) const1457 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
1458 { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }
1459
1460 //! <b>Requires</b>: This overload is available only if
1461 //! key_compare::is_transparent exists.
1462 //!
1463 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1464 //!
1465 //! <b>Complexity</b>: Logarithmic.
1466 template<class K>
equal_range(const K & x)1467 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
1468 { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); }
1469
1470 //! <b>Requires</b>: This overload is available only if
1471 //! key_compare::is_transparent exists.
1472 //!
1473 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1474 //!
1475 //! <b>Complexity</b>: Logarithmic.
1476 template<class K>
equal_range(const K & x) const1477 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const
1478 { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }
1479
1480 //! <b>Effects</b>: Extracts the internal sequence container.
1481 //!
1482 //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
1483 //!
1484 //! <b>Postcondition</b>: this->empty()
1485 //!
1486 //! <b>Throws</b>: If secuence_type's move constructor throws
extract_sequence()1487 BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
1488 {
1489 return boost::move(dtl::force<sequence_type>(m_flat_tree.get_sequence_ref()));
1490 }
1491
1492 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1493 //! one passed externally using the move assignment. Erases non-unique elements.
1494 //!
1495 //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
1496 //!
1497 //! <b>Throws</b>: If the comparison or the move constructor throws
adopt_sequence(BOOST_RV_REF (sequence_type)seq)1498 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
1499 { this->m_flat_tree.adopt_sequence_unique(boost::move(dtl::force<impl_sequence_type>(seq))); }
1500
1501 //! <b>Requires</b>: seq shall be ordered according to this->compare()
1502 //! and shall contain unique elements.
1503 //!
1504 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1505 //! one passed externally using the move assignment.
1506 //!
1507 //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
1508 //!
1509 //! <b>Throws</b>: If the move assignment throws
adopt_sequence(ordered_unique_range_t,BOOST_RV_REF (sequence_type)seq)1510 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
1511 { this->m_flat_tree.adopt_sequence_unique(ordered_unique_range_t(), boost::move(dtl::force<impl_sequence_type>(seq))); }
1512
1513 //! <b>Effects</b>: Returns true if x and y are equal
1514 //!
1515 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator ==(const flat_map & x,const flat_map & y)1516 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_map& x, const flat_map& y)
1517 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1518
1519 //! <b>Effects</b>: Returns true if x and y are unequal
1520 //!
1521 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator !=(const flat_map & x,const flat_map & y)1522 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_map& x, const flat_map& y)
1523 { return !(x == y); }
1524
1525 //! <b>Effects</b>: Returns true if x is less than y
1526 //!
1527 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <(const flat_map & x,const flat_map & y)1528 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_map& x, const flat_map& y)
1529 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1530
1531 //! <b>Effects</b>: Returns true if x is greater than y
1532 //!
1533 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >(const flat_map & x,const flat_map & y)1534 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_map& x, const flat_map& y)
1535 { return y < x; }
1536
1537 //! <b>Effects</b>: Returns true if x is equal or less than y
1538 //!
1539 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <=(const flat_map & x,const flat_map & y)1540 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_map& x, const flat_map& y)
1541 { return !(y < x); }
1542
1543 //! <b>Effects</b>: Returns true if x is equal or greater than y
1544 //!
1545 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >=(const flat_map & x,const flat_map & y)1546 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_map& x, const flat_map& y)
1547 { return !(x < y); }
1548
1549 //! <b>Effects</b>: x.swap(y)
1550 //!
1551 //! <b>Complexity</b>: Constant.
swap(flat_map & x,flat_map & y)1552 BOOST_CONTAINER_FORCEINLINE friend void swap(flat_map& x, flat_map& y)
1553 { x.swap(y); }
1554
1555 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1556 private:
priv_subscript(const key_type & k)1557 mapped_type &priv_subscript(const key_type& k)
1558 {
1559 iterator i = lower_bound(k);
1560 // i->first is greater than or equivalent to k.
1561 if (i == end() || key_comp()(k, (*i).first)){
1562 dtl::value_init<mapped_type> m;
1563 i = insert(i, impl_value_type(k, ::boost::move(m.m_t)));
1564 }
1565 return (*i).second;
1566 }
priv_subscript(BOOST_RV_REF (key_type)mk)1567 mapped_type &priv_subscript(BOOST_RV_REF(key_type) mk)
1568 {
1569 key_type &k = mk;
1570 iterator i = lower_bound(k);
1571 // i->first is greater than or equivalent to k.
1572 if (i == end() || key_comp()(k, (*i).first)){
1573 dtl::value_init<mapped_type> m;
1574 i = insert(i, impl_value_type(boost::move(k), ::boost::move(m.m_t)));
1575 }
1576 return (*i).second;
1577 }
1578 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1579 };
1580
1581 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1582
1583 template <typename InputIterator>
1584 flat_map(InputIterator, InputIterator) ->
1585 flat_map< it_based_non_const_first_type_t<InputIterator>
1586 , it_based_second_type_t<InputIterator>>;
1587
1588 template < typename InputIterator, typename AllocatorOrCompare>
1589 flat_map(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1590 flat_map< it_based_non_const_first_type_t<InputIterator>
1591 , it_based_second_type_t<InputIterator>
1592 , typename dtl::if_c< // Compare
1593 dtl::is_allocator<AllocatorOrCompare>::value
1594 , std::less<it_based_non_const_first_type_t<InputIterator>>
1595 , AllocatorOrCompare
1596 >::type
1597 , typename dtl::if_c< // Allocator
1598 dtl::is_allocator<AllocatorOrCompare>::value
1599 , AllocatorOrCompare
1600 , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1601 >::type
1602 >;
1603
1604 template < typename InputIterator, typename Compare, typename Allocator
1605 , typename = dtl::require_nonallocator_t<Compare>
1606 , typename = dtl::require_allocator_t<Allocator>>
1607 flat_map(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1608 flat_map< it_based_non_const_first_type_t<InputIterator>
1609 , it_based_second_type_t<InputIterator>
1610 , Compare
1611 , Allocator>;
1612
1613 template <typename InputIterator>
1614 flat_map(ordered_unique_range_t, InputIterator, InputIterator) ->
1615 flat_map< it_based_non_const_first_type_t<InputIterator>
1616 , it_based_second_type_t<InputIterator>>;
1617
1618 template < typename InputIterator, typename AllocatorOrCompare>
1619 flat_map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1620 flat_map< it_based_non_const_first_type_t<InputIterator>
1621 , it_based_second_type_t<InputIterator>
1622 , typename dtl::if_c< // Compare
1623 dtl::is_allocator<AllocatorOrCompare>::value
1624 , std::less<it_based_non_const_first_type_t<InputIterator>>
1625 , AllocatorOrCompare
1626 >::type
1627 , typename dtl::if_c< // Allocator
1628 dtl::is_allocator<AllocatorOrCompare>::value
1629 , AllocatorOrCompare
1630 , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1631 >::type
1632 >;
1633
1634 template < typename InputIterator, typename Compare, typename Allocator
1635 , typename = dtl::require_nonallocator_t<Compare>
1636 , typename = dtl::require_allocator_t<Allocator>>
1637 flat_map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1638 flat_map< it_based_non_const_first_type_t<InputIterator>
1639 , it_based_second_type_t<InputIterator>
1640 , Compare
1641 , Allocator>;
1642
1643 #endif
1644
1645 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1646
1647 } //namespace container {
1648
1649 //!has_trivial_destructor_after_move<> == true_type
1650 //!specialization for optimizations
1651 template <class Key, class T, class Compare, class AllocatorOrContainer>
1652 struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, AllocatorOrContainer> >
1653 {
1654 typedef typename ::boost::container::allocator_traits<AllocatorOrContainer>::pointer pointer;
1655 static const bool value = ::boost::has_trivial_destructor_after_move<AllocatorOrContainer>::value &&
1656 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1657 ::boost::has_trivial_destructor_after_move<Compare>::value;
1658 };
1659
1660 namespace container {
1661
1662 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1663
1664 //! A flat_multimap is a kind of associative container that supports equivalent keys
1665 //! (possibly containing multiple copies of the same key value) and provides for
1666 //! fast retrieval of values of another type T based on the keys.
1667 //!
1668 //! A flat_multimap satisfies all of the requirements of a container and of a reversible
1669 //! container and of an associative container. For a
1670 //! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
1671 //! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
1672 //!
1673 //! flat_multimap is similar to std::multimap but it's implemented by as an ordered sequence container.
1674 //! The underlying sequence container is by default <i>vector</i> but it can also work
1675 //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
1676 //!
1677 //! Using vector-like sequence containers means that inserting a new element into a flat_multimap might invalidate
1678 //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
1679 //! container that offers stable pointers and references). Similarly, erasing an element might invalidate
1680 //! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
1681 //!
1682 //! This container provides random-access iterators.
1683 //!
1684 //! \tparam Key is the key_type of the map
1685 //! \tparam Value is the <code>mapped_type</code>
1686 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1687 //! \tparam AllocatorOrContainer is either:
1688 //! - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
1689 //! (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
1690 //! - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
1691 //! sequence container with random-access iterators.
1692 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1693 template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > >
1694 #else
1695 template <class Key, class T, class Compare, class AllocatorOrContainer>
1696 #endif
1697 class flat_multimap
1698 {
1699 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1700 private:
1701 BOOST_COPYABLE_AND_MOVABLE(flat_multimap)
1702 typedef dtl::flat_tree<
1703 std::pair<Key, T>,
1704 dtl::select1st<Key>,
1705 Compare,
1706 AllocatorOrContainer> tree_t;
1707 //This is the real tree stored here. It's based on a movable pair
1708 typedef dtl::flat_tree<
1709 dtl::pair<Key, T>,
1710 dtl::select1st<Key>,
1711 Compare,
1712 typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type
1713 > impl_tree_t;
1714 impl_tree_t m_flat_tree; // flat tree representing flat_map
1715
1716 typedef typename impl_tree_t::value_type impl_value_type;
1717 typedef typename impl_tree_t::const_iterator impl_const_iterator;
1718 typedef typename impl_tree_t::iterator impl_iterator;
1719 typedef typename impl_tree_t::allocator_type impl_allocator_type;
1720 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1721 typedef std::initializer_list<impl_value_type> impl_initializer_list;
1722 #endif
1723
1724 typedef dtl::flat_tree_value_compare
1725 < Compare
1726 , dtl::select1st<Key>
1727 , std::pair<Key, T> > value_compare_t;
1728 typedef typename tree_t::iterator iterator_t;
1729 typedef typename tree_t::const_iterator const_iterator_t;
1730 typedef typename tree_t::reverse_iterator reverse_iterator_t;
1731 typedef typename tree_t::const_reverse_iterator const_reverse_iterator_t;
1732
1733 public:
1734 typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type;
1735 typedef typename impl_tree_t::sequence_type impl_sequence_type;
1736
tree()1737 BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree()
1738 { return m_flat_tree; }
1739
tree() const1740 BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const
1741 { return m_flat_tree; }
1742
1743 private:
1744 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1745
1746 public:
1747
1748 //////////////////////////////////////////////
1749 //
1750 // types
1751 //
1752 //////////////////////////////////////////////
1753 typedef Key key_type;
1754 typedef T mapped_type;
1755 typedef Compare key_compare;
1756 typedef std::pair<Key, T> value_type;
1757 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type) sequence_type;
1758 typedef typename sequence_type::allocator_type allocator_type;
1759 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
1760 typedef typename sequence_type::pointer pointer;
1761 typedef typename sequence_type::const_pointer const_pointer;
1762 typedef typename sequence_type::reference reference;
1763 typedef typename sequence_type::const_reference const_reference;
1764 typedef typename sequence_type::size_type size_type;
1765 typedef typename sequence_type::difference_type difference_type;
1766 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
1767 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare) value_compare;
1768
1769 typedef typename sequence_type::iterator iterator;
1770 typedef typename sequence_type::const_iterator const_iterator;
1771 typedef typename sequence_type::reverse_iterator reverse_iterator;
1772 typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
1773 typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type;
1774
1775 //AllocatorOrContainer::value_type must be std::pair<Key, T>
1776 BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, value_type>::value));
1777
1778 //////////////////////////////////////////////
1779 //
1780 // construct/copy/destroy
1781 //
1782 //////////////////////////////////////////////
1783
1784 //! <b>Effects</b>: Default constructs an empty flat_map.
1785 //!
1786 //! <b>Complexity</b>: Constant.
flat_multimap()1787 BOOST_CONTAINER_FORCEINLINE flat_multimap()
1788 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value &&
1789 dtl::is_nothrow_default_constructible<Compare>::value)
1790 : m_flat_tree()
1791 {}
1792
1793 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified allocator.
1794 //!
1795 //! <b>Complexity</b>: Constant.
flat_multimap(const allocator_type & a)1796 BOOST_CONTAINER_FORCEINLINE explicit flat_multimap(const allocator_type& a)
1797 : m_flat_tree(dtl::force<const impl_allocator_type>(a))
1798 {}
1799
1800 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison
1801 //! object .
1802 //!
1803 //! <b>Complexity</b>: Constant.
flat_multimap(const Compare & comp)1804 BOOST_CONTAINER_FORCEINLINE explicit flat_multimap(const Compare& comp)
1805 : m_flat_tree(comp)
1806 {}
1807
1808 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison
1809 //! object and allocator.
1810 //!
1811 //! <b>Complexity</b>: Constant.
1812 BOOST_CONTAINER_FORCEINLINE
flat_multimap(const Compare & comp,const allocator_type & a)1813 flat_multimap(const Compare& comp, const allocator_type& a)
1814 : m_flat_tree(comp, dtl::force<const impl_allocator_type>(a))
1815 {}
1816
1817 //! <b>Effects</b>: Constructs an empty flat_multimap
1818 //! and inserts elements from the range [first ,last ).
1819 //!
1820 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1821 //! the predicate and otherwise N logN, where N is last - first.
1822 template <class InputIterator>
1823 BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last)1824 flat_multimap(InputIterator first, InputIterator last)
1825 : m_flat_tree(false, first, last)
1826 {}
1827
1828 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified
1829 //! allocator, and inserts elements from the range [first ,last ).
1830 //!
1831 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1832 //! the predicate and otherwise N logN, where N is last - first.
1833 template <class InputIterator>
1834 BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last,const allocator_type & a)1835 flat_multimap(InputIterator first, InputIterator last, const allocator_type& a)
1836 : m_flat_tree(false, first, last, dtl::force<const impl_allocator_type>(a))
1837 {}
1838
1839 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object
1840 //! and inserts elements from the range [first ,last ).
1841 //!
1842 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1843 //! the predicate and otherwise N logN, where N is last - first.
1844 template <class InputIterator>
1845 BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last,const Compare & comp)1846 flat_multimap(InputIterator first, InputIterator last, const Compare& comp)
1847 : m_flat_tree(false, first, last, comp)
1848 {}
1849
1850 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object
1851 //! and allocator, and inserts elements from the range [first ,last ).
1852 //!
1853 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1854 //! the predicate and otherwise N logN, where N is last - first.
1855 template <class InputIterator>
1856 BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)1857 flat_multimap(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1858 : m_flat_tree(false, first, last, comp, dtl::force<const impl_allocator_type>(a))
1859 {}
1860
1861 //! <b>Effects</b>: Constructs an empty flat_multimap
1862 //! and inserts elements from the ordered range [first ,last). This function
1863 //! is more efficient than the normal range creation for ordered ranges.
1864 //!
1865 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1866 //!
1867 //! <b>Complexity</b>: Linear in N.
1868 //!
1869 //! <b>Note</b>: Non-standard extension.
1870 template <class InputIterator>
1871 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last)1872 flat_multimap(ordered_range_t, InputIterator first, InputIterator last)
1873 : m_flat_tree(ordered_range, first, last)
1874 {}
1875
1876 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1877 //! inserts elements from the ordered range [first ,last). This function
1878 //! is more efficient than the normal range creation for ordered ranges.
1879 //!
1880 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1881 //!
1882 //! <b>Complexity</b>: Linear in N.
1883 //!
1884 //! <b>Note</b>: Non-standard extension.
1885 template <class InputIterator>
1886 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp)1887 flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1888 : m_flat_tree(ordered_range, first, last, comp)
1889 {}
1890
1891 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1892 //! allocator, and inserts elements from the ordered range [first ,last). This function
1893 //! is more efficient than the normal range creation for ordered ranges.
1894 //!
1895 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1896 //!
1897 //! <b>Complexity</b>: Linear in N.
1898 //!
1899 //! <b>Note</b>: Non-standard extension.
1900 template <class InputIterator>
1901 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)1902 flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1903 : m_flat_tree(ordered_range, first, last, comp, a)
1904 {}
1905
1906 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1907 //! inserts elements from the ordered range [first ,last). This function
1908 //! is more efficient than the normal range creation for ordered ranges.
1909 //!
1910 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1911 //!
1912 //! <b>Complexity</b>: Linear in N.
1913 //!
1914 //! <b>Note</b>: Non-standard extension.
1915 template <class InputIterator>
1916 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const allocator_type & a)1917 flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type &a)
1918 : m_flat_tree(ordered_range, first, last, Compare(), a)
1919 {}
1920
1921 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1922 //! <b>Effects</b>: Constructs an empty flat_map and
1923 //! inserts elements from the range [il.begin(), il.end()).
1924 //!
1925 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1926 //! the predicate and otherwise N logN, where N is last - first.
1927 BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il)1928 flat_multimap(std::initializer_list<value_type> il)
1929 : m_flat_tree( false
1930 , dtl::force<impl_initializer_list>(il).begin()
1931 , dtl::force<impl_initializer_list>(il).end())
1932 {}
1933
1934 //! <b>Effects</b>: Constructs an empty flat_map using the specified
1935 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1936 //!
1937 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1938 //! the predicate and otherwise N logN, where N is last - first.
1939 BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il,const allocator_type & a)1940 flat_multimap(std::initializer_list<value_type> il, const allocator_type& a)
1941 : m_flat_tree(false
1942 , dtl::force<impl_initializer_list>(il).begin()
1943 , dtl::force<impl_initializer_list>(il).end()
1944 , dtl::force<const impl_allocator_type>(a))
1945 {}
1946
1947 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
1948 //! inserts elements from the range [il.begin(), il.end()).
1949 //!
1950 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1951 //! the predicate and otherwise N logN, where N is last - first.
1952 BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il,const Compare & comp)1953 flat_multimap(std::initializer_list<value_type> il, const Compare& comp)
1954 : m_flat_tree(false
1955 , dtl::force<impl_initializer_list>(il).begin()
1956 , dtl::force<impl_initializer_list>(il).end(), comp)
1957 {}
1958
1959 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
1960 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1961 //!
1962 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1963 //! the predicate and otherwise N logN, where N is last - first.
1964 BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)1965 flat_multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1966 : m_flat_tree( false
1967 , dtl::force<impl_initializer_list>(il).begin()
1968 , dtl::force<impl_initializer_list>(il).end()
1969 , comp, dtl::force<const impl_allocator_type>(a))
1970 {}
1971
1972 //! <b>Effects</b>: Constructs an empty flat_multimap and
1973 //! inserts elements from the ordered range [il.begin(), il.end()). This function
1974 //! is more efficient than the normal range creation for ordered ranges.
1975 //!
1976 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1977 //!
1978 //! <b>Complexity</b>: Linear in N.
1979 //!
1980 //! <b>Note</b>: Non-standard extension.
1981 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,std::initializer_list<value_type> il)1982 flat_multimap(ordered_range_t, std::initializer_list<value_type> il)
1983 : m_flat_tree( ordered_range
1984 , dtl::force<impl_initializer_list>(il).begin()
1985 , dtl::force<impl_initializer_list>(il).end())
1986 {}
1987
1988 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1989 //! inserts elements from the ordered range [il.begin(), il.end()). This function
1990 //! is more efficient than the normal range creation for ordered ranges.
1991 //!
1992 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1993 //!
1994 //! <b>Complexity</b>: Linear in N.
1995 //!
1996 //! <b>Note</b>: Non-standard extension.
1997 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp)1998 flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1999 : m_flat_tree( ordered_range
2000 , dtl::force<impl_initializer_list>(il).begin()
2001 , dtl::force<impl_initializer_list>(il).end(), comp)
2002 {}
2003
2004 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
2005 //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function
2006 //! is more efficient than the normal range creation for ordered ranges.
2007 //!
2008 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
2009 //!
2010 //! <b>Complexity</b>: Linear in N.
2011 //!
2012 //! <b>Note</b>: Non-standard extension.
2013 BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)2014 flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
2015 : m_flat_tree( ordered_range
2016 , dtl::force<impl_initializer_list>(il).begin()
2017 , dtl::force<impl_initializer_list>(il).end()
2018 , comp, dtl::force<const impl_allocator_type>(a))
2019 {}
2020 #endif
2021
2022 //! <b>Effects</b>: Copy constructs a flat_multimap.
2023 //!
2024 //! <b>Complexity</b>: Linear in x.size().
2025 BOOST_CONTAINER_FORCEINLINE
flat_multimap(const flat_multimap & x)2026 flat_multimap(const flat_multimap& x)
2027 : m_flat_tree(x.m_flat_tree)
2028 {}
2029
2030 //! <b>Effects</b>: Move constructs a flat_multimap. Constructs *this using x's resources.
2031 //!
2032 //! <b>Complexity</b>: Constant.
2033 //!
2034 //! <b>Postcondition</b>: x is emptied.
2035 BOOST_CONTAINER_FORCEINLINE
flat_multimap(BOOST_RV_REF (flat_multimap)x)2036 flat_multimap(BOOST_RV_REF(flat_multimap) x)
2037 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
2038 : m_flat_tree(boost::move(x.m_flat_tree))
2039 {}
2040
2041 //! <b>Effects</b>: Copy constructs a flat_multimap using the specified allocator.
2042 //!
2043 //! <b>Complexity</b>: Linear in x.size().
2044 BOOST_CONTAINER_FORCEINLINE
flat_multimap(const flat_multimap & x,const allocator_type & a)2045 flat_multimap(const flat_multimap& x, const allocator_type &a)
2046 : m_flat_tree(x.m_flat_tree, dtl::force<const impl_allocator_type>(a))
2047 {}
2048
2049 //! <b>Effects</b>: Move constructs a flat_multimap using the specified allocator.
2050 //! Constructs *this using x's resources.
2051 //!
2052 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
2053 BOOST_CONTAINER_FORCEINLINE
flat_multimap(BOOST_RV_REF (flat_multimap)x,const allocator_type & a)2054 flat_multimap(BOOST_RV_REF(flat_multimap) x, const allocator_type &a)
2055 : m_flat_tree(boost::move(x.m_flat_tree), dtl::force<const impl_allocator_type>(a))
2056 {}
2057
2058 //! <b>Effects</b>: Makes *this a copy of x.
2059 //!
2060 //! <b>Complexity</b>: Linear in x.size().
2061 BOOST_CONTAINER_FORCEINLINE
operator =(BOOST_COPY_ASSIGN_REF (flat_multimap)x)2062 flat_multimap& operator=(BOOST_COPY_ASSIGN_REF(flat_multimap) x)
2063 { m_flat_tree = x.m_flat_tree; return *this; }
2064
2065 //! <b>Effects</b>: this->swap(x.get()).
2066 //!
2067 //! <b>Complexity</b>: Constant.
2068 BOOST_CONTAINER_FORCEINLINE
operator =(BOOST_RV_REF (flat_multimap)x)2069 flat_multimap& operator=(BOOST_RV_REF(flat_multimap) x)
2070 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
2071 allocator_traits_type::is_always_equal::value) &&
2072 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
2073 { m_flat_tree = boost::move(x.m_flat_tree); return *this; }
2074
2075 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2076 //! <b>Effects</b>: Assign content of il to *this
2077 //!
2078 //! <b>Complexity</b>: Linear in il.size().
2079 BOOST_CONTAINER_FORCEINLINE
operator =(std::initializer_list<value_type> il)2080 flat_multimap& operator=(std::initializer_list<value_type> il)
2081 {
2082 this->clear();
2083 this->insert(il.begin(), il.end());
2084 return *this;
2085 }
2086 #endif
2087
2088 //! <b>Effects</b>: Returns a copy of the allocator that
2089 //! was passed to the object's constructor.
2090 //!
2091 //! <b>Complexity</b>: Constant.
2092 BOOST_CONTAINER_FORCEINLINE
get_allocator() const2093 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
2094 { return dtl::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
2095
2096 //! <b>Effects</b>: Returns a reference to the internal allocator.
2097 //!
2098 //! <b>Throws</b>: Nothing
2099 //!
2100 //! <b>Complexity</b>: Constant.
2101 //!
2102 //! <b>Note</b>: Non-standard extension.
2103 BOOST_CONTAINER_FORCEINLINE
get_stored_allocator()2104 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
2105 { return dtl::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
2106
2107 //! <b>Effects</b>: Returns a reference to the internal allocator.
2108 //!
2109 //! <b>Throws</b>: Nothing
2110 //!
2111 //! <b>Complexity</b>: Constant.
2112 //!
2113 //! <b>Note</b>: Non-standard extension.
2114 BOOST_CONTAINER_FORCEINLINE
get_stored_allocator() const2115 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
2116 { return dtl::force<const stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
2117
2118 //////////////////////////////////////////////
2119 //
2120 // iterators
2121 //
2122 //////////////////////////////////////////////
2123
2124 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
2125 //!
2126 //! <b>Throws</b>: Nothing.
2127 //!
2128 //! <b>Complexity</b>: Constant.
2129 BOOST_CONTAINER_FORCEINLINE
begin()2130 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
2131 { return dtl::force_copy<iterator>(m_flat_tree.begin()); }
2132
2133 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
2134 //!
2135 //! <b>Throws</b>: Nothing.
2136 //!
2137 //! <b>Complexity</b>: Constant.
2138 BOOST_CONTAINER_FORCEINLINE
begin() const2139 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
2140 { return dtl::force_copy<const_iterator>(m_flat_tree.begin()); }
2141
2142 //! <b>Effects</b>: Returns an iterator to the end of the container.
2143 //!
2144 //! <b>Throws</b>: Nothing.
2145 //!
2146 //! <b>Complexity</b>: Constant.
2147 BOOST_CONTAINER_FORCEINLINE
end()2148 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
2149 { return dtl::force_copy<iterator>(m_flat_tree.end()); }
2150
2151 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
2152 //!
2153 //! <b>Throws</b>: Nothing.
2154 //!
2155 //! <b>Complexity</b>: Constant.
2156 BOOST_CONTAINER_FORCEINLINE
end() const2157 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
2158 { return dtl::force_copy<const_iterator>(m_flat_tree.end()); }
2159
2160 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
2161 //! of the reversed container.
2162 //!
2163 //! <b>Throws</b>: Nothing.
2164 //!
2165 //! <b>Complexity</b>: Constant.
2166 BOOST_CONTAINER_FORCEINLINE
rbegin()2167 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
2168 { return dtl::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
2169
2170 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
2171 //! of the reversed container.
2172 //!
2173 //! <b>Throws</b>: Nothing.
2174 //!
2175 //! <b>Complexity</b>: Constant.
2176 BOOST_CONTAINER_FORCEINLINE
rbegin() const2177 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
2178 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
2179
2180 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
2181 //! of the reversed container.
2182 //!
2183 //! <b>Throws</b>: Nothing.
2184 //!
2185 //! <b>Complexity</b>: Constant.
2186 BOOST_CONTAINER_FORCEINLINE
rend()2187 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
2188 { return dtl::force_copy<reverse_iterator>(m_flat_tree.rend()); }
2189
2190 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
2191 //! of the reversed container.
2192 //!
2193 //! <b>Throws</b>: Nothing.
2194 //!
2195 //! <b>Complexity</b>: Constant.
2196 BOOST_CONTAINER_FORCEINLINE
rend() const2197 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
2198 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
2199
2200 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
2201 //!
2202 //! <b>Throws</b>: Nothing.
2203 //!
2204 //! <b>Complexity</b>: Constant.
2205 BOOST_CONTAINER_FORCEINLINE
cbegin() const2206 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
2207 { return dtl::force_copy<const_iterator>(m_flat_tree.cbegin()); }
2208
2209 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
2210 //!
2211 //! <b>Throws</b>: Nothing.
2212 //!
2213 //! <b>Complexity</b>: Constant.
2214 BOOST_CONTAINER_FORCEINLINE
cend() const2215 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
2216 { return dtl::force_copy<const_iterator>(m_flat_tree.cend()); }
2217
2218 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
2219 //! of the reversed container.
2220 //!
2221 //! <b>Throws</b>: Nothing.
2222 //!
2223 //! <b>Complexity</b>: Constant.
2224 BOOST_CONTAINER_FORCEINLINE
crbegin() const2225 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
2226 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
2227
2228 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
2229 //! of the reversed container.
2230 //!
2231 //! <b>Throws</b>: Nothing.
2232 //!
2233 //! <b>Complexity</b>: Constant.
2234 BOOST_CONTAINER_FORCEINLINE
crend() const2235 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
2236 { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
2237
2238 //////////////////////////////////////////////
2239 //
2240 // capacity
2241 //
2242 //////////////////////////////////////////////
2243
2244 //! <b>Effects</b>: Returns true if the container contains no elements.
2245 //!
2246 //! <b>Throws</b>: Nothing.
2247 //!
2248 //! <b>Complexity</b>: Constant.
2249 BOOST_CONTAINER_FORCEINLINE
empty() const2250 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
2251 { return m_flat_tree.empty(); }
2252
2253 //! <b>Effects</b>: Returns the number of the elements contained in the container.
2254 //!
2255 //! <b>Throws</b>: Nothing.
2256 //!
2257 //! <b>Complexity</b>: Constant.
2258 BOOST_CONTAINER_FORCEINLINE
size() const2259 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
2260 { return m_flat_tree.size(); }
2261
2262 //! <b>Effects</b>: Returns the largest possible size of the container.
2263 //!
2264 //! <b>Throws</b>: Nothing.
2265 //!
2266 //! <b>Complexity</b>: Constant.
2267 BOOST_CONTAINER_FORCEINLINE
max_size() const2268 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
2269 { return m_flat_tree.max_size(); }
2270
2271 //! <b>Effects</b>: Number of elements for which memory has been allocated.
2272 //! capacity() is always greater than or equal to size().
2273 //!
2274 //! <b>Throws</b>: Nothing.
2275 //!
2276 //! <b>Complexity</b>: Constant.
2277 BOOST_CONTAINER_FORCEINLINE
capacity() const2278 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
2279 { return m_flat_tree.capacity(); }
2280
2281 //! <b>Effects</b>: If n is less than or equal to capacity(), or the
2282 //! underlying container has no `reserve` member, this call has no
2283 //! effect. Otherwise, it is a request for allocation of additional memory.
2284 //! If the request is successful, then capacity() is greater than or equal to
2285 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
2286 //!
2287 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
2288 //!
2289 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
2290 //! to values might be invalidated.
2291 BOOST_CONTAINER_FORCEINLINE
reserve(size_type cnt)2292 void reserve(size_type cnt)
2293 { m_flat_tree.reserve(cnt); }
2294
2295 //! <b>Effects</b>: Tries to deallocate the excess of memory created
2296 // with previous allocations. The size of the vector is unchanged
2297 //!
2298 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
2299 //!
2300 //! <b>Complexity</b>: Linear to size().
2301 BOOST_CONTAINER_FORCEINLINE
shrink_to_fit()2302 void shrink_to_fit()
2303 { m_flat_tree.shrink_to_fit(); }
2304
2305 //! @copydoc ::boost::container::flat_set::nth(size_type)
2306 BOOST_CONTAINER_FORCEINLINE
nth(size_type n)2307 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
2308 { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); }
2309
2310 //! @copydoc ::boost::container::flat_set::nth(size_type) const
2311 BOOST_CONTAINER_FORCEINLINE
nth(size_type n) const2312 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
2313 { return dtl::force_copy<iterator>(m_flat_tree.nth(n)); }
2314
2315 //! @copydoc ::boost::container::flat_set::index_of(iterator)
2316 BOOST_CONTAINER_FORCEINLINE
index_of(iterator p)2317 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
2318 { return m_flat_tree.index_of(dtl::force_copy<impl_iterator>(p)); }
2319
2320 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
2321 BOOST_CONTAINER_FORCEINLINE
index_of(const_iterator p) const2322 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
2323 { return m_flat_tree.index_of(dtl::force_copy<impl_const_iterator>(p)); }
2324
2325 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2326
2327 //! <b>Effects</b>: Inserts an object of type T constructed with
2328 //! std::forward<Args>(args)... and returns the iterator pointing to the
2329 //! newly inserted element.
2330 //!
2331 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2332 //! to the elements with bigger keys than x.
2333 //!
2334 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2335 template <class... Args>
2336 BOOST_CONTAINER_FORCEINLINE
emplace(BOOST_FWD_REF (Args)...args)2337 iterator emplace(BOOST_FWD_REF(Args)... args)
2338 { return dtl::force_copy<iterator>(m_flat_tree.emplace_equal(boost::forward<Args>(args)...)); }
2339
2340 //! <b>Effects</b>: Inserts an object of type T constructed with
2341 //! std::forward<Args>(args)... in the container.
2342 //! p is a hint pointing to where the insert should start to search.
2343 //!
2344 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2345 //! to the key of x.
2346 //!
2347 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2348 //! is to be inserted before p) plus linear insertion
2349 //! to the elements with bigger keys than x.
2350 //!
2351 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2352 template <class... Args>
2353 BOOST_CONTAINER_FORCEINLINE
emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)2354 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
2355 {
2356 return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_equal
2357 (dtl::force_copy<impl_const_iterator>(hint), boost::forward<Args>(args)...));
2358 }
2359
2360 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
2361
2362 #define BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE(N) \
2363 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2364 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
2365 { return dtl::force_copy<iterator>(m_flat_tree.emplace_equal(BOOST_MOVE_FWD##N)); }\
2366 \
2367 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2368 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2369 {\
2370 return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_equal\
2371 (dtl::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
2372 }\
2373 //
BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)2374 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)
2375 #undef BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE
2376
2377 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
2378
2379 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
2380 //! newly inserted element.
2381 //!
2382 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2383 //! to the elements with bigger keys than x.
2384 //!
2385 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2386 BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x)
2387 {
2388 return dtl::force_copy<iterator>(
2389 m_flat_tree.insert_equal(dtl::force<const impl_value_type>(x)));
2390 }
2391
2392 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
2393 //! the iterator pointing to the newly inserted element.
2394 //!
2395 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2396 //! to the elements with bigger keys than x.
2397 //!
2398 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (value_type)x)2399 BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(value_type) x)
2400 { return dtl::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
2401
2402 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
2403 //! the iterator pointing to the newly inserted element.
2404 //!
2405 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2406 //! to the elements with bigger keys than x.
2407 //!
2408 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (impl_value_type)x)2409 BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(impl_value_type) x)
2410 { return dtl::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
2411
2412 //! <b>Effects</b>: Inserts a copy of x in the container.
2413 //! p is a hint pointing to where the insert should start to search.
2414 //!
2415 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2416 //! to the key of x.
2417 //!
2418 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2419 //! is to be inserted before p) plus linear insertion
2420 //! to the elements with bigger keys than x.
2421 //!
2422 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,const value_type & x)2423 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
2424 {
2425 return dtl::force_copy<iterator>
2426 (m_flat_tree.insert_equal( dtl::force_copy<impl_const_iterator>(p)
2427 , dtl::force<const impl_value_type>(x)));
2428 }
2429
2430 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
2431 //! p is a hint pointing to where the insert should start to search.
2432 //!
2433 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2434 //! to the key of x.
2435 //!
2436 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2437 //! is to be inserted before p) plus linear insertion
2438 //! to the elements with bigger keys than x.
2439 //!
2440 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (value_type)x)2441 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
2442 {
2443 return dtl::force_copy<iterator>
2444 (m_flat_tree.insert_equal(dtl::force_copy<impl_const_iterator>(p)
2445 , boost::move(x)));
2446 }
2447
2448 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
2449 //! p is a hint pointing to where the insert should start to search.
2450 //!
2451 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2452 //! to the key of x.
2453 //!
2454 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2455 //! is to be inserted before p) plus linear insertion
2456 //! to the elements with bigger keys than x.
2457 //!
2458 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (impl_value_type)x)2459 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(impl_value_type) x)
2460 {
2461 return dtl::force_copy<iterator>(
2462 m_flat_tree.insert_equal(dtl::force_copy<impl_const_iterator>(p), boost::move(x)));
2463 }
2464
2465 //! <b>Requires</b>: first, last are not iterators into *this.
2466 //!
2467 //! <b>Effects</b>: inserts each element from the range [first,last) .
2468 //!
2469 //! <b>Complexity</b>: N log(N).
2470 //!
2471 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2472 template <class InputIterator>
insert(InputIterator first,InputIterator last)2473 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
2474 { m_flat_tree.insert_equal(first, last); }
2475
2476 //! <b>Requires</b>: first, last are not iterators into *this.
2477 //!
2478 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
2479 //!
2480 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
2481 //! if there is no element with key equivalent to the key of that element. This
2482 //! function is more efficient than the normal range creation for ordered ranges.
2483 //!
2484 //! <b>Complexity</b>: Linear.
2485 //!
2486 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2487 //!
2488 //! <b>Note</b>: Non-standard extension.
2489 template <class InputIterator>
insert(ordered_range_t,InputIterator first,InputIterator last)2490 BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, InputIterator first, InputIterator last)
2491 { m_flat_tree.insert_equal(ordered_range, first, last); }
2492
2493 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2494 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .
2495 //!
2496 //! <b>Complexity</b>: N log(N).
2497 //!
2498 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(std::initializer_list<value_type> il)2499 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
2500 {
2501 m_flat_tree.insert_equal( dtl::force<impl_initializer_list>(il).begin()
2502 , dtl::force<impl_initializer_list>(il).end());
2503 }
2504
2505 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
2506 //!
2507 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
2508 //! if there is no element with key equivalent to the key of that element. This
2509 //! function is more efficient than the normal range creation for ordered ranges.
2510 //!
2511 //! <b>Complexity</b>: Linear.
2512 //!
2513 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2514 //!
2515 //! <b>Note</b>: Non-standard extension.
insert(ordered_range_t,std::initializer_list<value_type> il)2516 BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, std::initializer_list<value_type> il)
2517 {
2518 m_flat_tree.insert_equal( ordered_range
2519 , dtl::force<impl_initializer_list>(il).begin()
2520 , dtl::force<impl_initializer_list>(il).end());
2521 }
2522 #endif
2523
2524 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
2525 //!
2526 //! <b>Effects</b>: Extracts each element in source and insert it into a using
2527 //! the comparison object of *this.
2528 //!
2529 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
2530 //! to those same elements but as members of *this. Iterators referring to the transferred
2531 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
2532 //! not into source.
2533 //!
2534 //! <b>Throws</b>: Nothing unless the comparison object throws.
2535 //!
2536 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
2537 template<class C2>
merge(flat_multimap<Key,T,C2,AllocatorOrContainer> & source)2538 BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, AllocatorOrContainer>& source)
2539 { m_flat_tree.merge_equal(source.tree()); }
2540
2541 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&)
2542 template<class C2>
merge(BOOST_RV_REF_BEG flat_multimap<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)2543 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
2544 { return this->merge(static_cast<flat_multimap<Key, T, C2, AllocatorOrContainer>&>(source)); }
2545
2546 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&)
2547 template<class C2>
merge(flat_map<Key,T,C2,AllocatorOrContainer> & source)2548 BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, AllocatorOrContainer>& source)
2549 { m_flat_tree.merge_equal(source.tree()); }
2550
2551 //! @copydoc ::boost::container::flat_multimap::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
2552 template<class C2>
merge(BOOST_RV_REF_BEG flat_map<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)2553 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
2554 { return this->merge(static_cast<flat_map<Key, T, C2, AllocatorOrContainer>&>(source)); }
2555
2556 //! <b>Effects</b>: Erases the element pointed to by p.
2557 //!
2558 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
2559 //! following q prior to the element being erased. If no such element exists,
2560 //! returns end().
2561 //!
2562 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
2563 //!
2564 //! <b>Note</b>: Invalidates elements with keys
2565 //! not less than the erased element.
erase(const_iterator p)2566 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p)
2567 {
2568 return dtl::force_copy<iterator>(
2569 m_flat_tree.erase(dtl::force_copy<impl_const_iterator>(p)));
2570 }
2571
2572 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
2573 //!
2574 //! <b>Returns</b>: Returns the number of erased elements.
2575 //!
2576 //! <b>Complexity</b>: Logarithmic search time plus erasure time
2577 //! linear to the elements with bigger keys.
erase(const key_type & x)2578 BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x)
2579 { return m_flat_tree.erase(x); }
2580
2581 //! <b>Effects</b>: Erases all the elements in the range [first, last).
2582 //!
2583 //! <b>Returns</b>: Returns last.
2584 //!
2585 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
2586 //!
2587 //! <b>Complexity</b>: Logarithmic search time plus erasure time
2588 //! linear to the elements with bigger keys.
erase(const_iterator first,const_iterator last)2589 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
2590 {
2591 return dtl::force_copy<iterator>
2592 (m_flat_tree.erase( dtl::force_copy<impl_const_iterator>(first)
2593 , dtl::force_copy<impl_const_iterator>(last)));
2594 }
2595
2596 //! <b>Effects</b>: Swaps the contents of *this and x.
2597 //!
2598 //! <b>Throws</b>: Nothing.
2599 //!
2600 //! <b>Complexity</b>: Constant.
swap(flat_multimap & x)2601 BOOST_CONTAINER_FORCEINLINE void swap(flat_multimap& x)
2602 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
2603 && boost::container::dtl::is_nothrow_swappable<Compare>::value )
2604 { m_flat_tree.swap(x.m_flat_tree); }
2605
2606 //! <b>Effects</b>: erase(a.begin(),a.end()).
2607 //!
2608 //! <b>Postcondition</b>: size() == 0.
2609 //!
2610 //! <b>Complexity</b>: linear in size().
clear()2611 BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW
2612 { m_flat_tree.clear(); }
2613
2614 //////////////////////////////////////////////
2615 //
2616 // observers
2617 //
2618 //////////////////////////////////////////////
2619
2620 //! <b>Effects</b>: Returns the comparison object out
2621 //! of which a was constructed.
2622 //!
2623 //! <b>Complexity</b>: Constant.
key_comp() const2624 BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
2625 { return dtl::force_copy<key_compare>(m_flat_tree.key_comp()); }
2626
2627 //! <b>Effects</b>: Returns an object of value_compare constructed out
2628 //! of the comparison object.
2629 //!
2630 //! <b>Complexity</b>: Constant.
value_comp() const2631 BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
2632 { return value_compare(dtl::force_copy<key_compare>(m_flat_tree.key_comp())); }
2633
2634 //////////////////////////////////////////////
2635 //
2636 // map operations
2637 //
2638 //////////////////////////////////////////////
2639
2640 //! <b>Returns</b>: An iterator pointing to an element with the key
2641 //! equivalent to x, or end() if such an element is not found.
2642 //!
2643 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)2644 BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& x)
2645 { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
2646
2647 //! <b>Returns</b>: An const_iterator pointing to an element with the key
2648 //! equivalent to x, or end() if such an element is not found.
2649 //!
2650 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const2651 BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const
2652 { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
2653
2654 //! <b>Requires</b>: This overload is available only if
2655 //! key_compare::is_transparent exists.
2656 //!
2657 //! <b>Returns</b>: An iterator pointing to an element with the key
2658 //! equivalent to x, or end() if such an element is not found.
2659 //!
2660 //! <b>Complexity</b>: Logarithmic.
2661 template<class K>
find(const K & x)2662 BOOST_CONTAINER_FORCEINLINE iterator find(const K& x)
2663 { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
2664
2665 //! <b>Requires</b>: This overload is available only if
2666 //! key_compare::is_transparent exists.
2667 //!
2668 //! <b>Returns</b>: An const_iterator pointing to an element with the key
2669 //! equivalent to x, or end() if such an element is not found.
2670 //!
2671 //! <b>Complexity</b>: Logarithmic.
2672 template<class K>
find(const K & x) const2673 BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const
2674 { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
2675
2676 //! <b>Returns</b>: The number of elements with key equivalent to x.
2677 //!
2678 //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const2679 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
2680 { return m_flat_tree.count(x); }
2681
2682 //! <b>Requires</b>: This overload is available only if
2683 //! key_compare::is_transparent exists.
2684 //!
2685 //! <b>Returns</b>: The number of elements with key equivalent to x.
2686 //!
2687 //! <b>Complexity</b>: log(size())+count(k)
2688 template<class K>
count(const K & x) const2689 BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
2690 { return m_flat_tree.count(x); }
2691
2692 //! <b>Returns</b>: Returns true if there is an element with key
2693 //! equivalent to key in the container, otherwise false.
2694 //!
2695 //! <b>Complexity</b>: log(size()).
contains(const key_type & x) const2696 bool contains(const key_type& x) const
2697 { return m_flat_tree.find(x) != m_flat_tree.end(); }
2698
2699 //! <b>Requires</b>: This overload is available only if
2700 //! key_compare::is_transparent exists.
2701 //!
2702 //! <b>Returns</b>: Returns true if there is an element with key
2703 //! equivalent to key in the container, otherwise false.
2704 //!
2705 //! <b>Complexity</b>: log(size()).
2706 template<typename K>
contains(const K & x) const2707 bool contains(const K& x) const
2708 { return m_flat_tree.find(x) != m_flat_tree.end(); }
2709
2710 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2711 //! than k, or a.end() if such an element is not found.
2712 //!
2713 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x)2714 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x)
2715 { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
2716
2717 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2718 //! than k, or a.end() if such an element is not found.
2719 //!
2720 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x) const2721 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const
2722 { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
2723
2724 //! <b>Requires</b>: This overload is available only if
2725 //! key_compare::is_transparent exists.
2726 //!
2727 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2728 //! than k, or a.end() if such an element is not found.
2729 //!
2730 //! <b>Complexity</b>: Logarithmic
2731 template<class K>
lower_bound(const K & x)2732 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x)
2733 { return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
2734
2735 //! <b>Requires</b>: This overload is available only if
2736 //! key_compare::is_transparent exists.
2737 //!
2738 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2739 //! than k, or a.end() if such an element is not found.
2740 //!
2741 //! <b>Complexity</b>: Logarithmic
2742 template<class K>
lower_bound(const K & x) const2743 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const
2744 { return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
2745
2746 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2747 //! than x, or end() if such an element is not found.
2748 //!
2749 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x)2750 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& x)
2751 {return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
2752
2753 //! <b>Returns</b>: A const iterator pointing to the first element with key
2754 //! not less than x, or end() if such an element is not found.
2755 //!
2756 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x) const2757 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const
2758 { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
2759
2760 //! <b>Requires</b>: This overload is available only if
2761 //! key_compare::is_transparent exists.
2762 //!
2763 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2764 //! than x, or end() if such an element is not found.
2765 //!
2766 //! <b>Complexity</b>: Logarithmic
2767 template<class K>
upper_bound(const K & x)2768 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x)
2769 {return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
2770
2771 //! <b>Requires</b>: This overload is available only if
2772 //! key_compare::is_transparent exists.
2773 //!
2774 //! <b>Returns</b>: A const iterator pointing to the first element with key
2775 //! not less than x, or end() if such an element is not found.
2776 //!
2777 //! <b>Complexity</b>: Logarithmic
2778 template<class K>
upper_bound(const K & x) const2779 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const
2780 { return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
2781
2782 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2783 //!
2784 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x)2785 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
2786 { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
2787
2788 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2789 //!
2790 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x) const2791 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
2792 { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
2793
2794 //! <b>Requires</b>: This overload is available only if
2795 //! key_compare::is_transparent exists.
2796 //!
2797 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2798 //!
2799 //! <b>Complexity</b>: Logarithmic
2800 template<class K>
equal_range(const K & x)2801 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
2802 { return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
2803
2804 //! <b>Requires</b>: This overload is available only if
2805 //! key_compare::is_transparent exists.
2806 //!
2807 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2808 //!
2809 //! <b>Complexity</b>: Logarithmic
2810 template<class K>
equal_range(const K & x) const2811 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const
2812 { return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
2813
2814 //! <b>Effects</b>: Extracts the internal sequence container.
2815 //!
2816 //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
2817 //!
2818 //! <b>Postcondition</b>: this->empty()
2819 //!
2820 //! <b>Throws</b>: If secuence_type's move constructor throws
extract_sequence()2821 BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
2822 {
2823 return boost::move(dtl::force<sequence_type>(m_flat_tree.get_sequence_ref()));
2824 }
2825
2826 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
2827 //! one passed externally using the move assignment.
2828 //!
2829 //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
2830 //!
2831 //! <b>Throws</b>: If the comparison or the move constructor throws
adopt_sequence(BOOST_RV_REF (sequence_type)seq)2832 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
2833 { this->m_flat_tree.adopt_sequence_equal(boost::move(dtl::force<impl_sequence_type>(seq))); }
2834
2835 //! <b>Requires</b>: seq shall be ordered according to this->compare().
2836 //!
2837 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
2838 //! one passed externally using the move assignment.
2839 //!
2840 //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
2841 //!
2842 //! <b>Throws</b>: If the move assignment throws
adopt_sequence(ordered_range_t,BOOST_RV_REF (sequence_type)seq)2843 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
2844 { this->m_flat_tree.adopt_sequence_equal(ordered_range_t(), boost::move(dtl::force<impl_sequence_type>(seq))); }
2845
2846 //! <b>Effects</b>: Returns true if x and y are equal
2847 //!
2848 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator ==(const flat_multimap & x,const flat_multimap & y)2849 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_multimap& x, const flat_multimap& y)
2850 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
2851
2852 //! <b>Effects</b>: Returns true if x and y are unequal
2853 //!
2854 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator !=(const flat_multimap & x,const flat_multimap & y)2855 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_multimap& x, const flat_multimap& y)
2856 { return !(x == y); }
2857
2858 //! <b>Effects</b>: Returns true if x is less than y
2859 //!
2860 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <(const flat_multimap & x,const flat_multimap & y)2861 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_multimap& x, const flat_multimap& y)
2862 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
2863
2864 //! <b>Effects</b>: Returns true if x is greater than y
2865 //!
2866 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >(const flat_multimap & x,const flat_multimap & y)2867 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_multimap& x, const flat_multimap& y)
2868 { return y < x; }
2869
2870 //! <b>Effects</b>: Returns true if x is equal or less than y
2871 //!
2872 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <=(const flat_multimap & x,const flat_multimap & y)2873 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_multimap& x, const flat_multimap& y)
2874 { return !(y < x); }
2875
2876 //! <b>Effects</b>: Returns true if x is equal or greater than y
2877 //!
2878 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >=(const flat_multimap & x,const flat_multimap & y)2879 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_multimap& x, const flat_multimap& y)
2880 { return !(x < y); }
2881
2882 //! <b>Effects</b>: x.swap(y)
2883 //!
2884 //! <b>Complexity</b>: Constant.
swap(flat_multimap & x,flat_multimap & y)2885 BOOST_CONTAINER_FORCEINLINE friend void swap(flat_multimap& x, flat_multimap& y)
2886 { x.swap(y); }
2887 };
2888
2889 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2890
2891 template <typename InputIterator>
2892 flat_multimap(InputIterator, InputIterator) ->
2893 flat_multimap< it_based_non_const_first_type_t<InputIterator>
2894 , it_based_second_type_t<InputIterator>>;
2895
2896 template < typename InputIterator, typename AllocatorOrCompare>
2897 flat_multimap(InputIterator, InputIterator, AllocatorOrCompare const&) ->
2898 flat_multimap< it_based_non_const_first_type_t<InputIterator>
2899 , it_based_second_type_t<InputIterator>
2900 , typename dtl::if_c< // Compare
2901 dtl::is_allocator<AllocatorOrCompare>::value
2902 , std::less<it_based_non_const_first_type_t<InputIterator>>
2903 , AllocatorOrCompare
2904 >::type
2905 , typename dtl::if_c< // Allocator
2906 dtl::is_allocator<AllocatorOrCompare>::value
2907 , AllocatorOrCompare
2908 , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2909 >::type
2910 >;
2911
2912 template < typename InputIterator, typename Compare, typename Allocator
2913 , typename = dtl::require_nonallocator_t<Compare>
2914 , typename = dtl::require_allocator_t<Allocator>>
2915 flat_multimap(InputIterator, InputIterator, Compare const&, Allocator const&) ->
2916 flat_multimap< it_based_non_const_first_type_t<InputIterator>
2917 , it_based_second_type_t<InputIterator>
2918 , Compare
2919 , Allocator>;
2920
2921 template <typename InputIterator>
2922 flat_multimap(ordered_range_t, InputIterator, InputIterator) ->
2923 flat_multimap< it_based_non_const_first_type_t<InputIterator>
2924 , it_based_second_type_t<InputIterator>>;
2925
2926 template < typename InputIterator, typename AllocatorOrCompare>
2927 flat_multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
2928 flat_multimap< it_based_non_const_first_type_t<InputIterator>
2929 , it_based_second_type_t<InputIterator>
2930 , typename dtl::if_c< // Compare
2931 dtl::is_allocator<AllocatorOrCompare>::value
2932 , std::less<it_based_non_const_first_type_t<InputIterator>>
2933 , AllocatorOrCompare
2934 >::type
2935 , typename dtl::if_c< // Allocator
2936 dtl::is_allocator<AllocatorOrCompare>::value
2937 , AllocatorOrCompare
2938 , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2939 >::type
2940 >;
2941
2942 template < typename InputIterator, typename Compare, typename Allocator
2943 , typename = dtl::require_nonallocator_t<Compare>
2944 , typename = dtl::require_allocator_t<Allocator>>
2945 flat_multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
2946 flat_multimap< it_based_non_const_first_type_t<InputIterator>
2947 , it_based_second_type_t<InputIterator>
2948 , Compare
2949 , Allocator>;
2950
2951 #endif
2952
2953 }}
2954
2955 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2956
2957 namespace boost {
2958
2959 //!has_trivial_destructor_after_move<> == true_type
2960 //!specialization for optimizations
2961 template <class Key, class T, class Compare, class AllocatorOrContainer>
2962 struct has_trivial_destructor_after_move< boost::container::flat_multimap<Key, T, Compare, AllocatorOrContainer> >
2963 {
2964 typedef typename ::boost::container::allocator_traits<AllocatorOrContainer>::pointer pointer;
2965 static const bool value = ::boost::has_trivial_destructor_after_move<AllocatorOrContainer>::value &&
2966 ::boost::has_trivial_destructor_after_move<pointer>::value &&
2967 ::boost::has_trivial_destructor_after_move<Compare>::value;
2968 };
2969
2970 } //namespace boost {
2971
2972 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2973
2974 #include <boost/container/detail/config_end.hpp>
2975
2976 #endif // BOOST_CONTAINER_FLAT_MAP_HPP
2977