3

Programming Priciples and Practice Using C++ Chapter 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

スワップ関数テンプレートは として定義されていtemplate<class T, class A>ます。したがって、次のように呼び出す必要がありますSwap<T,A>(*this, b);。Swap<Vector_base<T,A>>(*this, b);

そして実際、呼び出しSwap<T,A>(*this, b)はまったく正しくありません。要求されたサイズのメモリを割り当て、既存の要素を新しい領域にコピーする必要があります。次に、最初に割り当てたメモリを解放します。

2番目の問題は次のとおりです。

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

const オブジェクトで非 const メンバー関数を呼び出すことはできません。したがって、alloc.allocate(n)代わりに使用しa.allocate(n)ます。

更新 1

また、 Vector の代入演算子にandnew演算子deleteをまだ混在させています。alloc.allocate()alloc.deallocate()

更新 2

代入演算子は に対して定義されていますが、Swap<T, A>実際には で作業しているため、代入演算子が呼び出されることはありません。そうなります。Vector_baseVectorMemberwise 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.deallocate2 回呼び出されます。最初~Vector_base()に呼び出されるのは、返されるときcに範囲外になるときだからです。Swapそして、2回目のデストラクタは、返さ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ます。これが、自家製の容器ではなく標準の容器を使用する一番の理由です。

topたとえば、例外の安全性がとpopinの理由std::stackです: オブジェクトのコピーを返すメソッドしかpopない場合、コピーの構築で例外がスローされるとどうなるでしょうか?

独自のコンテナーを (演習として、または熟慮した決定として) 実装したい場合は、標準ライブラリーからの実装を確認することをお勧めします。STL コンテナーはテンプレートであり、すべてのコードはヘッダー ファイルに存在します。注意深く勉強してください。多くのことを学ぶことができます。

于 2012-10-12T11:28:32.640 に答える