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 // move 35 #include <boost/move/traits.hpp> 36 #include <boost/move/utility_core.hpp> 37 // move/detail 38 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 39 #include <boost/move/detail/fwd_macros.hpp> 40 #endif 41 #include <boost/move/detail/move_helpers.hpp> 42 // intrusive/detail 43 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair 44 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal 45 // other 46 #include <boost/static_assert.hpp> 47 #include <boost/core/no_exceptions_support.hpp> 48 // std 49 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 50 #include <initializer_list> 51 #endif 52 53 namespace boost { 54 namespace container { 55 56 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 57 58 //! A map is a kind of associative container that supports unique keys (contains at 59 //! most one of each key value) and provides for fast retrieval of values of another 60 //! type T based on the keys. The map class supports bidirectional iterators. 61 //! 62 //! A map satisfies all of the requirements of a container and of a reversible 63 //! container and of an associative container. The <code>value_type</code> stored 64 //! by this container is the value_type is std::pair<const Key, T>. 65 //! 66 //! \tparam Key is the key_type of the map 67 //! \tparam T is the <code>mapped_type</code> 68 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). 69 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s 70 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>). 71 //! \tparam MapOptions is an packed option type generated using using boost::container::tree_assoc_options. 72 template < class Key, class T, class Compare = std::less<Key> 73 , class Allocator = new_allocator< std::pair< const Key, T> >, class MapOptions = tree_assoc_defaults > 74 #else 75 template <class Key, class T, class Compare, class Allocator, class MapOptions> 76 #endif 77 class map 78 ///@cond 79 : public container_detail::tree 80 < Key, std::pair<const Key, T> 81 , container_detail::select1st< std::pair<const Key, T> > 82 , Compare, Allocator, MapOptions> 83 ///@endcond 84 { 85 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 86 private: 87 BOOST_COPYABLE_AND_MOVABLE(map) 88 89 typedef std::pair<const Key, T> value_type_impl; 90 typedef container_detail::tree 91 <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator, MapOptions> base_t; 92 typedef container_detail::pair <Key, T> movable_value_type_impl; 93 typedef container_detail::tree_value_compare 94 < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl> 95 > value_compare_impl; 96 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 97 98 public: 99 ////////////////////////////////////////////// 100 // 101 // types 102 // 103 ////////////////////////////////////////////// 104 105 typedef Key key_type; 106 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; 107 typedef T mapped_type; 108 typedef std::pair<const Key, T> value_type; 109 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer; 110 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer; 111 typedef typename boost::container::allocator_traits<Allocator>::reference reference; 112 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference; 113 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type; 114 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type; 115 typedef Allocator allocator_type; 116 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 117 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; 118 typedef Compare key_compare; 119 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 120 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 121 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 122 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 123 typedef std::pair<key_type, mapped_type> nonconst_value_type; 124 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; 125 126 ////////////////////////////////////////////// 127 // 128 // construct/copy/destroy 129 // 130 ////////////////////////////////////////////// 131 132 //! <b>Effects</b>: Default constructs an empty map. 133 //! 134 //! <b>Complexity</b>: Constant. map()135 map() 136 : base_t() 137 { 138 //A type must be std::pair<CONST Key, T> 139 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 140 } 141 142 //! <b>Effects</b>: Constructs an empty map using the specified comparison object 143 //! and allocator. 144 //! 145 //! <b>Complexity</b>: Constant. map(const Compare & comp,const allocator_type & a=allocator_type ())146 explicit map(const Compare& comp, const allocator_type& a = allocator_type()) 147 : base_t(comp, a) 148 { 149 //A type must be std::pair<CONST Key, T> 150 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 151 } 152 153 //! <b>Effects</b>: Constructs an empty map using the specified allocator. 154 //! 155 //! <b>Complexity</b>: Constant. map(const allocator_type & a)156 explicit map(const allocator_type& a) 157 : base_t(a) 158 { 159 //A type must be std::pair<CONST Key, T> 160 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 161 } 162 163 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 164 //! allocator, and inserts elements from the range [first ,last ). 165 //! 166 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 167 //! comp and otherwise N logN, where N is last - first. 168 template <class InputIterator> map(InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())169 map(InputIterator first, InputIterator last, const Compare& comp = Compare(), 170 const allocator_type& a = allocator_type()) 171 : base_t(true, first, last, comp, a) 172 { 173 //A type must be std::pair<CONST Key, T> 174 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 175 } 176 177 //! <b>Effects</b>: Constructs an empty map using the specified 178 //! allocator, and inserts elements from the range [first ,last ). 179 //! 180 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 181 //! comp and otherwise N logN, where N is last - first. 182 template <class InputIterator> map(InputIterator first,InputIterator last,const allocator_type & a)183 map(InputIterator first, InputIterator last, const allocator_type& a) 184 : base_t(true, first, last, Compare(), a) 185 { 186 //A type must be std::pair<CONST Key, T> 187 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 188 } 189 190 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 191 //! allocator, and inserts elements from the ordered unique range [first ,last). This function 192 //! is more efficient than the normal range creation for ordered ranges. 193 //! 194 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 195 //! unique values. 196 //! 197 //! <b>Complexity</b>: Linear in N. 198 //! 199 //! <b>Note</b>: Non-standard extension. 200 template <class InputIterator> map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())201 map( ordered_unique_range_t, InputIterator first, InputIterator last 202 , const Compare& comp = Compare(), const allocator_type& a = allocator_type()) 203 : base_t(ordered_range, first, last, comp, a) 204 { 205 //A type must be std::pair<CONST Key, T> 206 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 207 } 208 209 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 210 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and 211 //! allocator, and inserts elements from the range [il.begin(), il.end()). 212 //! 213 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 214 //! comp and otherwise N logN, where N is il.first() - il.end(). map(std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())215 map(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) 216 : base_t(true, il.begin(), il.end(), comp, a) 217 { 218 //A type must be std::pair<CONST Key, T> 219 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 220 } 221 222 //! <b>Effects</b>: Constructs an empty map using the specified 223 //! allocator, and inserts elements from the range [il.begin(), il.end()). 224 //! 225 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 226 //! comp and otherwise N logN, where N is il.first() - il.end(). map(std::initializer_list<value_type> il,const allocator_type & a)227 map(std::initializer_list<value_type> il, const allocator_type& a) 228 : base_t(true, il.begin(), il.end(), Compare(), a) 229 { 230 //A type must be std::pair<CONST Key, T> 231 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 232 } 233 234 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 235 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function 236 //! is more efficient than the normal range creation for ordered ranges. 237 //! 238 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 239 //! unique values. 240 //! 241 //! <b>Complexity</b>: Linear in N. 242 //! 243 //! <b>Note</b>: Non-standard extension. map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())244 map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), 245 const allocator_type& a = allocator_type()) 246 : base_t(ordered_range, il.begin(), il.end(), comp, a) 247 { 248 //A type must be std::pair<CONST Key, T> 249 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 250 } 251 #endif 252 253 //! <b>Effects</b>: Copy constructs a map. 254 //! 255 //! <b>Complexity</b>: Linear in x.size(). map(const map & x)256 map(const map& x) 257 : base_t(static_cast<const base_t&>(x)) 258 { 259 //A type must be std::pair<CONST Key, T> 260 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 261 } 262 263 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources. 264 //! 265 //! <b>Complexity</b>: Constant. 266 //! 267 //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF (map)x)268 map(BOOST_RV_REF(map) x) 269 : base_t(BOOST_MOVE_BASE(base_t, x)) 270 { 271 //A type must be std::pair<CONST Key, T> 272 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 273 } 274 275 //! <b>Effects</b>: Copy constructs a map using the specified allocator. 276 //! 277 //! <b>Complexity</b>: Linear in x.size(). map(const map & x,const allocator_type & a)278 map(const map& x, const allocator_type &a) 279 : base_t(static_cast<const base_t&>(x), a) 280 { 281 //A type must be std::pair<CONST Key, T> 282 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 283 } 284 285 //! <b>Effects</b>: Move constructs a map using the specified allocator. 286 //! Constructs *this using x's resources. 287 //! 288 //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise. 289 //! 290 //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF (map)x,const allocator_type & a)291 map(BOOST_RV_REF(map) x, const allocator_type &a) 292 : base_t(BOOST_MOVE_BASE(base_t, x), a) 293 { 294 //A type must be std::pair<CONST Key, T> 295 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 296 } 297 298 //! <b>Effects</b>: Makes *this a copy of x. 299 //! 300 //! <b>Complexity</b>: Linear in x.size(). operator =(BOOST_COPY_ASSIGN_REF (map)x)301 map& operator=(BOOST_COPY_ASSIGN_REF(map) x) 302 { return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 303 304 //! <b>Effects</b>: this->swap(x.get()). 305 //! 306 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 307 //! is false and (allocation throws or value_type's move constructor throws) 308 //! 309 //! <b>Complexity</b>: Constant if allocator_traits_type:: 310 //! propagate_on_container_move_assignment is true or 311 //! this->get>allocator() == x.get_allocator(). Linear otherwise. operator =(BOOST_RV_REF (map)x)312 map& operator=(BOOST_RV_REF(map) x) 313 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 314 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) 315 316 { return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 317 318 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 319 //! <b>Effects</b>: Assign content of il to *this. 320 //! operator =(std::initializer_list<value_type> il)321 map& operator=(std::initializer_list<value_type> il) 322 { 323 this->clear(); 324 insert(il.begin(), il.end()); 325 return *this; 326 } 327 #endif 328 329 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 330 331 //! <b>Effects</b>: Returns a copy of the allocator that 332 //! was passed to the object's constructor. 333 //! 334 //! <b>Complexity</b>: Constant. 335 allocator_type get_allocator() const; 336 337 //! <b>Effects</b>: Returns a reference to the internal allocator. 338 //! 339 //! <b>Throws</b>: Nothing 340 //! 341 //! <b>Complexity</b>: Constant. 342 //! 343 //! <b>Note</b>: Non-standard extension. 344 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW; 345 346 //! <b>Effects</b>: Returns a reference to the internal allocator. 347 //! 348 //! <b>Throws</b>: Nothing 349 //! 350 //! <b>Complexity</b>: Constant. 351 //! 352 //! <b>Note</b>: Non-standard extension. 353 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW; 354 355 //! <b>Effects</b>: Returns an iterator to the first element contained in the container. 356 //! 357 //! <b>Throws</b>: Nothing. 358 //! 359 //! <b>Complexity</b>: Constant. 360 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW; 361 362 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 363 //! 364 //! <b>Throws</b>: Nothing. 365 //! 366 //! <b>Complexity</b>: Constant. 367 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW; 368 369 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 370 //! 371 //! <b>Throws</b>: Nothing. 372 //! 373 //! <b>Complexity</b>: Constant. 374 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 375 376 //! <b>Effects</b>: Returns an iterator to the end of the container. 377 //! 378 //! <b>Throws</b>: Nothing. 379 //! 380 //! <b>Complexity</b>: Constant. 381 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 382 383 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 384 //! 385 //! <b>Throws</b>: Nothing. 386 //! 387 //! <b>Complexity</b>: Constant. 388 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 389 390 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 391 //! 392 //! <b>Throws</b>: Nothing. 393 //! 394 //! <b>Complexity</b>: Constant. 395 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 396 397 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 398 //! of the reversed container. 399 //! 400 //! <b>Throws</b>: Nothing. 401 //! 402 //! <b>Complexity</b>: Constant. 403 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 404 405 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 406 //! of the reversed container. 407 //! 408 //! <b>Throws</b>: Nothing. 409 //! 410 //! <b>Complexity</b>: Constant. 411 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 412 413 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 414 //! of the reversed container. 415 //! 416 //! <b>Throws</b>: Nothing. 417 //! 418 //! <b>Complexity</b>: Constant. 419 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 420 421 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 422 //! of the reversed container. 423 //! 424 //! <b>Throws</b>: Nothing. 425 //! 426 //! <b>Complexity</b>: Constant. 427 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 428 429 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 430 //! of the reversed container. 431 //! 432 //! <b>Throws</b>: Nothing. 433 //! 434 //! <b>Complexity</b>: Constant. 435 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 436 437 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 438 //! of the reversed container. 439 //! 440 //! <b>Throws</b>: Nothing. 441 //! 442 //! <b>Complexity</b>: Constant. 443 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 444 445 //! <b>Effects</b>: Returns true if the container contains no elements. 446 //! 447 //! <b>Throws</b>: Nothing. 448 //! 449 //! <b>Complexity</b>: Constant. 450 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW; 451 452 //! <b>Effects</b>: Returns the number of the elements contained in the container. 453 //! 454 //! <b>Throws</b>: Nothing. 455 //! 456 //! <b>Complexity</b>: Constant. 457 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW; 458 459 //! <b>Effects</b>: Returns the largest possible size of the container. 460 //! 461 //! <b>Throws</b>: Nothing. 462 //! 463 //! <b>Complexity</b>: Constant. 464 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW; 465 466 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 467 468 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 469 //! Effects: If there is no key equivalent to x in the map, inserts 470 //! value_type(x, T()) into the map. 471 //! 472 //! Returns: A reference to the mapped_type corresponding to x in *this. 473 //! 474 //! Complexity: Logarithmic. 475 mapped_type& operator[](const key_type &k); 476 477 //! Effects: If there is no key equivalent to x in the map, inserts 478 //! value_type(boost::move(x), T()) into the map (the key is move-constructed) 479 //! 480 //! Returns: A reference to the mapped_type corresponding to x in *this. 481 //! 482 //! Complexity: Logarithmic. 483 mapped_type& operator[](key_type &&k); 484 #else 485 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) 486 #endif 487 488 //! Returns: A reference to the element whose key is equivalent to x. 489 //! Throws: An exception object of type out_of_range if no such element is present. 490 //! Complexity: logarithmic. at(const key_type & k)491 T& at(const key_type& k) 492 { 493 iterator i = this->find(k); 494 if(i == this->end()){ 495 throw_out_of_range("map::at key not found"); 496 } 497 return i->second; 498 } 499 500 //! Returns: A reference to the element whose key is equivalent to x. 501 //! Throws: An exception object of type out_of_range if no such element is present. 502 //! Complexity: logarithmic. at(const key_type & k) const503 const T& at(const key_type& k) const 504 { 505 const_iterator i = this->find(k); 506 if(i == this->end()){ 507 throw_out_of_range("map::at key not found"); 508 } 509 return i->second; 510 } 511 512 ////////////////////////////////////////////// 513 // 514 // modifiers 515 // 516 ////////////////////////////////////////////// 517 518 //! <b>Effects</b>: Inserts x if and only if there is no element in the container 519 //! with key equivalent to the key of x. 520 //! 521 //! <b>Returns</b>: The bool component of the returned pair is true if and only 522 //! if the insertion takes place, and the iterator component of the pair 523 //! points to the element with key equivalent to the key of x. 524 //! 525 //! <b>Complexity</b>: Logarithmic. insert(const value_type & x)526 std::pair<iterator,bool> insert(const value_type& x) 527 { return this->base_t::insert_unique(x); } 528 529 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if 530 //! there is no element in the container with key equivalent to the key of x. 531 //! 532 //! <b>Returns</b>: The bool component of the returned pair is true if and only 533 //! if the insertion takes place, and the iterator component of the pair 534 //! points to the element with key equivalent to the key of x. 535 //! 536 //! <b>Complexity</b>: Logarithmic. insert(const nonconst_value_type & x)537 std::pair<iterator,bool> insert(const nonconst_value_type& x) 538 { return this->base_t::insert_unique(x); } 539 540 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and 541 //! only if there is no element in the container with key equivalent to the key of x. 542 //! 543 //! <b>Returns</b>: The bool component of the returned pair is true if and only 544 //! if the insertion takes place, and the iterator component of the pair 545 //! points to the element with key equivalent to the key of x. 546 //! 547 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (nonconst_value_type)x)548 std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x) 549 { return this->base_t::insert_unique(boost::move(x)); } 550 551 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and 552 //! only if there is no element in the container with key equivalent to the key of x. 553 //! 554 //! <b>Returns</b>: The bool component of the returned pair is true if and only 555 //! if the insertion takes place, and the iterator component of the pair 556 //! points to the element with key equivalent to the key of x. 557 //! 558 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (movable_value_type)x)559 std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x) 560 { return this->base_t::insert_unique(boost::move(x)); } 561 562 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 563 //! no element in the container with key equivalent to the key of x. 564 //! 565 //! <b>Returns</b>: The bool component of the returned pair is true if and only 566 //! if the insertion takes place, and the iterator component of the pair 567 //! points to the element with key equivalent to the key of x. 568 //! 569 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (value_type)x)570 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) 571 { return this->base_t::insert_unique(boost::move(x)); } 572 573 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is 574 //! no element in the container with key equivalent to the key of x. 575 //! p is a hint pointing to where the insert should start to search. 576 //! 577 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 578 //! to the key of x. 579 //! 580 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 581 //! is inserted right before p. insert(const_iterator p,const value_type & x)582 iterator insert(const_iterator p, const value_type& x) 583 { return this->base_t::insert_unique(p, x); } 584 585 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 586 //! no element in the container with key equivalent to the key of x. 587 //! p is a hint pointing to where the insert should start to search. 588 //! 589 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 590 //! to the key of x. 591 //! 592 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 593 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (nonconst_value_type)x)594 iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) 595 { return this->base_t::insert_unique(p, boost::move(x)); } 596 597 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 598 //! no element in the container with key equivalent to the key of x. 599 //! p is a hint pointing to where the insert should start to search. 600 //! 601 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 602 //! to the key of x. 603 //! 604 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 605 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)606 iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) 607 { return this->base_t::insert_unique(p, boost::move(x)); } 608 609 //! <b>Effects</b>: Inserts a copy of x in the container. 610 //! p is a hint pointing to where the insert should start to search. 611 //! 612 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 613 //! 614 //! <b>Complexity</b>: Logarithmic. insert(const_iterator p,const nonconst_value_type & x)615 iterator insert(const_iterator p, const nonconst_value_type& x) 616 { return this->base_t::insert_unique(p, x); } 617 618 //! <b>Effects</b>: Inserts an element move constructed from x in the container. 619 //! p is a hint pointing to where the insert should start to search. 620 //! 621 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 622 //! 623 //! <b>Complexity</b>: Logarithmic. insert(const_iterator p,BOOST_RV_REF (value_type)x)624 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) 625 { return this->base_t::insert_unique(p, boost::move(x)); } 626 627 //! <b>Requires</b>: first, last are not iterators into *this. 628 //! 629 //! <b>Effects</b>: inserts each element from the range [first,last) if and only 630 //! if there is no element with key equivalent to the key of that element. 631 //! 632 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 633 template <class InputIterator> insert(InputIterator first,InputIterator last)634 void insert(InputIterator first, InputIterator last) 635 { this->base_t::insert_unique(first, last); } 636 637 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 638 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only 639 //! if there is no element with key equivalent to the key of that element. 640 //! 641 //! <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)642 void insert(std::initializer_list<value_type> il) 643 { this->base_t::insert_unique(il.begin(), il.end()); } 644 #endif 645 646 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 647 648 //! <b>Effects</b>: Inserts an object x of type T constructed with 649 //! std::forward<Args>(args)... in the container if and only if there is 650 //! no element in the container with an equivalent key. 651 //! p is a hint pointing to where the insert should start to search. 652 //! 653 //! <b>Returns</b>: The bool component of the returned pair is true if and only 654 //! if the insertion takes place, and the iterator component of the pair 655 //! points to the element with key equivalent to the key of x. 656 //! 657 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 658 //! is inserted right before p. 659 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)660 std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) 661 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); } 662 663 //! <b>Effects</b>: Inserts an object of type T constructed with 664 //! std::forward<Args>(args)... in the container if and only if there is 665 //! no element in the container with an equivalent key. 666 //! p is a hint pointing to where the insert should start to search. 667 //! 668 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 669 //! to the key of x. 670 //! 671 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 672 //! is inserted right before p. 673 template <class... Args> emplace_hint(const_iterator p,BOOST_FWD_REF (Args)...args)674 iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 675 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); } 676 677 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 678 679 #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \ 680 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 681 std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ 682 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\ 683 \ 684 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 685 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 686 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 687 // 688 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE) 689 #undef BOOST_CONTAINER_MAP_EMPLACE_CODE 690 691 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 692 693 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 694 695 //! <b>Effects</b>: Erases the element pointed to by p. 696 //! 697 //! <b>Returns</b>: Returns an iterator pointing to the element immediately 698 //! following q prior to the element being erased. If no such element exists, 699 //! returns end(). 700 //! 701 //! <b>Complexity</b>: Amortized constant time 702 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW; 703 704 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. 705 //! 706 //! <b>Returns</b>: Returns the number of erased elements. 707 //! 708 //! <b>Complexity</b>: log(size()) + count(k) 709 size_type erase(const key_type& x) BOOST_NOEXCEPT_OR_NOTHROW; 710 711 //! <b>Effects</b>: Erases all the elements in the range [first, last). 712 //! 713 //! <b>Returns</b>: Returns last. 714 //! 715 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. 716 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW; 717 718 //! <b>Effects</b>: Swaps the contents of *this and x. 719 //! 720 //! <b>Throws</b>: Nothing. 721 //! 722 //! <b>Complexity</b>: Constant. 723 void swap(map& x) 724 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 725 && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) 726 727 //! <b>Effects</b>: erase(a.begin(),a.end()). 728 //! 729 //! <b>Postcondition</b>: size() == 0. 730 //! 731 //! <b>Complexity</b>: linear in size(). 732 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 733 734 //! <b>Effects</b>: Returns the comparison object out 735 //! of which a was constructed. 736 //! 737 //! <b>Complexity</b>: Constant. 738 key_compare key_comp() const; 739 740 //! <b>Effects</b>: Returns an object of value_compare constructed out 741 //! of the comparison object. 742 //! 743 //! <b>Complexity</b>: Constant. 744 value_compare value_comp() const; 745 746 //! <b>Returns</b>: An iterator pointing to an element with the key 747 //! equivalent to x, or end() if such an element is not found. 748 //! 749 //! <b>Complexity</b>: Logarithmic. 750 iterator find(const key_type& x); 751 752 //! <b>Returns</b>: A const_iterator pointing to an element with the key 753 //! equivalent to x, or end() if such an element is not found. 754 //! 755 //! <b>Complexity</b>: Logarithmic. 756 const_iterator find(const key_type& x) const; 757 758 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 759 760 //! <b>Returns</b>: The number of elements with key equivalent to x. 761 //! 762 //! <b>Complexity</b>: log(size())+count(k) count(const key_type & x) const763 size_type count(const key_type& x) const 764 { return static_cast<size_type>(this->find(x) != this->cend()); } 765 766 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 767 768 //! <b>Returns</b>: An iterator pointing to the first element with key not less 769 //! than k, or a.end() if such an element is not found. 770 //! 771 //! <b>Complexity</b>: Logarithmic 772 iterator lower_bound(const key_type& x); 773 774 //! <b>Returns</b>: A const iterator pointing to the first element with key not 775 //! less than k, or a.end() if such an element is not found. 776 //! 777 //! <b>Complexity</b>: Logarithmic 778 const_iterator lower_bound(const key_type& x) const; 779 780 //! <b>Returns</b>: An iterator pointing to the first element with key not less 781 //! than x, or end() if such an element is not found. 782 //! 783 //! <b>Complexity</b>: Logarithmic 784 iterator upper_bound(const key_type& x); 785 786 //! <b>Returns</b>: A const iterator pointing to the first element with key not 787 //! less than x, or end() if such an element is not found. 788 //! 789 //! <b>Complexity</b>: Logarithmic 790 const_iterator upper_bound(const key_type& x) const; 791 792 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 793 //! 794 //! <b>Complexity</b>: Logarithmic 795 std::pair<iterator,iterator> equal_range(const key_type& x); 796 797 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 798 //! 799 //! <b>Complexity</b>: Logarithmic 800 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; 801 802 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 803 //! 804 //! <b>Complexity</b>: Linear 805 void rebalance(); 806 807 //! <b>Effects</b>: Returns true if x and y are equal 808 //! 809 //! <b>Complexity</b>: Linear to the number of elements in the container. 810 friend bool operator==(const map& x, const map& y); 811 812 //! <b>Effects</b>: Returns true if x and y are unequal 813 //! 814 //! <b>Complexity</b>: Linear to the number of elements in the container. 815 friend bool operator!=(const map& x, const map& y); 816 817 //! <b>Effects</b>: Returns true if x is less than y 818 //! 819 //! <b>Complexity</b>: Linear to the number of elements in the container. 820 friend bool operator<(const map& x, const map& y); 821 822 //! <b>Effects</b>: Returns true if x is greater than y 823 //! 824 //! <b>Complexity</b>: Linear to the number of elements in the container. 825 friend bool operator>(const map& x, const map& y); 826 827 //! <b>Effects</b>: Returns true if x is equal or less than y 828 //! 829 //! <b>Complexity</b>: Linear to the number of elements in the container. 830 friend bool operator<=(const map& x, const map& y); 831 832 //! <b>Effects</b>: Returns true if x is equal or greater than y 833 //! 834 //! <b>Complexity</b>: Linear to the number of elements in the container. 835 friend bool operator>=(const map& x, const map& y); 836 837 //! <b>Effects</b>: x.swap(y) 838 //! 839 //! <b>Complexity</b>: Constant. 840 friend void swap(map& x, map& y); 841 842 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 843 844 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 845 private: priv_subscript(const key_type & k)846 mapped_type& priv_subscript(const key_type &k) 847 { 848 //we can optimize this 849 iterator i = this->lower_bound(k); 850 // i->first is greater than or equivalent to k. 851 if (i == this->end() || this->key_comp()(k, (*i).first)){ 852 container_detail::value_init<mapped_type> m; 853 movable_value_type val(k, boost::move(m.m_t)); 854 i = insert(i, boost::move(val)); 855 } 856 return (*i).second; 857 } 858 priv_subscript(BOOST_RV_REF (key_type)mk)859 mapped_type& priv_subscript(BOOST_RV_REF(key_type) mk) 860 { 861 key_type &k = mk; 862 //we can optimize this 863 iterator i = this->lower_bound(k); 864 // i->first is greater than or equivalent to k. 865 if (i == this->end() || this->key_comp()(k, (*i).first)){ 866 container_detail::value_init<mapped_type> m; 867 movable_value_type val(boost::move(k), boost::move(m.m_t)); 868 i = insert(i, boost::move(val)); 869 } 870 return (*i).second; 871 } 872 873 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 874 }; 875 876 877 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 878 879 } //namespace container { 880 881 //!has_trivial_destructor_after_move<> == true_type 882 //!specialization for optimizations 883 template <class Key, class T, class Compare, class Allocator> 884 struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator> > 885 { 886 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 887 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 888 ::boost::has_trivial_destructor_after_move<pointer>::value && 889 ::boost::has_trivial_destructor_after_move<Compare>::value; 890 }; 891 892 namespace container { 893 894 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 895 896 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 897 898 //! A multimap is a kind of associative container that supports equivalent keys 899 //! (possibly containing multiple copies of the same key value) and provides for 900 //! fast retrieval of values of another type T based on the keys. The multimap class 901 //! supports bidirectional iterators. 902 //! 903 //! A multimap satisfies all of the requirements of a container and of a reversible 904 //! container and of an associative container. The <code>value_type</code> stored 905 //! by this container is the value_type is std::pair<const Key, T>. 906 //! 907 //! \tparam Key is the key_type of the map 908 //! \tparam Value is the <code>mapped_type</code> 909 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). 910 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s 911 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>). 912 //! \tparam MultiMapOptions is an packed option type generated using using boost::container::tree_assoc_options. 913 template < class Key, class T, class Compare = std::less<Key> 914 , class Allocator = new_allocator< std::pair< const Key, T> >, class MultiMapOptions = tree_assoc_defaults> 915 #else 916 template <class Key, class T, class Compare, class Allocator, class MultiMapOptions> 917 #endif 918 class multimap 919 ///@cond 920 : public container_detail::tree 921 < Key, std::pair<const Key, T> 922 , container_detail::select1st< std::pair<const Key, T> > 923 , Compare, Allocator, MultiMapOptions> 924 ///@endcond 925 { 926 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 927 private: 928 BOOST_COPYABLE_AND_MOVABLE(multimap) 929 930 typedef std::pair<const Key, T> value_type_impl; 931 typedef container_detail::tree 932 <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator, MultiMapOptions> base_t; 933 typedef container_detail::pair <Key, T> movable_value_type_impl; 934 typedef container_detail::tree_value_compare 935 < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl> 936 > value_compare_impl; 937 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 938 939 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; 940 941 public: 942 ////////////////////////////////////////////// 943 // 944 // types 945 // 946 ////////////////////////////////////////////// 947 948 typedef Key key_type; 949 typedef T mapped_type; 950 typedef std::pair<const Key, T> value_type; 951 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer; 952 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer; 953 typedef typename boost::container::allocator_traits<Allocator>::reference reference; 954 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference; 955 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type; 956 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type; 957 typedef Allocator allocator_type; 958 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 959 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; 960 typedef Compare key_compare; 961 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 962 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 963 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 964 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 965 typedef std::pair<key_type, mapped_type> nonconst_value_type; 966 typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; 967 968 ////////////////////////////////////////////// 969 // 970 // construct/copy/destroy 971 // 972 ////////////////////////////////////////////// 973 974 //! <b>Effects</b>: Default constructs an empty multimap. 975 //! 976 //! <b>Complexity</b>: Constant. multimap()977 multimap() 978 : base_t() 979 { 980 //A type must be std::pair<CONST Key, T> 981 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 982 } 983 984 //! <b>Effects</b>: Constructs an empty multimap using the specified allocator. 985 //! 986 //! <b>Complexity</b>: Constant. multimap(const Compare & comp,const allocator_type & a=allocator_type ())987 explicit multimap(const Compare& comp, const allocator_type& a = allocator_type()) 988 : base_t(comp, a) 989 { 990 //A type must be std::pair<CONST Key, T> 991 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 992 } 993 994 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison 995 //! object and allocator. 996 //! 997 //! <b>Complexity</b>: Constant. multimap(const allocator_type & a)998 explicit multimap(const allocator_type& a) 999 : base_t(a) 1000 { 1001 //A type must be std::pair<CONST Key, T> 1002 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1003 } 1004 1005 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object 1006 //! and allocator, and inserts elements from the range [first ,last ). 1007 //! 1008 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1009 //! comp and otherwise N logN, where N is last - first. 1010 template <class InputIterator> multimap(InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1011 multimap(InputIterator first, InputIterator last, 1012 const Compare& comp = Compare(), 1013 const allocator_type& a = allocator_type()) 1014 : base_t(false, first, last, comp, a) 1015 { 1016 //A type must be std::pair<CONST Key, T> 1017 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1018 } 1019 1020 //! <b>Effects</b>: Constructs an empty multimap using the specified 1021 //! allocator, and inserts elements from the range [first ,last ). 1022 //! 1023 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1024 //! comp and otherwise N logN, where N is last - first. 1025 template <class InputIterator> multimap(InputIterator first,InputIterator last,const allocator_type & a)1026 multimap(InputIterator first, InputIterator last, const allocator_type& a) 1027 : base_t(false, first, last, Compare(), a) 1028 { 1029 //A type must be std::pair<CONST Key, T> 1030 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1031 } 1032 1033 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1034 //! allocator, and inserts elements from the ordered range [first ,last). This function 1035 //! is more efficient than the normal range creation for ordered ranges. 1036 //! 1037 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 1038 //! 1039 //! <b>Complexity</b>: Linear in N. 1040 //! 1041 //! <b>Note</b>: Non-standard extension. 1042 template <class InputIterator> multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1043 multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp = Compare(), 1044 const allocator_type& a = allocator_type()) 1045 : base_t(ordered_range, first, last, comp, a) 1046 {} 1047 1048 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1049 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and 1050 //! allocator, and inserts elements from the range [il.begin(), il.end()). 1051 //! 1052 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1053 //! comp and otherwise N logN, where N is il.first() - il.end(). multimap(std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1054 multimap(std::initializer_list<value_type> il, const Compare& comp = Compare(), 1055 const allocator_type& a = allocator_type()) 1056 : base_t(false, il.begin(), il.end(), comp, a) 1057 { 1058 //A type must be std::pair<CONST Key, T> 1059 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1060 } 1061 1062 //! <b>Effects</b>: Constructs an empty multimap using the specified 1063 //! allocator, and inserts elements from the range [il.begin(), il.end()). 1064 //! 1065 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 1066 //! comp and otherwise N logN, where N is il.first() - il.end(). multimap(std::initializer_list<value_type> il,const allocator_type & a)1067 multimap(std::initializer_list<value_type> il, const allocator_type& a) 1068 : base_t(false, il.begin(), il.end(), Compare(), a) 1069 { 1070 //A type must be std::pair<CONST Key, T> 1071 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1072 } 1073 1074 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 1075 //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function 1076 //! is more efficient than the normal range creation for ordered ranges. 1077 //! 1078 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. 1079 //! 1080 //! <b>Complexity</b>: Linear in N. 1081 //! 1082 //! <b>Note</b>: Non-standard extension. multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())1083 multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), 1084 const allocator_type& a = allocator_type()) 1085 : base_t(ordered_range, il.begin(), il.end(), comp, a) 1086 { 1087 //A type must be std::pair<CONST Key, T> 1088 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1089 } 1090 #endif 1091 1092 //! <b>Effects</b>: Copy constructs a multimap. 1093 //! 1094 //! <b>Complexity</b>: Linear in x.size(). multimap(const multimap & x)1095 multimap(const multimap& x) 1096 : base_t(static_cast<const base_t&>(x)) 1097 { 1098 //A type must be std::pair<CONST Key, T> 1099 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1100 } 1101 1102 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources. 1103 //! 1104 //! <b>Complexity</b>: Constant. 1105 //! 1106 //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF (multimap)x)1107 multimap(BOOST_RV_REF(multimap) x) 1108 : base_t(BOOST_MOVE_BASE(base_t, x)) 1109 { 1110 //A type must be std::pair<CONST Key, T> 1111 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1112 } 1113 1114 //! <b>Effects</b>: Copy constructs a multimap. 1115 //! 1116 //! <b>Complexity</b>: Linear in x.size(). multimap(const multimap & x,const allocator_type & a)1117 multimap(const multimap& x, const allocator_type &a) 1118 : base_t(static_cast<const base_t&>(x), a) 1119 { 1120 //A type must be std::pair<CONST Key, T> 1121 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1122 } 1123 1124 //! <b>Effects</b>: Move constructs a multimap using the specified allocator. 1125 //! Constructs *this using x's resources. 1126 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. 1127 //! 1128 //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF (multimap)x,const allocator_type & a)1129 multimap(BOOST_RV_REF(multimap) x, const allocator_type &a) 1130 : base_t(BOOST_MOVE_BASE(base_t, x), a) 1131 { 1132 //A type must be std::pair<CONST Key, T> 1133 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); 1134 } 1135 1136 //! <b>Effects</b>: Makes *this a copy of x. 1137 //! 1138 //! <b>Complexity</b>: Linear in x.size(). operator =(BOOST_COPY_ASSIGN_REF (multimap)x)1139 multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x) 1140 { return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 1141 1142 //! <b>Effects</b>: this->swap(x.get()). 1143 //! 1144 //! <b>Complexity</b>: Constant. operator =(BOOST_RV_REF (multimap)x)1145 multimap& operator=(BOOST_RV_REF(multimap) x) 1146 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1147 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) 1148 { return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 1149 1150 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1151 //! <b>Effects</b>: Assign content of il to *this. 1152 //! operator =(std::initializer_list<value_type> il)1153 multimap& operator=(std::initializer_list<value_type> il) 1154 { 1155 this->clear(); 1156 insert(il.begin(), il.end()); 1157 return *this; 1158 } 1159 #endif 1160 1161 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1162 1163 //! @copydoc ::boost::container::set::get_allocator() 1164 allocator_type get_allocator() const; 1165 1166 //! @copydoc ::boost::container::set::get_stored_allocator() 1167 stored_allocator_type &get_stored_allocator(); 1168 1169 //! @copydoc ::boost::container::set::get_stored_allocator() const 1170 const stored_allocator_type &get_stored_allocator() const; 1171 1172 //! @copydoc ::boost::container::set::begin() 1173 iterator begin(); 1174 1175 //! @copydoc ::boost::container::set::begin() const 1176 const_iterator begin() const; 1177 1178 //! @copydoc ::boost::container::set::cbegin() const 1179 const_iterator cbegin() const; 1180 1181 //! @copydoc ::boost::container::set::end() 1182 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 1183 1184 //! @copydoc ::boost::container::set::end() const 1185 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 1186 1187 //! @copydoc ::boost::container::set::cend() const 1188 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 1189 1190 //! @copydoc ::boost::container::set::rbegin() 1191 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 1192 1193 //! @copydoc ::boost::container::set::rbegin() const 1194 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 1195 1196 //! @copydoc ::boost::container::set::crbegin() const 1197 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 1198 1199 //! @copydoc ::boost::container::set::rend() 1200 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 1201 1202 //! @copydoc ::boost::container::set::rend() const 1203 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 1204 1205 //! @copydoc ::boost::container::set::crend() const 1206 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 1207 1208 //! @copydoc ::boost::container::set::empty() const 1209 bool empty() const; 1210 1211 //! @copydoc ::boost::container::set::size() const 1212 size_type size() const; 1213 1214 //! @copydoc ::boost::container::set::max_size() const 1215 size_type max_size() const; 1216 1217 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1218 1219 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1220 1221 //! <b>Effects</b>: Inserts an object of type T constructed with 1222 //! std::forward<Args>(args)... in the container. 1223 //! p is a hint pointing to where the insert should start to search. 1224 //! 1225 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1226 //! to the key of x. 1227 //! 1228 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1229 //! is inserted right before p. 1230 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)1231 iterator emplace(BOOST_FWD_REF(Args)... args) 1232 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); } 1233 1234 //! <b>Effects</b>: Inserts an object of type T constructed with 1235 //! std::forward<Args>(args)... in the container. 1236 //! p is a hint pointing to where the insert should start to search. 1237 //! 1238 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1239 //! to the key of x. 1240 //! 1241 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1242 //! is inserted right before p. 1243 template <class... Args> emplace_hint(const_iterator p,BOOST_FWD_REF (Args)...args)1244 iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 1245 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); } 1246 1247 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1248 1249 #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \ 1250 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1251 iterator emplace(BOOST_MOVE_UREF##N)\ 1252 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\ 1253 \ 1254 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1255 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1256 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 1257 // BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE)1258 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE) 1259 #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE 1260 1261 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1262 1263 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the 1264 //! newly inserted element. 1265 //! 1266 //! <b>Complexity</b>: Logarithmic. 1267 iterator insert(const value_type& x) 1268 { return this->base_t::insert_equal(x); } 1269 1270 //! <b>Effects</b>: Inserts a new value constructed from x and returns 1271 //! the iterator pointing to the newly inserted element. 1272 //! 1273 //! <b>Complexity</b>: Logarithmic. insert(const nonconst_value_type & x)1274 iterator insert(const nonconst_value_type& x) 1275 { return this->base_t::insert_equal(x); } 1276 1277 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns 1278 //! the iterator pointing to the newly inserted element. 1279 //! 1280 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (nonconst_value_type)x)1281 iterator insert(BOOST_RV_REF(nonconst_value_type) x) 1282 { return this->base_t::insert_equal(boost::move(x)); } 1283 1284 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns 1285 //! the iterator pointing to the newly inserted element. 1286 //! 1287 //! <b>Complexity</b>: Logarithmic. insert(BOOST_RV_REF (movable_value_type)x)1288 iterator insert(BOOST_RV_REF(movable_value_type) x) 1289 { return this->base_t::insert_equal(boost::move(x)); } 1290 1291 //! <b>Effects</b>: Inserts a copy of x in the container. 1292 //! p is a hint pointing to where the insert should start to search. 1293 //! 1294 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1295 //! to the key of x. 1296 //! 1297 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1298 //! is inserted right before p. insert(const_iterator p,const value_type & x)1299 iterator insert(const_iterator p, const value_type& x) 1300 { return this->base_t::insert_equal(p, x); } 1301 1302 //! <b>Effects</b>: Inserts a new value constructed from x in the container. 1303 //! p is a hint pointing to where the insert should start to search. 1304 //! 1305 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1306 //! to the key of x. 1307 //! 1308 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1309 //! is inserted right before p. insert(const_iterator p,const nonconst_value_type & x)1310 iterator insert(const_iterator p, const nonconst_value_type& x) 1311 { return this->base_t::insert_equal(p, x); } 1312 1313 //! <b>Effects</b>: Inserts a new value move constructed from x in the container. 1314 //! p is a hint pointing to where the insert should start to search. 1315 //! 1316 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1317 //! to the key of x. 1318 //! 1319 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1320 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (nonconst_value_type)x)1321 iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) 1322 { return this->base_t::insert_equal(p, boost::move(x)); } 1323 1324 //! <b>Effects</b>: Inserts a new value move constructed from x in the container. 1325 //! p is a hint pointing to where the insert should start to search. 1326 //! 1327 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1328 //! to the key of x. 1329 //! 1330 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1331 //! is inserted right before p. insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)1332 iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) 1333 { return this->base_t::insert_equal(p, boost::move(x)); } 1334 1335 //! <b>Requires</b>: first, last are not iterators into *this. 1336 //! 1337 //! <b>Effects</b>: inserts each element from the range [first,last) . 1338 //! 1339 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 1340 template <class InputIterator> insert(InputIterator first,InputIterator last)1341 void insert(InputIterator first, InputIterator last) 1342 { this->base_t::insert_equal(first, last); } 1343 1344 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1345 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end(). 1346 //! 1347 //! <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)1348 void insert(std::initializer_list<value_type> il) 1349 { this->base_t::insert_equal(il.begin(), il.end()); } 1350 #endif 1351 1352 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1353 1354 //! @copydoc ::boost::container::set::erase(const_iterator) 1355 iterator erase(const_iterator p); 1356 1357 //! @copydoc ::boost::container::set::erase(const key_type&) 1358 size_type erase(const key_type& x); 1359 1360 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator) 1361 iterator erase(const_iterator first, const_iterator last); 1362 1363 //! @copydoc ::boost::container::set::swap 1364 void swap(multiset& x) 1365 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1366 && boost::container::container_detail::is_nothrow_swappable<Compare>::value ); 1367 1368 //! @copydoc ::boost::container::set::clear 1369 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 1370 1371 //! @copydoc ::boost::container::set::key_comp 1372 key_compare key_comp() const; 1373 1374 //! @copydoc ::boost::container::set::value_comp 1375 value_compare value_comp() const; 1376 1377 //! <b>Returns</b>: An iterator pointing to an element with the key 1378 //! equivalent to x, or end() if such an element is not found. 1379 //! 1380 //! <b>Complexity</b>: Logarithmic. 1381 iterator find(const key_type& x); 1382 1383 //! <b>Returns</b>: A const iterator pointing to an element with the key 1384 //! equivalent to x, or end() if such an element is not found. 1385 //! 1386 //! <b>Complexity</b>: Logarithmic. 1387 const_iterator find(const key_type& x) const; 1388 1389 //! <b>Returns</b>: The number of elements with key equivalent to x. 1390 //! 1391 //! <b>Complexity</b>: log(size())+count(k) 1392 size_type count(const key_type& x) const; 1393 1394 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1395 //! than k, or a.end() if such an element is not found. 1396 //! 1397 //! <b>Complexity</b>: Logarithmic 1398 iterator lower_bound(const key_type& x); 1399 1400 //! <b>Returns</b>: A const iterator pointing to the first element with key not 1401 //! less than k, or a.end() if such an element is not found. 1402 //! 1403 //! <b>Complexity</b>: Logarithmic 1404 const_iterator lower_bound(const key_type& x) const; 1405 1406 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1407 //! than x, or end() if such an element is not found. 1408 //! 1409 //! <b>Complexity</b>: Logarithmic 1410 iterator upper_bound(const key_type& x); 1411 1412 //! <b>Returns</b>: A const iterator pointing to the first element with key not 1413 //! less than x, or end() if such an element is not found. 1414 //! 1415 //! <b>Complexity</b>: Logarithmic 1416 const_iterator upper_bound(const key_type& x) const; 1417 1418 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1419 //! 1420 //! <b>Complexity</b>: Logarithmic 1421 std::pair<iterator,iterator> equal_range(const key_type& x); 1422 1423 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1424 //! 1425 //! <b>Complexity</b>: Logarithmic 1426 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; 1427 1428 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 1429 //! 1430 //! <b>Complexity</b>: Linear 1431 void rebalance(); 1432 1433 //! <b>Effects</b>: Returns true if x and y are equal 1434 //! 1435 //! <b>Complexity</b>: Linear to the number of elements in the container. 1436 friend bool operator==(const multimap& x, const multimap& y); 1437 1438 //! <b>Effects</b>: Returns true if x and y are unequal 1439 //! 1440 //! <b>Complexity</b>: Linear to the number of elements in the container. 1441 friend bool operator!=(const multimap& x, const multimap& y); 1442 1443 //! <b>Effects</b>: Returns true if x is less than y 1444 //! 1445 //! <b>Complexity</b>: Linear to the number of elements in the container. 1446 friend bool operator<(const multimap& x, const multimap& y); 1447 1448 //! <b>Effects</b>: Returns true if x is greater than y 1449 //! 1450 //! <b>Complexity</b>: Linear to the number of elements in the container. 1451 friend bool operator>(const multimap& x, const multimap& y); 1452 1453 //! <b>Effects</b>: Returns true if x is equal or less than y 1454 //! 1455 //! <b>Complexity</b>: Linear to the number of elements in the container. 1456 friend bool operator<=(const multimap& x, const multimap& y); 1457 1458 //! <b>Effects</b>: Returns true if x is equal or greater than y 1459 //! 1460 //! <b>Complexity</b>: Linear to the number of elements in the container. 1461 friend bool operator>=(const multimap& x, const multimap& y); 1462 1463 //! <b>Effects</b>: x.swap(y) 1464 //! 1465 //! <b>Complexity</b>: Constant. 1466 friend void swap(multimap& x, multimap& y); 1467 1468 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1469 }; 1470 1471 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1472 1473 } //namespace container { 1474 1475 //!has_trivial_destructor_after_move<> == true_type 1476 //!specialization for optimizations 1477 template <class Key, class T, class Compare, class Allocator> 1478 struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator> > 1479 { 1480 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 1481 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 1482 ::boost::has_trivial_destructor_after_move<pointer>::value && 1483 ::boost::has_trivial_destructor_after_move<Compare>::value; 1484 }; 1485 1486 namespace container { 1487 1488 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1489 1490 }} 1491 1492 #include <boost/container/detail/config_end.hpp> 1493 1494 #endif // BOOST_CONTAINER_MAP_HPP 1495 1496