1 //////////////////////////////////////////////////////////////////////////////
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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
10 #ifndef BOOST_CONTAINER_MAP_HPP
11 #define BOOST_CONTAINER_MAP_HPP
13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
25 #include <boost/container/container_fwd.hpp>
26 #include <boost/container/new_allocator.hpp> //new_allocator
27 #include <boost/container/throw_exception.hpp>
29 #include <boost/container/detail/mpl.hpp>
30 #include <boost/container/detail/tree.hpp>
31 #include <boost/container/detail/type_traits.hpp>
32 #include <boost/container/detail/value_init.hpp>
33 #include <boost/container/detail/pair.hpp>
34 #include <boost/container/detail/pair_key_mapped_of_value.hpp>
37 #include <boost/move/traits.hpp>
38 #include <boost/move/utility_core.hpp>
40 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
41 #include <boost/move/detail/fwd_macros.hpp>
43 #include <boost/move/detail/move_helpers.hpp>
45 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
46 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
48 #include <boost/static_assert.hpp>
49 #include <boost/core/no_exceptions_support.hpp>
51 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
52 #include <initializer_list>
58 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
60 //! A map is a kind of associative container that supports unique keys (contains at
61 //! most one of each key value) and provides for fast retrieval of values of another
62 //! type T based on the keys. The map class supports bidirectional iterators.
64 //! A map satisfies all of the requirements of a container and of a reversible
65 //! container and of an associative container. The <code>value_type</code> stored
66 //! by this container is the value_type is std::pair<const Key, T>.
68 //! \tparam Key is the key_type of the map
69 //! \tparam T is the <code>mapped_type</code>
70 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
71 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
72 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
73 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
74 template < class Key, class T, class Compare = std::less<Key>
75 , class Allocator = void, class Options = tree_assoc_defaults >
77 template <class Key, class T, class Compare, class Allocator, class Options>
82 < std::pair<const Key, T>
84 , Compare, Allocator, Options>
87 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
89 BOOST_COPYABLE_AND_MOVABLE(map)
91 typedef int select_1st_t;
92 typedef std::pair<const Key, T> value_type_impl;
94 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t;
95 typedef dtl::pair <Key, T> movable_value_type_impl;
96 typedef typename base_t::value_compare value_compare_impl;
97 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
100 //////////////////////////////////////////////
104 //////////////////////////////////////////////
106 typedef Key key_type;
107 typedef T mapped_type;
108 typedef typename base_t::allocator_type allocator_type;
109 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
110 typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type;
111 typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer;
112 typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer;
113 typedef typename boost::container::allocator_traits<allocator_type>::reference reference;
114 typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference;
115 typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type;
116 typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_type;
117 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
118 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
119 typedef Compare key_compare;
120 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
121 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
122 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
123 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
124 typedef std::pair<key_type, mapped_type> nonconst_value_type;
125 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type;
126 typedef BOOST_CONTAINER_IMPDEF(node_handle<
127 typename base_t::stored_allocator_type
128 BOOST_MOVE_I pair_key_mapped_of_value
129 <key_type BOOST_MOVE_I mapped_type> >) node_type;
130 typedef BOOST_CONTAINER_IMPDEF
131 (insert_return_type_base<iterator BOOST_MOVE_I node_type>) insert_return_type;
133 //allocator_type::value_type type must be std::pair<CONST Key, T>
134 BOOST_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value));
136 //////////////////////////////////////////////
138 // construct/copy/destroy
140 //////////////////////////////////////////////
142 //! <b>Effects</b>: Default constructs an empty map.
144 //! <b>Complexity</b>: Constant.
145 BOOST_CONTAINER_FORCEINLINE
146 map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
147 dtl::is_nothrow_default_constructible<Compare>::value)
151 //! <b>Effects</b>: Constructs an empty map using the specified comparison object
154 //! <b>Complexity</b>: Constant.
155 BOOST_CONTAINER_FORCEINLINE map(const Compare& comp, const allocator_type& a)
159 //! <b>Effects</b>: Constructs an empty map using the specified comparison object.
161 //! <b>Complexity</b>: Constant.
162 BOOST_CONTAINER_FORCEINLINE explicit map(const Compare& comp)
166 //! <b>Effects</b>: Constructs an empty map using the specified allocator.
168 //! <b>Complexity</b>: Constant.
169 BOOST_CONTAINER_FORCEINLINE explicit map(const allocator_type& a)
173 //! <b>Effects</b>: Constructs an empty map and
174 //! inserts elements from the range [first ,last ).
176 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
177 //! the predicate and otherwise N logN, where N is last - first.
178 template <class InputIterator>
179 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last)
180 : base_t(true, first, last)
183 //! <b>Effects</b>: Constructs an empty map using the specified
184 //! allocator, and inserts elements from the range [first ,last ).
186 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
187 //! the predicate and otherwise N logN, where N is last - first.
188 template <class InputIterator>
189 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const allocator_type& a)
190 : base_t(true, first, last, Compare(), a)
193 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
194 //! inserts elements from the range [first ,last ).
196 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
197 //! the predicate and otherwise N logN, where N is last - first.
198 template <class InputIterator>
199 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const Compare& comp)
200 : base_t(true, first, last, comp)
203 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
204 //! allocator, and inserts elements from the range [first ,last ).
206 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
207 //! the predicate and otherwise N logN, where N is last - first.
208 template <class InputIterator>
209 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
210 : base_t(true, first, last, comp, a)
213 //! <b>Effects</b>: Constructs an empty map and
214 //! inserts elements from the ordered unique range [first ,last). This function
215 //! is more efficient than the normal range creation for ordered ranges.
217 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
220 //! <b>Complexity</b>: Linear in N.
222 //! <b>Note</b>: Non-standard extension.
223 template <class InputIterator>
224 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last)
225 : base_t(ordered_range, first, last)
228 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
229 //! inserts elements from the ordered unique range [first ,last). This function
230 //! is more efficient than the normal range creation for ordered ranges.
232 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
235 //! <b>Complexity</b>: Linear in N.
237 //! <b>Note</b>: Non-standard extension.
238 template <class InputIterator>
239 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
240 : base_t(ordered_range, first, last, comp)
243 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
244 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
245 //! is more efficient than the normal range creation for ordered ranges.
247 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
250 //! <b>Complexity</b>: Linear in N.
252 //! <b>Note</b>: Non-standard extension.
253 template <class InputIterator>
254 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last
255 , const Compare& comp, const allocator_type& a)
256 : base_t(ordered_range, first, last, comp, a)
259 //! <b>Effects</b>: Constructs an empty map using the specified allocator object and
260 //! inserts elements from the ordered unique range [first ,last). This function
261 //! is more efficient than the normal range creation for ordered ranges.
263 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
266 //! <b>Complexity</b>: Linear in N.
268 //! <b>Note</b>: Non-standard extension.
269 template <class InputIterator>
270 BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
271 : base_t(ordered_range, first, last, Compare(), a)
275 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
276 //! <b>Effects</b>: Constructs an empty map and
277 //! inserts elements from the range [il.begin(), il.end()).
279 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted according
280 //! to the predicate and otherwise N logN, where N is il.first() - il.end().
281 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il)
282 : base_t(true, il.begin(), il.end())
285 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
286 //! inserts elements from the range [il.begin(), il.end()).
288 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
289 //! the predicate and otherwise N logN, where N is il.first() - il.end().
290 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const Compare& comp)
291 : base_t(true, il.begin(), il.end(), comp)
294 //! <b>Effects</b>: Constructs an empty map using the specified
295 //! allocator, and inserts elements from the range [il.begin(), il.end()).
297 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
298 //! the predicate and otherwise N logN, where N is il.first() - il.end().
299 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const allocator_type& a)
300 : base_t(true, il.begin(), il.end(), Compare(), a)
303 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
304 //! allocator, and inserts elements from the range [il.begin(), il.end()).
306 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
307 //! the predicate and otherwise N logN, where N is il.first() - il.end().
308 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
309 : base_t(true, il.begin(), il.end(), comp, a)
312 //! <b>Effects</b>: Constructs an empty map and inserts elements from the ordered unique range [il.begin(), il.end()).
313 //! This function is more efficient than the normal range creation for ordered ranges.
315 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
318 //! <b>Complexity</b>: Linear in N.
320 //! <b>Note</b>: Non-standard extension.
321 BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, std::initializer_list<value_type> il)
322 : base_t(ordered_range, il.begin(), il.end())
325 //! <b>Effects</b>: Constructs an empty map using the specified comparison object,
326 //! and inserts elements from the ordered unique range [il.begin(), il.end()). This function
327 //! is more efficient than the normal range creation for ordered ranges.
329 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
332 //! <b>Complexity</b>: Linear in N.
334 //! <b>Note</b>: Non-standard extension.
335 BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
336 : base_t(ordered_range, il.begin(), il.end(), comp)
339 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
340 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
341 //! is more efficient than the normal range creation for ordered ranges.
343 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
346 //! <b>Complexity</b>: Linear in N.
348 //! <b>Note</b>: Non-standard extension.
349 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, std::initializer_list<value_type> il
350 , const Compare& comp, const allocator_type& a)
351 : base_t(ordered_range, il.begin(), il.end(), comp, a)
356 //! <b>Effects</b>: Copy constructs a map.
358 //! <b>Complexity</b>: Linear in x.size().
359 BOOST_CONTAINER_FORCEINLINE map(const map& x)
360 : base_t(static_cast<const base_t&>(x))
363 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources.
365 //! <b>Complexity</b>: Constant.
367 //! <b>Postcondition</b>: x is emptied.
368 BOOST_CONTAINER_FORCEINLINE map(BOOST_RV_REF(map) x)
369 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
370 : base_t(BOOST_MOVE_BASE(base_t, x))
373 //! <b>Effects</b>: Copy constructs a map using the specified allocator.
375 //! <b>Complexity</b>: Linear in x.size().
376 BOOST_CONTAINER_FORCEINLINE map(const map& x, const allocator_type &a)
377 : base_t(static_cast<const base_t&>(x), a)
380 //! <b>Effects</b>: Move constructs a map using the specified allocator.
381 //! Constructs *this using x's resources.
383 //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise.
385 //! <b>Postcondition</b>: x is emptied.
386 BOOST_CONTAINER_FORCEINLINE map(BOOST_RV_REF(map) x, const allocator_type &a)
387 : base_t(BOOST_MOVE_BASE(base_t, x), a)
390 //! <b>Effects</b>: Makes *this a copy of x.
392 //! <b>Complexity</b>: Linear in x.size().
393 BOOST_CONTAINER_FORCEINLINE map& operator=(BOOST_COPY_ASSIGN_REF(map) x)
394 { return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
396 //! <b>Effects</b>: this->swap(x.get()).
398 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
399 //! is false and (allocation throws or value_type's move constructor throws)
401 //! <b>Complexity</b>: Constant if allocator_traits_type::
402 //! propagate_on_container_move_assignment is true or
403 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
404 BOOST_CONTAINER_FORCEINLINE map& operator=(BOOST_RV_REF(map) x)
405 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
406 allocator_traits_type::is_always_equal::value) &&
407 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
408 { return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
410 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
411 //! <b>Effects</b>: Assign content of il to *this.
413 BOOST_CONTAINER_FORCEINLINE map& operator=(std::initializer_list<value_type> il)
416 insert(il.begin(), il.end());
421 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
423 //! <b>Effects</b>: Returns a copy of the allocator that
424 //! was passed to the object's constructor.
426 //! <b>Complexity</b>: Constant.
427 allocator_type get_allocator() const;
429 //! <b>Effects</b>: Returns a reference to the internal allocator.
431 //! <b>Throws</b>: Nothing
433 //! <b>Complexity</b>: Constant.
435 //! <b>Note</b>: Non-standard extension.
436 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
438 //! <b>Effects</b>: Returns a reference to the internal allocator.
440 //! <b>Throws</b>: Nothing
442 //! <b>Complexity</b>: Constant.
444 //! <b>Note</b>: Non-standard extension.
445 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
447 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
449 //! <b>Throws</b>: Nothing.
451 //! <b>Complexity</b>: Constant.
452 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
454 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
456 //! <b>Throws</b>: Nothing.
458 //! <b>Complexity</b>: Constant.
459 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW;
461 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
463 //! <b>Throws</b>: Nothing.
465 //! <b>Complexity</b>: Constant.
466 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
468 //! <b>Effects</b>: Returns an iterator to the end of the container.
470 //! <b>Throws</b>: Nothing.
472 //! <b>Complexity</b>: Constant.
473 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
475 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
477 //! <b>Throws</b>: Nothing.
479 //! <b>Complexity</b>: Constant.
480 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
482 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
484 //! <b>Throws</b>: Nothing.
486 //! <b>Complexity</b>: Constant.
487 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
489 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
490 //! of the reversed container.
492 //! <b>Throws</b>: Nothing.
494 //! <b>Complexity</b>: Constant.
495 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
497 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
498 //! of the reversed container.
500 //! <b>Throws</b>: Nothing.
502 //! <b>Complexity</b>: Constant.
503 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
505 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
506 //! of the reversed container.
508 //! <b>Throws</b>: Nothing.
510 //! <b>Complexity</b>: Constant.
511 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
513 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
514 //! of the reversed container.
516 //! <b>Throws</b>: Nothing.
518 //! <b>Complexity</b>: Constant.
519 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
521 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
522 //! of the reversed container.
524 //! <b>Throws</b>: Nothing.
526 //! <b>Complexity</b>: Constant.
527 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
529 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
530 //! of the reversed container.
532 //! <b>Throws</b>: Nothing.
534 //! <b>Complexity</b>: Constant.
535 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
537 //! <b>Effects</b>: Returns true if the container contains no elements.
539 //! <b>Throws</b>: Nothing.
541 //! <b>Complexity</b>: Constant.
542 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
544 //! <b>Effects</b>: Returns the number of the elements contained in the container.
546 //! <b>Throws</b>: Nothing.
548 //! <b>Complexity</b>: Constant.
549 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
551 //! <b>Effects</b>: Returns the largest possible size of the container.
553 //! <b>Throws</b>: Nothing.
555 //! <b>Complexity</b>: Constant.
556 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
558 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
560 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
561 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts
562 //! value_type(x, T()) into the map.
564 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this.
566 //! <b>Complexity</b>: Logarithmic.
567 mapped_type& operator[](const key_type &k);
569 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts
570 //! value_type(boost::move(x), T()) into the map (the key is move-constructed)
572 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this.
574 //! <b>Complexity</b>: Logarithmic.
575 mapped_type& operator[](key_type &&k);
576 #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
577 //in compilers like GCC 3.4, we can't catch temporaries
578 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); }
579 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); }
581 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
584 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
585 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
586 //! as if by insert, constructing it from value_type(k, forward<M>(obj)).
588 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
589 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
590 //! references obtained to that element before it was extracted become valid.
592 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
593 //! took place. The iterator component is pointing at the element that was inserted or updated.
595 //! <b>Complexity</b>: Logarithmic in the size of the container.
597 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj)
598 { return this->base_t::insert_or_assign(const_iterator(), k, ::boost::forward<M>(obj)); }
600 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
601 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
602 //! as if by insert, constructing it from value_type(k, move(obj)).
604 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
605 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
606 //! references obtained to that element before it was extracted become valid.
608 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
609 //! took place. The iterator component is pointing at the element that was inserted or updated.
611 //! <b>Complexity</b>: Logarithmic in the size of the container.
613 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
614 { return this->base_t::insert_or_assign(const_iterator(), ::boost::move(k), ::boost::forward<M>(obj)); }
616 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
617 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
618 //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element
619 //! to the container as close as possible to the position just before hint.
621 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
622 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
623 //! references obtained to that element before it was extracted become valid.
625 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
626 //! took place. The iterator component is pointing at the element that was inserted or updated.
628 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if
629 //! the new element is inserted just before hint.
631 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
632 { return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)).first; }
634 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
635 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
636 //! as if by insert, constructing it from value_type(k, move(obj)) and the new element
637 //! to the container as close as possible to the position just before hint.
639 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
640 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
641 //! references obtained to that element before it was extracted become valid.
643 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
644 //! took place. The iterator component is pointing at the element that was inserted or updated.
646 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if
647 //! the new element is inserted just before hint.
649 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
650 { return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)).first; }
652 //! <b>Returns</b>: A reference to the element whose key is equivalent to x.
653 //! Throws: An exception object of type out_of_range if no such element is present.
654 //! <b>Complexity</b>: logarithmic.
655 T& at(const key_type& k)
657 iterator i = this->find(k);
658 if(i == this->end()){
659 throw_out_of_range("map::at key not found");
664 //! <b>Returns</b>: A reference to the element whose key is equivalent to x.
665 //! Throws: An exception object of type out_of_range if no such element is present.
666 //! <b>Complexity</b>: logarithmic.
667 const T& at(const key_type& k) const
669 const_iterator i = this->find(k);
670 if(i == this->end()){
671 throw_out_of_range("map::at key not found");
676 //////////////////////////////////////////////
680 //////////////////////////////////////////////
682 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
683 //! with key equivalent to the key of x.
685 //! <b>Returns</b>: The bool component of the returned pair is true if and only
686 //! if the insertion takes place, and the iterator component of the pair
687 //! points to the element with key equivalent to the key of x.
689 //! <b>Complexity</b>: Logarithmic.
690 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x)
691 { return this->base_t::insert_unique(x); }
693 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if
694 //! there is no element in the container with key equivalent to the key of x.
696 //! <b>Returns</b>: The bool component of the returned pair is true if and only
697 //! if the insertion takes place, and the iterator component of the pair
698 //! points to the element with key equivalent to the key of x.
700 //! <b>Complexity</b>: Logarithmic.
701 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const nonconst_value_type& x)
702 { return this->try_emplace(x.first, x.second); }
704 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
705 //! only if there is no element in the container with key equivalent to the key of x.
707 //! <b>Returns</b>: The bool component of the returned pair is true if and only
708 //! if the insertion takes place, and the iterator component of the pair
709 //! points to the element with key equivalent to the key of x.
711 //! <b>Complexity</b>: Logarithmic.
712 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x)
713 { return this->try_emplace(boost::move(x.first), boost::move(x.second)); }
715 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
716 //! only if there is no element in the container with key equivalent to the key of x.
718 //! <b>Returns</b>: The bool component of the returned pair is true if and only
719 //! if the insertion takes place, and the iterator component of the pair
720 //! points to the element with key equivalent to the key of x.
722 //! <b>Complexity</b>: Logarithmic.
723 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
724 { return this->try_emplace(boost::move(x.first), boost::move(x.second)); }
726 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
727 //! no element in the container with key equivalent to the key of x.
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.
733 //! <b>Complexity</b>: Logarithmic.
734 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
735 { return this->base_t::insert_unique(boost::move(x)); }
737 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
738 //! no element in the container with key equivalent to the key of x.
739 //! p is a hint pointing to where the insert should start to search.
741 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
744 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
745 //! is inserted right before p.
746 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
747 { return this->base_t::insert_unique(p, x); }
749 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
750 //! no element in the container with key equivalent to the key of x.
751 //! p is a hint pointing to where the insert should start to search.
753 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
756 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
757 //! is inserted right before p.
758 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x)
759 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); }
761 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
762 //! no element in the container with key equivalent to the key of x.
763 //! p is a hint pointing to where the insert should start to search.
765 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
768 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
769 //! is inserted right before p.
770 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
771 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); }
773 //! <b>Effects</b>: Inserts a copy of x in the container.
774 //! p is a hint pointing to where the insert should start to search.
776 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
778 //! <b>Complexity</b>: Logarithmic.
779 iterator insert(const_iterator p, const nonconst_value_type& x)
780 { return this->try_emplace(p, x.first, x.second); }
782 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
783 //! p is a hint pointing to where the insert should start to search.
785 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
787 //! <b>Complexity</b>: Logarithmic.
788 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
789 { return this->base_t::insert_unique(p, boost::move(x)); }
791 //! <b>Requires</b>: first, last are not iterators into *this.
793 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
794 //! if there is no element with key equivalent to the key of that element.
796 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
797 template <class InputIterator>
798 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
799 { this->base_t::insert_unique(first, last); }
801 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
802 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
803 //! if there is no element with key equivalent to the key of that element.
805 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
806 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
807 { this->base_t::insert_unique(il.begin(), il.end()); }
810 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator().
812 //! <b>Effects</b>: If nh is empty, has no effect. Otherwise, inserts the element owned
813 //! by nh if and only if there is no element in the container with a key equivalent to nh.key().
815 //! <b>Returns</b>: If nh is empty, insert_return_type.inserted is false, insert_return_type.position
816 //! is end(), and insert_return_type.node is empty. Otherwise if the insertion took place,
817 //! insert_return_type.inserted is true, insert_return_type.position points to the inserted element,
818 //! and insert_return_type.node is empty; if the insertion failed, insert_return_type.inserted is
819 //! false, insert_return_type.node has the previous value of nh, and insert_return_type.position
820 //! points to an element with a key equivalent to nh.key().
822 //! <b>Complexity</b>: Logarithmic
823 insert_return_type insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
825 typename base_t::node_type n(boost::move(nh));
826 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(boost::move(n)));
827 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node));
830 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible
831 //! to the position just prior to "hint".
833 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted
834 //! right before "hint".
835 insert_return_type insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
837 typename base_t::node_type n(boost::move(nh));
838 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(hint, boost::move(n)));
839 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node));
842 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
844 //! <b>Effects</b>: Inserts an object x of type T constructed with
845 //! std::forward<Args>(args)... in the container if and only if there is
846 //! no element in the container with an equivalent key.
847 //! p is a hint pointing to where the insert should start to search.
849 //! <b>Returns</b>: The bool component of the returned pair is true if and only
850 //! if the insertion takes place, and the iterator component of the pair
851 //! points to the element with key equivalent to the key of x.
853 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
854 //! is inserted right before p.
855 template <class... Args>
856 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
857 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
859 //! <b>Effects</b>: Inserts an object of type T constructed with
860 //! std::forward<Args>(args)... in the container if and only if there is
861 //! no element in the container with an equivalent key.
862 //! p is a hint pointing to where the insert should start to search.
864 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
867 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
868 //! is inserted right before p.
869 template <class... Args>
870 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
871 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
873 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
874 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
876 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
877 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
878 //! forward_as_tuple(forward<Args>(args)...).
880 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
881 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
883 //! <b>Complexity</b>: Logarithmic.
884 template <class... Args>
885 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args)
886 { return this->base_t::try_emplace(const_iterator(), k, boost::forward<Args>(args)...); }
888 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
889 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
891 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
892 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
893 //! forward_as_tuple(forward<Args>(args)...).
895 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
897 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
898 //! is inserted right before p.
899 template <class... Args>
900 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args)
901 { return this->base_t::try_emplace(hint, k, boost::forward<Args>(args)...).first; }
903 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
904 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
906 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
907 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
908 //! forward_as_tuple(forward<Args>(args)...).
910 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
911 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
913 //! <b>Complexity</b>: Logarithmic.
914 template <class... Args>
915 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
916 { return this->base_t::try_emplace(const_iterator(), boost::move(k), boost::forward<Args>(args)...); }
918 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
919 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
921 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
922 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
923 //! forward_as_tuple(forward<Args>(args)...).
925 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
927 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
928 //! is inserted right before p.
929 template <class... Args>
930 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
931 { return this->base_t::try_emplace(hint, boost::move(k), boost::forward<Args>(args)...).first; }
933 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
935 #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \
936 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
937 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
938 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\
940 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
941 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
942 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
944 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
945 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
946 { return this->base_t::try_emplace(const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
948 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
949 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
950 { return this->base_t::try_emplace(hint, k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\
952 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
953 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
954 { return this->base_t::try_emplace(const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
956 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
957 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
958 { return this->base_t::try_emplace(hint, boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\
960 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE)
961 #undef BOOST_CONTAINER_MAP_EMPLACE_CODE
963 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
965 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
967 //! <b>Effects</b>: Erases the element pointed to by p.
969 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
970 //! following q prior to the element being erased. If no such element exists,
973 //! <b>Complexity</b>: Amortized constant time
974 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
976 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
978 //! <b>Returns</b>: Returns the number of erased elements.
980 //! <b>Complexity</b>: log(size()) + count(k)
981 size_type erase(const key_type& x) BOOST_NOEXCEPT_OR_NOTHROW;
983 //! <b>Effects</b>: Erases all the elements in the range [first, last).
985 //! <b>Returns</b>: Returns last.
987 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
988 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW;
992 //! <b>Effects</b>: Removes the first element in the container with key equivalent to k.
994 //! <b>Returns</b>: A node_type owning the element if found, otherwise an empty node_type.
996 //! <b>Complexity</b>: log(size()).
997 node_type extract(const key_type& k)
999 typename base_t::node_type base_nh(this->base_t::extract(k));
1000 node_type nh(boost::move(base_nh));
1001 return BOOST_MOVE_RET(node_type, nh);
1004 //! <b>Effects</b>: Removes the element pointed to by "position".
1006 //! <b>Returns</b>: A node_type owning the element, otherwise an empty node_type.
1008 //! <b>Complexity</b>: Amortized constant.
1009 node_type extract(const_iterator position)
1011 typename base_t::node_type base_nh(this->base_t::extract(position));
1012 node_type nh(boost::move(base_nh));
1013 return BOOST_MOVE_RET(node_type, nh);
1016 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1018 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
1019 //! the comparison object of *this. If there is an element in a with key equivalent to the
1020 //! key of an element from source, then that element is not extracted from source.
1022 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1023 //! to those same elements but as members of *this. Iterators referring to the transferred
1024 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
1025 //! not into source.
1027 //! <b>Throws</b>: Nothing unless the comparison object throws.
1029 //! <b>Complexity</b>: N log(size() + N) (N has the value source.size())
1031 BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source)
1034 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1035 this->merge_unique(static_cast<base2_t&>(source));
1038 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1040 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1041 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); }
1043 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1045 BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source)
1048 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1049 this->base_t::merge_unique(static_cast<base2_t&>(source));
1052 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1054 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1055 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); }
1057 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1058 //! <b>Effects</b>: Swaps the contents of *this and x.
1060 //! <b>Throws</b>: Nothing.
1062 //! <b>Complexity</b>: Constant.
1064 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1065 && boost::container::dtl::is_nothrow_swappable<Compare>::value )
1067 //! <b>Effects</b>: erase(begin(),end()).
1069 //! <b>Postcondition</b>: size() == 0.
1071 //! <b>Complexity</b>: linear in size().
1072 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1074 //! <b>Effects</b>: Returns the comparison object out
1075 //! of which a was constructed.
1077 //! <b>Complexity</b>: Constant.
1078 key_compare key_comp() const;
1080 //! <b>Effects</b>: Returns an object of value_compare constructed out
1081 //! of the comparison object.
1083 //! <b>Complexity</b>: Constant.
1084 value_compare value_comp() const;
1086 //! <b>Returns</b>: An iterator pointing to an element with the key
1087 //! equivalent to x, or end() if such an element is not found.
1089 //! <b>Complexity</b>: Logarithmic.
1090 iterator find(const key_type& x);
1092 //! <b>Returns</b>: A const_iterator pointing to an element with the key
1093 //! equivalent to x, or end() if such an element is not found.
1095 //! <b>Complexity</b>: Logarithmic.
1096 const_iterator find(const key_type& x) const;
1098 //! <b>Requires</b>: This overload is available only if
1099 //! key_compare::is_transparent exists.
1101 //! <b>Returns</b>: An iterator pointing to an element with the key
1102 //! equivalent to x, or end() if such an element is not found.
1104 //! <b>Complexity</b>: Logarithmic.
1105 template<typename K>
1106 iterator find(const K& x);
1108 //! <b>Requires</b>: This overload is available only if
1109 //! key_compare::is_transparent exists.
1111 //! <b>Returns</b>: A const_iterator pointing to an element with the key
1112 //! equivalent to x, or end() if such an element is not found.
1114 //! <b>Complexity</b>: Logarithmic.
1115 template<typename K>
1116 const_iterator find(const K& x) const;
1118 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1120 //! <b>Returns</b>: The number of elements with key equivalent to x.
1122 //! <b>Complexity</b>: log(size())+count(k)
1123 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
1124 { return static_cast<size_type>(this->find(x) != this->cend()); }
1126 //! <b>Requires</b>: This overload is available only if
1127 //! key_compare::is_transparent exists.
1129 //! <b>Returns</b>: The number of elements with key equivalent to x.
1131 //! <b>Complexity</b>: log(size())+count(k)
1132 template<typename K>
1133 BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
1134 { return static_cast<size_type>(this->find(x) != this->cend()); }
1136 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1138 //! <b>Returns</b>: Returns true if there is an element with key
1139 //! equivalent to key in the container, otherwise false.
1141 //! <b>Complexity</b>: log(size()).
1142 bool contains(const key_type& x) const;
1144 //! <b>Requires</b>: This overload is available only if
1145 //! key_compare::is_transparent exists.
1147 //! <b>Returns</b>: Returns true if there is an element with key
1148 //! equivalent to key in the container, otherwise false.
1150 //! <b>Complexity</b>: log(size()).
1151 template<typename K>
1152 bool contains(const K& x) const;
1154 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1155 //! than x, or end() if such an element is not found.
1157 //! <b>Complexity</b>: Logarithmic
1158 iterator lower_bound(const key_type& x);
1160 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1161 //! less than x, or end() if such an element is not found.
1163 //! <b>Complexity</b>: Logarithmic
1164 const_iterator lower_bound(const key_type& x) const;
1166 //! <b>Requires</b>: This overload is available only if
1167 //! key_compare::is_transparent exists.
1169 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1170 //! than x, or end() if such an element is not found.
1172 //! <b>Complexity</b>: Logarithmic
1173 template<typename K>
1174 iterator lower_bound(const K& x);
1176 //! <b>Requires</b>: This overload is available only if
1177 //! key_compare::is_transparent exists.
1179 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1180 //! less than x, or end() if such an element is not found.
1182 //! <b>Complexity</b>: Logarithmic
1183 template<typename K>
1184 const_iterator lower_bound(const K& x) const;
1186 //! <b>Returns</b>: An iterator pointing to the first element with key greater
1187 //! than x, or end() if such an element is not found.
1189 //! <b>Complexity</b>: Logarithmic
1190 iterator upper_bound(const key_type& x);
1192 //! <b>Returns</b>: A const iterator pointing to the first element with key
1193 //! greater than x, or end() if such an element is not found.
1195 //! <b>Complexity</b>: Logarithmic
1196 const_iterator upper_bound(const key_type& x) const;
1198 //! <b>Requires</b>: This overload is available only if
1199 //! key_compare::is_transparent exists.
1201 //! <b>Returns</b>: An iterator pointing to the first element with key greater
1202 //! than x, or end() if such an element is not found.
1204 //! <b>Complexity</b>: Logarithmic
1205 template<typename K>
1206 iterator upper_bound(const K& x);
1208 //! <b>Requires</b>: This overload is available only if
1209 //! key_compare::is_transparent exists.
1211 //! <b>Returns</b>: A const iterator pointing to the first element with key
1212 //! greater than x, or end() if such an element is not found.
1214 //! <b>Complexity</b>: Logarithmic
1215 template<typename K>
1216 const_iterator upper_bound(const K& x) const;
1218 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1220 //! <b>Complexity</b>: Logarithmic
1221 std::pair<iterator,iterator> equal_range(const key_type& x);
1223 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1225 //! <b>Complexity</b>: Logarithmic
1226 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
1228 //! <b>Requires</b>: This overload is available only if
1229 //! key_compare::is_transparent exists.
1231 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1233 //! <b>Complexity</b>: Logarithmic
1234 template<typename K>
1235 std::pair<iterator,iterator> equal_range(const K& x);
1237 //! <b>Requires</b>: This overload is available only if
1238 //! key_compare::is_transparent exists.
1240 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1242 //! <b>Complexity</b>: Logarithmic
1243 template<typename K>
1244 std::pair<const_iterator,const_iterator> equal_range(const K& x) const;
1246 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
1248 //! <b>Complexity</b>: Linear
1251 //! <b>Effects</b>: Returns true if x and y are equal
1253 //! <b>Complexity</b>: Linear to the number of elements in the container.
1254 friend bool operator==(const map& x, const map& y);
1256 //! <b>Effects</b>: Returns true if x and y are unequal
1258 //! <b>Complexity</b>: Linear to the number of elements in the container.
1259 friend bool operator!=(const map& x, const map& y);
1261 //! <b>Effects</b>: Returns true if x is less than y
1263 //! <b>Complexity</b>: Linear to the number of elements in the container.
1264 friend bool operator<(const map& x, const map& y);
1266 //! <b>Effects</b>: Returns true if x is greater than y
1268 //! <b>Complexity</b>: Linear to the number of elements in the container.
1269 friend bool operator>(const map& x, const map& y);
1271 //! <b>Effects</b>: Returns true if x is equal or less than y
1273 //! <b>Complexity</b>: Linear to the number of elements in the container.
1274 friend bool operator<=(const map& x, const map& y);
1276 //! <b>Effects</b>: Returns true if x is equal or greater than y
1278 //! <b>Complexity</b>: Linear to the number of elements in the container.
1279 friend bool operator>=(const map& x, const map& y);
1281 //! <b>Effects</b>: x.swap(y)
1283 //! <b>Complexity</b>: Constant.
1284 friend void swap(map& x, map& y);
1286 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1288 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1290 template<class KeyConvertible>
1291 BOOST_CONTAINER_FORCEINLINE mapped_type& priv_subscript(BOOST_FWD_REF(KeyConvertible) k)
1293 return this->try_emplace(boost::forward<KeyConvertible>(k)).first->second;
1295 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1298 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1300 template <typename InputIterator>
1301 map(InputIterator, InputIterator) ->
1302 map< it_based_non_const_first_type_t<InputIterator>
1303 , it_based_second_type_t<InputIterator>>;
1305 template < typename InputIterator, typename AllocatorOrCompare>
1306 map(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1307 map< it_based_non_const_first_type_t<InputIterator>
1308 , it_based_second_type_t<InputIterator>
1309 , typename dtl::if_c< // Compare
1310 dtl::is_allocator<AllocatorOrCompare>::value
1311 , std::less<it_based_non_const_first_type_t<InputIterator>>
1312 , AllocatorOrCompare
1314 , typename dtl::if_c< // Allocator
1315 dtl::is_allocator<AllocatorOrCompare>::value
1316 , AllocatorOrCompare
1317 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1321 template < typename InputIterator, typename Compare, typename Allocator
1322 , typename = dtl::require_nonallocator_t<Compare>
1323 , typename = dtl::require_allocator_t<Allocator>>
1324 map(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1325 map< it_based_non_const_first_type_t<InputIterator>
1326 , it_based_second_type_t<InputIterator>
1330 template <typename InputIterator>
1331 map(ordered_unique_range_t, InputIterator, InputIterator) ->
1332 map< it_based_non_const_first_type_t<InputIterator>
1333 , it_based_second_type_t<InputIterator>>;
1335 template < typename InputIterator, typename AllocatorOrCompare>
1336 map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1337 map< it_based_non_const_first_type_t<InputIterator>
1338 , it_based_second_type_t<InputIterator>
1339 , typename dtl::if_c< // Compare
1340 dtl::is_allocator<AllocatorOrCompare>::value
1341 , std::less<it_based_non_const_first_type_t<InputIterator>>
1342 , AllocatorOrCompare
1344 , typename dtl::if_c< // Allocator
1345 dtl::is_allocator<AllocatorOrCompare>::value
1346 , AllocatorOrCompare
1347 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1351 template < typename InputIterator, typename Compare, typename Allocator
1352 , typename = dtl::require_nonallocator_t<Compare>
1353 , typename = dtl::require_allocator_t<Allocator>>
1354 map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1355 map< it_based_non_const_first_type_t<InputIterator>
1356 , it_based_second_type_t<InputIterator>
1363 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1365 } //namespace container {
1367 //!has_trivial_destructor_after_move<> == true_type
1368 //!specialization for optimizations
1369 template <class Key, class T, class Compare, class Allocator, class Options>
1370 struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator, Options> >
1372 typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree;
1373 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
1376 namespace container {
1378 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1380 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1382 //! A multimap is a kind of associative container that supports equivalent keys
1383 //! (possibly containing multiple copies of the same key value) and provides for
1384 //! fast retrieval of values of another type T based on the keys. The multimap class
1385 //! supports bidirectional iterators.
1387 //! A multimap satisfies all of the requirements of a container and of a reversible
1388 //! container and of an associative container. The <code>value_type</code> stored
1389 //! by this container is the value_type is std::pair<const Key, T>.
1391 //! \tparam Key is the key_type of the map
1392 //! \tparam Value is the <code>mapped_type</code>
1393 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1394 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
1395 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
1396 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
1397 template < class Key, class T, class Compare = std::less<Key>
1398 , class Allocator = new_allocator< std::pair< const Key, T> >, class Options = tree_assoc_defaults>
1400 template <class Key, class T, class Compare, class Allocator, class Options>
1405 < std::pair<const Key, T>
1407 , Compare, Allocator, Options>
1410 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1412 BOOST_COPYABLE_AND_MOVABLE(multimap)
1414 typedef int select_1st_t;
1415 typedef std::pair<const Key, T> value_type_impl;
1417 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t;
1418 typedef dtl::pair <Key, T> movable_value_type_impl;
1419 typedef typename base_t::value_compare value_compare_impl;
1420 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1423 //////////////////////////////////////////////
1427 //////////////////////////////////////////////
1429 typedef Key key_type;
1430 typedef T mapped_type;
1431 typedef typename base_t::allocator_type allocator_type;
1432 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
1433 typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type;
1434 typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer;
1435 typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer;
1436 typedef typename boost::container::allocator_traits<allocator_type>::reference reference;
1437 typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference;
1438 typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type;
1439 typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_type;
1440 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
1441 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
1442 typedef Compare key_compare;
1443 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
1444 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
1445 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
1446 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
1447 typedef std::pair<key_type, mapped_type> nonconst_value_type;
1448 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type;
1449 typedef BOOST_CONTAINER_IMPDEF(node_handle<
1450 typename base_t::stored_allocator_type
1451 BOOST_MOVE_I pair_key_mapped_of_value
1452 <key_type BOOST_MOVE_I mapped_type> >) node_type;
1454 //allocator_type::value_type type must be std::pair<CONST Key, T>
1455 BOOST_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value));
1457 //////////////////////////////////////////////
1459 // construct/copy/destroy
1461 //////////////////////////////////////////////
1463 //! <b>Effects</b>: Default constructs an empty multimap.
1465 //! <b>Complexity</b>: Constant.
1466 BOOST_CONTAINER_FORCEINLINE multimap()
1467 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
1468 dtl::is_nothrow_default_constructible<Compare>::value)
1472 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator
1473 //! object and allocator.
1475 //! <b>Complexity</b>: Constant.
1476 BOOST_CONTAINER_FORCEINLINE explicit multimap(const allocator_type& a)
1480 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison.
1482 //! <b>Complexity</b>: Constant.
1483 BOOST_CONTAINER_FORCEINLINE explicit multimap(const Compare& comp)
1487 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison and allocator.
1489 //! <b>Complexity</b>: Constant.
1490 BOOST_CONTAINER_FORCEINLINE multimap(const Compare& comp, const allocator_type& a)
1494 //! <b>Effects</b>: Constructs an empty multimap and
1495 //! inserts elements from the range [first ,last ).
1497 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1498 //! the predicate and otherwise N logN, where N is last - first.
1499 template <class InputIterator>
1500 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last)
1501 : base_t(false, first, last)
1504 //! <b>Effects</b>: Constructs an empty multimap using the specified
1505 //! allocator, and inserts elements from the range [first ,last ).
1507 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1508 //! the predicate and otherwise N logN, where N is last - first.
1509 template <class InputIterator>
1510 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const allocator_type& a)
1511 : base_t(false, first, last, Compare(), a)
1514 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1515 //! inserts elements from the range [first ,last ).
1517 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1518 //! the predicate and otherwise N logN, where N is last - first.
1519 template <class InputIterator>
1520 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const Compare& comp)
1521 : base_t(false, first, last, comp)
1524 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object
1525 //! and allocator, and inserts elements from the range [first ,last ).
1527 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1528 //! the predicate and otherwise N logN, where N is last - first.
1529 template <class InputIterator>
1530 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last,
1531 const Compare& comp, const allocator_type& a)
1532 : base_t(false, first, last, comp, a)
1535 //! <b>Effects</b>: Constructs an empty multimap and
1536 //! inserts elements from the ordered range [first ,last). This function
1537 //! is more efficient than the normal range creation for ordered ranges.
1539 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1541 //! <b>Complexity</b>: Linear in N.
1543 //! <b>Note</b>: Non-standard extension.
1544 template <class InputIterator>
1545 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last)
1546 : base_t(ordered_range, first, last)
1549 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1550 //! inserts elements from the ordered range [first ,last). This function
1551 //! is more efficient than the normal range creation for ordered ranges.
1553 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1555 //! <b>Complexity</b>: Linear in N.
1557 //! <b>Note</b>: Non-standard extension.
1558 template <class InputIterator>
1559 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1560 : base_t(ordered_range, first, last, comp)
1563 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1564 //! allocator, and inserts elements from the ordered range [first ,last). This function
1565 //! is more efficient than the normal range creation for ordered ranges.
1567 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1569 //! <b>Complexity</b>: Linear in N.
1571 //! <b>Note</b>: Non-standard extension.
1572 template <class InputIterator>
1573 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp,
1574 const allocator_type& a)
1575 : base_t(ordered_range, first, last, comp, a)
1578 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator and
1579 //! inserts elements from the ordered range [first ,last). This function
1580 //! is more efficient than the normal range creation for ordered ranges.
1582 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1584 //! <b>Complexity</b>: Linear in N.
1586 //! <b>Note</b>: Non-standard extension.
1587 template <class InputIterator>
1588 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type& a)
1589 : base_t(ordered_range, first, last, Compare(), a)
1592 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1593 //! <b>Effects</b>: Constructs an empty multimap and
1594 //! and inserts elements from the range [il.begin(), il.end()).
1596 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1597 //! the predicate and otherwise N logN, where N is il.first() - il.end().
1598 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il)
1599 : base_t(false, il.begin(), il.end())
1602 //! <b>Effects</b>: Constructs an empty multimap using the specified
1603 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1605 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1606 //! the predicate and otherwise N logN, where N is il.first() - il.end().
1607 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const allocator_type& a)
1608 : base_t(false, il.begin(), il.end(), Compare(), a)
1611 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1612 //! inserts elements from the range [il.begin(), il.end()).
1614 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1615 //! the predicate and otherwise N logN, where N is il.first() - il.end().
1616 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const Compare& comp)
1617 : base_t(false, il.begin(), il.end(), comp)
1620 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1621 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1623 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1624 //! the predicate and otherwise N logN, where N is il.first() - il.end().
1625 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1626 : base_t(false, il.begin(), il.end(), comp, a)
1630 //! <b>Effects</b>: Constructs an empty map and
1631 //! inserts elements from the ordered range [il.begin(), il.end()). This function
1632 //! is more efficient than the normal range creation for ordered ranges.
1634 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1636 //! <b>Complexity</b>: Linear in N.
1638 //! <b>Note</b>: Non-standard extension.
1639 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il)
1640 : base_t(ordered_range, il.begin(), il.end())
1643 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
1644 //! inserts elements from the ordered range [il.begin(), il.end()). This function
1645 //! is more efficient than the normal range creation for ordered ranges.
1647 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1649 //! <b>Complexity</b>: Linear in N.
1651 //! <b>Note</b>: Non-standard extension.
1652 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1653 : base_t(ordered_range, il.begin(), il.end(), comp)
1656 //! <b>Effects</b>: Constructs an empty map and
1657 //! inserts elements from the ordered range [il.begin(), il.end()). This function
1658 //! is more efficient than the normal range creation for ordered ranges.
1660 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1662 //! <b>Complexity</b>: Linear in N.
1664 //! <b>Note</b>: Non-standard extension.
1665 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1666 : base_t(ordered_range, il.begin(), il.end(), comp, a)
1671 //! <b>Effects</b>: Copy constructs a multimap.
1673 //! <b>Complexity</b>: Linear in x.size().
1674 BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x)
1675 : base_t(static_cast<const base_t&>(x))
1678 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources.
1680 //! <b>Complexity</b>: Constant.
1682 //! <b>Postcondition</b>: x is emptied.
1683 BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x)
1684 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
1685 : base_t(BOOST_MOVE_BASE(base_t, x))
1688 //! <b>Effects</b>: Copy constructs a multimap.
1690 //! <b>Complexity</b>: Linear in x.size().
1691 BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x, const allocator_type &a)
1692 : base_t(static_cast<const base_t&>(x), a)
1695 //! <b>Effects</b>: Move constructs a multimap using the specified allocator.
1696 //! Constructs *this using x's resources.
1697 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
1699 //! <b>Postcondition</b>: x is emptied.
1700 BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x, const allocator_type &a)
1701 : base_t(BOOST_MOVE_BASE(base_t, x), a)
1704 //! <b>Effects</b>: Makes *this a copy of x.
1706 //! <b>Complexity</b>: Linear in x.size().
1707 BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x)
1708 { return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
1710 //! <b>Effects</b>: this->swap(x.get()).
1712 //! <b>Complexity</b>: Constant.
1713 BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_RV_REF(multimap) x)
1714 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1715 allocator_traits_type::is_always_equal::value) &&
1716 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
1717 { return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
1719 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1720 //! <b>Effects</b>: Assign content of il to *this.
1722 BOOST_CONTAINER_FORCEINLINE multimap& operator=(std::initializer_list<value_type> il)
1725 insert(il.begin(), il.end());
1730 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1732 //! @copydoc ::boost::container::set::get_allocator()
1733 allocator_type get_allocator() const;
1735 //! @copydoc ::boost::container::set::get_stored_allocator()
1736 stored_allocator_type &get_stored_allocator();
1738 //! @copydoc ::boost::container::set::get_stored_allocator() const
1739 const stored_allocator_type &get_stored_allocator() const;
1741 //! @copydoc ::boost::container::set::begin()
1744 //! @copydoc ::boost::container::set::begin() const
1745 const_iterator begin() const;
1747 //! @copydoc ::boost::container::set::cbegin() const
1748 const_iterator cbegin() const;
1750 //! @copydoc ::boost::container::set::end()
1751 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
1753 //! @copydoc ::boost::container::set::end() const
1754 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
1756 //! @copydoc ::boost::container::set::cend() const
1757 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
1759 //! @copydoc ::boost::container::set::rbegin()
1760 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
1762 //! @copydoc ::boost::container::set::rbegin() const
1763 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1765 //! @copydoc ::boost::container::set::crbegin() const
1766 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1768 //! @copydoc ::boost::container::set::rend()
1769 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
1771 //! @copydoc ::boost::container::set::rend() const
1772 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
1774 //! @copydoc ::boost::container::set::crend() const
1775 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
1777 //! @copydoc ::boost::container::set::empty() const
1780 //! @copydoc ::boost::container::set::size() const
1781 size_type size() const;
1783 //! @copydoc ::boost::container::set::max_size() const
1784 size_type max_size() const;
1786 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1788 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1790 //! <b>Effects</b>: Inserts an object of type T constructed with
1791 //! std::forward<Args>(args)... in the container.
1792 //! p is a hint pointing to where the insert should start to search.
1794 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1795 //! to the key of x.
1797 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1798 //! is inserted right before p.
1799 template <class... Args>
1800 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args)
1801 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
1803 //! <b>Effects</b>: Inserts an object of type T constructed with
1804 //! std::forward<Args>(args)... in the container.
1805 //! p is a hint pointing to where the insert should start to search.
1807 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1808 //! to the key of x.
1810 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1811 //! is inserted right before p.
1812 template <class... Args>
1813 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1814 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1816 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1818 #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \
1819 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1820 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
1821 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\
1823 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1824 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1825 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
1827 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE)
1828 #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE
1830 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1832 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1833 //! newly inserted element.
1835 //! <b>Complexity</b>: Logarithmic.
1836 BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x)
1837 { return this->base_t::insert_equal(x); }
1839 //! <b>Effects</b>: Inserts a new value constructed from x and returns
1840 //! the iterator pointing to the newly inserted element.
1842 //! <b>Complexity</b>: Logarithmic.
1843 BOOST_CONTAINER_FORCEINLINE iterator insert(const nonconst_value_type& x)
1844 { return this->base_t::emplace_equal(x); }
1846 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1847 //! the iterator pointing to the newly inserted element.
1849 //! <b>Complexity</b>: Logarithmic.
1850 BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(nonconst_value_type) x)
1851 { return this->base_t::emplace_equal(boost::move(x)); }
1853 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1854 //! the iterator pointing to the newly inserted element.
1856 //! <b>Complexity</b>: Logarithmic.
1857 iterator insert(BOOST_RV_REF(movable_value_type) x)
1858 { return this->base_t::emplace_equal(boost::move(x)); }
1860 //! <b>Effects</b>: Inserts a copy of x in the container.
1861 //! p is a hint pointing to where the insert should start to search.
1863 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1864 //! to the key of x.
1866 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1867 //! is inserted right before p.
1868 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
1869 { return this->base_t::insert_equal(p, x); }
1871 //! <b>Effects</b>: Inserts a new value constructed from x in the container.
1872 //! p is a hint pointing to where the insert should start to search.
1874 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1875 //! to the key of x.
1877 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1878 //! is inserted right before p.
1879 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const nonconst_value_type& x)
1880 { return this->base_t::emplace_hint_equal(p, x); }
1882 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1883 //! p is a hint pointing to where the insert should start to search.
1885 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1886 //! to the key of x.
1888 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1889 //! is inserted right before p.
1890 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x)
1891 { return this->base_t::emplace_hint_equal(p, boost::move(x)); }
1893 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1894 //! p is a hint pointing to where the insert should start to search.
1896 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1897 //! to the key of x.
1899 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1900 //! is inserted right before p.
1901 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
1902 { return this->base_t::emplace_hint_equal(p, boost::move(x)); }
1904 //! <b>Requires</b>: first, last are not iterators into *this.
1906 //! <b>Effects</b>: inserts each element from the range [first,last) .
1908 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1909 template <class InputIterator>
1910 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1911 { this->base_t::insert_equal(first, last); }
1913 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1914 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end().
1916 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
1917 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1918 { this->base_t::insert_equal(il.begin(), il.end()); }
1921 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator().
1923 //! <b>Effects/Returns</b>: If nh is empty, has no effect and returns end(). Otherwise, inserts
1924 //! the element owned by nh and returns an iterator pointing to the newly inserted element.
1925 //! If a range containing elements with keys equivalent to nh.key() exists,
1926 //! the element is inserted at the end of that range. nh is always emptied.
1928 //! <b>Complexity</b>: Logarithmic
1929 iterator insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1931 typename base_t::node_type n(boost::move(nh));
1932 return this->base_t::insert_equal_node(boost::move(n));
1935 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible
1936 //! to the position just prior to "hint".
1938 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted
1939 //! right before "hint".
1940 iterator insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1942 typename base_t::node_type n(boost::move(nh));
1943 return this->base_t::insert_equal_node(hint, boost::move(n));
1946 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1948 //! @copydoc ::boost::container::set::erase(const_iterator)
1949 iterator erase(const_iterator p);
1951 //! @copydoc ::boost::container::set::erase(const key_type&)
1952 size_type erase(const key_type& x);
1954 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator)
1955 iterator erase(const_iterator first, const_iterator last);
1958 //! @copydoc ::boost::container::map::extract(const key_type&)
1959 node_type extract(const key_type& k)
1961 typename base_t::node_type base_nh(this->base_t::extract(k));
1962 return node_type(boost::move(base_nh));
1965 //! @copydoc ::boost::container::map::extract(const_iterator)
1966 node_type extract(const_iterator position)
1968 typename base_t::node_type base_nh(this->base_t::extract(position));
1969 return node_type (boost::move(base_nh));
1972 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1974 //! <b>Effects</b>: Extracts each element in source and insert it into a using
1975 //! the comparison object of *this.
1977 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1978 //! to those same elements but as members of *this. Iterators referring to the transferred
1979 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
1980 //! not into source.
1982 //! <b>Throws</b>: Nothing unless the comparison object throws.
1984 //! <b>Complexity</b>: N log(size() + N) (N has the value source.size())
1986 BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source)
1989 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1990 this->base_t::merge_equal(static_cast<base2_t&>(source));
1993 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
1995 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1996 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); }
1998 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
2000 BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source)
2003 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
2004 this->base_t::merge_equal(static_cast<base2_t&>(source));
2007 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
2009 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
2010 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); }
2012 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2013 //! @copydoc ::boost::container::set::swap
2014 void swap(multiset& x)
2015 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
2016 && boost::container::dtl::is_nothrow_swappable<Compare>::value );
2018 //! @copydoc ::boost::container::set::clear
2019 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
2021 //! @copydoc ::boost::container::set::key_comp
2022 key_compare key_comp() const;
2024 //! @copydoc ::boost::container::set::value_comp
2025 value_compare value_comp() const;
2027 //! <b>Returns</b>: An iterator pointing to an element with the key
2028 //! equivalent to x, or end() if such an element is not found.
2030 //! <b>Complexity</b>: Logarithmic.
2031 iterator find(const key_type& x);
2033 //! <b>Returns</b>: A const iterator pointing to an element with the key
2034 //! equivalent to x, or end() if such an element is not found.
2036 //! <b>Complexity</b>: Logarithmic.
2037 const_iterator find(const key_type& x) const;
2039 //! <b>Requires</b>: This overload is available only if
2040 //! key_compare::is_transparent exists.
2042 //! <b>Returns</b>: An iterator pointing to an element with the key
2043 //! equivalent to x, or end() if such an element is not found.
2045 //! <b>Complexity</b>: Logarithmic.
2046 template<typename K>
2047 iterator find(const K& x);
2049 //! <b>Requires</b>: This overload is available only if
2050 //! key_compare::is_transparent exists.
2052 //! <b>Returns</b>: A const_iterator pointing to an element with the key
2053 //! equivalent to x, or end() if such an element is not found.
2055 //! <b>Complexity</b>: Logarithmic.
2056 template<typename K>
2057 const_iterator find(const K& x) const;
2059 //! <b>Returns</b>: The number of elements with key equivalent to x.
2061 //! <b>Complexity</b>: log(size())+count(k)
2062 size_type count(const key_type& x) const;
2064 //! <b>Requires</b>: This overload is available only if
2065 //! key_compare::is_transparent exists.
2067 //! <b>Returns</b>: The number of elements with key equivalent to x.
2069 //! <b>Complexity</b>: log(size())+count(k)
2070 template<typename K>
2071 size_type count(const K& x) const;
2073 //! <b>Returns</b>: Returns true if there is an element with key
2074 //! equivalent to key in the container, otherwise false.
2076 //! <b>Complexity</b>: log(size()).
2077 bool contains(const key_type& x) const;
2079 //! <b>Requires</b>: This overload is available only if
2080 //! key_compare::is_transparent exists.
2082 //! <b>Returns</b>: Returns true if there is an element with key
2083 //! equivalent to key in the container, otherwise false.
2085 //! <b>Complexity</b>: log(size()).
2086 template<typename K>
2087 bool contains(const K& x) const;
2089 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2090 //! than x, or end() if such an element is not found.
2092 //! <b>Complexity</b>: Logarithmic
2093 iterator lower_bound(const key_type& x);
2095 //! <b>Returns</b>: A const iterator pointing to the first element with key not
2096 //! less than x, or end() if such an element is not found.
2098 //! <b>Complexity</b>: Logarithmic
2099 const_iterator lower_bound(const key_type& x) const;
2101 //! <b>Requires</b>: This overload is available only if
2102 //! key_compare::is_transparent exists.
2104 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2105 //! than x, or end() if such an element is not found.
2107 //! <b>Complexity</b>: Logarithmic
2108 template<typename K>
2109 iterator lower_bound(const K& x);
2111 //! <b>Requires</b>: This overload is available only if
2112 //! key_compare::is_transparent exists.
2114 //! <b>Returns</b>: A const iterator pointing to the first element with key not
2115 //! less than x, or end() if such an element is not found.
2117 //! <b>Complexity</b>: Logarithmic
2118 template<typename K>
2119 const_iterator lower_bound(const K& x) const;
2121 //! <b>Returns</b>: An iterator pointing to the first element with key greater
2122 //! than x, or end() if such an element is not found.
2124 //! <b>Complexity</b>: Logarithmic
2125 iterator upper_bound(const key_type& x);
2127 //! <b>Returns</b>: A const iterator pointing to the first element with key
2128 //! greater than x, or end() if such an element is not found.
2130 //! <b>Complexity</b>: Logarithmic
2131 const_iterator upper_bound(const key_type& x) const;
2133 //! <b>Requires</b>: This overload is available only if
2134 //! key_compare::is_transparent exists.
2136 //! <b>Returns</b>: An iterator pointing to the first element with key greater
2137 //! than x, or end() if such an element is not found.
2139 //! <b>Complexity</b>: Logarithmic
2140 template<typename K>
2141 iterator upper_bound(const K& x);
2143 //! <b>Requires</b>: This overload is available only if
2144 //! key_compare::is_transparent exists.
2146 //! <b>Returns</b>: A const iterator pointing to the first element with key
2147 //! greater than x, or end() if such an element is not found.
2149 //! <b>Complexity</b>: Logarithmic
2150 template<typename K>
2151 const_iterator upper_bound(const K& x) const;
2153 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2155 //! <b>Complexity</b>: Logarithmic
2156 std::pair<iterator,iterator> equal_range(const key_type& x);
2158 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2160 //! <b>Complexity</b>: Logarithmic
2161 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
2163 //! <b>Requires</b>: This overload is available only if
2164 //! key_compare::is_transparent exists.
2166 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2168 //! <b>Complexity</b>: Logarithmic
2169 template<typename K>
2170 std::pair<iterator,iterator> equal_range(const K& x);
2172 //! <b>Requires</b>: This overload is available only if
2173 //! key_compare::is_transparent exists.
2175 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2177 //! <b>Complexity</b>: Logarithmic
2178 template<typename K>
2179 std::pair<const_iterator,const_iterator> equal_range(const K& x) const;
2181 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
2183 //! <b>Complexity</b>: Linear
2186 //! <b>Effects</b>: Returns true if x and y are equal
2188 //! <b>Complexity</b>: Linear to the number of elements in the container.
2189 friend bool operator==(const multimap& x, const multimap& y);
2191 //! <b>Effects</b>: Returns true if x and y are unequal
2193 //! <b>Complexity</b>: Linear to the number of elements in the container.
2194 friend bool operator!=(const multimap& x, const multimap& y);
2196 //! <b>Effects</b>: Returns true if x is less than y
2198 //! <b>Complexity</b>: Linear to the number of elements in the container.
2199 friend bool operator<(const multimap& x, const multimap& y);
2201 //! <b>Effects</b>: Returns true if x is greater than y
2203 //! <b>Complexity</b>: Linear to the number of elements in the container.
2204 friend bool operator>(const multimap& x, const multimap& y);
2206 //! <b>Effects</b>: Returns true if x is equal or less than y
2208 //! <b>Complexity</b>: Linear to the number of elements in the container.
2209 friend bool operator<=(const multimap& x, const multimap& y);
2211 //! <b>Effects</b>: Returns true if x is equal or greater than y
2213 //! <b>Complexity</b>: Linear to the number of elements in the container.
2214 friend bool operator>=(const multimap& x, const multimap& y);
2216 //! <b>Effects</b>: x.swap(y)
2218 //! <b>Complexity</b>: Constant.
2219 friend void swap(multimap& x, multimap& y);
2221 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2224 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2226 template <typename InputIterator>
2227 multimap(InputIterator, InputIterator) ->
2228 multimap< it_based_non_const_first_type_t<InputIterator>
2229 , it_based_second_type_t<InputIterator>>;
2231 template < typename InputIterator, typename AllocatorOrCompare>
2232 multimap(InputIterator, InputIterator, AllocatorOrCompare const&) ->
2233 multimap< it_based_non_const_first_type_t<InputIterator>
2234 , it_based_second_type_t<InputIterator>
2235 , typename dtl::if_c< // Compare
2236 dtl::is_allocator<AllocatorOrCompare>::value
2237 , std::less<it_based_non_const_first_type_t<InputIterator>>
2238 , AllocatorOrCompare
2240 , typename dtl::if_c< // Allocator
2241 dtl::is_allocator<AllocatorOrCompare>::value
2242 , AllocatorOrCompare
2243 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2247 template < typename InputIterator, typename Compare, typename Allocator
2248 , typename = dtl::require_nonallocator_t<Compare>
2249 , typename = dtl::require_allocator_t<Allocator>>
2250 multimap(InputIterator, InputIterator, Compare const&, Allocator const&) ->
2251 multimap< it_based_non_const_first_type_t<InputIterator>
2252 , it_based_second_type_t<InputIterator>
2256 template <typename InputIterator>
2257 multimap(ordered_range_t, InputIterator, InputIterator) ->
2258 multimap< it_based_non_const_first_type_t<InputIterator>
2259 , it_based_second_type_t<InputIterator>>;
2261 template < typename InputIterator, typename AllocatorOrCompare>
2262 multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
2263 multimap< it_based_non_const_first_type_t<InputIterator>
2264 , it_based_second_type_t<InputIterator>
2265 , typename dtl::if_c< // Compare
2266 dtl::is_allocator<AllocatorOrCompare>::value
2267 , std::less<it_based_const_first_type_t<InputIterator>>
2268 , AllocatorOrCompare
2270 , typename dtl::if_c< // Allocator
2271 dtl::is_allocator<AllocatorOrCompare>::value
2272 , AllocatorOrCompare
2273 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2277 template < typename InputIterator, typename Compare, typename Allocator
2278 , typename = dtl::require_nonallocator_t<Compare>
2279 , typename = dtl::require_allocator_t<Allocator>>
2280 multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
2281 multimap< it_based_non_const_first_type_t<InputIterator>
2282 , it_based_second_type_t<InputIterator>
2287 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2289 } //namespace container {
2291 //!has_trivial_destructor_after_move<> == true_type
2292 //!specialization for optimizations
2293 template <class Key, class T, class Compare, class Allocator, class Options>
2294 struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator, Options> >
2296 typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree;
2297 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
2300 namespace container {
2302 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2306 #include <boost/container/detail/config_end.hpp>
2308 #endif // BOOST_CONTAINER_MAP_HPP