yasli_vector.h

loki库的源代码。loki库是以模板技术和面向对象技术为基础的c++类库。

#include "platform.h"
#include "yasli_fill_iterator.h"
#include "yasli_memory.h"
#include "yasli_traits.h"
#include "yasli_protocols.h"
#include <iterator>
#include <cassert>
#include <stdexcept>
#include "../TypeManip.h"

namespace yasli 
{
    template <class T, class Allocator = allocator<T> >
    class vector;
}

namespace yasli {
     
   template <class T, class Allocator>
   class vector 
   {
       struct ebo : public Allocator
       {
           T *beg_;
           ebo() {}
           ebo(const Allocator& a) : Allocator(a) {}
       } ebo_;
       T *end_;
       T *eos_; 
   public:
       // types:
       typedef          vector<T, Allocator>             this_type;//not standard
       typedef typename Allocator::reference             reference;
       typedef typename Allocator::const_reference       const_reference;
       typedef typename Allocator::pointer               iterator;       // See 23.1
       typedef typename Allocator::const_pointer         const_iterator; // See 23.1
       typedef typename Allocator::size_type             size_type;      // See 23.1
       typedef typename Allocator::difference_type       difference_type;// See 23.1
       typedef          T                                value_type;
       typedef          Allocator                        allocator_type;
       typedef typename Allocator::pointer               pointer;
       typedef typename Allocator::const_pointer         const_pointer;
       typedef std::reverse_iterator<iterator>           reverse_iterator;
       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
   private:
       void init_empty() 
       {
            
   #if YASLI_UNDEFINED_POINTERS_COPYABLE == 1
           end_ = ebo_.beg_;
           eos_ = ebo_.beg_;
   #else   
           ebo_.beg_ = 0;
           end_ = 0;
           eos_ = 0;    
   #endif
           assert(empty());
           
       }
       
       void init_move(vector& temp)
       {
           ebo_ = temp.ebo_;
           end_ = temp.end_;
           eos_ = temp.eos_;
           temp.init_empty();
       }
   
       void init_fill(size_type n, const T& value, const Allocator& a)
       {
           // Will avoid catch (...)
           vector<T, Allocator> temp(a);
           temp.insert(temp.end(), n, value);
           init_move(temp);
           assert(size() == n);
       }
       
       // 23.2.4.1 construct/copy/destroy:
       template <class InputIterator, class looks_like_itr>
       void init(InputIterator first, InputIterator last, looks_like_itr, const Allocator& a)
       {
           vector temp(a);
           temp.insert(temp.end(), first, last);
           init_move(temp);
       }
       
       template <class non_iterator>
       void init(non_iterator n, non_iterator datum, Loki::Int2Type<false>, 
                                                     const Allocator& a)
       {
            init_fill((size_type)n, (const T&)datum, a);
       }
       
   public:
       vector()
       {
           init_empty();
       }
       
       explicit vector(const Allocator& a) 
           : ebo_(a)
       {
           init_empty();
       }
   
       explicit vector(size_type n, const T& value = T(),
               const Allocator& a = Allocator())
       {
           init_fill(n, value, a);
       }
       
       //!! avoid enable_if
       template <class InputIterator>
       vector(InputIterator first, InputIterator last, const Allocator& a = Allocator())
       {                
            init(first, last, Loki::Int2Type<
                       yasli_nstd::is_class<InputIterator>::value || 
                       yasli_nstd::is_pointer<InputIterator>::value >(), a);
       }
       
   public:
       vector(const vector<T,Allocator>& x)
       {
           vector temp(x.begin(), x.end(), x.ebo_);
           init_move(temp);
       }
   
       ~vector()
       {
           yasli_nstd::destroy(ebo_, ebo_.beg_, size());
           const size_type c = capacity();
           if (c != 0) ebo_.deallocate(ebo_.beg_, c);
       }
   
       // Note pass by value
       vector<T,Allocator>& operator=(vector<T,Allocator> temp)
       {
           temp.swap(*this);
           return *this;
       }
   
