From 73e1eac5f56ff2de695704895b6ad2cb8faf8225 Mon Sep 17 00:00:00 2001 From: paolo Date: Wed, 10 Feb 2010 16:09:42 +0000 Subject: [PATCH] 2010-02-10 Paolo Carlini * include/bits/hashtable.h: Fold in include/tr1_impl/hashtable.h for C++0x use. * include/bits/hashtable_policy.h: New, copy and adjust for C++0x use, include/tr1_impl/hashtable_policy.h; fix erase and insert member functions per n3000. * include/bits/unordered_map.h: Likewise for include/tr1_impl/ unordered_map. * include/bits/unordered_set.h: Likewise for include/tr1_impl/ unordered_set. * include/Makefile.am: Adjust. * include/Makefile.in: Regenerate. * include/tr1/unordered_map: Adjust. * include/tr1/unordered_set: Likewise. * include/tr1_impl/unordered_map: Adjust, now used only by tr1. * include/tr1_impl/hashtable: Likewise. * include/tr1_impl/hashtable_policy.h: Likewise. * include/tr1_impl/unordered_set: Likewise. * include/std/unordered_map: Adjust and simplify includes. * include/std/unordered_set: Likewise. * include/debug/unordered_map: Adjuse erase and insert members. * include/debug/unordered_set: Likewise. * include/profile/unordered_map: Likewise. * include/profile/unordered_set: Likewise. * testsuite/util/exception/safety.h: Fix for the updated erase and insert member functions of the unordered_containers. * testsuite/23_containers/unordered_map/erase/1.cc: New. * testsuite/23_containers/unordered_map/erase/24061-map.cc: Likewise. * testsuite/23_containers/unordered_map/insert/map_single.cc: Likewise. * testsuite/23_containers/unordered_map/insert/array_syntax.cc: Likewise. * testsuite/23_containers/unordered_map/insert/24061-map.cc: Likewise. * testsuite/23_containers/unordered_map/insert/map_range.cc: Likewise. * testsuite/23_containers/set/operators/1_neg.cc: Likewise. * testsuite/23_containers/unordered_multimap/erase/1.cc: Likewise. * testsuite/23_containers/unordered_multimap/erase/ 24061-multimap.cc: Likewise. * testsuite/23_containers/unordered_multimap/insert/ 24061-multimap.cc: Likewise. * testsuite/23_containers/unordered_multimap/insert/ multimap_range.cc: Likewise. * testsuite/23_containers/unordered_multimap/insert/ multimap_single.cc: Likewise. * testsuite/23_containers/unordered_set/erase/1.cc: Likewise. * testsuite/23_containers/unordered_set/erase/24061-set.cc: Likewise. * testsuite/23_containers/unordered_set/insert/set_single.cc: Likewise. * testsuite/23_containers/unordered_set/insert/24061-set.cc: Likewise. * testsuite/23_containers/unordered_set/insert/set_range.cc: Likewise. * testsuite/23_containers/unordered_multiset/erase/1.cc: Likewise. * testsuite/23_containers/unordered_multiset/erase/ 24061-multiset.cc: Likewise. * testsuite/23_containers/unordered_multiset/insert/ 24061-multiset.cc: Likewise. * testsuite/23_containers/unordered_multiset/insert/ multiset_range.cc: Likewise. * testsuite/23_containers/unordered_multiset/insert/ multiset_single.cc: Likewise. * testsuite/23_containers/set/operators/1_neg.cc: Tweak dg-errors to avoid spurious fails in debug-mode. * testsuite/23_containers/map/operators/1_neg.cc: Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@156661 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 64 ++ libstdc++-v3/include/Makefile.am | 5 +- libstdc++-v3/include/Makefile.in | 3 + libstdc++-v3/include/bits/hashtable.h | 1171 +++++++++++++++++++- libstdc++-v3/include/bits/hashtable_policy.h | 854 ++++++++++++++ libstdc++-v3/include/bits/unordered_map.h | 340 ++++++ libstdc++-v3/include/bits/unordered_set.h | 331 ++++++ libstdc++-v3/include/debug/unordered_map | 70 +- libstdc++-v3/include/debug/unordered_set | 70 +- libstdc++-v3/include/profile/unordered_map | 154 ++- libstdc++-v3/include/profile/unordered_set | 135 ++- libstdc++-v3/include/std/unordered_map | 27 +- libstdc++-v3/include/std/unordered_set | 27 +- libstdc++-v3/include/tr1/unordered_map | 21 +- libstdc++-v3/include/tr1/unordered_set | 21 +- libstdc++-v3/include/tr1_impl/hashtable | 89 +- libstdc++-v3/include/tr1_impl/hashtable_policy.h | 71 +- libstdc++-v3/include/tr1_impl/unordered_map | 80 +- libstdc++-v3/include/tr1_impl/unordered_set | 79 +- .../testsuite/23_containers/map/operators/1_neg.cc | 8 +- .../testsuite/23_containers/set/operators/1_neg.cc | 6 +- .../23_containers/unordered_map/erase/1.cc | 129 +++ .../23_containers/unordered_map/erase/24061-map.cc | 105 ++ .../unordered_map/insert/24061-map.cc | 60 + .../unordered_map/insert/array_syntax.cc | 57 + .../unordered_map/insert/map_range.cc | 97 ++ .../unordered_map/insert/map_single.cc | 72 ++ .../23_containers/unordered_multimap/erase/1.cc | 129 +++ .../unordered_multimap/erase/24061-multimap.cc | 108 ++ .../unordered_multimap/insert/24061-multimap.cc | 60 + .../unordered_multimap/insert/multimap_range.cc | 91 ++ .../unordered_multimap/insert/multimap_single.cc | 76 ++ .../23_containers/unordered_multiset/erase/1.cc | 128 +++ .../unordered_multiset/erase/24061-multiset.cc | 107 ++ .../unordered_multiset/insert/24061-multiset.cc | 57 + .../unordered_multiset/insert/multiset_range.cc | 79 ++ .../unordered_multiset/insert/multiset_single.cc | 67 ++ .../23_containers/unordered_set/erase/1.cc | 128 +++ .../23_containers/unordered_set/erase/24061-set.cc | 104 ++ .../unordered_set/insert/24061-set.cc | 57 + .../unordered_set/insert/set_range.cc | 77 ++ .../unordered_set/insert/set_single.cc | 65 ++ libstdc++-v3/testsuite/util/exception/safety.h | 140 ++- 43 files changed, 4921 insertions(+), 698 deletions(-) create mode 100644 libstdc++-v3/include/bits/hashtable_policy.h create mode 100644 libstdc++-v3/include/bits/unordered_map.h create mode 100644 libstdc++-v3/include/bits/unordered_set.h create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/erase/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/erase/24061-map.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/insert/24061-map.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_single.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/24061-multimap.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/24061-multimap.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_single.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/24061-multiset.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/erase/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/erase/24061-set.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/insert/24061-set.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_single.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 5b6eae73679..5b5672e243c 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,67 @@ +2010-02-10 Paolo Carlini + + * include/bits/hashtable.h: Fold in include/tr1_impl/hashtable.h + for C++0x use. + * include/bits/hashtable_policy.h: New, copy and adjust for + C++0x use, include/tr1_impl/hashtable_policy.h; fix erase and + insert member functions per n3000. + * include/bits/unordered_map.h: Likewise for include/tr1_impl/ + unordered_map. + * include/bits/unordered_set.h: Likewise for include/tr1_impl/ + unordered_set. + * include/Makefile.am: Adjust. + * include/Makefile.in: Regenerate. + * include/tr1/unordered_map: Adjust. + * include/tr1/unordered_set: Likewise. + * include/tr1_impl/unordered_map: Adjust, now used only by tr1. + * include/tr1_impl/hashtable: Likewise. + * include/tr1_impl/hashtable_policy.h: Likewise. + * include/tr1_impl/unordered_set: Likewise. + * include/std/unordered_map: Adjust and simplify includes. + * include/std/unordered_set: Likewise. + * include/debug/unordered_map: Adjuse erase and insert members. + * include/debug/unordered_set: Likewise. + * include/profile/unordered_map: Likewise. + * include/profile/unordered_set: Likewise. + * testsuite/util/exception/safety.h: Fix for the updated erase and + insert member functions of the unordered_containers. + * testsuite/23_containers/unordered_map/erase/1.cc: New. + * testsuite/23_containers/unordered_map/erase/24061-map.cc: Likewise. + * testsuite/23_containers/unordered_map/insert/map_single.cc: + Likewise. + * testsuite/23_containers/unordered_map/insert/array_syntax.cc: + Likewise. + * testsuite/23_containers/unordered_map/insert/24061-map.cc: Likewise. + * testsuite/23_containers/unordered_map/insert/map_range.cc: Likewise. + * testsuite/23_containers/set/operators/1_neg.cc: Likewise. + * testsuite/23_containers/unordered_multimap/erase/1.cc: Likewise. + * testsuite/23_containers/unordered_multimap/erase/ + 24061-multimap.cc: Likewise. + * testsuite/23_containers/unordered_multimap/insert/ + 24061-multimap.cc: Likewise. + * testsuite/23_containers/unordered_multimap/insert/ + multimap_range.cc: Likewise. + * testsuite/23_containers/unordered_multimap/insert/ + multimap_single.cc: Likewise. + * testsuite/23_containers/unordered_set/erase/1.cc: Likewise. + * testsuite/23_containers/unordered_set/erase/24061-set.cc: Likewise. + * testsuite/23_containers/unordered_set/insert/set_single.cc: Likewise. + * testsuite/23_containers/unordered_set/insert/24061-set.cc: Likewise. + * testsuite/23_containers/unordered_set/insert/set_range.cc: Likewise. + * testsuite/23_containers/unordered_multiset/erase/1.cc: Likewise. + * testsuite/23_containers/unordered_multiset/erase/ + 24061-multiset.cc: Likewise. + * testsuite/23_containers/unordered_multiset/insert/ + 24061-multiset.cc: Likewise. + * testsuite/23_containers/unordered_multiset/insert/ + multiset_range.cc: Likewise. + * testsuite/23_containers/unordered_multiset/insert/ + multiset_single.cc: Likewise. + + * testsuite/23_containers/set/operators/1_neg.cc: Tweak dg-errors + to avoid spurious fails in debug-mode. + * testsuite/23_containers/map/operators/1_neg.cc: Likewise. + 2010-02-09 Benjamin Kosnik * include/std/streambuf: Adjust doxygen group markup. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index ee7696b6f50..167871507dd 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -1,6 +1,6 @@ #o# Makefile for the include subdirectory of the GNU C++ Standard library. ## -## Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 +## Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 ## Free Software Foundation, Inc. ## ## This file is part of the libstdc++ version 3 distribution. @@ -102,6 +102,7 @@ bits_headers = \ ${bits_srcdir}/gslice.h \ ${bits_srcdir}/gslice_array.h \ ${bits_srcdir}/hashtable.h \ + ${bits_srcdir}/hashtable_policy.h \ ${bits_srcdir}/indirect_array.h \ ${bits_srcdir}/ios_base.h \ ${bits_srcdir}/istream.tcc \ @@ -154,6 +155,8 @@ bits_headers = \ ${bits_srcdir}/streambuf.tcc \ ${bits_srcdir}/stringfwd.h \ ${bits_srcdir}/unique_ptr.h \ + ${bits_srcdir}/unordered_map.h \ + ${bits_srcdir}/unordered_set.h \ ${bits_srcdir}/valarray_array.h \ ${bits_srcdir}/valarray_array.tcc \ ${bits_srcdir}/valarray_before.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 62a8dafcf5d..cd6e5c53496 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -344,6 +344,7 @@ bits_headers = \ ${bits_srcdir}/gslice.h \ ${bits_srcdir}/gslice_array.h \ ${bits_srcdir}/hashtable.h \ + ${bits_srcdir}/hashtable_policy.h \ ${bits_srcdir}/indirect_array.h \ ${bits_srcdir}/ios_base.h \ ${bits_srcdir}/istream.tcc \ @@ -396,6 +397,8 @@ bits_headers = \ ${bits_srcdir}/streambuf.tcc \ ${bits_srcdir}/stringfwd.h \ ${bits_srcdir}/unique_ptr.h \ + ${bits_srcdir}/unordered_map.h \ + ${bits_srcdir}/unordered_set.h \ ${bits_srcdir}/valarray_array.h \ ${bits_srcdir}/valarray_array.tcc \ ${bits_srcdir}/valarray_before.h \ diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index cdfa8af3ea4..96bb8ac63e6 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1,6 +1,6 @@ // hashtable.h header -*- C++ -*- -// Copyright (C) 2007, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010 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 @@ -32,27 +32,1152 @@ #pragma GCC system_header -#ifndef __GXX_EXPERIMENTAL_CXX0X__ -# include -#endif - -#if defined(_GLIBCXX_INCLUDE_AS_TR1) -# error C++0x header cannot be included from TR1 header -#endif - -#if defined(_GLIBCXX_INCLUDE_AS_CXX0X) -# include -#else -# define _GLIBCXX_INCLUDE_AS_CXX0X -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 -# define _GLIBCXX_END_NAMESPACE_TR1 -# define _GLIBCXX_TR1 -# include -# undef _GLIBCXX_TR1 -# undef _GLIBCXX_END_NAMESPACE_TR1 -# undef _GLIBCXX_END_NAMESPACE_TR1 -# undef _GLIBCXX_INCLUDE_AS_CXX0X -#endif +#include -#endif // _HASHTABLE_H +namespace std +{ + // Class template _Hashtable, class definition. + + // Meaning of class template _Hashtable's template parameters + + // _Key and _Value: arbitrary CopyConstructible types. + + // _Allocator: an allocator type ([lib.allocator.requirements]) whose + // value type is Value. As a conforming extension, we allow for + // value type != Value. + + // _ExtractKey: function object that takes a object of type Value + // and returns a value of type _Key. + + // _Equal: function object that takes two objects of type k and returns + // a bool-like value that is true if the two objects are considered equal. + + // _H1: the hash function. A unary function object with argument type + // Key and result type size_t. Return values should be distributed + // over the entire range [0, numeric_limits:::max()]. + + // _H2: the range-hashing function (in the terminology of Tavori and + // Dreizin). A binary function object whose argument types and result + // type are all size_t. Given arguments r and N, the return value is + // in the range [0, N). + + // _Hash: the ranged hash function (Tavori and Dreizin). A binary function + // whose argument types are _Key and size_t and whose result type is + // size_t. Given arguments k and N, the return value is in the range + // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other + // than the default, _H1 and _H2 are ignored. + + // _RehashPolicy: Policy class with three members, all of which govern + // the bucket count. _M_next_bkt(n) returns a bucket count no smaller + // than n. _M_bkt_for_elements(n) returns a bucket count appropriate + // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) + // determines whether, if the current bucket count is n_bkt and the + // current element count is n_elt, we need to increase the bucket + // count. If so, returns make_pair(true, n), where n is the new + // bucket count. If not, returns make_pair(false, ). + + // ??? Right now it is hard-wired that the number of buckets never + // shrinks. Should we allow _RehashPolicy to change that? + + // __cache_hash_code: bool. true if we store the value of the hash + // function along with the value. This is a time-space tradeoff. + // Storing it may improve lookup speed by reducing the number of times + // we need to call the Equal function. + + // __constant_iterators: bool. true if iterator and const_iterator are + // both constant iterator types. This is true for unordered_set and + // unordered_multiset, false for unordered_map and unordered_multimap. + + // __unique_keys: bool. true if the return value of _Hashtable::count(k) + // is always at most one, false if it may be an arbitrary number. This + // true for unordered_set and unordered_map, false for unordered_multiset + // and unordered_multimap. + + template + class _Hashtable + : public __detail::_Rehash_base<_RehashPolicy, + _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, + __cache_hash_code, + __constant_iterators, + __unique_keys> >, + public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __cache_hash_code>, + public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, + _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, + __cache_hash_code, + __constant_iterators, + __unique_keys> > + { + public: + typedef _Allocator allocator_type; + typedef _Value value_type; + typedef _Key key_type; + typedef _Equal key_equal; + // mapped_type, if present, comes from _Map_base. + // hasher, if present, comes from _Hash_code_base. + typedef typename _Allocator::difference_type difference_type; + typedef typename _Allocator::size_type size_type; + typedef typename _Allocator::pointer pointer; + typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Allocator::reference reference; + typedef typename _Allocator::const_reference const_reference; + + typedef __detail::_Node_iterator + local_iterator; + typedef __detail::_Node_const_iterator + const_local_iterator; + + typedef __detail::_Hashtable_iterator + iterator; + typedef __detail::_Hashtable_const_iterator + const_iterator; + + template + friend struct __detail::_Map_base; + + private: + typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; + typedef typename _Allocator::template rebind<_Node>::other + _Node_allocator_type; + typedef typename _Allocator::template rebind<_Node*>::other + _Bucket_allocator_type; + + typedef typename _Allocator::template rebind<_Value>::other + _Value_allocator_type; + + _Node_allocator_type _M_node_allocator; + _Node** _M_buckets; + size_type _M_bucket_count; + size_type _M_element_count; + _RehashPolicy _M_rehash_policy; + + _Node* + _M_allocate_node(const value_type& __v); + + void + _M_deallocate_node(_Node* __n); + + void + _M_deallocate_nodes(_Node**, size_type); + + _Node** + _M_allocate_buckets(size_type __n); + + void + _M_deallocate_buckets(_Node**, size_type __n); + + public: + // Constructor, destructor, assignment, swap + _Hashtable(size_type __bucket_hint, + const _H1&, const _H2&, const _Hash&, + const _Equal&, const _ExtractKey&, + const allocator_type&); + + template + _Hashtable(_InputIterator __first, _InputIterator __last, + size_type __bucket_hint, + const _H1&, const _H2&, const _Hash&, + const _Equal&, const _ExtractKey&, + const allocator_type&); + + _Hashtable(const _Hashtable&); + + _Hashtable(_Hashtable&&); + + _Hashtable& + operator=(const _Hashtable&); + + ~_Hashtable(); + + void swap(_Hashtable&); + + // Basic container operations + iterator + begin() + { + iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; + } + + const_iterator + begin() const + { + const_iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; + } + + iterator + end() + { return iterator(_M_buckets + _M_bucket_count); } + + const_iterator + end() const + { return const_iterator(_M_buckets + _M_bucket_count); } + + const_iterator + cbegin() const + { + const_iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; + } + + const_iterator + cend() const + { return const_iterator(_M_buckets + _M_bucket_count); } + + size_type + size() const + { return _M_element_count; } + + bool + empty() const + { return size() == 0; } + + allocator_type + get_allocator() const + { return allocator_type(_M_node_allocator); } + + _Value_allocator_type + _M_get_Value_allocator() const + { return _Value_allocator_type(_M_node_allocator); } + + size_type + max_size() const + { return _M_node_allocator.max_size(); } + + // Observers + key_equal + key_eq() const + { return this->_M_eq; } + + // hash_function, if present, comes from _Hash_code_base. + + // Bucket operations + size_type + bucket_count() const + { return _M_bucket_count; } + + size_type + max_bucket_count() const + { return max_size(); } + + size_type + bucket_size(size_type __n) const + { return std::distance(begin(__n), end(__n)); } + + size_type + bucket(const key_type& __k) const + { + return this->_M_bucket_index(__k, this->_M_hash_code(__k), + bucket_count()); + } + + local_iterator + begin(size_type __n) + { return local_iterator(_M_buckets[__n]); } + + local_iterator + end(size_type) + { return local_iterator(0); } + + const_local_iterator + begin(size_type __n) const + { return const_local_iterator(_M_buckets[__n]); } + + const_local_iterator + end(size_type) const + { return const_local_iterator(0); } + + // DR 691. + const_local_iterator + cbegin(size_type __n) const + { return const_local_iterator(_M_buckets[__n]); } + + const_local_iterator + cend(size_type) const + { return const_local_iterator(0); } + + float + load_factor() const + { + return static_cast(size()) / static_cast(bucket_count()); + } + + // max_load_factor, if present, comes from _Rehash_base. + + // Generalization of max_load_factor. Extension, not found in TR1. Only + // useful if _RehashPolicy is something other than the default. + const _RehashPolicy& + __rehash_policy() const + { return _M_rehash_policy; } + + void + __rehash_policy(const _RehashPolicy&); + + // Lookup. + iterator + find(const key_type& __k); + + const_iterator + find(const key_type& __k) const; + + size_type + count(const key_type& __k) const; + + std::pair + equal_range(const key_type& __k); + + std::pair + equal_range(const key_type& __k) const; + + private: // Find, insert and erase helper functions + // ??? This dispatching is a workaround for the fact that we don't + // have partial specialization of member templates; it would be + // better to just specialize insert on __unique_keys. There may be a + // cleaner workaround. + typedef typename std::conditional<__unique_keys, + std::pair, + iterator>::type + _Insert_Return_Type; + + typedef typename std::conditional<__unique_keys, + std::_Select1st<_Insert_Return_Type>, + std::_Identity<_Insert_Return_Type> + >::type + _Insert_Conv_Type; + + _Node* + _M_find_node(_Node*, const key_type&, + typename _Hashtable::_Hash_code_type) const; + + iterator + _M_insert_bucket(const value_type&, size_type, + typename _Hashtable::_Hash_code_type); + + std::pair + _M_insert(const value_type&, std::true_type); + + iterator + _M_insert(const value_type&, std::false_type); + + void + _M_erase_node(_Node*, _Node**); + + public: + // Insert and erase + _Insert_Return_Type + insert(const value_type& __v) + { return _M_insert(__v, std::integral_constant()); } + + iterator + insert(const_iterator, const value_type& __v) + { return iterator(_Insert_Conv_Type()(this->insert(__v))); } + + template + void + insert(_InputIterator __first, _InputIterator __last); + + void + insert(initializer_list __l) + { this->insert(__l.begin(), __l.end()); } + + iterator + erase(const_iterator); + + size_type + erase(const key_type&); + iterator + erase(const_iterator, const_iterator); + + void + clear(); + + // Set number of buckets to be appropriate for container of n element. + void rehash(size_type __n); + + private: + // Unconditionally change size of bucket array to n. + void _M_rehash(size_type __n); + }; + + + // Definitions of class template _Hashtable's out-of-line member functions. + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_allocate_node(const value_type& __v) + { + _Node* __n = _M_node_allocator.allocate(1); + __try + { + _M_node_allocator.construct(__n, __v); + __n->_M_next = 0; + return __n; + } + __catch(...) + { + _M_node_allocator.deallocate(__n, 1); + __throw_exception_again; + } + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_node(_Node* __n) + { + _M_node_allocator.destroy(__n); + _M_node_allocator.deallocate(__n, 1); + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_nodes(_Node** __array, size_type __n) + { + for (size_type __i = 0; __i < __n; ++__i) + { + _Node* __p = __array[__i]; + while (__p) + { + _Node* __tmp = __p; + __p = __p->_M_next; + _M_deallocate_node(__tmp); + } + __array[__i] = 0; + } + } + + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node** + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_allocate_buckets(size_type __n) + { + _Bucket_allocator_type __alloc(_M_node_allocator); + + // We allocate one extra bucket to hold a sentinel, an arbitrary + // non-null pointer. Iterator increment relies on this. + _Node** __p = __alloc.allocate(__n + 1); + std::fill(__p, __p + __n, (_Node*) 0); + __p[__n] = reinterpret_cast<_Node*>(0x1000); + return __p; + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_buckets(_Node** __p, size_type __n) + { + _Bucket_allocator_type __alloc(_M_node_allocator); + __alloc.deallocate(__p, __n + 1); + } + + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(size_type __bucket_hint, + const _H1& __h1, const _H2& __h2, const _Hash& __h, + const _Equal& __eq, const _ExtractKey& __exk, + const allocator_type& __a) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__exk, __eq, + __h1, __h2, __h), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + _M_node_allocator(__a), + _M_bucket_count(0), + _M_element_count(0), + _M_rehash_policy() + { + _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); + _M_buckets = _M_allocate_buckets(_M_bucket_count); + } + + template + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(_InputIterator __f, _InputIterator __l, + size_type __bucket_hint, + const _H1& __h1, const _H2& __h2, const _Hash& __h, + const _Equal& __eq, const _ExtractKey& __exk, + const allocator_type& __a) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__exk, __eq, + __h1, __h2, __h), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + _M_node_allocator(__a), + _M_bucket_count(0), + _M_element_count(0), + _M_rehash_policy() + { + _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), + _M_rehash_policy. + _M_bkt_for_elements(__detail:: + __distance_fw(__f, + __l))); + _M_buckets = _M_allocate_buckets(_M_bucket_count); + __try + { + for (; __f != __l; ++__f) + this->insert(*__f); + } + __catch(...) + { + clear(); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + __throw_exception_again; + } + } + + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(const _Hashtable& __ht) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__ht), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + _M_node_allocator(__ht._M_node_allocator), + _M_bucket_count(__ht._M_bucket_count), + _M_element_count(__ht._M_element_count), + _M_rehash_policy(__ht._M_rehash_policy) + { + _M_buckets = _M_allocate_buckets(_M_bucket_count); + __try + { + for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) + { + _Node* __n = __ht._M_buckets[__i]; + _Node** __tail = _M_buckets + __i; + while (__n) + { + *__tail = _M_allocate_node(__n->_M_v); + this->_M_copy_code(*__tail, __n); + __tail = &((*__tail)->_M_next); + __n = __n->_M_next; + } + } + } + __catch(...) + { + clear(); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + __throw_exception_again; + } + } + + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(_Hashtable&& __ht) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__ht), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + _M_node_allocator(__ht._M_node_allocator), + _M_bucket_count(__ht._M_bucket_count), + _M_element_count(__ht._M_element_count), + _M_rehash_policy(__ht._M_rehash_policy), + _M_buckets(__ht._M_buckets) + { + size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0); + __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt); + __ht._M_bucket_count = __n_bkt; + __ht._M_element_count = 0; + __ht._M_rehash_policy = _RehashPolicy(); + } + + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + operator=(const _Hashtable& __ht) + { + _Hashtable __tmp(__ht); + this->swap(__tmp); + return *this; + } + + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + ~_Hashtable() + { + clear(); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + swap(_Hashtable& __x) + { + // The only base class with member variables is hash_code_base. We + // define _Hash_code_base::_M_swap because different specializations + // have different members. + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>::_M_swap(__x); + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 431. Swapping containers with unequal allocators. + std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, + __x._M_node_allocator); + + std::swap(_M_rehash_policy, __x._M_rehash_policy); + std::swap(_M_buckets, __x._M_buckets); + std::swap(_M_bucket_count, __x._M_bucket_count); + std::swap(_M_element_count, __x._M_element_count); + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + __rehash_policy(const _RehashPolicy& __pol) + { + _M_rehash_policy = __pol; + size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); + if (__n_bkt > _M_bucket_count) + _M_rehash(__n_bkt); + } + + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + find(const key_type& __k) + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); + return __p ? iterator(__p, _M_buckets + __n) : this->end(); + } + + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + find(const key_type& __k) const + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); + return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); + } + + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::size_type + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + count(const key_type& __k) const + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + std::size_t __result = 0; + for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) + if (this->_M_compare(__k, __code, __p)) + ++__result; + return __result; + } + + template + std::pair::iterator, + typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + equal_range(const key_type& __k) + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node** __head = _M_buckets + __n; + _Node* __p = _M_find_node(*__head, __k, __code); + + if (__p) + { + _Node* __p1 = __p->_M_next; + for (; __p1; __p1 = __p1->_M_next) + if (!this->_M_compare(__k, __code, __p1)) + break; + + iterator __first(__p, __head); + iterator __last(__p1, __head); + if (!__p1) + __last._M_incr_bucket(); + return std::make_pair(__first, __last); + } + else + return std::make_pair(this->end(), this->end()); + } + + template + std::pair::const_iterator, + typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + equal_range(const key_type& __k) const + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node** __head = _M_buckets + __n; + _Node* __p = _M_find_node(*__head, __k, __code); + + if (__p) + { + _Node* __p1 = __p->_M_next; + for (; __p1; __p1 = __p1->_M_next) + if (!this->_M_compare(__k, __code, __p1)) + break; + + const_iterator __first(__p, __head); + const_iterator __last(__p1, __head); + if (!__p1) + __last._M_incr_bucket(); + return std::make_pair(__first, __last); + } + else + return std::make_pair(this->end(), this->end()); + } + + // Find the node whose key compares equal to k, beginning the search + // at p (usually the head of a bucket). Return nil if no node is found. + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + _Equal, _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_find_node(_Node* __p, const key_type& __k, + typename _Hashtable::_Hash_code_type __code) const + { + for (; __p; __p = __p->_M_next) + if (this->_M_compare(__k, __code, __p)) + return __p; + return false; + } + + // Insert v in bucket n (assumes no element with its key already present). + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert_bucket(const value_type& __v, size_type __n, + typename _Hashtable::_Hash_code_type __code) + { + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + + // Allocate the new node before doing the rehash so that we don't + // do a rehash if the allocation throws. + _Node* __new_node = _M_allocate_node(__v); + + __try + { + if (__do_rehash.first) + { + const key_type& __k = this->_M_extract(__v); + __n = this->_M_bucket_index(__k, __code, __do_rehash.second); + _M_rehash(__do_rehash.second); + } + + __new_node->_M_next = _M_buckets[__n]; + this->_M_store_code(__new_node, __code); + _M_buckets[__n] = __new_node; + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); + } + __catch(...) + { + _M_deallocate_node(__new_node); + __throw_exception_again; + } + } + + // Insert v if no element with its key is already present. + template + std::pair::iterator, bool> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(const value_type& __v, std::true_type) + { + const key_type& __k = this->_M_extract(__v); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + + if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) + return std::make_pair(iterator(__p, _M_buckets + __n), false); + return std::make_pair(_M_insert_bucket(__v, __n, __code), true); + } + + // Insert v unconditionally. + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(const value_type& __v, std::false_type) + { + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); + + const key_type& __k = this->_M_extract(__v); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + + // First find the node, avoid leaking new_node if compare throws. + _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); + _Node* __new_node = _M_allocate_node(__v); + + if (__prev) + { + __new_node->_M_next = __prev->_M_next; + __prev->_M_next = __new_node; + } + else + { + __new_node->_M_next = _M_buckets[__n]; + _M_buckets[__n] = __new_node; + } + this->_M_store_code(__new_node, __code); + + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); + } + + // For erase(iterator) and erase(const_iterator). + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_erase_node(_Node* __p, _Node** __b) + { + _Node* __cur = *__b; + if (__cur == __p) + *__b = __cur->_M_next; + else + { + _Node* __next = __cur->_M_next; + while (__next != __p) + { + __cur = __next; + __next = __cur->_M_next; + } + __cur->_M_next = __next->_M_next; + } + + _M_deallocate_node(__p); + --_M_element_count; + } + + template + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + insert(_InputIterator __first, _InputIterator __last) + { + size_type __n_elt = __detail::__distance_fw(__first, __last); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, __n_elt); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); + + for (; __first != __last; ++__first) + this->insert(*__first); + } + + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const_iterator __it) + { + iterator __result(__it._M_cur_node, __it._M_cur_bucket); + ++__result; + _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); + return __result; + } + + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::size_type + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const key_type& __k) + { + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + size_type __result = 0; + + _Node** __slot = _M_buckets + __n; + while (*__slot && !this->_M_compare(__k, __code, *__slot)) + __slot = &((*__slot)->_M_next); + + _Node** __saved_slot = 0; + while (*__slot && this->_M_compare(__k, __code, *__slot)) + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 526. Is it undefined if a function in the standard changes + // in parameters? + if (&this->_M_extract((*__slot)->_M_v) != &__k) + { + _Node* __p = *__slot; + *__slot = __p->_M_next; + _M_deallocate_node(__p); + --_M_element_count; + ++__result; + } + else + { + __saved_slot = __slot; + __slot = &((*__slot)->_M_next); + } + } + + if (__saved_slot) + { + _Node* __p = *__saved_slot; + *__saved_slot = __p->_M_next; + _M_deallocate_node(__p); + --_M_element_count; + ++__result; + } + + return __result; + } + + // ??? This could be optimized by taking advantage of the bucket + // structure, but it's not clear that it's worth doing. It probably + // wouldn't even be an optimization unless the load factor is large. + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const_iterator __first, const_iterator __last) + { + while (__first != __last) + __first = this->erase(__first); + return iterator(__last._M_cur_node, __last._M_cur_bucket); + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + clear() + { + _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_element_count = 0; + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + rehash(size_type __n) + { + _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), + _M_rehash_policy._M_bkt_for_elements(_M_element_count + + 1))); + } + + template + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_rehash(size_type __n) + { + _Node** __new_array = _M_allocate_buckets(__n); + __try + { + for (size_type __i = 0; __i < _M_bucket_count; ++__i) + while (_Node* __p = _M_buckets[__i]) + { + std::size_t __new_index = this->_M_bucket_index(__p, __n); + _M_buckets[__i] = __p->_M_next; + __p->_M_next = __new_array[__new_index]; + __new_array[__new_index] = __p; + } + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + _M_bucket_count = __n; + _M_buckets = __new_array; + } + __catch(...) + { + // A failure here means that a hash function threw an exception. + // We can't restore the previous state without calling the hash + // function again, so the only sensible recovery is to delete + // everything. + _M_deallocate_nodes(__new_array, __n); + _M_deallocate_buckets(__new_array, __n); + _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_element_count = 0; + __throw_exception_again; + } + } +} + +#endif // _HASHTABLE_H diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h new file mode 100644 index 00000000000..4eccc889682 --- /dev/null +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -0,0 +1,854 @@ +// Internal policy header for unordered_set and unordered_map -*- C++ -*- + +// Copyright (C) 2010 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 +// . + +/** @file bits/hashtable_policy.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef _HASHTABLE_POLICY_H +#define _HASHTABLE_POLICY_H 1 + +namespace std +{ +namespace __detail +{ + // Helper function: return distance(first, last) for forward + // iterators, or 0 for input iterators. + template + inline typename std::iterator_traits<_Iterator>::difference_type + __distance_fw(_Iterator __first, _Iterator __last, + std::input_iterator_tag) + { return 0; } + + template + inline typename std::iterator_traits<_Iterator>::difference_type + __distance_fw(_Iterator __first, _Iterator __last, + std::forward_iterator_tag) + { return std::distance(__first, __last); } + + template + inline typename std::iterator_traits<_Iterator>::difference_type + __distance_fw(_Iterator __first, _Iterator __last) + { + typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; + return __distance_fw(__first, __last, _Tag()); + } + + template + _RAIter + __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val) + { + typedef typename std::iterator_traits<_RAIter>::difference_type _DType; + + _DType __len = __last - __first; + while (__len > 0) + { + _DType __half = __len >> 1; + _RAIter __middle = __first + __half; + if (*__middle < __val) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + + // Auxiliary types used for all instantiations of _Hashtable: nodes + // and iterators. + + // Nodes, used to wrap elements stored in the hash table. A policy + // template parameter of class template _Hashtable controls whether + // nodes also store a hash code. In some cases (e.g. strings) this + // may be a performance win. + template + struct _Hash_node; + + template + struct _Hash_node<_Value, true> + { + _Value _M_v; + std::size_t _M_hash_code; + _Hash_node* _M_next; + + template + _Hash_node(_Args&&... __args) + : _M_v(std::forward<_Args>(__args)...), + _M_hash_code(), _M_next() { } + }; + + template + struct _Hash_node<_Value, false> + { + _Value _M_v; + _Hash_node* _M_next; + + template + _Hash_node(_Args&&... __args) + : _M_v(std::forward<_Args>(__args)...), + _M_next() { } + }; + + // Local iterators, used to iterate within a bucket but not between + // buckets. + template + struct _Node_iterator_base + { + _Node_iterator_base(_Hash_node<_Value, __cache>* __p) + : _M_cur(__p) { } + + void + _M_incr() + { _M_cur = _M_cur->_M_next; } + + _Hash_node<_Value, __cache>* _M_cur; + }; + + template + inline bool + operator==(const _Node_iterator_base<_Value, __cache>& __x, + const _Node_iterator_base<_Value, __cache>& __y) + { return __x._M_cur == __y._M_cur; } + + template + inline bool + operator!=(const _Node_iterator_base<_Value, __cache>& __x, + const _Node_iterator_base<_Value, __cache>& __y) + { return __x._M_cur != __y._M_cur; } + + template + struct _Node_iterator + : public _Node_iterator_base<_Value, __cache> + { + typedef _Value value_type; + typedef typename std::conditional<__constant_iterators, + const _Value*, _Value*>::type + pointer; + typedef typename std::conditional<__constant_iterators, + const _Value&, _Value&>::type + reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + _Node_iterator() + : _Node_iterator_base<_Value, __cache>(0) { } + + explicit + _Node_iterator(_Hash_node<_Value, __cache>* __p) + : _Node_iterator_base<_Value, __cache>(__p) { } + + reference + operator*() const + { return this->_M_cur->_M_v; } + + pointer + operator->() const + { return &this->_M_cur->_M_v; } + + _Node_iterator& + operator++() + { + this->_M_incr(); + return *this; + } + + _Node_iterator + operator++(int) + { + _Node_iterator __tmp(*this); + this->_M_incr(); + return __tmp; + } + }; + + template + struct _Node_const_iterator + : public _Node_iterator_base<_Value, __cache> + { + typedef _Value value_type; + typedef const _Value* pointer; + typedef const _Value& reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + _Node_const_iterator() + : _Node_iterator_base<_Value, __cache>(0) { } + + explicit + _Node_const_iterator(_Hash_node<_Value, __cache>* __p) + : _Node_iterator_base<_Value, __cache>(__p) { } + + _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, + __cache>& __x) + : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } + + reference + operator*() const + { return this->_M_cur->_M_v; } + + pointer + operator->() const + { return &this->_M_cur->_M_v; } + + _Node_const_iterator& + operator++() + { + this->_M_incr(); + return *this; + } + + _Node_const_iterator + operator++(int) + { + _Node_const_iterator __tmp(*this); + this->_M_incr(); + return __tmp; + } + }; + + template + struct _Hashtable_iterator_base + { + _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, + _Hash_node<_Value, __cache>** __bucket) + : _M_cur_node(__node), _M_cur_bucket(__bucket) { } + + void + _M_incr() + { + _M_cur_node = _M_cur_node->_M_next; + if (!_M_cur_node) + _M_incr_bucket(); + } + + void + _M_incr_bucket(); + + _Hash_node<_Value, __cache>* _M_cur_node; + _Hash_node<_Value, __cache>** _M_cur_bucket; + }; + + // Global iterators, used for arbitrary iteration within a hash + // table. Larger and more expensive than local iterators. + template + void + _Hashtable_iterator_base<_Value, __cache>:: + _M_incr_bucket() + { + ++_M_cur_bucket; + + // This loop requires the bucket array to have a non-null sentinel. + while (!*_M_cur_bucket) + ++_M_cur_bucket; + _M_cur_node = *_M_cur_bucket; + } + + template + inline bool + operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, + const _Hashtable_iterator_base<_Value, __cache>& __y) + { return __x._M_cur_node == __y._M_cur_node; } + + template + inline bool + operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, + const _Hashtable_iterator_base<_Value, __cache>& __y) + { return __x._M_cur_node != __y._M_cur_node; } + + template + struct _Hashtable_iterator + : public _Hashtable_iterator_base<_Value, __cache> + { + typedef _Value value_type; + typedef typename std::conditional<__constant_iterators, + const _Value*, _Value*>::type + pointer; + typedef typename std::conditional<__constant_iterators, + const _Value&, _Value&>::type + reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + _Hashtable_iterator() + : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } + + _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, + _Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } + + explicit + _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } + + reference + operator*() const + { return this->_M_cur_node->_M_v; } + + pointer + operator->() const + { return &this->_M_cur_node->_M_v; } + + _Hashtable_iterator& + operator++() + { + this->_M_incr(); + return *this; + } + + _Hashtable_iterator + operator++(int) + { + _Hashtable_iterator __tmp(*this); + this->_M_incr(); + return __tmp; + } + }; + + template + struct _Hashtable_const_iterator + : public _Hashtable_iterator_base<_Value, __cache> + { + typedef _Value value_type; + typedef const _Value* pointer; + typedef const _Value& reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + _Hashtable_const_iterator() + : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } + + _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, + _Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } + + explicit + _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } + + _Hashtable_const_iterator(const _Hashtable_iterator<_Value, + __constant_iterators, __cache>& __x) + : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, + __x._M_cur_bucket) { } + + reference + operator*() const + { return this->_M_cur_node->_M_v; } + + pointer + operator->() const + { return &this->_M_cur_node->_M_v; } + + _Hashtable_const_iterator& + operator++() + { + this->_M_incr(); + return *this; + } + + _Hashtable_const_iterator + operator++(int) + { + _Hashtable_const_iterator __tmp(*this); + this->_M_incr(); + return __tmp; + } + }; + + + // Many of class template _Hashtable's template parameters are policy + // classes. These are defaults for the policies. + + // Default range hashing function: use division to fold a large number + // into the range [0, N). + struct _Mod_range_hashing + { + typedef std::size_t first_argument_type; + typedef std::size_t second_argument_type; + typedef std::size_t result_type; + + result_type + operator()(first_argument_type __num, second_argument_type __den) const + { return __num % __den; } + }; + + // Default ranged hash function H. In principle it should be a + // function object composed from objects of type H1 and H2 such that + // h(k, N) = h2(h1(k), N), but that would mean making extra copies of + // h1 and h2. So instead we'll just use a tag to tell class template + // hashtable to do that composition. + struct _Default_ranged_hash { }; + + // Default value for rehash policy. Bucket size is (usually) the + // smallest prime that keeps the load factor small enough. + struct _Prime_rehash_policy + { + _Prime_rehash_policy(float __z = 1.0) + : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { } + + float + max_load_factor() const + { return _M_max_load_factor; } + + // Return a bucket size no smaller than n. + std::size_t + _M_next_bkt(std::size_t __n) const; + + // Return a bucket count appropriate for n elements + std::size_t + _M_bkt_for_elements(std::size_t __n) const; + + // __n_bkt is current bucket count, __n_elt is current element count, + // and __n_ins is number of elements to be inserted. Do we need to + // increase bucket count? If so, return make_pair(true, n), where n + // is the new bucket count. If not, return make_pair(false, 0). + std::pair + _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, + std::size_t __n_ins) const; + + enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; + + float _M_max_load_factor; + float _M_growth_factor; + mutable std::size_t _M_next_resize; + }; + + extern const unsigned long __prime_list[]; + + // XXX This is a hack. There's no good reason for any of + // _Prime_rehash_policy's member functions to be inline. + + // Return a prime no smaller than n. + inline std::size_t + _Prime_rehash_policy:: + _M_next_bkt(std::size_t __n) const + { + const unsigned long* __p = __lower_bound(__prime_list, __prime_list + + _S_n_primes, __n); + _M_next_resize = + static_cast(__builtin_ceil(*__p * _M_max_load_factor)); + return *__p; + } + + // Return the smallest prime p such that alpha p >= n, where alpha + // is the load factor. + inline std::size_t + _Prime_rehash_policy:: + _M_bkt_for_elements(std::size_t __n) const + { + const float __min_bkts = __n / _M_max_load_factor; + const unsigned long* __p = __lower_bound(__prime_list, __prime_list + + _S_n_primes, __min_bkts); + _M_next_resize = + static_cast(__builtin_ceil(*__p * _M_max_load_factor)); + return *__p; + } + + // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. + // If p > __n_bkt, return make_pair(true, p); otherwise return + // make_pair(false, 0). In principle this isn't very different from + // _M_bkt_for_elements. + + // The only tricky part is that we're caching the element count at + // which we need to rehash, so we don't have to do a floating-point + // multiply for every insertion. + + inline std::pair + _Prime_rehash_policy:: + _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, + std::size_t __n_ins) const + { + if (__n_elt + __n_ins > _M_next_resize) + { + float __min_bkts = ((float(__n_ins) + float(__n_elt)) + / _M_max_load_factor); + if (__min_bkts > __n_bkt) + { + __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); + const unsigned long* __p = + __lower_bound(__prime_list, __prime_list + _S_n_primes, + __min_bkts); + _M_next_resize = static_cast + (__builtin_ceil(*__p * _M_max_load_factor)); + return std::make_pair(true, *__p); + } + else + { + _M_next_resize = static_cast + (__builtin_ceil(__n_bkt * _M_max_load_factor)); + return std::make_pair(false, 0); + } + } + else + return std::make_pair(false, 0); + } + + // Base classes for std::tr1::_Hashtable. We define these base + // classes because in some cases we want to do different things + // depending on the value of a policy class. In some cases the + // policy class affects which member functions and nested typedefs + // are defined; we handle that by specializing base class templates. + // Several of the base class templates need to access other members + // of class template _Hashtable, so we use the "curiously recurring + // template pattern" for them. + + // class template _Map_base. If the hashtable has a value type of the + // form pair and a key extraction policy that returns the + // first part of the pair, the hashtable gets a mapped_type typedef. + // If it satisfies those criteria and also has unique keys, then it + // also gets an operator[]. + template + struct _Map_base { }; + + template + struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> + { + typedef typename _Pair::second_type mapped_type; + }; + + template + struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> + { + typedef typename _Pair::second_type mapped_type; + + mapped_type& + operator[](const _Key& __k); + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 761. unordered_map needs an at() member function. + mapped_type& + at(const _Key& __k); + + const mapped_type& + at(const _Key& __k) const; + }; + + template + typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, + true, _Hashtable>::mapped_type& + _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: + operator[](const _Key& __k) + { + _Hashtable* __h = static_cast<_Hashtable*>(this); + typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + std::size_t __n = __h->_M_bucket_index(__k, __code, + __h->_M_bucket_count); + + typename _Hashtable::_Node* __p = + __h->_M_find_node(__h->_M_buckets[__n], __k, __code); + if (!__p) + return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), + __n, __code)->second; + return (__p->_M_v).second; + } + + template + typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, + true, _Hashtable>::mapped_type& + _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: + at(const _Key& __k) + { + _Hashtable* __h = static_cast<_Hashtable*>(this); + typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + std::size_t __n = __h->_M_bucket_index(__k, __code, + __h->_M_bucket_count); + + typename _Hashtable::_Node* __p = + __h->_M_find_node(__h->_M_buckets[__n], __k, __code); + if (!__p) + __throw_out_of_range(__N("_Map_base::at")); + return (__p->_M_v).second; + } + + template + const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, + true, _Hashtable>::mapped_type& + _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: + at(const _Key& __k) const + { + const _Hashtable* __h = static_cast(this); + typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + std::size_t __n = __h->_M_bucket_index(__k, __code, + __h->_M_bucket_count); + + typename _Hashtable::_Node* __p = + __h->_M_find_node(__h->_M_buckets[__n], __k, __code); + if (!__p) + __throw_out_of_range(__N("_Map_base::at")); + return (__p->_M_v).second; + } + + // class template _Rehash_base. Give hashtable the max_load_factor + // functions iff the rehash policy is _Prime_rehash_policy. + template + struct _Rehash_base { }; + + template + struct _Rehash_base<_Prime_rehash_policy, _Hashtable> + { + float + max_load_factor() const + { + const _Hashtable* __this = static_cast(this); + return __this->__rehash_policy().max_load_factor(); + } + + void + max_load_factor(float __z) + { + _Hashtable* __this = static_cast<_Hashtable*>(this); + __this->__rehash_policy(_Prime_rehash_policy(__z)); + } + }; + + // Class template _Hash_code_base. Encapsulates two policy issues that + // aren't quite orthogonal. + // (1) the difference between using a ranged hash function and using + // the combination of a hash function and a range-hashing function. + // In the former case we don't have such things as hash codes, so + // we have a dummy type as placeholder. + // (2) Whether or not we cache hash codes. Caching hash codes is + // meaningless if we have a ranged hash function. + // We also put the key extraction and equality comparison function + // objects here, for convenience. + + // Primary template: unused except as a hook for specializations. + template + struct _Hash_code_base; + + // Specialization: ranged hash function, no caching hash codes. H1 + // and H2 are provided but ignored. We define a dummy hash code type. + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Hash, false> + { + protected: + _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, + const _H1&, const _H2&, const _Hash& __h) + : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } + + typedef void* _Hash_code_type; + + _Hash_code_type + _M_hash_code(const _Key& __key) const + { return 0; } + + std::size_t + _M_bucket_index(const _Key& __k, _Hash_code_type, + std::size_t __n) const + { return _M_ranged_hash(__k, __n); } + + std::size_t + _M_bucket_index(const _Hash_node<_Value, false>* __p, + std::size_t __n) const + { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } + + bool + _M_compare(const _Key& __k, _Hash_code_type, + _Hash_node<_Value, false>* __n) const + { return _M_eq(__k, _M_extract(__n->_M_v)); } + + void + _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const + { } + + void + _M_copy_code(_Hash_node<_Value, false>*, + const _Hash_node<_Value, false>*) const + { } + + void + _M_swap(_Hash_code_base& __x) + { + std::swap(_M_extract, __x._M_extract); + std::swap(_M_eq, __x._M_eq); + std::swap(_M_ranged_hash, __x._M_ranged_hash); + } + + protected: + _ExtractKey _M_extract; + _Equal _M_eq; + _Hash _M_ranged_hash; + }; + + + // No specialization for ranged hash function while caching hash codes. + // That combination is meaningless, and trying to do it is an error. + + + // Specialization: ranged hash function, cache hash codes. This + // combination is meaningless, so we provide only a declaration + // and no definition. + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Hash, true>; + + // Specialization: hash function and range-hashing function, no + // caching of hash codes. H is provided but ignored. Provides + // typedef and accessor required by TR1. + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Default_ranged_hash, false> + { + typedef _H1 hasher; + + hasher + hash_function() const + { return _M_h1; } + + protected: + _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, + const _H1& __h1, const _H2& __h2, + const _Default_ranged_hash&) + : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } + + typedef std::size_t _Hash_code_type; + + _Hash_code_type + _M_hash_code(const _Key& __k) const + { return _M_h1(__k); } + + std::size_t + _M_bucket_index(const _Key&, _Hash_code_type __c, + std::size_t __n) const + { return _M_h2(__c, __n); } + + std::size_t + _M_bucket_index(const _Hash_node<_Value, false>* __p, + std::size_t __n) const + { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } + + bool + _M_compare(const _Key& __k, _Hash_code_type, + _Hash_node<_Value, false>* __n) const + { return _M_eq(__k, _M_extract(__n->_M_v)); } + + void + _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const + { } + + void + _M_copy_code(_Hash_node<_Value, false>*, + const _Hash_node<_Value, false>*) const + { } + + void + _M_swap(_Hash_code_base& __x) + { + std::swap(_M_extract, __x._M_extract); + std::swap(_M_eq, __x._M_eq); + std::swap(_M_h1, __x._M_h1); + std::swap(_M_h2, __x._M_h2); + } + + protected: + _ExtractKey _M_extract; + _Equal _M_eq; + _H1 _M_h1; + _H2 _M_h2; + }; + + // Specialization: hash function and range-hashing function, + // caching hash codes. H is provided but ignored. Provides + // typedef and accessor required by TR1. + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Default_ranged_hash, true> + { + typedef _H1 hasher; + + hasher + hash_function() const + { return _M_h1; } + + protected: + _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, + const _H1& __h1, const _H2& __h2, + const _Default_ranged_hash&) + : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } + + typedef std::size_t _Hash_code_type; + + _Hash_code_type + _M_hash_code(const _Key& __k) const + { return _M_h1(__k); } + + std::size_t + _M_bucket_index(const _Key&, _Hash_code_type __c, + std::size_t __n) const + { return _M_h2(__c, __n); } + + std::size_t + _M_bucket_index(const _Hash_node<_Value, true>* __p, + std::size_t __n) const + { return _M_h2(__p->_M_hash_code, __n); } + + bool + _M_compare(const _Key& __k, _Hash_code_type __c, + _Hash_node<_Value, true>* __n) const + { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } + + void + _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const + { __n->_M_hash_code = __c; } + + void + _M_copy_code(_Hash_node<_Value, true>* __to, + const _Hash_node<_Value, true>* __from) const + { __to->_M_hash_code = __from->_M_hash_code; } + + void + _M_swap(_Hash_code_base& __x) + { + std::swap(_M_extract, __x._M_extract); + std::swap(_M_eq, __x._M_eq); + std::swap(_M_h1, __x._M_h1); + std::swap(_M_h2, __x._M_h2); + } + + protected: + _ExtractKey _M_extract; + _Equal _M_eq; + _H1 _M_h1; + _H2 _M_h2; + }; +} // namespace __detail +} + +#endif // _HASHTABLE_POLICY_H diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h new file mode 100644 index 00000000000..77236d3aca6 --- /dev/null +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -0,0 +1,340 @@ +// unordered_map implementation -*- C++ -*- + +// Copyright (C) 2010 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 +// . + +/** @file bits/unordered_map.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef _UNORDERED_MAP_H +#define _UNORDERED_MAP_H + +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) + + // XXX When we get typedef templates these class definitions + // will be unnecessary. + template, + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator >, + bool __cache_hash_code = false> + class __unordered_map + : public _Hashtable<_Key, std::pair, _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, true> + { + typedef _Hashtable<_Key, std::pair, _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, true> + _Base; + + public: + 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_map(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::_Select1st >(), __a) + { } + + template + __unordered_map(_InputIterator __f, _InputIterator __l, + size_type __n = 10, + 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::_Select1st >(), __a) + { } + + __unordered_map(__unordered_map&& __x) + : _Base(std::forward<_Base>(__x)) { } + }; + + template, + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator >, + bool __cache_hash_code = false> + class __unordered_multimap + : public _Hashtable<_Key, std::pair, + _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, false> + { + typedef _Hashtable<_Key, std::pair, + _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, false> + _Base; + + public: + 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_multimap(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::_Select1st >(), __a) + { } + + + template + __unordered_multimap(_InputIterator __f, _InputIterator __l, + typename _Base::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::_Select1st >(), __a) + { } + + __unordered_multimap(__unordered_multimap&& __x) + : _Base(std::forward<_Base>(__x)) { } + }; + + template + inline void + swap(__unordered_map<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + __unordered_map<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } + + template + inline void + swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + __unordered_multimap<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } + + + /** + * @brief A standard container composed of unique keys (containing + * at most one of each key value) that associates values of another type + * with the keys. + * + * @ingroup unordered_associative_containers + * + * Meets the requirements of a container, and + * unordered associative container + * + * @param Key Type of key objects. + * @param Tp Type of mapped objects. + * @param Hash Hashing function object type, defaults to hash. + * @param Pred Predicate function object type, defaults to equal_to. + * @param Alloc Allocator type, defaults to allocator. + * + * The resulting value type of the container is std::pair. + */ + template, + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator > > + class unordered_map + : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> + { + typedef __unordered_map<_Key, _Tp, _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_map(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 + unordered_map(_InputIterator __f, _InputIterator __l, + size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __eql, __a) + { } + + unordered_map(unordered_map&& __x) + : _Base(std::forward<_Base>(__x)) { } + + unordered_map(initializer_list __l, + size_type __n = 10, + 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_map& + operator=(unordered_map&& __x) + { + // NB: DR 1204. + // NB: DR 675. + this->clear(); + this->swap(__x); + return *this; + } + + unordered_map& + operator=(initializer_list __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) that associates + * values of another type with the keys. + * + * @ingroup unordered_associative_containers + * + * Meets the requirements of a container, and + * unordered associative container + * + * @param Key Type of key objects. + * @param Tp Type of mapped objects. + * @param Hash Hashing function object type, defaults to hash. + * @param Pred Predicate function object type, defaults to equal_to. + * @param Alloc Allocator type, defaults to allocator. + * + * The resulting value type of the container is std::pair. + */ + template, + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator > > + class unordered_multimap + : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> + { + typedef __unordered_multimap<_Key, _Tp, _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_multimap(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 + unordered_multimap(_InputIterator __f, _InputIterator __l, + typename _Base::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_multimap(unordered_multimap&& __x) + : _Base(std::forward<_Base>(__x)) { } + + unordered_multimap(initializer_list __l, + size_type __n = 10, + 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_multimap& + operator=(unordered_multimap&& __x) + { + // NB: DR 1204. + // NB: DR 675. + this->clear(); + this->swap(__x); + return *this; + } + + unordered_multimap& + operator=(initializer_list __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + }; + + template + inline void + swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, + unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) + { __x.swap(__y); } + + template + inline void + swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, + unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) + { __x.swap(__y); } + +_GLIBCXX_END_NESTED_NAMESPACE + +#endif /* _UNORDERED_MAP_H */ diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h new file mode 100644 index 00000000000..a20fbf4b05d --- /dev/null +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -0,0 +1,331 @@ +// unordered_set implementation -*- C++ -*- + +// Copyright (C) 2010 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 +// . + +/** @file bits/unordered_set.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef _UNORDERED_SET_H +#define _UNORDERED_SET_H + +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) + + // XXX When we get typedef templates these class definitions + // will be unnecessary. + template, + 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::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>(), __a) + { } + + template + __unordered_set(_InputIterator __f, _InputIterator __l, + size_type __n = 10, + 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>(), __a) + { } + + __unordered_set(__unordered_set&& __x) + : _Base(std::forward<_Base>(__x)) { } + }; + + template, + 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::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>(), __a) + { } + + + template + __unordered_multiset(_InputIterator __f, _InputIterator __l, + typename _Base::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>(), __a) + { } + + __unordered_multiset(__unordered_multiset&& __x) + : _Base(std::forward<_Base>(__x)) { } + }; + + template + 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 + 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); } + + + /** + * @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 container, and + * unordered associative container + * + * @param Value Type of key objects. + * @param Hash Hashing function object type, defaults to hash. + * @param Pred Predicate function object type, defaults to equal_to. + * @param Alloc Allocator type, defaults to allocator. + */ + template, + 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 + unordered_set(_InputIterator __f, _InputIterator __l, + size_type __n = 10, + 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(unordered_set&& __x) + : _Base(std::forward<_Base>(__x)) { } + + unordered_set(initializer_list __l, + size_type __n = 10, + 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=(unordered_set&& __x) + { + // NB: DR 1204. + // NB: DR 675. + this->clear(); + this->swap(__x); + return *this; + } + + unordered_set& + operator=(initializer_list __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 container, and + * unordered associative container + * + * @param Value Type of key objects. + * @param Hash Hashing function object type, defaults to hash. + * @param Pred Predicate function object type, defaults to equal_to. + * @param Alloc Allocator type, defaults to allocator. + */ + template, + 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 + unordered_multiset(_InputIterator __f, _InputIterator __l, + typename _Base::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(unordered_multiset&& __x) + : _Base(std::forward<_Base>(__x)) { } + + unordered_multiset(initializer_list __l, + size_type __n = 10, + 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=(unordered_multiset&& __x) + { + // NB: DR 1204. + // NB: DR 675. + this->clear(); + this->swap(__x); + return *this; + } + + unordered_multiset& + operator=(initializer_list __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + }; + + template + inline void + swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, + unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) + { __x.swap(__y); } + + template + inline void + swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, + unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) + { __x.swap(__y); } + +_GLIBCXX_END_NESTED_NAMESPACE + +#endif /* _UNORDERED_SET_H */ + diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 63b292b49f2..53ce7c09619 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -183,19 +183,11 @@ namespace __debug } iterator - insert(iterator, const value_type& __obj) - { - typedef std::pair __pair_type; - __pair_type __res = _Base::insert(__obj); - return iterator(__res.first, this); - } - - const_iterator insert(const_iterator, const value_type& __obj) { typedef std::pair __pair_type; __pair_type __res = _Base::insert(__obj); - return const_iterator(__res.first, this); + return iterator(__res.first, this); } void @@ -252,35 +244,14 @@ namespace __debug } iterator - erase(iterator __it) - { - __glibcxx_check_erase(__it); - __it._M_invalidate(); - return iterator(_Base::erase(__it.base()), this); - } - - const_iterator erase(const_iterator __it) { __glibcxx_check_erase(__it); __it._M_invalidate(); - return const_iterator(_Base::erase(__it.base()), this); + return iterator(_Base::erase(__it.base()), this); } iterator - erase(iterator __first, iterator __last) - { - __glibcxx_check_erase_range(__first, __last); - for (iterator __tmp = __first; __tmp != __last;) - { - iterator __victim = __tmp++; - __victim._M_invalidate(); - } - return iterator(_Base::erase(__first.base(), - __last.base()), this); - } - - const_iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -289,8 +260,8 @@ namespace __debug const_iterator __victim = __tmp++; __victim._M_invalidate(); } - return const_iterator(_Base::erase(__first.base(), - __last.base()), this); + return iterator(_Base::erase(__first.base(), + __last.base()), this); } _Base& @@ -453,12 +424,8 @@ namespace __debug { return iterator(_Base::insert(__obj), this); } iterator - insert(iterator, const value_type& __obj) - { return iterator(_Base::insert(__obj), this); } - - const_iterator insert(const_iterator, const value_type& __obj) - { return const_iterator(_Base::insert(__obj), this); } + { return iterator(_Base::insert(__obj), this); } void insert(std::initializer_list __l) @@ -514,35 +481,14 @@ namespace __debug } iterator - erase(iterator __it) - { - __glibcxx_check_erase(__it); - __it._M_invalidate(); - return iterator(_Base::erase(__it.base()), this); - } - - const_iterator erase(const_iterator __it) { __glibcxx_check_erase(__it); __it._M_invalidate(); - return const_iterator(_Base::erase(__it.base()), this); + return iterator(_Base::erase(__it.base()), this); } iterator - erase(iterator __first, iterator __last) - { - __glibcxx_check_erase_range(__first, __last); - for (iterator __tmp = __first; __tmp != __last;) - { - iterator __victim = __tmp++; - __victim._M_invalidate(); - } - return iterator(_Base::erase(__first.base(), - __last.base()), this); - } - - const_iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -551,8 +497,8 @@ namespace __debug const_iterator __victim = __tmp++; __victim._M_invalidate(); } - return const_iterator(_Base::erase(__first.base(), - __last.base()), this); + return iterator(_Base::erase(__first.base(), + __last.base()), this); } _Base& diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index d34b2816e70..19ff42408fd 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -183,19 +183,11 @@ namespace __debug } iterator - insert(iterator, const value_type& __obj) - { - typedef std::pair __pair_type; - __pair_type __res = _Base::insert(__obj); - return iterator(__res.first, this); - } - - const_iterator insert(const_iterator, const value_type& __obj) { typedef std::pair __pair_type; __pair_type __res = _Base::insert(__obj); - return const_iterator(__res.first, this); + return iterator(__res.first, this); } void @@ -252,35 +244,14 @@ namespace __debug } iterator - erase(iterator __it) - { - __glibcxx_check_erase(__it); - __it._M_invalidate(); - return iterator(_Base::erase(__it.base()), this); - } - - const_iterator erase(const_iterator __it) { __glibcxx_check_erase(__it); __it._M_invalidate(); - return const_iterator(_Base::erase(__it.base()), this); + return iterator(_Base::erase(__it.base()), this); } iterator - erase(iterator __first, iterator __last) - { - __glibcxx_check_erase_range(__first, __last); - for (iterator __tmp = __first; __tmp != __last;) - { - iterator __victim = __tmp++; - __victim._M_invalidate(); - } - return iterator(_Base::erase(__first.base(), - __last.base()), this); - } - - const_iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -289,8 +260,8 @@ namespace __debug const_iterator __victim = __tmp++; __victim._M_invalidate(); } - return const_iterator(_Base::erase(__first.base(), - __last.base()), this); + return iterator(_Base::erase(__first.base(), + __last.base()), this); } _Base& @@ -451,12 +422,8 @@ namespace __debug { return iterator(_Base::insert(__obj), this); } iterator - insert(iterator, const value_type& __obj) - { return iterator(_Base::insert(__obj), this); } - - const_iterator insert(const_iterator, const value_type& __obj) - { return const_iterator(_Base::insert(__obj), this); } + { return iterator(_Base::insert(__obj), this); } void insert(std::initializer_list __l) @@ -512,35 +479,14 @@ namespace __debug } iterator - erase(iterator __it) - { - __glibcxx_check_erase(__it); - __it._M_invalidate(); - return iterator(_Base::erase(__it.base()), this); - } - - const_iterator erase(const_iterator __it) { __glibcxx_check_erase(__it); __it._M_invalidate(); - return const_iterator(_Base::erase(__it.base()), this); + return iterator(_Base::erase(__it.base()), this); } iterator - erase(iterator __first, iterator __last) - { - __glibcxx_check_erase_range(__first, __last); - for (iterator __tmp = __first; __tmp != __last;) - { - iterator __victim = __tmp++; - __victim._M_invalidate(); - } - return iterator(_Base::erase(__first.base(), - __last.base()), this); - } - - const_iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -549,8 +495,8 @@ namespace __debug const_iterator __victim = __tmp++; __victim._M_invalidate(); } - return const_iterator(_Base::erase(__first.base(), - __last.base()), this); + return iterator(_Base::erase(__first.base(), + __last.base()), this); } _Base& diff --git a/libstdc++-v3/include/profile/unordered_map b/libstdc++-v3/include/profile/unordered_map index 74781de2dd4..61f32f3036f 100644 --- a/libstdc++-v3/include/profile/unordered_map +++ b/libstdc++-v3/include/profile/unordered_map @@ -186,31 +186,22 @@ namespace __profile } iterator - insert(iterator __iter, const value_type& __v) - { - size_type __old_size = _Base::bucket_count(); - iterator res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); - return res; - } - - const_iterator insert(const_iterator __iter, const value_type& __v) { size_type __old_size = _Base::bucket_count(); - const_iterator res =_Base::insert(__iter, __v); + iterator __res = _Base::insert(__iter, __v); _M_profile_resize(__old_size, _Base::bucket_count()); - return res; + return __res; } template - void - insert(_InputIter __first, _InputIter __last) - { - size_type __old_size = _Base::bucket_count(); - _Base::insert(__first.base(), __last.base()); - _M_profile_resize(__old_size, _Base::bucket_count()); - } + void + insert(_InputIter __first, _InputIter __last) + { + size_type __old_size = _Base::bucket_count(); + _Base::insert(__first.base(), __last.base()); + _M_profile_resize(__old_size, _Base::bucket_count()); + } void insert(const value_type* __first, const value_type* __last) @@ -233,51 +224,54 @@ namespace __profile void swap(unordered_map& __x) - { - _Base::swap(__x); - } - + { _Base::swap(__x); } + void rehash(size_type __n) { size_type __old_size = _Base::bucket_count(); _Base::rehash(__n); _M_profile_resize(__old_size, _Base::bucket_count()); } + private: - void _M_profile_resize(size_type __old_size, size_type __new_size) + void + _M_profile_resize(size_type __old_size, size_type __new_size) { if (__old_size != __new_size) - { - __profcxx_hashtable_resize(this, __old_size, __new_size); - } + __profcxx_hashtable_resize(this, __old_size, __new_size); } - void _M_profile_destruct() + + void + _M_profile_destruct() { size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator it = _M_base().begin(); it != _M_base().end(); it++) - { - while (it._M_cur_node->_M_next) { - __chain++; - it++; - } - if (__chain) { - __chain++; - __lc = __lc > __chain ? __lc : __chain; - __hops += __chain * (__chain - 1) / 2; - __chain = 0; - } - } + for (iterator __it = _M_base().begin(); __it != _M_base().end(); + ++__it) + { + while (__it._M_cur_node->_M_next) + { + ++__chain; + ++__it; + } + if (__chain) + { + ++__chain; + __lc = __lc > __chain ? __lc : __chain; + __hops += __chain * (__chain - 1) / 2; + __chain = 0; + } + } __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } }; + template + typename _Pred, typename _Alloc> inline void swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) + unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { __x.swap(__y); } - #undef _GLIBCXX_BASE #undef _GLIBCXX_STD_BASE #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> @@ -412,31 +406,22 @@ namespace __profile } iterator - insert(iterator __iter, const value_type& __v) - { - size_type __old_size = _Base::bucket_count(); - iterator res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); - return res; - } - - const_iterator insert(const_iterator __iter, const value_type& __v) { size_type __old_size = _Base::bucket_count(); - const_iterator res =_Base::insert(__iter, __v); + iterator __res =_Base::insert(__iter, __v); _M_profile_resize(__old_size, _Base::bucket_count()); - return res; + return __res; } template - void - insert(_InputIter __first, _InputIter __last) - { - size_type __old_size = _Base::bucket_count(); - _Base::insert(__first.base(), __last.base()); - _M_profile_resize(__old_size, _Base::bucket_count()); - } + void + insert(_InputIter __first, _InputIter __last) + { + size_type __old_size = _Base::bucket_count(); + _Base::insert(__first.base(), __last.base()); + _M_profile_resize(__old_size, _Base::bucket_count()); + } void insert(const value_type* __first, const value_type* __last) @@ -448,9 +433,7 @@ namespace __profile void swap(unordered_multimap& __x) - { - _Base::swap(__x); - } + { _Base::swap(__x); } void rehash(size_type __n) { @@ -458,40 +441,45 @@ namespace __profile _Base::rehash(__n); _M_profile_resize(__old_size, _Base::bucket_count()); } + private: - void _M_profile_resize(size_type __old_size, size_type __new_size) + void + _M_profile_resize(size_type __old_size, size_type __new_size) { if (__old_size != __new_size) - { __profcxx_hashtable_resize(this, __old_size, __new_size); - } } - void _M_profile_destruct() + void + _M_profile_destruct() { size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator it = _M_base().begin(); it != _M_base().end(); it++) - { - while (it._M_cur_node->_M_next) { - __chain++; - it++; - } - if (__chain) { - __chain++; - __lc = __lc > __chain ? __lc : __chain; - __hops += __chain * (__chain - 1) / 2; - __chain = 0; - } - } + for (iterator __it = _M_base().begin(); __it != _M_base().end(); + ++__it) + { + while (__it._M_cur_node->_M_next) + { + ++__chain; + ++__it; + } + if (__chain) + { + ++__chain; + __lc = __lc > __chain ? __lc : __chain; + __hops += __chain * (__chain - 1) / 2; + __chain = 0; + } + } __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } }; + template + typename _Pred, typename _Alloc> inline void swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) + unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { __x.swap(__y); } } // namespace __profile diff --git a/libstdc++-v3/include/profile/unordered_set b/libstdc++-v3/include/profile/unordered_set index 62bb1a423bd..0c0de77a58b 100644 --- a/libstdc++-v3/include/profile/unordered_set +++ b/libstdc++-v3/include/profile/unordered_set @@ -184,31 +184,22 @@ namespace __profile } iterator - insert(iterator __iter, const value_type& __v) - { - size_type __old_size = _Base::bucket_count(); - iterator res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); - return res; - } - - const_iterator insert(const_iterator __iter, const value_type& __v) { size_type __old_size = _Base::bucket_count(); - const_iterator res =_Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); - return res; + iterator __res = _Base::insert(__iter, __v); + _M_profile_resize(__old_size, _Base::bucket_count()); + return __res; } template - void - insert(_InputIter __first, _InputIter __last) - { - size_type __old_size = _Base::bucket_count(); - _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); - } + void + insert(_InputIter __first, _InputIter __last) + { + size_type __old_size = _Base::bucket_count(); + _Base::insert(__first, __last); + _M_profile_resize(__old_size, _Base::bucket_count()); + } void insert(const value_type* __first, const value_type* __last) @@ -232,37 +223,43 @@ namespace __profile const _Base& _M_base() const { return *this; } - void _M_profile_resize(size_type __old_size, size_type __new_size) + void + _M_profile_resize(size_type __old_size, size_type __new_size) { if (__old_size != __new_size) - { - __profcxx_hashtable_resize(this, __old_size, __new_size); - } + __profcxx_hashtable_resize(this, __old_size, __new_size); } - void _M_profile_destruct() + + void + _M_profile_destruct() { size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator it = _M_base().begin(); it != _M_base().end(); it++) + for (iterator __it = _M_base().begin(); __it != _M_base().end(); + ++__it) { - while (it._M_cur_node->_M_next) { - __chain++; - it++; - } - if (__chain) { - __chain++; - __lc = __lc > __chain ? __lc : __chain; - __hops += __chain * (__chain - 1) / 2; - __chain = 0; - } + while (__it._M_cur_node->_M_next) + { + ++__chain; + ++__it; + } + + if (__chain) + { + ++__chain; + __lc = __lc > __chain ? __lc : __chain; + __hops += __chain * (__chain - 1) / 2; + __chain = 0; + } } __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } }; + template inline void swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, - unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) + unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { __x.swap(__y); } #undef _GLIBCXX_BASE @@ -399,31 +396,22 @@ namespace __profile } iterator - insert(iterator __iter, const value_type& __v) - { - size_type __old_size = _Base::bucket_count(); - iterator res = _Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); - return res; - } - - const_iterator insert(const_iterator __iter, const value_type& __v) { size_type __old_size = _Base::bucket_count(); - const_iterator res =_Base::insert(__iter, __v); - _M_profile_resize(__old_size, _Base::bucket_count()); - return res; + iterator __res = _Base::insert(__iter, __v); + _M_profile_resize(__old_size, _Base::bucket_count()); + return __res; } template - void - insert(_InputIter __first, _InputIter __last) - { - size_type __old_size = _Base::bucket_count(); - _Base::insert(__first, __last); - _M_profile_resize(__old_size, _Base::bucket_count()); - } + void + insert(_InputIter __first, _InputIter __last) + { + size_type __old_size = _Base::bucket_count(); + _Base::insert(__first, __last); + _M_profile_resize(__old_size, _Base::bucket_count()); + } void insert(const value_type* __first, const value_type* __last) @@ -447,38 +435,43 @@ namespace __profile const _Base& _M_base() const { return *this; } - void _M_profile_resize(size_type __old_size, size_type __new_size) + void + _M_profile_resize(size_type __old_size, size_type __new_size) { if (__old_size != __new_size) - { __profcxx_hashtable_resize(this, __old_size, __new_size); - } } - void _M_profile_destruct() + void + _M_profile_destruct() { size_type __hops = 0, __lc = 0, __chain = 0; - for (iterator it = _M_base().begin(); it != _M_base().end(); it++) + for (iterator __it = _M_base().begin(); __it != _M_base().end(); + ++__it) { - while (it._M_cur_node->_M_next) { - __chain++; - it++; - } - if (__chain) { - __chain++; - __lc = __lc > __chain ? __lc : __chain; - __hops += __chain * (__chain - 1) / 2; - __chain = 0; - } + while (__it._M_cur_node->_M_next) + { + ++__chain; + ++__it; + } + + if (__chain) + { + ++__chain; + __lc = __lc > __chain ? __lc : __chain; + __hops += __chain * (__chain - 1) / 2; + __chain = 0; + } } __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); } }; + template inline void swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, - unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) + unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { __x.swap(__y); } } // namespace __profile diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map index f8cd5459787..2fe36660543 100644 --- a/libstdc++-v3/include/std/unordered_map +++ b/libstdc++-v3/include/std/unordered_map @@ -1,6 +1,6 @@ // -*- C++ -*- -// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010 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 @@ -35,10 +35,6 @@ # include #else -#if defined(_GLIBCXX_INCLUDE_AS_TR1) -# error C++0x header cannot be included from TR1 header -#endif - #include #include #include @@ -48,26 +44,7 @@ #include #include #include - -#if defined(_GLIBCXX_INCLUDE_AS_CXX0X) -# include -#else -# define _GLIBCXX_INCLUDE_AS_CXX0X -#if defined(_GLIBCXX_DEBUG) || defined(_GLIBCXX_PARALLEL) || defined(_GLIBCXX_PROFILE) -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 namespace _GLIBCXX_STD_D { -# define _GLIBCXX_END_NAMESPACE_TR1 } -# define _GLIBCXX_TR1 _GLIBCXX_STD_D -#else -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 -# define _GLIBCXX_END_NAMESPACE_TR1 -# define _GLIBCXX_TR1 -#endif -# include -# undef _GLIBCXX_TR1 -# undef _GLIBCXX_END_NAMESPACE_TR1 -# undef _GLIBCXX_BEGIN_NAMESPACE_TR1 -# undef _GLIBCXX_INCLUDE_AS_CXX0X -#endif +#include #ifdef _GLIBCXX_DEBUG # include diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set index b5b4f108980..9eaa22f8a53 100644 --- a/libstdc++-v3/include/std/unordered_set +++ b/libstdc++-v3/include/std/unordered_set @@ -1,6 +1,6 @@ // -*- C++ -*- -// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010 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 @@ -35,10 +35,6 @@ # include #else -#if defined(_GLIBCXX_INCLUDE_AS_TR1) -# error C++0x header cannot be included from TR1 header -#endif - #include #include #include @@ -48,26 +44,7 @@ #include #include #include - -#if defined(_GLIBCXX_INCLUDE_AS_CXX0X) -# include -#else -# define _GLIBCXX_INCLUDE_AS_CXX0X -#if defined(_GLIBCXX_DEBUG) || defined(_GLIBCXX_PARALLEL) || defined(_GLIBCXX_PROFILE) -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 namespace _GLIBCXX_STD_D { -# define _GLIBCXX_END_NAMESPACE_TR1 } -# define _GLIBCXX_TR1 _GLIBCXX_STD_D -#else -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 -# define _GLIBCXX_END_NAMESPACE_TR1 -# define _GLIBCXX_TR1 -#endif -# include -# undef _GLIBCXX_TR1 -# undef _GLIBCXX_END_NAMESPACE_TR1 -# undef _GLIBCXX_BEGIN_NAMESPACE_TR1 -# undef _GLIBCXX_INCLUDE_AS_CXX0X -#endif +#include #ifdef _GLIBCXX_DEBUG # include diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map index 316630f4cbf..4ac2d58aefb 100644 --- a/libstdc++-v3/include/tr1/unordered_map +++ b/libstdc++-v3/include/tr1/unordered_map @@ -1,6 +1,6 @@ // TR1 unordered_map -*- C++ -*- -// Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// Copyright (C) 2005, 2006, 2007, 2009, 2010 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 @@ -31,10 +31,6 @@ #pragma GCC system_header -#if defined(_GLIBCXX_INCLUDE_AS_CXX0X) -# error TR1 header cannot be included from C++0x header -#endif - #include #include #include @@ -43,19 +39,6 @@ #include #include #include - -#if defined(_GLIBCXX_INCLUDE_AS_TR1) -# include -#else -# define _GLIBCXX_INCLUDE_AS_TR1 -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 namespace tr1 { -# define _GLIBCXX_END_NAMESPACE_TR1 } -# define _GLIBCXX_TR1 tr1:: -# include -# undef _GLIBCXX_TR1 -# undef _GLIBCXX_END_NAMESPACE_TR1 -# undef _GLIBCXX_BEGIN_NAMESPACE_TR1 -# undef _GLIBCXX_INCLUDE_AS_TR1 -#endif +#include #endif // _GLIBCXX_TR1_UNORDERED_MAP diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set index 3bd09444ed6..73e3adb34e6 100644 --- a/libstdc++-v3/include/tr1/unordered_set +++ b/libstdc++-v3/include/tr1/unordered_set @@ -1,6 +1,6 @@ // TR1 unordered_set -*- C++ -*- -// Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// Copyright (C) 2005, 2006, 2007, 2009, 2010 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 @@ -31,10 +31,6 @@ #pragma GCC system_header -#if defined(_GLIBCXX_INCLUDE_AS_CXX0X) -# error TR1 header cannot be included from C++0x header -#endif - #include #include #include @@ -43,19 +39,6 @@ #include #include #include - -#if defined(_GLIBCXX_INCLUDE_AS_TR1) -# include -#else -# define _GLIBCXX_INCLUDE_AS_TR1 -# define _GLIBCXX_BEGIN_NAMESPACE_TR1 namespace tr1 { -# define _GLIBCXX_END_NAMESPACE_TR1 } -# define _GLIBCXX_TR1 tr1:: -# include -# undef _GLIBCXX_TR1 -# undef _GLIBCXX_END_NAMESPACE_TR1 -# undef _GLIBCXX_BEGIN_NAMESPACE_TR1 -# undef _GLIBCXX_INCLUDE_AS_TR1 -#endif +#include #endif // _GLIBCXX_TR1_UNORDERED_SET diff --git a/libstdc++-v3/include/tr1_impl/hashtable b/libstdc++-v3/include/tr1_impl/hashtable index f9ff933cad9..5be91b01068 100644 --- a/libstdc++-v3/include/tr1_impl/hashtable +++ b/libstdc++-v3/include/tr1_impl/hashtable @@ -49,8 +49,8 @@ namespace std { -_GLIBCXX_BEGIN_NAMESPACE_TR1 - +namespace tr1 +{ // Class template _Hashtable, class definition. // Meaning of class template _Hashtable's template parameters @@ -215,11 +215,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 const allocator_type&); _Hashtable(const _Hashtable&); - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - _Hashtable(_Hashtable&&); -#endif - + _Hashtable& operator=(const _Hashtable&); @@ -254,21 +250,6 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 end() const { return const_iterator(_M_buckets + _M_bucket_count); } -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - const_iterator - cbegin() const - { - const_iterator __i(_M_buckets); - if (!__i._M_cur_node) - __i._M_incr_bucket(); - return __i; - } - - const_iterator - cend() const - { return const_iterator(_M_buckets + _M_bucket_count); } -#endif - size_type size() const { return _M_element_count; } @@ -332,17 +313,6 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 end(size_type) const { return const_local_iterator(0); } -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - // DR 691. - const_local_iterator - cbegin(size_type __n) const - { return const_local_iterator(_M_buckets[__n]); } - - const_local_iterator - cend(size_type) const - { return const_local_iterator(0); } -#endif - float load_factor() const { @@ -400,10 +370,10 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 typename _Hashtable::_Hash_code_type); std::pair - _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type); + _M_insert(const value_type&, std::tr1::true_type); iterator - _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type); + _M_insert(const value_type&, std::tr1::false_type); void _M_erase_node(_Node*, _Node**); @@ -412,7 +382,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 // Insert and erase _Insert_Return_Type insert(const value_type& __v) - { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant()); } iterator @@ -427,12 +397,6 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 void insert(_InputIterator __first, _InputIterator __last); -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - void - insert(initializer_list __l) - { this->insert(__l.begin(), __l.end()); } -#endif - iterator erase(iterator); @@ -475,11 +439,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 _Node* __n = _M_node_allocator.allocate(1); __try { -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - _M_node_allocator.construct(__n, __v); -#else _M_get_Value_allocator().construct(&__n->_M_v, __v); -#endif __n->_M_next = 0; return __n; } @@ -499,11 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_deallocate_node(_Node* __n) { -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - _M_node_allocator.destroy(__n); -#else _M_get_Value_allocator().destroy(&__n->_M_v); -#endif _M_node_allocator.deallocate(__n, 1); } @@ -668,32 +624,6 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 } } -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - template - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _Hashtable(_Hashtable&& __ht) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), - __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__ht), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), - _M_node_allocator(__ht._M_node_allocator), - _M_bucket_count(__ht._M_bucket_count), - _M_element_count(__ht._M_element_count), - _M_rehash_policy(__ht._M_rehash_policy), - _M_buckets(__ht._M_buckets) - { - size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0); - __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt); - __ht._M_bucket_count = __n_bkt; - __ht._M_element_count = 0; - __ht._M_rehash_policy = _RehashPolicy(); - } -#endif - template::iterator, bool> _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert(const value_type& __v, std::_GLIBCXX_TR1 true_type) + _M_insert(const value_type& __v, std::tr1::true_type) { const key_type& __k = this->_M_extract(__v); typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); @@ -987,7 +917,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 __chc, __cit, __uk>::iterator _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert(const value_type& __v, std::_GLIBCXX_TR1 false_type) + _M_insert(const value_type& __v, std::tr1::false_type) { std::pair __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, @@ -1253,6 +1183,5 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 __throw_exception_again; } } - -_GLIBCXX_END_NAMESPACE_TR1 +} } diff --git a/libstdc++-v3/include/tr1_impl/hashtable_policy.h b/libstdc++-v3/include/tr1_impl/hashtable_policy.h index 8996d04d989..6b2dd342c17 100644 --- a/libstdc++-v3/include/tr1_impl/hashtable_policy.h +++ b/libstdc++-v3/include/tr1_impl/hashtable_policy.h @@ -1,6 +1,6 @@ // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- -// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010 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 @@ -29,8 +29,8 @@ namespace std { -_GLIBCXX_BEGIN_NAMESPACE_TR1 - +namespace tr1 +{ namespace __detail { // Helper function: return distance(first, last) for forward @@ -94,13 +94,6 @@ namespace __detail _Value _M_v; std::size_t _M_hash_code; _Hash_node* _M_next; - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - template - _Hash_node(_Args&&... __args) - : _M_v(std::forward<_Args>(__args)...), - _M_hash_code(), _M_next() { } -#endif }; template @@ -108,13 +101,6 @@ namespace __detail { _Value _M_v; _Hash_node* _M_next; - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - template - _Hash_node(_Args&&... __args) - : _M_v(std::forward<_Args>(__args)...), - _M_next() { } -#endif }; // Local iterators, used to iterate within a bucket but not between @@ -545,16 +531,6 @@ namespace __detail mapped_type& operator[](const _Key& __k); - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // DR 761. unordered_map needs an at() member function. - mapped_type& - at(const _Key& __k); - - const mapped_type& - at(const _Key& __k) const; -#endif }; template @@ -576,44 +552,6 @@ namespace __detail return (__p->_M_v).second; } -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - template - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - at(const _Key& __k) - { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); - std::size_t __n = __h->_M_bucket_index(__k, __code, - __h->_M_bucket_count); - - typename _Hashtable::_Node* __p = - __h->_M_find_node(__h->_M_buckets[__n], __k, __code); - if (!__p) - __throw_out_of_range(__N("_Map_base::at")); - return (__p->_M_v).second; - } - - template - const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - at(const _Key& __k) const - { - const _Hashtable* __h = static_cast(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); - std::size_t __n = __h->_M_bucket_index(__k, __code, - __h->_M_bucket_count); - - typename _Hashtable::_Node* __p = - __h->_M_find_node(__h->_M_buckets[__n], __k, __code); - if (!__p) - __throw_out_of_range(__N("_Map_base::at")); - return (__p->_M_v).second; - } -#endif - // class template _Rehash_base. Give hashtable the max_load_factor // functions iff the rehash policy is _Prime_rehash_policy. template @@ -860,6 +798,5 @@ namespace __detail _H2 _M_h2; }; } // namespace __detail - -_GLIBCXX_END_NAMESPACE_TR1 +} } diff --git a/libstdc++-v3/include/tr1_impl/unordered_map b/libstdc++-v3/include/tr1_impl/unordered_map index ba8f6729017..54b1e562954 100644 --- a/libstdc++-v3/include/tr1_impl/unordered_map +++ b/libstdc++-v3/include/tr1_impl/unordered_map @@ -1,6 +1,6 @@ // TR1 unordered_map -*- C++ -*- -// Copyright (C) 2007, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2009, 2010 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 @@ -29,8 +29,8 @@ namespace std { -_GLIBCXX_BEGIN_NAMESPACE_TR1 - +namespace tr1 +{ // XXX When we get typedef templates these class definitions // will be unnecessary. template >(), __a) { } - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - __unordered_map(__unordered_map&& __x) - : _Base(std::forward<_Base>(__x)) { } -#endif }; template >(), __a) { } - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - __unordered_multimap(__unordered_multimap&& __x) - : _Base(std::forward<_Base>(__x)) { } -#endif }; template(__x)) { } - - unordered_map(initializer_list __l, - size_type __n = 10, - 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_map& - operator=(unordered_map&& __x) - { - // NB: DR 1204. - // NB: DR 675. - this->clear(); - this->swap(__x); - return *this; - } - - unordered_map& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } -#endif }; /** @@ -298,36 +257,6 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 : _Base(__f, __l, __n, __hf, __eql, __a) { } -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - unordered_multimap(unordered_multimap&& __x) - : _Base(std::forward<_Base>(__x)) { } - - unordered_multimap(initializer_list __l, - size_type __n = 10, - 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_multimap& - operator=(unordered_multimap&& __x) - { - // NB: DR 1204. - // NB: DR 675. - this->clear(); - this->swap(__x); - return *this; - } - - unordered_multimap& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } -#endif }; template @@ -341,6 +270,5 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { __x.swap(__y); } - -_GLIBCXX_END_NAMESPACE_TR1 +} } diff --git a/libstdc++-v3/include/tr1_impl/unordered_set b/libstdc++-v3/include/tr1_impl/unordered_set index c11d9f3021b..6967ae5c343 100644 --- a/libstdc++-v3/include/tr1_impl/unordered_set +++ b/libstdc++-v3/include/tr1_impl/unordered_set @@ -29,8 +29,8 @@ namespace std { -_GLIBCXX_BEGIN_NAMESPACE_TR1 - +namespace tr1 +{ // XXX When we get typedef templates these class definitions // will be unnecessary. template(), __a) { } - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - __unordered_set(__unordered_set&& __x) - : _Base(std::forward<_Base>(__x)) { } -#endif }; template(), __a) { } - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - __unordered_multiset(__unordered_multiset&& __x) - : _Base(std::forward<_Base>(__x)) { } -#endif }; template(__x)) { } - - unordered_set(initializer_list __l, - size_type __n = 10, - 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=(unordered_set&& __x) - { - // NB: DR 1204. - // NB: DR 675. - this->clear(); - this->swap(__x); - return *this; - } - - unordered_set& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } -#endif }; /** @@ -287,37 +246,6 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) { } - -#ifdef _GLIBCXX_INCLUDE_AS_CXX0X - unordered_multiset(unordered_multiset&& __x) - : _Base(std::forward<_Base>(__x)) { } - - unordered_multiset(initializer_list __l, - size_type __n = 10, - 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=(unordered_multiset&& __x) - { - // NB: DR 1204. - // NB: DR 675. - this->clear(); - this->swap(__x); - return *this; - } - - unordered_multiset& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } -#endif }; template @@ -331,6 +259,5 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { __x.swap(__y); } - -_GLIBCXX_END_NAMESPACE_TR1 +} } diff --git a/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc b/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc index 647fef7f808..c5fd9cd0db6 100644 --- a/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc @@ -1,6 +1,7 @@ // { dg-do compile } -// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 +// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, +// 2008, 2009, 2010 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -40,6 +41,5 @@ void test01() test &= itr != mapByName.end(); // { dg-error "no" } test &= itr == mapByName.end(); // { dg-error "no" } } - -// { dg-error "candidate is" "" { target *-*-* } 212 } -// { dg-error "candidate is" "" { target *-*-* } 216 } + +// { dg-excess-errors "" } diff --git a/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc b/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc index 6765fc1d1da..babd6db2b2b 100644 --- a/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc @@ -1,6 +1,7 @@ // { dg-do compile } -// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 +// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, +// 2008, 2009, 2010 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -39,5 +40,4 @@ void test01() test &= itr == setByName.end(); // { dg-error "no" } } -// { dg-error "candidate is" "" { target *-*-* } 287 } -// { dg-error "candidate is" "" { target *-*-* } 291 } +// { dg-excess-errors "" } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/erase/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/erase/1.cc new file mode 100644 index 00000000000..f9b74e08c8d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/erase/1.cc @@ -0,0 +1,129 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef Map::iterator iterator; + typedef Map::const_iterator const_iterator; + typedef Map::value_type value_type; + + Map m1; + + m1.insert(value_type("because to why", 1)); + m1.insert(value_type("the stockholm syndrome", 2)); + m1.insert(value_type("a cereous night", 3)); + m1.insert(value_type("eeilo", 4)); + m1.insert(value_type("protean", 5)); + m1.insert(value_type("the way you are when", 6)); + m1.insert(value_type("tillsammans", 7)); + m1.insert(value_type("umbra/penumbra", 8)); + m1.insert(value_type("belonging (no longer mix)", 9)); + m1.insert(value_type("one line behind", 10)); + VERIFY( m1.size() == 10 ); + + VERIFY( m1.erase("eeilo") == 1 ); + VERIFY( m1.size() == 9 ); + iterator it1 = m1.find("eeilo"); + VERIFY( it1 == m1.end() ); + + VERIFY( m1.erase("tillsammans") == 1 ); + VERIFY( m1.size() == 8 ); + iterator it2 = m1.find("tillsammans"); + VERIFY( it2 == m1.end() ); + + // Must work (see DR 526) + iterator it3 = m1.find("belonging (no longer mix)"); + VERIFY( it3 != m1.end() ); + VERIFY( m1.erase(it3->first) == 1 ); + VERIFY( m1.size() == 7 ); + it3 = m1.find("belonging (no longer mix)"); + VERIFY( it3 == m1.end() ); + + VERIFY( !m1.erase("abra") ); + VERIFY( m1.size() == 7 ); + + VERIFY( !m1.erase("eeilo") ); + VERIFY( m1.size() == 7 ); + + VERIFY( m1.erase("because to why") == 1 ); + VERIFY( m1.size() == 6 ); + iterator it4 = m1.find("because to why"); + VERIFY( it4 == m1.end() ); + + iterator it5 = m1.find("umbra/penumbra"); + iterator it6 = m1.find("one line behind"); + VERIFY( it5 != m1.end() ); + VERIFY( it6 != m1.end() ); + + VERIFY( m1.find("the stockholm syndrome") != m1.end() ); + VERIFY( m1.find("a cereous night") != m1.end() ); + VERIFY( m1.find("the way you are when") != m1.end() ); + VERIFY( m1.find("a cereous night") != m1.end() ); + + VERIFY( m1.erase(it5->first) == 1 ); + VERIFY( m1.size() == 5 ); + it5 = m1.find("umbra/penumbra"); + VERIFY( it5 == m1.end() ); + + VERIFY( m1.erase(it6->first) == 1 ); + VERIFY( m1.size() == 4 ); + it6 = m1.find("one line behind"); + VERIFY( it6 == m1.end() ); + + iterator it7 = m1.begin(); + iterator it8 = it7; + ++it8; + iterator it9 = it8; + ++it9; + + VERIFY( m1.erase(it8->first) == 1 ); + VERIFY( m1.size() == 3 ); + VERIFY( ++it7 == it9 ); + + iterator it10 = it9; + ++it10; + iterator it11 = it10; + + VERIFY( m1.erase(it9->first) == 1 ); + VERIFY( m1.size() == 2 ); + VERIFY( ++it10 == m1.end() ); + + VERIFY( m1.erase(m1.begin()) != m1.end() ); + VERIFY( m1.size() == 1 ); + VERIFY( m1.begin() == it11 ); + + VERIFY( m1.erase(m1.begin()->first) == 1 ); + VERIFY( m1.size() == 0 ); + VERIFY( m1.begin() == m1.end() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/erase/24061-map.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/erase/24061-map.cc new file mode 100644 index 00000000000..87ab474a826 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/erase/24061-map.cc @@ -0,0 +1,105 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef Map::iterator iterator; + typedef Map::const_iterator const_iterator; + typedef Map::value_type value_type; + + Map m1; + + m1.insert(value_type("all the love in the world", 1)); + m1.insert(value_type("you know what you are?", 2)); + m1.insert(value_type("the collector", 3)); + m1.insert(value_type("the hand that feeds", 4)); + m1.insert(value_type("love is not enough", 5)); + m1.insert(value_type("every day is exactly the same", 6)); + m1.insert(value_type("with teeth", 7)); + m1.insert(value_type("only", 8)); + m1.insert(value_type("getting smaller", 9)); + m1.insert(value_type("sunspots", 10)); + VERIFY( m1.size() == 10 ); + + iterator it1 = m1.begin(); + ++it1; + iterator it2 = it1; + ++it2; + iterator it3 = m1.erase(it1); + VERIFY( m1.size() == 9 ); + VERIFY( it3 == it2 ); + VERIFY( *it3 == *it2 ); + + iterator it4 = m1.begin(); + ++it4; + ++it4; + ++it4; + iterator it5 = it4; + ++it5; + ++it5; + iterator it6 = m1.erase(it4, it5); + VERIFY( m1.size() == 7 ); + VERIFY( it6 == it5 ); + VERIFY( *it6 == *it5 ); + + const_iterator it7 = m1.begin(); + ++it7; + ++it7; + ++it7; + const_iterator it8 = it7; + ++it8; + const_iterator it9 = m1.erase(it7); + VERIFY( m1.size() == 6 ); + VERIFY( it9 == it8 ); + VERIFY( *it9 == *it8 ); + + const_iterator it10 = m1.begin(); + ++it10; + const_iterator it11 = it10; + ++it11; + ++it11; + ++it11; + ++it11; + const_iterator it12 = m1.erase(it10, it11); + VERIFY( m1.size() == 2 ); + VERIFY( it12 == it11 ); + VERIFY( *it12 == *it11 ); + VERIFY( ++it12 == m1.end() ); + + iterator it13 = m1.erase(m1.begin(), m1.end()); + VERIFY( m1.size() == 0 ); + VERIFY( it13 == it12 ); + VERIFY( it13 == m1.begin() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/24061-map.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/24061-map.cc new file mode 100644 index 00000000000..d9a1878702d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/24061-map.cc @@ -0,0 +1,60 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef Map::iterator iterator; + typedef Map::const_iterator const_iterator; + typedef Map::value_type value_type; + + Map m1; + + iterator it1 = m1.insert(m1.begin(), + value_type("all the love in the world", 1)); + VERIFY( m1.size() == 1 ); + VERIFY( *it1 == value_type("all the love in the world", 1) ); + + const_iterator cit1(it1); + const_iterator cit2 = m1.insert(cit1, + value_type("you know what you are?", 2)); + VERIFY( m1.size() == 2 ); + VERIFY( cit2 != cit1 ); + VERIFY( *cit2 == value_type("you know what you are?", 2) ); + + iterator it2 = m1.insert(it1, value_type("all the love in the world", 3)); + VERIFY( m1.size() == 2 ); + VERIFY( it2 == it1 ); + VERIFY( *it2 == value_type("all the love in the world", 1) ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax.cc new file mode 100644 index 00000000000..11fddbb39dd --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/array_syntax.cc @@ -0,0 +1,57 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Array version of insert + +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + m["red"] = 17; + VERIFY(m.size() == 1); + VERIFY(m.begin()->first == "red"); + VERIFY(m.begin()->second == 17); + VERIFY(m["red"] == 17); + + m["blue"] = 9; + VERIFY(m.size() == 2); + VERIFY(m["blue"] == 9); + + m["red"] = 5; + VERIFY(m.size() == 2); + VERIFY(m["red"] == 5); + VERIFY(m["blue"] == 9); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_range.cc new file mode 100644 index 00000000000..5e5298c0469 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_range.cc @@ -0,0 +1,97 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// range insert + +#include +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + Pair A[5] = + { + Pair("red", 5), + Pair("green", 9), + Pair("blue", 3), + Pair("cyan", 8), + Pair("magenta", 7) + }; + + m.insert(A+0, A+5); + VERIFY(m.size() == 5); + VERIFY(std::distance(m.begin(), m.end()) == 5); + + VERIFY(m["red"] == 5); + VERIFY(m["green"] == 9); + VERIFY(m["blue"] == 3); + VERIFY(m["cyan"] == 8); + VERIFY(m["magenta"] == 7); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + Pair A[9] = + { + Pair("red", 5), + Pair("green", 9), + Pair("red", 19), + Pair("blue", 3), + Pair("blue", 60), + Pair("cyan", 8), + Pair("magenta", 7), + Pair("blue", 99), + Pair("green", 33) + }; + + m.insert(A+0, A+9); + VERIFY(m.size() == 5); + VERIFY(std::distance(m.begin(), m.end()) == 5); + + VERIFY(m["red"] == 5); + VERIFY(m["green"] == 9); + VERIFY(m["blue"] == 3); + VERIFY(m["cyan"] == 8); + VERIFY(m["magenta"] == 7); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_single.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_single.cc new file mode 100644 index 00000000000..3905e26c9fc --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/map_single.cc @@ -0,0 +1,72 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Single-element insert + +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + std::pair p = m.insert(Pair("abcde", 3)); + VERIFY(p.second); + VERIFY(m.size() == 1); + VERIFY(std::distance(m.begin(), m.end()) == 1); + VERIFY(p.first == m.begin()); + VERIFY(p.first->first == "abcde"); + VERIFY(p.first->second == 3); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + std::pair p1 = m.insert(Pair("abcde", 3)); + std::pair p2 = m.insert(Pair("abcde", 7)); + + VERIFY(p1.second); + VERIFY(!p2.second); + VERIFY(m.size() == 1); + VERIFY(p1.first == p2.first); + VERIFY(p1.first->first == "abcde"); + VERIFY(p2.first->second == 3); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/1.cc new file mode 100644 index 00000000000..0aa1a071871 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/1.cc @@ -0,0 +1,129 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Mmap; + typedef Mmap::iterator iterator; + typedef Mmap::const_iterator const_iterator; + typedef Mmap::value_type value_type; + + Mmap mm1; + + mm1.insert(value_type("because to why", 1)); + mm1.insert(value_type("the stockholm syndrome", 2)); + mm1.insert(value_type("a cereous night", 3)); + mm1.insert(value_type("eeilo", 4)); + mm1.insert(value_type("protean", 5)); + mm1.insert(value_type("the way you are when", 6)); + mm1.insert(value_type("tillsammans", 7)); + mm1.insert(value_type("umbra/penumbra", 8)); + mm1.insert(value_type("belonging (no longer mix)", 9)); + mm1.insert(value_type("one line behind", 10)); + VERIFY( mm1.size() == 10 ); + + VERIFY( mm1.erase("eeilo") == 1 ); + VERIFY( mm1.size() == 9 ); + iterator it1 = mm1.find("eeilo"); + VERIFY( it1 == mm1.end() ); + + VERIFY( mm1.erase("tillsammans") == 1 ); + VERIFY( mm1.size() == 8 ); + iterator it2 = mm1.find("tillsammans"); + VERIFY( it2 == mm1.end() ); + + // Must work (see DR 526) + iterator it3 = mm1.find("belonging (no longer mix)"); + VERIFY( it3 != mm1.end() ); + VERIFY( mm1.erase(it3->first) == 1 ); + VERIFY( mm1.size() == 7 ); + it3 = mm1.find("belonging (no longer mix)"); + VERIFY( it3 == mm1.end() ); + + VERIFY( !mm1.erase("abra") ); + VERIFY( mm1.size() == 7 ); + + VERIFY( !mm1.erase("eeilo") ); + VERIFY( mm1.size() == 7 ); + + VERIFY( mm1.erase("because to why") == 1 ); + VERIFY( mm1.size() == 6 ); + iterator it4 = mm1.find("because to why"); + VERIFY( it4 == mm1.end() ); + + iterator it5 = mm1.find("umbra/penumbra"); + iterator it6 = mm1.find("one line behind"); + VERIFY( it5 != mm1.end() ); + VERIFY( it6 != mm1.end() ); + + VERIFY( mm1.find("the stockholm syndrome") != mm1.end() ); + VERIFY( mm1.find("a cereous night") != mm1.end() ); + VERIFY( mm1.find("the way you are when") != mm1.end() ); + VERIFY( mm1.find("a cereous night") != mm1.end() ); + + VERIFY( mm1.erase(it5->first) == 1 ); + VERIFY( mm1.size() == 5 ); + it5 = mm1.find("umbra/penumbra"); + VERIFY( it5 == mm1.end() ); + + VERIFY( mm1.erase(it6->first) == 1 ); + VERIFY( mm1.size() == 4 ); + it6 = mm1.find("one line behind"); + VERIFY( it6 == mm1.end() ); + + iterator it7 = mm1.begin(); + iterator it8 = it7; + ++it8; + iterator it9 = it8; + ++it9; + + VERIFY( mm1.erase(it8->first) == 1 ); + VERIFY( mm1.size() == 3 ); + VERIFY( ++it7 == it9 ); + + iterator it10 = it9; + ++it10; + iterator it11 = it10; + + VERIFY( mm1.erase(it9->first) == 1 ); + VERIFY( mm1.size() == 2 ); + VERIFY( ++it10 == mm1.end() ); + + VERIFY( mm1.erase(mm1.begin()) != mm1.end() ); + VERIFY( mm1.size() == 1 ); + VERIFY( mm1.begin() == it11 ); + + VERIFY( mm1.erase(mm1.begin()->first) == 1 ); + VERIFY( mm1.size() == 0 ); + VERIFY( mm1.begin() == mm1.end() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/24061-multimap.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/24061-multimap.cc new file mode 100644 index 00000000000..545d08278d6 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/24061-multimap.cc @@ -0,0 +1,108 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Mmap; + typedef Mmap::iterator iterator; + typedef Mmap::const_iterator const_iterator; + typedef Mmap::value_type value_type; + + Mmap mm1; + + mm1.insert(value_type("all the love in the world", 1)); + mm1.insert(value_type("you know what you are?", 2)); + mm1.insert(value_type("the collector", 3)); + mm1.insert(value_type("the hand that feeds", 4)); + mm1.insert(value_type("love is not enough", 5)); + mm1.insert(value_type("every day is exactly the same", 6)); + mm1.insert(value_type("with teeth", 7)); + mm1.insert(value_type("only", 8)); + mm1.insert(value_type("getting smaller", 9)); + mm1.insert(value_type("sunspots", 10)); + + mm1.insert(value_type("you know what you are?", 5)); + mm1.insert(value_type("the collector", 6)); + mm1.insert(value_type("the hand that feeds", 7)); + VERIFY( mm1.size() == 13 ); + + iterator it1 = mm1.begin(); + ++it1; + iterator it2 = it1; + ++it2; + iterator it3 = mm1.erase(it1); + VERIFY( mm1.size() == 12 ); + VERIFY( it3 == it2 ); + VERIFY( *it3 == *it2 ); + + iterator it4 = mm1.begin(); + ++it4; + ++it4; + ++it4; + iterator it5 = it4; + ++it5; + ++it5; + iterator it6 = mm1.erase(it4, it5); + VERIFY( mm1.size() == 10 ); + VERIFY( it6 == it5 ); + VERIFY( *it6 == *it5 ); + + const_iterator it7 = mm1.begin(); + ++it7; + ++it7; + ++it7; + const_iterator it8 = it7; + ++it8; + const_iterator it9 = mm1.erase(it7); + VERIFY( mm1.size() == 9 ); + VERIFY( it9 == it8 ); + VERIFY( *it9 == *it8 ); + + const_iterator it10 = mm1.begin(); + ++it10; + const_iterator it11 = it10; + ++it11; + ++it11; + ++it11; + ++it11; + const_iterator it12 = mm1.erase(it10, it11); + VERIFY( mm1.size() == 5 ); + VERIFY( it12 == it11 ); + VERIFY( *it12 == *it11 ); + + iterator it13 = mm1.erase(mm1.begin(), mm1.end()); + VERIFY( mm1.size() == 0 ); + VERIFY( it13 == mm1.end() ); + VERIFY( it13 == mm1.begin() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/24061-multimap.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/24061-multimap.cc new file mode 100644 index 00000000000..136580662f7 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/24061-multimap.cc @@ -0,0 +1,60 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Mmap; + typedef Mmap::iterator iterator; + typedef Mmap::const_iterator const_iterator; + typedef Mmap::value_type value_type; + + Mmap mm1; + + iterator it1 = mm1.insert(mm1.begin(), + value_type("all the love in the world", 1)); + VERIFY( mm1.size() == 1 ); + VERIFY( *it1 == value_type("all the love in the world", 1) ); + + const_iterator cit1(it1); + const_iterator cit2 = mm1.insert(cit1, + value_type("you know what you are?", 2)); + VERIFY( mm1.size() == 2 ); + VERIFY( cit2 != cit1 ); + VERIFY( *cit2 == value_type("you know what you are?", 2) ); + + iterator it2 = mm1.insert(it1, value_type("all the love in the world", 3)); + VERIFY( mm1.size() == 3 ); + VERIFY( it2 != it1 ); + VERIFY( *it2 == value_type("all the love in the world", 3) ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_range.cc new file mode 100644 index 00000000000..b7f405b763d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_range.cc @@ -0,0 +1,91 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// range insert + +#include +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + Pair A[5] = + { + Pair("red", 5), + Pair("green", 9), + Pair("blue", 3), + Pair("cyan", 8), + Pair("magenta", 7) + }; + + m.insert(A+0, A+5); + VERIFY(m.size() == 5); + VERIFY(std::distance(m.begin(), m.end()) == 5); + + for (int i = 0; i < 5; ++i) + VERIFY(std::find(m.begin(), m.end(), A[i]) != m.end()); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + Pair A[9] = + { + Pair("red", 5), + Pair("green", 9), + Pair("red", 19), + Pair("blue", 3), + Pair("blue", 60), + Pair("cyan", 8), + Pair("magenta", 7), + Pair("blue", 99), + Pair("green", 33) + }; + + m.insert(A+0, A+9); + VERIFY(m.size() == 9); + VERIFY(std::distance(m.begin(), m.end()) == 9); + + for (int i = 0; i < 9; ++i) + VERIFY(std::find(m.begin(), m.end(), A[i]) != m.end()); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_single.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_single.cc new file mode 100644 index 00000000000..1864098f582 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/multimap_single.cc @@ -0,0 +1,76 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Single-element insert + +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + Map::iterator i = m.insert(Pair("abcde", 3)); + VERIFY(m.size() == 1); + VERIFY(std::distance(m.begin(), m.end()) == 1); + VERIFY(i == m.begin()); + VERIFY(i->first == "abcde"); + VERIFY(i->second == 3); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + m.insert(Pair("abcde", 3)); + m.insert(Pair("abcde", 7)); + + VERIFY(m.size() == 2); + VERIFY(std::distance(m.begin(), m.end()) == 2); + + Map::iterator i1 = m.begin(); + Map::iterator i2 = i1; + ++i2; + + VERIFY(i1->first == "abcde"); + VERIFY(i2->first == "abcde"); + VERIFY((i1->second == 3 && i2->second == 7) || + (i1->second == 7 && i2->second == 3)); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc new file mode 100644 index 00000000000..9951838e9de --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc @@ -0,0 +1,128 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Mset; + typedef Mset::iterator iterator; + typedef Mset::const_iterator const_iterator; + + Mset ms1; + + ms1.insert("because to why"); + ms1.insert("the stockholm syndrome"); + ms1.insert("a cereous night"); + ms1.insert("eeilo"); + ms1.insert("protean"); + ms1.insert("the way you are when"); + ms1.insert("tillsammans"); + ms1.insert("umbra/penumbra"); + ms1.insert("belonging (no longer mix)"); + ms1.insert("one line behind"); + VERIFY( ms1.size() == 10 ); + + VERIFY( ms1.erase("eeilo") == 1 ); + VERIFY( ms1.size() == 9 ); + iterator it1 = ms1.find("eeilo"); + VERIFY( it1 == ms1.end() ); + + VERIFY( ms1.erase("tillsammans") == 1 ); + VERIFY( ms1.size() == 8 ); + iterator it2 = ms1.find("tillsammans"); + VERIFY( it2 == ms1.end() ); + + // Must work (see DR 526) + iterator it3 = ms1.find("belonging (no longer mix)"); + VERIFY( it3 != ms1.end() ); + VERIFY( ms1.erase(*it3) == 1 ); + VERIFY( ms1.size() == 7 ); + it3 = ms1.find("belonging (no longer mix)"); + VERIFY( it3 == ms1.end() ); + + VERIFY( !ms1.erase("abra") ); + VERIFY( ms1.size() == 7 ); + + VERIFY( !ms1.erase("eeilo") ); + VERIFY( ms1.size() == 7 ); + + VERIFY( ms1.erase("because to why") == 1 ); + VERIFY( ms1.size() == 6 ); + iterator it4 = ms1.find("because to why"); + VERIFY( it4 == ms1.end() ); + + iterator it5 = ms1.find("umbra/penumbra"); + iterator it6 = ms1.find("one line behind"); + VERIFY( it5 != ms1.end() ); + VERIFY( it6 != ms1.end() ); + + VERIFY( ms1.find("the stockholm syndrome") != ms1.end() ); + VERIFY( ms1.find("a cereous night") != ms1.end() ); + VERIFY( ms1.find("the way you are when") != ms1.end() ); + VERIFY( ms1.find("a cereous night") != ms1.end() ); + + VERIFY( ms1.erase(*it5) == 1 ); + VERIFY( ms1.size() == 5 ); + it5 = ms1.find("umbra/penumbra"); + VERIFY( it5 == ms1.end() ); + + VERIFY( ms1.erase(*it6) == 1 ); + VERIFY( ms1.size() == 4 ); + it6 = ms1.find("one line behind"); + VERIFY( it6 == ms1.end() ); + + iterator it7 = ms1.begin(); + iterator it8 = it7; + ++it8; + iterator it9 = it8; + ++it9; + + VERIFY( ms1.erase(*it8) == 1 ); + VERIFY( ms1.size() == 3 ); + VERIFY( ++it7 == it9 ); + + iterator it10 = it9; + ++it10; + iterator it11 = it10; + + VERIFY( ms1.erase(*it9) == 1 ); + VERIFY( ms1.size() == 2 ); + VERIFY( ++it10 == ms1.end() ); + + VERIFY( ms1.erase(ms1.begin()) != ms1.end() ); + VERIFY( ms1.size() == 1 ); + VERIFY( ms1.begin() == it11 ); + + VERIFY( ms1.erase(*ms1.begin()) == 1 ); + VERIFY( ms1.size() == 0 ); + VERIFY( ms1.begin() == ms1.end() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc new file mode 100644 index 00000000000..c5eea6eeebc --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc @@ -0,0 +1,107 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Mset; + typedef Mset::iterator iterator; + typedef Mset::const_iterator const_iterator; + + Mset ms1; + + ms1.insert("all the love in the world"); + ms1.insert("you know what you are?"); + ms1.insert("the collector"); + ms1.insert("the hand that feeds"); + ms1.insert("love is not enough"); + ms1.insert("every day is exactly the same"); + ms1.insert("with teeth"); + ms1.insert("only"); + ms1.insert("getting smaller"); + ms1.insert("sunspots"); + + ms1.insert("the hand that feeds"); + ms1.insert("love is not enough"); + ms1.insert("every day is exactly the same"); + VERIFY( ms1.size() == 13 ); + + iterator it1 = ms1.begin(); + ++it1; + iterator it2 = it1; + ++it2; + iterator it3 = ms1.erase(it1); + VERIFY( ms1.size() == 12 ); + VERIFY( it3 == it2 ); + VERIFY( *it3 == *it2 ); + + iterator it4 = ms1.begin(); + ++it4; + ++it4; + ++it4; + iterator it5 = it4; + ++it5; + ++it5; + iterator it6 = ms1.erase(it4, it5); + VERIFY( ms1.size() == 10 ); + VERIFY( it6 == it5 ); + VERIFY( *it6 == *it5 ); + + const_iterator it7 = ms1.begin(); + ++it7; + ++it7; + ++it7; + const_iterator it8 = it7; + ++it8; + const_iterator it9 = ms1.erase(it7); + VERIFY( ms1.size() == 9 ); + VERIFY( it9 == it8 ); + VERIFY( *it9 == *it8 ); + + const_iterator it10 = ms1.begin(); + ++it10; + const_iterator it11 = it10; + ++it11; + ++it11; + ++it11; + ++it11; + const_iterator it12 = ms1.erase(it10, it11); + VERIFY( ms1.size() == 5 ); + VERIFY( it12 == it11 ); + VERIFY( *it12 == *it11 ); + + iterator it13 = ms1.erase(ms1.begin(), ms1.end()); + VERIFY( ms1.size() == 0 ); + VERIFY( it13 == ms1.end() ); + VERIFY( it13 == ms1.begin() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/24061-multiset.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/24061-multiset.cc new file mode 100644 index 00000000000..6d8b34d3e8c --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/24061-multiset.cc @@ -0,0 +1,57 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Mset; + typedef Mset::iterator iterator; + typedef Mset::const_iterator const_iterator; + + Mset ms1; + + iterator it1 = ms1.insert(ms1.begin(), "all the love in the world"); + VERIFY( ms1.size() == 1 ); + VERIFY( *it1 == "all the love in the world" ); + + const_iterator cit1(it1); + const_iterator cit2 = ms1.insert(cit1, "you know what you are?"); + VERIFY( ms1.size() == 2 ); + VERIFY( cit2 != cit1 ); + VERIFY( *cit2 == "you know what you are?" ); + + iterator it2 = ms1.insert(it1, "all the love in the world"); + VERIFY( ms1.size() == 3 ); + VERIFY( it2 != it1 ); + VERIFY( *it2 == "all the love in the world" ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_range.cc new file mode 100644 index 00000000000..571346fd5c2 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_range.cc @@ -0,0 +1,79 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// range insert + +#include +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Set; + Set s; + VERIFY(s.empty()); + + const int N = 10; + const std::string A[N] = { "red", "green", "blue", "violet", "cyan", + "magenta", "yellow", "orange", "pink", "gray" }; + + s.insert(A+0, A+N); + VERIFY(s.size() == static_cast(N)); + VERIFY(std::distance(s.begin(), s.end()) == N); + + for (int i = 0; i < N; ++i) { + std::string str = A[i]; + Set::iterator it = std::find(s.begin(), s.end(), str); + VERIFY(it != s.end()); + } +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Set; + Set s; + VERIFY(s.empty()); + + const int N = 8; + const int A[N] = { 3, 7, 4, 8, 2, 4, 6, 7 }; + + s.insert(A+0, A+N); + VERIFY(s.size() == static_cast(N)); + VERIFY(std::distance(s.begin(), s.end()) == N); + + VERIFY(std::count(s.begin(), s.end(), 2) == 1); + VERIFY(std::count(s.begin(), s.end(), 3) == 1); + VERIFY(std::count(s.begin(), s.end(), 4) == 2); + VERIFY(std::count(s.begin(), s.end(), 6) == 1); + VERIFY(std::count(s.begin(), s.end(), 7) == 2); + VERIFY(std::count(s.begin(), s.end(), 8) == 1); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single.cc new file mode 100644 index 00000000000..f275e9a9bdd --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single.cc @@ -0,0 +1,67 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Single-element insert + +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Set; + Set s; + VERIFY(s.empty()); + + Set::iterator i = s.insert("abcde"); + VERIFY(s.size() == 1); + VERIFY(std::distance(s.begin(), s.end()) == 1); + VERIFY(i == s.begin()); + VERIFY(*i == "abcde"); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multiset Set; + Set s; + VERIFY(s.empty()); + + s.insert("abcde"); + Set::iterator i = s.insert("abcde"); + VERIFY(s.size() == 2); + VERIFY(std::distance(s.begin(), s.end()) == 2); + VERIFY(*i == "abcde"); + + Set::iterator i2 = s.begin(); + ++i2; + VERIFY(i == s.begin() || i == i2); + VERIFY(*(s.begin()) == "abcde" && *i2 == "abcde"); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/erase/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/erase/1.cc new file mode 100644 index 00000000000..8f59773d802 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/erase/1.cc @@ -0,0 +1,128 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_set Set; + typedef Set::iterator iterator; + typedef Set::const_iterator const_iterator; + + Set s1; + + s1.insert("because to why"); + s1.insert("the stockholm syndrome"); + s1.insert("a cereous night"); + s1.insert("eeilo"); + s1.insert("protean"); + s1.insert("the way you are when"); + s1.insert("tillsammans"); + s1.insert("umbra/penumbra"); + s1.insert("belonging (no longer mix)"); + s1.insert("one line behind"); + VERIFY( s1.size() == 10 ); + + VERIFY( s1.erase("eeilo") == 1 ); + VERIFY( s1.size() == 9 ); + iterator it1 = s1.find("eeilo"); + VERIFY( it1 == s1.end() ); + + VERIFY( s1.erase("tillsammans") == 1 ); + VERIFY( s1.size() == 8 ); + iterator it2 = s1.find("tillsammans"); + VERIFY( it2 == s1.end() ); + + // Must work (see DR 526) + iterator it3 = s1.find("belonging (no longer mix)"); + VERIFY( it3 != s1.end() ); + VERIFY( s1.erase(*it3) == 1 ); + VERIFY( s1.size() == 7 ); + it3 = s1.find("belonging (no longer mix)"); + VERIFY( it3 == s1.end() ); + + VERIFY( !s1.erase("abra") ); + VERIFY( s1.size() == 7 ); + + VERIFY( !s1.erase("eeilo") ); + VERIFY( s1.size() == 7 ); + + VERIFY( s1.erase("because to why") == 1 ); + VERIFY( s1.size() == 6 ); + iterator it4 = s1.find("because to why"); + VERIFY( it4 == s1.end() ); + + iterator it5 = s1.find("umbra/penumbra"); + iterator it6 = s1.find("one line behind"); + VERIFY( it5 != s1.end() ); + VERIFY( it6 != s1.end() ); + + VERIFY( s1.find("the stockholm syndrome") != s1.end() ); + VERIFY( s1.find("a cereous night") != s1.end() ); + VERIFY( s1.find("the way you are when") != s1.end() ); + VERIFY( s1.find("a cereous night") != s1.end() ); + + VERIFY( s1.erase(*it5) == 1 ); + VERIFY( s1.size() == 5 ); + it5 = s1.find("umbra/penumbra"); + VERIFY( it5 == s1.end() ); + + VERIFY( s1.erase(*it6) == 1 ); + VERIFY( s1.size() == 4 ); + it6 = s1.find("one line behind"); + VERIFY( it6 == s1.end() ); + + iterator it7 = s1.begin(); + iterator it8 = it7; + ++it8; + iterator it9 = it8; + ++it9; + + VERIFY( s1.erase(*it8) == 1 ); + VERIFY( s1.size() == 3 ); + VERIFY( ++it7 == it9 ); + + iterator it10 = it9; + ++it10; + iterator it11 = it10; + + VERIFY( s1.erase(*it9) == 1 ); + VERIFY( s1.size() == 2 ); + VERIFY( ++it10 == s1.end() ); + + VERIFY( s1.erase(s1.begin()) != s1.end() ); + VERIFY( s1.size() == 1 ); + VERIFY( s1.begin() == it11 ); + + VERIFY( s1.erase(*s1.begin()) == 1 ); + VERIFY( s1.size() == 0 ); + VERIFY( s1.begin() == s1.end() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/erase/24061-set.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/erase/24061-set.cc new file mode 100644 index 00000000000..b4cdde62d57 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/erase/24061-set.cc @@ -0,0 +1,104 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_set Set; + typedef Set::iterator iterator; + typedef Set::const_iterator const_iterator; + + Set s1; + + s1.insert("all the love in the world"); + s1.insert("you know what you are?"); + s1.insert("the collector"); + s1.insert("the hand that feeds"); + s1.insert("love is not enough"); + s1.insert("every day is exactly the same"); + s1.insert("with teeth"); + s1.insert("only"); + s1.insert("getting smaller"); + s1.insert("sunspots"); + VERIFY( s1.size() == 10 ); + + iterator it1 = s1.begin(); + ++it1; + iterator it2 = it1; + ++it2; + iterator it3 = s1.erase(it1); + VERIFY( s1.size() == 9 ); + VERIFY( it3 == it2 ); + VERIFY( *it3 == *it2 ); + + iterator it4 = s1.begin(); + ++it4; + ++it4; + ++it4; + iterator it5 = it4; + ++it5; + ++it5; + iterator it6 = s1.erase(it4, it5); + VERIFY( s1.size() == 7 ); + VERIFY( it6 == it5 ); + VERIFY( *it6 == *it5 ); + + const_iterator it7 = s1.begin(); + ++it7; + ++it7; + ++it7; + const_iterator it8 = it7; + ++it8; + const_iterator it9 = s1.erase(it7); + VERIFY( s1.size() == 6 ); + VERIFY( it9 == it8 ); + VERIFY( *it9 == *it8 ); + + const_iterator it10 = s1.begin(); + ++it10; + const_iterator it11 = it10; + ++it11; + ++it11; + ++it11; + ++it11; + const_iterator it12 = s1.erase(it10, it11); + VERIFY( s1.size() == 2 ); + VERIFY( it12 == it11 ); + VERIFY( *it12 == *it11 ); + VERIFY( ++it12 == s1.end() ); + + iterator it13 = s1.erase(s1.begin(), s1.end()); + VERIFY( s1.size() == 0 ); + VERIFY( it13 == s1.end() ); + VERIFY( it13 == s1.begin() ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/24061-set.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/24061-set.cc new file mode 100644 index 00000000000..54add351282 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/24061-set.cc @@ -0,0 +1,57 @@ +// { dg-options "-std=gnu++0x" } + +// 2010-02-10 Paolo Carlini +// +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +// libstdc++/24061 +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_set Set; + typedef Set::iterator iterator; + typedef Set::const_iterator const_iterator; + + Set s1; + + iterator it1 = s1.insert(s1.begin(), "all the love in the world"); + VERIFY( s1.size() == 1 ); + VERIFY( *it1 == "all the love in the world" ); + + const_iterator cit1(it1); + const_iterator cit2 = s1.insert(cit1, "you know what you are?"); + VERIFY( s1.size() == 2 ); + VERIFY( cit2 != cit1 ); + VERIFY( *cit2 == "you know what you are?" ); + + iterator it2 = s1.insert(it1, "all the love in the world"); + VERIFY( s1.size() == 2 ); + VERIFY( it2 == it1 ); + VERIFY( *it2 == "all the love in the world" ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_range.cc new file mode 100644 index 00000000000..86bd326bde4 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_range.cc @@ -0,0 +1,77 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// range insert + +#include +#include +#include +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::unordered_set Set; + Set s; + VERIFY(s.empty()); + + const int N = 10; + const std::string A[N] = { "red", "green", "blue", "violet", "cyan", + "magenta", "yellow", "orange", "pink", "gray" }; + + s.insert(A+0, A+N); + VERIFY(s.size() == static_cast(N)); + VERIFY(std::distance(s.begin(), s.end()) == N); + + for (int i = 0; i < N; ++i) { + std::string str = A[i]; + Set::iterator it = std::find(s.begin(), s.end(), str); + VERIFY(it != s.end()); + } +} + +void test02() +{ + typedef std::unordered_set Set; + Set s; + VERIFY(s.empty()); + + const int N = 8; + const int A[N] = { 3, 7, 4, 8, 2, 4, 6, 7 }; + + s.insert(A+0, A+N); + VERIFY(s.size() == 6); + VERIFY(std::distance(s.begin(), s.end()) == 6); + + VERIFY(std::count(s.begin(), s.end(), 2) == 1); + VERIFY(std::count(s.begin(), s.end(), 3) == 1); + VERIFY(std::count(s.begin(), s.end(), 4) == 1); + VERIFY(std::count(s.begin(), s.end(), 6) == 1); + VERIFY(std::count(s.begin(), s.end(), 7) == 1); + VERIFY(std::count(s.begin(), s.end(), 8) == 1); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_single.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_single.cc new file mode 100644 index 00000000000..d1288ce4255 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/set_single.cc @@ -0,0 +1,65 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2010 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Single-element insert + +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_set Set; + Set s; + VERIFY(s.empty()); + + std::pair p = s.insert("abcde"); + VERIFY(p.second); + VERIFY(s.size() == 1); + VERIFY(std::distance(s.begin(), s.end()) == 1); + VERIFY(p.first == s.begin()); + VERIFY(*p.first == "abcde"); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_set Set; + Set s; + VERIFY(s.empty()); + + std::pair p1 = s.insert("abcde"); + std::pair p2 = s.insert("abcde"); + VERIFY(p1.second); + VERIFY(!p2.second); + VERIFY(s.size() == 1); + VERIFY(p1.first == p2.first); + VERIFY(*p1.first == "abcde"); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/exception/safety.h b/libstdc++-v3/testsuite/util/exception/safety.h index 4be53185b8e..23862bcdbee 100644 --- a/libstdc++-v3/testsuite/util/exception/safety.h +++ b/libstdc++-v3/testsuite/util/exception/safety.h @@ -275,6 +275,78 @@ namespace __gnu_test _F_erase_range(&container_type::erase_after) { } }; + // Specializations for the unordered containers. + template + struct erase_base> + { + typedef std::unordered_map<_Tp1, _Tp2, _Tp3, _Tp4, _Tp5> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + + iterator (container_type::* _F_erase_point)(const_iterator); + iterator (container_type::* _F_erase_range)(const_iterator, + const_iterator); + + erase_base() + : _F_erase_point(&container_type::erase), + _F_erase_range(&container_type::erase) { } + }; + + template + struct erase_base> + { + typedef std::unordered_multimap<_Tp1, _Tp2, _Tp3, _Tp4, _Tp5> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + + iterator (container_type::* _F_erase_point)(const_iterator); + iterator (container_type::* _F_erase_range)(const_iterator, + const_iterator); + + erase_base() + : _F_erase_point(&container_type::erase), + _F_erase_range(&container_type::erase) { } + }; + + template + struct erase_base> + { + typedef std::unordered_set<_Tp1, _Tp2, _Tp3, _Tp4> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + + iterator (container_type::* _F_erase_point)(const_iterator); + iterator (container_type::* _F_erase_range)(const_iterator, + const_iterator); + + erase_base() + : _F_erase_point(&container_type::erase), + _F_erase_range(&container_type::erase) { } + }; + + template + struct erase_base> + { + typedef std::unordered_multiset<_Tp1, _Tp2, _Tp3, _Tp4> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + + iterator (container_type::* _F_erase_point)(const_iterator); + iterator (container_type::* _F_erase_range)(const_iterator, + const_iterator); + + erase_base() + : _F_erase_point(&container_type::erase), + _F_erase_range(&container_type::erase) { } + }; + template::has_erase::value> struct erase_point : public erase_base<_Tp> { @@ -532,15 +604,79 @@ namespace __gnu_test { typedef std::forward_list<_Tp1, _Tp2> container_type; typedef typename container_type::iterator iterator; - typedef typename container_type::const_iterator const_iterator; + typedef typename container_type::const_iterator const_iterator; typedef typename container_type::value_type value_type; iterator (container_type::* _F_insert_point)(const_iterator, - const value_type&); + const value_type&); insert_base() : _F_insert_point(&container_type::insert_after) { } }; + // Likewise for the unordered containers. + template + struct insert_base> + { + typedef std::unordered_map<_Tp1, _Tp2, _Tp3, _Tp4, _Tp5> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + typedef typename container_type::value_type value_type; + + iterator (container_type::* _F_insert_point)(const_iterator, + const value_type&); + + insert_base() : _F_insert_point(&container_type::insert) { } + }; + + template + struct insert_base> + { + typedef std::unordered_multimap<_Tp1, _Tp2, _Tp3, _Tp4, _Tp5> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + typedef typename container_type::value_type value_type; + + iterator (container_type::* _F_insert_point)(const_iterator, + const value_type&); + + insert_base() : _F_insert_point(&container_type::insert) { } + }; + + template + struct insert_base> + { + typedef std::unordered_set<_Tp1, _Tp2, _Tp3, _Tp4> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + typedef typename container_type::value_type value_type; + + iterator (container_type::* _F_insert_point)(const_iterator, + const value_type&); + + insert_base() : _F_insert_point(&container_type::insert) { } + }; + + template + struct insert_base> + { + typedef std::unordered_multiset<_Tp1, _Tp2, _Tp3, _Tp4> + container_type; + typedef typename container_type::iterator iterator; + typedef typename container_type::const_iterator const_iterator; + typedef typename container_type::value_type value_type; + + iterator (container_type::* _F_insert_point)(const_iterator, + const value_type&); + + insert_base() : _F_insert_point(&container_type::insert) { } + }; + template::has_insert::value> struct insert_point : public insert_base<_Tp> { -- 2.11.0