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>
35 #include <boost/move/traits.hpp>
36 #include <boost/move/utility_core.hpp>
38 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
39 #include <boost/move/detail/fwd_macros.hpp>
41 #include <boost/move/detail/move_helpers.hpp>
43 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
44 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
46 #include <boost/static_assert.hpp>
47 #include <boost/core/no_exceptions_support.hpp>
49 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
50 #include <initializer_list>
58 template<class Key, class Mapped>
59 struct pair_key_mapped_of_value
62 typedef Mapped mapped_type;
65 const key_type & key_of_value(const Pair &p) const
69 const mapped_type & mapped_of_value(const Pair &p) const
73 key_type & key_of_value(Pair &p) const
74 { return const_cast<key_type&>(p.first); }
77 mapped_type & mapped_of_value(Pair &p) const
84 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
86 //! A map is a kind of associative container that supports unique keys (contains at
87 //! most one of each key value) and provides for fast retrieval of values of another
88 //! type T based on the keys. The map class supports bidirectional iterators.
90 //! A map satisfies all of the requirements of a container and of a reversible
91 //! container and of an associative container. The <code>value_type</code> stored
92 //! by this container is the value_type is std::pair<const Key, T>.
94 //! \tparam Key is the key_type of the map
95 //! \tparam T is the <code>mapped_type</code>
96 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
97 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
98 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
99 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
100 template < class Key, class T, class Compare = std::less<Key>
101 , class Allocator = new_allocator< std::pair< const Key, T> >, class Options = tree_assoc_defaults >
103 template <class Key, class T, class Compare, class Allocator, class Options>
107 : public container_detail::tree
108 < std::pair<const Key, T>
109 , container_detail::select1st<Key>
110 , Compare, Allocator, Options>
113 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
115 BOOST_COPYABLE_AND_MOVABLE(map)
117 typedef container_detail::select1st<Key> select_1st_t;
118 typedef std::pair<const Key, T> value_type_impl;
119 typedef container_detail::tree
120 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t;
121 typedef container_detail::pair <Key, T> movable_value_type_impl;
122 typedef typename base_t::value_compare value_compare_impl;
123 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
126 //////////////////////////////////////////////
130 //////////////////////////////////////////////
132 typedef Key key_type;
133 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
134 typedef T mapped_type;
135 typedef std::pair<const Key, T> value_type;
136 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
137 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
138 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
139 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
140 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
141 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
142 typedef Allocator allocator_type;
143 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
144 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
145 typedef Compare key_compare;
146 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
147 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
148 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
149 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
150 typedef std::pair<key_type, mapped_type> nonconst_value_type;
151 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type;
152 typedef BOOST_CONTAINER_IMPDEF(node_handle<
153 typename base_t::node_type::container_node_type
154 BOOST_MOVE_I value_type
155 BOOST_MOVE_I allocator_type
156 BOOST_MOVE_I pair_key_mapped_of_value
157 <key_type BOOST_MOVE_I mapped_type> >) node_type;
158 typedef BOOST_CONTAINER_IMPDEF
159 (insert_return_type_base<iterator BOOST_MOVE_I node_type>) insert_return_type;
161 //////////////////////////////////////////////
163 // construct/copy/destroy
165 //////////////////////////////////////////////
167 //! <b>Effects</b>: Default constructs an empty map.
169 //! <b>Complexity</b>: Constant.
170 BOOST_CONTAINER_FORCEINLINE
171 map() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value &&
172 container_detail::is_nothrow_default_constructible<Compare>::value)
175 //A type must be std::pair<CONST Key, T>
176 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
179 //! <b>Effects</b>: Constructs an empty map using the specified comparison object
182 //! <b>Complexity</b>: Constant.
183 BOOST_CONTAINER_FORCEINLINE
184 explicit map(const Compare& comp, const allocator_type& a = allocator_type())
187 //A type must be std::pair<CONST Key, T>
188 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
191 //! <b>Effects</b>: Constructs an empty map using the specified allocator.
193 //! <b>Complexity</b>: Constant.
194 BOOST_CONTAINER_FORCEINLINE
195 explicit map(const allocator_type& a)
198 //A type must be std::pair<CONST Key, T>
199 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
202 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
203 //! allocator, and inserts elements from the range [first ,last ).
205 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
206 //! comp and otherwise N logN, where N is last - first.
207 template <class InputIterator>
208 BOOST_CONTAINER_FORCEINLINE
209 map(InputIterator first, InputIterator last, const Compare& comp = Compare(),
210 const allocator_type& a = allocator_type())
211 : base_t(true, first, last, comp, a)
213 //A type must be std::pair<CONST Key, T>
214 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
217 //! <b>Effects</b>: Constructs an empty map using the specified
218 //! allocator, and inserts elements from the range [first ,last ).
220 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
221 //! comp and otherwise N logN, where N is last - first.
222 template <class InputIterator>
223 BOOST_CONTAINER_FORCEINLINE
224 map(InputIterator first, InputIterator last, const allocator_type& a)
225 : base_t(true, first, last, Compare(), a)
227 //A type must be std::pair<CONST Key, T>
228 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
231 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
232 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
233 //! is more efficient than the normal range creation for ordered ranges.
235 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
238 //! <b>Complexity</b>: Linear in N.
240 //! <b>Note</b>: Non-standard extension.
241 template <class InputIterator>
242 BOOST_CONTAINER_FORCEINLINE
243 map( ordered_unique_range_t, InputIterator first, InputIterator last
244 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
245 : base_t(ordered_range, first, last, comp, a)
247 //A type must be std::pair<CONST Key, T>
248 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
251 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
252 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
253 //! allocator, and inserts elements from the range [il.begin(), il.end()).
255 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
256 //! comp and otherwise N logN, where N is il.first() - il.end().
257 BOOST_CONTAINER_FORCEINLINE
258 map(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
259 : base_t(true, il.begin(), il.end(), comp, a)
261 //A type must be std::pair<CONST Key, T>
262 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
265 //! <b>Effects</b>: Constructs an empty map using the specified
266 //! allocator, and inserts elements from the range [il.begin(), il.end()).
268 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
269 //! comp and otherwise N logN, where N is il.first() - il.end().
270 BOOST_CONTAINER_FORCEINLINE
271 map(std::initializer_list<value_type> il, const allocator_type& a)
272 : base_t(true, il.begin(), il.end(), Compare(), a)
274 //A type must be std::pair<CONST Key, T>
275 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
278 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
279 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
280 //! is more efficient than the normal range creation for ordered ranges.
282 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
285 //! <b>Complexity</b>: Linear in N.
287 //! <b>Note</b>: Non-standard extension.
288 BOOST_CONTAINER_FORCEINLINE
289 map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(),
290 const allocator_type& a = allocator_type())
291 : base_t(ordered_range, il.begin(), il.end(), comp, a)
293 //A type must be std::pair<CONST Key, T>
294 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
298 //! <b>Effects</b>: Copy constructs a map.
300 //! <b>Complexity</b>: Linear in x.size().
301 BOOST_CONTAINER_FORCEINLINE
303 : base_t(static_cast<const base_t&>(x))
305 //A type must be std::pair<CONST Key, T>
306 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
309 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources.
311 //! <b>Complexity</b>: Constant.
313 //! <b>Postcondition</b>: x is emptied.
314 BOOST_CONTAINER_FORCEINLINE
315 map(BOOST_RV_REF(map) x)
316 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
317 : base_t(BOOST_MOVE_BASE(base_t, x))
319 //A type must be std::pair<CONST Key, T>
320 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
323 //! <b>Effects</b>: Copy constructs a map using the specified allocator.
325 //! <b>Complexity</b>: Linear in x.size().
326 BOOST_CONTAINER_FORCEINLINE
327 map(const map& x, const allocator_type &a)
328 : base_t(static_cast<const base_t&>(x), a)
330 //A type must be std::pair<CONST Key, T>
331 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
334 //! <b>Effects</b>: Move constructs a map using the specified allocator.
335 //! Constructs *this using x's resources.
337 //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise.
339 //! <b>Postcondition</b>: x is emptied.
340 BOOST_CONTAINER_FORCEINLINE
341 map(BOOST_RV_REF(map) x, const allocator_type &a)
342 : base_t(BOOST_MOVE_BASE(base_t, x), a)
344 //A type must be std::pair<CONST Key, T>
345 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
348 //! <b>Effects</b>: Makes *this a copy of x.
350 //! <b>Complexity</b>: Linear in x.size().
351 BOOST_CONTAINER_FORCEINLINE
352 map& operator=(BOOST_COPY_ASSIGN_REF(map) x)
353 { return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
355 //! <b>Effects</b>: this->swap(x.get()).
357 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
358 //! is false and (allocation throws or value_type's move constructor throws)
360 //! <b>Complexity</b>: Constant if allocator_traits_type::
361 //! propagate_on_container_move_assignment is true or
362 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
363 BOOST_CONTAINER_FORCEINLINE
364 map& operator=(BOOST_RV_REF(map) x)
365 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
366 allocator_traits_type::is_always_equal::value) &&
367 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
368 { return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
370 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
371 //! <b>Effects</b>: Assign content of il to *this.
373 BOOST_CONTAINER_FORCEINLINE
374 map& operator=(std::initializer_list<value_type> il)
377 insert(il.begin(), il.end());
382 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
384 //! <b>Effects</b>: Returns a copy of the allocator that
385 //! was passed to the object's constructor.
387 //! <b>Complexity</b>: Constant.
388 allocator_type get_allocator() const;
390 //! <b>Effects</b>: Returns a reference to the internal allocator.
392 //! <b>Throws</b>: Nothing
394 //! <b>Complexity</b>: Constant.
396 //! <b>Note</b>: Non-standard extension.
397 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
399 //! <b>Effects</b>: Returns a reference to the internal allocator.
401 //! <b>Throws</b>: Nothing
403 //! <b>Complexity</b>: Constant.
405 //! <b>Note</b>: Non-standard extension.
406 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
408 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
410 //! <b>Throws</b>: Nothing.
412 //! <b>Complexity</b>: Constant.
413 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
415 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
417 //! <b>Throws</b>: Nothing.
419 //! <b>Complexity</b>: Constant.
420 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW;
422 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
424 //! <b>Throws</b>: Nothing.
426 //! <b>Complexity</b>: Constant.
427 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
429 //! <b>Effects</b>: Returns an iterator to the end of the container.
431 //! <b>Throws</b>: Nothing.
433 //! <b>Complexity</b>: Constant.
434 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
436 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
438 //! <b>Throws</b>: Nothing.
440 //! <b>Complexity</b>: Constant.
441 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
443 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
445 //! <b>Throws</b>: Nothing.
447 //! <b>Complexity</b>: Constant.
448 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
450 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
451 //! of the reversed container.
453 //! <b>Throws</b>: Nothing.
455 //! <b>Complexity</b>: Constant.
456 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
458 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
459 //! of the reversed container.
461 //! <b>Throws</b>: Nothing.
463 //! <b>Complexity</b>: Constant.
464 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
466 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
467 //! of the reversed container.
469 //! <b>Throws</b>: Nothing.
471 //! <b>Complexity</b>: Constant.
472 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
474 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
475 //! of the reversed container.
477 //! <b>Throws</b>: Nothing.
479 //! <b>Complexity</b>: Constant.
480 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
482 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
483 //! of the reversed container.
485 //! <b>Throws</b>: Nothing.
487 //! <b>Complexity</b>: Constant.
488 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
490 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
491 //! of the reversed container.
493 //! <b>Throws</b>: Nothing.
495 //! <b>Complexity</b>: Constant.
496 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
498 //! <b>Effects</b>: Returns true if the container contains no elements.
500 //! <b>Throws</b>: Nothing.
502 //! <b>Complexity</b>: Constant.
503 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
505 //! <b>Effects</b>: Returns the number of the elements contained in the container.
507 //! <b>Throws</b>: Nothing.
509 //! <b>Complexity</b>: Constant.
510 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
512 //! <b>Effects</b>: Returns the largest possible size of the container.
514 //! <b>Throws</b>: Nothing.
516 //! <b>Complexity</b>: Constant.
517 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
519 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
521 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
522 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts
523 //! value_type(x, T()) into the map.
525 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this.
527 //! <b>Complexity</b>: Logarithmic.
528 mapped_type& operator[](const key_type &k);
530 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts
531 //! value_type(boost::move(x), T()) into the map (the key is move-constructed)
533 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this.
535 //! <b>Complexity</b>: Logarithmic.
536 mapped_type& operator[](key_type &&k);
537 #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
538 //in compilers like GCC 3.4, we can't catch temporaries
539 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); }
540 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); }
542 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
545 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
546 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
547 //! as if by insert, constructing it from value_type(k, forward<M>(obj)).
549 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
550 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
551 //! references obtained to that element before it was extracted become valid.
553 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
554 //! took place. The iterator component is pointing at the element that was inserted or updated.
556 //! <b>Complexity</b>: Logarithmic in the size of the container.
558 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj)
559 { return this->base_t::insert_or_assign(const_iterator(), k, ::boost::forward<M>(obj)); }
561 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
562 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
563 //! as if by insert, constructing it from value_type(k, move(obj)).
565 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
566 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
567 //! references obtained to that element before it was extracted become valid.
569 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
570 //! took place. The iterator component is pointing at the element that was inserted or updated.
572 //! <b>Complexity</b>: Logarithmic in the size of the container.
574 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
575 { return this->base_t::insert_or_assign(const_iterator(), ::boost::move(k), ::boost::forward<M>(obj)); }
577 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
578 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
579 //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element
580 //! to the container as close as possible to the position just before hint.
582 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
583 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
584 //! references obtained to that element before it was extracted become valid.
586 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
587 //! took place. The iterator component is pointing at the element that was inserted or updated.
589 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if
590 //! the new element is inserted just before hint.
592 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
593 { return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)); }
595 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
596 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
597 //! as if by insert, constructing it from value_type(k, move(obj)) and the new element
598 //! to the container as close as possible to the position just before hint.
600 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
601 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
602 //! references obtained to that element before it was extracted become valid.
604 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
605 //! took place. The iterator component is pointing at the element that was inserted or updated.
607 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if
608 //! the new element is inserted just before hint.
610 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
611 { return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)); }
613 //! <b>Returns</b>: A reference to the element whose key is equivalent to x.
614 //! Throws: An exception object of type out_of_range if no such element is present.
615 //! <b>Complexity</b>: logarithmic.
616 T& at(const key_type& k)
618 iterator i = this->find(k);
619 if(i == this->end()){
620 throw_out_of_range("map::at key not found");
625 //! <b>Returns</b>: A reference to the element whose key is equivalent to x.
626 //! Throws: An exception object of type out_of_range if no such element is present.
627 //! <b>Complexity</b>: logarithmic.
628 const T& at(const key_type& k) const
630 const_iterator i = this->find(k);
631 if(i == this->end()){
632 throw_out_of_range("map::at key not found");
637 //////////////////////////////////////////////
641 //////////////////////////////////////////////
643 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
644 //! with key equivalent to the key of x.
646 //! <b>Returns</b>: The bool component of the returned pair is true if and only
647 //! if the insertion takes place, and the iterator component of the pair
648 //! points to the element with key equivalent to the key of x.
650 //! <b>Complexity</b>: Logarithmic.
651 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x)
652 { return this->base_t::insert_unique(x); }
654 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if
655 //! there is no element in the container with key equivalent to the key of x.
657 //! <b>Returns</b>: The bool component of the returned pair is true if and only
658 //! if the insertion takes place, and the iterator component of the pair
659 //! points to the element with key equivalent to the key of x.
661 //! <b>Complexity</b>: Logarithmic.
662 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const nonconst_value_type& x)
663 { return this->try_emplace(x.first, x.second); }
665 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
666 //! only if there is no element in the container with key equivalent to the key of x.
668 //! <b>Returns</b>: The bool component of the returned pair is true if and only
669 //! if the insertion takes place, and the iterator component of the pair
670 //! points to the element with key equivalent to the key of x.
672 //! <b>Complexity</b>: Logarithmic.
673 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x)
674 { return this->try_emplace(boost::move(x.first), boost::move(x.second)); }
676 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
677 //! only if there is no element in the container with key equivalent to the key of x.
679 //! <b>Returns</b>: The bool component of the returned pair is true if and only
680 //! if the insertion takes place, and the iterator component of the pair
681 //! points to the element with key equivalent to the key of x.
683 //! <b>Complexity</b>: Logarithmic.
684 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
685 { return this->try_emplace(boost::move(x.first), boost::move(x.second)); }
687 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
688 //! no element in the container with key equivalent to the key of x.
690 //! <b>Returns</b>: The bool component of the returned pair is true if and only
691 //! if the insertion takes place, and the iterator component of the pair
692 //! points to the element with key equivalent to the key of x.
694 //! <b>Complexity</b>: Logarithmic.
695 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
696 { return this->base_t::insert_unique(boost::move(x)); }
698 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
699 //! no element in the container with key equivalent to the key of x.
700 //! p is a hint pointing to where the insert should start to search.
702 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
705 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
706 //! is inserted right before p.
707 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
708 { return this->base_t::insert_unique(p, x); }
710 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
711 //! no element in the container with key equivalent to the key of x.
712 //! p is a hint pointing to where the insert should start to search.
714 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
717 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
718 //! is inserted right before p.
719 iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x)
720 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); }
722 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
723 //! no element in the container with key equivalent to the key of x.
724 //! p is a hint pointing to where the insert should start to search.
726 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
729 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
730 //! is inserted right before p.
731 iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
732 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); }
734 //! <b>Effects</b>: Inserts a copy of x in the container.
735 //! p is a hint pointing to where the insert should start to search.
737 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
739 //! <b>Complexity</b>: Logarithmic.
740 iterator insert(const_iterator p, const nonconst_value_type& x)
741 { return this->try_emplace(p, x.first, x.second); }
743 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
744 //! p is a hint pointing to where the insert should start to search.
746 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
748 //! <b>Complexity</b>: Logarithmic.
749 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
750 { return this->base_t::insert_unique(p, boost::move(x)); }
752 //! <b>Requires</b>: first, last are not iterators into *this.
754 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
755 //! if there is no element with key equivalent to the key of that element.
757 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
758 template <class InputIterator>
759 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
760 { this->base_t::insert_unique(first, last); }
762 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
763 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
764 //! if there is no element with key equivalent to the key of that element.
766 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
767 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
768 { this->base_t::insert_unique(il.begin(), il.end()); }
771 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator().
773 //! <b>Effects</b>: If nh is empty, has no effect. Otherwise, inserts the element owned
774 //! by nh if and only if there is no element in the container with a key equivalent to nh.key().
776 //! <b>Returns</b>: If nh is empty, insert_return_type.inserted is false, insert_return_type.position
777 //! is end(), and insert_return_type.node is empty. Otherwise if the insertion took place,
778 //! insert_return_type.inserted is true, insert_return_type.position points to the inserted element,
779 //! and insert_return_type.node is empty; if the insertion failed, insert_return_type.inserted is
780 //! false, insert_return_type.node has the previous value of nh, and insert_return_type.position
781 //! points to an element with a key equivalent to nh.key().
783 //! <b>Complexity</b>: Logarithmic
784 insert_return_type insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
786 typename base_t::node_type n(boost::move(nh));
787 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(boost::move(n)));
788 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node));
791 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible
792 //! to the position just prior to "hint".
794 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted
795 //! right before "hint".
796 insert_return_type insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
798 typename base_t::node_type n(boost::move(nh));
799 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(hint, boost::move(n)));
800 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node));
803 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
805 //! <b>Effects</b>: Inserts an object x of type T constructed with
806 //! std::forward<Args>(args)... in the container if and only if there is
807 //! no element in the container with an equivalent key.
808 //! p is a hint pointing to where the insert should start to search.
810 //! <b>Returns</b>: The bool component of the returned pair is true if and only
811 //! if the insertion takes place, and the iterator component of the pair
812 //! points to the element with key equivalent to the key of x.
814 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
815 //! is inserted right before p.
816 template <class... Args>
817 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
818 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
820 //! <b>Effects</b>: Inserts an object of type T constructed with
821 //! std::forward<Args>(args)... in the container if and only if there is
822 //! no element in the container with an equivalent key.
823 //! p is a hint pointing to where the insert should start to search.
825 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
828 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
829 //! is inserted right before p.
830 template <class... Args>
831 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
832 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
834 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
835 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
837 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
838 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
839 //! forward_as_tuple(forward<Args>(args)...).
841 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
842 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
844 //! <b>Complexity</b>: Logarithmic.
845 template <class... Args>
846 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args)
847 { return this->base_t::try_emplace(const_iterator(), k, boost::forward<Args>(args)...); }
849 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
850 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
852 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
853 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
854 //! forward_as_tuple(forward<Args>(args)...).
856 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
858 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
859 //! is inserted right before p.
860 template <class... Args>
861 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args)
862 { return this->base_t::try_emplace(hint, k, boost::forward<Args>(args)...).first; }
864 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
865 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
867 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
868 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
869 //! forward_as_tuple(forward<Args>(args)...).
871 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
872 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
874 //! <b>Complexity</b>: Logarithmic.
875 template <class... Args>
876 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
877 { return this->base_t::try_emplace(const_iterator(), boost::move(k), boost::forward<Args>(args)...); }
879 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
880 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
882 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
883 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
884 //! forward_as_tuple(forward<Args>(args)...).
886 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
888 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
889 //! is inserted right before p.
890 template <class... Args>
891 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
892 { return this->base_t::try_emplace(hint, boost::move(k), boost::forward<Args>(args)...).first; }
894 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
896 #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \
897 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
898 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
899 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\
901 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
902 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
903 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
905 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
906 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
907 { return this->base_t::try_emplace(const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
909 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
910 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
911 { return this->base_t::try_emplace(hint, k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\
913 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
914 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
915 { return this->base_t::try_emplace(const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
917 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
918 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
919 { return this->base_t::try_emplace(hint, boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\
921 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE)
922 #undef BOOST_CONTAINER_MAP_EMPLACE_CODE
924 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
926 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
928 //! <b>Effects</b>: Erases the element pointed to by p.
930 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
931 //! following q prior to the element being erased. If no such element exists,
934 //! <b>Complexity</b>: Amortized constant time
935 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
937 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
939 //! <b>Returns</b>: Returns the number of erased elements.
941 //! <b>Complexity</b>: log(size()) + count(k)
942 size_type erase(const key_type& x) BOOST_NOEXCEPT_OR_NOTHROW;
944 //! <b>Effects</b>: Erases all the elements in the range [first, last).
946 //! <b>Returns</b>: Returns last.
948 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
949 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW;
953 //! <b>Effects</b>: Removes the first element in the container with key equivalent to k.
955 //! <b>Returns</b>: A node_type owning the element if found, otherwise an empty node_type.
957 //! <b>Complexity</b>: log(a.size()).
958 node_type extract(const key_type& k)
960 typename base_t::node_type base_nh(this->base_t::extract(k));
961 node_type nh(boost::move(base_nh));
962 return BOOST_MOVE_RET(node_type, nh);
965 //! <b>Effects</b>: Removes the element pointed to by "position".
967 //! <b>Returns</b>: A node_type owning the element, otherwise an empty node_type.
969 //! <b>Complexity</b>: Amortized constant.
970 node_type extract(const_iterator position)
972 typename base_t::node_type base_nh(this->base_t::extract(position));
973 node_type nh(boost::move(base_nh));
974 return BOOST_MOVE_RET(node_type, nh);
977 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
979 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
980 //! the comparison object of *this. If there is an element in a with key equivalent to the
981 //! key of an element from source, then that element is not extracted from source.
983 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
984 //! to those same elements but as members of *this. Iterators referring to the transferred
985 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
988 //! <b>Throws</b>: Nothing unless the comparison object throws.
990 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
992 BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source)
994 typedef container_detail::tree
995 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
996 this->merge_unique(static_cast<base2_t&>(source));
999 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1001 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1002 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); }
1004 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1006 BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source)
1008 typedef container_detail::tree
1009 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1010 this->base_t::merge_unique(static_cast<base2_t&>(source));
1013 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1015 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1016 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); }
1018 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1019 //! <b>Effects</b>: Swaps the contents of *this and x.
1021 //! <b>Throws</b>: Nothing.
1023 //! <b>Complexity</b>: Constant.
1025 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1026 && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
1028 //! <b>Effects</b>: erase(a.begin(),a.end()).
1030 //! <b>Postcondition</b>: size() == 0.
1032 //! <b>Complexity</b>: linear in size().
1033 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1035 //! <b>Effects</b>: Returns the comparison object out
1036 //! of which a was constructed.
1038 //! <b>Complexity</b>: Constant.
1039 key_compare key_comp() const;
1041 //! <b>Effects</b>: Returns an object of value_compare constructed out
1042 //! of the comparison object.
1044 //! <b>Complexity</b>: Constant.
1045 value_compare value_comp() const;
1047 //! <b>Returns</b>: An iterator pointing to an element with the key
1048 //! equivalent to x, or end() if such an element is not found.
1050 //! <b>Complexity</b>: Logarithmic.
1051 iterator find(const key_type& x);
1053 //! <b>Returns</b>: A const_iterator pointing to an element with the key
1054 //! equivalent to x, or end() if such an element is not found.
1056 //! <b>Complexity</b>: Logarithmic.
1057 const_iterator find(const key_type& x) const;
1059 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1061 //! <b>Returns</b>: The number of elements with key equivalent to x.
1063 //! <b>Complexity</b>: log(size())+count(k)
1064 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
1065 { return static_cast<size_type>(this->find(x) != this->cend()); }
1067 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1069 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1070 //! than k, or a.end() if such an element is not found.
1072 //! <b>Complexity</b>: Logarithmic
1073 iterator lower_bound(const key_type& x);
1075 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1076 //! less than k, or a.end() if such an element is not found.
1078 //! <b>Complexity</b>: Logarithmic
1079 const_iterator lower_bound(const key_type& x) const;
1081 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1082 //! than x, or end() if such an element is not found.
1084 //! <b>Complexity</b>: Logarithmic
1085 iterator upper_bound(const key_type& x);
1087 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1088 //! less than x, or end() if such an element is not found.
1090 //! <b>Complexity</b>: Logarithmic
1091 const_iterator upper_bound(const key_type& x) const;
1093 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1095 //! <b>Complexity</b>: Logarithmic
1096 std::pair<iterator,iterator> equal_range(const key_type& x);
1098 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1100 //! <b>Complexity</b>: Logarithmic
1101 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
1103 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
1105 //! <b>Complexity</b>: Linear
1108 //! <b>Effects</b>: Returns true if x and y are equal
1110 //! <b>Complexity</b>: Linear to the number of elements in the container.
1111 friend bool operator==(const map& x, const map& y);
1113 //! <b>Effects</b>: Returns true if x and y are unequal
1115 //! <b>Complexity</b>: Linear to the number of elements in the container.
1116 friend bool operator!=(const map& x, const map& y);
1118 //! <b>Effects</b>: Returns true if x is less than y
1120 //! <b>Complexity</b>: Linear to the number of elements in the container.
1121 friend bool operator<(const map& x, const map& y);
1123 //! <b>Effects</b>: Returns true if x is greater than y
1125 //! <b>Complexity</b>: Linear to the number of elements in the container.
1126 friend bool operator>(const map& x, const map& y);
1128 //! <b>Effects</b>: Returns true if x is equal or less than y
1130 //! <b>Complexity</b>: Linear to the number of elements in the container.
1131 friend bool operator<=(const map& x, const map& y);
1133 //! <b>Effects</b>: Returns true if x is equal or greater than y
1135 //! <b>Complexity</b>: Linear to the number of elements in the container.
1136 friend bool operator>=(const map& x, const map& y);
1138 //! <b>Effects</b>: x.swap(y)
1140 //! <b>Complexity</b>: Constant.
1141 friend void swap(map& x, map& y);
1143 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1145 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1147 template<class KeyConvertible>
1148 BOOST_CONTAINER_FORCEINLINE mapped_type& priv_subscript(BOOST_FWD_REF(KeyConvertible) k)
1150 return this->try_emplace(boost::forward<KeyConvertible>(k)).first->second;
1152 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1156 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1158 } //namespace container {
1160 //!has_trivial_destructor_after_move<> == true_type
1161 //!specialization for optimizations
1162 template <class Key, class T, class Compare, class Allocator>
1163 struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator> >
1165 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1166 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1167 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1168 ::boost::has_trivial_destructor_after_move<Compare>::value;
1171 namespace container {
1173 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1175 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1177 //! A multimap is a kind of associative container that supports equivalent keys
1178 //! (possibly containing multiple copies of the same key value) and provides for
1179 //! fast retrieval of values of another type T based on the keys. The multimap class
1180 //! supports bidirectional iterators.
1182 //! A multimap satisfies all of the requirements of a container and of a reversible
1183 //! container and of an associative container. The <code>value_type</code> stored
1184 //! by this container is the value_type is std::pair<const Key, T>.
1186 //! \tparam Key is the key_type of the map
1187 //! \tparam Value is the <code>mapped_type</code>
1188 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1189 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
1190 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
1191 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
1192 template < class Key, class T, class Compare = std::less<Key>
1193 , class Allocator = new_allocator< std::pair< const Key, T> >, class Options = tree_assoc_defaults>
1195 template <class Key, class T, class Compare, class Allocator, class Options>
1199 : public container_detail::tree
1200 < std::pair<const Key, T>
1201 , container_detail::select1st<Key>
1202 , Compare, Allocator, Options>
1205 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1207 BOOST_COPYABLE_AND_MOVABLE(multimap)
1209 typedef container_detail::select1st<Key> select_1st_t;
1210 typedef std::pair<const Key, T> value_type_impl;
1211 typedef container_detail::tree
1212 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t;
1213 typedef container_detail::pair <Key, T> movable_value_type_impl;
1214 typedef typename base_t::value_compare value_compare_impl;
1215 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1217 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
1220 //////////////////////////////////////////////
1224 //////////////////////////////////////////////
1226 typedef Key key_type;
1227 typedef T mapped_type;
1228 typedef std::pair<const Key, T> value_type;
1229 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
1230 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
1231 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
1232 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
1233 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
1234 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
1235 typedef Allocator allocator_type;
1236 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
1237 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
1238 typedef Compare key_compare;
1239 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
1240 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
1241 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
1242 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
1243 typedef std::pair<key_type, mapped_type> nonconst_value_type;
1244 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type;
1245 typedef BOOST_CONTAINER_IMPDEF(node_handle<
1246 typename base_t::node_type::container_node_type
1247 BOOST_MOVE_I value_type
1248 BOOST_MOVE_I allocator_type
1249 BOOST_MOVE_I pair_key_mapped_of_value
1250 <key_type BOOST_MOVE_I mapped_type> >) node_type;
1252 //////////////////////////////////////////////
1254 // construct/copy/destroy
1256 //////////////////////////////////////////////
1258 //! <b>Effects</b>: Default constructs an empty multimap.
1260 //! <b>Complexity</b>: Constant.
1261 BOOST_CONTAINER_FORCEINLINE
1262 multimap() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value &&
1263 container_detail::is_nothrow_default_constructible<Compare>::value)
1266 //A type must be std::pair<CONST Key, T>
1267 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1270 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator.
1272 //! <b>Complexity</b>: Constant.
1273 BOOST_CONTAINER_FORCEINLINE
1274 explicit multimap(const Compare& comp, const allocator_type& a = allocator_type())
1277 //A type must be std::pair<CONST Key, T>
1278 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1281 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison
1282 //! object and allocator.
1284 //! <b>Complexity</b>: Constant.
1285 BOOST_CONTAINER_FORCEINLINE
1286 explicit multimap(const allocator_type& a)
1289 //A type must be std::pair<CONST Key, T>
1290 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1293 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object
1294 //! and allocator, and inserts elements from the range [first ,last ).
1296 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1297 //! comp and otherwise N logN, where N is last - first.
1298 template <class InputIterator>
1299 BOOST_CONTAINER_FORCEINLINE
1300 multimap(InputIterator first, InputIterator last,
1301 const Compare& comp = Compare(),
1302 const allocator_type& a = allocator_type())
1303 : base_t(false, first, last, comp, a)
1305 //A type must be std::pair<CONST Key, T>
1306 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1309 //! <b>Effects</b>: Constructs an empty multimap using the specified
1310 //! allocator, and inserts elements from the range [first ,last ).
1312 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1313 //! comp and otherwise N logN, where N is last - first.
1314 template <class InputIterator>
1315 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const allocator_type& a)
1316 : base_t(false, first, last, Compare(), a)
1318 //A type must be std::pair<CONST Key, T>
1319 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1322 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1323 //! allocator, and inserts elements from the ordered range [first ,last). This function
1324 //! is more efficient than the normal range creation for ordered ranges.
1326 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1328 //! <b>Complexity</b>: Linear in N.
1330 //! <b>Note</b>: Non-standard extension.
1331 template <class InputIterator>
1332 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp = Compare(),
1333 const allocator_type& a = allocator_type())
1334 : base_t(ordered_range, first, last, comp, a)
1337 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1338 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1339 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1341 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1342 //! comp and otherwise N logN, where N is il.first() - il.end().
1343 BOOST_CONTAINER_FORCEINLINE
1344 multimap(std::initializer_list<value_type> il, const Compare& comp = Compare(),
1345 const allocator_type& a = allocator_type())
1346 : base_t(false, il.begin(), il.end(), comp, a)
1348 //A type must be std::pair<CONST Key, T>
1349 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1352 //! <b>Effects</b>: Constructs an empty multimap using the specified
1353 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1355 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1356 //! comp and otherwise N logN, where N is il.first() - il.end().
1357 BOOST_CONTAINER_FORCEINLINE
1358 multimap(std::initializer_list<value_type> il, const allocator_type& a)
1359 : base_t(false, il.begin(), il.end(), Compare(), a)
1361 //A type must be std::pair<CONST Key, T>
1362 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1365 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
1366 //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function
1367 //! is more efficient than the normal range creation for ordered ranges.
1369 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1371 //! <b>Complexity</b>: Linear in N.
1373 //! <b>Note</b>: Non-standard extension.
1374 BOOST_CONTAINER_FORCEINLINE
1375 multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(),
1376 const allocator_type& a = allocator_type())
1377 : base_t(ordered_range, il.begin(), il.end(), comp, a)
1379 //A type must be std::pair<CONST Key, T>
1380 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1384 //! <b>Effects</b>: Copy constructs a multimap.
1386 //! <b>Complexity</b>: Linear in x.size().
1387 BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x)
1388 : base_t(static_cast<const base_t&>(x))
1390 //A type must be std::pair<CONST Key, T>
1391 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1394 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources.
1396 //! <b>Complexity</b>: Constant.
1398 //! <b>Postcondition</b>: x is emptied.
1399 BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x)
1400 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
1401 : base_t(BOOST_MOVE_BASE(base_t, x))
1403 //A type must be std::pair<CONST Key, T>
1404 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1407 //! <b>Effects</b>: Copy constructs a multimap.
1409 //! <b>Complexity</b>: Linear in x.size().
1410 BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x, const allocator_type &a)
1411 : base_t(static_cast<const base_t&>(x), a)
1413 //A type must be std::pair<CONST Key, T>
1414 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1417 //! <b>Effects</b>: Move constructs a multimap using the specified allocator.
1418 //! Constructs *this using x's resources.
1419 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
1421 //! <b>Postcondition</b>: x is emptied.
1422 BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x, const allocator_type &a)
1423 : base_t(BOOST_MOVE_BASE(base_t, x), a)
1425 //A type must be std::pair<CONST Key, T>
1426 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
1429 //! <b>Effects</b>: Makes *this a copy of x.
1431 //! <b>Complexity</b>: Linear in x.size().
1432 BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x)
1433 { return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
1435 //! <b>Effects</b>: this->swap(x.get()).
1437 //! <b>Complexity</b>: Constant.
1438 BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_RV_REF(multimap) x)
1439 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1440 allocator_traits_type::is_always_equal::value) &&
1441 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
1442 { return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
1444 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1445 //! <b>Effects</b>: Assign content of il to *this.
1447 BOOST_CONTAINER_FORCEINLINE multimap& operator=(std::initializer_list<value_type> il)
1450 insert(il.begin(), il.end());
1455 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1457 //! @copydoc ::boost::container::set::get_allocator()
1458 allocator_type get_allocator() const;
1460 //! @copydoc ::boost::container::set::get_stored_allocator()
1461 stored_allocator_type &get_stored_allocator();
1463 //! @copydoc ::boost::container::set::get_stored_allocator() const
1464 const stored_allocator_type &get_stored_allocator() const;
1466 //! @copydoc ::boost::container::set::begin()
1469 //! @copydoc ::boost::container::set::begin() const
1470 const_iterator begin() const;
1472 //! @copydoc ::boost::container::set::cbegin() const
1473 const_iterator cbegin() const;
1475 //! @copydoc ::boost::container::set::end()
1476 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
1478 //! @copydoc ::boost::container::set::end() const
1479 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
1481 //! @copydoc ::boost::container::set::cend() const
1482 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
1484 //! @copydoc ::boost::container::set::rbegin()
1485 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
1487 //! @copydoc ::boost::container::set::rbegin() const
1488 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1490 //! @copydoc ::boost::container::set::crbegin() const
1491 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1493 //! @copydoc ::boost::container::set::rend()
1494 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
1496 //! @copydoc ::boost::container::set::rend() const
1497 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
1499 //! @copydoc ::boost::container::set::crend() const
1500 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
1502 //! @copydoc ::boost::container::set::empty() const
1505 //! @copydoc ::boost::container::set::size() const
1506 size_type size() const;
1508 //! @copydoc ::boost::container::set::max_size() const
1509 size_type max_size() const;
1511 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1513 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1515 //! <b>Effects</b>: Inserts an object of type T constructed with
1516 //! std::forward<Args>(args)... in the container.
1517 //! p is a hint pointing to where the insert should start to search.
1519 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1520 //! to the key of x.
1522 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1523 //! is inserted right before p.
1524 template <class... Args>
1525 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args)
1526 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
1528 //! <b>Effects</b>: Inserts an object of type T constructed with
1529 //! std::forward<Args>(args)... in the container.
1530 //! p is a hint pointing to where the insert should start to search.
1532 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1533 //! to the key of x.
1535 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1536 //! is inserted right before p.
1537 template <class... Args>
1538 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1539 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1541 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1543 #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \
1544 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1545 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
1546 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\
1548 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1549 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1550 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
1552 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE)
1553 #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE
1555 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1557 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1558 //! newly inserted element.
1560 //! <b>Complexity</b>: Logarithmic.
1561 BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x)
1562 { return this->base_t::insert_equal(x); }
1564 //! <b>Effects</b>: Inserts a new value constructed from x and returns
1565 //! the iterator pointing to the newly inserted element.
1567 //! <b>Complexity</b>: Logarithmic.
1568 BOOST_CONTAINER_FORCEINLINE iterator insert(const nonconst_value_type& x)
1569 { return this->base_t::emplace_equal(x); }
1571 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1572 //! the iterator pointing to the newly inserted element.
1574 //! <b>Complexity</b>: Logarithmic.
1575 BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(nonconst_value_type) x)
1576 { return this->base_t::emplace_equal(boost::move(x)); }
1578 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1579 //! the iterator pointing to the newly inserted element.
1581 //! <b>Complexity</b>: Logarithmic.
1582 iterator insert(BOOST_RV_REF(movable_value_type) x)
1583 { return this->base_t::emplace_equal(boost::move(x)); }
1585 //! <b>Effects</b>: Inserts a copy of x in the container.
1586 //! p is a hint pointing to where the insert should start to search.
1588 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1589 //! to the key of x.
1591 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1592 //! is inserted right before p.
1593 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
1594 { return this->base_t::insert_equal(p, x); }
1596 //! <b>Effects</b>: Inserts a new value constructed from x in the container.
1597 //! p is a hint pointing to where the insert should start to search.
1599 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1600 //! to the key of x.
1602 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1603 //! is inserted right before p.
1604 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const nonconst_value_type& x)
1605 { return this->base_t::emplace_hint_equal(p, x); }
1607 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1608 //! p is a hint pointing to where the insert should start to search.
1610 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1611 //! to the key of x.
1613 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1614 //! is inserted right before p.
1615 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x)
1616 { return this->base_t::emplace_hint_equal(p, boost::move(x)); }
1618 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1619 //! p is a hint pointing to where the insert should start to search.
1621 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1622 //! to the key of x.
1624 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1625 //! is inserted right before p.
1626 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
1627 { return this->base_t::emplace_hint_equal(p, boost::move(x)); }
1629 //! <b>Requires</b>: first, last are not iterators into *this.
1631 //! <b>Effects</b>: inserts each element from the range [first,last) .
1633 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1634 template <class InputIterator>
1635 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1636 { this->base_t::insert_equal(first, last); }
1638 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1639 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end().
1641 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
1642 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1643 { this->base_t::insert_equal(il.begin(), il.end()); }
1646 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator().
1648 //! <b>Effects/Returns</b>: If nh is empty, has no effect and returns end(). Otherwise, inserts
1649 //! the element owned by nh and returns an iterator pointing to the newly inserted element.
1650 //! If a range containing elements with keys equivalent to nh.key() exists,
1651 //! the element is inserted at the end of that range. nh is always emptied.
1653 //! <b>Complexity</b>: Logarithmic
1654 iterator insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1656 typename base_t::node_type n(boost::move(nh));
1657 return this->base_t::insert_equal_node(boost::move(n));
1660 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible
1661 //! to the position just prior to "hint".
1663 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted
1664 //! right before "hint".
1665 iterator insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1667 typename base_t::node_type n(boost::move(nh));
1668 return this->base_t::insert_equal_node(hint, boost::move(n));
1671 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1673 //! @copydoc ::boost::container::set::erase(const_iterator)
1674 iterator erase(const_iterator p);
1676 //! @copydoc ::boost::container::set::erase(const key_type&)
1677 size_type erase(const key_type& x);
1679 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator)
1680 iterator erase(const_iterator first, const_iterator last);
1683 //! @copydoc ::boost::container::map::extract(const key_type&)
1684 node_type extract(const key_type& k)
1686 typename base_t::node_type base_nh(this->base_t::extract(k));
1687 return node_type(boost::move(base_nh));
1690 //! @copydoc ::boost::container::map::extract(const_iterator)
1691 node_type extract(const_iterator position)
1693 typename base_t::node_type base_nh(this->base_t::extract(position));
1694 return node_type (boost::move(base_nh));
1697 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1699 //! <b>Effects</b>: Extracts each element in source and insert it into a using
1700 //! the comparison object of *this.
1702 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1703 //! to those same elements but as members of *this. Iterators referring to the transferred
1704 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
1705 //! not into source.
1707 //! <b>Throws</b>: Nothing unless the comparison object throws.
1709 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
1711 void merge(multimap<Key, T, C2, Allocator, Options>& source)
1713 typedef container_detail::tree
1714 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1715 this->base_t::merge_equal(static_cast<base2_t&>(source));
1718 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
1720 void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1721 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); }
1723 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
1725 void merge(map<Key, T, C2, Allocator, Options>& source)
1727 typedef container_detail::tree
1728 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1729 this->base_t::merge_equal(static_cast<base2_t&>(source));
1732 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
1734 void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1735 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); }
1737 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1738 //! @copydoc ::boost::container::set::swap
1739 void swap(multiset& x)
1740 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1741 && boost::container::container_detail::is_nothrow_swappable<Compare>::value );
1743 //! @copydoc ::boost::container::set::clear
1744 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1746 //! @copydoc ::boost::container::set::key_comp
1747 key_compare key_comp() const;
1749 //! @copydoc ::boost::container::set::value_comp
1750 value_compare value_comp() const;
1752 //! <b>Returns</b>: An iterator pointing to an element with the key
1753 //! equivalent to x, or end() if such an element is not found.
1755 //! <b>Complexity</b>: Logarithmic.
1756 iterator find(const key_type& x);
1758 //! <b>Returns</b>: A const iterator pointing to an element with the key
1759 //! equivalent to x, or end() if such an element is not found.
1761 //! <b>Complexity</b>: Logarithmic.
1762 const_iterator find(const key_type& x) const;
1764 //! <b>Returns</b>: The number of elements with key equivalent to x.
1766 //! <b>Complexity</b>: log(size())+count(k)
1767 size_type count(const key_type& x) const;
1769 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1770 //! than k, or a.end() if such an element is not found.
1772 //! <b>Complexity</b>: Logarithmic
1773 iterator lower_bound(const key_type& x);
1775 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1776 //! less than k, or a.end() if such an element is not found.
1778 //! <b>Complexity</b>: Logarithmic
1779 const_iterator lower_bound(const key_type& x) const;
1781 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1782 //! than x, or end() if such an element is not found.
1784 //! <b>Complexity</b>: Logarithmic
1785 iterator upper_bound(const key_type& x);
1787 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1788 //! less than x, or end() if such an element is not found.
1790 //! <b>Complexity</b>: Logarithmic
1791 const_iterator upper_bound(const key_type& x) const;
1793 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1795 //! <b>Complexity</b>: Logarithmic
1796 std::pair<iterator,iterator> equal_range(const key_type& x);
1798 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1800 //! <b>Complexity</b>: Logarithmic
1801 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
1803 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
1805 //! <b>Complexity</b>: Linear
1808 //! <b>Effects</b>: Returns true if x and y are equal
1810 //! <b>Complexity</b>: Linear to the number of elements in the container.
1811 friend bool operator==(const multimap& x, const multimap& y);
1813 //! <b>Effects</b>: Returns true if x and y are unequal
1815 //! <b>Complexity</b>: Linear to the number of elements in the container.
1816 friend bool operator!=(const multimap& x, const multimap& y);
1818 //! <b>Effects</b>: Returns true if x is less than y
1820 //! <b>Complexity</b>: Linear to the number of elements in the container.
1821 friend bool operator<(const multimap& x, const multimap& y);
1823 //! <b>Effects</b>: Returns true if x is greater than y
1825 //! <b>Complexity</b>: Linear to the number of elements in the container.
1826 friend bool operator>(const multimap& x, const multimap& y);
1828 //! <b>Effects</b>: Returns true if x is equal or less than y
1830 //! <b>Complexity</b>: Linear to the number of elements in the container.
1831 friend bool operator<=(const multimap& x, const multimap& y);
1833 //! <b>Effects</b>: Returns true if x is equal or greater than y
1835 //! <b>Complexity</b>: Linear to the number of elements in the container.
1836 friend bool operator>=(const multimap& x, const multimap& y);
1838 //! <b>Effects</b>: x.swap(y)
1840 //! <b>Complexity</b>: Constant.
1841 friend void swap(multimap& x, multimap& y);
1843 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1846 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1848 } //namespace container {
1850 //!has_trivial_destructor_after_move<> == true_type
1851 //!specialization for optimizations
1852 template <class Key, class T, class Compare, class Allocator>
1853 struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator> >
1855 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1856 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1857 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1858 ::boost::has_trivial_destructor_after_move<Compare>::value;
1861 namespace container {
1863 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1867 #include <boost/container/detail/config_end.hpp>
1869 #endif // BOOST_CONTAINER_MAP_HPP