       template <class InputIterator>   
       void assign(InputIterator first, InputIterator last)
       {
                     
           assign_pre_impl(first, last, Loki::Int2Type<yasli_nstd::
                                  is_class<InputIterator>::value||yasli_nstd::
                                  is_pointer<InputIterator>::value>());
       }
       
   private://-------ASSIGN IMPLEMENTATION
       template <class InputIterator, class looks_like_itr>
       void assign_pre_impl(InputIterator first, InputIterator last, looks_like_itr)
       {    
            assign_impl(first, last,
               std::iterator_traits<InputIterator>::iterator_category());
       }
       
       template <class InputIterator>
       void assign_pre_impl(InputIterator n, InputIterator datum, Loki::Int2Type<false>)
       {    
            assign((size_type) n, (const T&) datum);
       }
   
       template <class InputIterator>
       void assign_impl(InputIterator first, InputIterator last, std::input_iterator_tag)
       {
           for (iterator i = begin(); i != end(); ++i, ++first)
           {
               if (first == last) 
               {
                   resize(i - begin());
                   return;
               }
               *i = *first;
           }
           // we filled up the vector, now insert the rest
           insert(end(), first, last);
       }
   
       template <class RanIt>
       void assign_impl(RanIt first, RanIt last, std::random_access_iterator_tag)
       {
           const typename std::iterator_traits<RanIt>::difference_type d = 
               last - first;
           assert(d >= 0);
           size_type newSize = size_type(d);
           assert(newSize == d); // no funky iterators
           reserve(newSize);
           if (newSize >= size())
           {
               const size_t delta = newSize - size();
               RanIt i = last - delta;
               copy(first, i, ebo_.beg_);
               insert(end(), i, last);
           }
           else
           {
               copy(first, last, ebo_.beg_);
               resize(newSize);
           }
           assert(size() == newSize);
       }
   public:
       void assign(size_type n, const T& u)
       {
           const size_type s = size();
           if (n <= s)
           {
               T* const newEnd = ebo_.beg_ + n;
               fill(ebo_.beg_, newEnd, u);
               yasli_nstd::destroy(ebo_, newEnd, s - n);
               end_ = newEnd;
           }
           else
           {
               reserve(n);
               T* const newEnd = ebo_.beg_ + n;
               fill(ebo_.beg_, end_, u);
               uninitialized_fill(end_, newEnd, u);
               end_ = newEnd;
           }
           assert(size() == n);
           assert(empty() || front() == back());
       }
   
       allocator_type get_allocator() const
       {
           return ebo_;
       }
       // iterators:
       iterator begin() { return ebo_.beg_; }
       const_iterator begin() const { return ebo_.beg_; }
       iterator end() { return end_; }
       const_iterator end() const { return end_; }
       reverse_iterator rbegin() { return reverse_iterator(end()); }
       const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
       reverse_iterator rend() { return reverse_iterator(begin()); }
       const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
   
       // 23.2.4.2 capacity:
   
       size_type size() const { return end_ - ebo_.beg_; }
       size_type max_size() const { return ebo_.max_size(); }
   
       void resize(size_type sz, T c = T()) 
       {
           const size_type oldSz = size();
           if (oldSz >= sz)
           {
               erase(ebo_.beg_ + sz, end_);
           }
           else
           {
               reserve(sz);
               uninitialized_fill(end_, end_ + (sz - oldSz), c);
               end_ = ebo_.beg_ + sz;
           }
           assert(size() == sz);
       }
   private:
       template<class is>
       void resize_impl(size_type sz, T c)
       {
       }
   public:
       size_type capacity() const
       {
           return eos_ - ebo_.beg_; 
       }
       bool empty() const
       {
           return ebo_.beg_ == end_; 
       }
       void reserve(size_type n)
       {
           const size_type 
               s = size(),
               c = capacity();
           if (c >= n) return;
           if (capacity() == 0)
           {
               ebo_.beg_ = ebo_.allocate(n);
           }
           else
           {
               ebo_.beg_ = yasli_nstd::allocator_traits<Allocator>::reallocate(
                   ebo_, ebo_.beg_, end_, n);
           }