C++如何爲迭代器的非連續容器如雙端查找下一個元素

-1

我想知道如何容器是非連續的，沒有鏈接列表實際上知道在哪裏可以找到下一個元素，因爲它不能保證在這個元素之後出現？是否有一張額外的表格說明這個deque的第一個x塊位於這個起點，接下來的y塊是從那裏開始的，以此類推？

2017-04-10 chrise

迭代器類包含足夠的信息來知道如何找到下一個元素。例如，deque迭代器可以工作的一種方式是保存一個指向當前「塊」的指針並保存一個索引，以選擇塊中的一個項目。 –

通常，迭代器可以引用容器（或其中的一部分），以便它可以訪問有關容器的內部信息。 –

@ M.M我的問題旨在解釋它如何知道不同的塊在哪裏。 – chrise

容器在內部保存必要的信息以便直接訪問元素，因爲deque的內部實現基本上是塊（向量）的雙端隊列。每個塊都有索引元素，一旦塊填滿，就會添加另一個塊，以保持索引的完整性，並且容器類保留提供訪問所需的信息，查找正確的塊，然後查找元素的索引位置。

你可以在這裏閱讀偉大的物品，其將提供所有你所尋求的知識，甚至比你所追求的： https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container

還看到一個簡短實現雙端隊列的，你可以通過對接受的答案堆棧溢出 What really is a deque in STL?

2017-04-10 09:58:52 Valgrind1691

回答