libstdc++
basic_types.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009 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 basic_types.hpp
38  * Contains basic types used by containers.
39  */
40 
41 #ifndef PB_DS_BASIC_TYPES_HPP
42 #define PB_DS_BASIC_TYPES_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 
49 namespace __gnu_pbds
50 {
51  namespace detail
52  {
53  template<typename Key, typename Mapped, typename Allocator, bool Store_Hash>
54  struct value_type_base;
55 
56  /**
57  * Specialization of value_type_base for the case where the hash value
58  * is not stored alongside each value.
59  **/
60  template<typename Key, typename Mapped, typename Allocator>
61  struct value_type_base<Key, Mapped, Allocator, false>
62  {
63  typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
64  typedef typename mapped_type_allocator::value_type mapped_type;
65  typedef typename mapped_type_allocator::pointer mapped_pointer;
66  typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
67  typedef typename mapped_type_allocator::reference mapped_reference;
68  typedef typename mapped_type_allocator::const_reference const_mapped_reference;
69 
70  typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
71  typedef typename value_type_allocator::value_type value_type;
72  typedef typename value_type_allocator::pointer pointer;
73  typedef typename value_type_allocator::const_pointer const_pointer;
74  typedef typename value_type_allocator::reference reference;
75  typedef typename value_type_allocator::const_reference const_reference;
76 
77  struct stored_value_type
78  {
79  value_type m_value;
80  };
81  };
82 
83  /**
84  * Specialization of value_type_base for the case where the hash value
85  * is stored alongside each value.
86  **/
87  template<typename Key, typename Mapped, typename Allocator>
88  struct value_type_base<Key, Mapped, Allocator, true>
89  {
90  typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
91  typedef typename mapped_type_allocator::value_type mapped_type;
92  typedef typename mapped_type_allocator::pointer mapped_pointer;
93  typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
94  typedef typename mapped_type_allocator::reference mapped_reference;
95  typedef typename mapped_type_allocator::const_reference const_mapped_reference;
96 
97  typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
98  typedef typename value_type_allocator::value_type value_type;
99  typedef typename value_type_allocator::pointer pointer;
100  typedef typename value_type_allocator::const_pointer const_pointer;
101  typedef typename value_type_allocator::reference reference;
102  typedef typename value_type_allocator::const_reference const_reference;
103 
104  struct stored_value_type
105  {
106  value_type m_value;
107  typename Allocator::size_type m_hash;
108  };
109  };
110 
111 #define PB_DS_CLASS_T_DEC \
112  template<typename Key, typename Allocator>
113 
114 #define PB_DS_CLASS_C_DEC \
115  value_type_base<Key, null_mapped_type, Allocator, false>
116 
117  /**
118  * Specialization of value_type_base for the case where the hash value
119  * is not stored alongside each value.
120  **/
121  template<typename Key, typename Allocator>
122  struct value_type_base<Key, null_mapped_type, Allocator, false>
123  {
124  typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
125  typedef typename mapped_type_allocator::value_type mapped_type;
126  typedef typename mapped_type_allocator::pointer mapped_pointer;
127  typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
128  typedef typename mapped_type_allocator::reference mapped_reference;
129  typedef typename mapped_type_allocator::const_reference const_mapped_reference;
130 
131  typedef Key value_type;
132 
133  typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
134  typedef typename value_type_allocator::pointer pointer;
135  typedef typename value_type_allocator::const_pointer const_pointer;
136  typedef typename value_type_allocator::reference reference;
137  typedef typename value_type_allocator::const_reference const_reference;
138 
139  struct stored_value_type
140  {
141  value_type m_value;
142  };
143 
144  static null_mapped_type s_null_mapped;
145  };
146 
147  PB_DS_CLASS_T_DEC
148  null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
149 
150 #undef PB_DS_CLASS_T_DEC
151 #undef PB_DS_CLASS_C_DEC
152 
153 #define PB_DS_CLASS_T_DEC \
154  template<typename Key, typename Allocator>
155 
156 #define PB_DS_CLASS_C_DEC \
157  value_type_base<Key, null_mapped_type, Allocator, true>
158 
159  /**
160  * Specialization of value_type_base for the case where the hash value
161  * is stored alongside each value.
162  **/
163  template<typename Key, typename Allocator>
164  struct value_type_base<Key, null_mapped_type, Allocator, true>
165  {
166  typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
167  typedef typename mapped_type_allocator::value_type mapped_type;
168  typedef typename mapped_type_allocator::pointer mapped_pointer;
169  typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
170  typedef typename mapped_type_allocator::reference mapped_reference;
171  typedef typename mapped_type_allocator::const_reference const_mapped_reference;
172 
173  typedef Key value_type;
174 
175  typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
176  typedef typename value_type_allocator::pointer pointer;
177  typedef typename value_type_allocator::const_pointer const_pointer;
178  typedef typename value_type_allocator::reference reference;
179  typedef typename value_type_allocator::const_reference const_reference;
180 
181  struct stored_value_type
182  {
183  value_type m_value;
184  typename Allocator::size_type m_hash;
185  };
186 
187  static null_mapped_type s_null_mapped;
188  };
189 
190  PB_DS_CLASS_T_DEC
191  null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
192 
193 #undef PB_DS_CLASS_T_DEC
194 #undef PB_DS_CLASS_C_DEC
195 
196  template<typename Key, typename Mapped>
197  struct no_throw_copies
198  {
199  typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator;
200  };
201 
202  template<typename Key>
203  struct no_throw_copies<Key, null_mapped_type>
204  {
205  typedef integral_constant<int, is_simple<Key>::value> indicator;
206  };
207  } // namespace detail
208 } // namespace __gnu_pbds
209 
210 #endif
211 
__gnu_pbds::null_mapped_type
A mapped-policy indicating that an associative container is a set.
Definition: tag_and_trait.hpp:89