重寫C++中的Vector

Vector的一種實現

注意幾點：

分配內存不要使用new和delete，因為new的同時就把對象構造了，而我們需要的是原始內存。

所以應該使用標准庫提供的allocator類來實現內存的控制。當然也可以重載operator new操作符，因為二者都是使用malloc作為底層實現，所以直接采用malloc也可以。

對象的復制必須使用系統提供的uninitialized_fill和uninitialized_copy，因為我們無法手工調用構造函數。

對於C++中的對象，除了POD之外，使用memcpy系列的函數是絕對錯誤的。

代碼如下：

#ifndef VECTOR_H_
#define VECTOR_H_

#include 
#include 
#include 

template 
class Vector
{
public:
    typedef T *iterator;
    typedef const T *const_iterator;
    typedef size_t size_type;
    typedef T value_type;

    Vector() { create(); }
    explicit Vector(size_type n, const T &t = T())  { create(n, t); }
    Vector(const Vector &v) { create(v.begin(),  v.end()); }
    ~Vector() { uncreate(); }

    Vector &operator=(const Vector &other);
    T &operator[] (size_type i) { return data_[i]; }
    const T &operator[] (size_type i) const { return data_[i]; }

    void push_back(const T &t);

    size_type size() const { return avail_ - data_; }
    size_type capacity() const { return limit_ - data_; }

    iterator begin() { return data_; }
    const_iterator begin() const { return data_; }
    iterator end() { return avail_; }
    const_iterator end() const { return avail_; }

private:
    iterator data_; //首元素
    iterator avail_; //末尾元素的下一個位置
    iterator limit_; //內存的後面一個位置

    std::allocator alloc_; //內存分配器

    void create();
    void create(size_type, const T &);
    void create(const_iterator, const_iterator);

    void uncreate();

    void grow();
    void uncheckedAppend(const T &);
};

template 
Vector &Vector::operator=(const Vector &rhs)
{
    if(this != &rhs)
    {
        uncreate(); //釋放原來的內存
        create(rhs.begin(), rhs.end());
    }

    return *this;
}

template 
void Vector::push_back(const T &t)
{
    if(avail_ == limit_)
    {
        grow();
    }
    uncheckedAppend(t);
}

template 
void Vector::create()
{
    //分配空的數組
    data_ = avail_ = limit_ = 0;
}

template 
void Vector::create(size_type n, const T &val)
{
    //分配原始內存
    data_ = alloc_.allocate(n);
    limit_ = avail_ = data_ + n;
    //向原始內存填充元素
    std::uninitialized_fill(data_, limit_, val);
}

template 
void Vector::create(const_iterator i, const_iterator j)
{
    data_ = alloc_.allocate(j-i);
    limit_ = avail_ = std::uninitialized_copy(i, j, data_);
}

template 
void Vector::uncreate()
{
    if(data_)
    {
        //逐個進行析構
        iterator it = avail_;
        while(it != data_)
        {
            alloc_.destroy(--it);
        }

        //真正的釋放內存
        alloc_.deallocate(data_, limit_ - data_);
    }
    //重置指針
    data_ = limit_ = avail_ = 0;
}

template 
void Vector::grow()
{
    //內存變為兩倍
    size_type new_size = std::max(2 * (limit_ - data_), std::ptrdiff_t(1));
    //分配原始內存
    iterator new_data = alloc_.allocate(new_size);
    //復制元素
    iterator new_avail = std::uninitialized_copy(data_, avail_, new_data);

    uncreate(); //釋放以前的內存，以及析構元素

    data_ = new_data;
    avail_ = new_avail;
    limit_ = data_ + new_size;
}

template 
void Vector::uncheckedAppend(const T &val)
{
    alloc_.construct(avail_++, val);
}


#endif  /* VECTOR_H_ */

測試代碼如下：

#include "Vector.hpp"
#include 
#include 
using namespace std;

int main(int argc, char const *argv[])
{
    Vector vec(3, "hello");

    for(Vector::const_iterator it = vec.begin();
        it != vec.end();
        ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    cout << "size = " << vec.size() << endl;
    cout << "capacity = " << vec.capacity() << endl;
    vec.push_back("foo");
    vec.push_back("bar");

    cout << "size = " << vec.size() << endl;
    cout << "capacity = " << vec.capacity() << endl;

    return 0;
}