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