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