eclipse-iceoryx / eclipse-iceoryx/iceoryx
Create a map data structure for the iceoryx hoofs library
- Dominant language
- C++
- Stars
- 2.2k
- Forks
- 492
- Avg merge
- 18h 57m
- Merged PRs (30d)
- 1
Description
## Brief feature description
We need a data structure which admits efficient management of key-value pairs which satisfies the requirements
- replacement for `std::map` in its core functionality: insertion, finding and removing key value pairs
- no duplicate keys, exactly one value per key (no multi-map but such a structure can be build with a container as value type)
- no full interface `std::map` interface, we start with a custom interface
- efficient operations, O(log(n)) in the long run
- memory static (by defining a bounded capacity) and no exceptions
- relocatable if required by the user (to be able to send it via iceoryx)
## Detailed information
- a relocatable map will incur overhead, but we can have two implementations differing on only a internal template type to have both on demand (by switching this type) this can be hidden from the end user
- Olog(n)) operations require a RB tree or similar, which are fairly complicated. we can start with an easier binary tree, finalize the prototype and then replace it with an RB tree in a separate issue.
- the binary tree does not provide the O(log(n)) guarantees but will have the same internal interface as the RB tree so it is easy to switch later
- the interface can be extended later to an STL one based on the custom interface (a full one is quite an effort for a lot of syntactic sugar)
- iterator support will be added later
To be further refined.
Contributor guide
Assessment
This issue has not been assessed yet.