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