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 SetOptions 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 SetOptions = tree_assoc_defaults > 64 #else 65 template <class Key, class Compare, class Allocator, class SetOptions> 66 #endif 67 class set 68 ///@cond 69 : public container_detail::tree 70 < Key, Key, container_detail::identity<Key>, Compare, Allocator, SetOptions> 71 ///@endcond 72 { 73 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 74 private: 75 BOOST_COPYABLE_AND_MOVABLE(set) 76 typedef container_detail::tree 77 < Key, Key, container_detail::identity<Key>, Compare, Allocator, SetOptions> 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 Compare value_compare; 90 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; 91 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 92 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; 93 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; 94 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; 95 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; 96 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; 97 typedef Allocator allocator_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 104 ////////////////////////////////////////////// 105 // 106 // construct/copy/destroy 107 // 108 ////////////////////////////////////////////// 109 110 //! <b>Effects</b>: Default constructs an empty set. 111 //! 112 //! <b>Complexity</b>: Constant. set()113 set() 114 : base_t() 115 {} 116 117 //! <b>Effects</b>: Constructs an empty set using the specified comparison object 118 //! and allocator. 119 //! 120 //! <b>Complexity</b>: Constant. set(const Compare & comp,const allocator_type & a=allocator_type ())121 explicit set(const Compare& comp, 122 const allocator_type& a = allocator_type()) 123 : base_t(comp, a) 124 {} 125 126 //! <b>Effects</b>: Constructs an empty set using the specified allocator object. 127 //! 128 //! <b>Complexity</b>: Constant. set(const allocator_type & a)129 explicit set(const allocator_type& a) 130 : base_t(a) 131 {} 132 133 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 134 //! allocator, and inserts elements from the range [first ,last ). 135 //! 136 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 137 //! comp and otherwise N logN, where N is last - first. 138 template <class InputIterator> set(InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())139 set(InputIterator first, InputIterator last, const Compare& comp = Compare(), 140 const allocator_type& a = allocator_type()) 141 : base_t(true, first, last, comp, a) 142 {} 143 144 //! <b>Effects</b>: Constructs an empty set using the specified 145 //! allocator, and 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 //! comp and otherwise N logN, where N is last - first. 149 template <class InputIterator> set(InputIterator first,InputIterator last,const allocator_type & a)150 set(InputIterator first, InputIterator last, const allocator_type& a) 151 : base_t(true, first, last, key_compare(), a) 152 {} 153 154 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 155 //! allocator, and inserts elements from the ordered unique range [first ,last). This function 156 //! is more efficient than the normal range creation for ordered ranges. 157 //! 158 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 159 //! unique values. 160 //! 161 //! <b>Complexity</b>: Linear in N. 162 //! 163 //! <b>Note</b>: Non-standard extension. 164 template <class InputIterator> set(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())165 set( ordered_unique_range_t, InputIterator first, InputIterator last 166 , const Compare& comp = Compare(), const allocator_type& a = allocator_type()) 167 : base_t(ordered_range, first, last, comp, a) 168 {} 169 170 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 171 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 172 //! allocator, and inserts elements from the range [il.begin(), il.end()). 173 //! 174 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using 175 //! comp and otherwise N logN, where N is il.begin() - il.end(). set(std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())176 set(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) 177 : base_t(true, il.begin(), il.end(), comp, a) 178 {} 179 180 //! <b>Effects</b>: Constructs an empty set using the specified 181 //! allocator, and inserts elements from the range [il.begin(), il.end()). 182 //! 183 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using 184 //! comp and otherwise N logN, where N is il.begin() - il.end(). set(std::initializer_list<value_type> il,const allocator_type & a)185 set(std::initializer_list<value_type> il, const allocator_type& a) 186 : base_t(true, il.begin(), il.end(), Compare(), a) 187 {} 188 189 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 190 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function 191 //! is more efficient than the normal range creation for ordered ranges. 192 //! 193 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be 194 //! unique values. 195 //! 196 //! <b>Complexity</b>: Linear in N. 197 //! 198 //! <b>Note</b>: Non-standard extension. set(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())199 set( ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare() 200 , const allocator_type& a = allocator_type()) 201 : base_t(ordered_range, il.begin(), il.end(), comp, a) 202 {} 203 #endif 204 205 //! <b>Effects</b>: Copy constructs a set. 206 //! 207 //! <b>Complexity</b>: Linear in x.size(). set(const set & x)208 set(const set& x) 209 : base_t(static_cast<const base_t&>(x)) 210 {} 211 212 //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources. 213 //! 214 //! <b>Complexity</b>: Constant. 215 //! 216 //! <b>Postcondition</b>: x is emptied. set(BOOST_RV_REF (set)x)217 set(BOOST_RV_REF(set) x) 218 : base_t(BOOST_MOVE_BASE(base_t, x)) 219 {} 220 221 //! <b>Effects</b>: Copy constructs a set using the specified allocator. 222 //! 223 //! <b>Complexity</b>: Linear in x.size(). set(const set & x,const allocator_type & a)224 set(const set& x, const allocator_type &a) 225 : base_t(static_cast<const base_t&>(x), a) 226 {} 227 228 //! <b>Effects</b>: Move constructs a set using the specified allocator. 229 //! Constructs *this using x's resources. 230 //! 231 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. set(BOOST_RV_REF (set)x,const allocator_type & a)232 set(BOOST_RV_REF(set) x, const allocator_type &a) 233 : base_t(BOOST_MOVE_BASE(base_t, x), a) 234 {} 235 236 //! <b>Effects</b>: Makes *this a copy of x. 237 //! 238 //! <b>Complexity</b>: Linear in x.size(). operator =(BOOST_COPY_ASSIGN_REF (set)x)239 set& operator=(BOOST_COPY_ASSIGN_REF(set) x) 240 { return static_cast<set&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 241 242 //! <b>Effects</b>: this->swap(x.get()). 243 //! 244 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 245 //! is false and (allocation throws or value_type's move constructor throws) 246 //! 247 //! <b>Complexity</b>: Constant if allocator_traits_type:: 248 //! propagate_on_container_move_assignment is true or 249 //! this->get>allocator() == x.get_allocator(). Linear otherwise. operator =(BOOST_RV_REF (set)x)250 set& operator=(BOOST_RV_REF(set) x) 251 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 252 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) 253 { return static_cast<set&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 254 255 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) operator =(std::initializer_list<value_type> il)256 set& operator=(std::initializer_list<value_type> il) 257 { 258 this->clear(); 259 insert(il.begin(), il.end()); 260 return *this; 261 } 262 #endif 263 264 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 265 266 //! <b>Effects</b>: Returns a copy of the allocator that 267 //! was passed to the object's constructor. 268 //! 269 //! <b>Complexity</b>: Constant. 270 allocator_type get_allocator() const; 271 272 //! <b>Effects</b>: Returns a reference to the internal allocator. 273 //! 274 //! <b>Throws</b>: Nothing 275 //! 276 //! <b>Complexity</b>: Constant. 277 //! 278 //! <b>Note</b>: Non-standard extension. 279 stored_allocator_type &get_stored_allocator(); 280 281 //! <b>Effects</b>: Returns a reference to the internal allocator. 282 //! 283 //! <b>Throws</b>: Nothing 284 //! 285 //! <b>Complexity</b>: Constant. 286 //! 287 //! <b>Note</b>: Non-standard extension. 288 const stored_allocator_type &get_stored_allocator() const; 289 290 //! <b>Effects</b>: Returns an iterator to the first element contained in the container. 291 //! 292 //! <b>Throws</b>: Nothing. 293 //! 294 //! <b>Complexity</b>: Constant 295 iterator begin(); 296 297 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 298 //! 299 //! <b>Throws</b>: Nothing. 300 //! 301 //! <b>Complexity</b>: Constant. 302 const_iterator begin() const; 303 304 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 305 //! 306 //! <b>Throws</b>: Nothing. 307 //! 308 //! <b>Complexity</b>: Constant. 309 const_iterator cbegin() const; 310 311 //! <b>Effects</b>: Returns an iterator to the end of the container. 312 //! 313 //! <b>Throws</b>: Nothing. 314 //! 315 //! <b>Complexity</b>: Constant. 316 iterator end(); 317 318 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 319 //! 320 //! <b>Throws</b>: Nothing. 321 //! 322 //! <b>Complexity</b>: Constant. 323 const_iterator end() const; 324 325 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 326 //! 327 //! <b>Throws</b>: Nothing. 328 //! 329 //! <b>Complexity</b>: Constant. 330 const_iterator cend() const; 331 332 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 333 //! of the reversed container. 334 //! 335 //! <b>Throws</b>: Nothing. 336 //! 337 //! <b>Complexity</b>: Constant. 338 reverse_iterator rbegin(); 339 340 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 341 //! of the reversed container. 342 //! 343 //! <b>Throws</b>: Nothing. 344 //! 345 //! <b>Complexity</b>: Constant. 346 const_reverse_iterator rbegin() const; 347 348 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 349 //! of the reversed container. 350 //! 351 //! <b>Throws</b>: Nothing. 352 //! 353 //! <b>Complexity</b>: Constant. 354 const_reverse_iterator crbegin() const; 355 356 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 357 //! of the reversed container. 358 //! 359 //! <b>Throws</b>: Nothing. 360 //! 361 //! <b>Complexity</b>: Constant. 362 reverse_iterator rend(); 363 364 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 365 //! of the reversed container. 366 //! 367 //! <b>Throws</b>: Nothing. 368 //! 369 //! <b>Complexity</b>: Constant. 370 const_reverse_iterator rend() const; 371 372 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 373 //! of the reversed container. 374 //! 375 //! <b>Throws</b>: Nothing. 376 //! 377 //! <b>Complexity</b>: Constant. 378 const_reverse_iterator crend() const; 379 380 //! <b>Effects</b>: Returns true if the container contains no elements. 381 //! 382 //! <b>Throws</b>: Nothing. 383 //! 384 //! <b>Complexity</b>: Constant. 385 bool empty() const; 386 387 //! <b>Effects</b>: Returns the number of the elements contained in the container. 388 //! 389 //! <b>Throws</b>: Nothing. 390 //! 391 //! <b>Complexity</b>: Constant. 392 size_type size() const; 393 394 //! <b>Effects</b>: Returns the largest possible size of the container. 395 //! 396 //! <b>Throws</b>: Nothing. 397 //! 398 //! <b>Complexity</b>: Constant. 399 size_type max_size() const; 400 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 401 402 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 403 404 //! <b>Effects</b>: Inserts an object x of type Key constructed with 405 //! std::forward<Args>(args)... if and only if there is 406 //! no element in the container with equivalent value. 407 //! and returns the iterator pointing to the 408 //! newly inserted element. 409 //! 410 //! <b>Returns</b>: The bool component of the returned pair is true if and only 411 //! if the insertion takes place, and the iterator component of the pair 412 //! points to the element with key equivalent to the key of x. 413 //! 414 //! <b>Throws</b>: If memory allocation throws or 415 //! Key's in-place constructor throws. 416 //! 417 //! <b>Complexity</b>: Logarithmic. 418 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)419 std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) 420 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); } 421 422 //! <b>Effects</b>: Inserts an object of type Key constructed with 423 //! std::forward<Args>(args)... if and only if there is 424 //! no element in the container with equivalent value. 425 //! p is a hint pointing to where the insert 426 //! should start to search. 427 //! 428 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 429 //! 430 //! <b>Complexity</b>: Logarithmic. 431 template <class... Args> emplace_hint(const_iterator p,BOOST_FWD_REF (Args)...args)432 iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 433 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); } 434 435 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 436 437 #define BOOST_CONTAINER_SET_EMPLACE_CODE(N) \ 438 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 439 std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ 440 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\ 441 \ 442 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 443 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 444 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 445 // 446 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SET_EMPLACE_CODE) 447 #undef BOOST_CONTAINER_SET_EMPLACE_CODE 448 449 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 450 451 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 452 //! <b>Effects</b>: Inserts x if and only if there is no element in the container 453 //! with key equivalent to the key of x. 454 //! 455 //! <b>Returns</b>: The bool component of the returned pair is true if and only 456 //! if the insertion takes place, and the iterator component of the pair 457 //! points to the element with key equivalent to the key of x. 458 //! 459 //! <b>Complexity</b>: Logarithmic. 460 std::pair<iterator, bool> insert(const value_type &x); 461 462 //! <b>Effects</b>: Move constructs a new value from x if and only if there is 463 //! no element in the container with key equivalent to the key of x. 464 //! 465 //! <b>Returns</b>: The bool component of the returned pair is true if and only 466 //! if the insertion takes place, and the iterator component of the pair 467 //! points to the element with key equivalent to the key of x. 468 //! 469 //! <b>Complexity</b>: Logarithmic. 470 std::pair<iterator, bool> insert(value_type &&x); 471 #else 472 private: 473 typedef std::pair<iterator, bool> insert_return_pair; 474 public: 475 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert) 476 #endif 477 478 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 479 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is 480 //! no element in the container with key equivalent to the key of x. 481 //! p is a hint pointing to where the insert should start to search. 482 //! 483 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 484 //! to the key of x. 485 //! 486 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 487 //! is inserted right before p. 488 iterator insert(const_iterator p, const value_type &x); 489 490 //! <b>Effects</b>: Inserts an element move constructed from x in the container. 491 //! p is a hint pointing to where the insert should start to search. 492 //! 493 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. 494 //! 495 //! <b>Complexity</b>: Logarithmic. 496 iterator insert(const_iterator p, value_type &&x); 497 #else 498 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator) 499 #endif 500 501 //! <b>Requires</b>: first, last are not iterators into *this. 502 //! 503 //! <b>Effects</b>: inserts each element from the range [first,last) if and only 504 //! if there is no element with key equivalent to the key of that element. 505 //! 506 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 507 template <class InputIterator> insert(InputIterator first,InputIterator last)508 void insert(InputIterator first, InputIterator last) 509 { this->base_t::insert_unique(first, last); } 510 511 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 512 //! <b>Effects</b>: inserts each element from the range [il.begin(),il.end()) if and only 513 //! if there is no element with key equivalent to the key of that element. 514 //! 515 //! <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)516 void insert(std::initializer_list<value_type> il) 517 { this->base_t::insert_unique(il.begin(), il.end()); } 518 #endif 519 520 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 521 522 //! <b>Effects</b>: Erases the element pointed to by p. 523 //! 524 //! <b>Returns</b>: Returns an iterator pointing to the element immediately 525 //! following q prior to the element being erased. If no such element exists, 526 //! returns end(). 527 //! 528 //! <b>Complexity</b>: Amortized constant time 529 iterator erase(const_iterator p); 530 531 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. 532 //! 533 //! <b>Returns</b>: Returns the number of erased elements. 534 //! 535 //! <b>Complexity</b>: log(size()) + count(k) 536 size_type erase(const key_type& x); 537 538 //! <b>Effects</b>: Erases all the elements in the range [first, last). 539 //! 540 //! <b>Returns</b>: Returns last. 541 //! 542 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. 543 iterator erase(const_iterator first, const_iterator last); 544 545 //! <b>Effects</b>: Swaps the contents of *this and x. 546 //! 547 //! <b>Throws</b>: Nothing. 548 //! 549 //! <b>Complexity</b>: Constant. 550 void swap(set& x) 551 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 552 && boost::container::container_detail::is_nothrow_swappable<Compare>::value ); 553 554 //! <b>Effects</b>: erase(a.begin(),a.end()). 555 //! 556 //! <b>Postcondition</b>: size() == 0. 557 //! 558 //! <b>Complexity</b>: linear in size(). 559 void clear(); 560 561 //! <b>Effects</b>: Returns the comparison object out 562 //! of which a was constructed. 563 //! 564 //! <b>Complexity</b>: Constant. 565 key_compare key_comp() const; 566 567 //! <b>Effects</b>: Returns an object of value_compare constructed out 568 //! of the comparison object. 569 //! 570 //! <b>Complexity</b>: Constant. 571 value_compare value_comp() const; 572 573 //! <b>Returns</b>: An iterator pointing to an element with the key 574 //! equivalent to x, or end() if such an element is not found. 575 //! 576 //! <b>Complexity</b>: Logarithmic. 577 iterator find(const key_type& x); 578 579 //! <b>Returns</b>: A const_iterator pointing to an element with the key 580 //! equivalent to x, or end() if such an element is not found. 581 //! 582 //! <b>Complexity</b>: Logarithmic. 583 const_iterator find(const key_type& x) const; 584 585 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 586 587 //! <b>Returns</b>: The number of elements with key equivalent to x. 588 //! 589 //! <b>Complexity</b>: log(size())+count(k) count(const key_type & x) const590 size_type count(const key_type& x) const 591 { return static_cast<size_type>(this->base_t::find(x) != this->base_t::cend()); } 592 593 //! <b>Returns</b>: The number of elements with key equivalent to x. 594 //! 595 //! <b>Complexity</b>: log(size())+count(k) count(const key_type & x)596 size_type count(const key_type& x) 597 { return static_cast<size_type>(this->base_t::find(x) != this->base_t::end()); } 598 599 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 600 601 //! <b>Returns</b>: An iterator pointing to the first element with key not less 602 //! than k, or a.end() if such an element is not found. 603 //! 604 //! <b>Complexity</b>: Logarithmic 605 iterator lower_bound(const key_type& x); 606 607 //! <b>Returns</b>: A const iterator pointing to the first element with key not 608 //! less than k, or a.end() if such an element is not found. 609 //! 610 //! <b>Complexity</b>: Logarithmic 611 const_iterator lower_bound(const key_type& x) const; 612 613 //! <b>Returns</b>: An iterator pointing to the first element with key not less 614 //! than x, or end() if such an element is not found. 615 //! 616 //! <b>Complexity</b>: Logarithmic 617 iterator upper_bound(const key_type& x); 618 619 //! <b>Returns</b>: A const iterator pointing to the first element with key not 620 //! less than x, or end() if such an element is not found. 621 //! 622 //! <b>Complexity</b>: Logarithmic 623 const_iterator upper_bound(const key_type& x) const; 624 625 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 626 627 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 628 //! 629 //! <b>Complexity</b>: Logarithmic equal_range(const key_type & x)630 std::pair<iterator,iterator> equal_range(const key_type& x) 631 { return this->base_t::lower_bound_range(x); } 632 633 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 634 //! 635 //! <b>Complexity</b>: Logarithmic equal_range(const key_type & x) const636 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const 637 { return this->base_t::lower_bound_range(x); } 638 639 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 640 641 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 642 //! 643 //! <b>Complexity</b>: Logarithmic 644 std::pair<iterator,iterator> equal_range(const key_type& x); 645 646 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 647 //! 648 //! <b>Complexity</b>: Logarithmic 649 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const; 650 651 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. 652 //! 653 //! <b>Complexity</b>: Linear 654 void rebalance(); 655 656 //! <b>Effects</b>: Returns true if x and y are equal 657 //! 658 //! <b>Complexity</b>: Linear to the number of elements in the container. 659 friend bool operator==(const set& x, const set& y); 660 661 //! <b>Effects</b>: Returns true if x and y are unequal 662 //! 663 //! <b>Complexity</b>: Linear to the number of elements in the container. 664 friend bool operator!=(const set& x, const set& y); 665 666 //! <b>Effects</b>: Returns true if x is less than y 667 //! 668 //! <b>Complexity</b>: Linear to the number of elements in the container. 669 friend bool operator<(const set& x, const set& y); 670 671 //! <b>Effects</b>: Returns true if x is greater than y 672 //! 673 //! <b>Complexity</b>: Linear to the number of elements in the container. 674 friend bool operator>(const set& x, const set& y); 675 676 //! <b>Effects</b>: Returns true if x is equal or less than y 677 //! 678 //! <b>Complexity</b>: Linear to the number of elements in the container. 679 friend bool operator<=(const set& x, const set& y); 680 681 //! <b>Effects</b>: Returns true if x is equal or greater than y 682 //! 683 //! <b>Complexity</b>: Linear to the number of elements in the container. 684 friend bool operator>=(const set& x, const set& y); 685 686 //! <b>Effects</b>: x.swap(y) 687 //! 688 //! <b>Complexity</b>: Constant. 689 friend void swap(set& x, set& y); 690 691 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 692 693 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 694 private: 695 template <class KeyType> priv_insert(BOOST_FWD_REF (KeyType)x)696 std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x) 697 { return this->base_t::insert_unique(::boost::forward<KeyType>(x)); } 698 699 template <class KeyType> priv_insert(const_iterator p,BOOST_FWD_REF (KeyType)x)700 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x) 701 { return this->base_t::insert_unique(p, ::boost::forward<KeyType>(x)); } 702 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 703 }; 704 705 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 706 707 } //namespace container { 708 709 //!has_trivial_destructor_after_move<> == true_type 710 //!specialization for optimizations 711 template <class Key, class Compare, class SetOptions, class Allocator> 712 struct has_trivial_destructor_after_move<boost::container::set<Key, Compare, Allocator, SetOptions> > 713 { 714 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 715 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 716 ::boost::has_trivial_destructor_after_move<pointer>::value && 717 ::boost::has_trivial_destructor_after_move<Compare>::value; 718 }; 719 720 namespace container { 721 722 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 723 724 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 725 726 //! A multiset is a kind of associative container that supports equivalent keys 727 //! (possibly contains multiple copies of the same key value) and provides for 728 //! fast retrieval of the keys themselves. Class multiset supports bidirectional iterators. 729 //! 730 //! A multiset satisfies all of the requirements of a container and of a reversible 731 //! container, and of an associative container). multiset also provides most operations 732 //! described for duplicate keys. 733 //! 734 //! \tparam Key is the type to be inserted in the set, which is also the key_type 735 //! \tparam Compare is the comparison functor used to order keys 736 //! \tparam Allocator is the allocator to be used to allocate memory for this container 737 //! \tparam MultiSetOptions is an packed option type generated using using boost::container::tree_assoc_options. 738 template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key>, class MultiSetOptions = tree_assoc_defaults > 739 #else 740 template <class Key, class Compare, class Allocator, class MultiSetOptions> 741 #endif 742 class multiset 743 /// @cond 744 : public container_detail::tree 745 <Key, Key,container_detail::identity<Key>, Compare, Allocator, MultiSetOptions> 746 /// @endcond 747 { 748 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 749 private: 750 BOOST_COPYABLE_AND_MOVABLE(multiset) 751 typedef container_detail::tree 752 <Key, Key,container_detail::identity<Key>, Compare, Allocator, MultiSetOptions> base_t; 753 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 754 755 public: 756 757 ////////////////////////////////////////////// 758 // 759 // types 760 // 761 ////////////////////////////////////////////// 762 typedef Key key_type; 763 typedef Key value_type; 764 typedef Compare key_compare; 765 typedef Compare value_compare; 766 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; 767 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 768 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; 769 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; 770 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; 771 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; 772 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; 773 typedef Allocator allocator_type; 774 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; 775 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; 776 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; 777 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; 778 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; 779 780 ////////////////////////////////////////////// 781 // 782 // construct/copy/destroy 783 // 784 ////////////////////////////////////////////// 785 786 //! @copydoc ::boost::container::set::set() multiset()787 multiset() 788 : base_t() 789 {} 790 791 //! @copydoc ::boost::container::set::set(const Compare&, const allocator_type&) multiset(const Compare & comp,const allocator_type & a=allocator_type ())792 explicit multiset(const Compare& comp, 793 const allocator_type& a = allocator_type()) 794 : base_t(comp, a) 795 {} 796 797 //! @copydoc ::boost::container::set::set(const allocator_type&) multiset(const allocator_type & a)798 explicit multiset(const allocator_type& a) 799 : base_t(a) 800 {} 801 802 //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const Compare& comp, const allocator_type&) 803 template <class InputIterator> multiset(InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())804 multiset(InputIterator first, InputIterator last, 805 const Compare& comp = Compare(), 806 const allocator_type& a = allocator_type()) 807 : base_t(false, first, last, comp, a) 808 {} 809 810 //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const allocator_type&) 811 template <class InputIterator> multiset(InputIterator first,InputIterator last,const allocator_type & a)812 multiset(InputIterator first, InputIterator last, const allocator_type& a) 813 : base_t(false, first, last, key_compare(), a) 814 {} 815 816 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and 817 //! allocator, and inserts elements from the ordered range [first ,last ). This function 818 //! is more efficient than the normal range creation for ordered ranges. 819 //! 820 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate. 821 //! 822 //! <b>Complexity</b>: Linear in N. 823 //! 824 //! <b>Note</b>: Non-standard extension. 825 template <class InputIterator> multiset(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())826 multiset( ordered_range_t, InputIterator first, InputIterator last 827 , const Compare& comp = Compare() 828 , const allocator_type& a = allocator_type()) 829 : base_t(ordered_range, first, last, comp, a) 830 {} 831 832 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 833 //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const Compare& comp, const allocator_type&) multiset(std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())834 multiset(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) 835 : base_t(false, il.begin(), il.end(), comp, a) 836 {} 837 838 //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const allocator_type&) multiset(std::initializer_list<value_type> il,const allocator_type & a)839 multiset(std::initializer_list<value_type> il, const allocator_type& a) 840 : base_t(false, il.begin(), il.end(), Compare(), a) 841 {} 842 843 //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare& comp, const allocator_type&) multiset(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp=Compare (),const allocator_type & a=allocator_type ())844 multiset(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) 845 : base_t(ordered_range, il.begin(), il.end(), comp, a) 846 {} 847 #endif 848 849 //! @copydoc ::boost::container::set::set(const set &) multiset(const multiset & x)850 multiset(const multiset& x) 851 : base_t(static_cast<const base_t&>(x)) 852 {} 853 854 //! @copydoc ::boost::container::set(set &&) multiset(BOOST_RV_REF (multiset)x)855 multiset(BOOST_RV_REF(multiset) x) 856 : base_t(BOOST_MOVE_BASE(base_t, x)) 857 {} 858 859 //! @copydoc ::boost::container::set(const set &, const allocator_type &) multiset(const multiset & x,const allocator_type & a)860 multiset(const multiset& x, const allocator_type &a) 861 : base_t(static_cast<const base_t&>(x), a) 862 {} 863 864 //! @copydoc ::boost::container::set(set &&, const allocator_type &) multiset(BOOST_RV_REF (multiset)x,const allocator_type & a)865 multiset(BOOST_RV_REF(multiset) x, const allocator_type &a) 866 : base_t(BOOST_MOVE_BASE(base_t, x), a) 867 {} 868 869 //! @copydoc ::boost::container::set::operator=(const set &) operator =(BOOST_COPY_ASSIGN_REF (multiset)x)870 multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x) 871 { return static_cast<multiset&>(this->base_t::operator=(static_cast<const base_t&>(x))); } 872 873 //! @copydoc ::boost::container::set::operator=(set &&) operator =(BOOST_RV_REF (multiset)x)874 multiset& operator=(BOOST_RV_REF(multiset) x) 875 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 876 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) 877 { return static_cast<multiset&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } 878 879 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 880 //! @copydoc ::boost::container::set::operator=(std::initializer_list<value_type>) operator =(std::initializer_list<value_type> il)881 multiset& operator=(std::initializer_list<value_type> il) 882 { 883 this->clear(); 884 insert(il.begin(), il.end()); 885 return *this; 886 } 887 #endif 888 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 889 890 //! @copydoc ::boost::container::set::get_allocator() 891 allocator_type get_allocator() const; 892 893 //! @copydoc ::boost::container::set::get_stored_allocator() 894 stored_allocator_type &get_stored_allocator(); 895 896 //! @copydoc ::boost::container::set::get_stored_allocator() const 897 const stored_allocator_type &get_stored_allocator() const; 898 899 //! @copydoc ::boost::container::set::begin() 900 iterator begin(); 901 902 //! @copydoc ::boost::container::set::begin() const 903 const_iterator begin() const; 904 905 //! @copydoc ::boost::container::set::cbegin() const 906 const_iterator cbegin() const; 907 908 //! @copydoc ::boost::container::set::end() 909 iterator end() BOOST_NOEXCEPT_OR_NOTHROW; 910 911 //! @copydoc ::boost::container::set::end() const 912 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; 913 914 //! @copydoc ::boost::container::set::cend() const 915 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; 916 917 //! @copydoc ::boost::container::set::rbegin() 918 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; 919 920 //! @copydoc ::boost::container::set::rbegin() const 921 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 922 923 //! @copydoc ::boost::container::set::crbegin() const 924 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; 925 926 //! @copydoc ::boost::container::set::rend() 927 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; 928 929 //! @copydoc ::boost::container::set::rend() const 930 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; 931 932 //! @copydoc ::boost::container::set::crend() const 933 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; 934 935 //! @copydoc ::boost::container::set::empty() const 936 bool empty() const; 937 938 //! @copydoc ::boost::container::set::size() const 939 size_type size() const; 940 941 //! @copydoc ::boost::container::set::max_size() const 942 size_type max_size() const; 943 944 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 945 946 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 947 948 //! <b>Effects</b>: Inserts an object of type Key constructed with 949 //! std::forward<Args>(args)... and returns the iterator pointing to the 950 //! newly inserted element. 951 //! 952 //! <b>Complexity</b>: Logarithmic. 953 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)954 iterator emplace(BOOST_FWD_REF(Args)... args) 955 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); } 956 957 //! <b>Effects</b>: Inserts an object of type Key constructed with 958 //! std::forward<Args>(args)... 959 //! 960 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 961 //! to the key of x. 962 //! 963 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 964 //! is inserted right before p. 965 template <class... Args> emplace_hint(const_iterator p,BOOST_FWD_REF (Args)...args)966 iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) 967 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); } 968 969 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 970 971 #define BOOST_CONTAINER_MULTISET_EMPLACE_CODE(N) \ 972 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 973 iterator emplace(BOOST_MOVE_UREF##N)\ 974 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\ 975 \ 976 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 977 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 978 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 979 // 980 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTISET_EMPLACE_CODE) 981 #undef BOOST_CONTAINER_MULTISET_EMPLACE_CODE 982 983 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 984 985 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 986 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the 987 //! newly inserted element. 988 //! 989 //! <b>Complexity</b>: Logarithmic. 990 iterator insert(const value_type &x); 991 992 //! <b>Effects</b>: Inserts a copy of x in the container. 993 //! 994 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 995 //! to the key of x. 996 //! 997 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 998 //! is inserted right before p. 999 iterator insert(value_type &&x); 1000 #else 1001 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert) 1002 #endif 1003 1004 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1005 //! <b>Effects</b>: Inserts a copy of x in the container. 1006 //! p is a hint pointing to where the insert should start to search. 1007 //! 1008 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1009 //! to the key of x. 1010 //! 1011 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1012 //! is inserted right before p. 1013 iterator insert(const_iterator p, const value_type &x); 1014 1015 //! <b>Effects</b>: Inserts a value move constructed from x in the container. 1016 //! p is a hint pointing to where the insert should start to search. 1017 //! 1018 //! <b>Returns</b>: An iterator pointing to the element with key equivalent 1019 //! to the key of x. 1020 //! 1021 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t 1022 //! is inserted right before p. 1023 iterator insert(const_iterator p, value_type &&x); 1024 #else 1025 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator) 1026 #endif 1027 1028 //! <b>Requires</b>: first, last are not iterators into *this. 1029 //! 1030 //! <b>Effects</b>: inserts each element from the range [first,last) . 1031 //! 1032 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) 1033 template <class InputIterator> insert(InputIterator first,InputIterator last)1034 void insert(InputIterator first, InputIterator last) 1035 { this->base_t::insert_equal(first, last); } 1036 1037 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1038 //! @copydoc ::boost::container::set::insert(std::initializer_list<value_type>) insert(std::initializer_list<value_type> il)1039 void insert(std::initializer_list<value_type> il) 1040 { this->base_t::insert_equal(il.begin(), il.end()); } 1041 #endif 1042 1043 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1044 1045 //! @copydoc ::boost::container::set::erase(const_iterator) 1046 iterator erase(const_iterator p); 1047 1048 //! @copydoc ::boost::container::set::erase(const key_type&) 1049 size_type erase(const key_type& x); 1050 1051 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator) 1052 iterator erase(const_iterator first, const_iterator last); 1053 1054 //! @copydoc ::boost::container::set::swap 1055 void swap(multiset& x) 1056 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1057 && boost::container::container_detail::is_nothrow_swappable<Compare>::value ); 1058 1059 //! @copydoc ::boost::container::set::clear 1060 void clear() BOOST_NOEXCEPT_OR_NOTHROW; 1061 1062 //! @copydoc ::boost::container::set::key_comp 1063 key_compare key_comp() const; 1064 1065 //! @copydoc ::boost::container::set::value_comp 1066 value_compare value_comp() const; 1067 1068 //! @copydoc ::boost::container::set::find(const key_type& ) 1069 iterator find(const key_type& x); 1070 1071 //! @copydoc ::boost::container::set::find(const key_type& ) const 1072 const_iterator find(const key_type& x) const; 1073 1074 //! @copydoc ::boost::container::set::count(const key_type& ) const 1075 size_type count(const key_type& x) const; 1076 1077 //! @copydoc ::boost::container::set::lower_bound(const key_type& ) 1078 iterator lower_bound(const key_type& x); 1079 1080 //! @copydoc ::boost::container::set::lower_bound(const key_type& ) const 1081 const_iterator lower_bound(const key_type& x) const; 1082 1083 //! @copydoc ::boost::container::set::upper_bound(const key_type& ) 1084 iterator upper_bound(const key_type& x); 1085 1086 //! @copydoc ::boost::container::set::upper_bound(const key_type& ) const 1087 const_iterator upper_bound(const key_type& x) const; 1088 1089 //! @copydoc ::boost::container::set::equal_range(const key_type& ) const 1090 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const; 1091 1092 //! @copydoc ::boost::container::set::equal_range(const key_type& ) 1093 std::pair<iterator,iterator> equal_range(const key_type& x); 1094 1095 //! @copydoc ::boost::container::set::rebalance() 1096 void rebalance(); 1097 1098 //! <b>Effects</b>: Returns true if x and y are equal 1099 //! 1100 //! <b>Complexity</b>: Linear to the number of elements in the container. 1101 friend bool operator==(const multiset& x, const multiset& y); 1102 1103 //! <b>Effects</b>: Returns true if x and y are unequal 1104 //! 1105 //! <b>Complexity</b>: Linear to the number of elements in the container. 1106 friend bool operator!=(const multiset& x, const multiset& y); 1107 1108 //! <b>Effects</b>: Returns true if x is less than y 1109 //! 1110 //! <b>Complexity</b>: Linear to the number of elements in the container. 1111 friend bool operator<(const multiset& x, const multiset& y); 1112 1113 //! <b>Effects</b>: Returns true if x is greater than y 1114 //! 1115 //! <b>Complexity</b>: Linear to the number of elements in the container. 1116 friend bool operator>(const multiset& x, const multiset& y); 1117 1118 //! <b>Effects</b>: Returns true if x is equal or less than y 1119 //! 1120 //! <b>Complexity</b>: Linear to the number of elements in the container. 1121 friend bool operator<=(const multiset& x, const multiset& y); 1122 1123 //! <b>Effects</b>: Returns true if x is equal or greater than y 1124 //! 1125 //! <b>Complexity</b>: Linear to the number of elements in the container. 1126 friend bool operator>=(const multiset& x, const multiset& y); 1127 1128 //! <b>Effects</b>: x.swap(y) 1129 //! 1130 //! <b>Complexity</b>: Constant. 1131 friend void swap(multiset& x, multiset& y); 1132 1133 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1134 1135 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1136 private: 1137 template <class KeyType> priv_insert(BOOST_FWD_REF (KeyType)x)1138 iterator priv_insert(BOOST_FWD_REF(KeyType) x) 1139 { return this->base_t::insert_equal(::boost::forward<KeyType>(x)); } 1140 1141 template <class KeyType> priv_insert(const_iterator p,BOOST_FWD_REF (KeyType)x)1142 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x) 1143 { return this->base_t::insert_equal(p, ::boost::forward<KeyType>(x)); } 1144 1145 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1146 }; 1147 1148 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1149 1150 } //namespace container { 1151 1152 //!has_trivial_destructor_after_move<> == true_type 1153 //!specialization for optimizations 1154 template <class Key, class Compare, class Allocator, class MultiSetOptions> 1155 struct has_trivial_destructor_after_move<boost::container::multiset<Key, Compare, Allocator, MultiSetOptions> > 1156 { 1157 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 1158 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 1159 ::boost::has_trivial_destructor_after_move<pointer>::value && 1160 ::boost::has_trivial_destructor_after_move<Compare>::value; 1161 }; 1162 1163 namespace container { 1164 1165 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1166 1167 }} 1168 1169 #include <boost/container/detail/config_end.hpp> 1170 1171 #endif // BOOST_CONTAINER_SET_HPP 1172