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