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 _GLIBCXX_ABI_TAG_CXX11 550 iterator 551 erase(const_iterator __position) 552 { return _M_t.erase(__position); } 553 #else 554 /** 555 * @brief Erases an element from a %set. 556 * @param position An iterator pointing to the element to be erased. 557 * 558 * This function erases an element, pointed to by the given iterator, 559 * from a %set. Note that this function only erases the element, and 560 * that if the element is itself a pointer, the pointed-to memory is not 561 * touched in any way. Managing the pointer is the user's 562 * responsibility. 563 */ 564 void 565 erase(iterator __position) 566 { _M_t.erase(__position); } 567 #endif 568 569 /** 570 * @brief Erases elements according to the provided key. 571 * @param __x Key of element to be erased. 572 * @return The number of elements erased. 573 * 574 * This function erases all the elements located by the given key from 575 * a %set. 576 * Note that this function only erases the element, and that if 577 * the element is itself a pointer, the pointed-to memory is not touched 578 * in any way. Managing the pointer is the user's responsibility. 579 */ 580 size_type 581 erase(const key_type& __x) 582 { return _M_t.erase(__x); } 583 584 #if __cplusplus >= 201103L 585 // _GLIBCXX_RESOLVE_LIB_DEFECTS 586 // DR 130. Associative erase should return an iterator. 587 /** 588 * @brief Erases a [__first,__last) range of elements from a %set. 589 * @param __first Iterator pointing to the start of the range to be 590 * erased. 591 592 * @param __last Iterator pointing to the end of the range to 593 * be erased. 594 * @return The iterator @a __last. 595 * 596 * This function erases a sequence of elements from a %set. 597 * Note that this function only erases the element, and that if 598 * the element is itself a pointer, the pointed-to memory is not touched 599 * in any way. Managing the pointer is the user's responsibility. 600 */ 601 _GLIBCXX_ABI_TAG_CXX11 602 iterator 603 erase(const_iterator __first, const_iterator __last) 604 { return _M_t.erase(__first, __last); } 605 #else 606 /** 607 * @brief Erases a [first,last) range of elements from a %set. 608 * @param __first Iterator pointing to the start of the range to be 609 * erased. 610 * @param __last Iterator pointing to the end of the range to 611 * be erased. 612 * 613 * This function erases a sequence of elements from a %set. 614 * Note that this function only erases the element, and that if 615 * the element is itself a pointer, the pointed-to memory is not touched 616 * in any way. Managing the pointer is the user's responsibility. 617 */ 618 void 619 erase(iterator __first, iterator __last) 620 { _M_t.erase(__first, __last); } 621 #endif 622 623 /** 624 * Erases all elements in a %set. Note that this function only erases 625 * the elements, and that if the elements themselves are pointers, the 626 * pointed-to memory is not touched in any way. Managing the pointer is 627 * the user's responsibility. 628 */ 629 void 630 clear() _GLIBCXX_NOEXCEPT 631 { _M_t.clear(); } 632 633 // set operations: 634 635 /** 636 * @brief Finds the number of elements. 637 * @param __x Element to located. 638 * @return Number of elements with specified key. 639 * 640 * This function only makes sense for multisets; for set the result will 641 * either be 0 (not present) or 1 (present). 642 */ 643 size_type 644 count(const key_type& __x) const 645 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 646 647 // _GLIBCXX_RESOLVE_LIB_DEFECTS 648 // 214. set::find() missing const overload 649 //@{ 650 /** 651 * @brief Tries to locate an element in a %set. 652 * @param __x Element to be located. 653 * @return Iterator pointing to sought-after element, or end() if not 654 * found. 655 * 656 * This function takes a key and tries to locate the element with which 657 * the key matches. If successful the function returns an iterator 658 * pointing to the sought after element. If unsuccessful it returns the 659 * past-the-end ( @c end() ) iterator. 660 */ 661 iterator 662 find(const key_type& __x) 663 { return _M_t.find(__x); } 664 665 const_iterator 666 find(const key_type& __x) const 667 { return _M_t.find(__x); } 668 //@} 669 670 //@{ 671 /** 672 * @brief Finds the beginning of a subsequence matching given key. 673 * @param __x Key to be located. 674 * @return Iterator pointing to first element equal to or greater 675 * than key, or end(). 676 * 677 * This function returns the first element of a subsequence of elements 678 * that matches the given key. If unsuccessful it returns an iterator 679 * pointing to the first element that has a greater value than given key 680 * or end() if no such element exists. 681 */ 682 iterator 683 lower_bound(const key_type& __x) 684 { return _M_t.lower_bound(__x); } 685 686 const_iterator 687 lower_bound(const key_type& __x) const 688 { return _M_t.lower_bound(__x); } 689 //@} 690 691 //@{ 692 /** 693 * @brief Finds the end of a subsequence matching given key. 694 * @param __x Key to be located. 695 * @return Iterator pointing to the first element 696 * greater than key, or end(). 697 */ 698 iterator 699 upper_bound(const key_type& __x) 700 { return _M_t.upper_bound(__x); } 701 702 const_iterator 703 upper_bound(const key_type& __x) const 704 { return _M_t.upper_bound(__x); } 705 //@} 706 707 //@{ 708 /** 709 * @brief Finds a subsequence matching given key. 710 * @param __x Key to be located. 711 * @return Pair of iterators that possibly points to the subsequence 712 * matching given key. 713 * 714 * This function is equivalent to 715 * @code 716 * std::make_pair(c.lower_bound(val), 717 * c.upper_bound(val)) 718 * @endcode 719 * (but is faster than making the calls separately). 720 * 721 * This function probably only makes sense for multisets. 722 */ 723 std::pair<iterator, iterator> 724 equal_range(const key_type& __x) 725 { return _M_t.equal_range(__x); } 726 727 std::pair<const_iterator, const_iterator> 728 equal_range(const key_type& __x) const 729 { return _M_t.equal_range(__x); } 730 //@} 731 732 template<typename _K1, typename _C1, typename _A1> 733 friend bool 734 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 735 736 template<typename _K1, typename _C1, typename _A1> 737 friend bool 738 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 739 }; 740 741 742 /** 743 * @brief Set equality comparison. 744 * @param __x A %set. 745 * @param __y A %set of the same type as @a x. 746 * @return True iff the size and elements of the sets are equal. 747 * 748 * This is an equivalence relation. It is linear in the size of the sets. 749 * Sets are considered equivalent if their sizes are equal, and if 750 * corresponding elements compare equal. 751 */ 752 template<typename _Key, typename _Compare, typename _Alloc> 753 inline bool 754 operator==(const set<_Key, _Compare, _Alloc>& __x, 755 const set<_Key, _Compare, _Alloc>& __y) 756 { return __x._M_t == __y._M_t; } 757 758 /** 759 * @brief Set ordering relation. 760 * @param __x A %set. 761 * @param __y A %set of the same type as @a x. 762 * @return True iff @a __x is lexicographically less than @a __y. 763 * 764 * This is a total ordering relation. It is linear in the size of the 765 * maps. The elements must be comparable with @c <. 766 * 767 * See std::lexicographical_compare() for how the determination is made. 768 */ 769 template<typename _Key, typename _Compare, typename _Alloc> 770 inline bool 771 operator<(const set<_Key, _Compare, _Alloc>& __x, 772 const set<_Key, _Compare, _Alloc>& __y) 773 { return __x._M_t < __y._M_t; } 774 775 /// Returns !(x == y). 776 template<typename _Key, typename _Compare, typename _Alloc> 777 inline bool 778 operator!=(const set<_Key, _Compare, _Alloc>& __x, 779 const set<_Key, _Compare, _Alloc>& __y) 780 { return !(__x == __y); } 781 782 /// Returns y < x. 783 template<typename _Key, typename _Compare, typename _Alloc> 784 inline bool 785 operator>(const set<_Key, _Compare, _Alloc>& __x, 786 const set<_Key, _Compare, _Alloc>& __y) 787 { return __y < __x; } 788 789 /// Returns !(y < x) 790 template<typename _Key, typename _Compare, typename _Alloc> 791 inline bool 792 operator<=(const set<_Key, _Compare, _Alloc>& __x, 793 const set<_Key, _Compare, _Alloc>& __y) 794 { return !(__y < __x); } 795 796 /// Returns !(x < y) 797 template<typename _Key, typename _Compare, typename _Alloc> 798 inline bool 799 operator>=(const set<_Key, _Compare, _Alloc>& __x, 800 const set<_Key, _Compare, _Alloc>& __y) 801 { return !(__x < __y); } 802 803 /// See std::set::swap(). 804 template<typename _Key, typename _Compare, typename _Alloc> 805 inline void 806 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) 807 { __x.swap(__y); } 808 809 _GLIBCXX_END_NAMESPACE_CONTAINER 810 } //namespace std 811 #endif /* _STL_SET_H */ 812
