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