diff options
Diffstat (limited to 'libstdc++-v3/include/bits/unordered_set.h')
| -rw-r--r-- | libstdc++-v3/include/bits/unordered_set.h | 401 |
1 files changed, 401 insertions, 0 deletions
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h new file mode 100644 index 000000000..38350bc39 --- /dev/null +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -0,0 +1,401 @@ +// unordered_set implementation -*- C++ -*- + +// Copyright (C) 2010, 2011 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file bits/unordered_set.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{unordered_set} + */ + +#ifndef _UNORDERED_SET_H +#define _UNORDERED_SET_H + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_CONTAINER + + // NB: When we get typedef templates these class definitions + // will be unnecessary. + template<class _Value, + class _Hash = hash<_Value>, + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value>, + bool __cache_hash_code = false> + class __unordered_set + : public _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, true> + { + typedef _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, true> + _Base; + + public: + typedef typename _Base::value_type value_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; + + explicit + __unordered_set(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<value_type>(), __a) + { } + + template<typename _InputIterator> + __unordered_set(_InputIterator __f, _InputIterator __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<value_type>(), __a) + { } + + __unordered_set(initializer_list<value_type> __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__l.begin(), __l.end(), __n, __hf, + __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<value_type>(), __a) + { } + + __unordered_set& + operator=(initializer_list<value_type> __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + }; + + template<class _Value, + class _Hash = hash<_Value>, + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value>, + bool __cache_hash_code = false> + class __unordered_multiset + : public _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, false> + { + typedef _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, false> + _Base; + + public: + typedef typename _Base::value_type value_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; + + explicit + __unordered_multiset(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<value_type>(), __a) + { } + + + template<typename _InputIterator> + __unordered_multiset(_InputIterator __f, _InputIterator __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<value_type>(), __a) + { } + + __unordered_multiset(initializer_list<value_type> __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__l.begin(), __l.end(), __n, __hf, + __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<value_type>(), __a) + { } + + __unordered_multiset& + operator=(initializer_list<value_type> __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + }; + + template<class _Value, class _Hash, class _Pred, class _Alloc, + bool __cache_hash_code> + inline void + swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x, + __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc, + bool __cache_hash_code> + inline void + swap(__unordered_multiset<_Value, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + __unordered_multiset<_Value, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc, + bool __cache_hash_code> + inline bool + operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __x, + const __unordered_set<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __y) + { return __x._M_equal(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc, + bool __cache_hash_code> + inline bool + operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __x, + const __unordered_set<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __y) + { return !(__x == __y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc, + bool __cache_hash_code> + inline bool + operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __x, + const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __y) + { return __x._M_equal(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc, + bool __cache_hash_code> + inline bool + operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __x, + const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, + __cache_hash_code>& __y) + { return !(__x == __y); } + + /** + * @brief A standard container composed of unique keys (containing + * at most one of each key value) in which the elements' keys are + * the elements themselves. + * + * @ingroup unordered_associative_containers + * + * Meets the requirements of a <a href="tables.html#65">container</a>, and + * <a href="tables.html#xx">unordered associative container</a> + * + * @param Value Type of key objects. + * @param Hash Hashing function object type, defaults to hash<Value>. + * @param Pred Predicate function object type, defaults to equal_to<Value>. + * @param Alloc Allocator type, defaults to allocator<Key>. + */ + template<class _Value, + class _Hash = hash<_Value>, + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value> > + class unordered_set + : public __unordered_set<_Value, _Hash, _Pred, _Alloc> + { + typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; + + public: + typedef typename _Base::value_type value_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; + + explicit + unordered_set(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __eql, __a) + { } + + template<typename _InputIterator> + unordered_set(_InputIterator __f, _InputIterator __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __eql, __a) + { } + + unordered_set(initializer_list<value_type> __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) + { } + + unordered_set& + operator=(initializer_list<value_type> __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + }; + + /** + * @brief A standard container composed of equivalent keys + * (possibly containing multiple of each key value) in which the + * elements' keys are the elements themselves. + * + * @ingroup unordered_associative_containers + * + * Meets the requirements of a <a href="tables.html#65">container</a>, and + * <a href="tables.html#xx">unordered associative container</a> + * + * @param Value Type of key objects. + * @param Hash Hashing function object type, defaults to hash<Value>. + * @param Pred Predicate function object type, defaults to equal_to<Value>. + * @param Alloc Allocator type, defaults to allocator<Key>. + */ + template<class _Value, + class _Hash = hash<_Value>, + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value> > + class unordered_multiset + : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc> + { + typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; + + public: + typedef typename _Base::value_type value_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; + + explicit + unordered_multiset(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __eql, __a) + { } + + + template<typename _InputIterator> + unordered_multiset(_InputIterator __f, _InputIterator __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __eql, __a) + { } + + unordered_multiset(initializer_list<value_type> __l, + size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) + { } + + unordered_multiset& + operator=(initializer_list<value_type> __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + }; + + template<class _Value, class _Hash, class _Pred, class _Alloc> + inline void + swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, + unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) + { __x.swap(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc> + inline void + swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, + unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) + { __x.swap(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc> + inline bool + operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, + const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) + { return __x._M_equal(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc> + inline bool + operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, + const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) + { return !(__x == __y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc> + inline bool + operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, + const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) + { return __x._M_equal(__y); } + + template<class _Value, class _Hash, class _Pred, class _Alloc> + inline bool + operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, + const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) + { return !(__x == __y); } + +_GLIBCXX_END_NAMESPACE_CONTAINER +} // namespace std + +#endif /* _UNORDERED_SET_H */ + |