eclipse-iceoryx / eclipse-iceoryx/iceoryx
Create a set 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 values which satisfies the requirements
- replacement for `std::set` in its core functionality: insertion, finding and removing of values
- no duplicate values
- no full interface `std::set` 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 set will incur overhead, but we can have two implementations differing on only a internal template type to have
- can be implemented in terms of the map in #829 by internally using the key and a dummy value type (presumably the easiest way, although slightly inefficient)
- if not implemented in terms of #829 will need a specific tree implementation applicable only for values (instead of key value pairs), note that reusing a tree implementation for both by specialized `operator<` for pairs is not recommended and causes inefficiencies and hard to grasp code (it appears)
- 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.
## Potential use case
1. Refactoring of service discovery
- result set could be a set, but currently we do not generate duplicates so there is no value
- internally we may improve find with a set, but #859 may be a better way to do so if needed
2. Generally: have a set type to be used in shared memory
Contributor guide
Assessment
This issue has not been assessed yet.