Еще моя версия вектора
Я читаю Принципы программирования и практику с использованием 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_base, A> &’from’ Vector ‘». Я знаю, что * это объект Vector, но b это объект Vector_base, но об этом говорится в книге. Как я могу заставить этот код работать? Есть ли утечка памяти в этом коде? Спасибо!
Решение
Ваш шаблон функции 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 возвращается.
Вот почему вы получаете необработанное исключение.
Другие решения
Есть ли утечка памяти в этом коде?
Да, в вашем коде есть утечки памяти. Например:
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 функция. Это причина номер 1, почему мы используем стандартные контейнеры, а не самодельные.
Например, безопасность исключений является причиной, по которой мы имеем top а также pop в std::stack: если бы были только pop метод, возвращающий копию объекта, что произойдет, если конструкция копии вызовет исключение?
Если вы хотите реализовать свои собственные контейнеры (в качестве упражнения или вдумчивого решения), лучше всего посмотреть на реализацию из вашей стандартной библиотеки. Контейнеры STL являются шаблонами, и весь код находится в заголовочных файлах. Изучите это внимательно, вы узнаете много вещей.