eclipse-iceoryx / eclipse-iceoryx/iceoryx

Create a set data structure for the iceoryx hoofs library

Open
#830 0 comments 1 reaction 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 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

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.