1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost 4 // Software License, Version 1.0. (See accompanying file 5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 // 7 // See http://www.boost.org/libs/container for documentation. 8 // 9 ////////////////////////////////////////////////////////////////////////////// 10 #ifndef BOOST_CONTAINER_MAP_HPP 11 #define BOOST_CONTAINER_MAP_HPP 12 13 #ifndef BOOST_CONFIG_HPP 14 # include <boost/config.hpp> 15 #endif 16 17 #if defined(BOOST_HAS_PRAGMA_ONCE) 18 # pragma once 19 #endif 20 21 #include <boost/container/detail/config_begin.hpp> 22 #include <boost/container/detail/workaround.hpp> 23 24 // container 25 #include <boost/container/container_fwd.hpp> 26 #include <boost/container/new_allocator.hpp> //new_allocator 27 #include <boost/container/throw_exception.hpp> 28 // container/detail 29 #include <boost/container/detail/mpl.hpp> 30 #include <boost/container/detail/tree.hpp> 31 #include <boost/container/detail/type_traits.hpp> 32 #include <boost/container/detail/value_init.hpp> 33 #include <boost/container/detail/pair.hpp> 34 #include <boost/container/detail/pair_key_mapped_of_value.hpp> 35 36 // move 37 #include <boost/move/traits.hpp> 38 #include <boost/move/utility_core.hpp> 39 // move/detail 40 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 41 #include <boost/move/detail/fwd_macros.hpp> 42 #endif 43 #include <boost/move/detail/move_helpers.hpp> 44 // intrusive/detail 45 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair 46 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal 47 // other 48 #include <boost/static_assert.hpp> 49 #include <boost/core/no_exceptions_support.hpp> 50 // std 51 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 52 #include <initializer_list> 53 #endif 54 55 namespace boost { 56 namespace container { 57 58 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 59 60 //! A map is a kind of associative container that supports unique keys (contains at 61 //! most one of each key value) and provides for fast retrieval of values of another 62 //! type T based on the keys. The map class supports bidirectional iterators. 63 //! 64 //! A map satisfies all of the requirements of a container and of a reversible 65 //! container and of an associative container. The <code>value_type</code> stored 66 //! by this container is the value_type is std::pair<const Key, T>. 67 //! 68 //! \tparam Key is the key_type of the map 69 //! \tparam T is the <code>mapped_type</code> 70 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). 71 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s 72 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>). 73 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options. 74 template < class Key, class T, class Compare = std::less<Key> 75 , class Allocator = void, class Options = tree_assoc_defaults > 76 #else 77 template <class Key, class T, class Compare, class Allocator, class Options> 78 #endif 79 class map 80 ///@cond 81 : public dtl::tree 82 < std::pair<const Key, T> 83 , int 84 , Compare, Allocator, Options> 85 ///@endcond 86 { 87 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 88 private: 89 BOOST_COPYABLE_AND_MOVABLE(map) 90 91 typedef int select_1st_t; 92 typedef std::pair<const Key, T> value_type_impl; 93 typedef dtl::tree 94 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t; 95 typedef dtl::pair <Key, T> movable_value_type_impl; 96 typedef typename base_t::value_compare value_compare_impl; 97 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 98 99 public: 100 ////////////////////////////////////////////// 101 // 102 // types 103 // 104 ////////////////////////////////////////////// 105 106 typedef Key key_type; 107 typedef T mapped_type; 108 typedef typename base_t::allocator_type allocator_type; 109 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type; 110 typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type; 111 typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer; 112 typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer; 113 typedef typename boost::container::allocator_traits<allocator_type>::reference reference; 114 typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference; 115 typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type; 116 typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_type; 117 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 118 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; 119 typedef Compare key_compare; 120 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 121 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 122 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 123 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 124 typedef std::pair<key_type, mapped_type> nonconst_value_type; 125 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; 126 typedef BOOST_CONTAINER_IMPDEF(node_handle< 127 typename base_t::stored_allocator_type 128 BOOST_MOVE_I pair_key_mapped_of_value 129 <key_type BOOST_MOVE_I mapped_type> >) node_type; 130 typedef BOOST_CONTAINER_IMPDEF 131 (insert_return_type_base<iterator BOOST_MOVE_I node_type>) insert_return_type; 132 133 //allocator_type::value_type type must be std::pair<CONST Key, T> 134 BOOST_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value)); 135 136 ////////////////////////////////////////////// 137 // 138 // construct/copy/destroy 139 // 140 ////////////////////////////////////////////// 141 142 //! <b>Effects</b>: Default constructs an empty map. 143 //! 144 //! <b>Complexity</b>: Constant. 145 BOOST_CONTAINER_FORCEINLINE map()146 map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value && 147 dtl::is_nothrow_default_constructible<Compare>::value) 148 : base_t() 149 {} 150 151 //! <b>Effects</b>: Constructs an empty map using the specified comparison object 152 //! and allocator. 153 //! 154 //! <b>Complexity</b>: Constant. map(const Compare & comp,const allocator_type & a)155 BOOST_CONTAINER_FORCEINLINE map(const Compare& comp, const allocator_type& a) 156 : base_t(comp, a) 157 {} 158 159 //! <b>Effects</b>: Constructs an empty map using the specified comparison object. 160 //! 161 //! <b>Complexity</b>: Constant. map(const Compare & comp)162 BOOST_CONTAINER_FORCEINLINE explicit map(const Compare& comp) 163 : base_t(comp) 164 {} 165 166 //! <b>Effects</b>: Constructs an empty map using the specified allocator. 167 //! 168 //! <b>Complexity</b>: Constant. map(const allocator_type & a)169 BOOST_CONTAINER_FORCEINLINE explicit map(const allocator_type& a) 170 : base_t(a) 171 {} 172 173 //! <b>Effects</b>: Constructs an empty map and 174 //! inserts elements from the range [first ,last ). 175 //! 176 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 177 //! the predicate and otherwise N logN, where N is last - first. 178 template <class InputIterator> map(InputIterator first,InputIterator last)179 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last) 180 : base_t(true, first, last) 181 {} 182 183 //! <b>Effects</b>: Constructs an empty map using the specified 184 //! allocator, and inserts elements from the range [first ,last ). 185 //! 186 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 187 //! the predicate and otherwise N logN, where N is last - first. 188 template <class InputIterator> map(InputIterator first,InputIterator last,const allocator_type & a)189 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const allocator_type& a) 190 : base_t(true, first, last, Compare(), a) 191 {} 192 193 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 194 //! inserts elements from the range [first ,last ). 195 //! 196 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 197 //! the predicate and otherwise N logN, where N is last - first. 198 template <class InputIterator> map(InputIterator first,InputIterator last,const Compare & comp)199 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const Compare& comp) 200 : base_t(true, first, last, comp) 201 {} 202 203 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 204 //! allocator, and inserts elements from the range [first ,last ). 205 //! 206 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 207 //! the predicate and otherwise N logN, where N is last - first. 208 template <class InputIterator> map(InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)209 BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a) 210 : base_t(true, first, last, comp, a) 211 {} 212 213 //! <b>Effects</b>: Constructs an empty map and 214 //! inserts elements from the ordered unique range [first ,last). This function 215 //! is more efficient than the normal range creation for ordered ranges. 216 //! 217 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 218 //! unique values. 219 //! 220 //! <b>Complexity</b>: Linear in N. 221 //! 222 //! <b>Note</b>: Non-standard extension. 223 template <class InputIterator> map(ordered_unique_range_t,InputIterator first,InputIterator last)224 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last) 225 : base_t(ordered_range, first, last) 226 {} 227 228 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 229 //! inserts elements from the ordered unique range [first ,last). This function 230 //! is more efficient than the normal range creation for ordered ranges. 231 //! 232 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 233 //! unique values. 234 //! 235 //! <b>Complexity</b>: Linear in N. 236 //! 237 //! <b>Note</b>: Non-standard extension. 238 template <class InputIterator> map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp)239 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp) 240 : base_t(ordered_range, first, last, comp) 241 {} 242 243 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 244 //! allocator, and inserts elements from the ordered unique range [first ,last). This function 245 //! is more efficient than the normal range creation for ordered ranges. 246 //! 247 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 248 //! unique values. 249 //! 250 //! <b>Complexity</b>: Linear in N. 251 //! 252 //! <b>Note</b>: Non-standard extension. 253 template <class InputIterator> map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)254 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last 255 , const Compare& comp, const allocator_type& a) 256 : base_t(ordered_range, first, last, comp, a) 257 {} 258 259 //! <b>Effects</b>: Constructs an empty map using the specified allocator object and 260 //! inserts elements from the ordered unique range [first ,last). This function 261 //! is more efficient than the normal range creation for ordered ranges. 262 //! 263 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 264 //! unique values. 265 //! 266 //! <b>Complexity</b>: Linear in N. 267 //! 268 //! <b>Note</b>: Non-standard extension. 269 template <class InputIterator> map(ordered_unique_range_t,InputIterator first,InputIterator last,const allocator_type & a)270 BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a) 271 : base_t(ordered_range, first, last, Compare(), a) 272 {} 273 274 275 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 276 //! <b>Effects</b>: Constructs an empty map and 277 //! inserts elements from the range [il.begin(), il.end()). 278 //! 279 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted according 280 //! to the predicate and otherwise N logN, where N is il.first() - il.end(). map(std::initializer_list<value_type> il)281 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il) 282 : base_t(true, il.begin(), il.end()) 283 {} 284 285 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 286 //! inserts elements from the range [il.begin(), il.end()). 287 //! 288 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 289 //! the predicate and otherwise N logN, where N is il.first() - il.end(). map(std::initializer_list<value_type> il,const Compare & comp)290 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const Compare& comp) 291 : base_t(true, il.begin(), il.end(), comp) 292 {} 293 294 //! <b>Effects</b>: Constructs an empty map using the specified 295 //! allocator, and inserts elements from the range [il.begin(), il.end()). 296 //! 297 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 298 //! the predicate and otherwise N logN, where N is il.first() - il.end(). map(std::initializer_list<value_type> il,const allocator_type & a)299 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const allocator_type& a) 300 : base_t(true, il.begin(), il.end(), Compare(), a) 301 {} 302 303 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 304 //! allocator, and inserts elements from the range [il.begin(), il.end()). 305 //! 306 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 307 //! the predicate and otherwise N logN, where N is il.first() - il.end(). map(std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)308 BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) 309 : base_t(true, il.begin(), il.end(), comp, a) 310 {} 311 312 //! <b>Effects</b>: Constructs an empty map and inserts elements from the ordered unique range [il.begin(), il.end()). 313 //! This function is more efficient than the normal range creation for ordered ranges. 314 //! 315 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 316 //! unique values. 317 //! 318 //! <b>Complexity</b>: Linear in N. 319 //! 320 //! <b>Note</b>: Non-standard extension. map(ordered_unique_range_t,std::initializer_list<value_type> il)321 BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, std::initializer_list<value_type> il) 322 : base_t(ordered_range, il.begin(), il.end()) 323 {} 324 325 //! <b>Effects</b>: Constructs an empty map using the specified comparison object, 326 //! and inserts elements from the ordered unique range [il.begin(), il.end()). This function 327 //! is more efficient than the normal range creation for ordered ranges. 328 //! 329 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 330 //! unique values. 331 //! 332 //! <b>Complexity</b>: Linear in N. 333 //! 334 //! <b>Note</b>: Non-standard extension. map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp)335 BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp) 336 : base_t(ordered_range, il.begin(), il.end(), comp) 337 {} 338 339 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 340 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function 341 //! is more efficient than the normal range creation for ordered ranges. 342 //! 343 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 344 //! unique values. 345 //! 346 //! <b>Complexity</b>: Linear in N. 347 //! 348 //! <b>Note</b>: Non-standard extension. map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)349 BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, std::initializer_list<value_type> il 350 , const Compare& comp, const allocator_type& a) 351 : base_t(ordered_range, il.begin(), il.end(), comp, a) 352 {} 353 354 #endif 355 356 //! <b>Effects</b>: Copy constructs a map. 357 //! 358 //! <b>Complexity</b>: Linear in x.size(). map(const map & x)359 BOOST_CONTAINER_FORCEINLINE map(const map& x) 360 : base_t(static_cast<const base_t&>(x)) 361 {} 362 363 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources. 364 //! 365 //! <b>Complexity</b>: Constant. 366 //! 367 //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF (map)x)368 BOOST_CONTAINER_FORCEINLINE map(BOOST_RV_REF(map) x) 369 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) 370 : base_t(BOOST_MOVE_BASE(base_t, x)) 371 {} 372 373 //! <b>Effects</b>: Copy constructs a map using the specified allocator. 374 //! 375 //! <b>Complexity</b>: Linear in x.size(). map(const map & x,const allocator_type & a)376 BOOST_CONTAINER_FORCEINLINE map(const map& x, const allocator_type &a) 377 : base_t(static_cast<const base_t&>(x), a) 378 {} 379 380 //! <b>Effects</b>: Move constructs a map using the specified allocator. 381 //! Constructs *this using x's resources. 382 //! 383 //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise. 384 //! 385 //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF (map)x,const allocator_type & a)386 BOOST_CONTAINER_FORCEINLINE map(BOOST_RV_REF(map) x, const allocator_type &a) 387 : base_t(BOOST_MOVE_BASE(base_t, x), a) 388 {} 389 390 //! <b>Effects</b>: Makes *this a copy of x. 391 //! 392 //! <b>Complexity</b>: Linear in x.size(). operator =(BOOST_COPY_ASSIGN_REF (map)x)393 BOOST_CONTAINER_FORCEINLINE map& operator=(BOOST_COPY_ASSIGN_REF(map) x) 394 { return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 395 396 //! <b>Effects</b>: this->swap(x.get()). 397 //! 398 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 399 //! is false and (allocation throws or value_type's move constructor throws) 400 //! 401 //! <b>Complexity</b>: Constant if allocator_traits_type:: 402 //! propagate_on_container_move_assignment is true or 403 //! this->get>allocator() == x.get_allocator(). Linear otherwise. operator =(BOOST_RV_REF (map)x)404 BOOST_CONTAINER_FORCEINLINE map& operator=(BOOST_RV_REF(map) x) 405 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || 406 allocator_traits_type::is_always_equal::value) && 407 boost::container::dtl::is_nothrow_move_assignable<Compare>::value) 408 { return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 409 410 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 411 //! <b>Effects</b>: Assign content of il to *this. 412 //! operator =(std::initializer_list<value_type> il)413 BOOST_CONTAINER_FORCEINLINE map& operator=(std::initializer_list<value_type> il) 414 { 415 this->clear(); 416 insert(il.begin(), il.end()); 417 return *this; 418 } 419 #endif 420 421 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 422 423 //! <b>Effects</b>: Returns a copy of the allocator that 424 //! was passed to the object's constructor. 425 //! 426 //! <b>Complexity</b>: Constant. 427 allocator_type get_allocator() const; 428 429 //! <b>Effects</b>: Returns a reference to the internal allocator. 430 //! 431 //! <b>Throws</b>: Nothing 432 //! 433 //! <b>Complexity</b>: Constant. 434 //! 435 //! <b>Note</b>: Non-standard extension. 436 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW; 437 438 //! <b>Effects</b>: Returns a reference to the internal allocator. 439 //! 440 //! <b>Throws</b>: Nothing 441 //! 442 //! <b>Complexity</b>: Constant. 443 //! 444 //! <b>Note</b>: Non-standard extension. 445 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW; 446 447 //! <b>Effects</b>: Returns an iterator to the first element contained in the container. 448 //! 449 //! <b>Throws</b>: Nothing. 450 //! 451 //! <b>Complexity</b>: Constant. 452 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW; 453 454 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 455 //! 456 //! <b>Throws</b>: Nothing. 457 //! 458 //! <b>Complexity</b>: Constant. 459 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW; 460 461 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 462 //! 463 //! <b>Throws</b>: Nothing. 464 //! 465 //! <b>Complexity</b>: Constant. 466 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 467 468 //! <b>Effects</b>: Returns an iterator to the end of the container. 469 //! 470 //! <b>Throws</b>: Nothing. 471 //! 472 //! <b>Complexity</b>: Constant. 473 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 474 475 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 476 //! 477 //! <b>Throws</b>: Nothing. 478 //! 479 //! <b>Complexity</b>: Constant. 480 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 481 482 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 483 //! 484 //! <b>Throws</b>: Nothing. 485 //! 486 //! <b>Complexity</b>: Constant. 487 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 488 489 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 490 //! of the reversed container. 491 //! 492 //! <b>Throws</b>: Nothing. 493 //! 494 //! <b>Complexity</b>: Constant. 495 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 496 497 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 498 //! of the reversed container. 499 //! 500 //! <b>Throws</b>: Nothing. 501 //! 502 //! <b>Complexity</b>: Constant. 503 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 504 505 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 506 //! of the reversed container. 507 //! 508 //! <b>Throws</b>: Nothing. 509 //! 510 //! <b>Complexity</b>: Constant. 511 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 512 513 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 514 //! of the reversed container. 515 //! 516 //! <b>Throws</b>: Nothing. 517 //! 518 //! <b>Complexity</b>: Constant. 519 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 520 521 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 522 //! of the reversed container. 523 //! 524 //! <b>Throws</b>: Nothing. 525 //! 526 //! <b>Complexity</b>: Constant. 527 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 528 529 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 530 //! of the reversed container. 531 //! 532 //! <b>Throws</b>: Nothing. 533 //! 534 //! <b>Complexity</b>: Constant. 535 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 536 537 //! <b>Effects</b>: Returns true if the container contains no elements. 538 //! 539 //! <b>Throws</b>: Nothing. 540 //! 541 //! <b>Complexity</b>: Constant. 542 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW; 543 544 //! <b>Effects</b>: Returns the number of the elements contained in the container. 545 //! 546 //! <b>Throws</b>: Nothing. 547 //! 548 //! <b>Complexity</b>: Constant. 549 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW; 550 551 //! <b>Effects</b>: Returns the largest possible size of the container. 552 //! 553 //! <b>Throws</b>: Nothing. 554 //! 555 //! <b>Complexity</b>: Constant. 556 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW; 557 558 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 559 560 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 561 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts 562 //! value_type(x, T()) into the map. 563 //! 564 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this. 565 //! 566 //! <b>Complexity</b>: Logarithmic. 567 mapped_type& operator[](const key_type &k); 568 569 //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts 570 //! value_type(boost::move(x), T()) into the map (the key is move-constructed) 571 //! 572 //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this. 573 //! 574 //! <b>Complexity</b>: Logarithmic. 575 mapped_type& operator[](key_type &&k); 576 #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) 577 //in compilers like GCC 3.4, we can't catch temporaries operator [](const key_type & k)578 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); } operator [](BOOST_RV_REF (key_type)k)579 BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); } 580 #else 581 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) 582 #endif 583 584 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 585 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 586 //! as if by insert, constructing it from value_type(k, forward<M>(obj)). 587 //! 588 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 589 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 590 //! references obtained to that element before it was extracted become valid. 591 //! 592 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 593 //! took place. The iterator component is pointing at the element that was inserted or updated. 594 //! 595 //! <b>Complexity</b>: Logarithmic in the size of the container. 596 template <class M> insert_or_assign(const key_type & k,BOOST_FWD_REF (M)obj)597 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj) 598 { return this->base_t::insert_or_assign(const_iterator(), k, ::boost::forward<M>(obj)); } 599 600 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 601 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 602 //! as if by insert, constructing it from value_type(k, move(obj)). 603 //! 604 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 605 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 606 //! references obtained to that element before it was extracted become valid. 607 //! 608 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 609 //! took place. The iterator component is pointing at the element that was inserted or updated. 610 //! 611 //! <b>Complexity</b>: Logarithmic in the size of the container. 612 template <class M> insert_or_assign(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)613 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) 614 { return this->base_t::insert_or_assign(const_iterator(), ::boost::move(k), ::boost::forward<M>(obj)); } 615 616 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 617 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 618 //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element 619 //! to the container as close as possible to the position just before hint. 620 //! 621 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 622 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 623 //! references obtained to that element before it was extracted become valid. 624 //! 625 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 626 //! took place. The iterator component is pointing at the element that was inserted or updated. 627 //! 628 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if 629 //! the new element is inserted just before hint. 630 template <class M> insert_or_assign(const_iterator hint,const key_type & k,BOOST_FWD_REF (M)obj)631 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj) 632 { return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)).first; } 633 634 //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj) 635 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value 636 //! as if by insert, constructing it from value_type(k, move(obj)) and the new element 637 //! to the container as close as possible to the position just before hint. 638 //! 639 //! No iterators or references are invalidated. If the insertion is successful, pointers and references 640 //! to the element obtained while it is held in the node handle are invalidated, and pointers and 641 //! references obtained to that element before it was extracted become valid. 642 //! 643 //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment 644 //! took place. The iterator component is pointing at the element that was inserted or updated. 645 //! 646 //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if 647 //! the new element is inserted just before hint. 648 template <class M> insert_or_assign(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)649 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) 650 { return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)).first; } 651 652 //! <b>Returns</b>: A reference to the element whose key is equivalent to x. 653 //! Throws: An exception object of type out_of_range if no such element is present. 654 //! <b>Complexity</b>: logarithmic. at(const key_type & k)655 T& at(const key_type& k) 656 { 657 iterator i = this->find(k); 658 if(i == this->end()){ 659 throw_out_of_range("map::at key not found"); 660 } 661 return i->second; 662 } 663 664 //! <b>Returns</b>: A reference to the element whose key is equivalent to x. 665 //! Throws: An exception object of type out_of_range if no such element is present. 666 //! <b>Complexity</b>: logarithmic. at(const key_type & k) const667 const T& at(const key_type& k) const 668 { 669 const_iterator i = this->find(k); 670 if(i == this->end()){ 671 throw_out_of_range("map::at key not found"); 672 } 673 return i->second; 674 } 675 676 ////////////////////////////////////////////// 677 // 678 // modifiers 679 // 680 ////////////////////////////////////////////// 681 682 //! <b>Effects</b>: Inserts x if and only if there is no element in the container 683 //! with key equivalent to the key of x. 684 //! 685 //! <b>Returns</b>: The bool component of the returned pair is true if and only 686 //! if the insertion takes place, and the iterator component of the pair 687 //! points to the element with key equivalent to the key of x. 688 //! 689 //! <b>Complexity</b>: Logarithmic. insert(const value_type & x)690 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x) 691 { return this->base_t::insert_unique(x); } 692 693 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if 694 //! there is no element in the container with key equivalent to the key of x. 695 //! 696 //! <b>Returns</b>: The bool component of the returned pair is true if and only 697 //! if the insertion takes place, and the iterator component of the pair 698 //! points to the element with key equivalent to the key of x. 699 //! 700 //! <b>Complexity</b>: Logarithmic. insert(const nonconst_value_type & x)701 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const nonconst_value_type& x) 702 { return this->try_emplace(x.first, x.second); } 703 704 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and 705 //! only if there is no element in the container with key equivalent to the key of x. 706 //! 707 //! <b>Returns</b>: The bool component of the returned pair is true if and only 708 //! if the insertion takes place, and the iterator component of the pair 709 //! points to the element with key equivalent to the key of x. 710 //! 711 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (nonconst_value_type)x)712 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x) 713 { return this->try_emplace(boost::move(x.first), boost::move(x.second)); } 714 715 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and 716 //! only if there is no element in the container with key equivalent to the key of x. 717 //! 718 //! <b>Returns</b>: The bool component of the returned pair is true if and only 719 //! if the insertion takes place, and the iterator component of the pair 720 //! points to the element with key equivalent to the key of x. 721 //! 722 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (movable_value_type)x)723 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x) 724 { return this->try_emplace(boost::move(x.first), boost::move(x.second)); } 725 726 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 727 //! no element in the container with key equivalent to the key of x. 728 //! 729 //! <b>Returns</b>: The bool component of the returned pair is true if and only 730 //! if the insertion takes place, and the iterator component of the pair 731 //! points to the element with key equivalent to the key of x. 732 //! 733 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (value_type)x)734 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) 735 { return this->base_t::insert_unique(boost::move(x)); } 736 737 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is 738 //! no element in the container with key equivalent to the key of x. 739 //! p is a hint pointing to where the insert should start to search. 740 //! 741 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 742 //! to the key of x. 743 //! 744 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 745 //! is inserted right before p. insert(const_iterator p,const value_type & x)746 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x) 747 { return this->base_t::insert_unique(p, x); } 748 749 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 750 //! no element in the container with key equivalent to the key of x. 751 //! p is a hint pointing to where the insert should start to search. 752 //! 753 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 754 //! to the key of x. 755 //! 756 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 757 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (nonconst_value_type)x)758 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) 759 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); } 760 761 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 762 //! no element in the container with key equivalent to the key of x. 763 //! p is a hint pointing to where the insert should start to search. 764 //! 765 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 766 //! to the key of x. 767 //! 768 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 769 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)770 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) 771 { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); } 772 773 //! <b>Effects</b>: Inserts a copy of x in the container. 774 //! p is a hint pointing to where the insert should start to search. 775 //! 776 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 777 //! 778 //! <b>Complexity</b>: Logarithmic. insert(const_iterator p,const nonconst_value_type & x)779 iterator insert(const_iterator p, const nonconst_value_type& x) 780 { return this->try_emplace(p, x.first, x.second); } 781 782 //! <b>Effects</b>: Inserts an element move constructed from x in the container. 783 //! p is a hint pointing to where the insert should start to search. 784 //! 785 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 786 //! 787 //! <b>Complexity</b>: Logarithmic. insert(const_iterator p,BOOST_RV_REF (value_type)x)788 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) 789 { return this->base_t::insert_unique(p, boost::move(x)); } 790 791 //! <b>Requires</b>: first, last are not iterators into *this. 792 //! 793 //! <b>Effects</b>: inserts each element from the range [first,last) if and only 794 //! if there is no element with key equivalent to the key of that element. 795 //! 796 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 797 template <class InputIterator> insert(InputIterator first,InputIterator last)798 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last) 799 { this->base_t::insert_unique(first, last); } 800 801 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 802 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only 803 //! if there is no element with key equivalent to the key of that element. 804 //! 805 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end()) insert(std::initializer_list<value_type> il)806 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il) 807 { this->base_t::insert_unique(il.begin(), il.end()); } 808 #endif 809 810 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator(). 811 //! 812 //! <b>Effects</b>: If nh is empty, has no effect. Otherwise, inserts the element owned 813 //! by nh if and only if there is no element in the container with a key equivalent to nh.key(). 814 //! 815 //! <b>Returns</b>: If nh is empty, insert_return_type.inserted is false, insert_return_type.position 816 //! is end(), and insert_return_type.node is empty. Otherwise if the insertion took place, 817 //! insert_return_type.inserted is true, insert_return_type.position points to the inserted element, 818 //! and insert_return_type.node is empty; if the insertion failed, insert_return_type.inserted is 819 //! false, insert_return_type.node has the previous value of nh, and insert_return_type.position 820 //! points to an element with a key equivalent to nh.key(). 821 //! 822 //! <b>Complexity</b>: Logarithmic insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)823 insert_return_type insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 824 { 825 typename base_t::node_type n(boost::move(nh)); 826 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(boost::move(n))); 827 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node)); 828 } 829 830 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible 831 //! to the position just prior to "hint". 832 //! 833 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted 834 //! right before "hint". insert(const_iterator hint,BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)835 insert_return_type insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 836 { 837 typename base_t::node_type n(boost::move(nh)); 838 typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(hint, boost::move(n))); 839 return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node)); 840 } 841 842 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 843 844 //! <b>Effects</b>: Inserts an object x of type T constructed with 845 //! std::forward<Args>(args)... in the container if and only if there is 846 //! no element in the container with an equivalent key. 847 //! p is a hint pointing to where the insert should start to search. 848 //! 849 //! <b>Returns</b>: The bool component of the returned pair is true if and only 850 //! if the insertion takes place, and the iterator component of the pair 851 //! points to the element with key equivalent to the key of x. 852 //! 853 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 854 //! is inserted right before p. 855 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)856 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) 857 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); } 858 859 //! <b>Effects</b>: Inserts an object of type T constructed with 860 //! std::forward<Args>(args)... in the container if and only if there is 861 //! no element in the container with an equivalent key. 862 //! p is a hint pointing to where the insert should start to search. 863 //! 864 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 865 //! to the key of x. 866 //! 867 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 868 //! is inserted right before p. 869 template <class... Args> emplace_hint(const_iterator p,BOOST_FWD_REF (Args)...args)870 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 871 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); } 872 873 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 874 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). 875 //! 876 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 877 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), 878 //! forward_as_tuple(forward<Args>(args)...). 879 //! 880 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the 881 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. 882 //! 883 //! <b>Complexity</b>: Logarithmic. 884 template <class... Args> try_emplace(const key_type & k,BOOST_FWD_REF (Args)...args)885 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args) 886 { return this->base_t::try_emplace(const_iterator(), k, boost::forward<Args>(args)...); } 887 888 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 889 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...). 890 //! 891 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 892 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k), 893 //! forward_as_tuple(forward<Args>(args)...). 894 //! 895 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. 896 //! 897 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value 898 //! is inserted right before p. 899 template <class... Args> try_emplace(const_iterator hint,const key_type & k,BOOST_FWD_REF (Args)...args)900 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args) 901 { return this->base_t::try_emplace(hint, k, boost::forward<Args>(args)...).first; } 902 903 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 904 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). 905 //! 906 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 907 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), 908 //! forward_as_tuple(forward<Args>(args)...). 909 //! 910 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the 911 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k. 912 //! 913 //! <b>Complexity</b>: Logarithmic. 914 template <class... Args> try_emplace(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)915 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) 916 { return this->base_t::try_emplace(const_iterator(), boost::move(k), boost::forward<Args>(args)...); } 917 918 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 919 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...). 920 //! 921 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise 922 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)), 923 //! forward_as_tuple(forward<Args>(args)...). 924 //! 925 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k. 926 //! 927 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value 928 //! is inserted right before p. 929 template <class... Args> try_emplace(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)930 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) 931 { return this->base_t::try_emplace(hint, boost::move(k), boost::forward<Args>(args)...).first; } 932 933 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 934 935 #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \ 936 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 937 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ 938 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\ 939 \ 940 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 941 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 942 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 943 \ 944 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 945 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 946 { return this->base_t::try_emplace(const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 947 \ 948 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 949 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 950 { return this->base_t::try_emplace(hint, k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\ 951 \ 952 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 953 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 954 { return this->base_t::try_emplace(const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 955 \ 956 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 957 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 958 { return this->base_t::try_emplace(hint, boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\ 959 // 960 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE) 961 #undef BOOST_CONTAINER_MAP_EMPLACE_CODE 962 963 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 964 965 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 966 967 //! <b>Effects</b>: Erases the element pointed to by p. 968 //! 969 //! <b>Returns</b>: Returns an iterator pointing to the element immediately 970 //! following q prior to the element being erased. If no such element exists, 971 //! returns end(). 972 //! 973 //! <b>Complexity</b>: Amortized constant time 974 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW; 975 976 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. 977 //! 978 //! <b>Returns</b>: Returns the number of erased elements. 979 //! 980 //! <b>Complexity</b>: log(size()) + count(k) 981 size_type erase(const key_type& x) BOOST_NOEXCEPT_OR_NOTHROW; 982 983 //! <b>Effects</b>: Erases all the elements in the range [first, last). 984 //! 985 //! <b>Returns</b>: Returns last. 986 //! 987 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. 988 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW; 989 990 #endif 991 992 //! <b>Effects</b>: Removes the first element in the container with key equivalent to k. 993 //! 994 //! <b>Returns</b>: A node_type owning the element if found, otherwise an empty node_type. 995 //! 996 //! <b>Complexity</b>: log(size()). extract(const key_type & k)997 node_type extract(const key_type& k) 998 { 999 typename base_t::node_type base_nh(this->base_t::extract(k)); 1000 node_type nh(boost::move(base_nh)); 1001 return BOOST_MOVE_RET(node_type, nh); 1002 } 1003 1004 //! <b>Effects</b>: Removes the element pointed to by "position". 1005 //! 1006 //! <b>Returns</b>: A node_type owning the element, otherwise an empty node_type. 1007 //! 1008 //! <b>Complexity</b>: Amortized constant. extract(const_iterator position)1009 node_type extract(const_iterator position) 1010 { 1011 typename base_t::node_type base_nh(this->base_t::extract(position)); 1012 node_type nh(boost::move(base_nh)); 1013 return BOOST_MOVE_RET(node_type, nh); 1014 } 1015 1016 //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). 1017 //! 1018 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using 1019 //! the comparison object of *this. If there is an element in a with key equivalent to the 1020 //! key of an element from source, then that element is not extracted from source. 1021 //! 1022 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 1023 //! to those same elements but as members of *this. Iterators referring to the transferred 1024 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 1025 //! not into source. 1026 //! 1027 //! <b>Throws</b>: Nothing unless the comparison object throws. 1028 //! 1029 //! <b>Complexity</b>: N log(size() + N) (N has the value source.size()) 1030 template<class C2> merge(map<Key,T,C2,Allocator,Options> & source)1031 BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source) 1032 { 1033 typedef dtl::tree 1034 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 1035 this->merge_unique(static_cast<base2_t&>(source)); 1036 } 1037 1038 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&) 1039 template<class C2> merge(BOOST_RV_REF_BEG map<Key,T,C2,Allocator,Options> BOOST_RV_REF_END source)1040 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 1041 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); } 1042 1043 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&) 1044 template<class C2> merge(multimap<Key,T,C2,Allocator,Options> & source)1045 BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source) 1046 { 1047 typedef dtl::tree 1048 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 1049 this->base_t::merge_unique(static_cast<base2_t&>(source)); 1050 } 1051 1052 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&) 1053 template<class C2> merge(BOOST_RV_REF_BEG multimap<Key,T,C2,Allocator,Options> BOOST_RV_REF_END source)1054 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 1055 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); } 1056 1057 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1058 //! <b>Effects</b>: Swaps the contents of *this and x. 1059 //! 1060 //! <b>Throws</b>: Nothing. 1061 //! 1062 //! <b>Complexity</b>: Constant. 1063 void swap(map& x) 1064 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1065 && boost::container::dtl::is_nothrow_swappable<Compare>::value ) 1066 1067 //! <b>Effects</b>: erase(begin(),end()). 1068 //! 1069 //! <b>Postcondition</b>: size() == 0. 1070 //! 1071 //! <b>Complexity</b>: linear in size(). 1072 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 1073 1074 //! <b>Effects</b>: Returns the comparison object out 1075 //! of which a was constructed. 1076 //! 1077 //! <b>Complexity</b>: Constant. 1078 key_compare key_comp() const; 1079 1080 //! <b>Effects</b>: Returns an object of value_compare constructed out 1081 //! of the comparison object. 1082 //! 1083 //! <b>Complexity</b>: Constant. 1084 value_compare value_comp() const; 1085 1086 //! <b>Returns</b>: An iterator pointing to an element with the key 1087 //! equivalent to x, or end() if such an element is not found. 1088 //! 1089 //! <b>Complexity</b>: Logarithmic. 1090 iterator find(const key_type& x); 1091 1092 //! <b>Returns</b>: A const_iterator pointing to an element with the key 1093 //! equivalent to x, or end() if such an element is not found. 1094 //! 1095 //! <b>Complexity</b>: Logarithmic. 1096 const_iterator find(const key_type& x) const; 1097 1098 //! <b>Requires</b>: This overload is available only if 1099 //! key_compare::is_transparent exists. 1100 //! 1101 //! <b>Returns</b>: An iterator pointing to an element with the key 1102 //! equivalent to x, or end() if such an element is not found. 1103 //! 1104 //! <b>Complexity</b>: Logarithmic. 1105 template<typename K> 1106 iterator find(const K& x); 1107 1108 //! <b>Requires</b>: This overload is available only if 1109 //! key_compare::is_transparent exists. 1110 //! 1111 //! <b>Returns</b>: A const_iterator pointing to an element with the key 1112 //! equivalent to x, or end() if such an element is not found. 1113 //! 1114 //! <b>Complexity</b>: Logarithmic. 1115 template<typename K> 1116 const_iterator find(const K& x) const; 1117 1118 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1119 1120 //! <b>Returns</b>: The number of elements with key equivalent to x. 1121 //! 1122 //! <b>Complexity</b>: log(size())+count(k) count(const key_type & x) const1123 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const 1124 { return static_cast<size_type>(this->find(x) != this->cend()); } 1125 1126 //! <b>Requires</b>: This overload is available only if 1127 //! key_compare::is_transparent exists. 1128 //! 1129 //! <b>Returns</b>: The number of elements with key equivalent to x. 1130 //! 1131 //! <b>Complexity</b>: log(size())+count(k) 1132 template<typename K> count(const K & x) const1133 BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const 1134 { return static_cast<size_type>(this->find(x) != this->cend()); } 1135 1136 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1137 1138 //! <b>Returns</b>: Returns true if there is an element with key 1139 //! equivalent to key in the container, otherwise false. 1140 //! 1141 //! <b>Complexity</b>: log(size()). 1142 bool contains(const key_type& x) const; 1143 1144 //! <b>Requires</b>: This overload is available only if 1145 //! key_compare::is_transparent exists. 1146 //! 1147 //! <b>Returns</b>: Returns true if there is an element with key 1148 //! equivalent to key in the container, otherwise false. 1149 //! 1150 //! <b>Complexity</b>: log(size()). 1151 template<typename K> 1152 bool contains(const K& x) const; 1153 1154 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1155 //! than x, or end() if such an element is not found. 1156 //! 1157 //! <b>Complexity</b>: Logarithmic 1158 iterator lower_bound(const key_type& x); 1159 1160 //! <b>Returns</b>: A const iterator pointing to the first element with key not 1161 //! less than x, or end() if such an element is not found. 1162 //! 1163 //! <b>Complexity</b>: Logarithmic 1164 const_iterator lower_bound(const key_type& x) const; 1165 1166 //! <b>Requires</b>: This overload is available only if 1167 //! key_compare::is_transparent exists. 1168 //! 1169 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1170 //! than x, or end() if such an element is not found. 1171 //! 1172 //! <b>Complexity</b>: Logarithmic 1173 template<typename K> 1174 iterator lower_bound(const K& x); 1175 1176 //! <b>Requires</b>: This overload is available only if 1177 //! key_compare::is_transparent exists. 1178 //! 1179 //! <b>Returns</b>: A const iterator pointing to the first element with key not 1180 //! less than x, or end() if such an element is not found. 1181 //! 1182 //! <b>Complexity</b>: Logarithmic 1183 template<typename K> 1184 const_iterator lower_bound(const K& x) const; 1185 1186 //! <b>Returns</b>: An iterator pointing to the first element with key greater 1187 //! than x, or end() if such an element is not found. 1188 //! 1189 //! <b>Complexity</b>: Logarithmic 1190 iterator upper_bound(const key_type& x); 1191 1192 //! <b>Returns</b>: A const iterator pointing to the first element with key 1193 //! greater than x, or end() if such an element is not found. 1194 //! 1195 //! <b>Complexity</b>: Logarithmic 1196 const_iterator upper_bound(const key_type& x) const; 1197 1198 //! <b>Requires</b>: This overload is available only if 1199 //! key_compare::is_transparent exists. 1200 //! 1201 //! <b>Returns</b>: An iterator pointing to the first element with key greater 1202 //! than x, or end() if such an element is not found. 1203 //! 1204 //! <b>Complexity</b>: Logarithmic 1205 template<typename K> 1206 iterator upper_bound(const K& x); 1207 1208 //! <b>Requires</b>: This overload is available only if 1209 //! key_compare::is_transparent exists. 1210 //! 1211 //! <b>Returns</b>: A const iterator pointing to the first element with key 1212 //! greater than x, or end() if such an element is not found. 1213 //! 1214 //! <b>Complexity</b>: Logarithmic 1215 template<typename K> 1216 const_iterator upper_bound(const K& x) const; 1217 1218 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1219 //! 1220 //! <b>Complexity</b>: Logarithmic 1221 std::pair<iterator,iterator> equal_range(const key_type& x); 1222 1223 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1224 //! 1225 //! <b>Complexity</b>: Logarithmic 1226 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; 1227 1228 //! <b>Requires</b>: This overload is available only if 1229 //! key_compare::is_transparent exists. 1230 //! 1231 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1232 //! 1233 //! <b>Complexity</b>: Logarithmic 1234 template<typename K> 1235 std::pair<iterator,iterator> equal_range(const K& x); 1236 1237 //! <b>Requires</b>: This overload is available only if 1238 //! key_compare::is_transparent exists. 1239 //! 1240 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1241 //! 1242 //! <b>Complexity</b>: Logarithmic 1243 template<typename K> 1244 std::pair<const_iterator,const_iterator> equal_range(const K& x) const; 1245 1246 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 1247 //! 1248 //! <b>Complexity</b>: Linear 1249 void rebalance(); 1250 1251 //! <b>Effects</b>: Returns true if x and y are equal 1252 //! 1253 //! <b>Complexity</b>: Linear to the number of elements in the container. 1254 friend bool operator==(const map& x, const map& y); 1255 1256 //! <b>Effects</b>: Returns true if x and y are unequal 1257 //! 1258 //! <b>Complexity</b>: Linear to the number of elements in the container. 1259 friend bool operator!=(const map& x, const map& y); 1260 1261 //! <b>Effects</b>: Returns true if x is less than y 1262 //! 1263 //! <b>Complexity</b>: Linear to the number of elements in the container. 1264 friend bool operator<(const map& x, const map& y); 1265 1266 //! <b>Effects</b>: Returns true if x is greater than y 1267 //! 1268 //! <b>Complexity</b>: Linear to the number of elements in the container. 1269 friend bool operator>(const map& x, const map& y); 1270 1271 //! <b>Effects</b>: Returns true if x is equal or less than y 1272 //! 1273 //! <b>Complexity</b>: Linear to the number of elements in the container. 1274 friend bool operator<=(const map& x, const map& y); 1275 1276 //! <b>Effects</b>: Returns true if x is equal or greater than y 1277 //! 1278 //! <b>Complexity</b>: Linear to the number of elements in the container. 1279 friend bool operator>=(const map& x, const map& y); 1280 1281 //! <b>Effects</b>: x.swap(y) 1282 //! 1283 //! <b>Complexity</b>: Constant. 1284 friend void swap(map& x, map& y); 1285 1286 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1287 1288 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1289 private: 1290 template<class KeyConvertible> priv_subscript(BOOST_FWD_REF (KeyConvertible)k)1291 BOOST_CONTAINER_FORCEINLINE mapped_type& priv_subscript(BOOST_FWD_REF(KeyConvertible) k) 1292 { 1293 return this->try_emplace(boost::forward<KeyConvertible>(k)).first->second; 1294 } 1295 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1296 }; 1297 1298 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 1299 1300 template <typename InputIterator> 1301 map(InputIterator, InputIterator) -> 1302 map< it_based_non_const_first_type_t<InputIterator> 1303 , it_based_second_type_t<InputIterator>>; 1304 1305 template < typename InputIterator, typename AllocatorOrCompare> 1306 map(InputIterator, InputIterator, AllocatorOrCompare const&) -> 1307 map< it_based_non_const_first_type_t<InputIterator> 1308 , it_based_second_type_t<InputIterator> 1309 , typename dtl::if_c< // Compare 1310 dtl::is_allocator<AllocatorOrCompare>::value 1311 , std::less<it_based_non_const_first_type_t<InputIterator>> 1312 , AllocatorOrCompare 1313 >::type 1314 , typename dtl::if_c< // Allocator 1315 dtl::is_allocator<AllocatorOrCompare>::value 1316 , AllocatorOrCompare 1317 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 1318 >::type 1319 >; 1320 1321 template < typename InputIterator, typename Compare, typename Allocator 1322 , typename = dtl::require_nonallocator_t<Compare> 1323 , typename = dtl::require_allocator_t<Allocator>> 1324 map(InputIterator, InputIterator, Compare const&, Allocator const&) -> 1325 map< it_based_non_const_first_type_t<InputIterator> 1326 , it_based_second_type_t<InputIterator> 1327 , Compare 1328 , Allocator>; 1329 1330 template <typename InputIterator> 1331 map(ordered_unique_range_t, InputIterator, InputIterator) -> 1332 map< it_based_non_const_first_type_t<InputIterator> 1333 , it_based_second_type_t<InputIterator>>; 1334 1335 template < typename InputIterator, typename AllocatorOrCompare> 1336 map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) -> 1337 map< it_based_non_const_first_type_t<InputIterator> 1338 , it_based_second_type_t<InputIterator> 1339 , typename dtl::if_c< // Compare 1340 dtl::is_allocator<AllocatorOrCompare>::value 1341 , std::less<it_based_non_const_first_type_t<InputIterator>> 1342 , AllocatorOrCompare 1343 >::type 1344 , typename dtl::if_c< // Allocator 1345 dtl::is_allocator<AllocatorOrCompare>::value 1346 , AllocatorOrCompare 1347 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 1348 >::type 1349 >; 1350 1351 template < typename InputIterator, typename Compare, typename Allocator 1352 , typename = dtl::require_nonallocator_t<Compare> 1353 , typename = dtl::require_allocator_t<Allocator>> 1354 map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) -> 1355 map< it_based_non_const_first_type_t<InputIterator> 1356 , it_based_second_type_t<InputIterator> 1357 , Compare 1358 , Allocator>; 1359 1360 #endif 1361 1362 1363 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1364 1365 } //namespace container { 1366 1367 //!has_trivial_destructor_after_move<> == true_type 1368 //!specialization for optimizations 1369 template <class Key, class T, class Compare, class Allocator, class Options> 1370 struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator, Options> > 1371 { 1372 typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree; 1373 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value; 1374 }; 1375 1376 namespace container { 1377 1378 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1379 1380 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 1381 1382 //! A multimap is a kind of associative container that supports equivalent keys 1383 //! (possibly containing multiple copies of the same key value) and provides for 1384 //! fast retrieval of values of another type T based on the keys. The multimap class 1385 //! supports bidirectional iterators. 1386 //! 1387 //! A multimap satisfies all of the requirements of a container and of a reversible 1388 //! container and of an associative container. The <code>value_type</code> stored 1389 //! by this container is the value_type is std::pair<const Key, T>. 1390 //! 1391 //! \tparam Key is the key_type of the map 1392 //! \tparam Value is the <code>mapped_type</code> 1393 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). 1394 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s 1395 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>). 1396 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options. 1397 template < class Key, class T, class Compare = std::less<Key> 1398 , class Allocator = new_allocator< std::pair< const Key, T> >, class Options = tree_assoc_defaults> 1399 #else 1400 template <class Key, class T, class Compare, class Allocator, class Options> 1401 #endif 1402 class multimap 1403 ///@cond 1404 : public dtl::tree 1405 < std::pair<const Key, T> 1406 , int 1407 , Compare, Allocator, Options> 1408 ///@endcond 1409 { 1410 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1411 private: 1412 BOOST_COPYABLE_AND_MOVABLE(multimap) 1413 1414 typedef int select_1st_t; 1415 typedef std::pair<const Key, T> value_type_impl; 1416 typedef dtl::tree 1417 <value_type_impl, select_1st_t, Compare, Allocator, Options> base_t; 1418 typedef dtl::pair <Key, T> movable_value_type_impl; 1419 typedef typename base_t::value_compare value_compare_impl; 1420 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1421 1422 public: 1423 ////////////////////////////////////////////// 1424 // 1425 // types 1426 // 1427 ////////////////////////////////////////////// 1428 1429 typedef Key key_type; 1430 typedef T mapped_type; 1431 typedef typename base_t::allocator_type allocator_type; 1432 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type; 1433 typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type; 1434 typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer; 1435 typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer; 1436 typedef typename boost::container::allocator_traits<allocator_type>::reference reference; 1437 typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference; 1438 typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type; 1439 typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_type; 1440 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 1441 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; 1442 typedef Compare key_compare; 1443 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 1444 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 1445 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 1446 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 1447 typedef std::pair<key_type, mapped_type> nonconst_value_type; 1448 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; 1449 typedef BOOST_CONTAINER_IMPDEF(node_handle< 1450 typename base_t::stored_allocator_type 1451 BOOST_MOVE_I pair_key_mapped_of_value 1452 <key_type BOOST_MOVE_I mapped_type> >) node_type; 1453 1454 //allocator_type::value_type type must be std::pair<CONST Key, T> 1455 BOOST_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value)); 1456 1457 ////////////////////////////////////////////// 1458 // 1459 // construct/copy/destroy 1460 // 1461 ////////////////////////////////////////////// 1462 1463 //! <b>Effects</b>: Default constructs an empty multimap. 1464 //! 1465 //! <b>Complexity</b>: Constant. multimap()1466 BOOST_CONTAINER_FORCEINLINE multimap() 1467 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value && 1468 dtl::is_nothrow_default_constructible<Compare>::value) 1469 : base_t() 1470 {} 1471 1472 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator 1473 //! object and allocator. 1474 //! 1475 //! <b>Complexity</b>: Constant. multimap(const allocator_type & a)1476 BOOST_CONTAINER_FORCEINLINE explicit multimap(const allocator_type& a) 1477 : base_t(a) 1478 {} 1479 1480 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison. 1481 //! 1482 //! <b>Complexity</b>: Constant. multimap(const Compare & comp)1483 BOOST_CONTAINER_FORCEINLINE explicit multimap(const Compare& comp) 1484 : base_t(comp) 1485 {} 1486 1487 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison and allocator. 1488 //! 1489 //! <b>Complexity</b>: Constant. multimap(const Compare & comp,const allocator_type & a)1490 BOOST_CONTAINER_FORCEINLINE multimap(const Compare& comp, const allocator_type& a) 1491 : base_t(comp, a) 1492 {} 1493 1494 //! <b>Effects</b>: Constructs an empty multimap and 1495 //! inserts elements from the range [first ,last ). 1496 //! 1497 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1498 //! the predicate and otherwise N logN, where N is last - first. 1499 template <class InputIterator> multimap(InputIterator first,InputIterator last)1500 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last) 1501 : base_t(false, first, last) 1502 {} 1503 1504 //! <b>Effects</b>: Constructs an empty multimap using the specified 1505 //! allocator, and inserts elements from the range [first ,last ). 1506 //! 1507 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1508 //! the predicate and otherwise N logN, where N is last - first. 1509 template <class InputIterator> multimap(InputIterator first,InputIterator last,const allocator_type & a)1510 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const allocator_type& a) 1511 : base_t(false, first, last, Compare(), a) 1512 {} 1513 1514 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1515 //! inserts elements from the range [first ,last ). 1516 //! 1517 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1518 //! the predicate and otherwise N logN, where N is last - first. 1519 template <class InputIterator> multimap(InputIterator first,InputIterator last,const Compare & comp)1520 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const Compare& comp) 1521 : base_t(false, first, last, comp) 1522 {} 1523 1524 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object 1525 //! and allocator, and inserts elements from the range [first ,last ). 1526 //! 1527 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1528 //! the predicate and otherwise N logN, where N is last - first. 1529 template <class InputIterator> multimap(InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)1530 BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, 1531 const Compare& comp, const allocator_type& a) 1532 : base_t(false, first, last, comp, a) 1533 {} 1534 1535 //! <b>Effects</b>: Constructs an empty multimap and 1536 //! inserts elements from the ordered range [first ,last). This function 1537 //! is more efficient than the normal range creation for ordered ranges. 1538 //! 1539 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1540 //! 1541 //! <b>Complexity</b>: Linear in N. 1542 //! 1543 //! <b>Note</b>: Non-standard extension. 1544 template <class InputIterator> multimap(ordered_range_t,InputIterator first,InputIterator last)1545 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last) 1546 : base_t(ordered_range, first, last) 1547 {} 1548 1549 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1550 //! inserts elements from the ordered range [first ,last). This function 1551 //! is more efficient than the normal range creation for ordered ranges. 1552 //! 1553 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1554 //! 1555 //! <b>Complexity</b>: Linear in N. 1556 //! 1557 //! <b>Note</b>: Non-standard extension. 1558 template <class InputIterator> multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp)1559 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp) 1560 : base_t(ordered_range, first, last, comp) 1561 {} 1562 1563 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1564 //! allocator, and inserts elements from the ordered range [first ,last). This function 1565 //! is more efficient than the normal range creation for ordered ranges. 1566 //! 1567 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1568 //! 1569 //! <b>Complexity</b>: Linear in N. 1570 //! 1571 //! <b>Note</b>: Non-standard extension. 1572 template <class InputIterator> multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)1573 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, 1574 const allocator_type& a) 1575 : base_t(ordered_range, first, last, comp, a) 1576 {} 1577 1578 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator and 1579 //! inserts elements from the ordered range [first ,last). This function 1580 //! is more efficient than the normal range creation for ordered ranges. 1581 //! 1582 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1583 //! 1584 //! <b>Complexity</b>: Linear in N. 1585 //! 1586 //! <b>Note</b>: Non-standard extension. 1587 template <class InputIterator> multimap(ordered_range_t,InputIterator first,InputIterator last,const allocator_type & a)1588 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type& a) 1589 : base_t(ordered_range, first, last, Compare(), a) 1590 {} 1591 1592 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1593 //! <b>Effects</b>: Constructs an empty multimap and 1594 //! and inserts elements from the range [il.begin(), il.end()). 1595 //! 1596 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1597 //! the predicate and otherwise N logN, where N is il.first() - il.end(). multimap(std::initializer_list<value_type> il)1598 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il) 1599 : base_t(false, il.begin(), il.end()) 1600 {} 1601 1602 //! <b>Effects</b>: Constructs an empty multimap using the specified 1603 //! allocator, and inserts elements from the range [il.begin(), il.end()). 1604 //! 1605 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1606 //! the predicate and otherwise N logN, where N is il.first() - il.end(). multimap(std::initializer_list<value_type> il,const allocator_type & a)1607 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const allocator_type& a) 1608 : base_t(false, il.begin(), il.end(), Compare(), a) 1609 {} 1610 1611 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1612 //! inserts elements from the range [il.begin(), il.end()). 1613 //! 1614 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1615 //! the predicate and otherwise N logN, where N is il.first() - il.end(). multimap(std::initializer_list<value_type> il,const Compare & comp)1616 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const Compare& comp) 1617 : base_t(false, il.begin(), il.end(), comp) 1618 {} 1619 1620 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1621 //! allocator, and inserts elements from the range [il.begin(), il.end()). 1622 //! 1623 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1624 //! the predicate and otherwise N logN, where N is il.first() - il.end(). multimap(std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)1625 BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) 1626 : base_t(false, il.begin(), il.end(), comp, a) 1627 {} 1628 1629 1630 //! <b>Effects</b>: Constructs an empty map and 1631 //! inserts elements from the ordered range [il.begin(), il.end()). This function 1632 //! is more efficient than the normal range creation for ordered ranges. 1633 //! 1634 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1635 //! 1636 //! <b>Complexity</b>: Linear in N. 1637 //! 1638 //! <b>Note</b>: Non-standard extension. multimap(ordered_range_t,std::initializer_list<value_type> il)1639 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il) 1640 : base_t(ordered_range, il.begin(), il.end()) 1641 {} 1642 1643 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 1644 //! inserts elements from the ordered range [il.begin(), il.end()). This function 1645 //! is more efficient than the normal range creation for ordered ranges. 1646 //! 1647 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1648 //! 1649 //! <b>Complexity</b>: Linear in N. 1650 //! 1651 //! <b>Note</b>: Non-standard extension. multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp)1652 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp) 1653 : base_t(ordered_range, il.begin(), il.end(), comp) 1654 {} 1655 1656 //! <b>Effects</b>: Constructs an empty map and 1657 //! inserts elements from the ordered range [il.begin(), il.end()). This function 1658 //! is more efficient than the normal range creation for ordered ranges. 1659 //! 1660 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1661 //! 1662 //! <b>Complexity</b>: Linear in N. 1663 //! 1664 //! <b>Note</b>: Non-standard extension. multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)1665 BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a) 1666 : base_t(ordered_range, il.begin(), il.end(), comp, a) 1667 {} 1668 1669 #endif 1670 1671 //! <b>Effects</b>: Copy constructs a multimap. 1672 //! 1673 //! <b>Complexity</b>: Linear in x.size(). multimap(const multimap & x)1674 BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x) 1675 : base_t(static_cast<const base_t&>(x)) 1676 {} 1677 1678 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources. 1679 //! 1680 //! <b>Complexity</b>: Constant. 1681 //! 1682 //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF (multimap)x)1683 BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x) 1684 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) 1685 : base_t(BOOST_MOVE_BASE(base_t, x)) 1686 {} 1687 1688 //! <b>Effects</b>: Copy constructs a multimap. 1689 //! 1690 //! <b>Complexity</b>: Linear in x.size(). multimap(const multimap & x,const allocator_type & a)1691 BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x, const allocator_type &a) 1692 : base_t(static_cast<const base_t&>(x), a) 1693 {} 1694 1695 //! <b>Effects</b>: Move constructs a multimap using the specified allocator. 1696 //! Constructs *this using x's resources. 1697 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. 1698 //! 1699 //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF (multimap)x,const allocator_type & a)1700 BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x, const allocator_type &a) 1701 : base_t(BOOST_MOVE_BASE(base_t, x), a) 1702 {} 1703 1704 //! <b>Effects</b>: Makes *this a copy of x. 1705 //! 1706 //! <b>Complexity</b>: Linear in x.size(). operator =(BOOST_COPY_ASSIGN_REF (multimap)x)1707 BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x) 1708 { return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 1709 1710 //! <b>Effects</b>: this->swap(x.get()). 1711 //! 1712 //! <b>Complexity</b>: Constant. operator =(BOOST_RV_REF (multimap)x)1713 BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_RV_REF(multimap) x) 1714 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || 1715 allocator_traits_type::is_always_equal::value) && 1716 boost::container::dtl::is_nothrow_move_assignable<Compare>::value) 1717 { return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 1718 1719 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1720 //! <b>Effects</b>: Assign content of il to *this. 1721 //! operator =(std::initializer_list<value_type> il)1722 BOOST_CONTAINER_FORCEINLINE multimap& operator=(std::initializer_list<value_type> il) 1723 { 1724 this->clear(); 1725 insert(il.begin(), il.end()); 1726 return *this; 1727 } 1728 #endif 1729 1730 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1731 1732 //! @copydoc ::boost::container::set::get_allocator() 1733 allocator_type get_allocator() const; 1734 1735 //! @copydoc ::boost::container::set::get_stored_allocator() 1736 stored_allocator_type &get_stored_allocator(); 1737 1738 //! @copydoc ::boost::container::set::get_stored_allocator() const 1739 const stored_allocator_type &get_stored_allocator() const; 1740 1741 //! @copydoc ::boost::container::set::begin() 1742 iterator begin(); 1743 1744 //! @copydoc ::boost::container::set::begin() const 1745 const_iterator begin() const; 1746 1747 //! @copydoc ::boost::container::set::cbegin() const 1748 const_iterator cbegin() const; 1749 1750 //! @copydoc ::boost::container::set::end() 1751 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 1752 1753 //! @copydoc ::boost::container::set::end() const 1754 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 1755 1756 //! @copydoc ::boost::container::set::cend() const 1757 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 1758 1759 //! @copydoc ::boost::container::set::rbegin() 1760 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 1761 1762 //! @copydoc ::boost::container::set::rbegin() const 1763 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 1764 1765 //! @copydoc ::boost::container::set::crbegin() const 1766 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 1767 1768 //! @copydoc ::boost::container::set::rend() 1769 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 1770 1771 //! @copydoc ::boost::container::set::rend() const 1772 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 1773 1774 //! @copydoc ::boost::container::set::crend() const 1775 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 1776 1777 //! @copydoc ::boost::container::set::empty() const 1778 bool empty() const; 1779 1780 //! @copydoc ::boost::container::set::size() const 1781 size_type size() const; 1782 1783 //! @copydoc ::boost::container::set::max_size() const 1784 size_type max_size() const; 1785 1786 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1787 1788 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1789 1790 //! <b>Effects</b>: Inserts an object of type T constructed with 1791 //! std::forward<Args>(args)... in the container. 1792 //! p is a hint pointing to where the insert should start to search. 1793 //! 1794 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1795 //! to the key of x. 1796 //! 1797 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1798 //! is inserted right before p. 1799 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)1800 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args) 1801 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); } 1802 1803 //! <b>Effects</b>: Inserts an object of type T constructed with 1804 //! std::forward<Args>(args)... in the container. 1805 //! p is a hint pointing to where the insert should start to search. 1806 //! 1807 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1808 //! to the key of x. 1809 //! 1810 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1811 //! is inserted right before p. 1812 template <class... Args> emplace_hint(const_iterator p,BOOST_FWD_REF (Args)...args)1813 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 1814 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); } 1815 1816 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1817 1818 #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \ 1819 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1820 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\ 1821 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\ 1822 \ 1823 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1824 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1825 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 1826 // BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE)1827 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE) 1828 #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE 1829 1830 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1831 1832 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the 1833 //! newly inserted element. 1834 //! 1835 //! <b>Complexity</b>: Logarithmic. 1836 BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x) 1837 { return this->base_t::insert_equal(x); } 1838 1839 //! <b>Effects</b>: Inserts a new value constructed from x and returns 1840 //! the iterator pointing to the newly inserted element. 1841 //! 1842 //! <b>Complexity</b>: Logarithmic. insert(const nonconst_value_type & x)1843 BOOST_CONTAINER_FORCEINLINE iterator insert(const nonconst_value_type& x) 1844 { return this->base_t::emplace_equal(x); } 1845 1846 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns 1847 //! the iterator pointing to the newly inserted element. 1848 //! 1849 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (nonconst_value_type)x)1850 BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(nonconst_value_type) x) 1851 { return this->base_t::emplace_equal(boost::move(x)); } 1852 1853 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns 1854 //! the iterator pointing to the newly inserted element. 1855 //! 1856 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (movable_value_type)x)1857 iterator insert(BOOST_RV_REF(movable_value_type) x) 1858 { return this->base_t::emplace_equal(boost::move(x)); } 1859 1860 //! <b>Effects</b>: Inserts a copy of x in the container. 1861 //! p is a hint pointing to where the insert should start to search. 1862 //! 1863 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1864 //! to the key of x. 1865 //! 1866 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1867 //! is inserted right before p. insert(const_iterator p,const value_type & x)1868 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x) 1869 { return this->base_t::insert_equal(p, x); } 1870 1871 //! <b>Effects</b>: Inserts a new value constructed from x in the container. 1872 //! p is a hint pointing to where the insert should start to search. 1873 //! 1874 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1875 //! to the key of x. 1876 //! 1877 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1878 //! is inserted right before p. insert(const_iterator p,const nonconst_value_type & x)1879 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const nonconst_value_type& x) 1880 { return this->base_t::emplace_hint_equal(p, x); } 1881 1882 //! <b>Effects</b>: Inserts a new value move constructed from x in the container. 1883 //! p is a hint pointing to where the insert should start to search. 1884 //! 1885 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1886 //! to the key of x. 1887 //! 1888 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1889 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (nonconst_value_type)x)1890 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) 1891 { return this->base_t::emplace_hint_equal(p, boost::move(x)); } 1892 1893 //! <b>Effects</b>: Inserts a new value move constructed from x in the container. 1894 //! p is a hint pointing to where the insert should start to search. 1895 //! 1896 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1897 //! to the key of x. 1898 //! 1899 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1900 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)1901 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) 1902 { return this->base_t::emplace_hint_equal(p, boost::move(x)); } 1903 1904 //! <b>Requires</b>: first, last are not iterators into *this. 1905 //! 1906 //! <b>Effects</b>: inserts each element from the range [first,last) . 1907 //! 1908 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 1909 template <class InputIterator> insert(InputIterator first,InputIterator last)1910 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last) 1911 { this->base_t::insert_equal(first, last); } 1912 1913 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1914 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end(). 1915 //! 1916 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end()) insert(std::initializer_list<value_type> il)1917 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il) 1918 { this->base_t::insert_equal(il.begin(), il.end()); } 1919 #endif 1920 1921 //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator(). 1922 //! 1923 //! <b>Effects/Returns</b>: If nh is empty, has no effect and returns end(). Otherwise, inserts 1924 //! the element owned by nh and returns an iterator pointing to the newly inserted element. 1925 //! If a range containing elements with keys equivalent to nh.key() exists, 1926 //! the element is inserted at the end of that range. nh is always emptied. 1927 //! 1928 //! <b>Complexity</b>: Logarithmic insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1929 iterator insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1930 { 1931 typename base_t::node_type n(boost::move(nh)); 1932 return this->base_t::insert_equal_node(boost::move(n)); 1933 } 1934 1935 //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible 1936 //! to the position just prior to "hint". 1937 //! 1938 //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted 1939 //! right before "hint". insert(const_iterator hint,BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1940 iterator insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1941 { 1942 typename base_t::node_type n(boost::move(nh)); 1943 return this->base_t::insert_equal_node(hint, boost::move(n)); 1944 } 1945 1946 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1947 1948 //! @copydoc ::boost::container::set::erase(const_iterator) 1949 iterator erase(const_iterator p); 1950 1951 //! @copydoc ::boost::container::set::erase(const key_type&) 1952 size_type erase(const key_type& x); 1953 1954 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator) 1955 iterator erase(const_iterator first, const_iterator last); 1956 #endif 1957 1958 //! @copydoc ::boost::container::map::extract(const key_type&) extract(const key_type & k)1959 node_type extract(const key_type& k) 1960 { 1961 typename base_t::node_type base_nh(this->base_t::extract(k)); 1962 return node_type(boost::move(base_nh)); 1963 } 1964 1965 //! @copydoc ::boost::container::map::extract(const_iterator) extract(const_iterator position)1966 node_type extract(const_iterator position) 1967 { 1968 typename base_t::node_type base_nh(this->base_t::extract(position)); 1969 return node_type (boost::move(base_nh)); 1970 } 1971 1972 //! <b>Requires</b>: this->get_allocator() == source.get_allocator(). 1973 //! 1974 //! <b>Effects</b>: Extracts each element in source and insert it into a using 1975 //! the comparison object of *this. 1976 //! 1977 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 1978 //! to those same elements but as members of *this. Iterators referring to the transferred 1979 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 1980 //! not into source. 1981 //! 1982 //! <b>Throws</b>: Nothing unless the comparison object throws. 1983 //! 1984 //! <b>Complexity</b>: N log(size() + N) (N has the value source.size()) 1985 template<class C2> merge(multimap<Key,T,C2,Allocator,Options> & source)1986 BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source) 1987 { 1988 typedef dtl::tree 1989 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 1990 this->base_t::merge_equal(static_cast<base2_t&>(source)); 1991 } 1992 1993 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&) 1994 template<class C2> merge(BOOST_RV_REF_BEG multimap<Key,T,C2,Allocator,Options> BOOST_RV_REF_END source)1995 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 1996 { return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); } 1997 1998 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&) 1999 template<class C2> merge(map<Key,T,C2,Allocator,Options> & source)2000 BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source) 2001 { 2002 typedef dtl::tree 2003 <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t; 2004 this->base_t::merge_equal(static_cast<base2_t&>(source)); 2005 } 2006 2007 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&) 2008 template<class C2> merge(BOOST_RV_REF_BEG map<Key,T,C2,Allocator,Options> BOOST_RV_REF_END source)2009 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source) 2010 { return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); } 2011 2012 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2013 //! @copydoc ::boost::container::set::swap 2014 void swap(multiset& x) 2015 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 2016 && boost::container::dtl::is_nothrow_swappable<Compare>::value ); 2017 2018 //! @copydoc ::boost::container::set::clear 2019 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 2020 2021 //! @copydoc ::boost::container::set::key_comp 2022 key_compare key_comp() const; 2023 2024 //! @copydoc ::boost::container::set::value_comp 2025 value_compare value_comp() const; 2026 2027 //! <b>Returns</b>: An iterator pointing to an element with the key 2028 //! equivalent to x, or end() if such an element is not found. 2029 //! 2030 //! <b>Complexity</b>: Logarithmic. 2031 iterator find(const key_type& x); 2032 2033 //! <b>Returns</b>: A const iterator pointing to an element with the key 2034 //! equivalent to x, or end() if such an element is not found. 2035 //! 2036 //! <b>Complexity</b>: Logarithmic. 2037 const_iterator find(const key_type& x) const; 2038 2039 //! <b>Requires</b>: This overload is available only if 2040 //! key_compare::is_transparent exists. 2041 //! 2042 //! <b>Returns</b>: An iterator pointing to an element with the key 2043 //! equivalent to x, or end() if such an element is not found. 2044 //! 2045 //! <b>Complexity</b>: Logarithmic. 2046 template<typename K> 2047 iterator find(const K& x); 2048 2049 //! <b>Requires</b>: This overload is available only if 2050 //! key_compare::is_transparent exists. 2051 //! 2052 //! <b>Returns</b>: A const_iterator pointing to an element with the key 2053 //! equivalent to x, or end() if such an element is not found. 2054 //! 2055 //! <b>Complexity</b>: Logarithmic. 2056 template<typename K> 2057 const_iterator find(const K& x) const; 2058 2059 //! <b>Returns</b>: The number of elements with key equivalent to x. 2060 //! 2061 //! <b>Complexity</b>: log(size())+count(k) 2062 size_type count(const key_type& x) const; 2063 2064 //! <b>Requires</b>: This overload is available only if 2065 //! key_compare::is_transparent exists. 2066 //! 2067 //! <b>Returns</b>: The number of elements with key equivalent to x. 2068 //! 2069 //! <b>Complexity</b>: log(size())+count(k) 2070 template<typename K> 2071 size_type count(const K& x) const; 2072 2073 //! <b>Returns</b>: Returns true if there is an element with key 2074 //! equivalent to key in the container, otherwise false. 2075 //! 2076 //! <b>Complexity</b>: log(size()). 2077 bool contains(const key_type& x) const; 2078 2079 //! <b>Requires</b>: This overload is available only if 2080 //! key_compare::is_transparent exists. 2081 //! 2082 //! <b>Returns</b>: Returns true if there is an element with key 2083 //! equivalent to key in the container, otherwise false. 2084 //! 2085 //! <b>Complexity</b>: log(size()). 2086 template<typename K> 2087 bool contains(const K& x) const; 2088 2089 //! <b>Returns</b>: An iterator pointing to the first element with key not less 2090 //! than x, or end() if such an element is not found. 2091 //! 2092 //! <b>Complexity</b>: Logarithmic 2093 iterator lower_bound(const key_type& x); 2094 2095 //! <b>Returns</b>: A const iterator pointing to the first element with key not 2096 //! less than x, or end() if such an element is not found. 2097 //! 2098 //! <b>Complexity</b>: Logarithmic 2099 const_iterator lower_bound(const key_type& x) const; 2100 2101 //! <b>Requires</b>: This overload is available only if 2102 //! key_compare::is_transparent exists. 2103 //! 2104 //! <b>Returns</b>: An iterator pointing to the first element with key not less 2105 //! than x, or end() if such an element is not found. 2106 //! 2107 //! <b>Complexity</b>: Logarithmic 2108 template<typename K> 2109 iterator lower_bound(const K& x); 2110 2111 //! <b>Requires</b>: This overload is available only if 2112 //! key_compare::is_transparent exists. 2113 //! 2114 //! <b>Returns</b>: A const iterator pointing to the first element with key not 2115 //! less than x, or end() if such an element is not found. 2116 //! 2117 //! <b>Complexity</b>: Logarithmic 2118 template<typename K> 2119 const_iterator lower_bound(const K& x) const; 2120 2121 //! <b>Returns</b>: An iterator pointing to the first element with key greater 2122 //! than x, or end() if such an element is not found. 2123 //! 2124 //! <b>Complexity</b>: Logarithmic 2125 iterator upper_bound(const key_type& x); 2126 2127 //! <b>Returns</b>: A const iterator pointing to the first element with key 2128 //! greater than x, or end() if such an element is not found. 2129 //! 2130 //! <b>Complexity</b>: Logarithmic 2131 const_iterator upper_bound(const key_type& x) const; 2132 2133 //! <b>Requires</b>: This overload is available only if 2134 //! key_compare::is_transparent exists. 2135 //! 2136 //! <b>Returns</b>: An iterator pointing to the first element with key greater 2137 //! than x, or end() if such an element is not found. 2138 //! 2139 //! <b>Complexity</b>: Logarithmic 2140 template<typename K> 2141 iterator upper_bound(const K& x); 2142 2143 //! <b>Requires</b>: This overload is available only if 2144 //! key_compare::is_transparent exists. 2145 //! 2146 //! <b>Returns</b>: A const iterator pointing to the first element with key 2147 //! greater than x, or end() if such an element is not found. 2148 //! 2149 //! <b>Complexity</b>: Logarithmic 2150 template<typename K> 2151 const_iterator upper_bound(const K& x) const; 2152 2153 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2154 //! 2155 //! <b>Complexity</b>: Logarithmic 2156 std::pair<iterator,iterator> equal_range(const key_type& x); 2157 2158 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2159 //! 2160 //! <b>Complexity</b>: Logarithmic 2161 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; 2162 2163 //! <b>Requires</b>: This overload is available only if 2164 //! key_compare::is_transparent exists. 2165 //! 2166 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2167 //! 2168 //! <b>Complexity</b>: Logarithmic 2169 template<typename K> 2170 std::pair<iterator,iterator> equal_range(const K& x); 2171 2172 //! <b>Requires</b>: This overload is available only if 2173 //! key_compare::is_transparent exists. 2174 //! 2175 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 2176 //! 2177 //! <b>Complexity</b>: Logarithmic 2178 template<typename K> 2179 std::pair<const_iterator,const_iterator> equal_range(const K& x) const; 2180 2181 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 2182 //! 2183 //! <b>Complexity</b>: Linear 2184 void rebalance(); 2185 2186 //! <b>Effects</b>: Returns true if x and y are equal 2187 //! 2188 //! <b>Complexity</b>: Linear to the number of elements in the container. 2189 friend bool operator==(const multimap& x, const multimap& y); 2190 2191 //! <b>Effects</b>: Returns true if x and y are unequal 2192 //! 2193 //! <b>Complexity</b>: Linear to the number of elements in the container. 2194 friend bool operator!=(const multimap& x, const multimap& y); 2195 2196 //! <b>Effects</b>: Returns true if x is less than y 2197 //! 2198 //! <b>Complexity</b>: Linear to the number of elements in the container. 2199 friend bool operator<(const multimap& x, const multimap& y); 2200 2201 //! <b>Effects</b>: Returns true if x is greater than y 2202 //! 2203 //! <b>Complexity</b>: Linear to the number of elements in the container. 2204 friend bool operator>(const multimap& x, const multimap& y); 2205 2206 //! <b>Effects</b>: Returns true if x is equal or less than y 2207 //! 2208 //! <b>Complexity</b>: Linear to the number of elements in the container. 2209 friend bool operator<=(const multimap& x, const multimap& y); 2210 2211 //! <b>Effects</b>: Returns true if x is equal or greater than y 2212 //! 2213 //! <b>Complexity</b>: Linear to the number of elements in the container. 2214 friend bool operator>=(const multimap& x, const multimap& y); 2215 2216 //! <b>Effects</b>: x.swap(y) 2217 //! 2218 //! <b>Complexity</b>: Constant. 2219 friend void swap(multimap& x, multimap& y); 2220 2221 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2222 }; 2223 2224 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 2225 2226 template <typename InputIterator> 2227 multimap(InputIterator, InputIterator) -> 2228 multimap< it_based_non_const_first_type_t<InputIterator> 2229 , it_based_second_type_t<InputIterator>>; 2230 2231 template < typename InputIterator, typename AllocatorOrCompare> 2232 multimap(InputIterator, InputIterator, AllocatorOrCompare const&) -> 2233 multimap< it_based_non_const_first_type_t<InputIterator> 2234 , it_based_second_type_t<InputIterator> 2235 , typename dtl::if_c< // Compare 2236 dtl::is_allocator<AllocatorOrCompare>::value 2237 , std::less<it_based_non_const_first_type_t<InputIterator>> 2238 , AllocatorOrCompare 2239 >::type 2240 , typename dtl::if_c< // Allocator 2241 dtl::is_allocator<AllocatorOrCompare>::value 2242 , AllocatorOrCompare 2243 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 2244 >::type 2245 >; 2246 2247 template < typename InputIterator, typename Compare, typename Allocator 2248 , typename = dtl::require_nonallocator_t<Compare> 2249 , typename = dtl::require_allocator_t<Allocator>> 2250 multimap(InputIterator, InputIterator, Compare const&, Allocator const&) -> 2251 multimap< it_based_non_const_first_type_t<InputIterator> 2252 , it_based_second_type_t<InputIterator> 2253 , Compare 2254 , Allocator>; 2255 2256 template <typename InputIterator> 2257 multimap(ordered_range_t, InputIterator, InputIterator) -> 2258 multimap< it_based_non_const_first_type_t<InputIterator> 2259 , it_based_second_type_t<InputIterator>>; 2260 2261 template < typename InputIterator, typename AllocatorOrCompare> 2262 multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) -> 2263 multimap< it_based_non_const_first_type_t<InputIterator> 2264 , it_based_second_type_t<InputIterator> 2265 , typename dtl::if_c< // Compare 2266 dtl::is_allocator<AllocatorOrCompare>::value 2267 , std::less<it_based_const_first_type_t<InputIterator>> 2268 , AllocatorOrCompare 2269 >::type 2270 , typename dtl::if_c< // Allocator 2271 dtl::is_allocator<AllocatorOrCompare>::value 2272 , AllocatorOrCompare 2273 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>> 2274 >::type 2275 >; 2276 2277 template < typename InputIterator, typename Compare, typename Allocator 2278 , typename = dtl::require_nonallocator_t<Compare> 2279 , typename = dtl::require_allocator_t<Allocator>> 2280 multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) -> 2281 multimap< it_based_non_const_first_type_t<InputIterator> 2282 , it_based_second_type_t<InputIterator> 2283 , Compare 2284 , Allocator>; 2285 #endif 2286 2287 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2288 2289 } //namespace container { 2290 2291 //!has_trivial_destructor_after_move<> == true_type 2292 //!specialization for optimizations 2293 template <class Key, class T, class Compare, class Allocator, class Options> 2294 struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator, Options> > 2295 { 2296 typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree; 2297 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value; 2298 }; 2299 2300 namespace container { 2301 2302 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2303 2304 }} 2305 2306 #include <boost/container/detail/config_end.hpp> 2307 2308 #endif // BOOST_CONTAINER_MAP_HPP 2309 2310