I understand how binary trees are implemented for most native elements such as ints or strings. 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.
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:
std::less.operator<).Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments