Java（如果你知道的話，還有 C#）中是否有一個可以迭代的集合數據結構，具有以下屬性：可以刪除當前元素而不影響當前迭代器（已啟動的迭代器的其余迭代）?？梢蕴砑有略?，但也不會影響當前迭代器——在當前迭代器的迭代仍在進行時，不會將其作為迭代值包含在內。在我的例子中，每次迭代只會添加一個新元素，但在從可迭代對象中獲取新迭代器之前，不會看到任何新元素。元素的順序無關緊要。實際上，有一個傳入列表和一個傳出項目列表。傳入的列表被迭代，一些被復制到一個新的列表中。一些新元素可以在迭代期間添加到新列表中。迭代結束后，舊的傳入列表被新的傳出列表替換。這整個過程本身就是一個循環。因此，與具有這些添加/刪除屬性的集合對象相比，每次將元素復制到新構建的集合對象似乎效率低下。我在想某種隊列，它可以讓我預覽當前項目，然后要么出隊，要么不退出，然后移動到下一個項目。而且我可以將更多項目添加到隊列的頭部，但不會看到它們，因為我正在向最后移動。雙向鏈表可以具有這些屬性，對嗎？如果您真的想知道它的用途，那就是在我的答案中增加第二個大代碼塊。
3 回答
波斯汪
TA貢獻1811條經驗 獲得超4個贊
在 C# 中，這很容易使用List<T>andfor (...)而不是foreach (...)：
using System;
using System.Collections.Generic;
using System.Linq;
namespace Demo
{
static class Program
{
static void Main()
{
List<int> list = Enumerable.Range(1, 10).ToList();
for (int i = 0; i < list.Count; ++i)
{
if ((list[i] % 3) == 0) // Remove multiples of 3.
list.RemoveAt(i--); // NOTE: Post-decrement i
else if ((list[i] % 4) == 0) // At each multiple of 4, add (2*value+1)
list.Add(list[i] * 2 + 1);
else
; // Do nothing.
}
Console.WriteLine(string.Join(", ", list)); // Outputs 1, 2, 4, 5, 7, 8, 10, 17
}
}
}
這里的關鍵是使用索引而不是foreach，并且在當前索引之前不要更改任何內容（從閱讀您的要求來看，不需要）。
但是，如果您確實需要在當前索引之前添加或刪除元素，那么這種方法就不起作用（或者至少，它變得更加復雜）。
ibeautiful
TA貢獻1993條經驗 獲得超6個贊
對于 C#，您可以LinkedList<T>像在好的 ol' C 中一樣使用：
public DoStuff<T>(LinkedList<T> list)
{
var node = list.First;
while(node != null)
{
// do stuff with node
node = node.Next;
}
}
該node是類型LinkedListNode<T>。您可以使用 訪問該值node.Value，使用 刪除list.Remove(node)。對于T elem你也有list.AddAfter(node, elem)，list.AddBefore(node, elem)，list.AddFirst(elem)和list.AddLast(elem)。所有這些操作都是 O(1)。你可以用它做各種迭代，如果你只想迭代原始元素，然后在做任何事情之前緩存下一個節點并記住最后一個節點：
var lastNode = list.Last;
var node = list.First;
while(node != lastNode.Next)
{
var nextNode = node.Next;
// do stuff with node
node = nextNode;
}
Java 中的等價數據結構也稱為LinkedList<E>. 但是，ListIterator<E>使用標準List<E>可能更清潔。
牧羊人nacy
TA貢獻1862條經驗 獲得超7個贊
在 java 中有CopyOnWriteArrayList 可以滿足您的要求：每次更改任何內容時，它都會復制支持數組。但這確實意味著一旦您開始迭代，任何迭代都是“一成不變的”，因此您可以隨意刪除/添加到底層集合，而不會影響任何正在運行的迭代器。
您還可以構建自己的具有此行為的集合類型。這將是一個 3 班輪：
public class ConstantIterationArrayList<T> extends ArrayList<T> {
public Iterator<T> iterator() {
return new ArrayList<T>(this).iterator();
}
}
（上面創建了列表的副本，然后為您提供了副本的迭代器，從而方便地確保對該列表的任何修改絕對不會對該迭代器產生影響）。
這是您問題的真正問題：
以上將不時復制底層數據存儲（我上面的代碼片段每次創建迭代器時都會這樣做。CopyOnWriteArrayList每次調用remove()或時都會這樣做add()）?！皬椭频讓訑祿鎯Α辈僮餍枰狾(n)時間，例如，兩倍大的列表需要兩倍的時間。
ArrayList通常remove()，除非您要刪除列表末尾或非常接近末尾的元素，否則該操作的屬性是O(n)操作：如果列表是列表的兩倍，則從列表中刪除元素需要兩倍的時間大。
幸運的是，現代 CPU 具有相當大的緩存，并且可以在緩存頁面內以極快的速度運行。翻譯為：盡管數據復制過的感覺效率不高，在實踐中，只要在頁面左右的時間內支持數組的配合，這是很多快于基于數據存儲的LinkedList語義。我們正在談論最多約 1000 個元素的給予或接受。（請注意，一般來說，您對 a 所做的幾乎所有事情LinkedList都是O(n)并且在ArrayList現代 CPU 架構中往往能很好地工作，但LinkedList往往做得很差。關鍵是：LinkedList也很少是正確的答案！）
因此，如果您在此列表中的項目不超過約 1000 項，我會繼續使用CopyOnWriteArrayList我在上面為您編寫的自定義類。
但是，如果你有更多的比，ArrayList是不正確的數據存儲在這里使用。即使您暫時忘記了不斷迭代的需求；調用remove()大型數組列表是一個壞主意（除非刪除非常接近列表的末尾）。在這種情況下，我會準確地勾勒出您需要對該數據類型執行哪些操作以及哪些操作真正需要快速，一旦您有了完整的列表，請嘗試找到一個完全符合您需求的集合類型，并且在（可能的）情況下，沒有任何特定的完美匹配，自己做一個。像上面一樣，當您必須滾動自己的數據類型時，讓現有數據類型完成大部分工作通常是個好主意，因此要么擴展現有數據類型，要么封裝一個。
- 3 回答
- 0 關注
- 215 瀏覽
添加回答
舉報
0/150
提交
取消