libstdc++
|
00001 // Set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2017 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996,1997 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/stl_set.h 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{set} 00054 */ 00055 00056 #ifndef _STL_SET_H 00057 #define _STL_SET_H 1 00058 00059 #include <bits/concept_check.h> 00060 #if __cplusplus >= 201103L 00061 #include <initializer_list> 00062 #endif 00063 00064 namespace std _GLIBCXX_VISIBILITY(default) 00065 { 00066 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00067 00068 template<typename _Key, typename _Compare, typename _Alloc> 00069 class multiset; 00070 00071 /** 00072 * @brief A standard container made up of unique keys, which can be 00073 * retrieved in logarithmic time. 00074 * 00075 * @ingroup associative_containers 00076 * 00077 * @tparam _Key Type of key objects. 00078 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 00079 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00080 * 00081 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00082 * <a href="tables.html#66">reversible container</a>, and an 00083 * <a href="tables.html#69">associative container</a> (using unique keys). 00084 * 00085 * Sets support bidirectional iterators. 00086 * 00087 * The private tree data is declared exactly the same way for set and 00088 * multiset; the distinction is made entirely in how the tree functions are 00089 * called (*_unique versus *_equal, same as the standard). 00090 */ 00091 template<typename _Key, typename _Compare = std::less<_Key>, 00092 typename _Alloc = std::allocator<_Key> > 00093 class set 00094 { 00095 #ifdef _GLIBCXX_CONCEPT_CHECKS 00096 // concept requirements 00097 typedef typename _Alloc::value_type _Alloc_value_type; 00098 # if __cplusplus < 201103L 00099 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 00100 # endif 00101 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 00102 _BinaryFunctionConcept) 00103 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 00104 #endif 00105 00106 public: 00107 // typedefs: 00108 //@{ 00109 /// Public typedefs. 00110 typedef _Key key_type; 00111 typedef _Key value_type; 00112 typedef _Compare key_compare; 00113 typedef _Compare value_compare; 00114 typedef _Alloc allocator_type; 00115 //@} 00116 00117 private: 00118 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00119 rebind<_Key>::other _Key_alloc_type; 00120 00121 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 00122 key_compare, _Key_alloc_type> _Rep_type; 00123 _Rep_type _M_t; // Red-black tree representing set. 00124 00125 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; 00126 00127 public: 00128 //@{ 00129 /// Iterator-related typedefs. 00130 typedef typename _Alloc_traits::pointer pointer; 00131 typedef typename _Alloc_traits::const_pointer const_pointer; 00132 typedef typename _Alloc_traits::reference reference; 00133 typedef typename _Alloc_traits::const_reference const_reference; 00134 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00135 // DR 103. set::iterator is required to be modifiable, 00136 // but this allows modification of keys. 00137 typedef typename _Rep_type::const_iterator iterator; 00138 typedef typename _Rep_type::const_iterator const_iterator; 00139 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 00140 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00141 typedef typename _Rep_type::size_type size_type; 00142 typedef typename _Rep_type::difference_type difference_type; 00143 //@} 00144 00145 #if __cplusplus > 201402L 00146 using node_type = typename _Rep_type::node_type; 00147 using insert_return_type = typename _Rep_type::insert_return_type; 00148 #endif 00149 00150 // allocation/deallocation 00151 /** 00152 * @brief Default constructor creates no elements. 00153 */ 00154 #if __cplusplus < 201103L 00155 set() : _M_t() { } 00156 #else 00157 set() = default; 00158 #endif 00159 00160 /** 00161 * @brief Creates a %set with no elements. 00162 * @param __comp Comparator to use. 00163 * @param __a An allocator object. 00164 */ 00165 explicit 00166 set(const _Compare& __comp, 00167 const allocator_type& __a = allocator_type()) 00168 : _M_t(__comp, _Key_alloc_type(__a)) { } 00169 00170 /** 00171 * @brief Builds a %set from a range. 00172 * @param __first An input iterator. 00173 * @param __last An input iterator. 00174 * 00175 * Create a %set consisting of copies of the elements from 00176 * [__first,__last). This is linear in N if the range is 00177 * already sorted, and NlogN otherwise (where N is 00178 * distance(__first,__last)). 00179 */ 00180 template<typename _InputIterator> 00181 set(_InputIterator __first, _InputIterator __last) 00182 : _M_t() 00183 { _M_t._M_insert_unique(__first, __last); } 00184 00185 /** 00186 * @brief Builds a %set from a range. 00187 * @param __first An input iterator. 00188 * @param __last An input iterator. 00189 * @param __comp A comparison functor. 00190 * @param __a An allocator object. 00191 * 00192 * Create a %set consisting of copies of the elements from 00193 * [__first,__last). This is linear in N if the range is 00194 * already sorted, and NlogN otherwise (where N is 00195 * distance(__first,__last)). 00196 */ 00197 template<typename _InputIterator> 00198 set(_InputIterator __first, _InputIterator __last, 00199 const _Compare& __comp, 00200 const allocator_type& __a = allocator_type()) 00201 : _M_t(__comp, _Key_alloc_type(__a)) 00202 { _M_t._M_insert_unique(__first, __last); } 00203 00204 /** 00205 * @brief %Set copy constructor. 00206 * 00207 * Whether the allocator is copied depends on the allocator traits. 00208 */ 00209 #if __cplusplus < 201103L 00210 set(const set& __x) 00211 : _M_t(__x._M_t) { } 00212 #else 00213 set(const set&) = default; 00214 00215 /** 00216 * @brief %Set move constructor 00217 * 00218 * The newly-created %set contains the exact contents of the moved 00219 * instance. The moved instance is a valid, but unspecified, %set. 00220 */ 00221 set(set&&) = default; 00222 00223 /** 00224 * @brief Builds a %set from an initializer_list. 00225 * @param __l An initializer_list. 00226 * @param __comp A comparison functor. 00227 * @param __a An allocator object. 00228 * 00229 * Create a %set consisting of copies of the elements in the list. 00230 * This is linear in N if the list is already sorted, and NlogN 00231 * otherwise (where N is @a __l.size()). 00232 */ 00233 set(initializer_list<value_type> __l, 00234 const _Compare& __comp = _Compare(), 00235 const allocator_type& __a = allocator_type()) 00236 : _M_t(__comp, _Key_alloc_type(__a)) 00237 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 00238 00239 /// Allocator-extended default constructor. 00240 explicit 00241 set(const allocator_type& __a) 00242 : _M_t(_Compare(), _Key_alloc_type(__a)) { } 00243 00244 /// Allocator-extended copy constructor. 00245 set(const set& __x, const allocator_type& __a) 00246 : _M_t(__x._M_t, _Key_alloc_type(__a)) { } 00247 00248 /// Allocator-extended move constructor. 00249 set(set&& __x, const allocator_type& __a) 00250 noexcept(is_nothrow_copy_constructible<_Compare>::value 00251 && _Alloc_traits::_S_always_equal()) 00252 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { } 00253 00254 /// Allocator-extended initialier-list constructor. 00255 set(initializer_list<value_type> __l, const allocator_type& __a) 00256 : _M_t(_Compare(), _Key_alloc_type(__a)) 00257 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 00258 00259 /// Allocator-extended range constructor. 00260 template<typename _InputIterator> 00261 set(_InputIterator __first, _InputIterator __last, 00262 const allocator_type& __a) 00263 : _M_t(_Compare(), _Key_alloc_type(__a)) 00264 { _M_t._M_insert_unique(__first, __last); } 00265 00266 /** 00267 * The dtor only erases the elements, and note that if the elements 00268 * themselves are pointers, the pointed-to memory is not touched in any 00269 * way. Managing the pointer is the user's responsibility. 00270 */ 00271 ~set() = default; 00272 #endif 00273 00274 /** 00275 * @brief %Set assignment operator. 00276 * 00277 * Whether the allocator is copied depends on the allocator traits. 00278 */ 00279 #if __cplusplus < 201103L 00280 set& 00281 operator=(const set& __x) 00282 { 00283 _M_t = __x._M_t; 00284 return *this; 00285 } 00286 #else 00287 set& 00288 operator=(const set&) = default; 00289 00290 /// Move assignment operator. 00291 set& 00292 operator=(set&&) = default; 00293 00294 /** 00295 * @brief %Set list assignment operator. 00296 * @param __l An initializer_list. 00297 * 00298 * This function fills a %set with copies of the elements in the 00299 * initializer list @a __l. 00300 * 00301 * Note that the assignment completely changes the %set and 00302 * that the resulting %set's size is the same as the number 00303 * of elements assigned. 00304 */ 00305 set& 00306 operator=(initializer_list<value_type> __l) 00307 { 00308 _M_t._M_assign_unique(__l.begin(), __l.end()); 00309 return *this; 00310 } 00311 #endif 00312 00313 // accessors: 00314 00315 /// Returns the comparison object with which the %set was constructed. 00316 key_compare 00317 key_comp() const 00318 { return _M_t.key_comp(); } 00319 /// Returns the comparison object with which the %set was constructed. 00320 value_compare 00321 value_comp() const 00322 { return _M_t.key_comp(); } 00323 /// Returns the allocator object with which the %set was constructed. 00324 allocator_type 00325 get_allocator() const _GLIBCXX_NOEXCEPT 00326 { return allocator_type(_M_t.get_allocator()); } 00327 00328 /** 00329 * Returns a read-only (constant) iterator that points to the first 00330 * element in the %set. Iteration is done in ascending order according 00331 * to the keys. 00332 */ 00333 iterator 00334 begin() const _GLIBCXX_NOEXCEPT 00335 { return _M_t.begin(); } 00336 00337 /** 00338 * Returns a read-only (constant) iterator that points one past the last 00339 * element in the %set. Iteration is done in ascending order according 00340 * to the keys. 00341 */ 00342 iterator 00343 end() const _GLIBCXX_NOEXCEPT 00344 { return _M_t.end(); } 00345 00346 /** 00347 * Returns a read-only (constant) iterator that points to the last 00348 * element in the %set. Iteration is done in descending order according 00349 * to the keys. 00350 */ 00351 reverse_iterator 00352 rbegin() const _GLIBCXX_NOEXCEPT 00353 { return _M_t.rbegin(); } 00354 00355 /** 00356 * Returns a read-only (constant) reverse iterator that points to the 00357 * last pair in the %set. Iteration is done in descending order 00358 * according to the keys. 00359 */ 00360 reverse_iterator 00361 rend() const _GLIBCXX_NOEXCEPT 00362 { return _M_t.rend(); } 00363 00364 #if __cplusplus >= 201103L 00365 /** 00366 * Returns a read-only (constant) iterator that points to the first 00367 * element in the %set. Iteration is done in ascending order according 00368 * to the keys. 00369 */ 00370 iterator 00371 cbegin() const noexcept 00372 { return _M_t.begin(); } 00373 00374 /** 00375 * Returns a read-only (constant) iterator that points one past the last 00376 * element in the %set. Iteration is done in ascending order according 00377 * to the keys. 00378 */ 00379 iterator 00380 cend() const noexcept 00381 { return _M_t.end(); } 00382 00383 /** 00384 * Returns a read-only (constant) iterator that points to the last 00385 * element in the %set. Iteration is done in descending order according 00386 * to the keys. 00387 */ 00388 reverse_iterator 00389 crbegin() const noexcept 00390 { return _M_t.rbegin(); } 00391 00392 /** 00393 * Returns a read-only (constant) reverse iterator that points to the 00394 * last pair in the %set. Iteration is done in descending order 00395 * according to the keys. 00396 */ 00397 reverse_iterator 00398 crend() const noexcept 00399 { return _M_t.rend(); } 00400 #endif 00401 00402 /// Returns true if the %set is empty. 00403 bool 00404 empty() const _GLIBCXX_NOEXCEPT 00405 { return _M_t.empty(); } 00406 00407 /// Returns the size of the %set. 00408 size_type 00409 size() const _GLIBCXX_NOEXCEPT 00410 { return _M_t.size(); } 00411 00412 /// Returns the maximum size of the %set. 00413 size_type 00414 max_size() const _GLIBCXX_NOEXCEPT 00415 { return _M_t.max_size(); } 00416 00417 /** 00418 * @brief Swaps data with another %set. 00419 * @param __x A %set of the same element and allocator types. 00420 * 00421 * This exchanges the elements between two sets in constant 00422 * time. (It is only swapping a pointer, an integer, and an 00423 * instance of the @c Compare type (which itself is often 00424 * stateless and empty), so it should be quite fast.) Note 00425 * that the global std::swap() function is specialized such 00426 * that std::swap(s1,s2) will feed to this function. 00427 * 00428 * Whether the allocators are swapped depends on the allocator traits. 00429 */ 00430 void 00431 swap(set& __x) 00432 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 00433 { _M_t.swap(__x._M_t); } 00434 00435 // insert/erase 00436 #if __cplusplus >= 201103L 00437 /** 00438 * @brief Attempts to build and insert an element into the %set. 00439 * @param __args Arguments used to generate an element. 00440 * @return A pair, of which the first element is an iterator that points 00441 * to the possibly inserted element, and the second is a bool 00442 * that is true if the element was actually inserted. 00443 * 00444 * This function attempts to build and insert an element into the %set. 00445 * A %set relies on unique keys and thus an element is only inserted if 00446 * it is not already present in the %set. 00447 * 00448 * Insertion requires logarithmic time. 00449 */ 00450 template<typename... _Args> 00451 std::pair<iterator, bool> 00452 emplace(_Args&&... __args) 00453 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } 00454 00455 /** 00456 * @brief Attempts to insert an element into the %set. 00457 * @param __pos An iterator that serves as a hint as to where the 00458 * element should be inserted. 00459 * @param __args Arguments used to generate the element to be 00460 * inserted. 00461 * @return An iterator that points to the element with key equivalent to 00462 * the one generated from @a __args (may or may not be the 00463 * element itself). 00464 * 00465 * This function is not concerned about whether the insertion took place, 00466 * and thus does not return a boolean like the single-argument emplace() 00467 * does. Note that the first parameter is only a hint and can 00468 * potentially improve the performance of the insertion process. A bad 00469 * hint would cause no gains in efficiency. 00470 * 00471 * For more on @a hinting, see: 00472 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00473 * 00474 * Insertion requires logarithmic time (if the hint is not taken). 00475 */ 00476 template<typename... _Args> 00477 iterator 00478 emplace_hint(const_iterator __pos, _Args&&... __args) 00479 { 00480 return _M_t._M_emplace_hint_unique(__pos, 00481 std::forward<_Args>(__args)...); 00482 } 00483 #endif 00484 00485 /** 00486 * @brief Attempts to insert an element into the %set. 00487 * @param __x Element to be inserted. 00488 * @return A pair, of which the first element is an iterator that points 00489 * to the possibly inserted element, and the second is a bool 00490 * that is true if the element was actually inserted. 00491 * 00492 * This function attempts to insert an element into the %set. A %set 00493 * relies on unique keys and thus an element is only inserted if it is 00494 * not already present in the %set. 00495 * 00496 * Insertion requires logarithmic time. 00497 */ 00498 std::pair<iterator, bool> 00499 insert(const value_type& __x) 00500 { 00501 std::pair<typename _Rep_type::iterator, bool> __p = 00502 _M_t._M_insert_unique(__x); 00503 return std::pair<iterator, bool>(__p.first, __p.second); 00504 } 00505 00506 #if __cplusplus >= 201103L 00507 std::pair<iterator, bool> 00508 insert(value_type&& __x) 00509 { 00510 std::pair<typename _Rep_type::iterator, bool> __p = 00511 _M_t._M_insert_unique(std::move(__x)); 00512 return std::pair<iterator, bool>(__p.first, __p.second); 00513 } 00514 #endif 00515 00516 /** 00517 * @brief Attempts to insert an element into the %set. 00518 * @param __position An iterator that serves as a hint as to where the 00519 * element should be inserted. 00520 * @param __x Element to be inserted. 00521 * @return An iterator that points to the element with key of 00522 * @a __x (may or may not be the element passed in). 00523 * 00524 * This function is not concerned about whether the insertion took place, 00525 * and thus does not return a boolean like the single-argument insert() 00526 * does. Note that the first parameter is only a hint and can 00527 * potentially improve the performance of the insertion process. A bad 00528 * hint would cause no gains in efficiency. 00529 * 00530 * For more on @a hinting, see: 00531 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00532 * 00533 * Insertion requires logarithmic time (if the hint is not taken). 00534 */ 00535 iterator 00536 insert(const_iterator __position, const value_type& __x) 00537 { return _M_t._M_insert_unique_(__position, __x); } 00538 00539 #if __cplusplus >= 201103L 00540 iterator 00541 insert(const_iterator __position, value_type&& __x) 00542 { return _M_t._M_insert_unique_(__position, std::move(__x)); } 00543 #endif 00544 00545 /** 00546 * @brief A template function that attempts to insert a range 00547 * of elements. 00548 * @param __first Iterator pointing to the start of the range to be 00549 * inserted. 00550 * @param __last Iterator pointing to the end of the range. 00551 * 00552 * Complexity similar to that of the range constructor. 00553 */ 00554 template<typename _InputIterator> 00555 void 00556 insert(_InputIterator __first, _InputIterator __last) 00557 { _M_t._M_insert_unique(__first, __last); } 00558 00559 #if __cplusplus >= 201103L 00560 /** 00561 * @brief Attempts to insert a list of elements into the %set. 00562 * @param __l A std::initializer_list<value_type> of elements 00563 * to be inserted. 00564 * 00565 * Complexity similar to that of the range constructor. 00566 */ 00567 void 00568 insert(initializer_list<value_type> __l) 00569 { this->insert(__l.begin(), __l.end()); } 00570 #endif 00571 00572 #if __cplusplus > 201402L 00573 /// Extract a node. 00574 node_type 00575 extract(const_iterator __pos) 00576 { 00577 __glibcxx_assert(__pos != end()); 00578 return _M_t.extract(__pos); 00579 } 00580 00581 /// Extract a node. 00582 node_type 00583 extract(const key_type& __x) 00584 { return _M_t.extract(__x); } 00585 00586 /// Re-insert an extracted node. 00587 insert_return_type 00588 insert(node_type&& __nh) 00589 { return _M_t._M_reinsert_node_unique(std::move(__nh)); } 00590 00591 /// Re-insert an extracted node. 00592 iterator 00593 insert(const_iterator __hint, node_type&& __nh) 00594 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); } 00595 00596 template<typename, typename> 00597 friend class _Rb_tree_merge_helper; 00598 00599 template<typename _Compare1> 00600 void 00601 merge(set<_Key, _Compare1, _Alloc>& __source) 00602 { 00603 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>; 00604 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); 00605 } 00606 00607 template<typename _Compare1> 00608 void 00609 merge(set<_Key, _Compare1, _Alloc>&& __source) 00610 { merge(__source); } 00611 00612 template<typename _Compare1> 00613 void 00614 merge(multiset<_Key, _Compare1, _Alloc>& __source) 00615 { 00616 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>; 00617 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); 00618 } 00619 00620 template<typename _Compare1> 00621 void 00622 merge(multiset<_Key, _Compare1, _Alloc>&& __source) 00623 { merge(__source); } 00624 #endif // C++17 00625 00626 #if __cplusplus >= 201103L 00627 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00628 // DR 130. Associative erase should return an iterator. 00629 /** 00630 * @brief Erases an element from a %set. 00631 * @param __position An iterator pointing to the element to be erased. 00632 * @return An iterator pointing to the element immediately following 00633 * @a __position prior to the element being erased. If no such 00634 * element exists, end() is returned. 00635 * 00636 * This function erases an element, pointed to by the given iterator, 00637 * from a %set. Note that this function only erases the element, and 00638 * that if the element is itself a pointer, the pointed-to memory is not 00639 * touched in any way. Managing the pointer is the user's 00640 * responsibility. 00641 */ 00642 _GLIBCXX_ABI_TAG_CXX11 00643 iterator 00644 erase(const_iterator __position) 00645 { return _M_t.erase(__position); } 00646 #else 00647 /** 00648 * @brief Erases an element from a %set. 00649 * @param position An iterator pointing to the element to be erased. 00650 * 00651 * This function erases an element, pointed to by the given iterator, 00652 * from a %set. Note that this function only erases the element, and 00653 * that if the element is itself a pointer, the pointed-to memory is not 00654 * touched in any way. Managing the pointer is the user's 00655 * responsibility. 00656 */ 00657 void 00658 erase(iterator __position) 00659 { _M_t.erase(__position); } 00660 #endif 00661 00662 /** 00663 * @brief Erases elements according to the provided key. 00664 * @param __x Key of element to be erased. 00665 * @return The number of elements erased. 00666 * 00667 * This function erases all the elements located by the given key from 00668 * a %set. 00669 * Note that this function only erases the element, and that if 00670 * the element is itself a pointer, the pointed-to memory is not touched 00671 * in any way. Managing the pointer is the user's responsibility. 00672 */ 00673 size_type 00674 erase(const key_type& __x) 00675 { return _M_t.erase(__x); } 00676 00677 #if __cplusplus >= 201103L 00678 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00679 // DR 130. Associative erase should return an iterator. 00680 /** 00681 * @brief Erases a [__first,__last) range of elements from a %set. 00682 * @param __first Iterator pointing to the start of the range to be 00683 * erased. 00684 00685 * @param __last Iterator pointing to the end of the range to 00686 * be erased. 00687 * @return The iterator @a __last. 00688 * 00689 * This function erases a sequence of elements from a %set. 00690 * Note that this function only erases the element, and that if 00691 * the element is itself a pointer, the pointed-to memory is not touched 00692 * in any way. Managing the pointer is the user's responsibility. 00693 */ 00694 _GLIBCXX_ABI_TAG_CXX11 00695 iterator 00696 erase(const_iterator __first, const_iterator __last) 00697 { return _M_t.erase(__first, __last); } 00698 #else 00699 /** 00700 * @brief Erases a [first,last) range of elements from a %set. 00701 * @param __first Iterator pointing to the start of the range to be 00702 * erased. 00703 * @param __last Iterator pointing to the end of the range to 00704 * be erased. 00705 * 00706 * This function erases a sequence of elements from a %set. 00707 * Note that this function only erases the element, and that if 00708 * the element is itself a pointer, the pointed-to memory is not touched 00709 * in any way. Managing the pointer is the user's responsibility. 00710 */ 00711 void 00712 erase(iterator __first, iterator __last) 00713 { _M_t.erase(__first, __last); } 00714 #endif 00715 00716 /** 00717 * Erases all elements in a %set. Note that this function only erases 00718 * the elements, and that if the elements themselves are pointers, the 00719 * pointed-to memory is not touched in any way. Managing the pointer is 00720 * the user's responsibility. 00721 */ 00722 void 00723 clear() _GLIBCXX_NOEXCEPT 00724 { _M_t.clear(); } 00725 00726 // set operations: 00727 00728 //@{ 00729 /** 00730 * @brief Finds the number of elements. 00731 * @param __x Element to located. 00732 * @return Number of elements with specified key. 00733 * 00734 * This function only makes sense for multisets; for set the result will 00735 * either be 0 (not present) or 1 (present). 00736 */ 00737 size_type 00738 count(const key_type& __x) const 00739 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 00740 00741 #if __cplusplus > 201103L 00742 template<typename _Kt> 00743 auto 00744 count(const _Kt& __x) const 00745 -> decltype(_M_t._M_count_tr(__x)) 00746 { return _M_t._M_count_tr(__x); } 00747 #endif 00748 //@} 00749 00750 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00751 // 214. set::find() missing const overload 00752 //@{ 00753 /** 00754 * @brief Tries to locate an element in a %set. 00755 * @param __x Element to be located. 00756 * @return Iterator pointing to sought-after element, or end() if not 00757 * found. 00758 * 00759 * This function takes a key and tries to locate the element with which 00760 * the key matches. If successful the function returns an iterator 00761 * pointing to the sought after element. If unsuccessful it returns the 00762 * past-the-end ( @c end() ) iterator. 00763 */ 00764 iterator 00765 find(const key_type& __x) 00766 { return _M_t.find(__x); } 00767 00768 const_iterator 00769 find(const key_type& __x) const 00770 { return _M_t.find(__x); } 00771 00772 #if __cplusplus > 201103L 00773 template<typename _Kt> 00774 auto 00775 find(const _Kt& __x) 00776 -> decltype(iterator{_M_t._M_find_tr(__x)}) 00777 { return iterator{_M_t._M_find_tr(__x)}; } 00778 00779 template<typename _Kt> 00780 auto 00781 find(const _Kt& __x) const 00782 -> decltype(const_iterator{_M_t._M_find_tr(__x)}) 00783 { return const_iterator{_M_t._M_find_tr(__x)}; } 00784 #endif 00785 //@} 00786 00787 //@{ 00788 /** 00789 * @brief Finds the beginning of a subsequence matching given key. 00790 * @param __x Key to be located. 00791 * @return Iterator pointing to first element equal to or greater 00792 * than key, or end(). 00793 * 00794 * This function returns the first element of a subsequence of elements 00795 * that matches the given key. If unsuccessful it returns an iterator 00796 * pointing to the first element that has a greater value than given key 00797 * or end() if no such element exists. 00798 */ 00799 iterator 00800 lower_bound(const key_type& __x) 00801 { return _M_t.lower_bound(__x); } 00802 00803 const_iterator 00804 lower_bound(const key_type& __x) const 00805 { return _M_t.lower_bound(__x); } 00806 00807 #if __cplusplus > 201103L 00808 template<typename _Kt> 00809 auto 00810 lower_bound(const _Kt& __x) 00811 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00812 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00813 00814 template<typename _Kt> 00815 auto 00816 lower_bound(const _Kt& __x) const 00817 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 00818 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 00819 #endif 00820 //@} 00821 00822 //@{ 00823 /** 00824 * @brief Finds the end of a subsequence matching given key. 00825 * @param __x Key to be located. 00826 * @return Iterator pointing to the first element 00827 * greater than key, or end(). 00828 */ 00829 iterator 00830 upper_bound(const key_type& __x) 00831 { return _M_t.upper_bound(__x); } 00832 00833 const_iterator 00834 upper_bound(const key_type& __x) const 00835 { return _M_t.upper_bound(__x); } 00836 00837 #if __cplusplus > 201103L 00838 template<typename _Kt> 00839 auto 00840 upper_bound(const _Kt& __x) 00841 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00842 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00843 00844 template<typename _Kt> 00845 auto 00846 upper_bound(const _Kt& __x) const 00847 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00848 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 00849 #endif 00850 //@} 00851 00852 //@{ 00853 /** 00854 * @brief Finds a subsequence matching given key. 00855 * @param __x Key to be located. 00856 * @return Pair of iterators that possibly points to the subsequence 00857 * matching given key. 00858 * 00859 * This function is equivalent to 00860 * @code 00861 * std::make_pair(c.lower_bound(val), 00862 * c.upper_bound(val)) 00863 * @endcode 00864 * (but is faster than making the calls separately). 00865 * 00866 * This function probably only makes sense for multisets. 00867 */ 00868 std::pair<iterator, iterator> 00869 equal_range(const key_type& __x) 00870 { return _M_t.equal_range(__x); } 00871 00872 std::pair<const_iterator, const_iterator> 00873 equal_range(const key_type& __x) const 00874 { return _M_t.equal_range(__x); } 00875 00876 #if __cplusplus > 201103L 00877 template<typename _Kt> 00878 auto 00879 equal_range(const _Kt& __x) 00880 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 00881 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 00882 00883 template<typename _Kt> 00884 auto 00885 equal_range(const _Kt& __x) const 00886 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 00887 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 00888 #endif 00889 //@} 00890 00891 template<typename _K1, typename _C1, typename _A1> 00892 friend bool 00893 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 00894 00895 template<typename _K1, typename _C1, typename _A1> 00896 friend bool 00897 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 00898 }; 00899 00900 00901 /** 00902 * @brief Set equality comparison. 00903 * @param __x A %set. 00904 * @param __y A %set of the same type as @a x. 00905 * @return True iff the size and elements of the sets are equal. 00906 * 00907 * This is an equivalence relation. It is linear in the size of the sets. 00908 * Sets are considered equivalent if their sizes are equal, and if 00909 * corresponding elements compare equal. 00910 */ 00911 template<typename _Key, typename _Compare, typename _Alloc> 00912 inline bool 00913 operator==(const set<_Key, _Compare, _Alloc>& __x, 00914 const set<_Key, _Compare, _Alloc>& __y) 00915 { return __x._M_t == __y._M_t; } 00916 00917 /** 00918 * @brief Set ordering relation. 00919 * @param __x A %set. 00920 * @param __y A %set of the same type as @a x. 00921 * @return True iff @a __x is lexicographically less than @a __y. 00922 * 00923 * This is a total ordering relation. It is linear in the size of the 00924 * sets. The elements must be comparable with @c <. 00925 * 00926 * See std::lexicographical_compare() for how the determination is made. 00927 */ 00928 template<typename _Key, typename _Compare, typename _Alloc> 00929 inline bool 00930 operator<(const set<_Key, _Compare, _Alloc>& __x, 00931 const set<_Key, _Compare, _Alloc>& __y) 00932 { return __x._M_t < __y._M_t; } 00933 00934 /// Returns !(x == y). 00935 template<typename _Key, typename _Compare, typename _Alloc> 00936 inline bool 00937 operator!=(const set<_Key, _Compare, _Alloc>& __x, 00938 const set<_Key, _Compare, _Alloc>& __y) 00939 { return !(__x == __y); } 00940 00941 /// Returns y < x. 00942 template<typename _Key, typename _Compare, typename _Alloc> 00943 inline bool 00944 operator>(const set<_Key, _Compare, _Alloc>& __x, 00945 const set<_Key, _Compare, _Alloc>& __y) 00946 { return __y < __x; } 00947 00948 /// Returns !(y < x) 00949 template<typename _Key, typename _Compare, typename _Alloc> 00950 inline bool 00951 operator<=(const set<_Key, _Compare, _Alloc>& __x, 00952 const set<_Key, _Compare, _Alloc>& __y) 00953 { return !(__y < __x); } 00954 00955 /// Returns !(x < y) 00956 template<typename _Key, typename _Compare, typename _Alloc> 00957 inline bool 00958 operator>=(const set<_Key, _Compare, _Alloc>& __x, 00959 const set<_Key, _Compare, _Alloc>& __y) 00960 { return !(__x < __y); } 00961 00962 /// See std::set::swap(). 00963 template<typename _Key, typename _Compare, typename _Alloc> 00964 inline void 00965 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) 00966 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 00967 { __x.swap(__y); } 00968 00969 _GLIBCXX_END_NAMESPACE_CONTAINER 00970 00971 #if __cplusplus > 201402L 00972 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00973 // Allow std::set access to internals of compatible sets. 00974 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2> 00975 struct 00976 _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2> 00977 { 00978 private: 00979 friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>; 00980 00981 static auto& 00982 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) 00983 { return __set._M_t; } 00984 00985 static auto& 00986 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) 00987 { return __set._M_t; } 00988 }; 00989 _GLIBCXX_END_NAMESPACE_VERSION 00990 #endif // C++17 00991 00992 } //namespace std 00993 #endif /* _STL_SET_H */