3

我正在阅读 Programming Pciples and Practice Using 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 对象，但这就是书上所说的。我怎样才能使这段代码工作？这段代码有内存泄漏吗？谢谢！

4

2 回答 2

2

您的 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)

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

更新 1

此外，您仍在将newanddelete运算符与Vector 的赋值运算符中的alloc.allocate()and混合使用。alloc.deallocate()

更新 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。

这就是为什么你会得到一个未处理的异常。

于 2012-10-12T10:18:26.257 回答
0

这段代码有内存泄漏吗？

是的，您的代码存在内存泄漏。例如：

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]); <--- what happens here
                                                  if construction fails ?
    elem = p;
    sz = arg.sz;
    space = arg.space;
};

如果复制构造函数抛出异常，就会泄漏分配的内存以及已经构造的对象所持有的任何资源。

治疗方法是：

for (int i = 0; i < arg.sz; ++i)
{
    try { alloc.construct (&p[i], arg.elem[i]); }
    catch (...)
    {
        // 1) Destroy the allocated objects
        while (--i != 0) alloc.destroy (&p[i]);

        // 2) Release p
        alloc.deallocate (p, arg.sz);

        // 3) rethrow exception
        throw; 
    }
}

您必须在整个代码中始终如一地执行此操作，而不仅仅是在copy函数中。这是我们使用标准容器而不是自制容器的第一大原因。

例如，异常安全是我们拥有topand popin的原因std::stack：如果只有一个pop方法返回对象的副本，如果复制构造抛出异常会发生什么？

如果您想实现自己的容器（作为练习或深思熟虑的决定），最好从标准库中查看实现。STL 容器是模板，所有代码都驻留在头文件中。仔细研究，你会学到很多东西。

于 2012-10-12T11:28:32.640 回答