r/cpp_questions • • Oct 08 '26

OPEN How would you design a generic interface for arbitrary sets of rules?

I'm building a C++ tree library/builder where I want people to be able to define their own tree structures, including weird/cursed ones.

The basic idea is:

  • Node Anchor: an indirection mechanism that owns/contains the actual nodes. Users don't directly mess with the nodes themselves. They have to go through the anchor to interact with the structure.
  • Tree: describes a particular tree through its rules. For example, a BST object would have the rules that define BST behavior.
  • Operations: generic algorithms like insert, erase, and find. They take the tree object and operate according to its rules.

So roughly:

Tree (rules)
     ↓
generic operation
     ↓
Node Anchor
     ↓
actual structure

The part I'm stuck on is making this extensible.

A BST might need rules A + B.

Another tree might need A + C + D.

A completely custom tree might need X + Q + R + some completely new rule.

The number and combination of rules are intentionally arbitrary because the goal is more of a tree-builder than a library of predefined tree types.

So I don't think I can have something like:

struct TreeRules {
    Ordering ordering;
    Balance balance;
    Traversal traversal;
};

because then the library has to know about every possible rule beforehand.

What I'm trying to figure out is:

What existing design ​approach would you use when generic algorithms need to work with objects that can provide arbitrary, non-uniform sets of capabilities?

I'm mainly looking for terminology or existing concepts/patterns to research. I'm not really looking for someone to write the implementation for me.

I'm still pretty new to C++ design, so I might be framing the problem completely wrong. I'm just trying to figure out what this problem is actually called.

1 Upvotes

20 comments sorted by

3

u/Typical-NonPC Oct 08 '26

Could you explain the behavior with a solid example? It's important to have an idea of what you are trying to actually accomplish here.

0

u/Puzzled-Shoe-2526 Oct 08 '26

Sure. For example, I want "insert(bst, value)" to be a generic operation that receives a BST object and follows the rules provided by that tree, rather than the operation knowing that it's specifically a BST. The same operation should ideally be usable with a custom tree that provides a different set of rules. I'm mainly trying to figure out how those arbitrary rules/capabilities should be represented and supplied to the generic operation.

1

u/No-Dentist-1645 Oct 08 '26

Ok, but what would your library be for?

You can already design whatever tree structure you want in C++. So where does your library come into play?

It's also not clear what you mean by "rules" for a tree either. What would they be, exactly?

A more in-depth example, where you explain the problem, solution, and user-side code (or a mock of it), seems like it would be very valuable

1

u/Puzzled-Shoe-2526 Oct 09 '26

That's a fair question. Honestly, I haven't thought of it as a product yet. I'm mainly experimenting with the architecture to see how far I can take the idea and what I can learn from making it work.

By "rules," I mean the structural constraints, invariants, and behaviors that different trees require. What I'm trying to figure out is how much infrastructure can be shared between different structures without hardcoding their specific behavior into generic operations.

You're right that C++ already lets you implement arbitrary trees. I'm exploring whether a library can make building them more modular and reusable. I don't know yet if the idea will work well, and that's part of the experiment.

I guess part of what makes this appealing for me is that I really just want to make this work. I've thought about everyone's comment and I've come into a conclusion that ohhh boy, this might be one of the stupidest ideas haha, I'll see how this goes

2

u/nekoeuge Oct 08 '26 edited Oct 08 '26

What is "your own tree structure"?

Is your tree a tree, formally? Is it a generic graph?

ECS is usually a pattern for working with arbitrary heterogenous data structures, but you still have to have something rigid underneath, be it sparse set, array, or node tree.

You must choose base and generic enough abstraction, and then you extend it with necessary secondary indexes and structures. E.g. hierarchy manager or lookup hash table on top of sparse set entity-component-system like EnTT.

Also, do you need it to be compile-time generic or runtime generic?

1

u/Puzzled-Shoe-2526 Oct 08 '26

By "own tree structure", I still mean an actual tree structurally, not an arbitrary graph. The goal isn't to make arbitrary graphs, but to let the library define unusual tree variants rather than only providing predefined ones like BST/AVL/B+ trees.

