1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
| #define _HAS_ITERATOR_DEBUGGING 0
//_HAS_ITERATOR_DEBUGGING=0;_SECURE_SCL=0;
#include <xmemory>
#include <vector>
#include <iostream>
#include <algorithm>
template<class BVA>
class bva_const_pointer
{
public:
typedef std::random_access_iterator_tag iterator_category;
typedef typename BVA::pointer pointer;
typedef typename BVA::reference reference;
typedef typename BVA::value_type value_type;
typedef typename BVA::size_type size_type;
typedef typename BVA::difference_type difference_type;
protected:
BVA const *bva_;
size_type pos_;
public:
bva_const_pointer(int pos=0)
: bva_((BVA const *)0), pos_(pos) {}
bva_const_pointer(size_type pos, BVA const *bva)
: bva_(bva), pos_(pos) {}
//operator void *()
// { return (void *)bva_->calc_addr(pos_); }
value_type const & operator*() const
{ return *bva_->calc_addr(pos_); }
value_type const *operator->() const
{ return bva_->calc_addr(pos_); }
operator value_type const *() const
{ return bva_->calc_addr(pos_); }
bva_const_pointer & operator++()
{ ++pos_; return (*this); }
bva_const_pointer operator++(int)
{ const_pointer tmp(*this); ++pos_; return tmp; }
bva_const_pointer & operator--()
{ --pos_; return *this; }
bva_const_pointer operator--(int)
{ bva_const_pointer tmp(*this); --pos_; return tmp; }
bva_const_pointer & operator+=(difference_type n)
{ pos_+=n; return *this; }
bva_const_pointer & operator-=(difference_type n)
{ return (*this += -n); }
bva_const_pointer operator+(difference_type n) const
{ bva_const_pointer tmp(*this); return (tmp += n); }
bva_const_pointer operator-(difference_type n) const
{ bva_const_pointer tmp(*this); return (tmp -= n); }
difference_type operator-(bva_const_pointer const & r) const
{ return (pos_ - r.pos_); }
//friend difference_type operator-(value_type const *p, bva_const_pointer const & r)
// { return (r.bva_->calc_pointer(*p) - r); }
value_type const & operator[](difference_type n) const
{ return (*(*this + n)); }
bool operator==(bva_const_pointer const & r) const
{ return (pos_ == r.pos_ && bva_ == r.bva_); }
bool operator!=(bva_const_pointer const & r) const
{ return (!(*this == r)); }
bool operator==(int i) const
{
if (i == 0)
return (bva_ == NULL);
throw std::exception("bva_const_pointer: i must be 0");
}
bool operator!=(int i) const
{ return (!(*this == r)); }
bool operator<(bva_const_pointer const & r) const
{ return (pos_ < r.pos_); }
//bool operator>(bva_const_pointer const & r) const
// {return (r < *this); }
//bool operator<=(bva_const_pointer const & r) const
// {return (!(r < *this)); }
//bool operator>=(bva_const_pointer const & r) const
// {return (!(*this < r)); }
};
template<class BVA>
class bva_pointer: protected bva_const_pointer<BVA>
{
public:
typedef bva_const_pointer<BVA> base_type;
typedef typename base_type::iterator_category iterator_category;
typedef typename base_type::pointer pointer;
typedef typename base_type::reference reference;
typedef typename base_type::value_type value_type;
typedef typename base_type::size_type size_type;
typedef typename base_type::difference_type difference_type;
bva_pointer(int pos=0)
: bva_const_pointer(pos) {}
bva_pointer(size_type pos, BVA const *bva)
: bva_const_pointer(pos, bva) {}
//operator void *()
// { return (void *)*(base_type *)this; }
value_type & operator*() const
{ return (value_type &)**(base_type *)this; }
value_type *operator->() const
{ return (&**this); }
operator value_type *() const
{ return (&**this); }
operator value_type const *() const
{ return (&**this); }
bva_pointer & operator++()
{ ++*(base_type *)this; return *this; }
bva_pointer operator++(int)
{ bva_pointer tmp(*this); ++*this; return tmp; }
bva_pointer & operator--()
{ --*(base_type *)this; return *this; }
bva_pointer operator--(int)
{ bva_pointer tmp(*this); --*this; return tmp; }
bva_pointer & operator+=(difference_type n)
{ *(base_type *)this += n; return (*this); }
bva_pointer & operator-=(difference_type n)
{ return (*this += -n); }
bva_pointer operator+(difference_type n) const
{ bva_pointer tmp(*this); return (tmp += n); }
bva_pointer operator-(difference_type n) const
{ bva_pointer tmp(*this); return (tmp -= n); }
difference_type operator-(bva_pointer const & r) const
{ return (*(base_type *)this - r); }
friend difference_type operator-(value_type *p, bva_pointer const & r)
{ return ((value_type const *)p - r); }
value_type & operator[](difference_type n) const
{ return (*(*this + n)); }
bool operator==(bva_pointer const & r) const
{ return (*(base_type *)this == r); }
bool operator!=(bva_pointer const & r) const
{ return (!(*this == r)); }
bool operator==(int i) const
{ return (*(base_type *)this == i); }
bool operator!=(int i) const
{ return (!(*this == i)); }
bool operator<(bva_pointer const & r) const
{ return (*(base_type *)this < r); }
};
template<class T, unsigned RS>
class bva_base
{
public:
typedef T value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef bva_pointer<bva_base<T, RS> > pointer;
typedef value_type & reference;
//protected:
enum { segment_size=RS/sizeof(T) };
typedef unsigned char byte;
std::vector<byte *> v_;
value_type *calc_addr(size_type pos) const
{
if (pos/* && v_size() ?*/)
{
--pos;
size_type segment=pos / segment_size;
size_type offset=pos % segment_size;
return (value_type *)&v_.at(segment)[offset*sizeof(value_type)];
}
return (value_type *)0;
}
bva_pointer<bva_base<T, RS> > calc_pointer(value_type const & r) const
{
value_type const *p=&r;
for (std::vector<byte *>::const_iterator it=v_.begin(); it!=v_.end(); ++it)
{
size_type offset=(p-(value_type const *)*it);
if (offset < segment_size)
{
size_type segment=(it-v_.begin());
size_type pos=segment*segment_size+offset+1;
return bva_pointer<bva_base<T, RS> >(pos, this);
}
}
return bva_pointer<bva_base<T, RS> >(0);
}
bva_pointer<bva_base<T, RS> > broken_alloc(size_type n)
{
if (v_.size())
throw std::bad_alloc("broken alloc");
while (n)
{
size_type n_alloc=(n>segment_size? segment_size: n);
byte *ptr=(byte *)::operator new(n_alloc*sizeof(value_type));
v_.push_back(ptr);
n-=n_alloc;
}
return bva_pointer<bva_base<T, RS> >(1, this);
}
void broken_dealloc()
{
for (auto it=v_.begin(); it!=v_.end(); ++it)
::operator delete(*it);
v_.clear();
}
};
template<class T, unsigned RS>
class broken_vector_allocator: public bva_base<T, RS>
{
public:
typedef bva_base<T, RS> base_type;
typedef typename base_type::value_type value_type;
typedef typename base_type::size_type size_type;
typedef typename base_type::difference_type difference_type;
typedef bva_pointer<bva_base<T, RS> > pointer;
typedef bva_const_pointer<bva_base<T, RS> > const_pointer;
typedef value_type & reference;
typedef const value_type & const_reference;
template<class Other>
struct rebind
{
typedef broken_vector_allocator<Other, RS> other;
};
pointer address(reference val) const
{ // return address of mutable _Val
return calc_pointer(val);
}
const_pointer address(const_reference val) const
{ // return address of nonmutable _Val
return calc_pointer(val);
}
broken_vector_allocator() throw()
{ // construct default allocator (do nothing)
}
broken_vector_allocator(broken_vector_allocator const &) throw()
{ // construct by copying (do nothing)
}
template<class Other>
broken_vector_allocator(broken_vector_allocator<Other, RS> const &) throw()
{ // construct from a related allocator (do nothing)
}
template<class Other>
broken_vector_allocator<T, RS> & operator=(broken_vector_allocator<Other, RS> const &)
{ // assign from a related allocator (do nothing)
return (*this);
}
void deallocate(pointer _Ptr, size_type)
{ // deallocate object at _Ptr, ignore size
broken_dealloc(/*_Ptr*/);
}
pointer allocate(size_type _Count)
{ // allocate array of _Count elements
return broken_alloc(_Count);
}
pointer allocate(size_type _Count, const void *)
{ // allocate array of _Count elements, ignore hint
return broken_alloc(_Count);
}
void construct(pointer _Ptr, T const & _Val)
{ // construct object at _Ptr with value _Val
void *ptr(_Ptr);
::new(ptr) T(_Val);
}
void destroy(pointer _Ptr)
{ // destroy object at _Ptr
T *ptr(_Ptr);
ptr->~T();
}
size_t max_size() const throw()
{ // estimate maximum array size
size_type _Count = (size_type)(-1) / sizeof (T);
return (0 < _Count ? _Count : 1);
}
};
template<class _Alloc,
class _Ty1>
void _Dest_val(_Alloc& _Alval, bva_pointer<_Ty1> _Pdest)
{ // destroy using allocator
_Alval.destroy(_Pdest);
}
template<class _Alloc,
class _Ty2>
void _Cons_val(_Alloc& _Alval, typename _Alloc::pointer _Pdest, _Ty2&& _Src)
{ // construct using allocator
_Alval.construct(_Pdest, _STD forward<_Ty2>(_Src));
}
int main()
{
typedef std::vector<int, broken_vector_allocator<int, 12> > bvector;
std::cout << "initialize vector" << std::endl;
bvector v;
v.reserve(10);
v.push_back(5);
v.push_back(4);
v.push_back(3);
v.push_back(2);
v.push_back(1);
v.push_back(6);
v.push_back(7);
for (bvector::iterator it=v.begin(); it!=v.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl;
std::cout << "sort vector" << std::endl;
std::sort(v.begin(), v.end());
for (bvector::iterator it=v.begin(); it!=v.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl;
std::cout << "insert some items" << std::endl;
v.insert(v.end(), 7);
bvector::iterator it_found=std::lower_bound(v.begin(), v.end(), 4);
if (it_found!=v.end())
v.insert(it_found, 4);
v.insert(v.begin(), 1);
for (bvector::const_iterator cit=v.cbegin(); cit!=v.cend(); ++cit)
std::cout << *cit << " ";
std::cout << std::endl;
std::cout << "erase duplicates" << std::endl;
v.erase(std::unique(v.begin(), v.end()), v.end());
for (bvector::const_iterator cit=v.cbegin(); cit!=v.cend(); ++cit)
std::cout << *cit << " ";
std::cout << std::endl;
ptrdiff_t d=v.cend()-v.cbegin();
std::cout << d << std::endl;
// int const *pi=it_found; pas OK ?
return 0;
} |
Partager