是否有可以迭代的 Java（和 C#，如果你知道）的集合數(shù)據(jù)結(jié)構(gòu)，具有以下屬性：可以刪除當(dāng)前元素而不影響當(dāng)前迭代器（已經(jīng)啟動的迭代器的其余迭代）?？梢蕴砑有略?，但也不會影響當(dāng)前迭代器——當(dāng)當(dāng)前迭代器的迭代仍在進(jìn)行時，不會作為迭代值包含在內(nèi)。在我的情況下，每次迭代只會添加一個新元素，但在從可迭代對象中獲取新迭代器之前，不會看到任何元素。元素的順序無關(guān)緊要。實際上，有一個傳入列表和一個傳出項目列表。傳入列表被迭代，一些被復(fù)制到一個新列表。一些新元素可以在迭代過程中添加到新列表中。迭代結(jié)束后，舊的傳入列表被新的傳出列表替換。整個過程本身就在一個循環(huán)中。因此，與具有這些添加/刪除屬性的元素相比，每次將元素復(fù)制到新構(gòu)造的集合對象似乎效率低下。我正在考慮某種隊列，讓我可以預(yù)覽當(dāng)前項目，然后將其出列或不出列，然后移至下一個項目。我可以將更多項目添加到隊列的頭部，但不會看到它們，因為我正在接近尾端。雙向鏈表可以具有這些屬性，對嗎？如果您真的想知道它的用途，那就是在我的回答中補充第二個大代碼塊。
3 回答
SMILET
TA貢獻(xiàn)1796條經(jīng)驗 獲得超4個贊
對于 C#，您可以LinkedList<T>在好的 ol' C 中使用like：
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你還有l(wèi)ist.AddAfter(node, elem), list.AddBefore(node, elem),list.AddFirst(elem)和list.AddLast(elem)。所有這些操作都是 O(1)。你可以用它做各種迭代，如果你只想迭代原始元素，然后在做任何事情之前緩存下一個節(jié)點并記住最后一個節(jié)點：
var lastNode = list.Last;
var node = list.First;
while(node != lastNode.Next)
{
var nextNode = node.Next;
// do stuff with node
node = nextNode;
}
Java 中的等效數(shù)據(jù)結(jié)構(gòu)也稱為LinkedList<E>. 但是，ListIterator<E>在標(biāo)準(zhǔn)List<E>上使用可能更清潔。
寶慕林4294392
TA貢獻(xiàn)2021條經(jīng)驗 獲得超8個贊
在 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
}
}
}
這里的關(guān)鍵是使用索引而不是foreach，并且在當(dāng)前索引之前不要更改任何內(nèi)容（從閱讀您的要求來看，不需要）。
但是，如果您確實需要在當(dāng)前索引之前添加或刪除元素，那么這種方法不起作用（或者至少，它變得更加復(fù)雜）。
慕容708150
TA貢獻(xiàn)1831條經(jīng)驗 獲得超4個贊
在 Java 中有CopyOnWriteArrayList可以執(zhí)行您想要的操作：每次更改任何內(nèi)容時，它都會創(chuàng)建一個后備數(shù)組的副本。但這確實意味著一旦開始迭代，任何迭代都是“一成不變的”，因此您可以隨意刪除/添加基礎(chǔ)集合，而不會影響任何正在運行的迭代器。
您還可以構(gòu)建自己的具有此行為的集合類型。這將是一個 3 班輪：
public class ConstantIterationArrayList<T> extends ArrayList<T> {
public Iterator<T> iterator() {
return new ArrayList<T>(this).iterator();
}
}
（上面制作了列表的副本，然后為您提供了副本的迭代器，從而方便地確保對此列表的任何修改絕對不會影響該迭代器）。
這是你的問題的真正問題：
上面的代碼會不時地制作底層數(shù)據(jù)存儲的副本（我上面的代碼片段每次制作迭代器時都會這樣做。CopyOnWriteArrayList每次調(diào)用remove()or時都會這樣做add()）?！皬?fù)制底層數(shù)據(jù)存儲”操作需要O(n)時間，因為對于兩倍大的列表，它需要兩倍的時間。
ArrayList通常具有這樣的屬性remove()，除非您要刪除列表末尾或非常接近列表末尾的元素，否則操作是O(n)操作：如果列表是兩倍，則從列表中刪除元素需要兩倍的時間大的。
幸運的是，現(xiàn)代 CPU 具有相當(dāng)大的緩存，并且可以在緩存頁面內(nèi)以極快的速度運行。翻譯為：盡管數(shù)據(jù)復(fù)制過的感覺效率不高，在實踐中，只要在頁面左右的時間內(nèi)支持?jǐn)?shù)組的配合，這是很多快于基于數(shù)據(jù)存儲的LinkedList語義。我們正在談?wù)撟疃嗉s 1000 個元素的給予或接受。（請注意，一般來說，您對 a 所做的幾乎所有事情LinkedList都是O(n)并且在ArrayList現(xiàn)代 CPU 架構(gòu)中LinkedList往往表現(xiàn)良好的地方往往表現(xiàn)不佳。重點是：LinkedList也很少是正確的答案！）
因此，如果此列表中的項目不超過 1000 項，我會繼續(xù)使用CopyOnWriteArrayList我在上面為您編寫的自定義類。
但是，如果您有更多，這里ArrayList就不是正確的數(shù)據(jù)存儲。即使您暫時忘記了不斷迭代的需求；調(diào)用remove()大型數(shù)組列表是一個壞主意（除非刪除非常接近列表末尾）。在這種情況下，我會準(zhǔn)確地勾勒出您需要對這種數(shù)據(jù)類型執(zhí)行哪些操作以及哪些操作確實需要快速，一旦您有了完整的列表，請嘗試找到完全符合您需求的集合類型，并且在（可能）情況下，沒有任何特定的東西可以完美匹配，請自己制作。像上面一樣，當(dāng)您必須滾動自己的數(shù)據(jù)類型時，讓大部分工作由現(xiàn)有數(shù)據(jù)類型完成通常是一個好主意，因此要么擴展現(xiàn)有數(shù)據(jù)類型，要么封裝一個。
添加回答
舉報
0/150
提交
取消