c++ - 仍然是我的 Vector 版本

Question

我正在阅读编程原理和使用 C++ 的实践第 17-19 章，并尝试编写我的 Vector 版本。这是我的代码:

#include <stdexcept>
#include <exception>

using namespace std;

struct Range_error:out_of_range{
    int index;
    Range_error(int i):out_of_range("Range error"),index(i){}
};

template<class T, class A = allocator<T>> struct Vector_base{
    A alloc;
    T* elem;
    int sz;                                                     // number of elements
    int space;                                                  // number of elements plus "free space"/"slots" for new elements("the current allocation")

    void copy(const Vector_base& arg)
    {
        T* p = alloc.allocate(arg.sz);
        for(int i=0; i<arg.sz; ++i) alloc.construct(&p[i], arg.elem[i]);
        elem = p;
        sz = arg.sz;
        space = arg.space;
    };

    Vector_base(): elem(alloc.allocate(0)), sz(0), space(0) {};
    Vector_base(int n):elem(alloc.allocate(n)), sz(n), space(n) {};
    Vector_base(const A& a, int n):alloc(a), elem(a.allocate(n)), sz(n), space(n){};
    Vector_base(const Vector_base& arg) {copy(arg);}
    ~Vector_base() {alloc.deallocate(elem, space);}
};

template<class T, class A = allocator<T>> class Vector : private Vector_base<T,A>{
public:
    Vector() : Vector_base(){};
    Vector(int n) : Vector_base(n) {for(int i=0; i<this->sz; ++i) this->alloc.construct(&this->elem[i], T());}
    Vector(const Vector& arg) : Vector_base(arg) {};
    Vector& operator=(const Vector&);

    ~Vector() {};

    int size() const {return this->sz;}
    int capacity() const {return this->space;}

    void resize(int newsize, T val=T());
    void push_back(const T& val);
    void pop_back();                                                // delete the last element
    void reserve(int newalloc);

    T& operator[](unsigned int n) 
    {
        return this->elem[n];   
    }

    const T& operator[](unsigned int n) const 
    {
        return this->elem[n];   
    }

    T& at(unsigned int n)
    {
        if(n<0 || this->sz<=n) throw Range_error(n);
        return this->elem[n];
    }

    const T& at(unsigned int n) const
    {
        if(n<0 || this->sz<=n) throw Range_error(n);
        return this->elem[n];
    }
};

template<class T, class A> void Swap(Vector_base<T,A>& a, Vector_base<T,A>& b){
    Vector_base<T,A> c(a);
    a=b;
    b=c;
}

template<class T, class A> Vector<T,A>& Vector<T,A>::operator=(const Vector<T,A>& a)
{
    if(this == &a) return *this;                                    // self-assignment, no work needed

    if(a.sz<=sz){
        for(int i=0; i<a.sz; ++i) elem[i] = a.elem[i];
        sz=a.sz;
        return *this;
    }

    T* p = new T[a.sz];
    for(int i=0; i<a.sz; ++i) p[i] = a.elem[i];
    delete elem;
    elem=p;
    space=sz = a.sz;
    return *this;

}

template<class T, class A> void Vector<T,A>::reserve(int newalloc)
{
    if(newalloc <= this->space) return;
    Vector_base<T,A> b(this->alloc,newalloc);
    for(int i=0; i<this->sz; ++i) this->alloc.construct(&b.elem[i], this->elem[i]);     // copy
    for(int i=0; i<this->sz; ++i) this->alloc.destroy(&this->elem[i]);

    Swap<Vector_base<T,A>>(*this, b);
    this->space = newalloc;
}

template<class T, class A> void Vector<T,A>::resize(int newsize, T val=T())
{
    reserve(newsize);
    for(int i=this->sz; i<newsize; ++i) this->alloc.construct(&this->elem[i], val);
    for(int i=newsize; i<this->sz; ++i) this->alloc.destroy(&this->elem[i]);
    this->sz = newsize;
}

template<class T, class A> void Vector<T,A>::push_back(const T& val)
{
    if(this->space == 0) reserve(8);
    else if(this->sz == this->space) reserve(2*(this->space));
    this->alloc.construct(&this->elem[this->sz], val);
    ++(this->sz);
}

template<class T, class A> void Vector<T,A>::pop_back()
{
    if(this->sz == 0) return;
    this->alloc.destroy(&this->elem[--(this->sz)]);
    if(this->sz <= (this->space)/2)
    {
        Vector_base<T,A> b(this->alloc,(this->space)/2);
        for(int i=0; i<this->sz; ++i) this->alloc.construct(&b.elem[i], this->elem[i]);     // copy
        for(int i=0; i<this->sz; ++i) this->alloc.destroy(&this->elem[i]);

        Swap<Vector_base<T,A>>(*this, b);

        this->space /= 2;
    }
}

编译时，vc++ 提示“void Swap(Vector_base &,Vector_base &)':无法从‘Vector’推断出‘Vector_base,A> &’的模板参数”。我知道 *this 是一个 Vector 对象，但 b 是 Vector_base 对象，但书上是这么说的。我怎样才能使这段代码工作？这段代码有内存泄漏吗？谢谢!

Answer 1

您的 Swap 函数模板定义为 template<class T, class A> .所以你应该这样调用它:Swap<T,A>(*this, b);而不是 Swap<Vector_base<T,A>>(*this, b);

实际上，调用 Swap<T,A>(*this, b)根本不正确。您应该分配请求大小的内存并将现有元素复制到新空间。然后释放您最初分配的内存。

第二个问题在:

Vector_base(const A& a, int n)
 : alloc(a), elem(a.allocate(n)), sz(n), space(n)

您不能在常量对象上调用非常量成员函数。所以，使用 alloc.allocate(n)而不是 a.allocate(n) .

更新 1

还有，你还在混new和 delete运算符 alloc.allocate()和 alloc.deallocate()在 Vector 的赋值运算符中。

更新 2

您的赋值运算符将永远不会在 Swap<T, A> 中被调用因为你实际上是在使用 Vector_base , 而赋值运算符是为 Vector 定义的.所以 Memberwise assignment 将会发生。

template<class T, class A> void Swap(Vector_base<T,A>& a, Vector_base<T,A>& b){
    Vector_base<T,A> c(a);
    a=b;
    b=c;
}

即b.elem和 c.elem将指向相同的地址和alloc.deallocate将为此被调用两次。因为第一次~Vector_base()将在 c 时调用当 Swap 时将超出范围返回。第二次析构函数将在 b 时被调用。当 reserve 时将超出范围返回。

这就是您得到未处理异常的原因。