Помогите решить задачу на СТРУКТУРЫ в C++
задача "Vector" в шаге 4.4(конструкторы и деструкторы) не решается. На обоих тестах(в тестирующей системе) пишет runtime-error.
Условие задачи
Мое решение:
struct vector{
int capacity;
int real;
int* arr;
vector(int m){
capacity = real = m;
arr = new int[capacity];
for (int i = 0; i < real; i++) arr[i] = 0;
}
vector(int m, int val){
capacity = real = m;
arr = new int[capacity];
for (int i = 0; i < real; i++) arr[i] = val;
}
void push_back(int val){
if (real == capacity){
capacity *= 2;
int *new_arr = new int[capacity];
for (int i = 0; i < real; i++){
new_arr[i] = arr[i];
}
arr = new int[capacity];
arr = new_arr;
delete[] new_arr;
}
arr[real] = val;
real++;
}
void pop_back(){
if (real > 0) real--;
}
int get(int i){
if (arr) return arr[i];
}
int size(){
return real;
}
};
Ответы (4 шт):
void push_back (const int val) {
if (real == capacity) {
capacity *= 2;
int* time_arr = nullptr;
try {
time_arr = new int [capacity];
}
catch (const std :: bad_alloc & e) {
capacity /= 2;
return;
}
for (int i = 0; i < real; ++i) {
time_arr [i] = arr [i];
}
delete [] arr;
arr = time_arr;
}
arr [real] = val;
++real;
}
~ vector () {
delete [] arr;
}
arr = new int[capacity];
arr = new_arr;
delete[] new_arr;
}
arr[real] = val;
Фактически тут произошло что:
- Вы выделили память, присвоили ссылку на неё в
arr - Забыли про эту выделенную память, потому что присвоили в
arrссылку на другую область памяти - Удалили ту область памяти, на которую у вас ссылается и
arrиnew_arr - И теперь пишете что-то в эту уже удалённую область памяти
То есть у вас будет и утечка памяти и запись в уже удалённую область памяти.
Как уже подсказали в комментариях, нужно сначала удалить уже не нужную вам область памяти, на которую указывает переменная arr, а потом уже присваивать в неё новую ссылку. Ну и второе выделение памяти лишнее.
// arr = new int[capacity];
delete[] arr;
arr = new_arr;
}
arr[real] = val;
Тестируя так:
int main (void) {
/*
В конструкторе vector(int m) при m = 0 или -1 не выделится память, в for будет ошибка и возникают проблемы.
*/
vector v (0);
vector v2 (-1);
/*
void push_back(int val){
if (real == capacity){
capacity *= 2; //При capacity -1 или 0 capacity не станет больше 0 при этом не выделится память, в for будет ошибка и возникают проблемы.
int *new_arr = new int[capacity];
for (int i = 0; i < real; i++){
new_arr[i] = arr[i];
}
arr = new int[capacity];
arr = new_arr;
delete[] new_arr;
}
arr[real] = val;
real++;
}
*/
v2.push_back (1);
}
Я проверил свой ответ и его было недостаточно.
class vector {
private:
int _size;
int _capacity;
int* arr;
public:
vector (const int quantity) {
if (quantity <= 0) {
_size = 0;
_capacity = 0;
arr = nullptr;
return;
}
else {
_capacity = _size = quantity;
}
arr = new int [_capacity];
for (int i = 0; i < _size; ++i) arr [i] = 0;
}
vector (const int quantity, const int value) {
if (quantity <= 0) {
_size = 0;
_capacity = 0;
arr = nullptr;
return;
}
else {
_capacity = _size = quantity;
}
arr = new int [_capacity];
for (int i = 0; i < _size; ++i) arr [i] = value;
}
void push_back (const int value) {
if (_size == _capacity) {
_capacity ? _capacity *= 2 : _capacity = 1;
int* time_arr = new int [_capacity];
for (int i = 0; i < _size; ++i) {
time_arr [i] = arr [i];
}
delete [] arr;
arr = time_arr;
}
arr [_size] = value;
++_size;
}
void pop_back () {
if (_size >= 1) --_size;
}
int get (const int i) const {
return arr [i];
}
int size () const {
return _size;
}
};
Большие ошибки
push_backудаляет старый массив и новый вместе с ним. Надо как-то так:
void push_back(int val){
if (real == capacity){
capacity *= 2;
int *new_arr = new int[capacity];
for (int i = 0; i < real; i++){
new_arr[i] = arr[i];
}
delete[] arr;
arr = new_arr;
}
arr[real] = val;
real++;
}
- нулевой
capacityвpush_backне приводит к увеличению массива. Можно добавить единичку еслиcapacityбыл нулём:
capacity = 2 * capacity + (capacity == 0);
- компилятор ругается что
getне всегда возвращает значение. В условия сказано что данные всегда корректны, убираемif:
int get(int i){
return arr[i];
}
Ошибки
- При удалении векторов память теряется. Это может не ловиться текущими тестами, но в
push_backмы за памятью следим. Надо бы добавить деструктор, чтобы прибирать за собой:
~vector() {
delete[] arr;
}
- Если скопировать переменную-вектор, то память
arrстанет общей для двух векторов:
vector v1(1); // просто вектор
vector v2(v1); // его копия
v1.push_back(2); // меняем первый вектор
v2.get(0); // второй вектор обращается к удалённой памяти
Это же касается присваивания векторов:
vector v1(1); // просто вектор
vector v2(1); // второй просто вектор
v1 = v2; // память `v1.arr` утеряна; оба вектора делят `arr`
v1.push_back(2); // меняем первый вектор
v2.get(0); // второй вектор обращается к удалённой памяти
Нужно или запретить конструктор копирования и оператор присваивания:
vector(const vector &other) = delete;
vector &operator =(const vector &other) = delete;
Или следовать правилу трёх и определить деструктор, конструктор копирования и оператор присваивания копированием.
Недочёты
- Компилятор использует конструктор для приведений. Нашему вектору можно присвоить число:
vector v(1); // просто вектор
v = 1000; // старое значение вектора выброшено,
// теперь у нас новый вектор с 1000 нулей
Чтобы запретить приведения, первый конструктор можно объявить явным:
explicit vector(int m){
...
}
Поля в классе желательно защитить от случайного доступа снаружи:
private/public.Два конструктора повторяют друг друга почти дословно. Можно обойтись одним:
explicit vector(int m, int val = 0){
capacity = real = m;
arr = new int[capacity];
for (int i = 0; i < real; i++) arr[i] = val;
}
Тут я остановлюсь. А по хорошему надо последовать правилу трёх/пяти и написать конструкторы и прочее, использовать списки инициализации в конструкторах, поддержать константность в векторе, обеспечить гарантии целостности данных в случае исключений, семантику перемещения и swap, сделать запись элементов по индексу. В общем ещё много работы.
