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
51 namespace boost {
52 namespace container {
53
54 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
55
56 namespace container_detail{
57
58 template<class D, class S>
force(const S & s)59 static D &force(const S &s)
60 { return *const_cast<D*>((reinterpret_cast<const D*>(&s))); }
61
62 template<class D, class S>
force_copy(S s)63 static D force_copy(S s)
64 {
65 D *vp = reinterpret_cast<D *>(&s);
66 return D(*vp);
67 }
68
69 } //namespace container_detail{
70
71 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
72
73 //! A flat_map is a kind of associative container that supports unique keys (contains at
74 //! most one of each key value) and provides for fast retrieval of values of another
75 //! type T based on the keys. The flat_map class supports random-access iterators.
76 //!
77 //! A flat_map satisfies all of the requirements of a container and of a reversible
78 //! container and of an associative container. A flat_map also provides
79 //! most operations described for unique keys. For a
80 //! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
81 //! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
82 //!
83 //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
84 //!
85 //! Allocator is the allocator to allocate the value_types
86 //! (e.g. <i>allocator< std::pair<Key, T> ></i>).
87 //!
88 //! flat_map is similar to std::map but it's implemented like an ordered vector.
89 //! This means that inserting a new element into a flat_map invalidates
90 //! previous iterators and references
91 //!
92 //! Erasing an element invalidates iterators and references
93 //! pointing to elements that come after (their keys are bigger) the erased element.
94 //!
95 //! This container provides random-access iterators.
96 //!
97 //! \tparam Key is the key_type of the map
98 //! \tparam Value is the <code>mapped_type</code>
99 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
100 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
101 //! (e.g. <i>allocator< std::pair<Key, T> > </i>).
102 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
103 template <class Key, class T, class Compare = std::less<Key>, class Allocator = new_allocator< std::pair< Key, T> > >
104 #else
105 template <class Key, class T, class Compare, class Allocator>
106 #endif
107 class flat_map
108 {
109 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
110 private:
111 BOOST_COPYABLE_AND_MOVABLE(flat_map)
112 //This is the tree that we should store if pair was movable
113 typedef container_detail::flat_tree<Key,
114 std::pair<Key, T>,
115 container_detail::select1st< std::pair<Key, T> >,
116 Compare,
117 Allocator> tree_t;
118
119 //This is the real tree stored here. It's based on a movable pair
120 typedef container_detail::flat_tree<Key,
121 container_detail::pair<Key, T>,
122 container_detail::select1st<container_detail::pair<Key, T> >,
123 Compare,
124 typename allocator_traits<Allocator>::template portable_rebind_alloc
125 <container_detail::pair<Key, T> >::type> impl_tree_t;
126 impl_tree_t m_flat_tree; // flat tree representing flat_map
127
128 typedef typename impl_tree_t::value_type impl_value_type;
129 typedef typename impl_tree_t::const_iterator impl_const_iterator;
130 typedef typename impl_tree_t::iterator impl_iterator;
131 typedef typename impl_tree_t::allocator_type impl_allocator_type;
132 typedef container_detail::flat_tree_value_compare
133 < Compare
134 , container_detail::select1st< std::pair<Key, T> >
135 , std::pair<Key, T> > value_compare_impl;
136 typedef typename container_detail::get_flat_tree_iterators
137 <typename allocator_traits<Allocator>::pointer>::iterator iterator_impl;
138 typedef typename container_detail::get_flat_tree_iterators
139 <typename allocator_traits<Allocator>::pointer>::const_iterator const_iterator_impl;
140 typedef typename container_detail::get_flat_tree_iterators
141 <typename allocator_traits<Allocator>::pointer>::reverse_iterator reverse_iterator_impl;
142 typedef typename container_detail::get_flat_tree_iterators
143 <typename allocator_traits<Allocator>::pointer>::const_reverse_iterator const_reverse_iterator_impl;
144 public:
145 typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type;
146 private:
147 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
148
149 public:
150
151 //////////////////////////////////////////////
152 //
153 // types
154 //
155 //////////////////////////////////////////////
156 typedef Key key_type;
157 typedef T mapped_type;
158 typedef std::pair<Key, T> value_type;
159 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
160 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
161 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
162 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
163 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
164 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
165 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
166 typedef Allocator allocator_type;
167 typedef BOOST_CONTAINER_IMPDEF(Allocator) stored_allocator_type;
168 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
169 typedef Compare key_compare;
170 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
171 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
172 typedef BOOST_CONTAINER_IMPDEF(reverse_iterator_impl) reverse_iterator;
173 typedef BOOST_CONTAINER_IMPDEF(const_reverse_iterator_impl) const_reverse_iterator;
174 typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type;
175
176 public:
177 //////////////////////////////////////////////
178 //
179 // construct/copy/destroy
180 //
181 //////////////////////////////////////////////
182
183 //! <b>Effects</b>: Default constructs an empty flat_map.
184 //!
185 //! <b>Complexity</b>: Constant.
flat_map()186 flat_map()
187 : m_flat_tree()
188 {
189 //A type must be std::pair<Key, T>
190 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
191 }
192
193 //! <b>Effects</b>: Constructs an empty flat_map using the specified
194 //! comparison object and allocator.
195 //!
196 //! <b>Complexity</b>: Constant.
flat_map(const Compare & comp,const allocator_type & a=allocator_type ())197 explicit flat_map(const Compare& comp, const allocator_type& a = allocator_type())
198 : m_flat_tree(comp, container_detail::force<impl_allocator_type>(a))
199 {
200 //A type must be std::pair<Key, T>
201 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
202 }
203
204 //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator.
205 //!
206 //! <b>Complexity</b>: Constant.
flat_map(const allocator_type & a)207 explicit flat_map(const allocator_type& a)
208 : m_flat_tree(container_detail::force<impl_allocator_type>(a))
209 {
210 //A type must be std::pair<Key, T>
211 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
212 }
213
214 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
215 //! allocator, and inserts elements from the range [first ,last ).
216 //!
217 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
218 //! comp and otherwise N logN, where N is last - first.
219 template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())220 flat_map(InputIterator first, InputIterator last, const Compare& comp = Compare(),
221 const allocator_type& a = allocator_type())
222 : m_flat_tree(true, first, last, comp, container_detail::force<impl_allocator_type>(a))
223 {
224 //A type must be std::pair<Key, T>
225 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
226 }
227
228 //! <b>Effects</b>: Constructs an empty flat_map using the specified
229 //! allocator, and inserts elements from the range [first ,last ).
230 //!
231 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
232 //! comp and otherwise N logN, where N is last - first.
233 template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const allocator_type & a)234 flat_map(InputIterator first, InputIterator last, const allocator_type& a)
235 : m_flat_tree(true, first, last, Compare(), container_detail::force<impl_allocator_type>(a))
236 {
237 //A type must be std::pair<Key, T>
238 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
239 }
240
241 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
242 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
243 //! is more efficient than the normal range creation for ordered ranges.
244 //!
245 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
246 //! unique values.
247 //!
248 //! <b>Complexity</b>: Linear in N.
249 //!
250 //! <b>Note</b>: Non-standard extension.
251 template <class InputIterator>
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())252 flat_map( ordered_unique_range_t, InputIterator first, InputIterator last
253 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
254 : m_flat_tree(ordered_range, first, last, comp, a)
255 {
256 //A type must be std::pair<Key, T>
257 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
258 }
259
260 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
261 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
262 //! allocator, and inserts elements from the range [il.begin() ,il.end()).
263 //!
264 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
265 //! comp and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())266 flat_map(std::initializer_list<value_type> il, const Compare& comp = Compare(),
267 const allocator_type& a = allocator_type())
268 : m_flat_tree(true, il.begin(), il.end(), comp, container_detail::force<impl_allocator_type>(a))
269 {
270 //A type must be std::pair<Key, T>
271 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
272 }
273
274 //! <b>Effects</b>: Constructs an empty flat_map using the specified
275 //! allocator, and inserts elements from the range [il.begin() ,il.end()).
276 //!
277 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
278 //! comp and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const allocator_type & a)279 flat_map(std::initializer_list<value_type> il, const allocator_type& a)
280 : m_flat_tree(true, il.begin(), il.end(), Compare(), container_detail::force<impl_allocator_type>(a))
281 {
282 //A type must be std::pair<Key, T>
283 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
284 }
285
286 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
287 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
288 //! is more efficient than the normal range creation for ordered ranges.
289 //!
290 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
291 //! unique values.
292 //!
293 //! <b>Complexity</b>: Linear in N.
294 //!
295 //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())296 flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(),
297 const allocator_type& a = allocator_type())
298 : m_flat_tree(ordered_range, il.begin(), il.end(), comp, a)
299 {
300 //A type must be std::pair<Key, T>
301 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
302 }
303 #endif
304
305 //! <b>Effects</b>: Copy constructs a flat_map.
306 //!
307 //! <b>Complexity</b>: Linear in x.size().
flat_map(const flat_map & x)308 flat_map(const flat_map& x)
309 : m_flat_tree(x.m_flat_tree)
310 {
311 //A type must be std::pair<Key, T>
312 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
313 }
314
315 //! <b>Effects</b>: Move constructs a flat_map.
316 //! Constructs *this using x's resources.
317 //!
318 //! <b>Complexity</b>: Constant.
319 //!
320 //! <b>Postcondition</b>: x is emptied.
flat_map(BOOST_RV_REF (flat_map)x)321 flat_map(BOOST_RV_REF(flat_map) x)
322 : m_flat_tree(boost::move(x.m_flat_tree))
323 {
324 //A type must be std::pair<Key, T>
325 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
326 }
327
328 //! <b>Effects</b>: Copy constructs a flat_map using the specified allocator.
329 //!
330 //! <b>Complexity</b>: Linear in x.size().
flat_map(const flat_map & x,const allocator_type & a)331 flat_map(const flat_map& x, const allocator_type &a)
332 : m_flat_tree(x.m_flat_tree, a)
333 {
334 //A type must be std::pair<Key, T>
335 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
336 }
337
338 //! <b>Effects</b>: Move constructs a flat_map using the specified allocator.
339 //! Constructs *this using x's resources.
340 //!
341 //! <b>Complexity</b>: Constant if x.get_allocator() == a, linear otherwise.
flat_map(BOOST_RV_REF (flat_map)x,const allocator_type & a)342 flat_map(BOOST_RV_REF(flat_map) x, const allocator_type &a)
343 : m_flat_tree(boost::move(x.m_flat_tree), a)
344 {
345 //A type must be std::pair<Key, T>
346 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
347 }
348
349 //! <b>Effects</b>: Makes *this a copy of x.
350 //!
351 //! <b>Complexity</b>: Linear in x.size().
operator =(BOOST_COPY_ASSIGN_REF (flat_map)x)352 flat_map& operator=(BOOST_COPY_ASSIGN_REF(flat_map) x)
353 { m_flat_tree = x.m_flat_tree; return *this; }
354
355 //! <b>Effects</b>: Move constructs a flat_map.
356 //! Constructs *this using x's resources.
357 //!
358 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
359 //! is false and (allocation throws or value_type's move constructor throws)
360 //!
361 //! <b>Complexity</b>: Constant if allocator_traits_type::
362 //! propagate_on_container_move_assignment is true or
363 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
operator =(BOOST_RV_REF (flat_map)x)364 flat_map& operator=(BOOST_RV_REF(flat_map) x)
365 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
366 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value )
367 { m_flat_tree = boost::move(x.m_flat_tree); return *this; }
368
369 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
370 //! <b>Effects</b>: Assign elements from il to *this
operator =(std::initializer_list<value_type> il)371 flat_map& operator=(std::initializer_list<value_type> il)
372 {
373 this->clear();
374 this->insert(il.begin(), il.end());
375 return *this;
376 }
377 #endif
378
379 //! <b>Effects</b>: Returns a copy of the allocator that
380 //! was passed to the object's constructor.
381 //!
382 //! <b>Complexity</b>: Constant.
get_allocator() const383 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
384 { return container_detail::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
385
386 //! <b>Effects</b>: Returns a reference to the internal allocator.
387 //!
388 //! <b>Throws</b>: Nothing
389 //!
390 //! <b>Complexity</b>: Constant.
391 //!
392 //! <b>Note</b>: Non-standard extension.
get_stored_allocator()393 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
394 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
395
396 //! <b>Effects</b>: Returns a reference to the internal allocator.
397 //!
398 //! <b>Throws</b>: Nothing
399 //!
400 //! <b>Complexity</b>: Constant.
401 //!
402 //! <b>Note</b>: Non-standard extension.
get_stored_allocator() const403 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
404 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
405
406 //////////////////////////////////////////////
407 //
408 // iterators
409 //
410 //////////////////////////////////////////////
411
412 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
413 //!
414 //! <b>Throws</b>: Nothing.
415 //!
416 //! <b>Complexity</b>: Constant.
begin()417 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
418 { return container_detail::force_copy<iterator>(m_flat_tree.begin()); }
419
420 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
421 //!
422 //! <b>Throws</b>: Nothing.
423 //!
424 //! <b>Complexity</b>: Constant.
begin() const425 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
426 { return container_detail::force_copy<const_iterator>(m_flat_tree.begin()); }
427
428 //! <b>Effects</b>: Returns an iterator to the end of the container.
429 //!
430 //! <b>Throws</b>: Nothing.
431 //!
432 //! <b>Complexity</b>: Constant.
end()433 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
434 { return container_detail::force_copy<iterator>(m_flat_tree.end()); }
435
436 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
437 //!
438 //! <b>Throws</b>: Nothing.
439 //!
440 //! <b>Complexity</b>: Constant.
end() const441 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
442 { return container_detail::force_copy<const_iterator>(m_flat_tree.end()); }
443
444 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
445 //! of the reversed container.
446 //!
447 //! <b>Throws</b>: Nothing.
448 //!
449 //! <b>Complexity</b>: Constant.
rbegin()450 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
451 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
452
453 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
454 //! of the reversed container.
455 //!
456 //! <b>Throws</b>: Nothing.
457 //!
458 //! <b>Complexity</b>: Constant.
rbegin() const459 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
460 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
461
462 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
463 //! of the reversed container.
464 //!
465 //! <b>Throws</b>: Nothing.
466 //!
467 //! <b>Complexity</b>: Constant.
rend()468 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
469 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rend()); }
470
471 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
472 //! of the reversed container.
473 //!
474 //! <b>Throws</b>: Nothing.
475 //!
476 //! <b>Complexity</b>: Constant.
rend() const477 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
478 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
479
480 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
481 //!
482 //! <b>Throws</b>: Nothing.
483 //!
484 //! <b>Complexity</b>: Constant.
cbegin() const485 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
486 { return container_detail::force_copy<const_iterator>(m_flat_tree.cbegin()); }
487
488 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
489 //!
490 //! <b>Throws</b>: Nothing.
491 //!
492 //! <b>Complexity</b>: Constant.
cend() const493 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
494 { return container_detail::force_copy<const_iterator>(m_flat_tree.cend()); }
495
496 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
497 //! of the reversed container.
498 //!
499 //! <b>Throws</b>: Nothing.
500 //!
501 //! <b>Complexity</b>: Constant.
crbegin() const502 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
503 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
504
505 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
506 //! of the reversed container.
507 //!
508 //! <b>Throws</b>: Nothing.
509 //!
510 //! <b>Complexity</b>: Constant.
crend() const511 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
512 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
513
514 //////////////////////////////////////////////
515 //
516 // capacity
517 //
518 //////////////////////////////////////////////
519
520 //! <b>Effects</b>: Returns true if the container contains no elements.
521 //!
522 //! <b>Throws</b>: Nothing.
523 //!
524 //! <b>Complexity</b>: Constant.
empty() const525 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
526 { return m_flat_tree.empty(); }
527
528 //! <b>Effects</b>: Returns the number of the elements contained in the container.
529 //!
530 //! <b>Throws</b>: Nothing.
531 //!
532 //! <b>Complexity</b>: Constant.
size() const533 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
534 { return m_flat_tree.size(); }
535
536 //! <b>Effects</b>: Returns the largest possible size of the container.
537 //!
538 //! <b>Throws</b>: Nothing.
539 //!
540 //! <b>Complexity</b>: Constant.
max_size() const541 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
542 { return m_flat_tree.max_size(); }
543
544 //! <b>Effects</b>: Number of elements for which memory has been allocated.
545 //! capacity() is always greater than or equal to size().
546 //!
547 //! <b>Throws</b>: Nothing.
548 //!
549 //! <b>Complexity</b>: Constant.
capacity() const550 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
551 { return m_flat_tree.capacity(); }
552
553 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
554 //! effect. Otherwise, it is a request for allocation of additional memory.
555 //! If the request is successful, then capacity() is greater than or equal to
556 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
557 //!
558 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
559 //!
560 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
561 //! to values might be invalidated.
reserve(size_type cnt)562 void reserve(size_type cnt)
563 { m_flat_tree.reserve(cnt); }
564
565 //! <b>Effects</b>: Tries to deallocate the excess of memory created
566 // with previous allocations. The size of the vector is unchanged
567 //!
568 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
569 //!
570 //! <b>Complexity</b>: Linear to size().
shrink_to_fit()571 void shrink_to_fit()
572 { m_flat_tree.shrink_to_fit(); }
573
574 //////////////////////////////////////////////
575 //
576 // element access
577 //
578 //////////////////////////////////////////////
579
580 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
581 //! Effects: If there is no key equivalent to x in the flat_map, inserts
582 //! value_type(x, T()) into the flat_map.
583 //!
584 //! Returns: A reference to the mapped_type corresponding to x in *this.
585 //!
586 //! Complexity: Logarithmic.
587 mapped_type &operator[](const key_type& k);
588
589 //! Effects: If there is no key equivalent to x in the flat_map, inserts
590 //! value_type(move(x), T()) into the flat_map (the key is move-constructed)
591 //!
592 //! Returns: A reference to the mapped_type corresponding to x in *this.
593 //!
594 //! Complexity: Logarithmic.
595 mapped_type &operator[](key_type &&k) ;
596
597 #else
598 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
599 #endif
600
601 //! @copydoc ::boost::container::flat_set::nth(size_type)
nth(size_type n)602 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
603 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
604
605 //! @copydoc ::boost::container::flat_set::nth(size_type) const
nth(size_type n) const606 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
607 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
608
609 //! @copydoc ::boost::container::flat_set::index_of(iterator)
index_of(iterator p)610 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
611 { return m_flat_tree.index_of(container_detail::force_copy<impl_iterator>(p)); }
612
613 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
index_of(const_iterator p) const614 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
615 { return m_flat_tree.index_of(container_detail::force_copy<impl_const_iterator>(p)); }
616
617 //! Returns: A reference to the element whose key is equivalent to x.
618 //!
619 //! Throws: An exception object of type out_of_range if no such element is present.
620 //!
621 //! Complexity: logarithmic.
at(const key_type & k)622 T& at(const key_type& k)
623 {
624 iterator i = this->find(k);
625 if(i == this->end()){
626 throw_out_of_range("flat_map::at key not found");
627 }
628 return i->second;
629 }
630
631 //! Returns: A reference to the element whose key is equivalent to x.
632 //!
633 //! Throws: An exception object of type out_of_range if no such element is present.
634 //!
635 //! Complexity: logarithmic.
at(const key_type & k) const636 const T& at(const key_type& k) const
637 {
638 const_iterator i = this->find(k);
639 if(i == this->end()){
640 throw_out_of_range("flat_map::at key not found");
641 }
642 return i->second;
643 }
644
645 //////////////////////////////////////////////
646 //
647 // modifiers
648 //
649 //////////////////////////////////////////////
650
651 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
652
653 //! <b>Effects</b>: Inserts an object x of type T constructed with
654 //! std::forward<Args>(args)... if and only if there is no element in the container
655 //! with key equivalent to the key of x.
656 //!
657 //! <b>Returns</b>: The bool component of the returned pair is true if and only
658 //! if the insertion takes place, and the iterator component of the pair
659 //! points to the element with key equivalent to the key of x.
660 //!
661 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
662 //! to the elements with bigger keys than x.
663 //!
664 //! <b>Note</b>: If an element is inserted it might invalidate elements.
665 template <class... Args>
emplace(BOOST_FWD_REF (Args)...args)666 std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
667 { return container_detail::force_copy< std::pair<iterator, bool> >(m_flat_tree.emplace_unique(boost::forward<Args>(args)...)); }
668
669 //! <b>Effects</b>: Inserts an object of type T constructed with
670 //! std::forward<Args>(args)... in the container if and only if there is
671 //! no element in the container with key equivalent to the key of x.
672 //! p is a hint pointing to where the insert should start to search.
673 //!
674 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
675 //! to the key of x.
676 //!
677 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
678 //! right before p) plus insertion linear to the elements with bigger keys than x.
679 //!
680 //! <b>Note</b>: If an element is inserted it might invalidate elements.
681 template <class... Args>
emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)682 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
683 {
684 return container_detail::force_copy<iterator>
685 (m_flat_tree.emplace_hint_unique( container_detail::force_copy<impl_const_iterator>(hint)
686 , boost::forward<Args>(args)...));
687 }
688
689 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
690
691 #define BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE(N) \
692 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
693 std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
694 {\
695 return container_detail::force_copy< std::pair<iterator, bool> >\
696 (m_flat_tree.emplace_unique(BOOST_MOVE_FWD##N));\
697 }\
698 \
699 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
700 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
701 {\
702 return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_unique\
703 (container_detail::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
704 }\
705 //
BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)706 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)
707 #undef BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE
708
709 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
710
711 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
712 //! with key equivalent to the key of x.
713 //!
714 //! <b>Returns</b>: The bool component of the returned pair is true if and only
715 //! if the insertion takes place, and the iterator component of the pair
716 //! points to the element with key equivalent to the key of x.
717 //!
718 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
719 //! to the elements with bigger keys than x.
720 //!
721 //! <b>Note</b>: If an element is inserted it might invalidate elements.
722 std::pair<iterator,bool> insert(const value_type& x)
723 { return container_detail::force_copy<std::pair<iterator,bool> >(
724 m_flat_tree.insert_unique(container_detail::force<impl_value_type>(x))); }
725
726 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
727 //! only if there is no element in the container with key equivalent to the key of x.
728 //!
729 //! <b>Returns</b>: The bool component of the returned pair is true if and only
730 //! if the insertion takes place, and the iterator component of the pair
731 //! points to the element with key equivalent to the key of x.
732 //!
733 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
734 //! to the elements with bigger keys than x.
735 //!
736 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (value_type)x)737 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
738 { return container_detail::force_copy<std::pair<iterator,bool> >(
739 m_flat_tree.insert_unique(boost::move(container_detail::force<impl_value_type>(x)))); }
740
741 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
742 //! only if there is no element in the container with key equivalent to the key of x.
743 //!
744 //! <b>Returns</b>: The bool component of the returned pair is true if and only
745 //! if the insertion takes place, and the iterator component of the pair
746 //! points to the element with key equivalent to the key of x.
747 //!
748 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
749 //! to the elements with bigger keys than x.
750 //!
751 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (movable_value_type)x)752 std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
753 {
754 return container_detail::force_copy<std::pair<iterator,bool> >
755 (m_flat_tree.insert_unique(boost::move(x)));
756 }
757
758 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
759 //! no element in the container with key equivalent to the key of x.
760 //! p is a hint pointing to where the insert should start to search.
761 //!
762 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
763 //! to the key of x.
764 //!
765 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
766 //! right before p) plus insertion linear to the elements with bigger keys than x.
767 //!
768 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,const value_type & x)769 iterator insert(const_iterator p, const value_type& x)
770 {
771 return container_detail::force_copy<iterator>(
772 m_flat_tree.insert_unique( container_detail::force_copy<impl_const_iterator>(p)
773 , container_detail::force<impl_value_type>(x)));
774 }
775
776 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
777 //! p is a hint pointing to where the insert should start to search.
778 //!
779 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
780 //!
781 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
782 //! right before p) plus insertion linear to the elements with bigger keys than x.
783 //!
784 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (value_type)x)785 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
786 {
787 return container_detail::force_copy<iterator>
788 (m_flat_tree.insert_unique( container_detail::force_copy<impl_const_iterator>(p)
789 , boost::move(container_detail::force<impl_value_type>(x))));
790 }
791
792 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
793 //! p is a hint pointing to where the insert should start to search.
794 //!
795 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
796 //!
797 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
798 //! right before p) plus insertion linear to the elements with bigger keys than x.
799 //!
800 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)801 iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
802 {
803 return container_detail::force_copy<iterator>(
804 m_flat_tree.insert_unique(container_detail::force_copy<impl_const_iterator>(p), boost::move(x)));
805 }
806
807 //! <b>Requires</b>: first, last are not iterators into *this.
808 //!
809 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
810 //! if there is no element with key equivalent to the key of that element.
811 //!
812 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
813 //! search time plus N*size() insertion time.
814 //!
815 //! <b>Note</b>: If an element is inserted it might invalidate elements.
816 template <class InputIterator>
insert(InputIterator first,InputIterator last)817 void insert(InputIterator first, InputIterator last)
818 { m_flat_tree.insert_unique(first, last); }
819
820 //! <b>Requires</b>: first, last are not iterators into *this.
821 //!
822 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
823 //! unique values.
824 //!
825 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
826 //! if there is no element with key equivalent to the key of that element. This
827 //! function is more efficient than the normal range creation for ordered ranges.
828 //!
829 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
830 //! search time plus N*size() insertion time.
831 //!
832 //! <b>Note</b>: If an element is inserted it might invalidate elements.
833 //!
834 //! <b>Note</b>: Non-standard extension.
835 template <class InputIterator>
insert(ordered_unique_range_t,InputIterator first,InputIterator last)836 void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
837 { m_flat_tree.insert_unique(ordered_unique_range, first, last); }
838
839 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
840 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
841 //! if there is no element with key equivalent to the key of that element.
842 //!
843 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.first() to il.end())
844 //! search time plus N*size() insertion time.
845 //!
846 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(std::initializer_list<value_type> il)847 void insert(std::initializer_list<value_type> il)
848 { m_flat_tree.insert_unique(il.begin(), il.end()); }
849
850 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
851 //! unique values.
852 //!
853 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
854 //! if there is no element with key equivalent to the key of that element. This
855 //! function is more efficient than the normal range creation for ordered ranges.
856 //!
857 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
858 //! search time plus N*size() insertion time.
859 //!
860 //! <b>Note</b>: If an element is inserted it might invalidate elements.
861 //!
862 //! <b>Note</b>: Non-standard extension.
insert(ordered_unique_range_t,std::initializer_list<value_type> il)863 void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
864 { m_flat_tree.insert_unique(ordered_unique_range, il.begin(), il.end()); }
865 #endif
866
867 //! <b>Effects</b>: Erases the element pointed to by p.
868 //!
869 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
870 //! following q prior to the element being erased. If no such element exists,
871 //! returns end().
872 //!
873 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
874 //!
875 //! <b>Note</b>: Invalidates elements with keys
876 //! not less than the erased element.
erase(const_iterator p)877 iterator erase(const_iterator p)
878 {
879 return container_detail::force_copy<iterator>
880 (m_flat_tree.erase(container_detail::force_copy<impl_const_iterator>(p)));
881 }
882
883 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
884 //!
885 //! <b>Returns</b>: Returns the number of erased elements.
886 //!
887 //! <b>Complexity</b>: Logarithmic search time plus erasure time
888 //! linear to the elements with bigger keys.
erase(const key_type & x)889 size_type erase(const key_type& x)
890 { return m_flat_tree.erase(x); }
891
892 //! <b>Effects</b>: Erases all the elements in the range [first, last).
893 //!
894 //! <b>Returns</b>: Returns last.
895 //!
896 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
897 //!
898 //! <b>Complexity</b>: Logarithmic search time plus erasure time
899 //! linear to the elements with bigger keys.
erase(const_iterator first,const_iterator last)900 iterator erase(const_iterator first, const_iterator last)
901 {
902 return container_detail::force_copy<iterator>(
903 m_flat_tree.erase( container_detail::force_copy<impl_const_iterator>(first)
904 , container_detail::force_copy<impl_const_iterator>(last)));
905 }
906
907 //! <b>Effects</b>: Swaps the contents of *this and x.
908 //!
909 //! <b>Throws</b>: Nothing.
910 //!
911 //! <b>Complexity</b>: Constant.
swap(flat_map & x)912 void swap(flat_map& x)
913 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
914 && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
915 { m_flat_tree.swap(x.m_flat_tree); }
916
917 //! <b>Effects</b>: erase(a.begin(),a.end()).
918 //!
919 //! <b>Postcondition</b>: size() == 0.
920 //!
921 //! <b>Complexity</b>: linear in size().
clear()922 void clear() BOOST_NOEXCEPT_OR_NOTHROW
923 { m_flat_tree.clear(); }
924
925 //////////////////////////////////////////////
926 //
927 // observers
928 //
929 //////////////////////////////////////////////
930
931 //! <b>Effects</b>: Returns the comparison object out
932 //! of which a was constructed.
933 //!
934 //! <b>Complexity</b>: Constant.
key_comp() const935 key_compare key_comp() const
936 { return container_detail::force_copy<key_compare>(m_flat_tree.key_comp()); }
937
938 //! <b>Effects</b>: Returns an object of value_compare constructed out
939 //! of the comparison object.
940 //!
941 //! <b>Complexity</b>: Constant.
value_comp() const942 value_compare value_comp() const
943 { return value_compare(container_detail::force_copy<key_compare>(m_flat_tree.key_comp())); }
944
945 //////////////////////////////////////////////
946 //
947 // map operations
948 //
949 //////////////////////////////////////////////
950
951 //! <b>Returns</b>: An iterator pointing to an element with the key
952 //! equivalent to x, or end() if such an element is not found.
953 //!
954 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)955 iterator find(const key_type& x)
956 { return container_detail::force_copy<iterator>(m_flat_tree.find(x)); }
957
958 //! <b>Returns</b>: A const_iterator pointing to an element with the key
959 //! equivalent to x, or end() if such an element is not found.
960 //!
961 //! <b>Complexity</b>: Logarithmic.s
find(const key_type & x) const962 const_iterator find(const key_type& x) const
963 { return container_detail::force_copy<const_iterator>(m_flat_tree.find(x)); }
964
965 //! <b>Returns</b>: The number of elements with key equivalent to x.
966 //!
967 //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const968 size_type count(const key_type& x) const
969 { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }
970
971 //! <b>Returns</b>: An iterator pointing to the first element with key not less
972 //! than k, or a.end() if such an element is not found.
973 //!
974 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x)975 iterator lower_bound(const key_type& x)
976 { return container_detail::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
977
978 //! <b>Returns</b>: A const iterator pointing to the first element with key not
979 //! less than k, or a.end() if such an element is not found.
980 //!
981 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x) const982 const_iterator lower_bound(const key_type& x) const
983 { return container_detail::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
984
985 //! <b>Returns</b>: An iterator pointing to the first element with key not less
986 //! than x, or end() if such an element is not found.
987 //!
988 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x)989 iterator upper_bound(const key_type& x)
990 { return container_detail::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
991
992 //! <b>Returns</b>: A const iterator pointing to the first element with key not
993 //! less than x, or end() if such an element is not found.
994 //!
995 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x) const996 const_iterator upper_bound(const key_type& x) const
997 { return container_detail::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
998
999 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1000 //!
1001 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x)1002 std::pair<iterator,iterator> equal_range(const key_type& x)
1003 { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); }
1004
1005 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1006 //!
1007 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x) const1008 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
1009 { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }
1010
1011 //! <b>Effects</b>: Returns true if x and y are equal
1012 //!
1013 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator ==(const flat_map & x,const flat_map & y)1014 friend bool operator==(const flat_map& x, const flat_map& y)
1015 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1016
1017 //! <b>Effects</b>: Returns true if x and y are unequal
1018 //!
1019 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator !=(const flat_map & x,const flat_map & y)1020 friend bool operator!=(const flat_map& x, const flat_map& y)
1021 { return !(x == y); }
1022
1023 //! <b>Effects</b>: Returns true if x is less than y
1024 //!
1025 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <(const flat_map & x,const flat_map & y)1026 friend bool operator<(const flat_map& x, const flat_map& y)
1027 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1028
1029 //! <b>Effects</b>: Returns true if x is greater than y
1030 //!
1031 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >(const flat_map & x,const flat_map & y)1032 friend bool operator>(const flat_map& x, const flat_map& y)
1033 { return y < x; }
1034
1035 //! <b>Effects</b>: Returns true if x is equal or less than y
1036 //!
1037 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <=(const flat_map & x,const flat_map & y)1038 friend bool operator<=(const flat_map& x, const flat_map& y)
1039 { return !(y < x); }
1040
1041 //! <b>Effects</b>: Returns true if x is equal or greater than y
1042 //!
1043 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >=(const flat_map & x,const flat_map & y)1044 friend bool operator>=(const flat_map& x, const flat_map& y)
1045 { return !(x < y); }
1046
1047 //! <b>Effects</b>: x.swap(y)
1048 //!
1049 //! <b>Complexity</b>: Constant.
swap(flat_map & x,flat_map & y)1050 friend void swap(flat_map& x, flat_map& y)
1051 { x.swap(y); }
1052
1053 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1054 private:
priv_subscript(const key_type & k)1055 mapped_type &priv_subscript(const key_type& k)
1056 {
1057 iterator i = lower_bound(k);
1058 // i->first is greater than or equivalent to k.
1059 if (i == end() || key_comp()(k, (*i).first)){
1060 container_detail::value_init<mapped_type> m;
1061 i = insert(i, impl_value_type(k, ::boost::move(m.m_t)));
1062 }
1063 return (*i).second;
1064 }
priv_subscript(BOOST_RV_REF (key_type)mk)1065 mapped_type &priv_subscript(BOOST_RV_REF(key_type) mk)
1066 {
1067 key_type &k = mk;
1068 iterator i = lower_bound(k);
1069 // i->first is greater than or equivalent to k.
1070 if (i == end() || key_comp()(k, (*i).first)){
1071 container_detail::value_init<mapped_type> m;
1072 i = insert(i, impl_value_type(boost::move(k), ::boost::move(m.m_t)));
1073 }
1074 return (*i).second;
1075 }
1076 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1077 };
1078
1079 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1080
1081 } //namespace container {
1082
1083 //!has_trivial_destructor_after_move<> == true_type
1084 //!specialization for optimizations
1085 template <class Key, class T, class Compare, class Allocator>
1086 struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, Allocator> >
1087 {
1088 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1089 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1090 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1091 ::boost::has_trivial_destructor_after_move<Compare>::value;
1092 };
1093
1094 namespace container {
1095
1096 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1097
1098 //! A flat_multimap is a kind of associative container that supports equivalent keys
1099 //! (possibly containing multiple copies of the same key value) and provides for
1100 //! fast retrieval of values of another type T based on the keys. The flat_multimap
1101 //! class supports random-access iterators.
1102 //!
1103 //! A flat_multimap satisfies all of the requirements of a container and of a reversible
1104 //! container and of an associative container. For a
1105 //! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
1106 //! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
1107 //!
1108 //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1109 //!
1110 //! Allocator is the allocator to allocate the value_types
1111 //! (e.g. <i>allocator< std::pair<Key, T> ></i>).
1112 //!
1113 //! flat_multimap is similar to std::multimap but it's implemented like an ordered vector.
1114 //! This means that inserting a new element into a flat_map invalidates
1115 //! previous iterators and references
1116 //!
1117 //! Erasing an element invalidates iterators and references
1118 //! pointing to elements that come after (their keys are bigger) the erased element.
1119 //!
1120 //! This container provides random-access iterators.
1121 //!
1122 //! \tparam Key is the key_type of the map
1123 //! \tparam Value is the <code>mapped_type</code>
1124 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1125 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
1126 //! (e.g. <i>allocator< std::pair<Key, T> > </i>).
1127 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1128 template <class Key, class T, class Compare = std::less<Key>, class Allocator = new_allocator< std::pair< Key, T> > >
1129 #else
1130 template <class Key, class T, class Compare, class Allocator>
1131 #endif
1132 class flat_multimap
1133 {
1134 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1135 private:
1136 BOOST_COPYABLE_AND_MOVABLE(flat_multimap)
1137 typedef container_detail::flat_tree<Key,
1138 std::pair<Key, T>,
1139 container_detail::select1st< std::pair<Key, T> >,
1140 Compare,
1141 Allocator> tree_t;
1142 //This is the real tree stored here. It's based on a movable pair
1143 typedef container_detail::flat_tree<Key,
1144 container_detail::pair<Key, T>,
1145 container_detail::select1st<container_detail::pair<Key, T> >,
1146 Compare,
1147 typename allocator_traits<Allocator>::template portable_rebind_alloc
1148 <container_detail::pair<Key, T> >::type> impl_tree_t;
1149 impl_tree_t m_flat_tree; // flat tree representing flat_map
1150
1151 typedef typename impl_tree_t::value_type impl_value_type;
1152 typedef typename impl_tree_t::const_iterator impl_const_iterator;
1153 typedef typename impl_tree_t::iterator impl_iterator;
1154 typedef typename impl_tree_t::allocator_type impl_allocator_type;
1155 typedef container_detail::flat_tree_value_compare
1156 < Compare
1157 , container_detail::select1st< std::pair<Key, T> >
1158 , std::pair<Key, T> > value_compare_impl;
1159 typedef typename container_detail::get_flat_tree_iterators
1160 <typename allocator_traits<Allocator>::pointer>::iterator iterator_impl;
1161 typedef typename container_detail::get_flat_tree_iterators
1162 <typename allocator_traits<Allocator>::pointer>::const_iterator const_iterator_impl;
1163 typedef typename container_detail::get_flat_tree_iterators
1164 <typename allocator_traits<Allocator>::pointer>::reverse_iterator reverse_iterator_impl;
1165 typedef typename container_detail::get_flat_tree_iterators
1166 <typename allocator_traits<Allocator>::pointer>::const_reverse_iterator const_reverse_iterator_impl;
1167 public:
1168 typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type;
1169 private:
1170 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1171
1172 public:
1173
1174 //////////////////////////////////////////////
1175 //
1176 // types
1177 //
1178 //////////////////////////////////////////////
1179 typedef Key key_type;
1180 typedef T mapped_type;
1181 typedef std::pair<Key, T> value_type;
1182 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
1183 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
1184 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
1185 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
1186 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
1187 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
1188 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
1189 typedef Allocator allocator_type;
1190 typedef BOOST_CONTAINER_IMPDEF(Allocator) stored_allocator_type;
1191 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
1192 typedef Compare key_compare;
1193 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
1194 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
1195 typedef BOOST_CONTAINER_IMPDEF(reverse_iterator_impl) reverse_iterator;
1196 typedef BOOST_CONTAINER_IMPDEF(const_reverse_iterator_impl) const_reverse_iterator;
1197 typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type;
1198
1199 //////////////////////////////////////////////
1200 //
1201 // construct/copy/destroy
1202 //
1203 //////////////////////////////////////////////
1204
1205 //! <b>Effects</b>: Default constructs an empty flat_map.
1206 //!
1207 //! <b>Complexity</b>: Constant.
flat_multimap()1208 flat_multimap()
1209 : m_flat_tree()
1210 {
1211 //A type must be std::pair<Key, T>
1212 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1213 }
1214
1215 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison
1216 //! object and allocator.
1217 //!
1218 //! <b>Complexity</b>: Constant.
flat_multimap(const Compare & comp,const allocator_type & a=allocator_type ())1219 explicit flat_multimap(const Compare& comp,
1220 const allocator_type& a = allocator_type())
1221 : m_flat_tree(comp, container_detail::force<impl_allocator_type>(a))
1222 {
1223 //A type must be std::pair<Key, T>
1224 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1225 }
1226
1227 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified allocator.
1228 //!
1229 //! <b>Complexity</b>: Constant.
flat_multimap(const allocator_type & a)1230 explicit flat_multimap(const allocator_type& a)
1231 : m_flat_tree(container_detail::force<impl_allocator_type>(a))
1232 {
1233 //A type must be std::pair<Key, T>
1234 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1235 }
1236
1237 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object
1238 //! and allocator, and inserts elements from the range [first ,last ).
1239 //!
1240 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1241 //! comp and otherwise N logN, where N is last - first.
1242 template <class InputIterator>
flat_multimap(InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1243 flat_multimap(InputIterator first, InputIterator last,
1244 const Compare& comp = Compare(),
1245 const allocator_type& a = allocator_type())
1246 : m_flat_tree(false, first, last, comp, container_detail::force<impl_allocator_type>(a))
1247 {
1248 //A type must be std::pair<Key, T>
1249 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1250 }
1251
1252 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified
1253 //! allocator, and inserts elements from the range [first ,last ).
1254 //!
1255 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1256 //! comp and otherwise N logN, where N is last - first.
1257 template <class InputIterator>
flat_multimap(InputIterator first,InputIterator last,const allocator_type & a)1258 flat_multimap(InputIterator first, InputIterator last, const allocator_type& a)
1259 : m_flat_tree(false, first, last, Compare(), container_detail::force<impl_allocator_type>(a))
1260 {
1261 //A type must be std::pair<Key, T>
1262 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1263 }
1264
1265 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1266 //! allocator, and inserts elements from the ordered range [first ,last). This function
1267 //! is more efficient than the normal range creation for ordered ranges.
1268 //!
1269 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1270 //!
1271 //! <b>Complexity</b>: Linear in N.
1272 //!
1273 //! <b>Note</b>: Non-standard extension.
1274 template <class InputIterator>
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1275 flat_multimap(ordered_range_t, InputIterator first, InputIterator last,
1276 const Compare& comp = Compare(),
1277 const allocator_type& a = allocator_type())
1278 : m_flat_tree(ordered_range, first, last, comp, a)
1279 {
1280 //A type must be std::pair<Key, T>
1281 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1282 }
1283
1284 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1285 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
1286 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1287 //!
1288 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1289 //! comp and otherwise N logN, where N is last - first.
flat_multimap(std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1290 flat_multimap(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
1291 : m_flat_tree(false, il.begin(), il.end(), comp, container_detail::force<impl_allocator_type>(a))
1292 {
1293 //A type must be std::pair<Key, T>
1294 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1295 }
1296
1297 //! <b>Effects</b>: Constructs an empty flat_map using the specified
1298 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1299 //!
1300 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1301 //! comp and otherwise N logN, where N is last - first.
flat_multimap(std::initializer_list<value_type> il,const allocator_type & a)1302 flat_multimap(std::initializer_list<value_type> il, const allocator_type& a)
1303 : m_flat_tree(false, il.begin(), il.end(), Compare(), container_detail::force<impl_allocator_type>(a))
1304 {
1305 //A type must be std::pair<Key, T>
1306 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1307 }
1308
1309 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1310 //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function
1311 //! is more efficient than the normal range creation for ordered ranges.
1312 //!
1313 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1314 //!
1315 //! <b>Complexity</b>: Linear in N.
1316 //!
1317 //! <b>Note</b>: Non-standard extension.
flat_multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1318 flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(),
1319 const allocator_type& a = allocator_type())
1320 : m_flat_tree(ordered_range, il.begin(), il.end(), comp, a)
1321 {
1322 //A type must be std::pair<Key, T>
1323 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1324 }
1325 #endif
1326
1327 //! <b>Effects</b>: Copy constructs a flat_multimap.
1328 //!
1329 //! <b>Complexity</b>: Linear in x.size().
flat_multimap(const flat_multimap & x)1330 flat_multimap(const flat_multimap& x)
1331 : m_flat_tree(x.m_flat_tree)
1332 {
1333 //A type must be std::pair<Key, T>
1334 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1335 }
1336
1337 //! <b>Effects</b>: Move constructs a flat_multimap. Constructs *this using x's resources.
1338 //!
1339 //! <b>Complexity</b>: Constant.
1340 //!
1341 //! <b>Postcondition</b>: x is emptied.
flat_multimap(BOOST_RV_REF (flat_multimap)x)1342 flat_multimap(BOOST_RV_REF(flat_multimap) x)
1343 : m_flat_tree(boost::move(x.m_flat_tree))
1344 {
1345 //A type must be std::pair<Key, T>
1346 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1347 }
1348
1349 //! <b>Effects</b>: Copy constructs a flat_multimap using the specified allocator.
1350 //!
1351 //! <b>Complexity</b>: Linear in x.size().
flat_multimap(const flat_multimap & x,const allocator_type & a)1352 flat_multimap(const flat_multimap& x, const allocator_type &a)
1353 : m_flat_tree(x.m_flat_tree, a)
1354 {
1355 //A type must be std::pair<Key, T>
1356 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1357 }
1358
1359 //! <b>Effects</b>: Move constructs a flat_multimap using the specified allocator.
1360 //! Constructs *this using x's resources.
1361 //!
1362 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
flat_multimap(BOOST_RV_REF (flat_multimap)x,const allocator_type & a)1363 flat_multimap(BOOST_RV_REF(flat_multimap) x, const allocator_type &a)
1364 : m_flat_tree(boost::move(x.m_flat_tree), a)
1365 {
1366 //A type must be std::pair<Key, T>
1367 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1368 }
1369
1370 //! <b>Effects</b>: Makes *this a copy of x.
1371 //!
1372 //! <b>Complexity</b>: Linear in x.size().
operator =(BOOST_COPY_ASSIGN_REF (flat_multimap)x)1373 flat_multimap& operator=(BOOST_COPY_ASSIGN_REF(flat_multimap) x)
1374 { m_flat_tree = x.m_flat_tree; return *this; }
1375
1376 //! <b>Effects</b>: this->swap(x.get()).
1377 //!
1378 //! <b>Complexity</b>: Constant.
operator =(BOOST_RV_REF (flat_multimap)x)1379 flat_multimap& operator=(BOOST_RV_REF(flat_multimap) x)
1380 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1381 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value )
1382 { m_flat_tree = boost::move(x.m_flat_tree); return *this; }
1383
1384 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1385 //! <b>Effects</b>: Assign content of il to *this
1386 //!
1387 //! <b>Complexity</b>: Linear in il.size().
operator =(std::initializer_list<value_type> il)1388 flat_multimap& operator=(std::initializer_list<value_type> il)
1389 {
1390 this->clear();
1391 this->insert(il.begin(), il.end());
1392 return *this;
1393 }
1394 #endif
1395
1396 //! <b>Effects</b>: Returns a copy of the allocator that
1397 //! was passed to the object's constructor.
1398 //!
1399 //! <b>Complexity</b>: Constant.
get_allocator() const1400 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
1401 { return container_detail::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
1402
1403 //! <b>Effects</b>: Returns a reference to the internal allocator.
1404 //!
1405 //! <b>Throws</b>: Nothing
1406 //!
1407 //! <b>Complexity</b>: Constant.
1408 //!
1409 //! <b>Note</b>: Non-standard extension.
get_stored_allocator()1410 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
1411 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
1412
1413 //! <b>Effects</b>: Returns a reference to the internal allocator.
1414 //!
1415 //! <b>Throws</b>: Nothing
1416 //!
1417 //! <b>Complexity</b>: Constant.
1418 //!
1419 //! <b>Note</b>: Non-standard extension.
get_stored_allocator() const1420 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
1421 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
1422
1423 //////////////////////////////////////////////
1424 //
1425 // iterators
1426 //
1427 //////////////////////////////////////////////
1428
1429 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
1430 //!
1431 //! <b>Throws</b>: Nothing.
1432 //!
1433 //! <b>Complexity</b>: Constant.
begin()1434 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
1435 { return container_detail::force_copy<iterator>(m_flat_tree.begin()); }
1436
1437 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
1438 //!
1439 //! <b>Throws</b>: Nothing.
1440 //!
1441 //! <b>Complexity</b>: Constant.
begin() const1442 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
1443 { return container_detail::force_copy<const_iterator>(m_flat_tree.begin()); }
1444
1445 //! <b>Effects</b>: Returns an iterator to the end of the container.
1446 //!
1447 //! <b>Throws</b>: Nothing.
1448 //!
1449 //! <b>Complexity</b>: Constant.
end()1450 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
1451 { return container_detail::force_copy<iterator>(m_flat_tree.end()); }
1452
1453 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
1454 //!
1455 //! <b>Throws</b>: Nothing.
1456 //!
1457 //! <b>Complexity</b>: Constant.
end() const1458 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
1459 { return container_detail::force_copy<const_iterator>(m_flat_tree.end()); }
1460
1461 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1462 //! of the reversed container.
1463 //!
1464 //! <b>Throws</b>: Nothing.
1465 //!
1466 //! <b>Complexity</b>: Constant.
rbegin()1467 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
1468 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
1469
1470 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1471 //! of the reversed container.
1472 //!
1473 //! <b>Throws</b>: Nothing.
1474 //!
1475 //! <b>Complexity</b>: Constant.
rbegin() const1476 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1477 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
1478
1479 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1480 //! of the reversed container.
1481 //!
1482 //! <b>Throws</b>: Nothing.
1483 //!
1484 //! <b>Complexity</b>: Constant.
rend()1485 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1486 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rend()); }
1487
1488 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1489 //! of the reversed container.
1490 //!
1491 //! <b>Throws</b>: Nothing.
1492 //!
1493 //! <b>Complexity</b>: Constant.
rend() const1494 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1495 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
1496
1497 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
1498 //!
1499 //! <b>Throws</b>: Nothing.
1500 //!
1501 //! <b>Complexity</b>: Constant.
cbegin() const1502 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1503 { return container_detail::force_copy<const_iterator>(m_flat_tree.cbegin()); }
1504
1505 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
1506 //!
1507 //! <b>Throws</b>: Nothing.
1508 //!
1509 //! <b>Complexity</b>: Constant.
cend() const1510 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1511 { return container_detail::force_copy<const_iterator>(m_flat_tree.cend()); }
1512
1513 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1514 //! of the reversed container.
1515 //!
1516 //! <b>Throws</b>: Nothing.
1517 //!
1518 //! <b>Complexity</b>: Constant.
crbegin() const1519 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1520 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
1521
1522 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1523 //! of the reversed container.
1524 //!
1525 //! <b>Throws</b>: Nothing.
1526 //!
1527 //! <b>Complexity</b>: Constant.
crend() const1528 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
1529 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
1530
1531 //////////////////////////////////////////////
1532 //
1533 // capacity
1534 //
1535 //////////////////////////////////////////////
1536
1537 //! <b>Effects</b>: Returns true if the container contains no elements.
1538 //!
1539 //! <b>Throws</b>: Nothing.
1540 //!
1541 //! <b>Complexity</b>: Constant.
empty() const1542 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1543 { return m_flat_tree.empty(); }
1544
1545 //! <b>Effects</b>: Returns the number of the elements contained in the container.
1546 //!
1547 //! <b>Throws</b>: Nothing.
1548 //!
1549 //! <b>Complexity</b>: Constant.
size() const1550 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1551 { return m_flat_tree.size(); }
1552
1553 //! <b>Effects</b>: Returns the largest possible size of the container.
1554 //!
1555 //! <b>Throws</b>: Nothing.
1556 //!
1557 //! <b>Complexity</b>: Constant.
max_size() const1558 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1559 { return m_flat_tree.max_size(); }
1560
1561 //! <b>Effects</b>: Number of elements for which memory has been allocated.
1562 //! capacity() is always greater than or equal to size().
1563 //!
1564 //! <b>Throws</b>: Nothing.
1565 //!
1566 //! <b>Complexity</b>: Constant.
capacity() const1567 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
1568 { return m_flat_tree.capacity(); }
1569
1570 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
1571 //! effect. Otherwise, it is a request for allocation of additional memory.
1572 //! If the request is successful, then capacity() is greater than or equal to
1573 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
1574 //!
1575 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
1576 //!
1577 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
1578 //! to values might be invalidated.
reserve(size_type cnt)1579 void reserve(size_type cnt)
1580 { m_flat_tree.reserve(cnt); }
1581
1582 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1583 // with previous allocations. The size of the vector is unchanged
1584 //!
1585 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1586 //!
1587 //! <b>Complexity</b>: Linear to size().
shrink_to_fit()1588 void shrink_to_fit()
1589 { m_flat_tree.shrink_to_fit(); }
1590
1591 //! @copydoc ::boost::container::flat_set::nth(size_type)
nth(size_type n)1592 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1593 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
1594
1595 //! @copydoc ::boost::container::flat_set::nth(size_type) const
nth(size_type n) const1596 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1597 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
1598
1599 //! @copydoc ::boost::container::flat_set::index_of(iterator)
index_of(iterator p)1600 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1601 { return m_flat_tree.index_of(container_detail::force_copy<impl_iterator>(p)); }
1602
1603 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
index_of(const_iterator p) const1604 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1605 { return m_flat_tree.index_of(container_detail::force_copy<impl_const_iterator>(p)); }
1606
1607 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1608
1609 //! <b>Effects</b>: Inserts an object of type T constructed with
1610 //! std::forward<Args>(args)... and returns the iterator pointing to the
1611 //! newly inserted element.
1612 //!
1613 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1614 //! to the elements with bigger keys than x.
1615 //!
1616 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1617 template <class... Args>
emplace(BOOST_FWD_REF (Args)...args)1618 iterator emplace(BOOST_FWD_REF(Args)... args)
1619 { return container_detail::force_copy<iterator>(m_flat_tree.emplace_equal(boost::forward<Args>(args)...)); }
1620
1621 //! <b>Effects</b>: Inserts an object of type T constructed with
1622 //! std::forward<Args>(args)... in the container.
1623 //! p is a hint pointing to where the insert should start to search.
1624 //!
1625 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1626 //! to the key of x.
1627 //!
1628 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1629 //! is to be inserted before p) plus linear insertion
1630 //! to the elements with bigger keys than x.
1631 //!
1632 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1633 template <class... Args>
emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)1634 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
1635 {
1636 return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_equal
1637 (container_detail::force_copy<impl_const_iterator>(hint), boost::forward<Args>(args)...));
1638 }
1639
1640 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1641
1642 #define BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE(N) \
1643 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1644 iterator emplace(BOOST_MOVE_UREF##N)\
1645 { return container_detail::force_copy<iterator>(m_flat_tree.emplace_equal(BOOST_MOVE_FWD##N)); }\
1646 \
1647 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1648 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1649 {\
1650 return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_equal\
1651 (container_detail::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1652 }\
1653 //
BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)1654 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)
1655 #undef BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE
1656
1657 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1658
1659 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1660 //! newly inserted element.
1661 //!
1662 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1663 //! to the elements with bigger keys than x.
1664 //!
1665 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1666 iterator insert(const value_type& x)
1667 {
1668 return container_detail::force_copy<iterator>(
1669 m_flat_tree.insert_equal(container_detail::force<impl_value_type>(x)));
1670 }
1671
1672 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1673 //! the iterator pointing to the newly inserted element.
1674 //!
1675 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1676 //! to the elements with bigger keys than x.
1677 //!
1678 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (value_type)x)1679 iterator insert(BOOST_RV_REF(value_type) x)
1680 { return container_detail::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
1681
1682 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1683 //! the iterator pointing to the newly inserted element.
1684 //!
1685 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1686 //! to the elements with bigger keys than x.
1687 //!
1688 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (impl_value_type)x)1689 iterator insert(BOOST_RV_REF(impl_value_type) x)
1690 { return container_detail::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
1691
1692 //! <b>Effects</b>: Inserts a copy of x in the container.
1693 //! p is a hint pointing to where the insert should start to search.
1694 //!
1695 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1696 //! to the key of x.
1697 //!
1698 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1699 //! is to be inserted before p) plus linear insertion
1700 //! to the elements with bigger keys than x.
1701 //!
1702 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,const value_type & x)1703 iterator insert(const_iterator p, const value_type& x)
1704 {
1705 return container_detail::force_copy<iterator>
1706 (m_flat_tree.insert_equal( container_detail::force_copy<impl_const_iterator>(p)
1707 , container_detail::force<impl_value_type>(x)));
1708 }
1709
1710 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
1711 //! p is a hint pointing to where the insert should start to search.
1712 //!
1713 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1714 //! to the key of x.
1715 //!
1716 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1717 //! is to be inserted before p) plus linear insertion
1718 //! to the elements with bigger keys than x.
1719 //!
1720 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (value_type)x)1721 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
1722 {
1723 return container_detail::force_copy<iterator>
1724 (m_flat_tree.insert_equal(container_detail::force_copy<impl_const_iterator>(p)
1725 , boost::move(x)));
1726 }
1727
1728 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
1729 //! p is a hint pointing to where the insert should start to search.
1730 //!
1731 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1732 //! to the key of x.
1733 //!
1734 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1735 //! is to be inserted before p) plus linear insertion
1736 //! to the elements with bigger keys than x.
1737 //!
1738 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (impl_value_type)x)1739 iterator insert(const_iterator p, BOOST_RV_REF(impl_value_type) x)
1740 {
1741 return container_detail::force_copy<iterator>(
1742 m_flat_tree.insert_equal(container_detail::force_copy<impl_const_iterator>(p), boost::move(x)));
1743 }
1744
1745 //! <b>Requires</b>: first, last are not iterators into *this.
1746 //!
1747 //! <b>Effects</b>: inserts each element from the range [first,last) .
1748 //!
1749 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1750 //! search time plus N*size() insertion time.
1751 //!
1752 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1753 template <class InputIterator>
insert(InputIterator first,InputIterator last)1754 void insert(InputIterator first, InputIterator last)
1755 { m_flat_tree.insert_equal(first, last); }
1756
1757 //! <b>Requires</b>: first, last are not iterators into *this.
1758 //!
1759 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1760 //!
1761 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1762 //! if there is no element with key equivalent to the key of that element. This
1763 //! function is more efficient than the normal range creation for ordered ranges.
1764 //!
1765 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1766 //! search time plus N*size() insertion time.
1767 //!
1768 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1769 //!
1770 //! <b>Note</b>: Non-standard extension.
1771 template <class InputIterator>
insert(ordered_range_t,InputIterator first,InputIterator last)1772 void insert(ordered_range_t, InputIterator first, InputIterator last)
1773 { m_flat_tree.insert_equal(ordered_range, first, last); }
1774
1775 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1776 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .
1777 //!
1778 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1779 //! search time plus N*size() insertion time.
1780 //!
1781 //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(std::initializer_list<value_type> il)1782 void insert(std::initializer_list<value_type> il)
1783 { m_flat_tree.insert_equal(il.begin(), il.end()); }
1784
1785 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1786 //!
1787 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1788 //! if there is no element with key equivalent to the key of that element. This
1789 //! function is more efficient than the normal range creation for ordered ranges.
1790 //!
1791 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1792 //! search time plus N*size() insertion time.
1793 //!
1794 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1795 //!
1796 //! <b>Note</b>: Non-standard extension.
insert(ordered_range_t,std::initializer_list<value_type> il)1797 void insert(ordered_range_t, std::initializer_list<value_type> il)
1798 { m_flat_tree.insert_equal(ordered_range, il.begin(), il.end()); }
1799 #endif
1800
1801 //! <b>Effects</b>: Erases the element pointed to by p.
1802 //!
1803 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1804 //! following q prior to the element being erased. If no such element exists,
1805 //! returns end().
1806 //!
1807 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
1808 //!
1809 //! <b>Note</b>: Invalidates elements with keys
1810 //! not less than the erased element.
erase(const_iterator p)1811 iterator erase(const_iterator p)
1812 {
1813 return container_detail::force_copy<iterator>(
1814 m_flat_tree.erase(container_detail::force_copy<impl_const_iterator>(p)));
1815 }
1816
1817 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1818 //!
1819 //! <b>Returns</b>: Returns the number of erased elements.
1820 //!
1821 //! <b>Complexity</b>: Logarithmic search time plus erasure time
1822 //! linear to the elements with bigger keys.
erase(const key_type & x)1823 size_type erase(const key_type& x)
1824 { return m_flat_tree.erase(x); }
1825
1826 //! <b>Effects</b>: Erases all the elements in the range [first, last).
1827 //!
1828 //! <b>Returns</b>: Returns last.
1829 //!
1830 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
1831 //!
1832 //! <b>Complexity</b>: Logarithmic search time plus erasure time
1833 //! linear to the elements with bigger keys.
erase(const_iterator first,const_iterator last)1834 iterator erase(const_iterator first, const_iterator last)
1835 {
1836 return container_detail::force_copy<iterator>
1837 (m_flat_tree.erase( container_detail::force_copy<impl_const_iterator>(first)
1838 , container_detail::force_copy<impl_const_iterator>(last)));
1839 }
1840
1841 //! <b>Effects</b>: Swaps the contents of *this and x.
1842 //!
1843 //! <b>Throws</b>: Nothing.
1844 //!
1845 //! <b>Complexity</b>: Constant.
swap(flat_multimap & x)1846 void swap(flat_multimap& x)
1847 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1848 && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
1849 { m_flat_tree.swap(x.m_flat_tree); }
1850
1851 //! <b>Effects</b>: erase(a.begin(),a.end()).
1852 //!
1853 //! <b>Postcondition</b>: size() == 0.
1854 //!
1855 //! <b>Complexity</b>: linear in size().
clear()1856 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1857 { m_flat_tree.clear(); }
1858
1859 //////////////////////////////////////////////
1860 //
1861 // observers
1862 //
1863 //////////////////////////////////////////////
1864
1865 //! <b>Effects</b>: Returns the comparison object out
1866 //! of which a was constructed.
1867 //!
1868 //! <b>Complexity</b>: Constant.
key_comp() const1869 key_compare key_comp() const
1870 { return container_detail::force_copy<key_compare>(m_flat_tree.key_comp()); }
1871
1872 //! <b>Effects</b>: Returns an object of value_compare constructed out
1873 //! of the comparison object.
1874 //!
1875 //! <b>Complexity</b>: Constant.
value_comp() const1876 value_compare value_comp() const
1877 { return value_compare(container_detail::force_copy<key_compare>(m_flat_tree.key_comp())); }
1878
1879 //////////////////////////////////////////////
1880 //
1881 // map operations
1882 //
1883 //////////////////////////////////////////////
1884
1885 //! <b>Returns</b>: An iterator pointing to an element with the key
1886 //! equivalent to x, or end() if such an element is not found.
1887 //!
1888 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)1889 iterator find(const key_type& x)
1890 { return container_detail::force_copy<iterator>(m_flat_tree.find(x)); }
1891
1892 //! <b>Returns</b>: An const_iterator pointing to an element with the key
1893 //! equivalent to x, or end() if such an element is not found.
1894 //!
1895 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const1896 const_iterator find(const key_type& x) const
1897 { return container_detail::force_copy<const_iterator>(m_flat_tree.find(x)); }
1898
1899 //! <b>Returns</b>: The number of elements with key equivalent to x.
1900 //!
1901 //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const1902 size_type count(const key_type& x) const
1903 { return m_flat_tree.count(x); }
1904
1905 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1906 //! than k, or a.end() if such an element is not found.
1907 //!
1908 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x)1909 iterator lower_bound(const key_type& x)
1910 { return container_detail::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
1911
1912 //! <b>Returns</b>: A const iterator pointing to the first element with key
1913 //! not less than k, or a.end() if such an element is not found.
1914 //!
1915 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x) const1916 const_iterator lower_bound(const key_type& x) const
1917 { return container_detail::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
1918
1919 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1920 //! than x, or end() if such an element is not found.
1921 //!
1922 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x)1923 iterator upper_bound(const key_type& x)
1924 {return container_detail::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
1925
1926 //! <b>Returns</b>: A const iterator pointing to the first element with key
1927 //! not less than x, or end() if such an element is not found.
1928 //!
1929 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x) const1930 const_iterator upper_bound(const key_type& x) const
1931 { return container_detail::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
1932
1933 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1934 //!
1935 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x)1936 std::pair<iterator,iterator> equal_range(const key_type& x)
1937 { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
1938
1939 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1940 //!
1941 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x) const1942 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
1943 { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
1944
1945 //! <b>Effects</b>: Returns true if x and y are equal
1946 //!
1947 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator ==(const flat_multimap & x,const flat_multimap & y)1948 friend bool operator==(const flat_multimap& x, const flat_multimap& y)
1949 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1950
1951 //! <b>Effects</b>: Returns true if x and y are unequal
1952 //!
1953 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator !=(const flat_multimap & x,const flat_multimap & y)1954 friend bool operator!=(const flat_multimap& x, const flat_multimap& y)
1955 { return !(x == y); }
1956
1957 //! <b>Effects</b>: Returns true if x is less than y
1958 //!
1959 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <(const flat_multimap & x,const flat_multimap & y)1960 friend bool operator<(const flat_multimap& x, const flat_multimap& y)
1961 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1962
1963 //! <b>Effects</b>: Returns true if x is greater than y
1964 //!
1965 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >(const flat_multimap & x,const flat_multimap & y)1966 friend bool operator>(const flat_multimap& x, const flat_multimap& y)
1967 { return y < x; }
1968
1969 //! <b>Effects</b>: Returns true if x is equal or less than y
1970 //!
1971 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <=(const flat_multimap & x,const flat_multimap & y)1972 friend bool operator<=(const flat_multimap& x, const flat_multimap& y)
1973 { return !(y < x); }
1974
1975 //! <b>Effects</b>: Returns true if x is equal or greater than y
1976 //!
1977 //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >=(const flat_multimap & x,const flat_multimap & y)1978 friend bool operator>=(const flat_multimap& x, const flat_multimap& y)
1979 { return !(x < y); }
1980
1981 //! <b>Effects</b>: x.swap(y)
1982 //!
1983 //! <b>Complexity</b>: Constant.
swap(flat_multimap & x,flat_multimap & y)1984 friend void swap(flat_multimap& x, flat_multimap& y)
1985 { x.swap(y); }
1986 };
1987
1988 }}
1989
1990 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1991
1992 namespace boost {
1993
1994 //!has_trivial_destructor_after_move<> == true_type
1995 //!specialization for optimizations
1996 template <class Key, class T, class Compare, class Allocator>
1997 struct has_trivial_destructor_after_move< boost::container::flat_multimap<Key, T, Compare, Allocator> >
1998 {
1999 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
2000 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
2001 ::boost::has_trivial_destructor_after_move<pointer>::value &&
2002 ::boost::has_trivial_destructor_after_move<Compare>::value;
2003 };
2004
2005 } //namespace boost {
2006
2007 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2008
2009 #include <boost/container/detail/config_end.hpp>
2010
2011 #endif // BOOST_CONTAINER_FLAT_MAP_HPP
2012