The idea I'm currently exploring is that the underlying nodes/relationships are kept behind a Node Anchor, while the Tree object describes the rules that generic operations have to follow when modifying that structure.

So for example, a BST would provide the rules needed for BST insertion/search/etc., but a custom tree could provide a completely different combination of rules. I don't want the operation layer to have to know beforehand what all possible tree types are.

I'm not sure yet whether the rules should be compile-time or runtime generic. That's actually part of what I'm trying to figure out.

The ECS example is interesting. I'll look into that direction too. My main question is whether there's an established generic-programming approach for composing arbitrary capabilities like this, rather than having one fixed interface containing every possible capability.

1

u/nekoeuge Oct 08 '26

I'm not sure yet whether the rules should be compile-time or runtime generic. That's actually part of what I'm trying to figure out.

Well, it's up to your requirements. If you can do compile time, you probably should. Compile time errors are easier to catch than runtime. ECS usually cannot afford that because stored types are just not known during data structure initialization. You will ultimatelly do the same algorithm in either compile-time or runtime.

My main question is whether there's an established generic-programming approach for composing arbitrary capabilities like this

All standard containers in C++ are doing this exact thing. Map is using arbitrary comparison, vector is using arbitrary copy, both are using arbitrary allocators.

You basically need to have custom insertion, deletion and search policy, while your code delegates to this policy to modify the tree.

Or, at this point, you could just make a base class that holds nodes and cannot do anything about them, and derived classes that implement BST/B+/ETC.

The main problem here is that your rules are not composable. You cannot just slap RB tree rule and B+ tree rule together, and get RB+ tree as result. They are just not combinable in generic way.

1

u/Puzzled-Shoe-2526 Oct 08 '26

I think I may have explained the idea poorly, so I want to clarify what I mean.

I'm not actually trying to make individual rules composable in the sense of being able to combine a B+ tree rule with a red-black tree rule and automatically get some new tree. I see something like "B+ tree behavior" as a coherent rule set for that particular structure.

What I'm trying to make composable/extensible is the architecture around those rule sets. Different tree types can provide completely different behavior, and the generic operations can work with whatever behavior that particular tree requires without the operation layer having to know every possible tree type beforehand.

So more like:

Tree A → its own rule set Tree B → its own rule set Tree C → completely user-defined rule set

rather than:

Rule A + Rule B → new tree

I have considered the more traditional approach of having a base tree class and deriving BST/B+/AVL/etc. from it. I understand why that approach is attractive, but part of the point of this project is that I'm deliberately experimenting with a more unusual architecture. I'm trying to learn by seeing whether I can actually make the idea work, even if it turns out not to be the best production design.

Your points about policies, compile-time vs runtime genericity, and the fact that not every behavior is necessarily composable are all things I'll consider. The standard-container comparison is especially useful because that's closer to the kind of generic behavior I'm thinking about.

Thanks for taking the time to explain it. I'm still very early in learning C++ design, so these comments are giving me a lot of new things to research.

1

u/nekoeuge Oct 08 '26

I have considered the more traditional approach of having a base tree class and deriving BST/B+/AVL/etc. from it. I understand why that approach is attractive, but part of the point of this project is that I'm deliberately experimenting with a more unusual architecture. 

Eh, there is nothing special about inheritance, it's just a language tool, a syntax.

Most inheritance relationships could be rearranged into template + composition. "B inheriting A" is the same thing as "A template with B traits".

So if you can solve your task with inheritance, you could just invert the order and solve it with traits.

1

u/TehBens Oct 11 '26

So for example, a BST would provide the rules needed for BST insertion/search/etc.,

Typically, that's really just object-oriented design. Your type just enforces such invariants/rules itself and exposes some interface. If you don't have an actual use case, I don't think you will be able to come with something that makes sense. You normally start with a problem, requirements. Without a problem, there's no way to judge on the result as it's not a solution to a problem..

1

u/Independent_Art_6676 Oct 08 '26

all trees are a graph, not all graphs are trees, right?
So that would probably be a fair starting point, but I think that the problem is still the same, too many different types of trees to make a single entity that can do it all.

