C++ Vector在C++中的实现

Implementation of Vector in C++

提问by UndefinedReference

I recently wrote an implementation of STL Vector as a programming exercise. The program compiles but I receive a strange error saying:

我最近编写了一个 STL Vector 的实现作为编程练习。该程序编译但我收到一个奇怪的错误说：

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

I've never come up with this error before and am not sure what exactly should be changed within my implementation to make it function correctly.

我以前从未想过这个错误，也不确定在我的实现中到底应该更改什么才能使其正常运行。

Can someone take a look through my code and see if anything jumps out at them as wrong in this specific case? Sorry I can't be more specific, I'm not sure where to look myself, thanks in advance.

有人可以查看我的代码，看看在这种特定情况下是否有任何错误？抱歉，我不能说得更具体，我不知道该去哪里找自己，提前致谢。

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

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);      
   ~Vector();

   unsigned int capacity() const;
   unsigned int size() const;
   bool empty() const;
   iterator begin();
   iterator end();
   T & front();
   T & back();
   void push_back(const T & value); 
   void pop_back();  

   void reserve(unsigned int capacity);   
   void resize(unsigned int size);   

   T & operator[](unsigned int index);  
   Vector<T> & operator=(const Vector<T> &);

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

// Your code goes here ...
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-size;
    my_capacity = size;
    buffer = new T [size];
    for (int i = 0; i < size; i++)
        buffer[i] = initial;
        T();
}

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;
    }    
    T * buffer = new T [capacity];
    assert(buffer);
    copy (buffer, buffer + my_size, buffer);
    my_capacity = capacity;
    delete[] buffer;
    buffer = 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);
    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";
}

回答by Phu Ta

Here is the complete source code, updated from your source:

这是完整的源代码，从您的来源更新：

    #pragma once


//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);      
    ~Vector();

    unsigned int capacity() const;
    unsigned int size() const;
    bool empty() const;
    iterator begin();
    iterator end();
    T & front();
    T & back();
    void push_back(const T & value); 
    void pop_back();  

    void reserve(unsigned int capacity);   
    void resize(unsigned int size);   

    T & operator[](unsigned int index);  
    Vector<T> & operator=(const Vector<T> &);
    void clear();
private:
    unsigned int my_size;
    unsigned int my_capacity;
    T * buffer;
};

// Your code goes here ...
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 (unsigned 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 = size;
    my_capacity = size;
    buffer = new T [size];
    for (unsigned int i = 0; i < size; i++)
        buffer[i] = initial;
    //T();
}

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 (unsigned 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>::front()
{
    return buffer[0];
}

template<class T>
T& Vector<T>::back()
{
    return buffer[my_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;
    }    
    T * Newbuffer = new T [capacity];
    //assert(Newbuffer);
    unsigned int l_Size = capacity < my_size ? capacity : my_size;
    //copy (buffer, buffer + l_Size, Newbuffer);

    for (unsigned int i = 0; i < l_Size; i++)
        Newbuffer[i] = buffer[i];

    my_capacity = capacity;
    delete[] buffer;
    buffer = Newbuffer;
}

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;
}
template <class T>
void Vector<T>::clear()
{
    my_capacity = 0;
    my_size = 0;
    buffer = 0;
}

回答by Mark Ransom

Maybe it's this typo?

也许是这个错字？

Vector<T>::Vector(unsigned int size, const T & initial)
{
    my_size-size; 

回答by Erik

Your "reserve" is broken. Use another variable name for the local buffer.

你的“储备”被打破了。为本地缓冲区使用另一个变量名。

回答by Zac Howland

In addition to needing to fix your reservefunction, your copy-constructor and copy-assignment-operator have an interesting problem:

除了需要修复您的reserve函数之外，您的复制构造函数和复制赋值运算符还有一个有趣的问题：

Vector<T> t1 = t2;

This will set the capacity of t1 equal to the capacity (variable) of t2, but the actual capacity of t1 will be the size of t2; Thus, as you start pushing elements onto the vector after the copy-constructor/assignment-operator, you'll have a buffer overrun problem.

这将设置 t1 的容量等于 t2 的容量（变量），但 t1 的实际容量将是 t2 的大小；因此，当您在复制构造函数/赋值运算符之后开始将元素推送到向量上时，您将遇到缓冲区溢出问题。

You need to change it to

你需要把它改成

template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
    my_size = v.my_size;
    my_capacity = v.my_capacity;
    buffer = new T[my_capacity];
    memcpy(buffer, v.buffer, my_size * sizeof(T));  
}

OR (if you want to allow it to resize to a smaller array)

或（如果你想允许它调整为更小的数组）

template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
    my_size = v.my_size;
    my_capacity = v.my_size;
    buffer = new T[my_size];
    memcpy(buffer, v.buffer, my_size * sizeof(T));  
}

回答by Jon Kalb

This code didn't compile for me. Clang complained that line 114 (the implementation of back() ) expected "size" to be called.

这段代码没有为我编译。Clang 抱怨第 114 行（ back() 的实现）期望调用“size”。

I think the line was intended to be "return buffer[size() -1];"

我认为该行的目的是“返回缓冲区 [size() -1];”

