c++ - 灵活的安全数组 C++

Question

我的 safearray 可以保存任何类型的数据，并且可以根据需要调整大小。我设置它要做的是，如果用户输入的数组大小小于 for 循环中的索引(在本例中为 30)，它将自行调整大小。但是它太大了，所以我只有很多零。例如，如果我输入 15 号，它将变成 45 号，这样我就可以存储所有数据，但我有多余的空间，我不需要。我的助教说这对于一个好成绩来说很好，但是因为它再过几天才到期，我想有一个调整大小的函数，可以将数组的大小调整为与索引的大小完全相同，而不管用户输入的大小是多少.我不确定如何最好地做到这一点。有什么帮助吗？谢谢。

#include <iostream>
using namespace std;


template<typename Element>
class SafeArray
{
   int size;
    Element*Array;
    Element def;

public:
    SafeArray()                         //default constructor(with no parameter)
    {
        Array = new Element[size];
    size = 10;
    }
    SafeArray(int value = NULL)         //constructor with one int
    {
        Array = new Element[value];
        size = value;
    }
    ~SafeArray() { delete [] Array;};                     //destructor

      Element get(int pos)                    //get method
    { if (pos<0)
    {cout<<"error";}

        if(pos>=size)
        { set_default(def);}
        return Array[pos]; }

    void set(int pos, Element val)      //set method
    { if (pos<0)
    {
        cout<<"error";
    }
        if(pos>=size)
    { resize(3); }
        Array[pos] = val; }

    void resize(int size_mult)           //resize function
    {
            Element*temp=new Element[size*size_mult];
            for(int i = 0; i<size;i++)
            {temp[i]=Array[i];}
            delete[]Array;
            Array = temp;
            size=size*size_mult;
        }
    void set_default(Element d)        //set_default(just a safety precaution, doesn't really effect the outcome)
    {
         def=d;
    }
    //Element get_default()
   // {
   //     return def;
   // }
    int get_size()                       //get size
    {
        return size;
    }
};


int main()
{

    int N;
    cout<<"How big should the Array be?"<<endl;
    cin>>N;
    SafeArray<int> X(N);
    SafeArray<double>Y(N);
    X.set_default(-1);
    cout<<"Array is size "<<X.get_size()<<endl;

    for(int i=0; i<30;i++)

    {
        int x=i*3+1;
        double y =1000.0/x;
        X.set(i,x);
        Y.set(i,y);
    }

    for (int i = 0; i <= X.get_size(); i += 1)
        {if(i<10)
            cout <<"0"<< i << ": x = " << X.get(i) << ", 1000/x = " << Y.get(i) << "\n";
        else
        cout << i << ": x = " << X.get(i) << ", 1000/x = " << Y.get(i) << "\n";}
            cout<<"Array is size "<<X.get_size()<<endl;

    return 0;

}

Answer 1

好吧，有些事情需要考虑。

1. 您是想节省空间还是时间复杂度？您现在设置它的方式(将当前长度乘以某个倍数)大大节省了您的时间复杂度，但正如您所指出的那样使用了一些额外的空间。通常，程序员希望将时间复杂度降至最低，但这完全取决于您的目标。

注意:与传递的倍数相比，我只乘以 2 可能是明智的，因为您将获得相同的时间 yield ，但不会在较大的调整大小时产生太多空间。 (即 10,000 * 2 = 20,000 与 10,000 * 3 = 30,000 节省了 10,000 个您可能最终不需要的空间)

1. 虽然与您的问题没有直接关系并且可能不在您的实验室问题的范围内，但您构建它的方式类似于 map /哈希表，因为您选择的任何索引都会存储一些值，但假设您有这种情况。 SafeArray.length 为 10，您将一个项目放置在索引 1000 处。您最终将无法充分调整数组的大小，因为您当前实现的 SafeArray 会出现越界错误。即使你确实调整了它的大小，也会有 10 - 999 的位置都是空的，这是一个巨大的浪费，你必须记住，你在 1000 处有一些值(value)，中间没有任何东西。如果您计划将 SafeArray 用作真正的数据结构，那么一些关于 SafeArray 应该如何工作的额外规则/限制可能是明智的。

现在要真正回答您的问题，最好的方法是创建一个从 0 到索引的 for 循环，然后将值复制到新数组中，并使最后一条语句成为新的赋值。见下文

集合会变成:

void set(int pos, Element val)      //set method
{ if (pos<0)
{
    cout<<"error";
}
    if(pos>=size)
{ resize(pos+1); }
    Array[pos] = val; }

调整大小看起来像这样:

void resize(int new_size)           //resize function
{
        Element*temp=new Element[new_size];
        for(int i = 0; i<new_size;i++)
        {temp[i]=Array[i];}
        delete[]Array;
        Array = temp;
        size=new_size;
    }

编辑:如果您不太关心空间，想要节省一些时间，并且仍然有一个安全的边界分配(有人在对您的问题的评论中指出)，您可以将以下内容用于 Set 方法:

设置:

void set(int pos, Element val)      //set method
{ if (pos<0)
{
    cout<<"error";
}
    if(pos>=size)
{ resize((pos - size) * 2); }
    Array[pos] = val; }

这将为您提供一些额外的空间，并且您可以使用大于 2 的倍数以在顺序情况下获得更好的时间节省(即通过 for 循环添加)。