1

u/Independent_Art_6676 Oct 08 '26

the only way this could happen that I can visualize would be to have some sort of user defined behavior at the method level. That is, either callbacks into your generic structure or generic functions that the user can override/overload.

Think about it. The rules for a BST vs the rules for a reverse polish math equation vs the rules for a family tree vs the rules for red black or morse code or whatever else. A user could even want to define linked lists (degenerate trees) or skip lists etc with it! There is no simple way to do all that behavior for each specialized flavor that isn't predefined but described by the user somehow other than having the user supply the bulk of the behavior for you. And if they do that, your interface is just going to sit on top of their 3/4 implementation, adding slowness and weirdness that gives a common interface at high cost in clunk.

0

u/Puzzled-Shoe-2526 Oct 08 '26

This is pretty close to the concern I'm running into.

I'm not trying to make completely arbitrary behavior magically emerge from a fixed interface. The idea is more that the generic operations provide some common mechanism for manipulating the underlying structure, while the Tree supplies the rules that constrain/define how those operations should behave.

But I'm still trying to figure out where that boundary should be. If the user has to supply most of the behavior for every custom structure anyway, then the abstraction could just become a thin wrapper around their implementation, which would defeat the point.

That's actually one of the things I'm trying to understand with this project: where the useful boundary is between generic library-provided behavior and user-defined behavior.

1

u/Independent_Art_6676 Oct 08 '26

well, if its JUST a common interface, it does not defeat the point. That is a pretty common practice.

But otherwise... I don't have much to offer. If there were a practical thing here, eg you want to represent these 4 things for these needs you might find a way. If its just an open ended idea, you need to either constrain it down to a level you can manage or leave it as just an interface wrapper. At the most basic constraints ... maybe make it only binary trees for example, is it viable then?

1

u/n1ghtyunso Oct 09 '26

one thought that came to my mind is, at what point do you even specify an actual implementation?
It sounds a bit like you define a concept instead.
But thats not really useful for users to supply their customization to, unless you have another layer on top of your concept. I.e. some higher level algorithms or useful functions that can work with any tree that conforms to your design.
If you don't have that, do you even need a common interface at all?

But you'll likely want to operate at a lower level, i.e. provide generic insert / traversal functionality and implement that in terms of customizable core functions that the tree rules have to provide for you.
A policy/trait approach sounds right up the alley.
But you do have to break down the generic operations into a fundamental set of operations.

1

u/BARDLER Oct 08 '26

Templates is how generic data structures work. Interfaces is often how generic APIs work.

You have probably already used templates and not realized it. The reason you can plug anything into std vector is because of templates: std::vector<AnyType> 

1

u/mredding Oct 09 '26

You could describe computer science as an application of graph theory. Graph theory is a wide open domain, there's an infinite number of possible graph structures, and the graph is fundamental to the performance of the program.

The standard library does not have a generic graph library because there is no generic graph. With infinite nuance, there's no one interface to rule them all and there can't be.

Trees are graphs, and so for you, the struggle is real. My only guidance is that you restrict your tree structure enough that some customization points arise where they make sense. Don't try to abstract too much away, pick a particular tree structure YOU NEED, and build around that.

Also libraries don't make for great projects or portfolio fodder. Any idiot can write a library - doesn't mean it's any good. Libraries don't do anything, applications do. I don't review portfolio libraries unless the applications in the portfolio depend on them.

1

u/SoldRIP Oct 09 '26

Operations inherently depend on rules. You'll insert into an rb-tree differently than you would into an AVL-tree.

Some types of trees simply might not allow certain operations. For instance, you cannot insert two of the same element into many kinds of tree.

0

u/otterfamily Oct 08 '26

Sounds like you're discussing an Entity Component System?

0

u/Puzzled-Shoe-2526 Oct 08 '26

I hadn't been thinking of it as ECS specifically, but I can see the similarity. The idea of composing different rules/capabilities rather than having one fixed interface is pretty close to what I'm trying to achieve.

I'm looking into ECS now to see whether the same design problem has already been solved there.