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#ifdef __GXX_EXPERIMENTAL_CXX0X__ 380 swap(multiset&& __x) 381#else 382 swap(multiset& __x) 383#endif 384 { _M_t.swap(__x._M_t); } 385 386 // insert/erase 387 /** 388 * @brief Inserts an element into the %multiset. 389 * @param x Element to be inserted. 390 * @return An iterator that points to the inserted element. 391 * 392 * This function inserts an element into the %multiset. Contrary 393 * to a std::set the %multiset does not rely on unique keys and thus 394 * multiple copies of the same element can be inserted. 395 * 396 * Insertion requires logarithmic time. 397 */ 398 iterator 399 insert(const value_type& __x) 400 { return _M_t._M_insert_equal(__x); } 401 402 /** 403 * @brief Inserts an element into the %multiset. 404 * @param position An iterator that serves as a hint as to where the 405 * element should be inserted. 406 * @param x Element to be inserted. 407 * @return An iterator that points to the inserted element. 408 * 409 * This function inserts an element into the %multiset. Contrary 410 * to a std::set the %multiset does not rely on unique keys and thus 411 * multiple copies of the same element can be inserted. 412 * 413 * Note that the first parameter is only a hint and can potentially 414 * improve the performance of the insertion process. A bad hint would 415 * cause no gains in efficiency. 416 * 417 * See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 418 * for more on "hinting". 419 * 420 * Insertion requires logarithmic time (if the hint is not taken). 421 */ 422 iterator 423 insert(iterator __position, const value_type& __x) 424 { return _M_t._M_insert_equal_(__position, __x); } 425 426 /** 427 * @brief A template function that attempts to insert a range of elements. 428 * @param first Iterator pointing to the start of the range to be 429 * inserted. 430 * @param last Iterator pointing to the end of the range. 431 * 432 * Complexity similar to that of the range constructor. 433 */ 434 template<typename _InputIterator> 435 void 436 insert(_InputIterator __first, _InputIterator __last) 437 { _M_t._M_insert_equal(__first, __last); } 438 439#ifdef __GXX_EXPERIMENTAL_CXX0X__ 440 /** 441 * @brief Attempts to insert a list of elements into the %multiset. 442 * @param list A std::initializer_list<value_type> of elements 443 * to be inserted. 444 * 445 * Complexity similar to that of the range constructor. 446 */ 447 void 448 insert(initializer_list<value_type> __l) 449 { this->insert(__l.begin(), __l.end()); } 450#endif 451 452 /** 453 * @brief Erases an element from a %multiset. 454 * @param position An iterator pointing to the element to be erased. 455 * 456 * This function erases an element, pointed to by the given iterator, 457 * from a %multiset. Note that this function only erases the element, 458 * and that if the element is itself a pointer, the pointed-to memory is 459 * not touched in any way. Managing the pointer is the user's 460 * responsibility. 461 */ 462 void 463 erase(iterator __position) 464 { _M_t.erase(__position); } 465 466 /** 467 * @brief Erases elements according to the provided key. 468 * @param x Key of element to be erased. 469 * @return The number of elements erased. 470 * 471 * This function erases all elements located by the given key from a 472 * %multiset. 473 * Note that this function only erases the element, and that if 474 * the element is itself a pointer, the pointed-to memory is not touched 475 * in any way. Managing the pointer is the user's responsibility. 476 */ 477 size_type 478 erase(const key_type& __x) 479 { return _M_t.erase(__x); } 480 481 /** 482 * @brief Erases a [first,last) range of elements from a %multiset. 483 * @param first Iterator pointing to the start of the range to be 484 * erased. 485 * @param last Iterator pointing to the end of the range to be erased. 486 * 487 * This function erases a sequence of elements from a %multiset. 488 * Note that this function only erases the elements, and that if 489 * the elements themselves are pointers, the pointed-to memory is not 490 * touched in any way. Managing the pointer is the user's responsibility. 491 */ 492 void 493 erase(iterator __first, iterator __last) 494 { _M_t.erase(__first, __last); } 495 496 /** 497 * Erases all elements in a %multiset. Note that this function only 498 * erases the elements, and that if the elements themselves are pointers, 499 * the pointed-to memory is not touched in any way. Managing the pointer 500 * is the user's responsibility. 501 */ 502 void 503 clear() 504 { _M_t.clear(); } 505 506 // multiset operations: 507 508 /** 509 * @brief Finds the number of elements with given key. 510 * @param x Key of elements to be located. 511 * @return Number of elements with specified key. 512 */ 513 size_type 514 count(const key_type& __x) const 515 { return _M_t.count(__x); } 516 517 // _GLIBCXX_RESOLVE_LIB_DEFECTS 518 // 214. set::find() missing const overload 519 //@{ 520 /** 521 * @brief Tries to locate an element in a %set. 522 * @param x Element to be located. 523 * @return Iterator pointing to sought-after element, or end() if not 524 * found. 525 * 526 * This function takes a key and tries to locate the element with which 527 * the key matches. If successful the function returns an iterator 528 * pointing to the sought after element. If unsuccessful it returns the 529 * past-the-end ( @c end() ) iterator. 530 */ 531 iterator 532 find(const key_type& __x) 533 { return _M_t.find(__x); } 534 535 const_iterator 536 find(const key_type& __x) const 537 { return _M_t.find(__x); } 538 //@} 539 540 //@{ 541 /** 542 * @brief Finds the beginning of a subsequence matching given key. 543 * @param x Key to be located. 544 * @return Iterator pointing to first element equal to or greater 545 * than key, or end(). 546 * 547 * This function returns the first element of a subsequence of elements 548 * that matches the given key. If unsuccessful it returns an iterator 549 * pointing to the first element that has a greater value than given key 550 * or end() if no such element exists. 551 */ 552 iterator 553 lower_bound(const key_type& __x) 554 { return _M_t.lower_bound(__x); } 555 556 const_iterator 557 lower_bound(const key_type& __x) const 558 { return _M_t.lower_bound(__x); } 559 //@} 560 561 //@{ 562 /** 563 * @brief Finds the end of a subsequence matching given key. 564 * @param x Key to be located. 565 * @return Iterator pointing to the first element 566 * greater than key, or end(). 567 */ 568 iterator 569 upper_bound(const key_type& __x) 570 { return _M_t.upper_bound(__x); } 571 572 const_iterator 573 upper_bound(const key_type& __x) const 574 { return _M_t.upper_bound(__x); } 575 //@} 576 577 //@{ 578 /** 579 * @brief Finds a subsequence matching given key. 580 * @param x Key to be located. 581 * @return Pair of iterators that possibly points to the subsequence 582 * matching given key. 583 * 584 * This function is equivalent to 585 * @code 586 * std::make_pair(c.lower_bound(val), 587 * c.upper_bound(val)) 588 * @endcode 589 * (but is faster than making the calls separately). 590 * 591 * This function probably only makes sense for multisets. 592 */ 593 std::pair<iterator, iterator> 594 equal_range(const key_type& __x) 595 { return _M_t.equal_range(__x); } 596 597 std::pair<const_iterator, const_iterator> 598 equal_range(const key_type& __x) const 599 { return _M_t.equal_range(__x); } 600 601 template<typename _K1, typename _C1, typename _A1> 602 friend bool 603 operator==(const multiset<_K1, _C1, _A1>&, 604 const multiset<_K1, _C1, _A1>&); 605 606 template<typename _K1, typename _C1, typename _A1> 607 friend bool 608 operator< (const multiset<_K1, _C1, _A1>&, 609 const multiset<_K1, _C1, _A1>&); 610 }; 611 612 /** 613 * @brief Multiset equality comparison. 614 * @param x A %multiset. 615 * @param y A %multiset of the same type as @a x. 616 * @return True iff the size and elements of the multisets are equal. 617 * 618 * This is an equivalence relation. It is linear in the size of the 619 * multisets. 620 * Multisets are considered equivalent if their sizes are equal, and if 621 * corresponding elements compare equal. 622 */ 623 template<typename _Key, typename _Compare, typename _Alloc> 624 inline bool 625 operator==(const multiset<_Key, _Compare, _Alloc>& __x, 626 const multiset<_Key, _Compare, _Alloc>& __y) 627 { return __x._M_t == __y._M_t; } 628 629 /** 630 * @brief Multiset ordering relation. 631 * @param x A %multiset. 632 * @param y A %multiset of the same type as @a x. 633 * @return True iff @a x is lexicographically less than @a y. 634 * 635 * This is a total ordering relation. It is linear in the size of the 636 * maps. The elements must be comparable with @c <. 637 * 638 * See std::lexicographical_compare() for how the determination is made. 639 */ 640 template<typename _Key, typename _Compare, typename _Alloc> 641 inline bool 642 operator<(const multiset<_Key, _Compare, _Alloc>& __x, 643 const multiset<_Key, _Compare, _Alloc>& __y) 644 { return __x._M_t < __y._M_t; } 645 646 /// Returns !(x == y). 647 template<typename _Key, typename _Compare, typename _Alloc> 648 inline bool 649 operator!=(const multiset<_Key, _Compare, _Alloc>& __x, 650 const multiset<_Key, _Compare, _Alloc>& __y) 651 { return !(__x == __y); } 652 653 /// Returns y < x. 654 template<typename _Key, typename _Compare, typename _Alloc> 655 inline bool 656 operator>(const multiset<_Key,_Compare,_Alloc>& __x, 657 const multiset<_Key,_Compare,_Alloc>& __y) 658 { return __y < __x; } 659 660 /// Returns !(y < x) 661 template<typename _Key, typename _Compare, typename _Alloc> 662 inline bool 663 operator<=(const multiset<_Key, _Compare, _Alloc>& __x, 664 const multiset<_Key, _Compare, _Alloc>& __y) 665 { return !(__y < __x); } 666 667 /// Returns !(x < y) 668 template<typename _Key, typename _Compare, typename _Alloc> 669 inline bool 670 operator>=(const multiset<_Key, _Compare, _Alloc>& __x, 671 const multiset<_Key, _Compare, _Alloc>& __y) 672 { return !(__x < __y); } 673 674 /// See std::multiset::swap(). 675 template<typename _Key, typename _Compare, typename _Alloc> 676 inline void 677 swap(multiset<_Key, _Compare, _Alloc>& __x, 678 multiset<_Key, _Compare, _Alloc>& __y) 679 { __x.swap(__y); } 680 681#ifdef __GXX_EXPERIMENTAL_CXX0X__ 682 template<typename _Key, typename _Compare, typename _Alloc> 683 inline void 684 swap(multiset<_Key, _Compare, _Alloc>&& __x, 685 multiset<_Key, _Compare, _Alloc>& __y) 686 { __x.swap(__y); } 687 688 template<typename _Key, typename _Compare, typename _Alloc> 689 inline void 690 swap(multiset<_Key, _Compare, _Alloc>& __x, 691 multiset<_Key, _Compare, _Alloc>&& __y) 692 { __x.swap(__y); } 693#endif 694 695_GLIBCXX_END_NESTED_NAMESPACE 696 697#endif /* _STL_MULTISET_H */ 698