Iterator does not carry the key

[evanxg852000]

It's very annoying that the iterator does not carry the associated key. In the example below, I would like to access the key it->key

auto it = m.begin();
  auto it_end = m.end();
  for (int i = 0; it != it_end; ++i, ++it) {
    std::cout << i << ": " << **it << std::endl;
    std::cout << i << ": " << it->key << std::endl;
  }

My use case: I am storing the keys in a file and using art<Node>, Node only knows the offset in the data file. I don't want to be doing disk io to fetch the keys when they are already in art.

Is there any constraint that ART is not able to do to that, I can help implement this you guide me. Thanks

[rafaelkallis]

The key is not included in the iterator in order to avoid a performance penalty for those that don't need the key during iteration.

However, there is an easy way around this for those that want to have the key during iteration for convenience. Wrap your values in a struct that has a key property (or any other metadata you require) before inserting them to the data structure. When you iterate through the tree, you are given your wrapped values, which also contain your key.

Let me know if this works for you.

EDIT: to be fully transparent, I did not validate whether or not there is a significant performance penalty when keys are carried during iteration. I am happy to merge a change request if there is evidence (by running the benchmarks) that carrying the key during iteration does not impair performance.

[evanxg852000]

I understand the tradeoff here, however art is used mostly for in-memory kv and having to store the key again in the value while this is available in the art is like storing the keys twice or maybe 1.5 times since art compressed it. relying on the compressed one in art makes the in-memory store accepts more keys and I think that's the primary goals of radix trees. I believe you need to consider that when evaluating the tradeoff. I am still trying to understand if I am able to unlock and inject the keys. I will put a benchmark on it.

[rafaelkallis]

I think we both agree here, I have created a discussion thread #10, you are very welcome keep discussing there.