I need compact data structure for (key, value) storage with random access and ability to iterate over elements in order of their keys. Like haskell’s IntMap, for example - I do not mind keys being restricted to some particular integer type. Does UE4 have something like this or should I bring some external library? If external, which one would you recommend?
You want to use TMap: TMap | Unreal Engine Documentation
“random access” is a little vague. TMap supports random access but unless you have an iterator for the item at hand you will need to access it using its key with is OLogN. Same with insertions and sorts. Neither boost nor STL that I know of provide any sorted containers with constant time lookups.
TMap iterators likely iterate by the ordered sort of their keys.
TMap and any third party containers do not support replication so if that is a requirement you will have to manually handle replicating the containers.
I have found TMap myself of course - should have written this in the question probably. Problem with TMap is that as far as I can see it is sortable, not always sorted collection. I can live with OLogN for read-write - its very reasonable complexity for map. But it looks like that insertion of new element into TMap invalidates its sorted state and if I need to do ONLogN hash rebuild after each insert to be sure that order of keys persists - that’s a real problem. Though, may be I have misunderstood something about TMap?
Nope, you are right. TMap is hashed and is thus more like std::unordered_map. There is no always-sorted associative container (i.e. like std::map) in UE4 at the present time, though there have been a few internal demands for such a container and is on our backlog for features to implement. I don’t have a timescale for its arrival though.
Steve
std::map it is then