3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
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 2, or (at your option) any later
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.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file basic_types.hpp
44 * Contains basic types used by containers.
47 #ifndef PB_DS_BASIC_TYPES_HPP
48 #define PB_DS_BASIC_TYPES_HPP
52 #include <ext/pb_ds/tag_and_trait.hpp>
53 #include <ext/pb_ds/detail/type_utils.hpp>
59 template<typename Key
, typename Mapped
, typename Allocator
, bool Store_Hash
>
60 struct value_type_base
;
63 * Specialization of value_type_base for the case where the hash value
64 * is not stored alongside each value.
66 template<typename Key
, typename Mapped
, typename Allocator
>
67 struct value_type_base
<Key
, Mapped
, Allocator
, false>
69 typedef typename
Allocator::template rebind
<Mapped
>::other mapped_type_allocator
;
70 typedef typename
mapped_type_allocator::value_type mapped_type
;
71 typedef typename
mapped_type_allocator::pointer mapped_pointer
;
72 typedef typename
mapped_type_allocator::const_pointer const_mapped_pointer
;
73 typedef typename
mapped_type_allocator::reference mapped_reference
;
74 typedef typename
mapped_type_allocator::const_reference const_mapped_reference
;
76 typedef typename
Allocator::template rebind
<std::pair
<const Key
, Mapped
> >::other value_type_allocator
;
77 typedef typename
value_type_allocator::value_type value_type
;
78 typedef typename
value_type_allocator::pointer pointer
;
79 typedef typename
value_type_allocator::const_pointer const_pointer
;
80 typedef typename
value_type_allocator::reference reference
;
81 typedef typename
value_type_allocator::const_reference const_reference
;
83 struct stored_value_type
90 * Specialization of value_type_base for the case where the hash value
91 * is stored alongside each value.
93 template<typename Key
, typename Mapped
, typename Allocator
>
94 struct value_type_base
<Key
, Mapped
, Allocator
, true>
96 typedef typename
Allocator::template rebind
<Mapped
>::other mapped_type_allocator
;
97 typedef typename
mapped_type_allocator::value_type mapped_type
;
98 typedef typename
mapped_type_allocator::pointer mapped_pointer
;
99 typedef typename
mapped_type_allocator::const_pointer const_mapped_pointer
;
100 typedef typename
mapped_type_allocator::reference mapped_reference
;
101 typedef typename
mapped_type_allocator::const_reference const_mapped_reference
;
103 typedef typename
Allocator::template rebind
<std::pair
<const Key
, Mapped
> >::other value_type_allocator
;
104 typedef typename
value_type_allocator::value_type value_type
;
105 typedef typename
value_type_allocator::pointer pointer
;
106 typedef typename
value_type_allocator::const_pointer const_pointer
;
107 typedef typename
value_type_allocator::reference reference
;
108 typedef typename
value_type_allocator::const_reference const_reference
;
110 struct stored_value_type
113 typename
Allocator::size_type m_hash
;
117 #define PB_DS_CLASS_T_DEC \
118 template<typename Key, typename Allocator>
120 #define PB_DS_CLASS_C_DEC \
121 value_type_base<Key, null_mapped_type, Allocator, false>
124 * Specialization of value_type_base for the case where the hash value
125 * is not stored alongside each value.
127 template<typename Key
, typename Allocator
>
128 struct value_type_base
<Key
, null_mapped_type
, Allocator
, false>
130 typedef typename
Allocator::template rebind
<null_mapped_type
>::other mapped_type_allocator
;
131 typedef typename
mapped_type_allocator::value_type mapped_type
;
132 typedef typename
mapped_type_allocator::pointer mapped_pointer
;
133 typedef typename
mapped_type_allocator::const_pointer const_mapped_pointer
;
134 typedef typename
mapped_type_allocator::reference mapped_reference
;
135 typedef typename
mapped_type_allocator::const_reference const_mapped_reference
;
137 typedef Key value_type
;
139 typedef typename
Allocator::template rebind
<value_type
>::other value_type_allocator
;
140 typedef typename
value_type_allocator::pointer pointer
;
141 typedef typename
value_type_allocator::const_pointer const_pointer
;
142 typedef typename
value_type_allocator::reference reference
;
143 typedef typename
value_type_allocator::const_reference const_reference
;
145 struct stored_value_type
150 static null_mapped_type s_null_mapped
;
154 null_mapped_type
PB_DS_CLASS_C_DEC::s_null_mapped
;
156 #undef PB_DS_CLASS_T_DEC
157 #undef PB_DS_CLASS_C_DEC
159 #define PB_DS_CLASS_T_DEC \
160 template<typename Key, typename Allocator>
162 #define PB_DS_CLASS_C_DEC \
163 value_type_base<Key, null_mapped_type, Allocator, true>
166 * Specialization of value_type_base for the case where the hash value
167 * is stored alongside each value.
169 template<typename Key
, typename Allocator
>
170 struct value_type_base
<Key
, null_mapped_type
, Allocator
, true>
172 typedef typename
Allocator::template rebind
<null_mapped_type
>::other mapped_type_allocator
;
173 typedef typename
mapped_type_allocator::value_type mapped_type
;
174 typedef typename
mapped_type_allocator::pointer mapped_pointer
;
175 typedef typename
mapped_type_allocator::const_pointer const_mapped_pointer
;
176 typedef typename
mapped_type_allocator::reference mapped_reference
;
177 typedef typename
mapped_type_allocator::const_reference const_mapped_reference
;
179 typedef Key value_type
;
181 typedef typename
Allocator::template rebind
<value_type
>::other value_type_allocator
;
182 typedef typename
value_type_allocator::pointer pointer
;
183 typedef typename
value_type_allocator::const_pointer const_pointer
;
184 typedef typename
value_type_allocator::reference reference
;
185 typedef typename
value_type_allocator::const_reference const_reference
;
187 struct stored_value_type
190 typename
Allocator::size_type m_hash
;
193 static null_mapped_type s_null_mapped
;
197 null_mapped_type
PB_DS_CLASS_C_DEC::s_null_mapped
;
199 #undef PB_DS_CLASS_T_DEC
200 #undef PB_DS_CLASS_C_DEC
202 template<typename Key
, typename Mapped
>
203 struct no_throw_copies
205 typedef integral_constant
<int, is_simple
<Key
>::value
&& is_simple
<Mapped
>::value
> indicator
;
208 template<typename Key
>
209 struct no_throw_copies
<Key
, null_mapped_type
>
211 typedef integral_constant
<int, is_simple
<Key
>::value
> indicator
;
213 } // namespace detail
214 } // namespace __gnu_pbds