libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file basic_types.hpp 00038 * Contains basic types used by containers. 00039 */ 00040 00041 #ifndef PB_DS_BASIC_TYPES_HPP 00042 #define PB_DS_BASIC_TYPES_HPP 00043 00044 #include <algorithm> 00045 #include <utility> 00046 #include <ext/pb_ds/tag_and_trait.hpp> 00047 #include <ext/pb_ds/detail/type_utils.hpp> 00048 00049 namespace __gnu_pbds 00050 { 00051 namespace detail 00052 { 00053 template<typename Key, typename Mapped, typename Allocator, bool Store_Hash> 00054 struct value_type_base; 00055 00056 /** 00057 * Specialization of value_type_base for the case where the hash value 00058 * is not stored alongside each value. 00059 **/ 00060 template<typename Key, typename Mapped, typename Allocator> 00061 struct value_type_base<Key, Mapped, Allocator, false> 00062 { 00063 typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator; 00064 typedef typename mapped_type_allocator::value_type mapped_type; 00065 typedef typename mapped_type_allocator::pointer mapped_pointer; 00066 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 00067 typedef typename mapped_type_allocator::reference mapped_reference; 00068 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 00069 00070 typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator; 00071 typedef typename value_type_allocator::value_type value_type; 00072 typedef typename value_type_allocator::pointer pointer; 00073 typedef typename value_type_allocator::const_pointer const_pointer; 00074 typedef typename value_type_allocator::reference reference; 00075 typedef typename value_type_allocator::const_reference const_reference; 00076 00077 struct stored_value_type 00078 { 00079 value_type m_value; 00080 }; 00081 }; 00082 00083 /** 00084 * Specialization of value_type_base for the case where the hash value 00085 * is stored alongside each value. 00086 **/ 00087 template<typename Key, typename Mapped, typename Allocator> 00088 struct value_type_base<Key, Mapped, Allocator, true> 00089 { 00090 typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator; 00091 typedef typename mapped_type_allocator::value_type mapped_type; 00092 typedef typename mapped_type_allocator::pointer mapped_pointer; 00093 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 00094 typedef typename mapped_type_allocator::reference mapped_reference; 00095 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 00096 00097 typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator; 00098 typedef typename value_type_allocator::value_type value_type; 00099 typedef typename value_type_allocator::pointer pointer; 00100 typedef typename value_type_allocator::const_pointer const_pointer; 00101 typedef typename value_type_allocator::reference reference; 00102 typedef typename value_type_allocator::const_reference const_reference; 00103 00104 struct stored_value_type 00105 { 00106 value_type m_value; 00107 typename Allocator::size_type m_hash; 00108 }; 00109 }; 00110 00111 #define PB_DS_CLASS_T_DEC \ 00112 template<typename Key, typename Allocator> 00113 00114 #define PB_DS_CLASS_C_DEC \ 00115 value_type_base<Key, null_mapped_type, Allocator, false> 00116 00117 /** 00118 * Specialization of value_type_base for the case where the hash value 00119 * is not stored alongside each value. 00120 **/ 00121 template<typename Key, typename Allocator> 00122 struct value_type_base<Key, null_mapped_type, Allocator, false> 00123 { 00124 typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator; 00125 typedef typename mapped_type_allocator::value_type mapped_type; 00126 typedef typename mapped_type_allocator::pointer mapped_pointer; 00127 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 00128 typedef typename mapped_type_allocator::reference mapped_reference; 00129 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 00130 00131 typedef Key value_type; 00132 00133 typedef typename Allocator::template rebind<value_type>::other value_type_allocator; 00134 typedef typename value_type_allocator::pointer pointer; 00135 typedef typename value_type_allocator::const_pointer const_pointer; 00136 typedef typename value_type_allocator::reference reference; 00137 typedef typename value_type_allocator::const_reference const_reference; 00138 00139 struct stored_value_type 00140 { 00141 value_type m_value; 00142 }; 00143 00144 static null_mapped_type s_null_mapped; 00145 }; 00146 00147 PB_DS_CLASS_T_DEC 00148 null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped; 00149 00150 #undef PB_DS_CLASS_T_DEC 00151 #undef PB_DS_CLASS_C_DEC 00152 00153 #define PB_DS_CLASS_T_DEC \ 00154 template<typename Key, typename Allocator> 00155 00156 #define PB_DS_CLASS_C_DEC \ 00157 value_type_base<Key, null_mapped_type, Allocator, true> 00158 00159 /** 00160 * Specialization of value_type_base for the case where the hash value 00161 * is stored alongside each value. 00162 **/ 00163 template<typename Key, typename Allocator> 00164 struct value_type_base<Key, null_mapped_type, Allocator, true> 00165 { 00166 typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator; 00167 typedef typename mapped_type_allocator::value_type mapped_type; 00168 typedef typename mapped_type_allocator::pointer mapped_pointer; 00169 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 00170 typedef typename mapped_type_allocator::reference mapped_reference; 00171 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 00172 00173 typedef Key value_type; 00174 00175 typedef typename Allocator::template rebind<value_type>::other value_type_allocator; 00176 typedef typename value_type_allocator::pointer pointer; 00177 typedef typename value_type_allocator::const_pointer const_pointer; 00178 typedef typename value_type_allocator::reference reference; 00179 typedef typename value_type_allocator::const_reference const_reference; 00180 00181 struct stored_value_type 00182 { 00183 value_type m_value; 00184 typename Allocator::size_type m_hash; 00185 }; 00186 00187 static null_mapped_type s_null_mapped; 00188 }; 00189 00190 PB_DS_CLASS_T_DEC 00191 null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped; 00192 00193 #undef PB_DS_CLASS_T_DEC 00194 #undef PB_DS_CLASS_C_DEC 00195 00196 template<typename Key, typename Mapped> 00197 struct no_throw_copies 00198 { 00199 typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator; 00200 }; 00201 00202 template<typename Key> 00203 struct no_throw_copies<Key, null_mapped_type> 00204 { 00205 typedef integral_constant<int, is_simple<Key>::value> indicator; 00206 }; 00207 } // namespace detail 00208 } // namespace __gnu_pbds 00209 00210 #endif 00211