如何在執行時找到映射到給定範圍（n_start，n_end）中的有效值的鍵？

我的問題與在執行時使用最少的氣體（如果可能的話）查找映射到給定範圍（n_start，n_end）中的有效值的鍵有關。

mapping(uint => myStruct) clusterContract;

uint包含區塊鏈上的塊號。所以這可能在 0 到 1,000,000 之間並保持增長。根據客戶的行為會生成新的映射，但可能會有一些空白點，例如退出mappings如下：

clusterContract[0]    = structA;
clusterContract[1001] = structB;
clusterContract[1002] = structC;
clusterContract[1003] = structD;
clusterContract[1100] = structE;
clusterContract[2000] = structF;
clusterContract[7999] = structG;
clusterContract[8001] = structH;

以下答案說：

不幸的是沒有。映射只是將鍵與值匹配。它本身沒有任何一個列表。

此時，例如：我只想到達從 1000 到 8000 之間的有效鍵指向的結構，應該是1001(structB)、1002(structC)、1002(structD)、2000(structF) 和 7999(structG ) .

為了做到這一點，我想出的唯一解決方案是遍歷從 1000 到 8000 的所有元素，並檢查每個塊號是否有效鍵，如果它有效，請執行我想要的操作：

for(int i=1000; i++; i<8000) {
   if( clusterContract[i] ) //check whether key exists. I could not figure out how to check key exists or not.
      clusterContract[i].StructX.val = 64; //or do something else.
}

$$ Q $$如您所見，我需要遍歷 7000 個值來檢查它們的鍵是否有效。if then這是一個建議的解決方案，因為如果範圍增加，我需要做 7000 次或更多，因此氣體使用可能效率低下？任何推薦的解決方案將不勝感激。請注意，二叉搜尋樹可能是一個很好的解決方案，但樹再次變大，添加新節點或在樹內搜尋會產生低效的氣體。 => 或者，如果我刪除密鑰有效性檢查（密鑰是否i存在），當此程式碼段通過 Solidity 轉換為最低級別程式碼段（乙太坊虛擬機程式碼）時，不存在的密鑰會被自動忽略，因為它們不存在？因此，只會考慮有效的密鑰，並且不會遍歷 7000 個項目。

for(int i=1000; i++; i<8000) 
  clusterContract[i].StructX.val = 64; //only existing keys are updated.

感謝您寶貴的時間和幫助。如果有語法錯誤，我很抱歉，我盡力用一些例子來解釋這個問題。

這是一個相當高級別的抽象，因為我不確切知道應用程序將要做什麼或您將如何建構部署。三部分答案。

**首先，我會對循環過程持懷疑態度。**盡量避免，並在不可避免時保持良好的界限。理由包括估計氣體可能很困難，而且在規模上，由於塊氣體限制，該過程可能根本無法執行。

通常可以通過暴露一個步驟來解決這種問題… // 或者做其他事情… 作為一個函式。您依賴契約之外的東西，即節點伺服器或 UI 客戶端等，來迭代循環並根據需要經常呼叫該函式。

第二部分。迭代映射本身是不可能的，但經常需要類似的東西。一種解決方案是維護一個索引並對其進行迭代。

address[] clusterContractIndex;

考慮如何展示一個例子，我開始覺得按塊號映射不是要走的路，所以我改成了按地址映射。如果使用此更改在同一塊中創建多個，則不會發生任何衝突。您可能希望將塊編號添加到結構中，以便在計算詳細資訊時將其記錄在某處。請注意，這對於在某個區塊中創建合約不是必需的。

作為一般習慣，考慮一些函式的有用性以使映射可迭代：

function getContractCount() returns(uint count) {
   return clusterContractIndex.length;
}

function getContractAtIndex(uint row) returns(address contract) {
   return clusterContractIndex[row];
}

在記錄它們的函式中，將結構寫入映射，並將push()鍵寫入索引：

function newClusterContract(address newContract) {
   clusterStructs[newContract] = contractStruct;
   clusterContractIndex.push(newContract);

這是一個累積的僅添加過程。現在，您可以按照合約的創建順序獲取合約，或者直接通過它們的地址獲取：

function getContract(address contract) returns(contract details) {}

**第三。高效的搜尋和過濾。**我還沒有一個好的鏈上搜尋過程:-)

在實踐中，您可能能夠退出該需求並依賴於鏈下服務，例如數據庫，甚至是瀏覽器 UI 的記憶體排序（取決於預期的規模）。這裡的要點是，大多數看起來需要鏈上索引/搜尋/過濾器解決方案的事情都可以由鏈下程序更好地處理。

每當狀態更改時，將事件發射器添加到合約中。

event LogNewContract(address contract);

當它發生時：

LogNewContract(address newContract);

當您開始建構 UI 時，您可能會發現對此的觀察者可以保留鏈上真相的同步副本，快速排序和過濾事物，然後獲取已知存在的合約的詳細資訊。從它的聲音來看，它只需要找到任何實際存在於給定區塊數範圍內的合約。客戶在事件到達時獲得創建合約的區塊號。這是收到的每個事件的獎勵。

希望能幫助到你。

ps 您可以將映射視為一個表，其中所有可能的地址都存在，並且所有剩餘的列都可靠地初始化為 0。如果您從從未寫入過的“空”地址中提取結構，那麼結構中的所有欄位都將是全 0. 0, false, 0x0, 空字元串，取決於類型。

更新

我創建了一個訂單統計樹，它解決了許多問題，例如在排序列表中找到一個值的中位數或排名，同時還提供了一種方法，可以將 gas 成本限制在任何規模的絕對最大/最壞情況限制。

這個 repo 建立在 Bokky Poobah 的 Red Black Tree 之上，它為自平衡樹提供了基礎。https://github.com/rob-Hitchens/OrderStatisticsTree

引用自：https://ethereum.stackexchange.com/questions/11701