It also gives warnings about the implementation of this constructor: template Vector::Vector(unsigned int size, const T & initial)

它还给出有关此构造函数实现的警告：模板 Vector::Vector(unsigned int size, const T & initial)

The first line was probably supposed to be "my_size = size;" The last line (of this constructor) should probably be deleted.

第一行可能应该是“my_size = size;” （此构造函数的）最后一行可能应该被删除。

Next it fails the assertion at line 209: assert(v3.size() == 1);

接下来它使第 209 行的断言失败： assert(v3.size() == 1);

This opens quite a can of worms, but the obvious problem is in resize() at the line: "size = size;" which is probably meant to be "my_size = size;"

这打开了很多蠕虫，但明显的问题是在 resize() 行中：“size = size;” 这可能意味着“my_size = size;”

With this change we now crash on line 121 which is in push_back() called from line 231 "v6.push_back(100);"

通过此更改，我们现在在第 121 行崩溃，该行位于从第 231 行“v6.push_back(100);”调用的 push_back() 中。

This is failing because of problems in reserve(). We are creating a local variable "buffer" with the same name as a member variable. Let's change the name to temp_buffer. Note: Do not assert() run time errors. assert() is for logic errors. This assert() cannot fail. new will never return 0. It will throw instead.

这是由于reserve() 中的问题而失败的。我们正在创建一个与成员变量同名的局部变量“缓冲区”。让我们将名称更改为 temp_buffer。注意：不要 assert() 运行时错误。assert() 用于逻辑错误。这个 assert() 不会失败。new 永远不会返回 0。它会抛出。

After making the obvious fixes in reserve() (there are other issues), we are now crashing in the copy() in reserve() in the call from resize() called from lin3 208 in main(), "v3.resize(1);".

在对reserve() 进行了明显的修复之后（还有其他问题），我们现在在resize() 的调用中在resize() 中的copy() 崩溃了，该调用从main() 中的lin3 208 调用，“v3.resize( 1);"。

We see that reserve is actually allocating a new buffer when we are reducing capacity. This is both a loss of performance and a loss of reliability (memory allocation can fail). But we should still not crash, so we'll try to prevent the crash without addressing the obvious design flaw.

我们看到当我们减少容量时，reserve 实际上是在分配一个新的缓冲区。这既是性能的损失，也是可靠性的损失（内存分配可能会失败）。但是我们仍然不应该崩溃，因此我们将尝试在不解决明显的设计缺陷的情况下防止崩溃。

The crash is coming because we are copying all of the items that exist in the container into the newly allocated array. This would be correct if we were only do this when we need to increase our capacity, but in this case, we have more items than our new capacity can hold. The code should set my_size to the new capacity if it was greater than that value.

崩溃即将到来，因为我们正在将容器中存在的所有项目复制到新分配的数组中。如果我们只在需要增加容量时才这样做，这将是正确的，但在这种情况下，我们拥有的物品超出了新容量所能容纳的数量。如果 my_size 大于该值，则代码应将其设置为新容量。

Now the test code reports "SUCCESS."

现在测试代码报告“成功”。

However there are still many issues with this code.

然而，这段代码仍然存在很多问题。

One of the biggest issues is that we are not using uninitialized memory in the allocated array. Doing this is required by the standard for std::vector and it has both performance and reliability advantages. But it also complicates the code and so this may be a shortcut we can live with for what is obviously an intellectual exercise.

最大的问题之一是我们没有在分配的数组中使用未初始化的内存。这样做是 std::vector 标准所要求的，它具有性能和可靠性优势。但它也使代码复杂化，因此这可能是我们可以忍受的一种捷径，显然是一种智力练习。

Constructors: Use initializer syntax to initialize data members.

构造函数：使用初始化语法来初始化数据成员。

With your copy constructor and your constructor from initial value, you'll leak the allocated array if any of your looped assignments throw an exception.

使用您的复制构造函数和初始值的构造函数，如果任何循环赋值抛出异常，您将泄漏分配的数组。

The assignment operator should allocate a new buffer of size "my_capacity" not "my_size" although there is an obvious optimization that if the size of the right-hand-side object is not greater than the "this" object, we shouldn't be allocating at all.

赋值运算符应该分配一个大小为“my_capacity”而不是“my_size”的新缓冲区，尽管有一个明显的优化，如果右侧对象的大小不大于“this”对象，我们不应该根本分配。

If allocating the new array fails in the assignment operator, we've already deleted the buffer, so we will eventually (when our Vector object is destroyed) have a double delete of the buffer and we may have all hell breaking loose before then.

如果在赋值运算符中分配新数组失败，我们已经删除了缓冲区，所以我们最终（当我们的 Vector 对象被销毁时）会对缓冲区进行双重删除，在那之前我们可能会崩溃。

In push_back(), in order to support the performance guarantees of the standard, we need to increase capacity by some constant fraction of the size of the existing capacity. For example something like: "reserve(my_capacity * 1.5);"

在 push_back() 中，为了支持标准的性能保证，我们需要将容量增加到现有容量大小的一定比例。例如：“reserve(my_capacity * 1.5);”