循環迭代在C++

我正在C++中使用動態分配的數組構建一個簡單的列表。我有一個功能remove(int item)應刪除列表中出現的所有item。但是，如果我做一個循環，迭代從0到陣列中length，我擔心我會超過我的數組的邊界，因爲length變化我刪除項目：循環迭代在C++

int List::pop(int index) 
{ 
    int retval = data[index]; 
    for (int i = index; i < length; i++) 
    data[i] = data[i+1]; 
    length--; 
    return retval; 
} 

void List::remove(int item) 
{ 
    for (int i = 0; i < length; i++) { 
    if (data[i] == item) 
     pop(i); 
}

所以，如果我叫remove(6)在array[6][4][2][6][1][3][5][6]上，C++會更新remove()中的for循環，更新後的值爲length後pop()？或者它會保持原來傳遞給它的相同的值，當調用remove()時？

來源

2011-04-01 Andrew

所以我想簡單一點來說，在這種情況下是C++調用值還是調用引用？ – Andrew 2011-04-01 04:03:32

該算法具有O（N^2）性能，因爲即使有多個項目副本，pop（）也會一次一步地複製其餘值。通過保留「打包」數據的索引並直接複製'！= item'元素，您可以輕鬆獲得單次O（N）解決方案。 – 2011-04-01 04:32:59

另一種解決方案是搜索相反的結果。只保留那些不相同的項目將被刪除。

void List::remove(int item) 
{ 
    int insert = 0; 
    for (int i = 0; i < length; i++) { 
     if (data[i] != item) 
      data[insert++] = data[i]; 
    } 
    length = insert; 
}

來源

2011-04-01 04:27:06 jfs

我認爲這是唯一不做任何浪費工作的方法。沒有任何東西移動一次以上。非常好。 – 2011-04-01 05:13:26

從數組的末尾開始，向後回到起始位置。或者，撥打pop(i--)而不是pop(i)。這將備份i，因此您不會跳過列表中的任何元素（包括最後一項）。

第一種方法的優點是您不會浪費時間往下移動最終要移除的元素。

來源

2011-04-01 04:04:43

條件表達式i < length在循環的每次迭代之前都會對其進行評估。 C++編譯器不會緩存i，也不會將此評估緩存爲length。只要length變量正確更新，此表達式將不允許i超出數組的界限。

雖然這不會幫助跳過元素的問題。要做到這一點，我會切換到一個while循環。

int i = 0; 
while (i < length) { 
    if (data[i] == item) { 
    pop(i); 
    } else { 
    i++; 
    } 
}

在這種情況下，我們不增加，如果我們pop一個項目。這樣，索引保持在同一位置，並且能夠捕獲在陣列中彼此相鄰的重複項目

來源

2011-04-01 04:05:29 JaredPar

他的問題並沒有真正走過名單的末尾;它會跳過跟隨任何已刪除元素的每個元素。 – 2011-04-01 04:08:04

@Ted，已更新，以解釋這一點。 – JaredPar 2011-04-01 04:11:19

+1 While循環在這裏也適用於循環，因爲它提示讀者在迭代開始時迭代次數不固定。當寫成for循環時，這並不明顯。 – 2011-04-01 04:15:19

循環迭代在C++

回答

相關問題