0

What is the best way to add an optional payload to a sorted container?

In my case, I have an AvlTree that obviously needs a Key type to sort it with. For this, I created a templated AvlNode class with the template KeyType as well as an AvlTree class with the same template. Due to some old code I just have a KeyType that implements operators for sorting, but also contains a payload that is independent of the key.

However, I think it would be cleaner, to just offer two template types (i.e. add a PayloadType). While I could just add this, I would then prevent others from using the tree with just a KeyType.

My first thought was to use

template <typename KeyType>
struct AvlNode
{
     KeyType key;
};


template <typename KeyType, typename PayloadType>
struct AvlNodePayload : public AvlNode<KeyType>
{
     PayloadType Payload;
};

However, my AvlTree always uses the AvlNode class and stores a root node of that class. Inheriting from that the same way would mean that I'd have to reimplement almost every method to accomodate for the payload node type. Furthermore, I'd have to hide the old root node and then use a new one, just to ensure the correct class. Therefore, this doesn't seem like a good solution to me.

A different way would be to add a default template to the original AvlNode struct, such that it always carries a payload, but this would obviously be an overhead in data whenever only a key is needed.

I'm not sure if there is an elegant solution to this (perhaps other than staying with what I have right now: If someone wants to have a payload, they need to implement their own Key class/struct - even then searching and deleting would require me to create this key entirely although I don't need the internal payload part).

Tare
  • 482
  • 1
  • 9
  • 25
  • Just copy whatever the standard library is doing in `std::map`. There's not always a need to be creative. If old trick works, why do new trick? – n. m. could be an AI Sep 03 '20 at 08:45
  • Give your node type two template parameters, say Key and Value. For the payload free version Key and Value would be the same, for the with payload version Key would be whatever and Value would be std::pair. There are a few type manipulations need to be done in the implementation but it's not too hard. This is how std::map and std::set work (at least the last time I looked). – john Sep 03 '20 at 08:49
  • @n.'pronouns'm. That is because the `std::map` does not have the payload optional, both Key and Value are mandatory. Or at least I have never seen it differently. Plus, I have never used `std::set` so far, so I didn't think about it. I will have a look at it though, so thanks for the hint to both of you. – Tare Sep 03 '20 at 09:03
  • as implemented in libstdc++, both `std::map` and `std::set` use the same `_Rb_tree<...>` underlying data structure, with a minor difference in template arguments. – n. m. could be an AI Sep 03 '20 at 09:49
  • From what I understand from the code of `set` and `map` don't do, what I intended. You either just have a key (set) or a key and a value (map), but you don't have one container that offers an optional value. You have to decide and ultimately that means you have two different classes with less code sharing. What they offer is only an optional comparator, but I wanted for example a that could be `Tree` or `Tree`, where the int is the key, but the float could be whatever. Please correct me if I'm wrong. – Tare Sep 03 '20 at 13:44
  • Don't look at the public interface of std::set and std::map. Look at the implementation, specifically at _Rb_tree. – n. m. could be an AI Sep 03 '20 at 23:17

1 Answers1

0

You can do this with std::set already using what is a called a transparent comparator. See this answer for example for detail or use google.

darune
  • 10,480
  • 2
  • 24
  • 62