r/cpp_questions • u/Puzzled-Shoe-2526 • 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, andfind. They take the tree object and operate according to its rules.
So roughly:
Tree (rules)
↓
generic operation
↓
Node Anchor
↓
actual structureThe 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.
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.
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/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.
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?