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