1 // Multiset implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file stl_multiset.h 53 * This is an internal header file, included by other library headers. 54 * You should not attempt to use it directly. 55 */ 56 57 #ifndef _STL_MULTISET_H 58 #define _STL_MULTISET_H 1 59 60 #include <bits/concept_check.h> 61 #include <initializer_list> 62 63 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 64 65 /** 66 * @brief A standard container made up of elements, which can be retrieved 67 * in logarithmic time. 68 * 69 * @ingroup associative_containers 70 * 71 * Meets the requirements of a <a href="tables.html#65">container</a>, a 72 * <a href="tables.html#66">reversible container</a>, and an 73 * <a href="tables.html#69">associative container</a> (using equivalent 74 * keys). For a @c multiset<Key> the key_type and value_type are Key. 75 * 76 * Multisets support bidirectional iterators. 77 * 78 * The private tree data is declared exactly the same way for set and 79 * multiset; the distinction is made entirely in how the tree functions are 80 * called (*_unique versus *_equal, same as the standard). 81 */ 82 template <typename _Key, typename _Compare = std::less<_Key>, 83 typename _Alloc = std::allocator<_Key> > 84 class multiset 85 { 86 // concept requirements 87 typedef typename _Alloc::value_type _Alloc_value_type; 88 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 89 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 90 _BinaryFunctionConcept) 91 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 92 93 public: 94 // typedefs: 95 typedef _Key key_type; 96 typedef _Key value_type; 97 typedef _Compare key_compare; 98 typedef _Compare value_compare; 99 typedef _Alloc allocator_type; 100 101 private: 102 /// This turns a red-black tree into a [multi]set. 103 typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type; 104 105 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 106 key_compare, _Key_alloc_type> _Rep_type; 107 /// The actual tree structure. 108 _Rep_type _M_t; 109 110 public: 111 typedef typename _Key_alloc_type::pointer pointer; 112 typedef typename _Key_alloc_type::const_pointer const_pointer; 113 typedef typename _Key_alloc_type::reference reference; 114 typedef typename _Key_alloc_type::const_reference const_reference; 115 // _GLIBCXX_RESOLVE_LIB_DEFECTS 116 // DR 103. set::iterator is required to be modifiable, 117 // but this allows modification of keys. 118 typedef typename _Rep_type::const_iterator iterator; 119 typedef typename _Rep_type::const_iterator const_iterator; 120 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 121 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 122 typedef typename _Rep_type::size_type size_type; 123 typedef typename _Rep_type::difference_type difference_type; 124 125 // allocation/deallocation 126 /** 127 * @brief Default constructor creates no elements. 128 */ 129 multiset() 130 : _M_t() { } 131 132 /** 133 * @brief Creates a %multiset with no elements. 134 * @param comp Comparator to use. 135 * @param a An allocator object. 136 */ 137 explicit 138 multiset(const _Compare& __comp, 139 const allocator_type& __a = allocator_type()) 140 : _M_t(__comp, __a) { } 141 142 /** 143 * @brief Builds a %multiset from a range. 144 * @param first An input iterator. 145 * @param last An input iterator. 146 * 147 * Create a %multiset consisting of copies of the elements from 148 * [first,last). This is linear in N if the range is already sorted, 149 * and NlogN otherwise (where N is distance(first,last)). 150 */ 151 template<typename _InputIterator> 152 multiset(_InputIterator __first, _InputIterator __last) 153 : _M_t() 154 { _M_t._M_insert_equal(__first, __last); } 155 156 /** 157 * @brief Builds a %multiset from a range. 158 * @param first An input iterator. 159 * @param last An input iterator. 160 * @param comp A comparison functor. 161 * @param a An allocator object. 162 * 163 * Create a %multiset consisting of copies of the elements from 164 * [first,last). This is linear in N if the range is already sorted, 165 * and NlogN otherwise (where N is distance(first,last)). 166 */ 167 template<typename _InputIterator> 168 multiset(_InputIterator __first, _InputIterator __last, 169 const _Compare& __comp, 170 const allocator_type& __a = allocator_type()) 171 : _M_t(__comp, __a) 172 { _M_t._M_insert_equal(__first, __last); } 173 174 /** 175 * @brief %Multiset copy constructor. 176 * @param x A %multiset of identical element and allocator types. 177 * 178 * The newly-created %multiset uses a copy of the allocation object used 179 * by @a x. 180 */ 181 multiset(const multiset& __x) 182 : _M_t(__x._M_t) { } 183 184 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 185 /** 186 * @brief %Multiset move constructor. 187 * @param x A %multiset of identical element and allocator types. 188 * 189 * The newly-created %multiset contains the exact contents of @a x. 190 * The contents of @a x are a valid, but unspecified %multiset. 191 */ 192 multiset(multiset&& __x) 193 : _M_t(std::forward<_Rep_type>(__x._M_t)) { } 194 195 /** 196 * @brief Builds a %multiset from an initializer_list. 197 * @param l An initializer_list. 198 * @param comp A comparison functor. 199 * @param a An allocator object. 200 * 201 * Create a %multiset consisting of copies of the elements from 202 * the list. This is linear in N if the list is already sorted, 203 * and NlogN otherwise (where N is @a l.size()). 204 */ 205 multiset(initializer_list<value_type> __l, 206 const _Compare& __comp = _Compare(), 207 const allocator_type& __a = allocator_type()) 208 : _M_t(__comp, __a) 209 { _M_t._M_insert_equal(__l.begin(), __l.end()); } 210 #endif 211 212 /** 213 * @brief %Multiset assignment operator. 214 * @param x A %multiset of identical element and allocator types. 215 * 216 * All the elements of @a x are copied, but unlike the copy constructor, 217 * the allocator object is not copied. 218 */ 219 multiset& 220 operator=(const multiset& __x) 221 { 222 _M_t = __x._M_t; 223 return *this; 224 } 225 226 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 227 /** 228 * @brief %Multiset move assignment operator. 229 * @param x A %multiset of identical element and allocator types. 230 * 231 * The contents of @a x are moved into this %multiset (without copying). 232 * @a x is a valid, but unspecified %multiset. 233 */ 234 multiset& 235 operator=(multiset&& __x) 236 { 237 // NB: DR 675. 238 this->clear(); 239 this->swap(__x); 240 return *this; 241 } 242 243 /** 244 * @brief %Multiset list assignment operator. 245 * @param l An initializer_list. 246 * 247 * This function fills a %multiset with copies of the elements in the 248 * initializer list @a l. 249 * 250 * Note that the assignment completely changes the %multiset and 251 * that the resulting %multiset's size is the same as the number 252 * of elements assigned. Old data may be lost. 253 */ 254 multiset& 255 operator=(initializer_list<value_type> __l) 256 { 257 this->clear(); 258 this->insert(__l.begin(), __l.end()); 259 return *this; 260 } 261 #endif 262 263 // accessors: 264 265 /// Returns the comparison object. 266 key_compare 267 key_comp() const 268 { return _M_t.key_comp(); } 269 /// Returns the comparison object. 270 value_compare 271 value_comp() const 272 { return _M_t.key_comp(); } 273 /// Returns the memory allocation object. 274 allocator_type 275 get_allocator() const 276 { return _M_t.get_allocator(); } 277 278 /** 279 * Returns a read-only (constant) iterator that points to the first 280 * element in the %multiset. Iteration is done in ascending order 281 * according to the keys. 282 */ 283 iterator 284 begin() const 285 { return _M_t.begin(); } 286 287 /** 288 * Returns a read-only (constant) iterator that points one past the last 289 * element in the %multiset. Iteration is done in ascending order 290 * according to the keys. 291 */ 292 iterator 293 end() const 294 { return _M_t.end(); } 295 296 /** 297 * Returns a read-only (constant) reverse iterator that points to the 298 * last element in the %multiset. Iteration is done in descending order 299 * according to the keys. 300 */ 301 reverse_iterator 302 rbegin() const 303 { return _M_t.rbegin(); } 304 305 /** 306 * Returns a read-only (constant) reverse iterator that points to the 307 * last element in the %multiset. Iteration is done in descending order 308 * according to the keys. 309 */ 310 reverse_iterator 311 rend() const 312 { return _M_t.rend(); } 313 314 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 315 /** 316 * Returns a read-only (constant) iterator that points to the first 317 * element in the %multiset. Iteration is done in ascending order 318 * according to the keys. 319 */ 320 iterator 321 cbegin() const 322 { return _M_t.begin(); } 323 324 /** 325 * Returns a read-only (constant) iterator that points one past the last 326 * element in the %multiset. Iteration is done in ascending order 327 * according to the keys. 328 */ 329 iterator 330 cend() const 331 { return _M_t.end(); } 332 333 /** 334 * Returns a read-only (constant) reverse iterator that points to the 335 * last element in the %multiset. Iteration is done in descending order 336 * according to the keys. 337 */ 338 reverse_iterator 339 crbegin() const 340 { return _M_t.rbegin(); } 341 342 /** 343 * Returns a read-only (constant) reverse iterator that points to the 344 * last element in the %multiset. Iteration is done in descending order 345 * according to the keys. 346 */ 347 reverse_iterator 348 crend() const 349 { return _M_t.rend(); } 350 #endif 351 352 /// Returns true if the %set is empty. 353 bool 354 empty() const 355 { return _M_t.empty(); } 356 357 /// Returns the size of the %set. 358 size_type 359 size() const 360 { return _M_t.size(); } 361 362 /// Returns the maximum size of the %set. 363 size_type 364 max_size() const 365 { return _M_t.max_size(); } 366 367 /** 368 * @brief Swaps data with another %multiset. 369 * @param x A %multiset of the same element and allocator types. 370 * 371 * This exchanges the elements between two multisets in constant time. 372 * (It is only swapping a pointer, an integer, and an instance of the @c 373 * Compare type (which itself is often stateless and empty), so it should 374 * be quite fast.) 375 * Note that the global std::swap() function is specialized such that 376 * std::swap(s1,s2) will feed to this function. 377 */ 378 void 379 swap(multiset& __x) 380 { _M_t.swap(__x._M_t); } 381 382 // insert/erase 383 /** 384 * @brief Inserts an element into the %multiset. 385 * @param x Element to be inserted. 386 * @return An iterator that points to the inserted element. 387 * 388 * This function inserts an element into the %multiset. Contrary 389 * to a std::set the %multiset does not rely on unique keys and thus 390 * multiple copies of the same element can be inserted. 391 * 392 * Insertion requires logarithmic time. 393 */ 394 iterator 395 insert(const value_type& __x) 396 { return _M_t._M_insert_equal(__x); } 397 398 /** 399 * @brief Inserts an element into the %multiset. 400 * @param position An iterator that serves as a hint as to where the 401 * element should be inserted. 402 * @param x Element to be inserted. 403 * @return An iterator that points to the inserted element. 404 * 405 * This function inserts an element into the %multiset. Contrary 406 * to a std::set the %multiset does not rely on unique keys and thus 407 * multiple copies of the same element can be inserted. 408 * 409 * Note that the first parameter is only a hint and can potentially 410 * improve the performance of the insertion process. A bad hint would 411 * cause no gains in efficiency. 412 * 413 * See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 414 * for more on "hinting". 415 * 416 * Insertion requires logarithmic time (if the hint is not taken). 417 */ 418 iterator 419 insert(iterator __position, const value_type& __x) 420 { return _M_t._M_insert_equal_(__position, __x); } 421 422 /** 423 * @brief A template function that attempts to insert a range of elements. 424 * @param first Iterator pointing to the start of the range to be 425 * inserted. 426 * @param last Iterator pointing to the end of the range. 427 * 428 * Complexity similar to that of the range constructor. 429 */ 430 template<typename _InputIterator> 431 void 432 insert(_InputIterator __first, _InputIterator __last) 433 { _M_t._M_insert_equal(__first, __last); } 434 435 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 436 /** 437 * @brief Attempts to insert a list of elements into the %multiset. 438 * @param list A std::initializer_list<value_type> of elements 439 * to be inserted. 440 * 441 * Complexity similar to that of the range constructor. 442 */ 443 void 444 insert(initializer_list<value_type> __l) 445 { this->insert(__l.begin(), __l.end()); } 446 #endif 447 448 /** 449 * @brief Erases an element from a %multiset. 450 * @param position An iterator pointing to the element to be erased. 451 * 452 * This function erases an element, pointed to by the given iterator, 453 * from a %multiset. Note that this function only erases the element, 454 * and that if the element is itself a pointer, the pointed-to memory is 455 * not touched in any way. Managing the pointer is the user's 456 * responsibility. 457 */ 458 void 459 erase(iterator __position) 460 { _M_t.erase(__position); } 461 462 /** 463 * @brief Erases elements according to the provided key. 464 * @param x Key of element to be erased. 465 * @return The number of elements erased. 466 * 467 * This function erases all elements located by the given key from a 468 * %multiset. 469 * Note that this function only erases the element, and that if 470 * the element is itself a pointer, the pointed-to memory is not touched 471 * in any way. Managing the pointer is the user's responsibility. 472 */ 473 size_type 474 erase(const key_type& __x) 475 { return _M_t.erase(__x); } 476 477 /** 478 * @brief Erases a [first,last) range of elements from a %multiset. 479 * @param first Iterator pointing to the start of the range to be 480 * erased. 481 * @param last Iterator pointing to the end of the range to be erased. 482 * 483 * This function erases a sequence of elements from a %multiset. 484 * Note that this function only erases the elements, and that if 485 * the elements themselves are pointers, the pointed-to memory is not 486 * touched in any way. Managing the pointer is the user's responsibility. 487 */ 488 void 489 erase(iterator __first, iterator __last) 490 { _M_t.erase(__first, __last); } 491 492 /** 493 * Erases all elements in a %multiset. Note that this function only 494 * erases the elements, and that if the elements themselves are pointers, 495 * the pointed-to memory is not touched in any way. Managing the pointer 496 * is the user's responsibility. 497 */ 498 void 499 clear() 500 { _M_t.clear(); } 501 502 // multiset operations: 503 504 /** 505 * @brief Finds the number of elements with given key. 506 * @param x Key of elements to be located. 507 * @return Number of elements with specified key. 508 */ 509 size_type 510 count(const key_type& __x) const 511 { return _M_t.count(__x); } 512 513 // _GLIBCXX_RESOLVE_LIB_DEFECTS 514 // 214. set::find() missing const overload 515 //@{ 516 /** 517 * @brief Tries to locate an element in a %set. 518 * @param x Element to be located. 519 * @return Iterator pointing to sought-after element, or end() if not 520 * found. 521 * 522 * This function takes a key and tries to locate the element with which 523 * the key matches. If successful the function returns an iterator 524 * pointing to the sought after element. If unsuccessful it returns the 525 * past-the-end ( @c end() ) iterator. 526 */ 527 iterator 528 find(const key_type& __x) 529 { return _M_t.find(__x); } 530 531 const_iterator 532 find(const key_type& __x) const 533 { return _M_t.find(__x); } 534 //@} 535 536 //@{ 537 /** 538 * @brief Finds the beginning of a subsequence matching given key. 539 * @param x Key to be located. 540 * @return Iterator pointing to first element equal to or greater 541 * than key, or end(). 542 * 543 * This function returns the first element of a subsequence of elements 544 * that matches the given key. If unsuccessful it returns an iterator 545 * pointing to the first element that has a greater value than given key 546 * or end() if no such element exists. 547 */ 548 iterator 549 lower_bound(const key_type& __x) 550 { return _M_t.lower_bound(__x); } 551 552 const_iterator 553 lower_bound(const key_type& __x) const 554 { return _M_t.lower_bound(__x); } 555 //@} 556 557 //@{ 558 /** 559 * @brief Finds the end of a subsequence matching given key. 560 * @param x Key to be located. 561 * @return Iterator pointing to the first element 562 * greater than key, or end(). 563 */ 564 iterator 565 upper_bound(const key_type& __x) 566 { return _M_t.upper_bound(__x); } 567 568 const_iterator 569 upper_bound(const key_type& __x) const 570 { return _M_t.upper_bound(__x); } 571 //@} 572 573 //@{ 574 /** 575 * @brief Finds a subsequence matching given key. 576 * @param x Key to be located. 577 * @return Pair of iterators that possibly points to the subsequence 578 * matching given key. 579 * 580 * This function is equivalent to 581 * @code 582 * std::make_pair(c.lower_bound(val), 583 * c.upper_bound(val)) 584 * @endcode 585 * (but is faster than making the calls separately). 586 * 587 * This function probably only makes sense for multisets. 588 */ 589 std::pair<iterator, iterator> 590 equal_range(const key_type& __x) 591 { return _M_t.equal_range(__x); } 592 593 std::pair<const_iterator, const_iterator> 594 equal_range(const key_type& __x) const 595 { return _M_t.equal_range(__x); } 596 597 template<typename _K1, typename _C1, typename _A1> 598 friend bool 599 operator==(const multiset<_K1, _C1, _A1>&, 600 const multiset<_K1, _C1, _A1>&); 601 602 template<typename _K1, typename _C1, typename _A1> 603 friend bool 604 operator< (const multiset<_K1, _C1, _A1>&, 605 const multiset<_K1, _C1, _A1>&); 606 }; 607 608 /** 609 * @brief Multiset equality comparison. 610 * @param x A %multiset. 611 * @param y A %multiset of the same type as @a x. 612 * @return True iff the size and elements of the multisets are equal. 613 * 614 * This is an equivalence relation. It is linear in the size of the 615 * multisets. 616 * Multisets are considered equivalent if their sizes are equal, and if 617 * corresponding elements compare equal. 618 */ 619 template<typename _Key, typename _Compare, typename _Alloc> 620 inline bool 621 operator==(const multiset<_Key, _Compare, _Alloc>& __x, 622 const multiset<_Key, _Compare, _Alloc>& __y) 623 { return __x._M_t == __y._M_t; } 624 625 /** 626 * @brief Multiset ordering relation. 627 * @param x A %multiset. 628 * @param y A %multiset of the same type as @a x. 629 * @return True iff @a x is lexicographically less than @a y. 630 * 631 * This is a total ordering relation. It is linear in the size of the 632 * maps. The elements must be comparable with @c <. 633 * 634 * See std::lexicographical_compare() for how the determination is made. 635 */ 636 template<typename _Key, typename _Compare, typename _Alloc> 637 inline bool 638 operator<(const multiset<_Key, _Compare, _Alloc>& __x, 639 const multiset<_Key, _Compare, _Alloc>& __y) 640 { return __x._M_t < __y._M_t; } 641 642 /// Returns !(x == y). 643 template<typename _Key, typename _Compare, typename _Alloc> 644 inline bool 645 operator!=(const multiset<_Key, _Compare, _Alloc>& __x, 646 const multiset<_Key, _Compare, _Alloc>& __y) 647 { return !(__x == __y); } 648 649 /// Returns y < x. 650 template<typename _Key, typename _Compare, typename _Alloc> 651 inline bool 652 operator>(const multiset<_Key,_Compare,_Alloc>& __x, 653 const multiset<_Key,_Compare,_Alloc>& __y) 654 { return __y < __x; } 655 656 /// Returns !(y < x) 657 template<typename _Key, typename _Compare, typename _Alloc> 658 inline bool 659 operator<=(const multiset<_Key, _Compare, _Alloc>& __x, 660 const multiset<_Key, _Compare, _Alloc>& __y) 661 { return !(__y < __x); } 662 663 /// Returns !(x < y) 664 template<typename _Key, typename _Compare, typename _Alloc> 665 inline bool 666 operator>=(const multiset<_Key, _Compare, _Alloc>& __x, 667 const multiset<_Key, _Compare, _Alloc>& __y) 668 { return !(__x < __y); } 669 670 /// See std::multiset::swap(). 671 template<typename _Key, typename _Compare, typename _Alloc> 672 inline void 673 swap(multiset<_Key, _Compare, _Alloc>& __x, 674 multiset<_Key, _Compare, _Alloc>& __y) 675 { __x.swap(__y); } 676 677 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 678 template<typename _Key, typename _Compare, typename _Alloc> 679 inline void 680 swap(multiset<_Key, _Compare, _Alloc>&& __x, 681 multiset<_Key, _Compare, _Alloc>& __y) 682 { __x.swap(__y); } 683 684 template<typename _Key, typename _Compare, typename _Alloc> 685 inline void 686 swap(multiset<_Key, _Compare, _Alloc>& __x, 687 multiset<_Key, _Compare, _Alloc>&& __y) 688 { __x.swap(__y); } 689 #endif 690 691 _GLIBCXX_END_NESTED_NAMESPACE 692 693 #endif /* _STL_MULTISET_H */ 694