libstdc++
types_traits.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2018 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 terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // 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 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file detail/types_traits.hpp
38  * Contains a traits class of types used by containers.
39  */
40 
41 #ifndef PB_DS_TYPES_TRAITS_HPP
42 #define PB_DS_TYPES_TRAITS_HPP
43 
44 #include <algorithm>
45 #include <utility>
46 #include <ext/pb_ds/tag_and_trait.hpp>
47 #include <ext/pb_ds/detail/type_utils.hpp>
48 #include <utility>
49 
50 namespace __gnu_pbds
51 {
52  namespace detail
53  {
54  /**
55  * @addtogroup traits Traits
56  * @{
57  */
58 
59  /// Primary template.
60  template<typename Key, typename Mapped>
61  struct no_throw_copies
62  {
63  static const bool __simple = is_simple<Key>::value
64  && is_simple<Mapped>::value;
65  typedef integral_constant<int, __simple> indicator;
66  };
67 
68  /// Specialization.
69  template<typename Key>
70  struct no_throw_copies<Key, null_type>
71  {
72  typedef integral_constant<int, is_simple<Key>::value> indicator;
73  };
74 
75 
76  /// Stored value.
77  template<typename _Tv>
78  struct stored_value
79  {
80  typedef _Tv value_type;
81  value_type m_value;
82  };
83 
84  /// Stored hash.
85  template<typename _Th>
86  struct stored_hash
87  {
88  typedef _Th hash_type;
89  hash_type m_hash;
90  };
91 
92  /// Primary template for representation of stored data.
93  /// Two types of data can be stored: value and hash.
94  template<typename _Tv, typename _Th>
95  struct stored_data
96  : public stored_value<_Tv>, public stored_hash<_Th>
97  { };
98 
99  /// Specialization for representation of stored data of just value type.
100  template<typename _Tv>
101  struct stored_data<_Tv, null_type>
102  : public stored_value<_Tv>
103  { };
104 
105  /// Primary template.
106  template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
107  struct type_base;
108 
109  /**
110  * Specialization of type_base for the case where the hash value
111  * is not stored alongside each value.
112  */
113  template<typename Key, typename Mapped, typename _Alloc>
114  struct type_base<Key, Mapped, _Alloc, false>
115  {
116  public:
117  typedef typename _Alloc::size_type size_type;
118 
119  private:
120  typedef typename _Alloc::template rebind<Mapped> __rebind_m;
121  typedef typename __rebind_m::other __rebind_ma;
122  typedef std::pair<const Key, Mapped> __value_type;
123  typedef typename _Alloc::template rebind<__value_type> __rebind_v;
124  typedef typename __rebind_v::other __rebind_va;
125 
126  public:
127  typedef typename __rebind_ma::value_type mapped_type;
128  typedef typename __rebind_ma::pointer mapped_pointer;
129  typedef typename __rebind_ma::const_pointer mapped_const_pointer;
130  typedef typename __rebind_ma::reference mapped_reference;
131  typedef typename __rebind_ma::const_reference mapped_const_reference;
132 
133  typedef typename __rebind_va::value_type value_type;
134  typedef typename __rebind_va::pointer pointer;
135  typedef typename __rebind_va::const_pointer const_pointer;
136  typedef typename __rebind_va::reference reference;
137  typedef typename __rebind_va::const_reference const_reference;
138 
139  typedef stored_data<value_type, null_type> stored_data_type;
140  };
141 
142  /**
143  * Specialization of type_base for the case where the hash value
144  * is stored alongside each value.
145  */
146  template<typename Key, typename Mapped, typename _Alloc>
147  struct type_base<Key, Mapped, _Alloc, true>
148  {
149  public:
150  typedef typename _Alloc::size_type size_type;
151 
152  private:
153  typedef typename _Alloc::template rebind<Mapped> __rebind_m;
154  typedef typename __rebind_m::other __rebind_ma;
155  typedef std::pair<const Key, Mapped> __value_type;
156  typedef typename _Alloc::template rebind<__value_type> __rebind_v;
157  typedef typename __rebind_v::other __rebind_va;
158 
159  public:
160  typedef typename __rebind_ma::value_type mapped_type;
161  typedef typename __rebind_ma::pointer mapped_pointer;
162  typedef typename __rebind_ma::const_pointer mapped_const_pointer;
163  typedef typename __rebind_ma::reference mapped_reference;
164  typedef typename __rebind_ma::const_reference mapped_const_reference;
165 
166  typedef typename __rebind_va::value_type value_type;
167  typedef typename __rebind_va::pointer pointer;
168  typedef typename __rebind_va::const_pointer const_pointer;
169  typedef typename __rebind_va::reference reference;
170  typedef typename __rebind_va::const_reference const_reference;
171 
172  typedef stored_data<value_type, size_type> stored_data_type;
173  };
174 
175 
176  /**
177  * Specialization of type_base for the case where the hash value
178  * is not stored alongside each value.
179  */
180  template<typename Key, typename _Alloc>
181  struct type_base<Key, null_type, _Alloc, false>
182  {
183  public:
184  typedef typename _Alloc::size_type size_type;
185  typedef Key value_type;
186 
187  private:
188  typedef typename _Alloc::template rebind<null_type> __rebind_m;
189  typedef typename __rebind_m::other __rebind_ma;
190  typedef typename _Alloc::template rebind<value_type> __rebind_v;
191  typedef typename __rebind_v::other __rebind_va;
192 
193  public:
194  typedef typename __rebind_ma::value_type mapped_type;
195  typedef typename __rebind_ma::pointer mapped_pointer;
196  typedef typename __rebind_ma::const_pointer mapped_const_pointer;
197  typedef typename __rebind_ma::reference mapped_reference;
198  typedef typename __rebind_ma::const_reference mapped_const_reference;
199 
200  typedef typename __rebind_va::pointer pointer;
201  typedef typename __rebind_va::const_pointer const_pointer;
202  typedef typename __rebind_va::reference reference;
203  typedef typename __rebind_va::const_reference const_reference;
204 
205  typedef stored_data<value_type, null_type> stored_data_type;
206 
207  static null_type s_null_type;
208  };
209 
210  template<typename Key, typename _Alloc>
211  null_type
212  type_base<Key, null_type, _Alloc, false>::s_null_type;
213 
214 
215  /**
216  * Specialization of type_base for the case where the hash value
217  * is stored alongside each value.
218  */
219  template<typename Key, typename _Alloc>
220  struct type_base<Key, null_type, _Alloc, true>
221  {
222  public:
223  typedef typename _Alloc::size_type size_type;
224  typedef Key value_type;
225 
226  private:
227  typedef typename _Alloc::template rebind<null_type> __rebind_m;
228  typedef typename __rebind_m::other __rebind_ma;
229  typedef typename _Alloc::template rebind<value_type> __rebind_v;
230  typedef typename __rebind_v::other __rebind_va;
231 
232  public:
233  typedef typename __rebind_ma::value_type mapped_type;
234  typedef typename __rebind_ma::pointer mapped_pointer;
235  typedef typename __rebind_ma::const_pointer mapped_const_pointer;
236  typedef typename __rebind_ma::reference mapped_reference;
237  typedef typename __rebind_ma::const_reference mapped_const_reference;
238 
239  typedef typename __rebind_va::pointer pointer;
240  typedef typename __rebind_va::const_pointer const_pointer;
241  typedef typename __rebind_va::reference reference;
242  typedef typename __rebind_va::const_reference const_reference;
243 
244  typedef stored_data<value_type, size_type> stored_data_type;
245 
246  static null_type s_null_type;
247  };
248 
249  template<typename Key, typename _Alloc>
250  null_type
251  type_base<Key, null_type, _Alloc, true>::s_null_type;
252 
253 
254  /// Type base dispatch.
255  template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
256  struct type_dispatch
257  {
258  typedef type_base<Key, Mapped, _Alloc, Store_Hash> type;
259  };
260 
261  /// Traits for abstract types.
262  template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
263  struct types_traits
264  : public type_dispatch<Key, Mapped, _Alloc, Store_Hash>::type
265  {
266  private:
267  typedef no_throw_copies<Key, Mapped> __nothrowcopy;
268  typedef typename _Alloc::template rebind<Key>::other __rebind_a;
269 
270  public:
271  typedef typename _Alloc::size_type size_type;
272  typedef typename __rebind_a::value_type key_type;
273  typedef typename __rebind_a::pointer key_pointer;
274  typedef typename __rebind_a::const_pointer key_const_pointer;
275  typedef typename __rebind_a::reference key_reference;
276  typedef typename __rebind_a::const_reference key_const_reference;
277  typedef std::pair<size_type, size_type> comp_hash;
278  typedef integral_constant<int, Store_Hash> store_extra;
279  typedef typename __nothrowcopy::indicator no_throw_indicator;
280 
281  store_extra m_store_extra_indicator;
282  no_throw_indicator m_no_throw_copies_indicator;
283  };
284  //@}
285  } // namespace detail
286 } // namespace __gnu_pbds
287 
288 #endif
__gnu_pbds::detail::stored_data
Primary template for representation of stored data. Two types of data can be stored: value and hash.
Definition: types_traits.hpp:95
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
__gnu_pbds::detail::types_traits
Traits for abstract types.
Definition: types_traits.hpp:263
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:51
__gnu_pbds::null_type
Represents no type, or absence of type, for template tricks.
Definition: tag_and_trait.hpp:210