![]() |
|
|||
File indexing completed on 2025-07-01 08:10:24
0001 ////////////////////////////////////////////////////////////////////////////// 0002 // 0003 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost 0004 // Software License, Version 1.0. (See accompanying file 0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 0006 // 0007 // See http://www.boost.org/libs/container for documentation. 0008 // 0009 ////////////////////////////////////////////////////////////////////////////// 0010 #ifndef BOOST_CONTAINER_MAP_HPP 0011 #define BOOST_CONTAINER_MAP_HPP 0012 0013 #ifndef BOOST_CONFIG_HPP 0014 # include <boost/config.hpp> 0015 #endif 0016 0017 #if defined(BOOST_HAS_PRAGMA_ONCE) 0018 # pragma once 0019 #endif 0020 0021 #include <boost/container/detail/config_begin.hpp> 0022 #include <boost/container/detail/workaround.hpp> 0023 0024 // container 0025 #include <boost/container/container_fwd.hpp> 0026 #include <boost/container/new_allocator.hpp> //new_allocator 0027 #include <boost/container/throw_exception.hpp> 0028 // container/detail 0029 #include <boost/container/detail/mpl.hpp> 0030 #include <boost/container/detail/tree.hpp> 0031 #include <boost/container/detail/type_traits.hpp> 0032 #include <boost/container/detail/value_init.hpp> 0033 #include <boost/container/detail/pair.hpp> 0034 #include <boost/container/detail/pair_key_mapped_of_value.hpp> 0035 0036 // move 0037 #include <boost/move/traits.hpp> 0038 #include <boost/move/utility_core.hpp> 0039 // move/detail 0040 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 0041 #include <boost/move/detail/fwd_macros.hpp> 0042 #endif 0043 #include <boost/move/detail/move_helpers.hpp> 0044 // intrusive/detail 0045 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair 0046 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal 0047 // std 0048 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 0049 #include <initializer_list> 0050 #endif 0051 0052 namespace boost { 0053 namespace container { 0054 0055 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 0056 0057 //! A map is a kind of associative container that supports unique keys (contains at 0058 //! most one of each key value) and provides for fast retrieval of values of another 0059 //! type T based on the keys. The map class supports bidirectional iterators. 0060 //! 0061 //! A map satisfies all of the requirements of a container and of a reversible 0062 //! container and of an associative container. The <code>value_type</code> stored 0063 //! by this container is the value_type is std::pair<const Key, T>. 0064 //! 0065 //! \tparam Key is the key_type of the map 0066 //! \tparam T is the <code>mapped_type</code> 0067 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). 0068 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s 0069 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>). 0070 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options. 0071 template < class Key, class T, class Compare = std::less<Key> 0072 , class Allocator = void, class Options = tree_assoc_defaults > 0073 #else 0074 template <class Key, class T, class Compare, class Allocator, class Options> 0075 #endif 0076 class map 0077 ///@cond 0078 : public dtl::tree 0079 < std::pair<const Key, T> 0080 , int 0081 , Compare, Allocator, Options> 0082 ///@endcond 0083 { 0084 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 0085 private: 0086 BOOST_COPYABLE_AND_MOVABLE(map) 0087 0088 typedef int select_1st_t; 0089 typedef std::pair<const Key, T> value_type_impl; 0090 typedef dtl::tree 0091 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t; 0092 typedef dtl::pair <Key, T> movable_value_type_impl; 0093 typedef typename base_t::value_compare value_compare_impl; 0094 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 0095 0096 public: 0097 ////////////////////////////////////////////// 0098 // 0099 // types 0100 // 0101 ////////////////////////////////////////////// 0102 0103 typedef Key key_type; 0104 typedef T mapped_type; 0105 typedef typename base_t::allocator_type allocator_type; 0106 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type; 0107 typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type; 0108 typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer; 0109 typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer; 0110 typedef typename boost::container::allocator_traits<allocator_type>::reference reference; 0111 typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference; 0112 typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type; 0113 typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_type; 0114 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 0115 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; 0116 typedef Compare key_compare; 0117 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 0118 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 0119 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 0120 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 0121 //typedef std::pair<key_type, mapped_type> nonconst_value_type; 0122 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; 0123 typedef BOOST_CONTAINER_IMPDEF(node_handle< 0124 typename base_t::stored_allocator_type 0125 BOOST_MOVE_I pair_key_mapped_of_value 0126 <key_type BOOST_MOVE_I mapped_type> >) node_type; 0127 typedef BOOST_CONTAINER_IMPDEF 0128 (insert_return_type_base<iterator BOOST_MOVE_I node_type>) insert_return_type; 0129 0130 //allocator_type::value_type type must be std::pair<CONST Key, T> 0131 BOOST_CONTAINER_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value)); 0132 0133 ////////////////////////////////////////////// 0134 // 0135 // construct/copy/destroy 0136 // 0137 ////////////////////////////////////////////// 0138 0139 //! <b>Effects</b>: Default constructs an empty map. 0140 //! 0141 //! <b>Complexity</b>: Constant. 0142 inline 0143 map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value && 0144 dtl::is_nothrow_default_constructible<Compare>::value) 0145 : base_t() 0146 {} 0147 0148 //! <b>Effects</b>: Constructs an empty map using the specified comparison object 0149 //! and allocator. 0150 //! 0151 //! <b>Complexity</b>: Constant. 0152 inline map(const Compare& comp, const allocator_type& a) 0153 : base_t(comp, a) 0154 {} 0155 0156 //! <b>Effects</b>: Constructs an empty map using the specified comparison object. 0157 //! 0158 //! <b>Complexity</b>: Constant. 0159 inline explicit map(const Compare& comp) 0160 : base_t(comp) 0161 {} 0162 0163 //! <b>Effects</b>: Constructs an empty map using the specified allocator. 0164 //! 0165 //! <b>Complexity</b>: Constant. 0166 inline explicit map(const allocator_type& a) 0167 : base_t(a) 0168 {} 0169 0170 //! <b>Effects</b>: Constructs an empty map and 0171 //! inserts elements from the range [first ,last ). 0172 //! 0173 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0174 //! the predicate and otherwise N logN, where N is last - first. 0175 template <class InputIterator> 0176 inline map(InputIterator first, InputIterator last) 0177 : base_t(true, first, last) 0178 {} 0179 0180 //! <b>Effects</b>: Constructs an empty map using the specified 0181 //! allocator, and inserts elements from the range [first ,last ). 0182 //! 0183 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0184 //! the predicate and otherwise N logN, where N is last - first. 0185 template <class InputIterator> 0186 inline map(InputIterator first, InputIterator last, const allocator_type& a) 0187 : base_t(true, first, last, Compare(), a) 0188 {} 0189 0190 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0191 //! inserts elements from the range [first ,last ). 0192 //! 0193 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0194 //! the predicate and otherwise N logN, where N is last - first. 0195 template <class InputIterator> 0196 inline map(InputIterator first, InputIterator last, const Compare& comp) 0197 : base_t(true, first, last, comp) 0198 {} 0199 0200 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0201 //! allocator, and inserts elements from the range [first ,last ). 0202 //! 0203 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0204 //! the predicate and otherwise N logN, where N is last - first. 0205 template <class InputIterator> 0206 inline map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a) 0207 : base_t(true, first, last, comp, a) 0208 {} 0209 0210 //! <b>Effects</b>: Constructs an empty map and 0211 //! inserts elements from the ordered unique range [first ,last). This function 0212 //! is more efficient than the normal range creation for ordered ranges. 0213 //! 0214 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 0215 //! unique values. 0216 //! 0217 //! <b>Complexity</b>: Linear in N. 0218 //! 0219 //! <b>Note</b>: Non-standard extension. 0220 template <class InputIterator> 0221 inline map( ordered_unique_range_t, InputIterator first, InputIterator last) 0222 : base_t(ordered_range, first, last) 0223 {} 0224 0225 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0226 //! inserts elements from the ordered unique range [first ,last). This function 0227 //! is more efficient than the normal range creation for ordered ranges. 0228 //! 0229 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 0230 //! unique values. 0231 //! 0232 //! <b>Complexity</b>: Linear in N. 0233 //! 0234 //! <b>Note</b>: Non-standard extension. 0235 template <class InputIterator> 0236 inline map( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp) 0237 : base_t(ordered_range, first, last, comp) 0238 {} 0239 0240 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0241 //! allocator, and inserts elements from the ordered unique range [first ,last). This function 0242 //! is more efficient than the normal range creation for ordered ranges. 0243 //! 0244 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 0245 //! unique values. 0246 //! 0247 //! <b>Complexity</b>: Linear in N. 0248 //! 0249 //! <b>Note</b>: Non-standard extension. 0250 template <class InputIterator> 0251 inline map( ordered_unique_range_t, InputIterator first, InputIterator last 0252 , const Compare& comp, const allocator_type& a) 0253 : base_t(ordered_range, first, last, comp, a) 0254 {} 0255 0256 //! <b>Effects</b>: Constructs an empty map using the specified allocator object and 0257 //! inserts elements from the ordered unique range [first ,last). This function 0258 //! is more efficient than the normal range creation for ordered ranges. 0259 //! 0260 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 0261 //! unique values. 0262 //! 0263 //! <b>Complexity</b>: Linear in N. 0264 //! 0265 //! <b>Note</b>: Non-standard extension. 0266 template <class InputIterator> 0267 inline map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a) 0268 : base_t(ordered_range, first, last, Compare(), a) 0269 {} 0270 0271 0272 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 0273 //! <b>Effects</b>: Constructs an empty map and 0274 //! inserts elements from the range [il.begin(), il.end()). 0275 //! 0276 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted according 0277 //! to the predicate and otherwise N logN, where N is il.first() - il.end(). 0278 inline map(std::initializer_list<value_type> il) 0279 : base_t(true, il.begin(), il.end()) 0280 {} 0281 0282 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0283 //! inserts elements from the range [il.begin(), il.end()). 0284 //! 0285 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0286 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 0287 inline map(std::initializer_list<value_type> il, const Compare& comp) 0288 : base_t(true, il.begin(), il.end(), comp) 0289 {} 0290 0291 //! <b>Effects</b>: Constructs an empty map using the specified 0292 //! allocator, and inserts elements from the range [il.begin(), il.end()). 0293 //! 0294 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0295 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 0296 inline map(std::initializer_list<value_type> il, const allocator_type& a) 0297 : base_t(true, il.begin(), il.end(), Compare(), a) 0298 {} 0299 0300 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0301 //! allocator, and inserts elements from the range [il.begin(), il.end()). 0302 //! 0303 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 0304 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 0305 inline map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) 0306 : base_t(true, il.begin(), il.end(), comp, a) 0307 {} 0308 0309 //! <b>Effects</b>: Constructs an empty map and inserts elements from the ordered unique range [il.begin(), il.end()). 0310 //! This function is more efficient than the normal range creation for ordered ranges. 0311 //! 0312 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 0313 //! unique values. 0314 //! 0315 //! <b>Complexity</b>: Linear in N. 0316 //! 0317 //! <b>Note</b>: Non-standard extension. 0318 inline map(ordered_unique_range_t, std::initializer_list<value_type> il) 0319 : base_t(ordered_range, il.begin(), il.end()) 0320 {} 0321 0322 //! <b>Effects</b>: Constructs an empty map using the specified comparison object, 0323 //! and inserts elements from the ordered unique range [il.begin(), il.end()). This function 0324 //! is more efficient than the normal range creation for ordered ranges. 0325 //! 0326 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 0327 //! unique values. 0328 //! 0329 //! <b>Complexity</b>: Linear in N. 0330 //! 0331 //! <b>Note</b>: Non-standard extension. 0332 inline map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp) 0333 : base_t(ordered_range, il.begin(), il.end(), comp) 0334 {} 0335 0336 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 0337 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function 0338 //! is more efficient than the normal range creation for ordered ranges. 0339 //! 0340 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 0341 //! unique values. 0342 //! 0343 //! <b>Complexity</b>: Linear in N. 0344 //! 0345 //! <b>Note</b>: Non-standard extension. 0346 inline map( ordered_unique_range_t, std::initializer_list<value_type> il 0347 , const Compare& comp, const allocator_type& a) 0348 : base_t(ordered_range, il.begin(), il.end(), comp, a) 0349 {} 0350 0351 #endif 0352 0353 //! <b>Effects</b>: Copy constructs a map. 0354 //! 0355 //! <b>Complexity</b>: Linear in x.size(). 0356 inline map(const map& x) 0357 : base_t(static_cast<const base_t&>(x)) 0358 {} 0359 0360 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources. 0361 //! 0362 //! <b>Complexity</b>: Constant. 0363 //! 0364 //! <b>Postcondition</b>: x is emptied. 0365 inline map(BOOST_RV_REF(map) x) 0366 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) 0367 : base_t(BOOST_MOVE_BASE(base_t, x)) 0368 {} 0369 0370 //! <b>Effects</b>: Copy constructs a map using the specified allocator. 0371 //! 0372 //! <b>Complexity</b>: Linear in x.size(). 0373 inline map(const map& x, const allocator_type &a) 0374 : base_t(static_cast<const base_t&>(x), a) 0375 {} 0376 0377 //! <b>Effects</b>: Move constructs a map using the specified allocator. 0378 //! Constructs *this using x's resources. 0379 //! 0380 //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise. 0381 //! 0382 //! <b>Postcondition</b>: x is emptied. 0383 inline map(BOOST_RV_REF(map) x, const allocator_type &a) 0384 : base_t(BOOST_MOVE_BASE(base_t, x), a) 0385 {} 0386 0387 //! <b>Effects</b>: Makes *this a copy of x. 0388 //! 0389 //! <b>Complexity</b>: Linear in x.size(). 0390 inline map& operator=(BOOST_COPY_ASSIGN_REF(map) x) 0391 { return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 0392 0393 //! <b>Effects</b>: this->swap(x.get()). 0394 //! 0395 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 0396 //! is false and (allocation throws or value_type's move constructor throws) 0397 //! 0398 //! <b>Complexity</b>: Constant if allocator_traits_type:: 0399 //! propagate_on_container_move_assignment is true or 0400 //! this->get>allocator() == x.get_allocator(). Linear otherwise. 0401 inline map& operator=(BOOST_RV_REF(map) x) 0402 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || 0403 allocator_traits_type::is_always_equal::value) && 0404 boost::container::dtl::is_nothrow_move_assignable<Compare>::value) 0405 { return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 0406 0407 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 0408 //! <b>Effects</b>: Assign content of il to *this. 0409 //! 0410 inline map& operator=(std::initializer_list<value_type> il) 0411 { 0412 this->clear(); 0413 insert(il.begin(), il.end()); 0414 return *this; 0415 } 0416 #endif 0417 0418 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 0419 0420 //! <b>Effects</b>: Returns a copy of the allocator that 0421 //! was passed to the object's constructor. 0422 //! 0423 //! <b>Complexity</b>: Constant. 0424 allocator_type get_allocator() const; 0425 0426 //! <b>Effects</b>: Returns a reference to the internal allocator. 0427 //! 0428 //! <b>Throws</b>: Nothing 0429 //! 0430 //! <b>Complexity</b>: Constant. 0431 //! 0432 //! <b>Note</b>: Non-standard extension. 0433 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW; 0434 0435 //! <b>Effects</b>: Returns a reference to the internal allocator. 0436 //! 0437 //! <b>Throws</b>: Nothing 0438 //! 0439 //! <b>Complexity</b>: Constant. 0440 //! 0441 //! <b>Note</b>: Non-standard extension. 0442 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW; 0443 0444 //! <b>Effects</b>: Returns an iterator to the first element contained in the container. 0445 //! 0446 //! <b>Throws</b>: Nothing. 0447 //! 0448 //! <b>Complexity</b>: Constant. 0449 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW; 0450 0451 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 0452 //! 0453 //! <b>Throws</b>: Nothing. 0454 //! 0455 //! <b>Complexity</b>: Constant. 0456 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW; 0457 0458 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 0459 //! 0460 //! <b>Throws</b>: Nothing. 0461 //! 0462 //! <b>Complexity</b>: Constant. 0463 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 0464 0465 //! <b>Effects</b>: Returns an iterator to the end of the container. 0466 //! 0467 //! <b>Throws</b>: Nothing. 0468 //! 0469 //! <b>Complexity</b>: Constant. 0470 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 0471 0472 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 0473 //! 0474 //! <b>Throws</b>: Nothing. 0475 //! 0476 //! <b>Complexity</b>: Constant. 0477 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 0478 0479 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 0480 //! 0481 //! <b>Throws</b>: Nothing. 0482 //! 0483 //! <b>Complexity</b>: Constant. 0484 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 0485 0486 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 0487 //! of the reversed container. 0488 //! 0489 //! <b>Throws</b>: Nothing. 0490 //! 0491 //! <b>Complexity</b>: Constant. 0492 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 0493 0494 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 0495 //! of the reversed container. 0496 //! 0497 //! <b>Throws</b>: Nothing. 0498 //! 0499 //! <b>Complexity</b>: Constant. 0500 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 0501 0502 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 0503 //! of the reversed container. 0504 //! 0505 //! <b>Throws</b>: Nothing. 0506 //! 0507 //! <b>Complexity</b>: Constant. 0508 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 0509 0510 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 0511 //! of the reversed container. 0512 //! 0513 //! <b>Throws</b>: Nothing. 0514 //! 0515 //! <b>Complexity</b>: Constant. 0516 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 0517 0518 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 0519 //! of the reversed container. 0520 //! 0521 //! <b>Throws</b>: Nothing. 0522 //! 0523 //! <b>Complexity</b>: Constant. 0524 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 0525 0526 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 0527 //! of the reversed container. 0528 //! 0529 //! <b>Throws</b>: Nothing. 0530 //! 0531 //! <b>Complexity</b>: Constant. 0532 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 0533 0534 //! <b>Effects</b>: Returns true if the container contains no elements. 0535 //! 0536 //! <b>Throws</b>: Nothing. 0537 //! 0538 //! <b>Complexity</b>: Constant. 0539 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW; 0540 0541 //! <b>Effects</b>: Returns the number of the elements contained in the container. 0542 //! 0543 //! <b>Throws</b>: Nothing. 0544 //! 0545 //! <b>Complexity</b>: Constant. 0546 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW; 0547 0548 //! <b>Effects</b>: Returns the largest possible size of the container. 0549 //! 0550 //! <b>Throws</b>: Nothing. 0551 //! 0552 //! <b>Complexity</b>: Constant. 0553 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW; 0554 0555 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 0556 0557 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 0558 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts 0559 //! value_type(x, T()) into the map. 0560 //! 0561 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this. 0562 //! 0563 //! <b>Complexity</b>: Logarithmic. 0564 mapped_type& operator[](const key_type &k); 0565 0566 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts 0567 //! value_type(boost::move(x), T()) into the map (the key is move-constructed) 0568 //! 0569 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this. 0570 //! 0571 //! <b>Complexity</b>: Logarithmic. 0572 mapped_type& operator[](key_type &&k); 0573 #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) 0574 //in compilers like GCC 3.4, we can't catch temporaries 0575 inline mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); } 0576 inline mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); } 0577 #else 0578 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) 0579 #endif 0580 0581 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 0582 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 0583 //! as if by insert, constructing it from value_type(k, forward<M>(obj)). 0584 //! 0585 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 0586 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 0587 //! references obtained to that element before it was extracted become valid. 0588 //! 0589 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 0590 //! took place. The iterator component is pointing at the element that was inserted or updated. 0591 //! 0592 //! <b>Complexity</b>: Logarithmic in the size of the container. 0593 template <class M> 0594 inline std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj) 0595 { return this->base_t::insert_or_assign(const_iterator(), k, ::boost::forward<M>(obj)); } 0596 0597 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 0598 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 0599 //! as if by insert, constructing it from value_type(k, move(obj)). 0600 //! 0601 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 0602 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 0603 //! references obtained to that element before it was extracted become valid. 0604 //! 0605 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 0606 //! took place. The iterator component is pointing at the element that was inserted or updated. 0607 //! 0608 //! <b>Complexity</b>: Logarithmic in the size of the container. 0609 template <class M> 0610 inline std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) 0611 { return this->base_t::insert_or_assign(const_iterator(), ::boost::move(k), ::boost::forward<M>(obj)); } 0612 0613 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 0614 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 0615 //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element 0616 //! to the container as close as possible to the position just before hint. 0617 //! 0618 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 0619 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 0620 //! references obtained to that element before it was extracted become valid. 0621 //! 0622 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 0623 //! took place. The iterator component is pointing at the element that was inserted or updated. 0624 //! 0625 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if 0626 //! the new element is inserted just before hint. 0627 template <class M> 0628 inline iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj) 0629 { return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)).first; } 0630 0631 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 0632 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 0633 //! as if by insert, constructing it from value_type(k, move(obj)) and the new element 0634 //! to the container as close as possible to the position just before hint. 0635 //! 0636 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 0637 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 0638 //! references obtained to that element before it was extracted become valid. 0639 //! 0640 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 0641 //! took place. The iterator component is pointing at the element that was inserted or updated. 0642 //! 0643 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if 0644 //! the new element is inserted just before hint. 0645 template <class M> 0646 inline iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) 0647 { return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)).first; } 0648 0649 //! <b>Returns</b>: A reference to the element whose key is equivalent to x. 0650 //! Throws: An exception object of type out_of_range if no such element is present. 0651 //! <b>Complexity</b>: logarithmic. 0652 T& at(const key_type& k) 0653 { 0654 iterator i = this->find(k); 0655 if(i == this->end()){ 0656 throw_out_of_range("map::at key not found"); 0657 } 0658 return i->second; 0659 } 0660 0661 //! <b>Returns</b>: A reference to the element whose key is equivalent to x. 0662 //! Throws: An exception object of type out_of_range if no such element is present. 0663 //! <b>Complexity</b>: logarithmic. 0664 BOOST_CONTAINER_ATTRIBUTE_NODISCARD const T& at(const key_type& k) const 0665 { 0666 const_iterator i = this->find(k); 0667 if(i == this->end()){ 0668 throw_out_of_range("map::at key not found"); 0669 } 0670 return i->second; 0671 } 0672 0673 ////////////////////////////////////////////// 0674 // 0675 // modifiers 0676 // 0677 ////////////////////////////////////////////// 0678 0679 //! <b>Effects</b>: Inserts x if and only if there is no element in the container 0680 //! with key equivalent to the key of x. 0681 //! 0682 //! <b>Returns</b>: The bool component of the returned pair is true if and only 0683 //! if the insertion takes place, and the iterator component of the pair 0684 //! points to the element with key equivalent to the key of x. 0685 //! 0686 //! <b>Complexity</b>: Logarithmic. 0687 inline std::pair<iterator,bool> insert(const value_type& x) 0688 { return this->base_t::insert_unique_convertible(x); } 0689 0690 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 0691 //! no element in the container with key equivalent to the key of x. 0692 //! 0693 //! <b>Returns</b>: The bool component of the returned pair is true if and only 0694 //! if the insertion takes place, and the iterator component of the pair 0695 //! points to the element with key equivalent to the key of x. 0696 //! 0697 //! <b>Complexity</b>: Logarithmic. 0698 inline std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) 0699 { return this->base_t::insert_unique_convertible(boost::move(x)); } 0700 0701 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if 0702 //! there is no element in the container with key equivalent to the key of x. 0703 //! 0704 //! <b>Returns</b>: The bool component of the returned pair is true if and only 0705 //! if the insertion takes place, and the iterator component of the pair 0706 //! points to the element with key equivalent to the key of x. 0707 //! 0708 //! <b>Complexity</b>: Logarithmic. 0709 template <class Pair> 0710 inline BOOST_CONTAINER_DOC1ST 0711 ( std::pair<iterator BOOST_MOVE_I bool> 0712 , typename dtl::enable_if_c< 0713 dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value || 0714 dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value 0715 BOOST_MOVE_I std::pair<iterator BOOST_MOVE_I bool> >::type) 0716 insert(BOOST_FWD_REF(Pair) x) 0717 { return this->base_t::emplace_unique(boost::forward<Pair>(x)); } 0718 0719 inline iterator insert(const_iterator p, const value_type& x) 0720 { return this->base_t::insert_unique_hint_convertible(p, x); } 0721 0722 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is 0723 //! no element in the container with key equivalent to the key of x. 0724 //! p is a hint pointing to where the insert should start to search. 0725 //! 0726 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 0727 //! to the key of x. 0728 //! 0729 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 0730 //! is inserted right before p. 0731 inline iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) 0732 { return this->base_t::insert_unique_hint_convertible(p, boost::move(x)); } 0733 0734 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is 0735 //! no element in the container with key equivalent to the key of x. 0736 //! p is a hint pointing to where the insert should start to search. 0737 //! 0738 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 0739 //! to the key of x. 0740 //! 0741 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 0742 //! is inserted right before p. 0743 template <class Pair> 0744 inline BOOST_CONTAINER_DOC1ST 0745 ( iterator 0746 , typename dtl::enable_if_c< 0747 dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value || 0748 dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value 0749 BOOST_MOVE_I iterator >::type) 0750 insert(const_iterator p, BOOST_FWD_REF(Pair) x) 0751 { return this->base_t::emplace_hint_unique(p, boost::forward<Pair>(x)); } 0752 0753 0754 /* 0755 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 0756 //! no element in the container with key equivalent to the key of x. 0757 //! p is a hint pointing to where the insert should start to search. 0758 //! 0759 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 0760 //! to the key of x. 0761 //! 0762 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 0763 //! is inserted right before p. 0764 inline iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) 0765 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); } 0766 0767 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 0768 //! no element in the container with key equivalent to the key of x. 0769 //! p is a hint pointing to where the insert should start to search. 0770 //! 0771 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 0772 //! to the key of x. 0773 //! 0774 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 0775 //! is inserted right before p. 0776 inline iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) 0777 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); } 0778 0779 //! <b>Effects</b>: Inserts a copy of x in the container. 0780 //! p is a hint pointing to where the insert should start to search. 0781 //! 0782 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 0783 //! 0784 //! <b>Complexity</b>: Logarithmic. 0785 inline iterator insert(const_iterator p, const nonconst_value_type& x) 0786 { return this->try_emplace(p, x.first, x.second); } 0787 0788 0789 */ 0790 //! <b>Requires</b>: first, last are not iterators into *this. 0791 //! 0792 //! <b>Effects</b>: inserts each element from the range [first,last) if and only 0793 //! if there is no element with key equivalent to the key of that element. 0794 //! 0795 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 0796 template <class InputIterator> 0797 inline void insert(InputIterator first, InputIterator last) 0798 { this->base_t::insert_unique_range(first, last); } 0799 0800 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 0801 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only 0802 //! if there is no element with key equivalent to the key of that element. 0803 //! 0804 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end()) 0805 inline void insert(std::initializer_list<value_type> il) 0806 { this->base_t::insert_unique_range(il.begin(), il.end()); } 0807 #endif 0808 0809 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator(). 0810 //! 0811 //! <b>Effects</b>: If nh is empty, has no effect. Otherwise, inserts the element owned 0812 //! by nh if and only if there is no element in the container with a key equivalent to nh.key(). 0813 //! 0814 //! <b>Returns</b>: If nh is empty, insert_return_type.inserted is false, insert_return_type.position 0815 //! is end(), and insert_return_type.node is empty. Otherwise if the insertion took place, 0816 //! insert_return_type.inserted is true, insert_return_type.position points to the inserted element, 0817 //! and insert_return_type.node is empty; if the insertion failed, insert_return_type.inserted is 0818 //! false, insert_return_type.node has the previous value of nh, and insert_return_type.position 0819 //! points to an element with a key equivalent to nh.key(). 0820 //! 0821 //! <b>Complexity</b>: Logarithmic 0822 insert_return_type insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 0823 { 0824 typename base_t::node_type n(boost::move(nh)); 0825 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(boost::move(n))); 0826 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node)); 0827 } 0828 0829 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible 0830 //! to the position just prior to "hint". 0831 //! 0832 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted 0833 //! right before "hint". 0834 insert_return_type insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 0835 { 0836 typename base_t::node_type n(boost::move(nh)); 0837 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(hint, boost::move(n))); 0838 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node)); 0839 } 0840 0841 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 0842 0843 //! <b>Effects</b>: Inserts an object x of type T constructed with 0844 //! std::forward<Args>(args)... in the container if and only if there is 0845 //! no element in the container with an equivalent key. 0846 //! p is a hint pointing to where the insert should start to search. 0847 //! 0848 //! <b>Returns</b>: The bool component of the returned pair is true if and only 0849 //! if the insertion takes place, and the iterator component of the pair 0850 //! points to the element with key equivalent to the key of x. 0851 //! 0852 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 0853 //! is inserted right before p. 0854 template <class... Args> 0855 inline std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) 0856 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); } 0857 0858 //! <b>Effects</b>: Inserts an object of type T constructed with 0859 //! std::forward<Args>(args)... in the container if and only if there is 0860 //! no element in the container with an equivalent key. 0861 //! p is a hint pointing to where the insert should start to search. 0862 //! 0863 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 0864 //! to the key of x. 0865 //! 0866 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 0867 //! is inserted right before p. 0868 template <class... Args> 0869 inline iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 0870 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); } 0871 0872 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 0873 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). 0874 //! 0875 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 0876 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), 0877 //! forward_as_tuple(forward<Args>(args)...). 0878 //! 0879 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the 0880 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. 0881 //! 0882 //! <b>Complexity</b>: Logarithmic. 0883 template <class... Args> 0884 inline std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args) 0885 { return this->base_t::try_emplace(const_iterator(), k, boost::forward<Args>(args)...); } 0886 0887 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 0888 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). 0889 //! 0890 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 0891 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), 0892 //! forward_as_tuple(forward<Args>(args)...). 0893 //! 0894 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. 0895 //! 0896 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value 0897 //! is inserted right before p. 0898 template <class... Args> 0899 inline iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args) 0900 { return this->base_t::try_emplace(hint, k, boost::forward<Args>(args)...).first; } 0901 0902 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 0903 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). 0904 //! 0905 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 0906 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), 0907 //! forward_as_tuple(forward<Args>(args)...). 0908 //! 0909 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the 0910 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. 0911 //! 0912 //! <b>Complexity</b>: Logarithmic. 0913 template <class... Args> 0914 inline std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) 0915 { return this->base_t::try_emplace(const_iterator(), boost::move(k), boost::forward<Args>(args)...); } 0916 0917 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 0918 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). 0919 //! 0920 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 0921 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), 0922 //! forward_as_tuple(forward<Args>(args)...). 0923 //! 0924 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. 0925 //! 0926 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value 0927 //! is inserted right before p. 0928 template <class... Args> 0929 inline iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) 0930 { return this->base_t::try_emplace(hint, boost::move(k), boost::forward<Args>(args)...).first; } 0931 0932 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 0933 0934 #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \ 0935 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 0936 inline std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ 0937 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\ 0938 \ 0939 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 0940 inline iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 0941 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 0942 \ 0943 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 0944 inline std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 0945 { return this->base_t::try_emplace(const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 0946 \ 0947 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 0948 inline iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 0949 { return this->base_t::try_emplace(hint, k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\ 0950 \ 0951 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 0952 inline std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 0953 { return this->base_t::try_emplace(const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 0954 \ 0955 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 0956 inline iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 0957 { return this->base_t::try_emplace(hint, boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\ 0958 // 0959 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE) 0960 #undef BOOST_CONTAINER_MAP_EMPLACE_CODE 0961 0962 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 0963 0964 //! <b>Effects</b>: If present, erases the element in the container with key equivalent to x. 0965 //! 0966 //! <b>Returns</b>: Returns the number of erased elements (0/1). 0967 //! 0968 //! <b>Complexity</b>: log(size()) + count(k) 0969 inline size_type erase(const key_type& x) 0970 { return this->base_t::erase_unique(x); } 0971 0972 //! <b>Requires</b>: This overload is available only if 0973 //! key_compare::is_transparent exists. 0974 //! 0975 //! <b>Effects</b>: If present, erases the element in the container with key equivalent to x. 0976 //! 0977 //! <b>Returns</b>: Returns the number of erased elements (0/1). 0978 template <class K> 0979 inline BOOST_CONTAINER_DOC1ST 0980 (size_type 0981 , typename dtl::enable_if_c< 0982 dtl::is_transparent<key_compare>::value && //transparent 0983 !dtl::is_convertible<K BOOST_MOVE_I iterator>::value && //not convertible to iterator 0984 !dtl::is_convertible<K BOOST_MOVE_I const_iterator>::value //not convertible to const_iterator 0985 BOOST_MOVE_I size_type>::type) 0986 erase(const K& x) 0987 { return this->base_t::erase_unique(x); } 0988 0989 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 0990 0991 //! <b>Effects</b>: Erases the element pointed to by p. 0992 //! 0993 //! <b>Returns</b>: Returns an iterator pointing to the element immediately 0994 //! following q prior to the element being erased. If no such element exists, 0995 //! returns end(). 0996 //! 0997 //! <b>Complexity</b>: Amortized constant time 0998 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW; 0999 1000 //! <b>Effects</b>: Erases all the elements in the range [first, last). 1001 //! 1002 //! <b>Returns</b>: Returns last. 1003 //! 1004 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. 1005 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW; 1006 1007 #else 1008 using base_t::erase; 1009 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1010 1011 //! <b>Effects</b>: Removes the first element in the container with key equivalent to k. 1012 //! 1013 //! <b>Returns</b>: A node_type owning the element if found, otherwise an empty node_type. 1014 //! 1015 //! <b>Complexity</b>: log(size()). 1016 node_type extract(const key_type& k) 1017 { 1018 typename base_t::node_type base_nh(this->base_t::extract(k)); 1019 node_type nh(boost::move(base_nh)); 1020 return BOOST_MOVE_RET(node_type, nh); 1021 } 1022 1023 //! <b>Effects</b>: Removes the element pointed to by "position". 1024 //! 1025 //! <b>Returns</b>: A node_type owning the element, otherwise an empty node_type. 1026 //! 1027 //! <b>Complexity</b>: Amortized constant. 1028 node_type extract(const_iterator position) 1029 { 1030 typename base_t::node_type base_nh(this->base_t::extract(position)); 1031 node_type nh(boost::move(base_nh)); 1032 return BOOST_MOVE_RET(node_type, nh); 1033 } 1034 1035 //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). 1036 //! 1037 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using 1038 //! the comparison object of *this. If there is an element in a with key equivalent to the 1039 //! key of an element from source, then that element is not extracted from source. 1040 //! 1041 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 1042 //! to those same elements but as members of *this. Iterators referring to the transferred 1043 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 1044 //! not into source. 1045 //! 1046 //! <b>Throws</b>: Nothing unless the comparison object throws. 1047 //! 1048 //! <b>Complexity</b>: N log(size() + N) (N has the value source.size()) 1049 template<class C2> 1050 inline void merge(map<Key, T, C2, Allocator, Options>& source) 1051 { 1052 typedef dtl::tree 1053 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 1054 this->merge_unique(static_cast<base2_t&>(source)); 1055 } 1056 1057 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&) 1058 template<class C2> 1059 inline void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 1060 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); } 1061 1062 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&) 1063 template<class C2> 1064 inline void merge(multimap<Key, T, C2, Allocator, Options>& source) 1065 { 1066 typedef dtl::tree 1067 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 1068 this->base_t::merge_unique(static_cast<base2_t&>(source)); 1069 } 1070 1071 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&) 1072 template<class C2> 1073 inline void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 1074 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); } 1075 1076 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1077 //! <b>Effects</b>: Swaps the contents of *this and x. 1078 //! 1079 //! <b>Throws</b>: Nothing. 1080 //! 1081 //! <b>Complexity</b>: Constant. 1082 void swap(map& x) 1083 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1084 && boost::container::dtl::is_nothrow_swappable<Compare>::value ); 1085 1086 //! <b>Effects</b>: erase(begin(),end()). 1087 //! 1088 //! <b>Postcondition</b>: size() == 0. 1089 //! 1090 //! <b>Complexity</b>: linear in size(). 1091 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 1092 1093 //! <b>Effects</b>: Returns the comparison object out 1094 //! of which a was constructed. 1095 //! 1096 //! <b>Complexity</b>: Constant. 1097 key_compare key_comp() const; 1098 1099 //! <b>Effects</b>: Returns an object of value_compare constructed out 1100 //! of the comparison object. 1101 //! 1102 //! <b>Complexity</b>: Constant. 1103 value_compare value_comp() const; 1104 1105 //! <b>Returns</b>: An iterator pointing to an element with the key 1106 //! equivalent to x, or end() if such an element is not found. 1107 //! 1108 //! <b>Complexity</b>: Logarithmic. 1109 iterator find(const key_type& x); 1110 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. 1113 //! 1114 //! <b>Complexity</b>: Logarithmic. 1115 const_iterator find(const key_type& x) const; 1116 1117 //! <b>Requires</b>: This overload is available only if 1118 //! key_compare::is_transparent exists. 1119 //! 1120 //! <b>Returns</b>: An iterator pointing to an element with the key 1121 //! equivalent to x, or end() if such an element is not found. 1122 //! 1123 //! <b>Complexity</b>: Logarithmic. 1124 template<typename K> 1125 iterator find(const K& x); 1126 1127 //! <b>Requires</b>: This overload is available only if 1128 //! key_compare::is_transparent exists. 1129 //! 1130 //! <b>Returns</b>: A const_iterator pointing to an element with the key 1131 //! equivalent to x, or end() if such an element is not found. 1132 //! 1133 //! <b>Complexity</b>: Logarithmic. 1134 template<typename K> 1135 const_iterator find(const K& x) const; 1136 1137 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1138 1139 //! <b>Returns</b>: The number of elements with key equivalent to x. 1140 //! 1141 //! <b>Complexity</b>: log(size())+count(k) 1142 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 1143 size_type count(const key_type& x) const 1144 { return static_cast<size_type>(this->find(x) != this->cend()); } 1145 1146 //! <b>Requires</b>: This overload is available only if 1147 //! key_compare::is_transparent exists. 1148 //! 1149 //! <b>Returns</b>: The number of elements with key equivalent to x. 1150 //! 1151 //! <b>Complexity</b>: log(size())+count(k) 1152 template<typename K> 1153 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 1154 size_type count(const K& x) const 1155 { return static_cast<size_type>(this->find(x) != this->cend()); } 1156 1157 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1158 1159 //! <b>Returns</b>: Returns true if there is an element with key 1160 //! equivalent to key in the container, otherwise false. 1161 //! 1162 //! <b>Complexity</b>: log(size()). 1163 bool contains(const key_type& x) const; 1164 1165 //! <b>Requires</b>: This overload is available only if 1166 //! key_compare::is_transparent exists. 1167 //! 1168 //! <b>Returns</b>: Returns true if there is an element with key 1169 //! equivalent to key in the container, otherwise false. 1170 //! 1171 //! <b>Complexity</b>: log(size()). 1172 template<typename K> 1173 bool contains(const K& x) const; 1174 1175 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1176 //! than x, or end() if such an element is not found. 1177 //! 1178 //! <b>Complexity</b>: Logarithmic 1179 iterator lower_bound(const key_type& x); 1180 1181 //! <b>Returns</b>: A const iterator pointing to the first element with key not 1182 //! less than x, or end() if such an element is not found. 1183 //! 1184 //! <b>Complexity</b>: Logarithmic 1185 const_iterator lower_bound(const key_type& x) const; 1186 1187 //! <b>Requires</b>: This overload is available only if 1188 //! key_compare::is_transparent exists. 1189 //! 1190 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1191 //! than x, or end() if such an element is not found. 1192 //! 1193 //! <b>Complexity</b>: Logarithmic 1194 template<typename K> 1195 iterator lower_bound(const K& x); 1196 1197 //! <b>Requires</b>: This overload is available only if 1198 //! key_compare::is_transparent exists. 1199 //! 1200 //! <b>Returns</b>: A const iterator pointing to the first element with key not 1201 //! less than x, or end() if such an element is not found. 1202 //! 1203 //! <b>Complexity</b>: Logarithmic 1204 template<typename K> 1205 const_iterator lower_bound(const K& x) const; 1206 1207 //! <b>Returns</b>: An iterator pointing to the first element with key greater 1208 //! than x, or end() if such an element is not found. 1209 //! 1210 //! <b>Complexity</b>: Logarithmic 1211 iterator upper_bound(const key_type& x); 1212 1213 //! <b>Returns</b>: A const iterator pointing to the first element with key 1214 //! greater than x, or end() if such an element is not found. 1215 //! 1216 //! <b>Complexity</b>: Logarithmic 1217 const_iterator upper_bound(const key_type& x) const; 1218 1219 //! <b>Requires</b>: This overload is available only if 1220 //! key_compare::is_transparent exists. 1221 //! 1222 //! <b>Returns</b>: An iterator pointing to the first element with key greater 1223 //! than x, or end() if such an element is not found. 1224 //! 1225 //! <b>Complexity</b>: Logarithmic 1226 template<typename K> 1227 iterator upper_bound(const K& x); 1228 1229 //! <b>Requires</b>: This overload is available only if 1230 //! key_compare::is_transparent exists. 1231 //! 1232 //! <b>Returns</b>: A const iterator pointing to the first element with key 1233 //! greater than x, or end() if such an element is not found. 1234 //! 1235 //! <b>Complexity</b>: Logarithmic 1236 template<typename K> 1237 const_iterator upper_bound(const K& x) const; 1238 1239 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1240 //! 1241 //! <b>Complexity</b>: Logarithmic 1242 std::pair<iterator,iterator> equal_range(const key_type& x); 1243 1244 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1245 //! 1246 //! <b>Complexity</b>: Logarithmic 1247 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; 1248 1249 //! <b>Requires</b>: This overload is available only if 1250 //! key_compare::is_transparent exists. 1251 //! 1252 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1253 //! 1254 //! <b>Complexity</b>: Logarithmic 1255 template<typename K> 1256 std::pair<iterator,iterator> equal_range(const K& x); 1257 1258 //! <b>Requires</b>: This overload is available only if 1259 //! key_compare::is_transparent exists. 1260 //! 1261 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1262 //! 1263 //! <b>Complexity</b>: Logarithmic 1264 template<typename K> 1265 std::pair<const_iterator,const_iterator> equal_range(const K& x) const; 1266 1267 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 1268 //! 1269 //! <b>Complexity</b>: Linear 1270 void rebalance(); 1271 1272 //! <b>Effects</b>: Returns true if x and y are equal 1273 //! 1274 //! <b>Complexity</b>: Linear to the number of elements in the container. 1275 friend bool operator==(const map& x, const map& y); 1276 1277 //! <b>Effects</b>: Returns true if x and y are unequal 1278 //! 1279 //! <b>Complexity</b>: Linear to the number of elements in the container. 1280 friend bool operator!=(const map& x, const map& y); 1281 1282 //! <b>Effects</b>: Returns true if x is less than y 1283 //! 1284 //! <b>Complexity</b>: Linear to the number of elements in the container. 1285 friend bool operator<(const map& x, const map& y); 1286 1287 //! <b>Effects</b>: Returns true if x is greater than y 1288 //! 1289 //! <b>Complexity</b>: Linear to the number of elements in the container. 1290 friend bool operator>(const map& x, const map& y); 1291 1292 //! <b>Effects</b>: Returns true if x is equal or less than y 1293 //! 1294 //! <b>Complexity</b>: Linear to the number of elements in the container. 1295 friend bool operator<=(const map& x, const map& y); 1296 1297 //! <b>Effects</b>: Returns true if x is equal or greater than y 1298 //! 1299 //! <b>Complexity</b>: Linear to the number of elements in the container. 1300 friend bool operator>=(const map& x, const map& y); 1301 1302 //! <b>Effects</b>: x.swap(y) 1303 //! 1304 //! <b>Complexity</b>: Constant. 1305 friend void swap(map& x, map& y) 1306 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1307 && boost::container::dtl::is_nothrow_swappable<Compare>::value ); 1308 1309 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1310 1311 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1312 private: 1313 template<class KeyConvertible> 1314 inline mapped_type& priv_subscript(BOOST_FWD_REF(KeyConvertible) k) 1315 { 1316 return this->try_emplace(boost::forward<KeyConvertible>(k)).first->second; 1317 } 1318 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1319 }; 1320 1321 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 1322 1323 template <typename InputIterator> 1324 map(InputIterator, InputIterator) -> 1325 map< it_based_non_const_first_type_t<InputIterator> 1326 , it_based_second_type_t<InputIterator>>; 1327 1328 template < typename InputIterator, typename AllocatorOrCompare> 1329 map(InputIterator, InputIterator, AllocatorOrCompare const&) -> 1330 map< it_based_non_const_first_type_t<InputIterator> 1331 , it_based_second_type_t<InputIterator> 1332 , typename dtl::if_c< // Compare 1333 dtl::is_allocator<AllocatorOrCompare>::value 1334 , std::less<it_based_non_const_first_type_t<InputIterator>> 1335 , AllocatorOrCompare 1336 >::type 1337 , typename dtl::if_c< // Allocator 1338 dtl::is_allocator<AllocatorOrCompare>::value 1339 , AllocatorOrCompare 1340 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 1341 >::type 1342 >; 1343 1344 template < typename InputIterator, typename Compare, typename Allocator 1345 , typename = dtl::require_nonallocator_t<Compare> 1346 , typename = dtl::require_allocator_t<Allocator>> 1347 map(InputIterator, InputIterator, Compare const&, Allocator const&) -> 1348 map< it_based_non_const_first_type_t<InputIterator> 1349 , it_based_second_type_t<InputIterator> 1350 , Compare 1351 , Allocator>; 1352 1353 template <typename InputIterator> 1354 map(ordered_unique_range_t, InputIterator, InputIterator) -> 1355 map< it_based_non_const_first_type_t<InputIterator> 1356 , it_based_second_type_t<InputIterator>>; 1357 1358 template < typename InputIterator, typename AllocatorOrCompare> 1359 map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) -> 1360 map< it_based_non_const_first_type_t<InputIterator> 1361 , it_based_second_type_t<InputIterator> 1362 , typename dtl::if_c< // Compare 1363 dtl::is_allocator<AllocatorOrCompare>::value 1364 , std::less<it_based_non_const_first_type_t<InputIterator>> 1365 , AllocatorOrCompare 1366 >::type 1367 , typename dtl::if_c< // Allocator 1368 dtl::is_allocator<AllocatorOrCompare>::value 1369 , AllocatorOrCompare 1370 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 1371 >::type 1372 >; 1373 1374 template < typename InputIterator, typename Compare, typename Allocator 1375 , typename = dtl::require_nonallocator_t<Compare> 1376 , typename = dtl::require_allocator_t<Allocator>> 1377 map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) -> 1378 map< it_based_non_const_first_type_t<InputIterator> 1379 , it_based_second_type_t<InputIterator> 1380 , Compare 1381 , Allocator>; 1382 1383 #endif 1384 1385 1386 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1387 1388 } //namespace container { 1389 1390 //!has_trivial_destructor_after_move<> == true_type 1391 //!specialization for optimizations 1392 template <class Key, class T, class Compare, class Allocator, class Options> 1393 struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator, Options> > 1394 { 1395 typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree; 1396 BOOST_STATIC_CONSTEXPR bool value = ::boost::has_trivial_destructor_after_move<tree>::value; 1397 }; 1398 1399 namespace container { 1400 1401 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1402 1403 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 1404 1405 //! A multimap is a kind of associative container that supports equivalent keys 1406 //! (possibly containing multiple copies of the same key value) and provides for 1407 //! fast retrieval of values of another type T based on the keys. The multimap class 1408 //! supports bidirectional iterators. 1409 //! 1410 //! A multimap satisfies all of the requirements of a container and of a reversible 1411 //! container and of an associative container. The <code>value_type</code> stored 1412 //! by this container is the value_type is std::pair<const Key, T>. 1413 //! 1414 //! \tparam Key is the key_type of the map 1415 //! \tparam Value is the <code>mapped_type</code> 1416 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). 1417 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s 1418 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>). 1419 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options. 1420 template < class Key, class T, class Compare = std::less<Key> 1421 , class Allocator = new_allocator< std::pair< const Key, T> >, class Options = tree_assoc_defaults> 1422 #else 1423 template <class Key, class T, class Compare, class Allocator, class Options> 1424 #endif 1425 class multimap 1426 ///@cond 1427 : public dtl::tree 1428 < std::pair<const Key, T> 1429 , int 1430 , Compare, Allocator, Options> 1431 ///@endcond 1432 { 1433 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1434 private: 1435 BOOST_COPYABLE_AND_MOVABLE(multimap) 1436 1437 typedef int select_1st_t; 1438 typedef std::pair<const Key, T> value_type_impl; 1439 typedef dtl::tree 1440 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t; 1441 typedef dtl::pair <Key, T> movable_value_type_impl; 1442 typedef typename base_t::value_compare value_compare_impl; 1443 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1444 1445 public: 1446 ////////////////////////////////////////////// 1447 // 1448 // types 1449 // 1450 ////////////////////////////////////////////// 1451 1452 typedef Key key_type; 1453 typedef T mapped_type; 1454 typedef typename base_t::allocator_type allocator_type; 1455 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type; 1456 typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type; 1457 typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer; 1458 typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer; 1459 typedef typename boost::container::allocator_traits<allocator_type>::reference reference; 1460 typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference; 1461 typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type; 1462 typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_type; 1463 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 1464 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; 1465 typedef Compare key_compare; 1466 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 1467 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 1468 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 1469 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 1470 //typedef std::pair<key_type, mapped_type> nonconst_value_type; 1471 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; 1472 typedef BOOST_CONTAINER_IMPDEF(node_handle< 1473 typename base_t::stored_allocator_type 1474 BOOST_MOVE_I pair_key_mapped_of_value 1475 <key_type BOOST_MOVE_I mapped_type> >) node_type; 1476 1477 //allocator_type::value_type type must be std::pair<CONST Key, T> 1478 BOOST_CONTAINER_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value)); 1479 1480 ////////////////////////////////////////////// 1481 // 1482 // construct/copy/destroy 1483 // 1484 ////////////////////////////////////////////// 1485 1486 //! <b>Effects</b>: Default constructs an empty multimap. 1487 //! 1488 //! <b>Complexity</b>: Constant. 1489 inline multimap() 1490 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value && 1491 dtl::is_nothrow_default_constructible<Compare>::value) 1492 : base_t() 1493 {} 1494 1495 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator 1496 //! object and allocator. 1497 //! 1498 //! <b>Complexity</b>: Constant. 1499 inline explicit multimap(const allocator_type& a) 1500 : base_t(a) 1501 {} 1502 1503 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison. 1504 //! 1505 //! <b>Complexity</b>: Constant. 1506 inline explicit multimap(const Compare& comp) 1507 : base_t(comp) 1508 {} 1509 1510 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison and allocator. 1511 //! 1512 //! <b>Complexity</b>: Constant. 1513 inline multimap(const Compare& comp, const allocator_type& a) 1514 : base_t(comp, a) 1515 {} 1516 1517 //! <b>Effects</b>: Constructs an empty multimap and 1518 //! inserts elements from the range [first ,last ). 1519 //! 1520 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1521 //! the predicate and otherwise N logN, where N is last - first. 1522 template <class InputIterator> 1523 inline multimap(InputIterator first, InputIterator last) 1524 : base_t(false, first, last) 1525 {} 1526 1527 //! <b>Effects</b>: Constructs an empty multimap using the specified 1528 //! allocator, and inserts elements from the range [first ,last ). 1529 //! 1530 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1531 //! the predicate and otherwise N logN, where N is last - first. 1532 template <class InputIterator> 1533 inline multimap(InputIterator first, InputIterator last, const allocator_type& a) 1534 : base_t(false, first, last, Compare(), a) 1535 {} 1536 1537 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1538 //! inserts elements from the range [first ,last ). 1539 //! 1540 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1541 //! the predicate and otherwise N logN, where N is last - first. 1542 template <class InputIterator> 1543 inline multimap(InputIterator first, InputIterator last, const Compare& comp) 1544 : base_t(false, first, last, comp) 1545 {} 1546 1547 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object 1548 //! and allocator, and inserts elements from the range [first ,last ). 1549 //! 1550 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1551 //! the predicate and otherwise N logN, where N is last - first. 1552 template <class InputIterator> 1553 inline multimap(InputIterator first, InputIterator last, 1554 const Compare& comp, const allocator_type& a) 1555 : base_t(false, first, last, comp, a) 1556 {} 1557 1558 //! <b>Effects</b>: Constructs an empty multimap and 1559 //! inserts elements from the ordered range [first ,last). This function 1560 //! is more efficient than the normal range creation for ordered ranges. 1561 //! 1562 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1563 //! 1564 //! <b>Complexity</b>: Linear in N. 1565 //! 1566 //! <b>Note</b>: Non-standard extension. 1567 template <class InputIterator> 1568 inline multimap(ordered_range_t, InputIterator first, InputIterator last) 1569 : base_t(ordered_range, first, last) 1570 {} 1571 1572 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1573 //! inserts elements from the ordered range [first ,last). This function 1574 //! is more efficient than the normal range creation for ordered ranges. 1575 //! 1576 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1577 //! 1578 //! <b>Complexity</b>: Linear in N. 1579 //! 1580 //! <b>Note</b>: Non-standard extension. 1581 template <class InputIterator> 1582 inline multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp) 1583 : base_t(ordered_range, first, last, comp) 1584 {} 1585 1586 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1587 //! allocator, and inserts elements from the ordered range [first ,last). This function 1588 //! is more efficient than the normal range creation for ordered ranges. 1589 //! 1590 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1591 //! 1592 //! <b>Complexity</b>: Linear in N. 1593 //! 1594 //! <b>Note</b>: Non-standard extension. 1595 template <class InputIterator> 1596 inline multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, 1597 const allocator_type& a) 1598 : base_t(ordered_range, first, last, comp, a) 1599 {} 1600 1601 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator and 1602 //! inserts elements from the ordered range [first ,last). This function 1603 //! is more efficient than the normal range creation for ordered ranges. 1604 //! 1605 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1606 //! 1607 //! <b>Complexity</b>: Linear in N. 1608 //! 1609 //! <b>Note</b>: Non-standard extension. 1610 template <class InputIterator> 1611 inline multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type& a) 1612 : base_t(ordered_range, first, last, Compare(), a) 1613 {} 1614 1615 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1616 //! <b>Effects</b>: Constructs an empty multimap and 1617 //! and inserts elements from the range [il.begin(), il.end()). 1618 //! 1619 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1620 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 1621 inline multimap(std::initializer_list<value_type> il) 1622 : base_t(false, il.begin(), il.end()) 1623 {} 1624 1625 //! <b>Effects</b>: Constructs an empty multimap using the specified 1626 //! allocator, and inserts elements from the range [il.begin(), il.end()). 1627 //! 1628 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1629 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 1630 inline multimap(std::initializer_list<value_type> il, const allocator_type& a) 1631 : base_t(false, il.begin(), il.end(), Compare(), a) 1632 {} 1633 1634 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1635 //! inserts elements from the range [il.begin(), il.end()). 1636 //! 1637 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1638 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 1639 inline multimap(std::initializer_list<value_type> il, const Compare& comp) 1640 : base_t(false, il.begin(), il.end(), comp) 1641 {} 1642 1643 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1644 //! allocator, and inserts elements from the range [il.begin(), il.end()). 1645 //! 1646 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1647 //! the predicate and otherwise N logN, where N is il.first() - il.end(). 1648 inline multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) 1649 : base_t(false, il.begin(), il.end(), comp, a) 1650 {} 1651 1652 1653 //! <b>Effects</b>: Constructs an empty map and 1654 //! inserts elements from the ordered range [il.begin(), il.end()). This function 1655 //! is more efficient than the normal range creation for ordered ranges. 1656 //! 1657 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1658 //! 1659 //! <b>Complexity</b>: Linear in N. 1660 //! 1661 //! <b>Note</b>: Non-standard extension. 1662 inline multimap(ordered_range_t, std::initializer_list<value_type> il) 1663 : base_t(ordered_range, il.begin(), il.end()) 1664 {} 1665 1666 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 1667 //! inserts elements from the ordered range [il.begin(), il.end()). This function 1668 //! is more efficient than the normal range creation for ordered ranges. 1669 //! 1670 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1671 //! 1672 //! <b>Complexity</b>: Linear in N. 1673 //! 1674 //! <b>Note</b>: Non-standard extension. 1675 inline multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp) 1676 : base_t(ordered_range, il.begin(), il.end(), comp) 1677 {} 1678 1679 //! <b>Effects</b>: Constructs an empty map and 1680 //! inserts elements from the ordered range [il.begin(), il.end()). This function 1681 //! is more efficient than the normal range creation for ordered ranges. 1682 //! 1683 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1684 //! 1685 //! <b>Complexity</b>: Linear in N. 1686 //! 1687 //! <b>Note</b>: Non-standard extension. 1688 inline multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) 1689 : base_t(ordered_range, il.begin(), il.end(), comp, a) 1690 {} 1691 1692 #endif 1693 1694 //! <b>Effects</b>: Copy constructs a multimap. 1695 //! 1696 //! <b>Complexity</b>: Linear in x.size(). 1697 inline multimap(const multimap& x) 1698 : base_t(static_cast<const base_t&>(x)) 1699 {} 1700 1701 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources. 1702 //! 1703 //! <b>Complexity</b>: Constant. 1704 //! 1705 //! <b>Postcondition</b>: x is emptied. 1706 inline multimap(BOOST_RV_REF(multimap) x) 1707 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) 1708 : base_t(BOOST_MOVE_BASE(base_t, x)) 1709 {} 1710 1711 //! <b>Effects</b>: Copy constructs a multimap. 1712 //! 1713 //! <b>Complexity</b>: Linear in x.size(). 1714 inline multimap(const multimap& x, const allocator_type &a) 1715 : base_t(static_cast<const base_t&>(x), a) 1716 {} 1717 1718 //! <b>Effects</b>: Move constructs a multimap using the specified allocator. 1719 //! Constructs *this using x's resources. 1720 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. 1721 //! 1722 //! <b>Postcondition</b>: x is emptied. 1723 inline multimap(BOOST_RV_REF(multimap) x, const allocator_type &a) 1724 : base_t(BOOST_MOVE_BASE(base_t, x), a) 1725 {} 1726 1727 //! <b>Effects</b>: Makes *this a copy of x. 1728 //! 1729 //! <b>Complexity</b>: Linear in x.size(). 1730 inline multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x) 1731 { return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 1732 1733 //! <b>Effects</b>: this->swap(x.get()). 1734 //! 1735 //! <b>Complexity</b>: Constant. 1736 inline multimap& operator=(BOOST_RV_REF(multimap) x) 1737 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || 1738 allocator_traits_type::is_always_equal::value) && 1739 boost::container::dtl::is_nothrow_move_assignable<Compare>::value) 1740 { return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 1741 1742 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1743 //! <b>Effects</b>: Assign content of il to *this. 1744 //! 1745 inline multimap& operator=(std::initializer_list<value_type> il) 1746 { 1747 this->clear(); 1748 insert(il.begin(), il.end()); 1749 return *this; 1750 } 1751 #endif 1752 1753 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1754 1755 //! @copydoc ::boost::container::set::get_allocator() 1756 allocator_type get_allocator() const; 1757 1758 //! @copydoc ::boost::container::set::get_stored_allocator() 1759 stored_allocator_type &get_stored_allocator(); 1760 1761 //! @copydoc ::boost::container::set::get_stored_allocator() const 1762 const stored_allocator_type &get_stored_allocator() const; 1763 1764 //! @copydoc ::boost::container::set::begin() 1765 iterator begin(); 1766 1767 //! @copydoc ::boost::container::set::begin() const 1768 const_iterator begin() const; 1769 1770 //! @copydoc ::boost::container::set::cbegin() const 1771 const_iterator cbegin() const; 1772 1773 //! @copydoc ::boost::container::set::end() 1774 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 1775 1776 //! @copydoc ::boost::container::set::end() const 1777 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 1778 1779 //! @copydoc ::boost::container::set::cend() const 1780 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 1781 1782 //! @copydoc ::boost::container::set::rbegin() 1783 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 1784 1785 //! @copydoc ::boost::container::set::rbegin() const 1786 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 1787 1788 //! @copydoc ::boost::container::set::crbegin() const 1789 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 1790 1791 //! @copydoc ::boost::container::set::rend() 1792 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 1793 1794 //! @copydoc ::boost::container::set::rend() const 1795 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 1796 1797 //! @copydoc ::boost::container::set::crend() const 1798 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 1799 1800 //! @copydoc ::boost::container::set::empty() const 1801 bool empty() const; 1802 1803 //! @copydoc ::boost::container::set::size() const 1804 size_type size() const; 1805 1806 //! @copydoc ::boost::container::set::max_size() const 1807 size_type max_size() const; 1808 1809 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1810 1811 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1812 1813 //! <b>Effects</b>: Inserts an object of type T constructed with 1814 //! std::forward<Args>(args)... in the container. 1815 //! p is a hint pointing to where the insert should start to search. 1816 //! 1817 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1818 //! to the key of x. 1819 //! 1820 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1821 //! is inserted right before p. 1822 template <class... Args> 1823 inline iterator emplace(BOOST_FWD_REF(Args)... args) 1824 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); } 1825 1826 //! <b>Effects</b>: Inserts an object of type T constructed with 1827 //! std::forward<Args>(args)... in the container. 1828 //! p is a hint pointing to where the insert should start to search. 1829 //! 1830 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1831 //! to the key of x. 1832 //! 1833 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1834 //! is inserted right before p. 1835 template <class... Args> 1836 inline iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 1837 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); } 1838 1839 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1840 1841 #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \ 1842 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1843 inline iterator emplace(BOOST_MOVE_UREF##N)\ 1844 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\ 1845 \ 1846 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1847 inline iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1848 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 1849 // 1850 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE) 1851 #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE 1852 1853 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1854 1855 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the 1856 //! newly inserted element. 1857 //! 1858 //! <b>Complexity</b>: Logarithmic. 1859 inline iterator insert(const value_type& x) 1860 { return this->base_t::insert_equal_convertible(x); } 1861 1862 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns 1863 //! the iterator pointing to the newly inserted element. 1864 //! 1865 //! <b>Complexity</b>: Logarithmic. 1866 inline iterator insert(BOOST_RV_REF(value_type) x) 1867 { return this->base_t::insert_equal_convertible(boost::move(x)); } 1868 1869 //! <b>Effects</b>: Inserts a new value constructed from x and returns 1870 //! the iterator pointing to the newly inserted element. 1871 //! 1872 //! <b>Complexity</b>: Logarithmic. 1873 template<class Pair> 1874 inline BOOST_CONTAINER_DOC1ST 1875 ( iterator 1876 , typename dtl::enable_if_c< 1877 dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value || 1878 dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value 1879 BOOST_MOVE_I iterator >::type) 1880 insert(BOOST_FWD_REF(Pair) x) 1881 { return this->base_t::emplace_equal(boost::forward<Pair>(x)); } 1882 1883 //! <b>Effects</b>: Inserts a copy of x in the container. 1884 //! p is a hint pointing to where the insert should start to search. 1885 //! 1886 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1887 //! to the key of x. 1888 //! 1889 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1890 //! is inserted right before p. 1891 inline iterator insert(const_iterator p, const value_type& x) 1892 { return this->base_t::insert_equal_hint_convertible(p, x); } 1893 1894 //! <b>Effects</b>: Inserts a new value move constructed from x in the container. 1895 //! p is a hint pointing to where the insert should start to search. 1896 //! 1897 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1898 //! to the key of x. 1899 //! 1900 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1901 //! is inserted right before p. 1902 inline iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) 1903 { return this->base_t::insert_equal_hint_convertible(p, boost::move(x)); } 1904 1905 //! <b>Effects</b>: Inserts a new value constructed from x in the container. 1906 //! p is a hint pointing to where the insert should start to search. 1907 //! 1908 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1909 //! to the key of x. 1910 //! 1911 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1912 //! is inserted right before p. 1913 template<class Pair> 1914 inline BOOST_CONTAINER_DOC1ST 1915 ( iterator 1916 , typename dtl::enable_if_c< 1917 dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value || 1918 dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value 1919 BOOST_MOVE_I iterator>::type) 1920 insert(const_iterator p, BOOST_FWD_REF(Pair) x) 1921 { return this->base_t::emplace_hint_equal(p, boost::forward<Pair>(x)); } 1922 1923 //! <b>Requires</b>: first, last are not iterators into *this. 1924 //! 1925 //! <b>Effects</b>: inserts each element from the range [first,last) . 1926 //! 1927 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 1928 template <class InputIterator> 1929 inline void insert(InputIterator first, InputIterator last) 1930 { this->base_t::insert_equal_range(first, last); } 1931 1932 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1933 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end(). 1934 //! 1935 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end()) 1936 inline void insert(std::initializer_list<value_type> il) 1937 { this->base_t::insert_equal_range(il.begin(), il.end()); } 1938 #endif 1939 1940 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator(). 1941 //! 1942 //! <b>Effects/Returns</b>: If nh is empty, has no effect and returns end(). Otherwise, inserts 1943 //! the element owned by nh and returns an iterator pointing to the newly inserted element. 1944 //! If a range containing elements with keys equivalent to nh.key() exists, 1945 //! the element is inserted at the end of that range. nh is always emptied. 1946 //! 1947 //! <b>Complexity</b>: Logarithmic 1948 iterator insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1949 { 1950 typename base_t::node_type n(boost::move(nh)); 1951 return this->base_t::insert_equal_node(boost::move(n)); 1952 } 1953 1954 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible 1955 //! to the position just prior to "hint". 1956 //! 1957 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted 1958 //! right before "hint". 1959 iterator insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1960 { 1961 typename base_t::node_type n(boost::move(nh)); 1962 return this->base_t::insert_equal_node(hint, boost::move(n)); 1963 } 1964 1965 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1966 1967 //! @copydoc ::boost::container::set::erase(const_iterator) 1968 iterator erase(const_iterator p); 1969 1970 //! @copydoc ::boost::container::set::erase(const key_type&) 1971 size_type erase(const key_type& x); 1972 1973 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator) 1974 iterator erase(const_iterator first, const_iterator last); 1975 #endif 1976 1977 //! @copydoc ::boost::container::map::extract(const key_type&) 1978 node_type extract(const key_type& k) 1979 { 1980 typename base_t::node_type base_nh(this->base_t::extract(k)); 1981 return node_type(boost::move(base_nh)); 1982 } 1983 1984 //! @copydoc ::boost::container::map::extract(const_iterator) 1985 node_type extract(const_iterator position) 1986 { 1987 typename base_t::node_type base_nh(this->base_t::extract(position)); 1988 return node_type (boost::move(base_nh)); 1989 } 1990 1991 //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). 1992 //! 1993 //! <b>Effects</b>: Extracts each element in source and insert it into a using 1994 //! the comparison object of *this. 1995 //! 1996 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 1997 //! to those same elements but as members of *this. Iterators referring to the transferred 1998 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 1999 //! not into source. 2000 //! 2001 //! <b>Throws</b>: Nothing unless the comparison object throws. 2002 //! 2003 //! <b>Complexity</b>: N log(size() + N) (N has the value source.size()) 2004 template<class C2> 2005 inline void merge(multimap<Key, T, C2, Allocator, Options>& source) 2006 { 2007 typedef dtl::tree 2008 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 2009 this->base_t::merge_equal(static_cast<base2_t&>(source)); 2010 } 2011 2012 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&) 2013 template<class C2> 2014 inline void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 2015 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); } 2016 2017 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&) 2018 template<class C2> 2019 inline void merge(map<Key, T, C2, Allocator, Options>& source) 2020 { 2021 typedef dtl::tree 2022 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 2023 this->base_t::merge_equal(static_cast<base2_t&>(source)); 2024 } 2025 2026 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&) 2027 template<class C2> 2028 inline void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 2029 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); } 2030 2031 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2032 //! @copydoc ::boost::container::set::swap 2033 void swap(multiset& x) 2034 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 2035 && boost::container::dtl::is_nothrow_swappable<Compare>::value ); 2036 2037 //! @copydoc ::boost::container::set::clear 2038 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 2039 2040 //! @copydoc ::boost::container::set::key_comp 2041 key_compare key_comp() const; 2042 2043 //! @copydoc ::boost::container::set::value_comp 2044 value_compare value_comp() const; 2045 2046 //! <b>Returns</b>: An iterator pointing to an element with the key 2047 //! equivalent to x, or end() if such an element is not found. 2048 //! 2049 //! <b>Complexity</b>: Logarithmic. 2050 iterator find(const key_type& x); 2051 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. 2054 //! 2055 //! <b>Complexity</b>: Logarithmic. 2056 const_iterator find(const key_type& x) const; 2057 2058 //! <b>Requires</b>: This overload is available only if 2059 //! key_compare::is_transparent exists. 2060 //! 2061 //! <b>Returns</b>: An iterator pointing to an element with the key 2062 //! equivalent to x, or end() if such an element is not found. 2063 //! 2064 //! <b>Complexity</b>: Logarithmic. 2065 template<typename K> 2066 iterator find(const K& x); 2067 2068 //! <b>Requires</b>: This overload is available only if 2069 //! key_compare::is_transparent exists. 2070 //! 2071 //! <b>Returns</b>: A const_iterator pointing to an element with the key 2072 //! equivalent to x, or end() if such an element is not found. 2073 //! 2074 //! <b>Complexity</b>: Logarithmic. 2075 template<typename K> 2076 const_iterator find(const K& x) const; 2077 2078 //! <b>Returns</b>: The number of elements with key equivalent to x. 2079 //! 2080 //! <b>Complexity</b>: log(size())+count(k) 2081 size_type count(const key_type& x) const; 2082 2083 //! <b>Requires</b>: This overload is available only if 2084 //! key_compare::is_transparent exists. 2085 //! 2086 //! <b>Returns</b>: The number of elements with key equivalent to x. 2087 //! 2088 //! <b>Complexity</b>: log(size())+count(k) 2089 template<typename K> 2090 size_type count(const K& x) const; 2091 2092 //! <b>Returns</b>: Returns true if there is an element with key 2093 //! equivalent to key in the container, otherwise false. 2094 //! 2095 //! <b>Complexity</b>: log(size()). 2096 bool contains(const key_type& x) const; 2097 2098 //! <b>Requires</b>: This overload is available only if 2099 //! key_compare::is_transparent exists. 2100 //! 2101 //! <b>Returns</b>: Returns true if there is an element with key 2102 //! equivalent to key in the container, otherwise false. 2103 //! 2104 //! <b>Complexity</b>: log(size()). 2105 template<typename K> 2106 bool contains(const K& x) const; 2107 2108 //! <b>Returns</b>: An iterator pointing to the first element with key not less 2109 //! than x, or end() if such an element is not found. 2110 //! 2111 //! <b>Complexity</b>: Logarithmic 2112 iterator lower_bound(const key_type& x); 2113 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. 2116 //! 2117 //! <b>Complexity</b>: Logarithmic 2118 const_iterator lower_bound(const key_type& x) const; 2119 2120 //! <b>Requires</b>: This overload is available only if 2121 //! key_compare::is_transparent exists. 2122 //! 2123 //! <b>Returns</b>: An iterator pointing to the first element with key not less 2124 //! than x, or end() if such an element is not found. 2125 //! 2126 //! <b>Complexity</b>: Logarithmic 2127 template<typename K> 2128 iterator lower_bound(const K& x); 2129 2130 //! <b>Requires</b>: This overload is available only if 2131 //! key_compare::is_transparent exists. 2132 //! 2133 //! <b>Returns</b>: A const iterator pointing to the first element with key not 2134 //! less than x, or end() if such an element is not found. 2135 //! 2136 //! <b>Complexity</b>: Logarithmic 2137 template<typename K> 2138 const_iterator lower_bound(const K& x) const; 2139 2140 //! <b>Returns</b>: An iterator pointing to the first element with key greater 2141 //! than x, or end() if such an element is not found. 2142 //! 2143 //! <b>Complexity</b>: Logarithmic 2144 iterator upper_bound(const key_type& x); 2145 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. 2148 //! 2149 //! <b>Complexity</b>: Logarithmic 2150 const_iterator upper_bound(const key_type& x) const; 2151 2152 //! <b>Requires</b>: This overload is available only if 2153 //! key_compare::is_transparent exists. 2154 //! 2155 //! <b>Returns</b>: An iterator pointing to the first element with key greater 2156 //! than x, or end() if such an element is not found. 2157 //! 2158 //! <b>Complexity</b>: Logarithmic 2159 template<typename K> 2160 iterator upper_bound(const K& x); 2161 2162 //! <b>Requires</b>: This overload is available only if 2163 //! key_compare::is_transparent exists. 2164 //! 2165 //! <b>Returns</b>: A const iterator pointing to the first element with key 2166 //! greater than x, or end() if such an element is not found. 2167 //! 2168 //! <b>Complexity</b>: Logarithmic 2169 template<typename K> 2170 const_iterator upper_bound(const K& x) const; 2171 2172 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2173 //! 2174 //! <b>Complexity</b>: Logarithmic 2175 std::pair<iterator,iterator> equal_range(const key_type& x); 2176 2177 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2178 //! 2179 //! <b>Complexity</b>: Logarithmic 2180 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; 2181 2182 //! <b>Requires</b>: This overload is available only if 2183 //! key_compare::is_transparent exists. 2184 //! 2185 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2186 //! 2187 //! <b>Complexity</b>: Logarithmic 2188 template<typename K> 2189 std::pair<iterator,iterator> equal_range(const K& x); 2190 2191 //! <b>Requires</b>: This overload is available only if 2192 //! key_compare::is_transparent exists. 2193 //! 2194 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2195 //! 2196 //! <b>Complexity</b>: Logarithmic 2197 template<typename K> 2198 std::pair<const_iterator,const_iterator> equal_range(const K& x) const; 2199 2200 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 2201 //! 2202 //! <b>Complexity</b>: Linear 2203 void rebalance(); 2204 2205 //! <b>Effects</b>: Returns true if x and y are equal 2206 //! 2207 //! <b>Complexity</b>: Linear to the number of elements in the container. 2208 friend bool operator==(const multimap& x, const multimap& y); 2209 2210 //! <b>Effects</b>: Returns true if x and y are unequal 2211 //! 2212 //! <b>Complexity</b>: Linear to the number of elements in the container. 2213 friend bool operator!=(const multimap& x, const multimap& y); 2214 2215 //! <b>Effects</b>: Returns true if x is less than y 2216 //! 2217 //! <b>Complexity</b>: Linear to the number of elements in the container. 2218 friend bool operator<(const multimap& x, const multimap& y); 2219 2220 //! <b>Effects</b>: Returns true if x is greater than y 2221 //! 2222 //! <b>Complexity</b>: Linear to the number of elements in the container. 2223 friend bool operator>(const multimap& x, const multimap& y); 2224 2225 //! <b>Effects</b>: Returns true if x is equal or less than y 2226 //! 2227 //! <b>Complexity</b>: Linear to the number of elements in the container. 2228 friend bool operator<=(const multimap& x, const multimap& y); 2229 2230 //! <b>Effects</b>: Returns true if x is equal or greater than y 2231 //! 2232 //! <b>Complexity</b>: Linear to the number of elements in the container. 2233 friend bool operator>=(const multimap& x, const multimap& y); 2234 2235 //! <b>Effects</b>: x.swap(y) 2236 //! 2237 //! <b>Complexity</b>: Constant. 2238 friend void swap(multimap& x, multimap& y) 2239 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 2240 && boost::container::dtl::is_nothrow_swappable<Compare>::value ); 2241 2242 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2243 }; 2244 2245 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 2246 2247 template <typename InputIterator> 2248 multimap(InputIterator, InputIterator) -> 2249 multimap< it_based_non_const_first_type_t<InputIterator> 2250 , it_based_second_type_t<InputIterator>>; 2251 2252 template < typename InputIterator, typename AllocatorOrCompare> 2253 multimap(InputIterator, InputIterator, AllocatorOrCompare const&) -> 2254 multimap< it_based_non_const_first_type_t<InputIterator> 2255 , it_based_second_type_t<InputIterator> 2256 , typename dtl::if_c< // Compare 2257 dtl::is_allocator<AllocatorOrCompare>::value 2258 , std::less<it_based_non_const_first_type_t<InputIterator>> 2259 , AllocatorOrCompare 2260 >::type 2261 , typename dtl::if_c< // Allocator 2262 dtl::is_allocator<AllocatorOrCompare>::value 2263 , AllocatorOrCompare 2264 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 2265 >::type 2266 >; 2267 2268 template < typename InputIterator, typename Compare, typename Allocator 2269 , typename = dtl::require_nonallocator_t<Compare> 2270 , typename = dtl::require_allocator_t<Allocator>> 2271 multimap(InputIterator, InputIterator, Compare const&, Allocator const&) -> 2272 multimap< it_based_non_const_first_type_t<InputIterator> 2273 , it_based_second_type_t<InputIterator> 2274 , Compare 2275 , Allocator>; 2276 2277 template <typename InputIterator> 2278 multimap(ordered_range_t, InputIterator, InputIterator) -> 2279 multimap< it_based_non_const_first_type_t<InputIterator> 2280 , it_based_second_type_t<InputIterator>>; 2281 2282 template < typename InputIterator, typename AllocatorOrCompare> 2283 multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) -> 2284 multimap< it_based_non_const_first_type_t<InputIterator> 2285 , it_based_second_type_t<InputIterator> 2286 , typename dtl::if_c< // Compare 2287 dtl::is_allocator<AllocatorOrCompare>::value 2288 , std::less<it_based_const_first_type_t<InputIterator>> 2289 , AllocatorOrCompare 2290 >::type 2291 , typename dtl::if_c< // Allocator 2292 dtl::is_allocator<AllocatorOrCompare>::value 2293 , AllocatorOrCompare 2294 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 2295 >::type 2296 >; 2297 2298 template < typename InputIterator, typename Compare, typename Allocator 2299 , typename = dtl::require_nonallocator_t<Compare> 2300 , typename = dtl::require_allocator_t<Allocator>> 2301 multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) -> 2302 multimap< it_based_non_const_first_type_t<InputIterator> 2303 , it_based_second_type_t<InputIterator> 2304 , Compare 2305 , Allocator>; 2306 #endif 2307 2308 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2309 2310 } //namespace container { 2311 2312 //!has_trivial_destructor_after_move<> == true_type 2313 //!specialization for optimizations 2314 template <class Key, class T, class Compare, class Allocator, class Options> 2315 struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator, Options> > 2316 { 2317 typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree; 2318 BOOST_STATIC_CONSTEXPR bool value = ::boost::has_trivial_destructor_after_move<tree>::value; 2319 }; 2320 2321 namespace container { 2322 2323 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2324 2325 }} 2326 2327 #include <boost/container/detail/config_end.hpp> 2328 2329 #endif // BOOST_CONTAINER_MAP_HPP 2330
[ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
![]() ![]() |