Add map/set final() method?

[MBkkt]

final method should return some map type without insert and other non const methods.

In that case you can use eytzinger/btree/vEB (add user ability to choose) for more efficient search.

What do you think?

[MBkkt]

I think its possible to implement btree/etc search now.

Btw I think its also fix problem with small maps

[muggenhor]

It's possible to do btree. But that would also change iteration order. So would probably need a new name than map/set...

[MBkkt]

But that would also change iteration order

It depends on implementation, but by default no, because it sorted order of iteration, it could change iteration speed compared to just sorted array

[muggenhor]

Right. I was just misled by looking at my own multiplicative B-tree implementation which has a descending link computation function but lacks the inverse. So just spent some time creating the inverse and proving it. (Both are O(1) if you assume integer mul & div to be constant time).

So retaining sorted iteration order is doable. Though it would, as you mentioned, affect speed (by having reduced memory locality for that scenario). Though that's at least predictable, so could be ameliorated by prefetching the successor block in the dereferencing operator.

I'm not sure about the iterator category though. I.e. random access iterators are required to have iter + offset be O(1). Any structure that stores its links is definitely not going to meet that requirement when counting random access memory reads. That leaves versions with calculated/implicit links such as a multiplicative B-tree. There it's not going to be O(log N), maybe O(log log N), for the arithmetic.

So: is it worth counting the arithmetic to determine iterator category? I'm inclined to say yes, which would effectively downgrade iterator category to bidirectional.

[MBkkt]

Maybe you're right and having separate class is better alternative.

I'm not sure about the iterator category though. I.e. random access iterators are required to have iter + offset be O(1). Any structure that stores its links is definitely not going to meet that requirement when counting random access memory reads. That leaves versions with calculated/implicit links such as a multiplicative B-tree. There it's not going to be O(log N), maybe O(log log N), for the arithmetic.

It's possible to make b tree for simple types like sorted array + index part. So when we call find it uses b tree layout, when we iterate array layout.

Though that's at least predictable, so could be ameliorated by prefetching the successor block in the dereferencing operator.

Btw https://en.algorithmica.org/hpc/data-structures/s-tree