OSDN Git Service

2011-11-23 Fran├žois Dumont <fdumont@gcc.gnu.org>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / unordered_map.h
1 // unordered_map implementation -*- C++ -*-
2
3 // Copyright (C) 2010, 2011 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file bits/unordered_map.h
26  *  This is an internal header file, included by other library headers.
27  *  Do not attempt to use it directly. @headername{unordered_map}
28  */
29
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
32
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36
37   // NB: When we get typedef templates these class definitions
38   // will be unnecessary.
39   template<class _Key, class _Tp,
40            class _Hash = hash<_Key>,
41            class _Pred = std::equal_to<_Key>,
42            class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
43            bool __cache_hash_code =
44              __not_<__and_<is_integral<_Key>,
45                            __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
46     class __unordered_map
47     : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
48                         std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 
49                         _Hash, __detail::_Mod_range_hashing,
50                         __detail::_Default_ranged_hash,
51                         __detail::_Prime_rehash_policy,
52                         __cache_hash_code, false, true>
53     {
54       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
55                          std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
56                          _Hash, __detail::_Mod_range_hashing,
57                          __detail::_Default_ranged_hash,
58                          __detail::_Prime_rehash_policy,
59                          __cache_hash_code, false, true>
60         _Base;
61
62     public:
63       typedef typename _Base::value_type      value_type;
64       typedef typename _Base::size_type       size_type;
65       typedef typename _Base::hasher          hasher;
66       typedef typename _Base::key_equal       key_equal;
67       typedef typename _Base::allocator_type  allocator_type;
68
69       explicit
70       __unordered_map(size_type __n = 10,
71                       const hasher& __hf = hasher(),
72                       const key_equal& __eql = key_equal(),
73                       const allocator_type& __a = allocator_type())
74       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
75               __detail::_Default_ranged_hash(),
76               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
77       { }
78
79       template<typename _InputIterator>
80         __unordered_map(_InputIterator __f, _InputIterator __l, 
81                         size_type __n = 0,
82                         const hasher& __hf = hasher(), 
83                         const key_equal& __eql = key_equal(), 
84                         const allocator_type& __a = allocator_type())
85         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
86                 __detail::_Default_ranged_hash(),
87                 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
88         { }
89
90       __unordered_map(initializer_list<value_type> __l,
91                       size_type __n = 0,
92                       const hasher& __hf = hasher(),
93                       const key_equal& __eql = key_equal(),
94                       const allocator_type& __a = allocator_type())
95       : _Base(__l.begin(), __l.end(), __n, __hf,
96               __detail::_Mod_range_hashing(),
97               __detail::_Default_ranged_hash(),
98               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
99       { }
100
101       __unordered_map&
102       operator=(initializer_list<value_type> __l)
103       {
104         this->clear();
105         this->insert(__l.begin(), __l.end());
106         return *this;
107       }
108     };
109   
110   template<class _Key, class _Tp,
111            class _Hash = hash<_Key>,
112            class _Pred = std::equal_to<_Key>,
113            class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
114            bool __cache_hash_code =
115              __not_<__and_<is_integral<_Key>,
116                            __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
117     class __unordered_multimap
118     : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
119                         _Alloc,
120                         std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
121                         _Hash, __detail::_Mod_range_hashing,
122                         __detail::_Default_ranged_hash,
123                         __detail::_Prime_rehash_policy,
124                         __cache_hash_code, false, false>
125     {
126       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
127                          _Alloc,
128                          std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
129                          _Hash, __detail::_Mod_range_hashing,
130                          __detail::_Default_ranged_hash,
131                          __detail::_Prime_rehash_policy,
132                          __cache_hash_code, false, false>
133         _Base;
134
135     public:
136       typedef typename _Base::value_type      value_type;
137       typedef typename _Base::size_type       size_type;
138       typedef typename _Base::hasher          hasher;
139       typedef typename _Base::key_equal       key_equal;
140       typedef typename _Base::allocator_type  allocator_type;
141       
142       explicit
143       __unordered_multimap(size_type __n = 10,
144                            const hasher& __hf = hasher(),
145                            const key_equal& __eql = key_equal(),
146                            const allocator_type& __a = allocator_type())
147       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
148               __detail::_Default_ranged_hash(),
149               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
150       { }
151
152
153       template<typename _InputIterator>
154         __unordered_multimap(_InputIterator __f, _InputIterator __l, 
155                              size_type __n = 0,
156                              const hasher& __hf = hasher(), 
157                              const key_equal& __eql = key_equal(), 
158                              const allocator_type& __a = allocator_type())
159         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
160                 __detail::_Default_ranged_hash(),
161                 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
162         { }
163
164       __unordered_multimap(initializer_list<value_type> __l,
165                            size_type __n = 0,
166                            const hasher& __hf = hasher(),
167                            const key_equal& __eql = key_equal(),
168                            const allocator_type& __a = allocator_type())
169       : _Base(__l.begin(), __l.end(), __n, __hf,
170               __detail::_Mod_range_hashing(),
171               __detail::_Default_ranged_hash(),
172               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
173       { }
174
175       __unordered_multimap&
176       operator=(initializer_list<value_type> __l)
177       {
178         this->clear();
179         this->insert(__l.begin(), __l.end());
180         return *this;
181       }
182     };
183
184   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
185            bool __cache_hash_code>
186     inline void
187     swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
188          _Alloc, __cache_hash_code>& __x,
189          __unordered_map<_Key, _Tp, _Hash, _Pred,
190          _Alloc, __cache_hash_code>& __y)
191     { __x.swap(__y); }
192
193   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
194            bool __cache_hash_code>
195     inline void
196     swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
197          _Alloc, __cache_hash_code>& __x,
198          __unordered_multimap<_Key, _Tp, _Hash, _Pred,
199          _Alloc, __cache_hash_code>& __y)
200     { __x.swap(__y); }
201
202   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
203            bool __cache_hash_code>
204     inline bool
205     operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
206                __cache_hash_code>& __x,
207                const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
208                __cache_hash_code>& __y)
209     { return __x._M_equal(__y); }
210
211   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
212            bool __cache_hash_code>
213     inline bool
214     operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
215                __cache_hash_code>& __x,
216                const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
217                __cache_hash_code>& __y)
218     { return !(__x == __y); }
219
220   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
221            bool __cache_hash_code>
222     inline bool
223     operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
224                __cache_hash_code>& __x,
225                const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
226                __cache_hash_code>& __y)
227     { return __x._M_equal(__y); }
228
229   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
230            bool __cache_hash_code>
231     inline bool
232     operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
233                __cache_hash_code>& __x,
234                const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
235                __cache_hash_code>& __y)
236     { return !(__x == __y); }
237
238   /**
239    *  @brief A standard container composed of unique keys (containing
240    *  at most one of each key value) that associates values of another type
241    *  with the keys.
242    *
243    *  @ingroup unordered_associative_containers
244    *
245    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
246    *  <a href="tables.html#xx">unordered associative container</a>
247    *
248    *  @param  Key  Type of key objects.
249    *  @param  Tp  Type of mapped objects.
250    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
251    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
252    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
253    *
254    * The resulting value type of the container is std::pair<const Key, Tp>.
255    */
256   template<class _Key, class _Tp,
257            class _Hash = hash<_Key>,
258            class _Pred = std::equal_to<_Key>,
259            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
260     class unordered_map
261     : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
262     {
263       typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
264
265     public:
266       typedef typename _Base::value_type      value_type;
267       typedef typename _Base::size_type       size_type;
268       typedef typename _Base::hasher          hasher;
269       typedef typename _Base::key_equal       key_equal;
270       typedef typename _Base::allocator_type  allocator_type;
271
272       explicit
273       unordered_map(size_type __n = 10,
274                     const hasher& __hf = hasher(),
275                     const key_equal& __eql = key_equal(),
276                     const allocator_type& __a = allocator_type())
277       : _Base(__n, __hf, __eql, __a)
278       { }
279
280       template<typename _InputIterator>
281         unordered_map(_InputIterator __f, _InputIterator __l, 
282                       size_type __n = 0,
283                       const hasher& __hf = hasher(), 
284                       const key_equal& __eql = key_equal(), 
285                       const allocator_type& __a = allocator_type())
286         : _Base(__f, __l, __n, __hf, __eql, __a)
287         { }
288
289       unordered_map(initializer_list<value_type> __l,
290                     size_type __n = 0,
291                     const hasher& __hf = hasher(),
292                     const key_equal& __eql = key_equal(),
293                     const allocator_type& __a = allocator_type())
294       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
295       { }
296
297       unordered_map&
298       operator=(initializer_list<value_type> __l)
299       {
300         this->clear();
301         this->insert(__l.begin(), __l.end());
302         return *this;
303       }
304     };
305   
306   /**
307    *  @brief A standard container composed of equivalent keys
308    *  (possibly containing multiple of each key value) that associates
309    *  values of another type with the keys.
310    *
311    *  @ingroup unordered_associative_containers
312    *
313    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
314    *  <a href="tables.html#xx">unordered associative container</a>
315    *
316    *  @param  Key  Type of key objects.
317    *  @param  Tp  Type of mapped objects.
318    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
319    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
320    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
321    *
322    * The resulting value type of the container is std::pair<const Key, Tp>.
323    */
324   template<class _Key, class _Tp,
325            class _Hash = hash<_Key>,
326            class _Pred = std::equal_to<_Key>,
327            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
328     class unordered_multimap
329     : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
330     {
331       typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
332
333     public:
334       typedef typename _Base::value_type      value_type;
335       typedef typename _Base::size_type       size_type;
336       typedef typename _Base::hasher          hasher;
337       typedef typename _Base::key_equal       key_equal;
338       typedef typename _Base::allocator_type  allocator_type;
339       
340       explicit
341       unordered_multimap(size_type __n = 10,
342                          const hasher& __hf = hasher(),
343                          const key_equal& __eql = key_equal(),
344                          const allocator_type& __a = allocator_type())
345       : _Base(__n, __hf, __eql, __a)
346       { }
347
348       template<typename _InputIterator>
349         unordered_multimap(_InputIterator __f, _InputIterator __l, 
350                            size_type __n = 0,
351                            const hasher& __hf = hasher(), 
352                            const key_equal& __eql = key_equal(), 
353                            const allocator_type& __a = allocator_type())
354         : _Base(__f, __l, __n, __hf, __eql, __a)
355         { }
356
357       unordered_multimap(initializer_list<value_type> __l,
358                          size_type __n = 0,
359                          const hasher& __hf = hasher(),
360                          const key_equal& __eql = key_equal(),
361                          const allocator_type& __a = allocator_type())
362       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
363       { }
364
365       unordered_multimap&
366       operator=(initializer_list<value_type> __l)
367       {
368         this->clear();
369         this->insert(__l.begin(), __l.end());
370         return *this;
371       }
372     };
373
374   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
375     inline void
376     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
377          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
378     { __x.swap(__y); }
379
380   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
381     inline void
382     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
383          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
384     { __x.swap(__y); }
385
386   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
387     inline bool
388     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
389                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
390     { return __x._M_equal(__y); }
391
392   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
393     inline bool
394     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
395                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
396     { return !(__x == __y); }
397
398   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
399     inline bool
400     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
401                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
402     { return __x._M_equal(__y); }
403
404   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
405     inline bool
406     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
407                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
408     { return !(__x == __y); }
409
410 _GLIBCXX_END_NAMESPACE_CONTAINER
411 } // namespace std
412
413 #endif /* _UNORDERED_MAP_H */