Feature: cc_tree / cc_graph

[gabewillen]

I’m working on a library that uses a tree structure for creating hierarchical models, and I’ve noticed significant overlap with the internal structures of CC. I’d like to propose incorporating this tree structure into the library. If you’re interested, I can open a PR with the API spec for your review. If you decide to move forward, I can quickly port my library code into the CC namespace and submit a PR with the implementation.

[JacksonAllan]

I’m hesitant to introduce any new containers (beside the planned null-terminated strings) for a few reasons:

• CC is not only a single-header library but also a library that, for best performance, needs to be compiled once per translation unit that uses it (or else be compiled with link-time optimization enabled). That’s because we want the compiler to inline as many of the container functions as possible so that it can optimize all the calls to memcpy and comparison and hash functions, just like it would if there were separate, specialized functions for every container/key/element-type combination. This approach is the reason that every function in CC is declared as static inline and that CC, unlike other single-header libraries, doesn’t ask the user to define something like CC_IMPLEMENTATION in one translation unit. However, it also means that there’s a strong incentive to keep the library lean in order to limit its impact on build times and limit code duplication (for any functions that don't get inlined) inside the resulting executable. Even before the addition of strings, the header is already 291 KB (although about 40% consists of documentation and comments, and a lot of whitespace is used to format macros nicely).

• The container lineup – vectors, linked lists, maps and sets (i.e. hash tables), ordered maps and ordered sets (i.e. binary search trees), and strings – was planned since the beginning on the basis that it constitutes a minimal set of containers that would cover most common needs. My thinking was always that for more specific or esoteric needs, users should turn to a specialized library. For example, CC's pair of associative containers—namely one high-performance unordered container without iterator stability (its hash table) and one lower-performance ordered container with iterator stability (its red-black tree)—should hopefully serve most users' needs, but a user who needs the specific combination of high performance, order, and no iterator stability should perhaps look elsewhere for a standalone b-tree library.

The point I’m making here is that the fact that a container could be incorporated into CC doesn’t necessarily mean that it should be, both from a practical and technical perspective (i.e. limiting build times and potential code duplication) and from the perspective of design-philosophy (i.e. keeping the scope limited and focused on common needs).

With all that said, I would consider adding another container if I thought it catered to a common use case. In this regard, I don’t really understand the tree structure you’re proposing. How would it differ from the red-black trees that CC already includes? Is there an existing implementation or library that I can look at to get a clearer idea?

On a side note, I think the easiest way to add a new container to CC is to implement it separately first and then worry about integrating it into the library. CC has quite a few unusual implementation details that can be distracting when you’re trying to lock in the logic of the actual data structure. That's how I went about developing both CC's hash table and its red-black tree.