Возникли проблемы с двумя функциями в реализации вектора в C ++

Question

Я написал реализацию вектора, которая компилируется, но не работает должным образом в соответствии с программой main(), которую мне дали.

Я уверен, что ошибка в моей push_back() функции или в моей reserve() функции, но я не уверен, что именно это не так.

Может кто-нибудь посмотреть через две функции и сказать мне, если что-то отсутствует или нужно изменить?

#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
#include <cstring>



// Vector.h

using namespace std;

template <class T>
class Vector
{
public:

   typedef T * iterator;

   Vector();
   Vector(unsigned int size);
   Vector(unsigned int size, const T & initial);
   Vector(const Vector<T> & v);           // copy constructor//Done
   ~Vector();

   unsigned int capacity() const;         // return capacity of vector (in elements)//Done
   unsigned int size() const;             // return the number of elements in the vector//Done
   bool empty() const;

   iterator begin();                      // return an iterator pointing to the first element // Done
   iterator end();                        // return an iterator pointing to one past the last element //Done
   T & front();                           // return a reference to the first element //Done
   T & back();                            // return a reference to the last element //Done
   void push_back(const T & value);       // add a new element //Done
   void pop_back();                       // remove the last element //Done

   void reserve(unsigned int capacity);   // adjust capacity //Done
   void resize(unsigned int size);        // adjust size //Done

   T & operator[](unsigned int index);    // return reference to numbered element
   Vector<T> & operator=(const Vector<T> &);

private:
   unsigned int my_size;
   unsigned int my_capacity;
   T * buffer;
};

template<class T>//
Vector<T>::Vector()
{
    my_capacity = 0;
    my_size = 0;
    buffer = 0;
}

template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
    my_size = v.my_size;
    my_capacity = v.my_capacity;
    buffer = new T[my_size]; 
    for (int i = 0; i < my_size; i++)
        buffer[i] = v.buffer[i];  
}

template<class T>//
Vector<T>::Vector(unsigned int size)
{
    my_capacity = size;
    my_size = size;
    buffer = new T[size];
}

template<class T>//
Vector<T>::Vector(unsigned int size, const T & initial)
{
    my_size;
    my_capacity = size;
    buffer = new T [size];
    for (int i = 0; i < size; i++)
        buffer[i] = initial;
}

template<class T>//
Vector<T> & Vector<T>::operator = (const Vector<T> & v)
{
    delete[ ] buffer;
    my_size = v.my_size;
    my_capacity = v.my_capacity;
    buffer = new T [my_size];
    for (int i = 0; i < my_size; i++)
        buffer[i] = v.buffer[i];
    return *this;
}

template<class T>//
typename Vector<T>::iterator Vector<T>::begin()
{
    return buffer;
}

template<class T>//
typename Vector<T>::iterator Vector<T>::end()
{
    return buffer + size();
}

template<class T>//
T& Vector<T>::Vector<T>::front()
{
    return buffer[0];
}

template<class T>//
T& Vector<T>::Vector<T>::back()
{
    return buffer[size - 1];
}

template<class T>
void Vector<T>::push_back(const T & v)
{
    if (my_size >= my_capacity)
    reserve(my_capacity +5);
    buffer [my_size++] = v;
}

template<class T>//
void Vector<T>::pop_back()
{
    my_size--;
}

template<class T>//
void Vector<T>::reserve(unsigned int capacity)
{
    if(buffer == 0)
    {
        my_size = 0;
        my_capacity = 0;
    }    
    if (capacity <= my_capacity)
    return;
    T * new_buffer = new T [capacity];
    assert(new_buffer);
    copy (buffer, buffer + my_size, new_buffer);
    my_capacity = capacity;
    delete[] buffer;
    buffer = new_buffer;

}

template<class T>//
unsigned int Vector<T>::size()const
{
    return my_size;
}

template<class T>//
void Vector<T>::resize(unsigned int size)
{
    reserve(size);
    my_size = size;
}

template<class T>//
T& Vector<T>::operator[](unsigned int index)
{
    return buffer[index];
}  

template<class T>//
unsigned int Vector<T>::capacity()const
{
    return my_capacity;
}

template<class T>//
Vector<T>::~Vector()
{
    delete[]buffer;
}

