git.cworth.org Git - vogl/blob - src/extlib/loki/include/loki/yasli/yasli_vector.h

   1 #ifndef YASLI_VECTOR_H_
   2 #define YASLI_VECTOR_H_
   3
   4 // $Id: yasli_vector.h 754 2006-10-17 19:59:11Z syntheticpp $
   5
   6
   7 #include "platform.h"
   8 #include "yasli_fill_iterator.h"
   9 #include "yasli_memory.h"
  10 #include "yasli_traits.h"
  11 #include "yasli_protocols.h"
  12 #include <iterator>
  13 #include <cassert>
  14 #include <stdexcept>
  15 #include "../TypeManip.h"
  16
  17 namespace yasli
  18 {
  19 template <class T, class Allocator = allocator<T> >
  20 class vector;
  21 }
  22
  23 namespace yasli
  24 {
  25
  26 template <class T, class Allocator>
  27 class vector
  28 {
  29         struct ebo : public Allocator
  30         {
  31                 T *beg_;
  32                 ebo() {}
  33                 ebo(const Allocator &a) : Allocator(a) {}
  34         } ebo_;
  35         T *end_;
  36         T *eos_;
  37 public:
  38         // types:
  39         typedef          vector<T, Allocator>             this_type;//not standard
  40         typedef typename Allocator::reference             reference;
  41         typedef typename Allocator::const_reference       const_reference;
  42         typedef typename Allocator::pointer               iterator;       // See 23.1
  43         typedef typename Allocator::const_pointer         const_iterator; // See 23.1
  44         typedef typename Allocator::size_type             size_type;      // See 23.1
  45         typedef typename Allocator::difference_type       difference_type;// See 23.1
  46         typedef          T                                value_type;
  47         typedef          Allocator                        allocator_type;
  48         typedef typename Allocator::pointer               pointer;
  49         typedef typename Allocator::const_pointer         const_pointer;
  50         typedef std::reverse_iterator<iterator>           reverse_iterator;
  51         typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  52 private:
  53         void init_empty()
  54         {
  55
  56 #if YASLI_UNDEFINED_POINTERS_COPYABLE == 1
  57                 end_ = ebo_.beg_;
  58                 eos_ = ebo_.beg_;
  59 #else
  60                 ebo_.beg_ = 0;
  61                 end_ = 0;
  62                 eos_ = 0;
  63 #endif
  64                 assert(empty());
  65
  66         }
  67
  68         void init_move(vector &temp)
  69         {
  70                 ebo_ = temp.ebo_;
  71                 end_ = temp.end_;
  72                 eos_ = temp.eos_;
  73                 temp.init_empty();
  74         }
  75
  76         void init_fill(size_type n, const T &value, const Allocator &a)
  77         {
  78                 // Will avoid catch (...)
  79                 vector<T, Allocator> temp(a);
  80                 temp.insert(temp.end(), n, value);
  81                 init_move(temp);
  82                 assert(size() == n);
  83         }
  84
  85         // 23.2.4.1 construct/copy/destroy:
  86         template <class InputIterator, class looks_like_itr>
  87         void init(InputIterator first, InputIterator last, looks_like_itr, const Allocator &a)
  88         {
  89                 vector temp(a);
  90                 temp.insert(temp.end(), first, last);
  91                 init_move(temp);
  92         }
  93
  94         template <class non_iterator>
  95         void init(non_iterator n, non_iterator datum, Loki::Int2Type<false>,
  96                   const Allocator &a)
  97         {
  98                 init_fill((size_type)n, (const T &)datum, a);
  99         }
 100
 101 public:
 102         vector()
 103         {
 104                 init_empty();
 105         }
 106
 107         explicit vector(const Allocator &a)
 108                 : ebo_(a)
 109         {
 110                 init_empty();
 111         }
 112
 113         explicit vector(size_type n, const T &value = T(),
 114                         const Allocator &a = Allocator())
 115         {
 116                 init_fill(n, value, a);
 117         }
 118
 119         //!! avoid enable_if
 120         template <class InputIterator>
 121         vector(InputIterator first, InputIterator last, const Allocator &a = Allocator())
 122         {
 123                 init(first, last, Loki::Int2Type<
 124                      yasli_nstd::is_class<InputIterator>::value ||
 125                      yasli_nstd::is_pointer<InputIterator>::value >(), a);
 126         }
 127
 128 public:
 129         vector(const vector<T,Allocator>& x)
 130         {
 131                 vector temp(x.begin(), x.end(), x.ebo_);
 132                 init_move(temp);
 133         }
 134
 135         ~vector()
 136         {
 137                 yasli_nstd::destroy(ebo_, ebo_.beg_, size());
 138                 const size_type c = capacity();
 139                 if (c != 0) ebo_.deallocate(ebo_.beg_, c);
 140         }
 141
 142         // Note pass by value
 143         vector<T,Allocator>& operator=(vector<T,Allocator> temp)
 144         {
 145                 temp.swap(*this);
 146                 return *this;
 147         }
 148
 149         template <class InputIterator>
 150         void assign(InputIterator first, InputIterator last)
 151         {
 152
 153                 assign_pre_impl(first, last, Loki::Int2Type<yasli_nstd::
 154                                 is_class<InputIterator>::value||yasli_nstd::
 155                                 is_pointer<InputIterator>::value>());
 156         }
 157
 158 private://-------ASSIGN IMPLEMENTATION
 159         template <class InputIterator, class looks_like_itr>
 160         void assign_pre_impl(InputIterator first, InputIterator last, looks_like_itr)
 161         {
 162                 assign_impl(first, last,
 163                             std::iterator_traits<InputIterator>::iterator_category());
 164         }
 165
 166         template <class InputIterator>
 167         void assign_pre_impl(InputIterator n, InputIterator datum, Loki::Int2Type<false>)
 168         {
 169                 assign((size_type) n, (const T &) datum);
 170         }
 171
 172         template <class InputIterator>
 173         void assign_impl(InputIterator first, InputIterator last, std::input_iterator_tag)
 174         {
 175                 for (iterator i = begin(); i != end(); ++i, ++first)
 176                 {
 177                         if (first == last)
 178                         {
 179                                 resize(i - begin());
 180                                 return;
 181                         }
 182                         *i = *first;
 183                 }
 184                 // we filled up the vector, now insert the rest
 185                 insert(end(), first, last);
 186         }
 187
 188         template <class RanIt>
 189         void assign_impl(RanIt first, RanIt last, std::random_access_iterator_tag)
 190         {
 191                 const typename std::iterator_traits<RanIt>::difference_type d =
 192                     last - first;
 193                 assert(d >= 0);
 194                 size_type newSize = size_type(d);
 195                 assert(newSize == d); // no funky iterators
 196                 reserve(newSize);
 197                 if (newSize >= size())
 198                 {
 199                         const size_t delta = newSize - size();
 200                         RanIt i = last - delta;
 201                         copy(first, i, ebo_.beg_);
 202                         insert(end(), i, last);
 203                 }
 204                 else
 205                 {
 206                         copy(first, last, ebo_.beg_);
 207                         resize(newSize);
 208                 }
 209                 assert(size() == newSize);
 210         }
 211 public:
 212         void assign(size_type n, const T &u)
 213         {
 214                 const size_type s = size();
 215                 if (n <= s)
 216                 {
 217                         T *const newEnd = ebo_.beg_ + n;
 218                         fill(ebo_.beg_, newEnd, u);
 219                         yasli_nstd::destroy(ebo_, newEnd, s - n);
 220                         end_ = newEnd;
 221                 }
 222                 else
 223                 {
 224                         reserve(n);
 225                         T *const newEnd = ebo_.beg_ + n;
 226                         fill(ebo_.beg_, end_, u);
 227                         uninitialized_fill(end_, newEnd, u);
 228                         end_ = newEnd;
 229                 }
 230                 assert(size() == n);
 231                 assert(empty() || front() == back());
 232         }
 233
 234         allocator_type get_allocator() const
 235         {
 236                 return ebo_;
 237         }
 238         // iterators:
 239         iterator begin()
 240         {
 241                 return ebo_.beg_;
 242         }
 243         const_iterator begin() const
 244         {
 245                 return ebo_.beg_;
 246         }
 247         iterator end()
 248         {
 249                 return end_;
 250         }
 251         const_iterator end() const
 252         {
 253                 return end_;
 254         }
 255         reverse_iterator rbegin()
 256         {
 257                 return reverse_iterator(end());
 258         }
 259         const_reverse_iterator rbegin() const
 260         {
 261                 return const_reverse_iterator(end());
 262         }
 263         reverse_iterator rend()
 264         {
 265                 return reverse_iterator(begin());
 266         }
 267         const_reverse_iterator rend() const
 268         {
 269                 return const_reverse_iterator(begin());
 270         }
 271
 272         // 23.2.4.2 capacity:
 273
 274         size_type size() const
 275         {
 276                 return end_ - ebo_.beg_;
 277         }
 278         size_type max_size() const
 279         {
 280                 return ebo_.max_size();
 281         }
 282
 283         void resize(size_type sz, T c = T())
 284         {
 285                 const size_type oldSz = size();
 286                 if (oldSz >= sz)
 287                 {
 288                         erase(ebo_.beg_ + sz, end_);
 289                 }
 290                 else
 291                 {
 292                         reserve(sz);
 293                         uninitialized_fill(end_, end_ + (sz - oldSz), c);
 294                         end_ = ebo_.beg_ + sz;
 295                 }
 296                 assert(size() == sz);
 297         }
 298 private:
 299         template<class is>
 300         void resize_impl(size_type sz, T c)
 301         {
 302         }
 303 public:
 304         size_type capacity() const
 305         {
 306                 return eos_ - ebo_.beg_;
 307         }
 308         bool empty() const
 309         {
 310                 return ebo_.beg_ == end_;
 311         }
 312         void reserve(size_type n)
 313         {
 314                 const size_type
 315                 s = size(),
 316                 c = capacity();
 317                 if (c >= n) return;
 318                 if (capacity() == 0)
 319                 {
 320                         ebo_.beg_ = ebo_.allocate(n);
 321                 }
 322                 else
 323                 {
 324                         ebo_.beg_ = yasli_nstd::allocator_traits<Allocator>::reallocate(
 325                                         ebo_, ebo_.beg_, end_, n);
 326                 }
 327                 end_ = ebo_.beg_ + s;
 328                 eos_ = ebo_.beg_ + n;
 329                 assert(capacity() >= n);
 330                 assert(size() == s);
 331         }
 332         bool reserve_inplace_nstd(size_type n)
 333         {
 334                 if (capacity() >= n) return true;
 335                 if (!yasli_nstd::allocator_traits<Allocator>::reallocate_inplace(
 336                             ebo_, ebo_.beg_, n))
 337                 {
 338                         return false;
 339                 }
 340                 eos_ = ebo_.beg_ + n;
 341                 return true;
 342         }
 343         // element access:
 344         reference operator[](size_type n)
 345         {
 346                 assert(n < size());
 347                 return ebo_.beg_[n];
 348         }
 349         const_reference operator[](size_type n) const
 350         {
 351                 assert(n < size());
 352                 return ebo_.beg_[n];
 353         }
 354         const_reference at(size_type n) const
 355         {
 356                 // Fix by Joseph Canedo
 357                 if (n >= size()) throw std::range_error("vector<>::at");
 358                 return ebo_.beg_[n];
 359         }
 360         reference at(size_type n)
 361         {
 362                 // Fix by Joseph Canedo
 363                 if (n >= size()) throw std::range_error("vector<>::at");
 364                 return ebo_.beg_[n];
 365         }
 366         reference front()
 367         {
 368                 assert(!empty());
 369                 return *ebo_.beg_;
 370         }
 371         const_reference front() const
 372         {
 373                 assert(!empty());
 374                 return *ebo_.beg_;
 375         }
 376         reference back()
 377         {
 378                 assert(!empty());
 379                 return end_[-1];
 380         }
 381         const_reference back() const
 382         {
 383                 assert(!empty());
 384                 return end_[-1];
 385         }
 386
 387 private:
 388
 389         void prepare_growth(size_type delta)
 390         {
 391                 const size_type s = size();
 392                 // @@@ todo: replace magic constant with something meaningful
 393                 const size_type smallThreshold = 8;
 394                 if (s < smallThreshold)
 395                 {
 396                         reserve(std::max(smallThreshold, delta));
 397                 }
 398                 else
 399                 {
 400                         const size_type multiply = 3;
 401                         const size_type divide = 2;
 402                         const size_type suggestedSize = (s * multiply) / divide;
 403                         reserve(std::max(s + delta, suggestedSize));
 404                 }
 405         }
 406
 407 public:
 408         // 23.2.4.3 modifiers:
 409         void push_back(const T &x)
 410         {
 411                 if (size() == capacity())
 412                 {
 413                         prepare_growth(1);
 414                 }
 415                 new(end_) T(x);
 416                 ++end_;
 417         }
 418         void pop_back()
 419         {
 420                 assert(!empty());
 421                 ebo_.destroy(--end_);
 422         }
 423         void move_back_nstd(T &x)
 424         {
 425                 if (size() == capacity())
 426                 {
 427                         prepare_growth(1);
 428                 }
 429                 yasli_protocols::move_traits<T>::nondestructive_move(&x, &x + 1, end_);
 430         }
 431
 432         // 23.2.4.3 modifiers:
 433         iterator insert(iterator position, const T &x)
 434         {
 435                 // @@@ be smarter about this reservation
 436                 reserve(size() + 1);
 437                 const size_type pos = position - begin();
 438                 insert(position, (size_type)1, x);
 439                 return ebo_.beg_ + pos;
 440         }
 441         void insert(iterator position, size_type n, const T &x)
 442         {
 443                 insert(position,
 444                        yasli_nstd::fill_iterator<const T &>(x),
 445                        yasli_nstd::fill_iterator<const T &>(x, n)
 446                       );
 447         }
 448
 449         template <class InputIterator>
 450         void insert(iterator position, InputIterator first, InputIterator last)
 451         {
 452                 insert_pre_impl(position, first, last,
 453                                 Loki::Int2Type<yasli_nstd::is_class<InputIterator>::value||
 454                                 yasli_nstd::is_pointer<InputIterator>::value>());
 455         }
 456 private:
 457         template<class InputIterator, class looks_like_iterator>
 458         void
 459         insert_pre_impl(iterator position, InputIterator first, InputIterator last,
 460                         looks_like_iterator)
 461         {
 462                 insert_impl(position, first, last,
 463                             typename std::iterator_traits<InputIterator>::iterator_category());
 464         }
 465
 466         template <class non_iterator>
 467         void insert_pre_impl(iterator position, non_iterator n, non_iterator x,
 468                              Loki::Int2Type<false>)
 469         {
 470                 //used if e.g. T is int and insert(itr, 10, 6) is called
 471                 insert(position, static_cast<size_type>(n),
 472                        static_cast<value_type>(x));
 473         }
 474
 475         template <class InputIterator>
 476         void insert_impl(iterator position,
 477                          InputIterator first, InputIterator last, std::input_iterator_tag)
 478         {
 479                 for (; first != last; ++first)
 480                 {
 481                         position = insert(position, *first) + 1;
 482                 }
 483         }
 484         template <class FwdIterator>
 485         void insert_impl(iterator position,
 486                          FwdIterator first, FwdIterator last, std::forward_iterator_tag)
 487         {
 488                 typedef yasli_protocols::move_traits<T> mt;
 489
 490                 const typename std::iterator_traits<FwdIterator>::difference_type
 491                 count = std::distance(first, last);
 492
 493                 if (eos_ - end_ > count || reserve_inplace_nstd(size() + count)) // there's enough room
 494                 {
 495                         if (count > end_ - &*position)
 496                         {
 497                                 // Step 1: fill the hole between end_ and position+count
 498                                 FwdIterator i1 = first;
 499                                 std::advance(i1, end_ - &*position);
 500                                 FwdIterator i2 = i1;
 501                                 std::advance(i2, &*position + count - end_);//why not i2 = first; advance(i2,count);
 502                                 T *const oldEnd = end_;
 503                                 end_ = copy(i1, i2, end_);
 504                                 assert(end_ == &*position + count);
 505                                 // Step 2: move existing data to the end
 506                                 mt::nondestructive_move(
 507                                     position,
 508                                     oldEnd,
 509                                     end_);
 510                                 end_ = oldEnd + count;
 511                                 // Step 3: copy in the remaining data
 512                                 copy(first, i1, position);
 513                         }
 514                         else // simpler case
 515                         {
 516                                 mt::nondestructive_move(
 517                                     end_ - count,
 518                                     end_,
 519                                     end_);
 520                                 end_ += count;
 521                                 mt::nondestructive_assign_move(
 522                                     position,
 523                                     end_ - count,
 524                                     position + count);
 525                                 copy(first, last, position);
 526                         }
 527                 }
 528                 else
 529                 {
 530                         vector<T, Allocator> temp(ebo_);
 531                         temp.reserve(size() + count);
 532                         // The calls below won't cause infinite recursion
 533                         //   because they will fall on the other branch
 534                         //   of the if statement
 535                         temp.insert(temp.end(), begin(), position);
 536                         temp.insert(temp.end(), first, last);
 537                         temp.insert(temp.end(), position, end());
 538                         assert(temp.size() == size() + count);
 539                         temp.swap(*this);
 540                 }
 541         }
 542 public:
 543
 544         iterator erase(iterator position)
 545         {
 546                 erase(position, position + 1);
 547                 return position;
 548         }
 549         iterator erase(iterator first, iterator last)
 550         {
 551                 yasli_protocols::move_traits<T>::nondestructive_assign_move(
 552                     last, end(), first);
 553                 Allocator &a = ebo_;
 554                 const size_type destroyed = last - first;
 555                 yasli_nstd::destroy(a, end_ - destroyed, destroyed);
 556                 end_ -= destroyed;
 557                 return first;
 558         }
 559         void swap(vector<T,Allocator>& rhs)//COULD DO THIS WITH LESS TEMPORARIES
 560         {
 561                 std::swap(static_cast<Allocator &>(ebo_), static_cast<Allocator &>(rhs.ebo_));
 562                 std::swap(ebo_.beg_, rhs.ebo_.beg_);
 563                 std::swap(end_, rhs.end_);
 564                 std::swap(eos_, rhs.eos_);
 565         }
 566         void clear()
 567         {
 568                 Allocator &a = ebo_;
 569                 yasli_nstd::destroy(a, ebo_.beg_, size());
 570                 end_ = ebo_.beg_;
 571         }
 572 };//vector
 573
 574
 575
 576 template <class T, class Allocator>
 577 bool operator==(const vector<T,Allocator>& x,
 578                 const vector<T,Allocator>& y);
 579 template <class T, class Allocator>
 580 bool operator< (const vector<T,Allocator>& x,
 581                 const vector<T,Allocator>& y);
 582 template <class T, class Allocator>
 583 bool operator!=(const vector<T,Allocator>& x,
 584                 const vector<T,Allocator>& y);
 585 template <class T, class Allocator>
 586 bool operator> (const vector<T,Allocator>& x,
 587                 const vector<T,Allocator>& y);
 588 template <class T, class Allocator>
 589 bool operator>=(const vector<T,Allocator>& x,
 590                 const vector<T,Allocator>& y);
 591 template <class T, class Allocator>
 592 bool operator<=(const vector<T,Allocator>& x,
 593                 const vector<T,Allocator>& y);
 594 // specialized algorithms:
 595 template <class T, class Allocator>
 596 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
 597
 598 }//yasli
 599
 600
 601
 602 namespace yasli_protocols
 603 {
 604 template <class T, class A>
 605 struct move_traits< yasli::vector<T, A> >:public
 606                 yasli_nstd::type_selector<
 607 sizeof(yasli::vector<T, A>) != (3 * sizeof(T *)),
 608        memmove_traits< std::complex<T> >,
 609        safe_move_traits< std::complex<T> >
 610        >::result
 611        {
 612        };
 613 }
 614
 615 #endif