00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047 #ifndef PB_DS_BASIC_TYPES_HPP
00048 #define PB_DS_BASIC_TYPES_HPP
00049
00050 #include <algorithm>
00051 #include <utility>
00052 #include <ext/pb_ds/tag_and_trait.hpp>
00053 #include <ext/pb_ds/detail/type_utils.hpp>
00054
00055 namespace __gnu_pbds
00056 {
00057 namespace detail
00058 {
00059 template<typename Key, typename Mapped, typename Allocator, bool Store_Hash>
00060 struct value_type_base;
00061
00062
00063
00064
00065
00066 template<typename Key, typename Mapped, typename Allocator>
00067 struct value_type_base<Key, Mapped, Allocator, false>
00068 {
00069 typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
00070 typedef typename mapped_type_allocator::value_type mapped_type;
00071 typedef typename mapped_type_allocator::pointer mapped_pointer;
00072 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
00073 typedef typename mapped_type_allocator::reference mapped_reference;
00074 typedef typename mapped_type_allocator::const_reference const_mapped_reference;
00075
00076 typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
00077 typedef typename value_type_allocator::value_type value_type;
00078 typedef typename value_type_allocator::pointer pointer;
00079 typedef typename value_type_allocator::const_pointer const_pointer;
00080 typedef typename value_type_allocator::reference reference;
00081 typedef typename value_type_allocator::const_reference const_reference;
00082
00083 struct stored_value_type
00084 {
00085 value_type m_value;
00086 };
00087 };
00088
00089
00090
00091
00092
00093 template<typename Key, typename Mapped, typename Allocator>
00094 struct value_type_base<Key, Mapped, Allocator, true>
00095 {
00096 typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
00097 typedef typename mapped_type_allocator::value_type mapped_type;
00098 typedef typename mapped_type_allocator::pointer mapped_pointer;
00099 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
00100 typedef typename mapped_type_allocator::reference mapped_reference;
00101 typedef typename mapped_type_allocator::const_reference const_mapped_reference;
00102
00103 typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
00104 typedef typename value_type_allocator::value_type value_type;
00105 typedef typename value_type_allocator::pointer pointer;
00106 typedef typename value_type_allocator::const_pointer const_pointer;
00107 typedef typename value_type_allocator::reference reference;
00108 typedef typename value_type_allocator::const_reference const_reference;
00109
00110 struct stored_value_type
00111 {
00112 value_type m_value;
00113 typename Allocator::size_type m_hash;
00114 };
00115 };
00116
00117 #define PB_DS_CLASS_T_DEC \
00118 template<typename Key, typename Allocator>
00119
00120 #define PB_DS_CLASS_C_DEC \
00121 value_type_base<Key, null_mapped_type, Allocator, false>
00122
00123
00124
00125
00126
00127 template<typename Key, typename Allocator>
00128 struct value_type_base<Key, null_mapped_type, Allocator, false>
00129 {
00130 typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
00131 typedef typename mapped_type_allocator::value_type mapped_type;
00132 typedef typename mapped_type_allocator::pointer mapped_pointer;
00133 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
00134 typedef typename mapped_type_allocator::reference mapped_reference;
00135 typedef typename mapped_type_allocator::const_reference const_mapped_reference;
00136
00137 typedef Key value_type;
00138
00139 typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
00140 typedef typename value_type_allocator::pointer pointer;
00141 typedef typename value_type_allocator::const_pointer const_pointer;
00142 typedef typename value_type_allocator::reference reference;
00143 typedef typename value_type_allocator::const_reference const_reference;
00144
00145 struct stored_value_type
00146 {
00147 value_type m_value;
00148 };
00149
00150 static null_mapped_type s_null_mapped;
00151 };
00152
00153 PB_DS_CLASS_T_DEC
00154 null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
00155
00156 #undef PB_DS_CLASS_T_DEC
00157 #undef PB_DS_CLASS_C_DEC
00158
00159 #define PB_DS_CLASS_T_DEC \
00160 template<typename Key, typename Allocator>
00161
00162 #define PB_DS_CLASS_C_DEC \
00163 value_type_base<Key, null_mapped_type, Allocator, true>
00164
00165
00166
00167
00168
00169 template<typename Key, typename Allocator>
00170 struct value_type_base<Key, null_mapped_type, Allocator, true>
00171 {
00172 typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
00173 typedef typename mapped_type_allocator::value_type mapped_type;
00174 typedef typename mapped_type_allocator::pointer mapped_pointer;
00175 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
00176 typedef typename mapped_type_allocator::reference mapped_reference;
00177 typedef typename mapped_type_allocator::const_reference const_mapped_reference;
00178
00179 typedef Key value_type;
00180
00181 typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
00182 typedef typename value_type_allocator::pointer pointer;
00183 typedef typename value_type_allocator::const_pointer const_pointer;
00184 typedef typename value_type_allocator::reference reference;
00185 typedef typename value_type_allocator::const_reference const_reference;
00186
00187 struct stored_value_type
00188 {
00189 value_type m_value;
00190 typename Allocator::size_type m_hash;
00191 };
00192
00193 static null_mapped_type s_null_mapped;
00194 };
00195
00196 PB_DS_CLASS_T_DEC
00197 null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
00198
00199 #undef PB_DS_CLASS_T_DEC
00200 #undef PB_DS_CLASS_C_DEC
00201
00202 template<typename Key, typename Mapped>
00203 struct no_throw_copies
00204 {
00205 typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator;
00206 };
00207
00208 template<typename Key>
00209 struct no_throw_copies<Key, null_mapped_type>
00210 {
00211 typedef integral_constant<int, is_simple<Key>::value> indicator;
00212 };
00213 }
00214 }
00215
00216 #endif
00217