libstdc++
|
00001 // unordered_set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2010-2013 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 /** @file bits/unordered_set.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{unordered_set} 00028 */ 00029 00030 #ifndef _UNORDERED_SET_H 00031 #define _UNORDERED_SET_H 00032 00033 namespace std _GLIBCXX_VISIBILITY(default) 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00036 00037 /// Base types for unordered_set. 00038 template<bool _Cache> 00039 using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; 00040 00041 template<typename _Value, 00042 typename _Hash = hash<_Value>, 00043 typename _Pred = std::equal_to<_Value>, 00044 typename _Alloc = std::allocator<_Value>, 00045 typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> 00046 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, 00047 __detail::_Identity, _Pred, _Hash, 00048 __detail::_Mod_range_hashing, 00049 __detail::_Default_ranged_hash, 00050 __detail::_Prime_rehash_policy, _Tr>; 00051 00052 /// Base types for unordered_multiset. 00053 template<bool _Cache> 00054 using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; 00055 00056 template<typename _Value, 00057 typename _Hash = hash<_Value>, 00058 typename _Pred = std::equal_to<_Value>, 00059 typename _Alloc = std::allocator<_Value>, 00060 typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> 00061 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, 00062 __detail::_Identity, 00063 _Pred, _Hash, 00064 __detail::_Mod_range_hashing, 00065 __detail::_Default_ranged_hash, 00066 __detail::_Prime_rehash_policy, _Tr>; 00067 00068 /** 00069 * @brief A standard container composed of unique keys (containing 00070 * at most one of each key value) in which the elements' keys are 00071 * the elements themselves. 00072 * 00073 * @ingroup unordered_associative_containers 00074 * 00075 * @tparam _Value Type of key objects. 00076 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 00077 00078 * @tparam _Pred Predicate function object type, defaults to 00079 * equal_to<_Value>. 00080 * 00081 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00082 * 00083 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00084 * <a href="tables.html#xx">unordered associative container</a> 00085 * 00086 * Base is _Hashtable, dispatched at compile time via template 00087 * alias __uset_hashtable. 00088 */ 00089 template<class _Value, 00090 class _Hash = hash<_Value>, 00091 class _Pred = std::equal_to<_Value>, 00092 class _Alloc = std::allocator<_Value> > 00093 class unordered_set : __check_copy_constructible<_Alloc> 00094 { 00095 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 00096 _Hashtable _M_h; 00097 00098 public: 00099 // typedefs: 00100 //@{ 00101 /// Public typedefs. 00102 typedef typename _Hashtable::key_type key_type; 00103 typedef typename _Hashtable::value_type value_type; 00104 typedef typename _Hashtable::hasher hasher; 00105 typedef typename _Hashtable::key_equal key_equal; 00106 typedef typename _Hashtable::allocator_type allocator_type; 00107 //@} 00108 00109 //@{ 00110 /// Iterator-related typedefs. 00111 typedef typename allocator_type::pointer pointer; 00112 typedef typename allocator_type::const_pointer const_pointer; 00113 typedef typename allocator_type::reference reference; 00114 typedef typename allocator_type::const_reference const_reference; 00115 typedef typename _Hashtable::iterator iterator; 00116 typedef typename _Hashtable::const_iterator const_iterator; 00117 typedef typename _Hashtable::local_iterator local_iterator; 00118 typedef typename _Hashtable::const_local_iterator const_local_iterator; 00119 typedef typename _Hashtable::size_type size_type; 00120 typedef typename _Hashtable::difference_type difference_type; 00121 //@} 00122 00123 // construct/destroy/copy 00124 /** 00125 * @brief Default constructor creates no elements. 00126 * @param __n Initial number of buckets. 00127 * @param __hf A hash functor. 00128 * @param __eql A key equality functor. 00129 * @param __a An allocator object. 00130 */ 00131 explicit 00132 unordered_set(size_type __n = 10, 00133 const hasher& __hf = hasher(), 00134 const key_equal& __eql = key_equal(), 00135 const allocator_type& __a = allocator_type()) 00136 : _M_h(__n, __hf, __eql, __a) 00137 { } 00138 00139 /** 00140 * @brief Builds an %unordered_set from a range. 00141 * @param __first An input iterator. 00142 * @param __last An input iterator. 00143 * @param __n Minimal initial number of buckets. 00144 * @param __hf A hash functor. 00145 * @param __eql A key equality functor. 00146 * @param __a An allocator object. 00147 * 00148 * Create an %unordered_set consisting of copies of the elements from 00149 * [__first,__last). This is linear in N (where N is 00150 * distance(__first,__last)). 00151 */ 00152 template<typename _InputIterator> 00153 unordered_set(_InputIterator __f, _InputIterator __l, 00154 size_type __n = 0, 00155 const hasher& __hf = hasher(), 00156 const key_equal& __eql = key_equal(), 00157 const allocator_type& __a = allocator_type()) 00158 : _M_h(__f, __l, __n, __hf, __eql, __a) 00159 { } 00160 00161 /// Copy constructor. 00162 unordered_set(const unordered_set&) = default; 00163 00164 /// Move constructor. 00165 unordered_set(unordered_set&&) = default; 00166 00167 /** 00168 * @brief Builds an %unordered_set from an initializer_list. 00169 * @param __l An initializer_list. 00170 * @param __n Minimal initial number of buckets. 00171 * @param __hf A hash functor. 00172 * @param __eql A key equality functor. 00173 * @param __a An allocator object. 00174 * 00175 * Create an %unordered_set consisting of copies of the elements in the 00176 * list. This is linear in N (where N is @a __l.size()). 00177 */ 00178 unordered_set(initializer_list<value_type> __l, 00179 size_type __n = 0, 00180 const hasher& __hf = hasher(), 00181 const key_equal& __eql = key_equal(), 00182 const allocator_type& __a = allocator_type()) 00183 : _M_h(__l, __n, __hf, __eql, __a) 00184 { } 00185 00186 /// Copy assignment operator. 00187 unordered_set& 00188 operator=(const unordered_set&) = default; 00189 00190 /// Move assignment operator. 00191 unordered_set& 00192 operator=(unordered_set&&) = default; 00193 00194 /** 00195 * @brief %Unordered_set list assignment operator. 00196 * @param __l An initializer_list. 00197 * 00198 * This function fills an %unordered_set with copies of the elements in 00199 * the initializer list @a __l. 00200 * 00201 * Note that the assignment completely changes the %unordered_set and 00202 * that the resulting %unordered_set's size is the same as the number 00203 * of elements assigned. Old data may be lost. 00204 */ 00205 unordered_set& 00206 operator=(initializer_list<value_type> __l) 00207 { 00208 _M_h = __l; 00209 return *this; 00210 } 00211 00212 /// Returns the allocator object with which the %unordered_set was 00213 /// constructed. 00214 allocator_type 00215 get_allocator() const noexcept 00216 { return _M_h.get_allocator(); } 00217 00218 // size and capacity: 00219 00220 /// Returns true if the %unordered_set is empty. 00221 bool 00222 empty() const noexcept 00223 { return _M_h.empty(); } 00224 00225 /// Returns the size of the %unordered_set. 00226 size_type 00227 size() const noexcept 00228 { return _M_h.size(); } 00229 00230 /// Returns the maximum size of the %unordered_set. 00231 size_type 00232 max_size() const noexcept 00233 { return _M_h.max_size(); } 00234 00235 // iterators. 00236 00237 //@{ 00238 /** 00239 * Returns a read-only (constant) iterator that points to the first 00240 * element in the %unordered_set. 00241 */ 00242 iterator 00243 begin() noexcept 00244 { return _M_h.begin(); } 00245 00246 const_iterator 00247 begin() const noexcept 00248 { return _M_h.begin(); } 00249 //@} 00250 00251 //@{ 00252 /** 00253 * Returns a read-only (constant) iterator that points one past the last 00254 * element in the %unordered_set. 00255 */ 00256 iterator 00257 end() noexcept 00258 { return _M_h.end(); } 00259 00260 const_iterator 00261 end() const noexcept 00262 { return _M_h.end(); } 00263 //@} 00264 00265 /** 00266 * Returns a read-only (constant) iterator that points to the first 00267 * element in the %unordered_set. 00268 */ 00269 const_iterator 00270 cbegin() const noexcept 00271 { return _M_h.begin(); } 00272 00273 /** 00274 * Returns a read-only (constant) iterator that points one past the last 00275 * element in the %unordered_set. 00276 */ 00277 const_iterator 00278 cend() const noexcept 00279 { return _M_h.end(); } 00280 00281 // modifiers. 00282 00283 /** 00284 * @brief Attempts to build and insert an element into the 00285 * %unordered_set. 00286 * @param __args Arguments used to generate an element. 00287 * @return A pair, of which the first element is an iterator that points 00288 * to the possibly inserted element, and the second is a bool 00289 * that is true if the element was actually inserted. 00290 * 00291 * This function attempts to build and insert an element into the 00292 * %unordered_set. An %unordered_set relies on unique keys and thus an 00293 * element is only inserted if it is not already present in the 00294 * %unordered_set. 00295 * 00296 * Insertion requires amortized constant time. 00297 */ 00298 template<typename... _Args> 00299 std::pair<iterator, bool> 00300 emplace(_Args&&... __args) 00301 { return _M_h.emplace(std::forward<_Args>(__args)...); } 00302 00303 /** 00304 * @brief Attempts to insert an element into the %unordered_set. 00305 * @param __pos An iterator that serves as a hint as to where the 00306 * element should be inserted. 00307 * @param __args Arguments used to generate the element to be 00308 * inserted. 00309 * @return An iterator that points to the element with key equivalent to 00310 * the one generated from @a __args (may or may not be the 00311 * element itself). 00312 * 00313 * This function is not concerned about whether the insertion took place, 00314 * and thus does not return a boolean like the single-argument emplace() 00315 * does. Note that the first parameter is only a hint and can 00316 * potentially improve the performance of the insertion process. A bad 00317 * hint would cause no gains in efficiency. 00318 * 00319 * For more on @a hinting, see: 00320 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 00321 * 00322 * Insertion requires amortized constant time. 00323 */ 00324 template<typename... _Args> 00325 iterator 00326 emplace_hint(const_iterator __pos, _Args&&... __args) 00327 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 00328 00329 //@{ 00330 /** 00331 * @brief Attempts to insert an element into the %unordered_set. 00332 * @param __x Element to be inserted. 00333 * @return A pair, of which the first element is an iterator that points 00334 * to the possibly inserted element, and the second is a bool 00335 * that is true if the element was actually inserted. 00336 * 00337 * This function attempts to insert an element into the %unordered_set. 00338 * An %unordered_set relies on unique keys and thus an element is only 00339 * inserted if it is not already present in the %unordered_set. 00340 * 00341 * Insertion requires amortized constant time. 00342 */ 00343 std::pair<iterator, bool> 00344 insert(const value_type& __x) 00345 { return _M_h.insert(__x); } 00346 00347 std::pair<iterator, bool> 00348 insert(value_type&& __x) 00349 { return _M_h.insert(std::move(__x)); } 00350 //@} 00351 00352 //@{ 00353 /** 00354 * @brief Attempts to insert an element into the %unordered_set. 00355 * @param __hint An iterator that serves as a hint as to where the 00356 * element should be inserted. 00357 * @param __x Element to be inserted. 00358 * @return An iterator that points to the element with key of 00359 * @a __x (may or may not be the element passed in). 00360 * 00361 * This function is not concerned about whether the insertion took place, 00362 * and thus does not return a boolean like the single-argument insert() 00363 * does. Note that the first parameter is only a hint and can 00364 * potentially improve the performance of the insertion process. A bad 00365 * hint would cause no gains in efficiency. 00366 * 00367 * For more on @a hinting, see: 00368 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 00369 * 00370 * Insertion requires amortized constant. 00371 */ 00372 iterator 00373 insert(const_iterator __hint, const value_type& __x) 00374 { return _M_h.insert(__hint, __x); } 00375 00376 iterator 00377 insert(const_iterator __hint, value_type&& __x) 00378 { return _M_h.insert(__hint, std::move(__x)); } 00379 //@} 00380 00381 /** 00382 * @brief A template function that attempts to insert a range of 00383 * elements. 00384 * @param __first Iterator pointing to the start of the range to be 00385 * inserted. 00386 * @param __last Iterator pointing to the end of the range. 00387 * 00388 * Complexity similar to that of the range constructor. 00389 */ 00390 template<typename _InputIterator> 00391 void 00392 insert(_InputIterator __first, _InputIterator __last) 00393 { _M_h.insert(__first, __last); } 00394 00395 /** 00396 * @brief Attempts to insert a list of elements into the %unordered_set. 00397 * @param __l A std::initializer_list<value_type> of elements 00398 * to be inserted. 00399 * 00400 * Complexity similar to that of the range constructor. 00401 */ 00402 void 00403 insert(initializer_list<value_type> __l) 00404 { _M_h.insert(__l); } 00405 00406 //@{ 00407 /** 00408 * @brief Erases an element from an %unordered_set. 00409 * @param __position An iterator pointing to the element to be erased. 00410 * @return An iterator pointing to the element immediately following 00411 * @a __position prior to the element being erased. If no such 00412 * element exists, end() is returned. 00413 * 00414 * This function erases an element, pointed to by the given iterator, 00415 * from an %unordered_set. Note that this function only erases the 00416 * element, and that if the element is itself a pointer, the pointed-to 00417 * memory is not touched in any way. Managing the pointer is the user's 00418 * responsibility. 00419 */ 00420 iterator 00421 erase(const_iterator __position) 00422 { return _M_h.erase(__position); } 00423 00424 // LWG 2059. 00425 iterator 00426 erase(iterator __it) 00427 { return _M_h.erase(__it); } 00428 //@} 00429 00430 /** 00431 * @brief Erases elements according to the provided key. 00432 * @param __x Key of element to be erased. 00433 * @return The number of elements erased. 00434 * 00435 * This function erases all the elements located by the given key from 00436 * an %unordered_set. For an %unordered_set the result of this function 00437 * can only be 0 (not present) or 1 (present). 00438 * Note that this function only erases the element, and that if 00439 * the element is itself a pointer, the pointed-to memory is not touched 00440 * in any way. Managing the pointer is the user's responsibility. 00441 */ 00442 size_type 00443 erase(const key_type& __x) 00444 { return _M_h.erase(__x); } 00445 00446 /** 00447 * @brief Erases a [__first,__last) range of elements from an 00448 * %unordered_set. 00449 * @param __first Iterator pointing to the start of the range to be 00450 * erased. 00451 * @param __last Iterator pointing to the end of the range to 00452 * be erased. 00453 * @return The iterator @a __last. 00454 * 00455 * This function erases a sequence of elements from an %unordered_set. 00456 * Note that this function only erases the element, and that if 00457 * the element is itself a pointer, the pointed-to memory is not touched 00458 * in any way. Managing the pointer is the user's responsibility. 00459 */ 00460 iterator 00461 erase(const_iterator __first, const_iterator __last) 00462 { return _M_h.erase(__first, __last); } 00463 00464 /** 00465 * Erases all elements in an %unordered_set. Note that this function only 00466 * erases the elements, and that if the elements themselves are pointers, 00467 * the pointed-to memory is not touched in any way. Managing the pointer 00468 * is the user's responsibility. 00469 */ 00470 void 00471 clear() noexcept 00472 { _M_h.clear(); } 00473 00474 /** 00475 * @brief Swaps data with another %unordered_set. 00476 * @param __x An %unordered_set of the same element and allocator 00477 * types. 00478 * 00479 * This exchanges the elements between two sets in constant time. 00480 * Note that the global std::swap() function is specialized such that 00481 * std::swap(s1,s2) will feed to this function. 00482 */ 00483 void 00484 swap(unordered_set& __x) 00485 { _M_h.swap(__x._M_h); } 00486 00487 // observers. 00488 00489 /// Returns the hash functor object with which the %unordered_set was 00490 /// constructed. 00491 hasher 00492 hash_function() const 00493 { return _M_h.hash_function(); } 00494 00495 /// Returns the key comparison object with which the %unordered_set was 00496 /// constructed. 00497 key_equal 00498 key_eq() const 00499 { return _M_h.key_eq(); } 00500 00501 // lookup. 00502 00503 //@{ 00504 /** 00505 * @brief Tries to locate an element in an %unordered_set. 00506 * @param __x Element to be located. 00507 * @return Iterator pointing to sought-after element, or end() if not 00508 * found. 00509 * 00510 * This function takes a key and tries to locate the element with which 00511 * the key matches. If successful the function returns an iterator 00512 * pointing to the sought after element. If unsuccessful it returns the 00513 * past-the-end ( @c end() ) iterator. 00514 */ 00515 iterator 00516 find(const key_type& __x) 00517 { return _M_h.find(__x); } 00518 00519 const_iterator 00520 find(const key_type& __x) const 00521 { return _M_h.find(__x); } 00522 //@} 00523 00524 /** 00525 * @brief Finds the number of elements. 00526 * @param __x Element to located. 00527 * @return Number of elements with specified key. 00528 * 00529 * This function only makes sense for unordered_multisets; for 00530 * unordered_set the result will either be 0 (not present) or 1 00531 * (present). 00532 */ 00533 size_type 00534 count(const key_type& __x) const 00535 { return _M_h.count(__x); } 00536 00537 //@{ 00538 /** 00539 * @brief Finds a subsequence matching given key. 00540 * @param __x Key to be located. 00541 * @return Pair of iterators that possibly points to the subsequence 00542 * matching given key. 00543 * 00544 * This function probably only makes sense for multisets. 00545 */ 00546 std::pair<iterator, iterator> 00547 equal_range(const key_type& __x) 00548 { return _M_h.equal_range(__x); } 00549 00550 std::pair<const_iterator, const_iterator> 00551 equal_range(const key_type& __x) const 00552 { return _M_h.equal_range(__x); } 00553 //@} 00554 00555 // bucket interface. 00556 00557 /// Returns the number of buckets of the %unordered_set. 00558 size_type 00559 bucket_count() const noexcept 00560 { return _M_h.bucket_count(); } 00561 00562 /// Returns the maximum number of buckets of the %unordered_set. 00563 size_type 00564 max_bucket_count() const noexcept 00565 { return _M_h.max_bucket_count(); } 00566 00567 /* 00568 * @brief Returns the number of elements in a given bucket. 00569 * @param __n A bucket index. 00570 * @return The number of elements in the bucket. 00571 */ 00572 size_type 00573 bucket_size(size_type __n) const 00574 { return _M_h.bucket_size(__n); } 00575 00576 /* 00577 * @brief Returns the bucket index of a given element. 00578 * @param __key A key instance. 00579 * @return The key bucket index. 00580 */ 00581 size_type 00582 bucket(const key_type& __key) const 00583 { return _M_h.bucket(__key); } 00584 00585 //@{ 00586 /** 00587 * @brief Returns a read-only (constant) iterator pointing to the first 00588 * bucket element. 00589 * @param __n The bucket index. 00590 * @return A read-only local iterator. 00591 */ 00592 local_iterator 00593 begin(size_type __n) 00594 { return _M_h.begin(__n); } 00595 00596 const_local_iterator 00597 begin(size_type __n) const 00598 { return _M_h.begin(__n); } 00599 00600 const_local_iterator 00601 cbegin(size_type __n) const 00602 { return _M_h.cbegin(__n); } 00603 //@} 00604 00605 //@{ 00606 /** 00607 * @brief Returns a read-only (constant) iterator pointing to one past 00608 * the last bucket elements. 00609 * @param __n The bucket index. 00610 * @return A read-only local iterator. 00611 */ 00612 local_iterator 00613 end(size_type __n) 00614 { return _M_h.end(__n); } 00615 00616 const_local_iterator 00617 end(size_type __n) const 00618 { return _M_h.end(__n); } 00619 00620 const_local_iterator 00621 cend(size_type __n) const 00622 { return _M_h.cend(__n); } 00623 //@} 00624 00625 // hash policy. 00626 00627 /// Returns the average number of elements per bucket. 00628 float 00629 load_factor() const noexcept 00630 { return _M_h.load_factor(); } 00631 00632 /// Returns a positive number that the %unordered_set tries to keep the 00633 /// load factor less than or equal to. 00634 float 00635 max_load_factor() const noexcept 00636 { return _M_h.max_load_factor(); } 00637 00638 /** 00639 * @brief Change the %unordered_set maximum load factor. 00640 * @param __z The new maximum load factor. 00641 */ 00642 void 00643 max_load_factor(float __z) 00644 { _M_h.max_load_factor(__z); } 00645 00646 /** 00647 * @brief May rehash the %unordered_set. 00648 * @param __n The new number of buckets. 00649 * 00650 * Rehash will occur only if the new number of buckets respect the 00651 * %unordered_set maximum load factor. 00652 */ 00653 void 00654 rehash(size_type __n) 00655 { _M_h.rehash(__n); } 00656 00657 /** 00658 * @brief Prepare the %unordered_set for a specified number of 00659 * elements. 00660 * @param __n Number of elements required. 00661 * 00662 * Same as rehash(ceil(n / max_load_factor())). 00663 */ 00664 void 00665 reserve(size_type __n) 00666 { _M_h.reserve(__n); } 00667 00668 template<typename _Value1, typename _Hash1, typename _Pred1, 00669 typename _Alloc1> 00670 friend bool 00671 operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&, 00672 const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&); 00673 }; 00674 00675 /** 00676 * @brief A standard container composed of equivalent keys 00677 * (possibly containing multiple of each key value) in which the 00678 * elements' keys are the elements themselves. 00679 * 00680 * @ingroup unordered_associative_containers 00681 * 00682 * @tparam _Value Type of key objects. 00683 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 00684 * @tparam _Pred Predicate function object type, defaults 00685 * to equal_to<_Value>. 00686 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00687 * 00688 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00689 * <a href="tables.html#xx">unordered associative container</a> 00690 * 00691 * Base is _Hashtable, dispatched at compile time via template 00692 * alias __umset_hashtable. 00693 */ 00694 template<class _Value, 00695 class _Hash = hash<_Value>, 00696 class _Pred = std::equal_to<_Value>, 00697 class _Alloc = std::allocator<_Value> > 00698 class unordered_multiset : __check_copy_constructible<_Alloc> 00699 { 00700 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 00701 _Hashtable _M_h; 00702 00703 public: 00704 // typedefs: 00705 //@{ 00706 /// Public typedefs. 00707 typedef typename _Hashtable::key_type key_type; 00708 typedef typename _Hashtable::value_type value_type; 00709 typedef typename _Hashtable::hasher hasher; 00710 typedef typename _Hashtable::key_equal key_equal; 00711 typedef typename _Hashtable::allocator_type allocator_type; 00712 //@} 00713 00714 //@{ 00715 /// Iterator-related typedefs. 00716 typedef typename allocator_type::pointer pointer; 00717 typedef typename allocator_type::const_pointer const_pointer; 00718 typedef typename allocator_type::reference reference; 00719 typedef typename allocator_type::const_reference const_reference; 00720 typedef typename _Hashtable::iterator iterator; 00721 typedef typename _Hashtable::const_iterator const_iterator; 00722 typedef typename _Hashtable::local_iterator local_iterator; 00723 typedef typename _Hashtable::const_local_iterator const_local_iterator; 00724 typedef typename _Hashtable::size_type size_type; 00725 typedef typename _Hashtable::difference_type difference_type; 00726 //@} 00727 00728 // construct/destroy/copy 00729 /** 00730 * @brief Default constructor creates no elements. 00731 * @param __n Initial number of buckets. 00732 * @param __hf A hash functor. 00733 * @param __eql A key equality functor. 00734 * @param __a An allocator object. 00735 */ 00736 explicit 00737 unordered_multiset(size_type __n = 10, 00738 const hasher& __hf = hasher(), 00739 const key_equal& __eql = key_equal(), 00740 const allocator_type& __a = allocator_type()) 00741 : _M_h(__n, __hf, __eql, __a) 00742 { } 00743 00744 /** 00745 * @brief Builds an %unordered_multiset from a range. 00746 * @param __first An input iterator. 00747 * @param __last An input iterator. 00748 * @param __n Minimal initial number of buckets. 00749 * @param __hf A hash functor. 00750 * @param __eql A key equality functor. 00751 * @param __a An allocator object. 00752 * 00753 * Create an %unordered_multiset consisting of copies of the elements 00754 * from [__first,__last). This is linear in N (where N is 00755 * distance(__first,__last)). 00756 */ 00757 template<typename _InputIterator> 00758 unordered_multiset(_InputIterator __f, _InputIterator __l, 00759 size_type __n = 0, 00760 const hasher& __hf = hasher(), 00761 const key_equal& __eql = key_equal(), 00762 const allocator_type& __a = allocator_type()) 00763 : _M_h(__f, __l, __n, __hf, __eql, __a) 00764 { } 00765 00766 /// Copy constructor. 00767 unordered_multiset(const unordered_multiset&) = default; 00768 00769 /// Move constructor. 00770 unordered_multiset(unordered_multiset&&) = default; 00771 00772 /** 00773 * @brief Builds an %unordered_multiset from an initializer_list. 00774 * @param __l An initializer_list. 00775 * @param __n Minimal initial number of buckets. 00776 * @param __hf A hash functor. 00777 * @param __eql A key equality functor. 00778 * @param __a An allocator object. 00779 * 00780 * Create an %unordered_multiset consisting of copies of the elements in 00781 * the list. This is linear in N (where N is @a __l.size()). 00782 */ 00783 unordered_multiset(initializer_list<value_type> __l, 00784 size_type __n = 0, 00785 const hasher& __hf = hasher(), 00786 const key_equal& __eql = key_equal(), 00787 const allocator_type& __a = allocator_type()) 00788 : _M_h(__l, __n, __hf, __eql, __a) 00789 { } 00790 00791 /// Copy assignment operator. 00792 unordered_multiset& 00793 operator=(const unordered_multiset&) = default; 00794 00795 /// Move assignment operator. 00796 unordered_multiset& 00797 operator=(unordered_multiset&& __x) = default; 00798 00799 /** 00800 * @brief %Unordered_multiset list assignment operator. 00801 * @param __l An initializer_list. 00802 * 00803 * This function fills an %unordered_multiset with copies of the elements 00804 * in the initializer list @a __l. 00805 * 00806 * Note that the assignment completely changes the %unordered_multiset 00807 * and that the resulting %unordered_set's size is the same as the number 00808 * of elements assigned. Old data may be lost. 00809 */ 00810 unordered_multiset& 00811 operator=(initializer_list<value_type> __l) 00812 { 00813 _M_h = __l; 00814 return *this; 00815 } 00816 00817 /// Returns the allocator object with which the %unordered_multiset was 00818 /// constructed. 00819 allocator_type 00820 get_allocator() const noexcept 00821 { return _M_h.get_allocator(); } 00822 00823 // size and capacity: 00824 00825 /// Returns true if the %unordered_multiset is empty. 00826 bool 00827 empty() const noexcept 00828 { return _M_h.empty(); } 00829 00830 /// Returns the size of the %unordered_multiset. 00831 size_type 00832 size() const noexcept 00833 { return _M_h.size(); } 00834 00835 /// Returns the maximum size of the %unordered_multiset. 00836 size_type 00837 max_size() const noexcept 00838 { return _M_h.max_size(); } 00839 00840 // iterators. 00841 00842 //@{ 00843 /** 00844 * Returns a read-only (constant) iterator that points to the first 00845 * element in the %unordered_multiset. 00846 */ 00847 iterator 00848 begin() noexcept 00849 { return _M_h.begin(); } 00850 00851 const_iterator 00852 begin() const noexcept 00853 { return _M_h.begin(); } 00854 //@} 00855 00856 //@{ 00857 /** 00858 * Returns a read-only (constant) iterator that points one past the last 00859 * element in the %unordered_multiset. 00860 */ 00861 iterator 00862 end() noexcept 00863 { return _M_h.end(); } 00864 00865 const_iterator 00866 end() const noexcept 00867 { return _M_h.end(); } 00868 //@} 00869 00870 /** 00871 * Returns a read-only (constant) iterator that points to the first 00872 * element in the %unordered_multiset. 00873 */ 00874 const_iterator 00875 cbegin() const noexcept 00876 { return _M_h.begin(); } 00877 00878 /** 00879 * Returns a read-only (constant) iterator that points one past the last 00880 * element in the %unordered_multiset. 00881 */ 00882 const_iterator 00883 cend() const noexcept 00884 { return _M_h.end(); } 00885 00886 // modifiers. 00887 00888 /** 00889 * @brief Builds and insert an element into the %unordered_multiset. 00890 * @param __args Arguments used to generate an element. 00891 * @return An iterator that points to the inserted element. 00892 * 00893 * Insertion requires amortized constant time. 00894 */ 00895 template<typename... _Args> 00896 iterator 00897 emplace(_Args&&... __args) 00898 { return _M_h.emplace(std::forward<_Args>(__args)...); } 00899 00900 /** 00901 * @brief Inserts an element into the %unordered_multiset. 00902 * @param __pos An iterator that serves as a hint as to where the 00903 * element should be inserted. 00904 * @param __args Arguments used to generate the element to be 00905 * inserted. 00906 * @return An iterator that points to the inserted element. 00907 * 00908 * Note that the first parameter is only a hint and can potentially 00909 * improve the performance of the insertion process. A bad hint would 00910 * cause no gains in efficiency. 00911 * 00912 * For more on @a hinting, see: 00913 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 00914 * 00915 * Insertion requires amortized constant time. 00916 */ 00917 template<typename... _Args> 00918 iterator 00919 emplace_hint(const_iterator __pos, _Args&&... __args) 00920 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 00921 00922 //@{ 00923 /** 00924 * @brief Inserts an element into the %unordered_multiset. 00925 * @param __x Element to be inserted. 00926 * @return An iterator that points to the inserted element. 00927 * 00928 * Insertion requires amortized constant time. 00929 */ 00930 iterator 00931 insert(const value_type& __x) 00932 { return _M_h.insert(__x); } 00933 00934 iterator 00935 insert(value_type&& __x) 00936 { return _M_h.insert(std::move(__x)); } 00937 //@} 00938 00939 //@{ 00940 /** 00941 * @brief Inserts an element into the %unordered_multiset. 00942 * @param __hint An iterator that serves as a hint as to where the 00943 * element should be inserted. 00944 * @param __x Element to be inserted. 00945 * @return An iterator that points to the inserted element. 00946 * 00947 * Note that the first parameter is only a hint and can potentially 00948 * improve the performance of the insertion process. A bad hint would 00949 * cause no gains in efficiency. 00950 * 00951 * For more on @a hinting, see: 00952 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 00953 * 00954 * Insertion requires amortized constant. 00955 */ 00956 iterator 00957 insert(const_iterator __hint, const value_type& __x) 00958 { return _M_h.insert(__hint, __x); } 00959 00960 iterator 00961 insert(const_iterator __hint, value_type&& __x) 00962 { return _M_h.insert(__hint, std::move(__x)); } 00963 //@} 00964 00965 /** 00966 * @brief A template function that inserts a range of elements. 00967 * @param __first Iterator pointing to the start of the range to be 00968 * inserted. 00969 * @param __last Iterator pointing to the end of the range. 00970 * 00971 * Complexity similar to that of the range constructor. 00972 */ 00973 template<typename _InputIterator> 00974 void 00975 insert(_InputIterator __first, _InputIterator __last) 00976 { _M_h.insert(__first, __last); } 00977 00978 /** 00979 * @brief Inserts a list of elements into the %unordered_multiset. 00980 * @param __l A std::initializer_list<value_type> of elements to be 00981 * inserted. 00982 * 00983 * Complexity similar to that of the range constructor. 00984 */ 00985 void 00986 insert(initializer_list<value_type> __l) 00987 { _M_h.insert(__l); } 00988 00989 //@{ 00990 /** 00991 * @brief Erases an element from an %unordered_multiset. 00992 * @param __position An iterator pointing to the element to be erased. 00993 * @return An iterator pointing to the element immediately following 00994 * @a __position prior to the element being erased. If no such 00995 * element exists, end() is returned. 00996 * 00997 * This function erases an element, pointed to by the given iterator, 00998 * from an %unordered_multiset. 00999 * 01000 * Note that this function only erases the element, and that if the 01001 * element is itself a pointer, the pointed-to memory is not touched in 01002 * any way. Managing the pointer is the user's responsibility. 01003 */ 01004 iterator 01005 erase(const_iterator __position) 01006 { return _M_h.erase(__position); } 01007 01008 // LWG 2059. 01009 iterator 01010 erase(iterator __it) 01011 { return _M_h.erase(__it); } 01012 //@} 01013 01014 01015 /** 01016 * @brief Erases elements according to the provided key. 01017 * @param __x Key of element to be erased. 01018 * @return The number of elements erased. 01019 * 01020 * This function erases all the elements located by the given key from 01021 * an %unordered_multiset. 01022 * 01023 * Note that this function only erases the element, and that if the 01024 * element is itself a pointer, the pointed-to memory is not touched in 01025 * any way. Managing the pointer is the user's responsibility. 01026 */ 01027 size_type 01028 erase(const key_type& __x) 01029 { return _M_h.erase(__x); } 01030 01031 /** 01032 * @brief Erases a [__first,__last) range of elements from an 01033 * %unordered_multiset. 01034 * @param __first Iterator pointing to the start of the range to be 01035 * erased. 01036 * @param __last Iterator pointing to the end of the range to 01037 * be erased. 01038 * @return The iterator @a __last. 01039 * 01040 * This function erases a sequence of elements from an 01041 * %unordered_multiset. 01042 * 01043 * Note that this function only erases the element, and that if 01044 * the element is itself a pointer, the pointed-to memory is not touched 01045 * in any way. Managing the pointer is the user's responsibility. 01046 */ 01047 iterator 01048 erase(const_iterator __first, const_iterator __last) 01049 { return _M_h.erase(__first, __last); } 01050 01051 /** 01052 * Erases all elements in an %unordered_multiset. 01053 * 01054 * Note that this function only erases the elements, and that if the 01055 * elements themselves are pointers, the pointed-to memory is not touched 01056 * in any way. Managing the pointer is the user's responsibility. 01057 */ 01058 void 01059 clear() noexcept 01060 { _M_h.clear(); } 01061 01062 /** 01063 * @brief Swaps data with another %unordered_multiset. 01064 * @param __x An %unordered_multiset of the same element and allocator 01065 * types. 01066 * 01067 * This exchanges the elements between two sets in constant time. 01068 * Note that the global std::swap() function is specialized such that 01069 * std::swap(s1,s2) will feed to this function. 01070 */ 01071 void 01072 swap(unordered_multiset& __x) 01073 { _M_h.swap(__x._M_h); } 01074 01075 // observers. 01076 01077 /// Returns the hash functor object with which the %unordered_multiset 01078 /// was constructed. 01079 hasher 01080 hash_function() const 01081 { return _M_h.hash_function(); } 01082 01083 /// Returns the key comparison object with which the %unordered_multiset 01084 /// was constructed. 01085 key_equal 01086 key_eq() const 01087 { return _M_h.key_eq(); } 01088 01089 // lookup. 01090 01091 //@{ 01092 /** 01093 * @brief Tries to locate an element in an %unordered_multiset. 01094 * @param __x Element to be located. 01095 * @return Iterator pointing to sought-after element, or end() if not 01096 * found. 01097 * 01098 * This function takes a key and tries to locate the element with which 01099 * the key matches. If successful the function returns an iterator 01100 * pointing to the sought after element. If unsuccessful it returns the 01101 * past-the-end ( @c end() ) iterator. 01102 */ 01103 iterator 01104 find(const key_type& __x) 01105 { return _M_h.find(__x); } 01106 01107 const_iterator 01108 find(const key_type& __x) const 01109 { return _M_h.find(__x); } 01110 //@} 01111 01112 /** 01113 * @brief Finds the number of elements. 01114 * @param __x Element to located. 01115 * @return Number of elements with specified key. 01116 */ 01117 size_type 01118 count(const key_type& __x) const 01119 { return _M_h.count(__x); } 01120 01121 //@{ 01122 /** 01123 * @brief Finds a subsequence matching given key. 01124 * @param __x Key to be located. 01125 * @return Pair of iterators that possibly points to the subsequence 01126 * matching given key. 01127 */ 01128 std::pair<iterator, iterator> 01129 equal_range(const key_type& __x) 01130 { return _M_h.equal_range(__x); } 01131 01132 std::pair<const_iterator, const_iterator> 01133 equal_range(const key_type& __x) const 01134 { return _M_h.equal_range(__x); } 01135 //@} 01136 01137 // bucket interface. 01138 01139 /// Returns the number of buckets of the %unordered_multiset. 01140 size_type 01141 bucket_count() const noexcept 01142 { return _M_h.bucket_count(); } 01143 01144 /// Returns the maximum number of buckets of the %unordered_multiset. 01145 size_type 01146 max_bucket_count() const noexcept 01147 { return _M_h.max_bucket_count(); } 01148 01149 /* 01150 * @brief Returns the number of elements in a given bucket. 01151 * @param __n A bucket index. 01152 * @return The number of elements in the bucket. 01153 */ 01154 size_type 01155 bucket_size(size_type __n) const 01156 { return _M_h.bucket_size(__n); } 01157 01158 /* 01159 * @brief Returns the bucket index of a given element. 01160 * @param __key A key instance. 01161 * @return The key bucket index. 01162 */ 01163 size_type 01164 bucket(const key_type& __key) const 01165 { return _M_h.bucket(__key); } 01166 01167 //@{ 01168 /** 01169 * @brief Returns a read-only (constant) iterator pointing to the first 01170 * bucket element. 01171 * @param __n The bucket index. 01172 * @return A read-only local iterator. 01173 */ 01174 local_iterator 01175 begin(size_type __n) 01176 { return _M_h.begin(__n); } 01177 01178 const_local_iterator 01179 begin(size_type __n) const 01180 { return _M_h.begin(__n); } 01181 01182 const_local_iterator 01183 cbegin(size_type __n) const 01184 { return _M_h.cbegin(__n); } 01185 //@} 01186 01187 //@{ 01188 /** 01189 * @brief Returns a read-only (constant) iterator pointing to one past 01190 * the last bucket elements. 01191 * @param __n The bucket index. 01192 * @return A read-only local iterator. 01193 */ 01194 local_iterator 01195 end(size_type __n) 01196 { return _M_h.end(__n); } 01197 01198 const_local_iterator 01199 end(size_type __n) const 01200 { return _M_h.end(__n); } 01201 01202 const_local_iterator 01203 cend(size_type __n) const 01204 { return _M_h.cend(__n); } 01205 //@} 01206 01207 // hash policy. 01208 01209 /// Returns the average number of elements per bucket. 01210 float 01211 load_factor() const noexcept 01212 { return _M_h.load_factor(); } 01213 01214 /// Returns a positive number that the %unordered_multiset tries to keep the 01215 /// load factor less than or equal to. 01216 float 01217 max_load_factor() const noexcept 01218 { return _M_h.max_load_factor(); } 01219 01220 /** 01221 * @brief Change the %unordered_multiset maximum load factor. 01222 * @param __z The new maximum load factor. 01223 */ 01224 void 01225 max_load_factor(float __z) 01226 { _M_h.max_load_factor(__z); } 01227 01228 /** 01229 * @brief May rehash the %unordered_multiset. 01230 * @param __n The new number of buckets. 01231 * 01232 * Rehash will occur only if the new number of buckets respect the 01233 * %unordered_multiset maximum load factor. 01234 */ 01235 void 01236 rehash(size_type __n) 01237 { _M_h.rehash(__n); } 01238 01239 /** 01240 * @brief Prepare the %unordered_multiset for a specified number of 01241 * elements. 01242 * @param __n Number of elements required. 01243 * 01244 * Same as rehash(ceil(n / max_load_factor())). 01245 */ 01246 void 01247 reserve(size_type __n) 01248 { _M_h.reserve(__n); } 01249 01250 template<typename _Value1, typename _Hash1, typename _Pred1, 01251 typename _Alloc1> 01252 friend bool 01253 operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&, 01254 const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&); 01255 }; 01256 01257 template<class _Value, class _Hash, class _Pred, class _Alloc> 01258 inline void 01259 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 01260 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 01261 { __x.swap(__y); } 01262 01263 template<class _Value, class _Hash, class _Pred, class _Alloc> 01264 inline void 01265 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01266 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01267 { __x.swap(__y); } 01268 01269 template<class _Value, class _Hash, class _Pred, class _Alloc> 01270 inline bool 01271 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 01272 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 01273 { return __x._M_h._M_equal(__y._M_h); } 01274 01275 template<class _Value, class _Hash, class _Pred, class _Alloc> 01276 inline bool 01277 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 01278 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 01279 { return !(__x == __y); } 01280 01281 template<class _Value, class _Hash, class _Pred, class _Alloc> 01282 inline bool 01283 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01284 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01285 { return __x._M_h._M_equal(__y._M_h); } 01286 01287 template<class _Value, class _Hash, class _Pred, class _Alloc> 01288 inline bool 01289 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01290 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01291 { return !(__x == __y); } 01292 01293 _GLIBCXX_END_NAMESPACE_CONTAINER 01294 } // namespace std 01295 01296 #endif /* _UNORDERED_SET_H */