1 // Set implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2015 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 __gnu_cxx::__alloc_traits<_Alloc>::template 112 rebind<_Key>::other _Key_alloc_type; 113 114 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 115 key_compare, _Key_alloc_type> _Rep_type; 116 _Rep_type _M_t; // Red-black tree representing set. 117 118 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; 119 120 public: 121 //@{ 122 /// Iterator-related typedefs. 123 typedef typename _Alloc_traits::pointer pointer; 124 typedef typename _Alloc_traits::const_pointer const_pointer; 125 typedef typename _Alloc_traits::reference reference; 126 typedef typename _Alloc_traits::const_reference const_reference; 127 // _GLIBCXX_RESOLVE_LIB_DEFECTS 128 // DR 103. set::iterator is required to be modifiable, 129 // but this allows modification of keys. 130 typedef typename _Rep_type::const_iterator iterator; 131 typedef typename _Rep_type::const_iterator const_iterator; 132 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 133 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 134 typedef typename _Rep_type::size_type size_type; 135 typedef typename _Rep_type::difference_type difference_type; 136 //@} 137 138 // allocation/deallocation 139 /** 140 * @brief Default constructor creates no elements. 141 */ 142 set() 143 #if __cplusplus >= 201103L 144 noexcept(is_nothrow_default_constructible<allocator_type>::value 145 && is_nothrow_default_constructible<key_compare>::value) 146 #endif 147 : _M_t() { } 148 149 /** 150 * @brief Creates a %set with no elements. 151 * @param __comp Comparator to use. 152 * @param __a An allocator object. 153 */ 154 explicit 155 set(const _Compare& __comp, 156 const allocator_type& __a = allocator_type()) 157 : _M_t(__comp, _Key_alloc_type(__a)) { } 158 159 /** 160 * @brief Builds a %set from a range. 161 * @param __first An input iterator. 162 * @param __last An input iterator. 163 * 164 * Create a %set consisting of copies of the elements from 165 * [__first,__last). This is linear in N if the range is 166 * already sorted, and NlogN otherwise (where N is 167 * distance(__first,__last)). 168 */ 169 template<typename _InputIterator> 170 set(_InputIterator __first, _InputIterator __last) 171 : _M_t() 172 { _M_t._M_insert_unique(__first, __last); } 173 174 /** 175 * @brief Builds a %set from a range. 176 * @param __first An input iterator. 177 * @param __last An input iterator. 178 * @param __comp A comparison functor. 179 * @param __a An allocator object. 180 * 181 * Create a %set consisting of copies of the elements from 182 * [__first,__last). This is linear in N if the range is 183 * already sorted, and NlogN otherwise (where N is 184 * distance(__first,__last)). 185 */ 186 template<typename _InputIterator> 187 set(_InputIterator __first, _InputIterator __last, 188 const _Compare& __comp, 189 const allocator_type& __a = allocator_type()) 190 : _M_t(__comp, _Key_alloc_type(__a)) 191 { _M_t._M_insert_unique(__first, __last); } 192 193 /** 194 * @brief %Set copy constructor. 195 * @param __x A %set of identical element and allocator types. 196 * 197 * The newly-created %set uses a copy of the allocation object used 198 * by @a __x. 199 */ 200 set(const set& __x) 201 : _M_t(__x._M_t) { } 202 203 #if __cplusplus >= 201103L 204 /** 205 * @brief %Set move constructor 206 * @param __x A %set of identical element and allocator types. 207 * 208 * The newly-created %set contains the exact contents of @a x. 209 * The contents of @a x are a valid, but unspecified %set. 210 */ 211 set(set&& __x) 212 noexcept(is_nothrow_copy_constructible<_Compare>::value) 213 : _M_t(std::move(__x._M_t)) { } 214 215 /** 216 * @brief Builds a %set from an initializer_list. 217 * @param __l An initializer_list. 218 * @param __comp A comparison functor. 219 * @param __a An allocator object. 220 * 221 * Create a %set consisting of copies of the elements in the list. 222 * This is linear in N if the list is already sorted, and NlogN 223 * otherwise (where N is @a __l.size()). 224 */ 225 set(initializer_list<value_type> __l, 226 const _Compare& __comp = _Compare(), 227 const allocator_type& __a = allocator_type()) 228 : _M_t(__comp, _Key_alloc_type(__a)) 229 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 230 231 /// Allocator-extended default constructor. 232 explicit 233 set(const allocator_type& __a) 234 : _M_t(_Compare(), _Key_alloc_type(__a)) { } 235 236 /// Allocator-extended copy constructor. 237 set(const set& __x, const allocator_type& __a) 238 : _M_t(__x._M_t, _Key_alloc_type(__a)) { } 239 240 /// Allocator-extended move constructor. 241 set(set&& __x, const allocator_type& __a) 242 noexcept(is_nothrow_copy_constructible<_Compare>::value 243 && _Alloc_traits::_S_always_equal()) 244 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { } 245 246 /// Allocator-extended initialier-list constructor. 247 set(initializer_list<value_type> __l, const allocator_type& __a) 248 : _M_t(_Compare(), _Key_alloc_type(__a)) 249 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 250 251 /// Allocator-extended range constructor. 252 template<typename _InputIterator> 253 set(_InputIterator __first, _InputIterator __last, 254 const allocator_type& __a) 255 : _M_t(_Compare(), _Key_alloc_type(__a)) 256 { _M_t._M_insert_unique(__first, __last); } 257 #endif 258 259 /** 260 * @brief %Set assignment operator. 261 * @param __x A %set of identical element and allocator types. 262 * 263 * All the elements of @a __x are copied, but unlike the copy 264 * constructor, the allocator object is not copied. 265 */ 266 set& 267 operator=(const set& __x) 268 { 269 _M_t = __x._M_t; 270 return *this; 271 } 272 273 #if __cplusplus >= 201103L 274 /// Move assignment operator. 275 set& 276 operator=(set&&) = default; 277 278 /** 279 * @brief %Set list assignment operator. 280 * @param __l An initializer_list. 281 * 282 * This function fills a %set with copies of the elements in the 283 * initializer list @a __l. 284 * 285 * Note that the assignment completely changes the %set and 286 * that the resulting %set's size is the same as the number 287 * of elements assigned. Old data may be lost. 288 */ 289 set& 290 operator=(initializer_list<value_type> __l) 291 { 292 _M_t._M_assign_unique(__l.begin(), __l.end()); 293 return *this; 294 } 295 #endif 296 297 // accessors: 298 299 /// Returns the comparison object with which the %set was constructed. 300 key_compare 301 key_comp() const 302 { return _M_t.key_comp(); } 303 /// Returns the comparison object with which the %set was constructed. 304 value_compare 305 value_comp() const 306 { return _M_t.key_comp(); } 307 /// Returns the allocator object with which the %set was constructed. 308 allocator_type 309 get_allocator() const _GLIBCXX_NOEXCEPT 310 { return allocator_type(_M_t.get_allocator()); } 311 312 /** 313 * Returns a read-only (constant) iterator that points to the first 314 * element in the %set. Iteration is done in ascending order according 315 * to the keys. 316 */ 317 iterator 318 begin() const _GLIBCXX_NOEXCEPT 319 { return _M_t.begin(); } 320 321 /** 322 * Returns a read-only (constant) iterator that points one past the last 323 * element in the %set. Iteration is done in ascending order according 324 * to the keys. 325 */ 326 iterator 327 end() const _GLIBCXX_NOEXCEPT 328 { return _M_t.end(); } 329 330 /** 331 * Returns a read-only (constant) iterator that points to the last 332 * element in the %set. Iteration is done in descending order according 333 * to the keys. 334 */ 335 reverse_iterator 336 rbegin() const _GLIBCXX_NOEXCEPT 337 { return _M_t.rbegin(); } 338 339 /** 340 * Returns a read-only (constant) reverse iterator that points to the 341 * last pair in the %set. Iteration is done in descending order 342 * according to the keys. 343 */ 344 reverse_iterator 345 rend() const _GLIBCXX_NOEXCEPT 346 { return _M_t.rend(); } 347 348 #if __cplusplus >= 201103L 349 /** 350 * Returns a read-only (constant) iterator that points to the first 351 * element in the %set. Iteration is done in ascending order according 352 * to the keys. 353 */ 354 iterator 355 cbegin() const noexcept 356 { return _M_t.begin(); } 357 358 /** 359 * Returns a read-only (constant) iterator that points one past the last 360 * element in the %set. Iteration is done in ascending order according 361 * to the keys. 362 */ 363 iterator 364 cend() const noexcept 365 { return _M_t.end(); } 366 367 /** 368 * Returns a read-only (constant) iterator that points to the last 369 * element in the %set. Iteration is done in descending order according 370 * to the keys. 371 */ 372 reverse_iterator 373 crbegin() const noexcept 374 { return _M_t.rbegin(); } 375 376 /** 377 * Returns a read-only (constant) reverse iterator that points to the 378 * last pair in the %set. Iteration is done in descending order 379 * according to the keys. 380 */ 381 reverse_iterator 382 crend() const noexcept 383 { return _M_t.rend(); } 384 #endif 385 386 /// Returns true if the %set is empty. 387 bool 388 empty() const _GLIBCXX_NOEXCEPT 389 { return _M_t.empty(); } 390 391 /// Returns the size of the %set. 392 size_type 393 size() const _GLIBCXX_NOEXCEPT 394 { return _M_t.size(); } 395 396 /// Returns the maximum size of the %set. 397 size_type 398 max_size() const _GLIBCXX_NOEXCEPT 399 { return _M_t.max_size(); } 400 401 /** 402 * @brief Swaps data with another %set. 403 * @param __x A %set of the same element and allocator types. 404 * 405 * This exchanges the elements between two sets in constant 406 * time. (It is only swapping a pointer, an integer, and an 407 * instance of the @c Compare type (which itself is often 408 * stateless and empty), so it should be quite fast.) Note 409 * that the global std::swap() function is specialized such 410 * that std::swap(s1,s2) will feed to this function. 411 */ 412 void 413 swap(set& __x) 414 #if __cplusplus >= 201103L 415 noexcept(_Alloc_traits::_S_nothrow_swap()) 416 #endif 417 { _M_t.swap(__x._M_t); } 418 419 // insert/erase 420 #if __cplusplus >= 201103L 421 /** 422 * @brief Attempts to build and insert an element into the %set. 423 * @param __args Arguments used to generate an element. 424 * @return A pair, of which the first element is an iterator that points 425 * to the possibly inserted element, and the second is a bool 426 * that is true if the element was actually inserted. 427 * 428 * This function attempts to build and insert an element into the %set. 429 * A %set relies on unique keys and thus an element is only inserted if 430 * it is not already present in the %set. 431 * 432 * Insertion requires logarithmic time. 433 */ 434 template<typename... _Args> 435 std::pair<iterator, bool> 436 emplace(_Args&&... __args) 437 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } 438 439 /** 440 * @brief Attempts to insert an element into the %set. 441 * @param __pos An iterator that serves as a hint as to where the 442 * element should be inserted. 443 * @param __args Arguments used to generate the element to be 444 * inserted. 445 * @return An iterator that points to the element with key equivalent to 446 * the one generated from @a __args (may or may not be the 447 * element itself). 448 * 449 * This function is not concerned about whether the insertion took place, 450 * and thus does not return a boolean like the single-argument emplace() 451 * does. Note that the first parameter is only a hint and can 452 * potentially improve the performance of the insertion process. A bad 453 * hint would cause no gains in efficiency. 454 * 455 * For more on @a hinting, see: 456 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 457 * 458 * Insertion requires logarithmic time (if the hint is not taken). 459 */ 460 template<typename... _Args> 461 iterator 462 emplace_hint(const_iterator __pos, _Args&&... __args) 463 { 464 return _M_t._M_emplace_hint_unique(__pos, 465 std::forward<_Args>(__args)...); 466 } 467 #endif 468 469 /** 470 * @brief Attempts to insert an element into the %set. 471 * @param __x Element to be inserted. 472 * @return A pair, of which the first element is an iterator that points 473 * to the possibly inserted element, and the second is a bool 474 * that is true if the element was actually inserted. 475 * 476 * This function attempts to insert an element into the %set. A %set 477 * relies on unique keys and thus an element is only inserted if it is 478 * not already present in the %set. 479 * 480 * Insertion requires logarithmic time. 481 */ 482 std::pair<iterator, bool> 483 insert(const value_type& __x) 484 { 485 std::pair<typename _Rep_type::iterator, bool> __p = 486 _M_t._M_insert_unique(__x); 487 return std::pair<iterator, bool>(__p.first, __p.second); 488 } 489 490 #if __cplusplus >= 201103L 491 std::pair<iterator, bool> 492 insert(value_type&& __x) 493 { 494 std::pair<typename _Rep_type::iterator, bool> __p = 495 _M_t._M_insert_unique(std::move(__x)); 496 return std::pair<iterator, bool>(__p.first, __p.second); 497 } 498 #endif 499 500 /** 501 * @brief Attempts to insert an element into the %set. 502 * @param __position An iterator that serves as a hint as to where the 503 * element should be inserted. 504 * @param __x Element to be inserted. 505 * @return An iterator that points to the element with key of 506 * @a __x (may or may not be the element passed in). 507 * 508 * This function is not concerned about whether the insertion took place, 509 * and thus does not return a boolean like the single-argument insert() 510 * does. Note that the first parameter is only a hint and can 511 * potentially improve the performance of the insertion process. A bad 512 * hint would cause no gains in efficiency. 513 * 514 * For more on @a hinting, see: 515 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 516 * 517 * Insertion requires logarithmic time (if the hint is not taken). 518 */ 519 iterator 520 insert(const_iterator __position, const value_type& __x) 521 { return _M_t._M_insert_unique_(__position, __x); } 522 523 #if __cplusplus >= 201103L 524 iterator 525 insert(const_iterator __position, value_type&& __x) 526 { return _M_t._M_insert_unique_(__position, std::move(__x)); } 527 #endif 528 529 /** 530 * @brief A template function that attempts to insert a range 531 * of elements. 532 * @param __first Iterator pointing to the start of the range to be 533 * inserted. 534 * @param __last Iterator pointing to the end of the range. 535 * 536 * Complexity similar to that of the range constructor. 537 */ 538 template<typename _InputIterator> 539 void 540 insert(_InputIterator __first, _InputIterator __last) 541 { _M_t._M_insert_unique(__first, __last); } 542 543 #if __cplusplus >= 201103L 544 /** 545 * @brief Attempts to insert a list of elements into the %set. 546 * @param __l A std::initializer_list<value_type> of elements 547 * to be inserted. 548 * 549 * Complexity similar to that of the range constructor. 550 */ 551 void 552 insert(initializer_list<value_type> __l) 553 { this->insert(__l.begin(), __l.end()); } 554 #endif 555 556 #if __cplusplus >= 201103L 557 // _GLIBCXX_RESOLVE_LIB_DEFECTS 558 // DR 130. Associative erase should return an iterator. 559 /** 560 * @brief Erases an element from a %set. 561 * @param __position An iterator pointing to the element to be erased. 562 * @return An iterator pointing to the element immediately following 563 * @a __position prior to the element being erased. If no such 564 * element exists, end() is returned. 565 * 566 * This function erases an element, pointed to by the given iterator, 567 * from a %set. Note that this function only erases the element, and 568 * that if the element is itself a pointer, the pointed-to memory is not 569 * touched in any way. Managing the pointer is the user's 570 * responsibility. 571 */ 572 _GLIBCXX_ABI_TAG_CXX11 573 iterator 574 erase(const_iterator __position) 575 { return _M_t.erase(__position); } 576 #else 577 /** 578 * @brief Erases an element from a %set. 579 * @param position An iterator pointing to the element to be erased. 580 * 581 * This function erases an element, pointed to by the given iterator, 582 * from a %set. Note that this function only erases the element, and 583 * that if the element is itself a pointer, the pointed-to memory is not 584 * touched in any way. Managing the pointer is the user's 585 * responsibility. 586 */ 587 void 588 erase(iterator __position) 589 { _M_t.erase(__position); } 590 #endif 591 592 /** 593 * @brief Erases elements according to the provided key. 594 * @param __x Key of element to be erased. 595 * @return The number of elements erased. 596 * 597 * This function erases all the elements located by the given key from 598 * a %set. 599 * Note that this function only erases the element, and that if 600 * the element is itself a pointer, the pointed-to memory is not touched 601 * in any way. Managing the pointer is the user's responsibility. 602 */ 603 size_type 604 erase(const key_type& __x) 605 { return _M_t.erase(__x); } 606 607 #if __cplusplus >= 201103L 608 // _GLIBCXX_RESOLVE_LIB_DEFECTS 609 // DR 130. Associative erase should return an iterator. 610 /** 611 * @brief Erases a [__first,__last) range of elements from a %set. 612 * @param __first Iterator pointing to the start of the range to be 613 * erased. 614 615 * @param __last Iterator pointing to the end of the range to 616 * be erased. 617 * @return The iterator @a __last. 618 * 619 * This function erases a sequence of elements from a %set. 620 * Note that this function only erases the element, and that if 621 * the element is itself a pointer, the pointed-to memory is not touched 622 * in any way. Managing the pointer is the user's responsibility. 623 */ 624 _GLIBCXX_ABI_TAG_CXX11 625 iterator 626 erase(const_iterator __first, const_iterator __last) 627 { return _M_t.erase(__first, __last); } 628 #else 629 /** 630 * @brief Erases a [first,last) range of elements from a %set. 631 * @param __first Iterator pointing to the start of the range to be 632 * erased. 633 * @param __last Iterator pointing to the end of the range to 634 * be erased. 635 * 636 * This function erases a sequence of elements from a %set. 637 * Note that this function only erases the element, and that if 638 * the element is itself a pointer, the pointed-to memory is not touched 639 * in any way. Managing the pointer is the user's responsibility. 640 */ 641 void 642 erase(iterator __first, iterator __last) 643 { _M_t.erase(__first, __last); } 644 #endif 645 646 /** 647 * Erases all elements in a %set. Note that this function only erases 648 * the elements, and that if the elements themselves are pointers, the 649 * pointed-to memory is not touched in any way. Managing the pointer is 650 * the user's responsibility. 651 */ 652 void 653 clear() _GLIBCXX_NOEXCEPT 654 { _M_t.clear(); } 655 656 // set operations: 657 658 //@{ 659 /** 660 * @brief Finds the number of elements. 661 * @param __x Element to located. 662 * @return Number of elements with specified key. 663 * 664 * This function only makes sense for multisets; for set the result will 665 * either be 0 (not present) or 1 (present). 666 */ 667 size_type 668 count(const key_type& __x) const 669 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 670 671 #if __cplusplus > 201103L 672 template<typename _Kt> 673 auto 674 count(const _Kt& __x) const 675 -> decltype(_M_t._M_count_tr(__x)) 676 { return _M_t._M_count_tr(__x); } 677 #endif 678 //@} 679 680 // _GLIBCXX_RESOLVE_LIB_DEFECTS 681 // 214. set::find() missing const overload 682 //@{ 683 /** 684 * @brief Tries to locate an element in a %set. 685 * @param __x Element to be located. 686 * @return Iterator pointing to sought-after element, or end() if not 687 * found. 688 * 689 * This function takes a key and tries to locate the element with which 690 * the key matches. If successful the function returns an iterator 691 * pointing to the sought after element. If unsuccessful it returns the 692 * past-the-end ( @c end() ) iterator. 693 */ 694 iterator 695 find(const key_type& __x) 696 { return _M_t.find(__x); } 697 698 const_iterator 699 find(const key_type& __x) const 700 { return _M_t.find(__x); } 701 702 #if __cplusplus > 201103L 703 template<typename _Kt> 704 auto 705 find(const _Kt& __x) 706 -> decltype(iterator{_M_t._M_find_tr(__x)}) 707 { return iterator{_M_t._M_find_tr(__x)}; } 708 709 template<typename _Kt> 710 auto 711 find(const _Kt& __x) const 712 -> decltype(const_iterator{_M_t._M_find_tr(__x)}) 713 { return const_iterator{_M_t._M_find_tr(__x)}; } 714 #endif 715 //@} 716 717 //@{ 718 /** 719 * @brief Finds the beginning of a subsequence matching given key. 720 * @param __x Key to be located. 721 * @return Iterator pointing to first element equal to or greater 722 * than key, or end(). 723 * 724 * This function returns the first element of a subsequence of elements 725 * that matches the given key. If unsuccessful it returns an iterator 726 * pointing to the first element that has a greater value than given key 727 * or end() if no such element exists. 728 */ 729 iterator 730 lower_bound(const key_type& __x) 731 { return _M_t.lower_bound(__x); } 732 733 const_iterator 734 lower_bound(const key_type& __x) const 735 { return _M_t.lower_bound(__x); } 736 737 #if __cplusplus > 201103L 738 template<typename _Kt> 739 auto 740 lower_bound(const _Kt& __x) 741 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 742 { return iterator(_M_t._M_lower_bound_tr(__x)); } 743 744 template<typename _Kt> 745 auto 746 lower_bound(const _Kt& __x) const 747 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 748 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 749 #endif 750 //@} 751 752 //@{ 753 /** 754 * @brief Finds the end of a subsequence matching given key. 755 * @param __x Key to be located. 756 * @return Iterator pointing to the first element 757 * greater than key, or end(). 758 */ 759 iterator 760 upper_bound(const key_type& __x) 761 { return _M_t.upper_bound(__x); } 762 763 const_iterator 764 upper_bound(const key_type& __x) const 765 { return _M_t.upper_bound(__x); } 766 767 #if __cplusplus > 201103L 768 template<typename _Kt> 769 auto 770 upper_bound(const _Kt& __x) 771 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 772 { return iterator(_M_t._M_upper_bound_tr(__x)); } 773 774 template<typename _Kt> 775 auto 776 upper_bound(const _Kt& __x) const 777 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 778 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 779 #endif 780 //@} 781 782 //@{ 783 /** 784 * @brief Finds a subsequence matching given key. 785 * @param __x Key to be located. 786 * @return Pair of iterators that possibly points to the subsequence 787 * matching given key. 788 * 789 * This function is equivalent to 790 * @code 791 * std::make_pair(c.lower_bound(val), 792 * c.upper_bound(val)) 793 * @endcode 794 * (but is faster than making the calls separately). 795 * 796 * This function probably only makes sense for multisets. 797 */ 798 std::pair<iterator, iterator> 799 equal_range(const key_type& __x) 800 { return _M_t.equal_range(__x); } 801 802 std::pair<const_iterator, const_iterator> 803 equal_range(const key_type& __x) const 804 { return _M_t.equal_range(__x); } 805 806 #if __cplusplus > 201103L 807 template<typename _Kt> 808 auto 809 equal_range(const _Kt& __x) 810 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 811 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 812 813 template<typename _Kt> 814 auto 815 equal_range(const _Kt& __x) const 816 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 817 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 818 #endif 819 //@} 820 821 template<typename _K1, typename _C1, typename _A1> 822 friend bool 823 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 824 825 template<typename _K1, typename _C1, typename _A1> 826 friend bool 827 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 828 }; 829 830 831 /** 832 * @brief Set equality comparison. 833 * @param __x A %set. 834 * @param __y A %set of the same type as @a x. 835 * @return True iff the size and elements of the sets are equal. 836 * 837 * This is an equivalence relation. It is linear in the size of the sets. 838 * Sets are considered equivalent if their sizes are equal, and if 839 * corresponding elements compare equal. 840 */ 841 template<typename _Key, typename _Compare, typename _Alloc> 842 inline bool 843 operator==(const set<_Key, _Compare, _Alloc>& __x, 844 const set<_Key, _Compare, _Alloc>& __y) 845 { return __x._M_t == __y._M_t; } 846 847 /** 848 * @brief Set ordering relation. 849 * @param __x A %set. 850 * @param __y A %set of the same type as @a x. 851 * @return True iff @a __x is lexicographically less than @a __y. 852 * 853 * This is a total ordering relation. It is linear in the size of the 854 * sets. The elements must be comparable with @c <. 855 * 856 * See std::lexicographical_compare() for how the determination is made. 857 */ 858 template<typename _Key, typename _Compare, typename _Alloc> 859 inline bool 860 operator<(const set<_Key, _Compare, _Alloc>& __x, 861 const set<_Key, _Compare, _Alloc>& __y) 862 { return __x._M_t < __y._M_t; } 863 864 /// Returns !(x == y). 865 template<typename _Key, typename _Compare, typename _Alloc> 866 inline bool 867 operator!=(const set<_Key, _Compare, _Alloc>& __x, 868 const set<_Key, _Compare, _Alloc>& __y) 869 { return !(__x == __y); } 870 871 /// Returns y < x. 872 template<typename _Key, typename _Compare, typename _Alloc> 873 inline bool 874 operator>(const set<_Key, _Compare, _Alloc>& __x, 875 const set<_Key, _Compare, _Alloc>& __y) 876 { return __y < __x; } 877 878 /// Returns !(y < x) 879 template<typename _Key, typename _Compare, typename _Alloc> 880 inline bool 881 operator<=(const set<_Key, _Compare, _Alloc>& __x, 882 const set<_Key, _Compare, _Alloc>& __y) 883 { return !(__y < __x); } 884 885 /// Returns !(x < y) 886 template<typename _Key, typename _Compare, typename _Alloc> 887 inline bool 888 operator>=(const set<_Key, _Compare, _Alloc>& __x, 889 const set<_Key, _Compare, _Alloc>& __y) 890 { return !(__x < __y); } 891 892 /// See std::set::swap(). 893 template<typename _Key, typename _Compare, typename _Alloc> 894 inline void 895 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) 896 { __x.swap(__y); } 897 898 _GLIBCXX_END_NAMESPACE_CONTAINER 899 } //namespace std 900 #endif /* _STL_SET_H */ 901