eclipse-iceoryx / eclipse-iceoryx/iceoryx

Create a map data structure for the iceoryx hoofs library

Open
#829 0 comments 0 reactions 1 assignee Claimed by @MatthiasKillat View on GitHub
enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.