14 #ifndef STK_UTIL_UTIL_vecmap_hpp 15 #define STK_UTIL_UTIL_vecmap_hpp 59 template <
class Key,
class T,
class Compare = std::less<Key> >
62 typedef Key key_type ;
63 typedef T mapped_type ;
64 typedef Compare key_compare ;
67 typedef std::vector< std::pair<const key_type,mapped_type> > storage ;
70 typedef typename storage::value_type value_type ;
71 typedef typename storage::allocator_type allocator_type ;
72 typedef typename allocator_type::reference reference ;
73 typedef typename allocator_type::const_reference const_reference ;
74 typedef typename allocator_type::pointer pointer ;
75 typedef typename allocator_type::const_pointer const_pointer ;
76 typedef typename storage::size_type size_type ;
77 typedef typename storage::difference_type difference_type ;
78 typedef typename storage::iterator iterator ;
79 typedef typename storage::const_iterator const_iterator ;
80 typedef typename storage::reverse_iterator reverse_iterator ;
81 typedef typename storage::const_reverse_iterator const_reverse_iterator ;
83 typedef std::pair<key_type,mapped_type> value_type_unconst_key ;
87 :
public std::binary_function<value_type,value_type,bool> {
91 bool operator ()(
const value_type & RHS ,
const value_type & LHS )
const 92 {
return comp( RHS.first , LHS.first ); }
95 class value_compare_key
96 :
public std::binary_function<value_type,key_type,bool> {
100 bool operator()(
const value_type & RHS ,
const key_type & LHS )
const 101 {
return comp( RHS.first , LHS ); }
104 class value_compare_unconst_key
105 :
public std::binary_function<value_type_unconst_key,key_type,bool> {
109 bool operator()(
const value_type_unconst_key & RHS ,
const key_type & LHS )
const 110 {
return comp( RHS.first , LHS ); }
114 std::vector<value_type_unconst_key> Storage;
115 value_compare ValueComp ;
116 value_compare_key ValueKeyComp ;
117 value_compare_unconst_key UnconstValueKeyComp ;
118 key_compare KeyComp ;
122 char &i =
reinterpret_cast<char&
>(Storage);
123 return reinterpret_cast<storage&
>(i);
126 const storage & pub()
const {
127 const char &i =
reinterpret_cast<const char&
>(Storage);
128 return reinterpret_cast<const storage&
>(i);
131 typedef typename std::vector<value_type_unconst_key>::iterator iterator_private ;
133 static iterator_private & castit( iterator & i )
134 {
return reinterpret_cast<iterator_private &
>(i); }
136 static iterator & castit( iterator_private & i )
137 {
return reinterpret_cast<iterator &
>(i); }
147 Storage = rhs.Storage ;
152 Storage.swap( v.Storage );
155 iterator begin() {
return pub().begin(); }
156 iterator end() {
return pub().end(); }
157 const_iterator begin()
const {
return pub().begin(); }
158 const_iterator end()
const {
return pub().end(); }
159 reverse_iterator rbegin() {
return pub().rbegin(); }
160 reverse_iterator rend() {
return pub().rend(); }
161 const_reverse_iterator rbegin()
const {
return pub().rbegin(); }
162 const_reverse_iterator rend()
const {
return pub().rend(); }
163 bool empty()
const {
return Storage.empty(); }
164 size_type size()
const {
return Storage.size(); }
165 size_type max_size()
const {
return Storage.max_size(); }
168 typename std::vector<value_type_unconst_key>::iterator lower_bound_private_comp_(
const key_type & k ) {
169 typename std::vector<value_type_unconst_key>::iterator __first = Storage.begin();
170 typename std::vector<value_type_unconst_key>::iterator __last = Storage.end();
173 difference_type __len = __last - __first;
174 difference_type __half;
175 typename std::vector<value_type_unconst_key>::iterator __middle;
182 if (UnconstValueKeyComp(*__middle, k)) {
185 __len = __len - __half - 1;
193 std::pair<iterator,bool> insert(
const value_type & v ) {
194 typename std::vector<value_type_unconst_key>::iterator ip =
195 lower_bound_private_comp_(v.first);
197 const bool b = Storage.end() == ip || KeyComp( v.first , ip->first );
199 if ( b ) ip = Storage.insert(ip,value_type_unconst_key(v.first,v.second));
200 return std::pair<iterator,bool>( castit(ip), b );
203 mapped_type & operator[](
const key_type & k ) {
204 typename std::vector<value_type_unconst_key>::iterator ip =
205 lower_bound_private_comp_(k);
208 if ( Storage.end() == ip || KeyComp(k,ip->first) ) {
210 ( ip = Storage.insert(ip,value_type_unconst_key()) )->first = k ;
215 void erase( iterator i ) {
216 Storage.erase( castit(i) );
219 void erase( iterator first , iterator last ) {
220 Storage.erase( castit(first), castit(last) );
223 size_type erase(
const key_type & k ) {
224 const typename std::vector<value_type_unconst_key>::iterator i =
225 lower_bound_private_comp_(k);
226 return KeyComp( k , i->first ) ? 0 : ( Storage.erase(i) , 1 );
233 key_compare key_comp()
const {
return KeyComp ; }
235 value_compare value_comp()
const {
return ValueComp ; }
237 iterator lower_bound(
const key_type & k ) {
238 iterator __first = begin();
239 iterator __last = end();
242 difference_type __len = __last - __first;
243 difference_type __half;
251 if (ValueKeyComp(*__middle, k)) {
254 __len = __len - __half - 1;
262 const_iterator lower_bound(
const key_type & k )
const {
263 const_iterator __first = begin();
264 const_iterator __last = end();
267 difference_type __len = __last - __first;
268 difference_type __half;
269 const_iterator __middle;
276 if (ValueKeyComp(*__middle, k)) {
279 __len = __len - __half - 1;
287 iterator upper_bound(
const key_type & k ) {
288 iterator __first = begin();
289 iterator __last = end();
292 difference_type __len = __last - __first;
293 difference_type __half;
301 if (__comp(k, *__middle))
306 __len = __len - __half - 1;
313 const_iterator upper_bound(
const key_type & k )
const {
314 const_iterator __first = begin();
315 const_iterator __last = end();
318 difference_type __len = __last - __first;
319 difference_type __half;
320 const_iterator __middle;
327 if (__comp(k, *__middle))
332 __len = __len - __half - 1;
339 iterator find(
const key_type & k ) {
340 const iterator i = lower_bound(k);
341 return end() == i || KeyComp( k , i->first ) ? end() : i ;
344 const_iterator find(
const key_type & k )
const {
345 const const_iterator i = lower_bound(k);
346 return end() == i || KeyComp( k , i->first ) ? end() : i ;
349 size_type count(
const key_type & k )
const {
350 const const_iterator i = lower_bound(k);
351 return end() == i || KeyComp( k , i->first ) ? 0 : 1 ;
357 operator const std::vector<value_type> & ()
const {
358 return *
reinterpret_cast<const std::vector<value_type>*
>( &Storage );
361 operator const std::vector< std::pair<key_type,mapped_type> > & ()
const {
365 void reserve( size_type n ) {
370 return Storage == rhs.Storage ;
374 return Storage != rhs.Storage ;
380 #endif // STK_UTIL_UTIL_vecmap_hpp
Vector-based std::map functionality.