靈活的安全數組C++

Question

我的safearray可以容納任何類型的數據，如果需要可以調整大小。我所要做的就是如果用戶輸入的數組大小小於for循環中的索引（本例中爲30），它將自行調整大小。但是它太大了，所以我只有很多零。例如，如果我輸入大小15，它將使它的大小爲45，這允許我存儲所有的數據，但我有額外的空間，我不需要。我的TA說這對於一個好的成績來說很好，但是因爲這不是一兩天的時間，所以我希望有一個調整大小的函數，將數組的大小調整爲與索引大小完全一致，而不管用戶輸入的大小是多少。我不知道如何最好地做到這一點。任何幫助？謝謝。

#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乘以多重因爲您將獲得同樣的時間利益，但不會在較大的調整大小上產生太多空間。 （即萬* 2 = 20,000 VS萬* 3 = 30,000節省萬點的空間，你可能不會最終需要）

雖然不直接關係到你的問題，並可能超出範圍的您的實驗室問題，您構建的方式與地圖/散列表類似，因爲您選擇的任何索引都會存儲一些值，但是說您有這種情況。 SafeArray.length是10，並且您將一個項目放置在索引1000.您將結束不調整您的數組足夠大的當前實施SafeArray並出現界限錯誤。即使你調整了足夠的尺寸，也會有10到999個空位，這是一個巨大的浪費，你將不得不記住，你有一些1000的值，而沒有任何值。如果您計劃將此作爲真正的數據結構，則對於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; 
    } 

編輯： 如果你不關心空間爲多，想節省一些時間，並仍然有一個安全的界限分配（有人在你的問題的評論中指出的人），你可以使用以下設置方法：

設置：

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循環添加）。