How to find keys mapped to valid values in a given range (n_start, n_end) at runtime?

Question

My question is related to finding keys mapped to valid values in a given range (n_start, n_end) at runtime using minimum gas, if possible.

mapping(uint => myStruct) clusterContract;

uint contains the block number on the blockchain. So this may be in between 0 and 1,000,000 and keep increases. Based on client's behaviour new mapping will be generated but there may be some empty spots, for example exiting mappings as follows:

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

Following answer says that:

Unfortunately not. A mapping just matches a key to a value. It doesn't have a list of either per se.

At this point, for example: I just want to reach structs that pointed from valid keys in between 1000 and 8000, which should be 1001(structB), 1002(structC), 1002(structD), 2000(structF) and 7999(structG).

In order to do that only solution I have come up with is to iterate through all elements from 1000 to 8000 and check that each block number valid key or not and if it is valid do the operation I want to:

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] As you can see, I need to iterate through 7000 values to check if their keys are valid or not. Is this a suggested solution, where gas usage might be inefficient since I need to do 7000 if then or more if the range increases? Any recommended solution would be very appreciated. Please note that Binary Search Tree might be a good solution but again larger the tree, there would be inefficient gas for adding new nodes or searching within the tree.

=> Or if I remove the key validity check (whether key i exists or not), when this code piece is converted into lowest level code piece (Ethereum Virtual Machine code) by Solidity, would nonexisting keys be ignored automatically, since they don't exist? Hence only valid keys will be considered and it won't iterate through 7000 items.

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

Thank you for your valuable time and help. I am sorry if there is grammar mistakes, I did my best to explain this problem with some examples.

Answer 1

This is a fairly high level of abstraction because I don't know exactly what the application is going to do or how you will structure the deployment. Three-part answer.

First, I would be leery about a loopy process. Try to avoid whenever possible and keep it well-bounded when it's unavoidable. The rationale includes the fact that estimating gas may be difficult, and at scale, it's possible the process won't be able to run at all due to the block gas limit.

It's often possible to get around that sort of thing by exposing a single step ... // or do something else ... as a function. You rely on something outside the contract, i.e. a node server or a UI client, etc., to iterate over a loop and call that function as often as necessary.

Second part. Iterating over a mapping itself isn't possible but something like that is often needed. A solution is to maintain an index and iterate over that.

address[] clusterContractIndex;

Mulling over how to present an example, I started developing a feeling that mapping by the block number isn't the way to go, so I've changed to mapping by address. There won't be any collision if multiples are created in the same block with this change. You may want to add the block number to the struct to record it somewhere as you work out the details. Note that this won't be necessary to get contracts created in a certain block.

As a general habit, consider the usefulness of some functions to make the mapping iterable:

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

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

Inside the function that records them, write the structs to the mapping, and also push() the keys to the index:

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

This is a cumulative add-only process. Now you can get the contracts in the order they were created, or by their address directly with:

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

Third. Efficient search and filtering. I don't have a good on-chain search process, yet :-)

In practice, you may be able to eject that requirement and depend on offchain services such as a database or even an in-memory sort by a browser UI (depending on expected scale). The takeaway here is most things that look like the need for an onchain index/search/filter solution are really better handled by offchain processes.

Add an event emitter to the contract whenever state changes.

event LogNewContract(address contract);

And when it happens:

LogNewContract(address newContract);

When you get on to building the UI, you'll probably find that a watcher over this can keep a synced copy of the on-chain truths, quickly sort and filter things, and then fetch the details of a contract that's known to exist. From the sound of it, it only needs to finds any contracts that actually exist in a given range of block numbers. Clients get the blocknumber a contract was created in when the event arrives. It's a bonus piece of every event received.

Hope it helps.

p.s. You can think of the mapping as a table in which all possible addresses exist and all remaining columns are reliably initialized to 0. If you pull a struct from an "empty" address you never wrote to, then all fields in the struct will be all 0. 0, false, 0x0, empty string, depending on type.

UPDATE

I've created an Order Statistics Tree that resolves a number of problems such as finding the median or rank of a value in a sorted list while also providing a method to cap gas cost to an absolute maximum/worst-case limit at any scale.

This repo builds on Bokky Poobah's Red Black Tree which provides the basis for the self-balancing tree. https://github.com/rob-Hitchens/OrderStatisticsTree