int main()
{  

   Vector<int> v;

   v.reserve(2);
   assert(v.capacity() == 2);

   Vector<string> v1(2);
   assert(v1.capacity() == 2);
   assert(v1.size() == 2);
   assert(v1[0] == "");
   assert(v1[1] == "");

   v1[0] = "hi";
   assert(v1[0] == "hi");

   Vector<int> v2(2, 7);
   assert(v2[1] == 7);

   Vector<int> v10(v2);
   assert(v10[1] == 7);

   Vector<string> v3(2, "hello");
   assert(v3.size() == 2);
   assert(v3.capacity() == 2);
   assert(v3[0] == "hello");
   assert(v3[1] == "hello");

   v3.resize(1);
   assert(v3.size() == 1);
   assert(v3[0] == "hello");

   Vector<string> v4 = v3;
   assert(v4.size() == 1);
   assert(v4[0] == v3[0]);
   v3[0] = "test";
   assert(v4[0] != v3[0]);  
   assert(v4[0] == "hello");

   v3.pop_back();
   assert(v3.size() == 0);

   Vector<int> v5(7, 9);
   Vector<int>::iterator it = v5.begin();
   while (it != v5.end())
   {
      assert(*it == 9);
      ++it;
   }

   Vector<int> v6;
   v6.push_back(100);
   assert(v6.size() == 1);
   assert(v6[0] == 100);
   v6.push_back(101);
   assert(v6.size() == 2);
   assert(v6[0] == 100);
   v6.push_back(101);

   cout << "SUCCESS\n";
}

Answer 1

Я думаю, что ваша проблема в этом коде:

template<class T>//
Vector<T>::Vector(unsigned int size, const T & initial)
{
    my_size;
    my_capacity = size;
    buffer = new T [size];
    for (int i = 0; i < size; i++)
        buffer[i] = initial;
}

Обратите внимание, что эта первая строка

my_size;

не имеет никакого эффекта.Я думаю, что вы хотели написать

my_size = size;

Когда я сделал это на моей машине, это решило проблему, и все тесты прошли.Valgrind подтверждает отсутствие утечек или повреждения памяти.

Однако есть несколько других частей этого кода, которые вы, возможно, захотите изучить.Вот краткий контрольный список вещей, на которые следует обратить внимание:

1. В своем коде для reserve вы выделяете буфер, записывая T* new_buffer = new T[capacity], а затем используете assert, чтобы подтвердить, чтобуфер не является NULL.В C ++, когда вы выделяете память с помощью new или new[], вы никогда не получите указатель NULL;вместо этого программа выдаст исключение bad_alloc в случае неудачного размещения.Вы можете явно запросить получение памяти таким способом, который никогда не вызывает исключение, но это, вероятно, не то, что вы хотите сделать здесь.

2. У вас есть конструктор с одним аргументом Vector(unsigned int size)это не отмечено explicit.Это означает, что C ++ будет рассматривать его как конструктор неявного преобразования и позволит вам писать код, подобный Vector<int> v = 137;, так как компилятор интерпретирует это как Vector<int> v(137).Вероятно, это не то, что вы намеревались, поэтому я бы предложил пометить конструктор explicit, чтобы запретить такое поведение.

3. Ваш код для обеспечения наличия достаточного пространства в Vector:Действителен, но ваша стратегия роста не очень эффективна.В частности, если вы продолжите увеличивать вектор на пять элементов за раз, тогда время, необходимое для выполнения n push_back с, будет равно O (n ² ), что не очень хорошо.Более распространенная стратегия - удваивать размер вектора, когда вам нужно пространство.Используя амортизированный анализ , вы можете показать, что это означает, что n вставок занимает только O (n) время, что значительно лучше, чем ваш текущий подход.

4. ВашОператор присваивания (operator =) содержит ошибку, которая приведет к неопределенному поведению, если вы назначите вектор себе, написав что-то вроде v = v.Причина этого в том, что ваш оператор присваивания delete[] s буфера, а затем пытается скопировать из другого объекта.Однако, если другой объект идентичен вашему собственному объекту, вы будете пытаться считывать только что удаленный указатель.Чтобы это исправить, вы можете заключить код в operator= в галочку if (this != &v).Это означает, что если вы когда-нибудь попытаетесь присвоить Vector самому себе, он не будет работать вместо сбоя во время выполнения.

Надеюсь, это поможет!

Answer 2

На первый взгляд эта строка my_size; в Vector<T>::Vector(unsigned int size, const T & initial) кажется мне очень странной. Вы, вероятно, имели в виду это my_size = size;

Answer 3

Я не пробовал отлаживать ваш код для проверки, но с первого взгляда push_back и reserve выглядят хорошо для ваших целей (я предполагаю, что вас не волнует безопасность исключений или уничтожение удаленных объектов в подходящем / ожидаемом время).

Однако я вижу несколько явных логических проблем в реализациях:

• template<class T> Vector<T>::Vector(const Vector<T> & v) и template<class T> Vector<T> & Vector<T>::operator = (const Vector<T> & v): что происходит, когда по умолчанию создается и пусто Vector копируется / назначается?
• template<class T> Vector<T>::Vector(unsigned int size): что происходит, когда размер == 0?
• template<class T> Vector<T>::Vector(unsigned int size, const T & initial): то же, что и выше, и my_size; как отдельное утверждение кажется совершенно неправильным
• resize: resize должно уменьшить Vector (уменьшить его емкость), reserve не