How is C++'s std::set class able to implement a binary tree for ANY type of data structure?
algorithm, c++
Solution
What you want is a good book on templates and template meta-programming.
In short, the `std::set` class only defines a prototype for a class, which is then instantiated at compile-type using the provided arguments (some Key-type `Key`, some value-type `T`, which deduces `std::less<Key>` and `std::allocator<std::pair<Key, T>>` if not given, or whatever else).
A big part of the flexibility comes from being able to create partial specialisations and using other templates and default arguments.
Now, `std::less` is defined for many standard-library types and all basic types, but not for custom types.
There are 3 ways to provide the comparison `std::map` needs:
- Override the default template argument and provide it to the template (if the override has state, it might make sense to provide an object to the constructor).
- Specialise `std::less`.
- Add a comparison operator (`operator<`).
Problem
I understand how binary trees are implemented for most native elements such as `int`s or `string`s. So I can understand an implementation of `std::set` that would have a constructor like ``` switch(typeof(T)) // T being the typename/class in the implementation { case int: { /* create a binary tree structure that uses the bitshift operator to add elements, e.g. 13=1101 is created as / / / / 1 / / / 1 \ \ 0 / 1 */ } case string: { /* Do something where the string is added to a tree by going letter-by-letter and looking whether the letter is in the second half of the alphabet (?) */ } // etcetera for every imaginable type } ``` but obviously this is not how `std::set` is actually implemented, because it is able to create a tree even when I use a homemade data structure like ``` struct myStruct { char c; bool b; }; std::set<myStruct> mySet; ``` Could it be possible to create a generic binary tree class that looks at all the bits of a data structure and does something like the `int` case I mentioned above? For instance, in the case of `myStruct`, the size of the structure is 2 bytes of 16 bits, so a `myStruct` element `S` with `S.c = '!'` and `S.b = true` could look like ``` 00010101 00000001 (c part) (b part) = \ \ 0 \ \ 0 \ \ 0 / / 1 \ [etcetera] ``` since the ASCII value for `'!'` is 21 and a `bool = true` as an int is 1. Then again, this could be inefficient to do generically because a very large data structure would correspond to a gigantic tree that might take more time to traverse then just doing a basic linear search on the elements. Does that make sense? I'm truly confused an would love if some people here could set me straight.