Templates for unique id generation for types : a beginning
After reading one of the comments on this blog post, I decided to publish here a proof of concept for the generation of unique ids for types.
Basically, it’s just about one template structure, using very basical templates techniques : specialization, metaprogramming-level recursion and nested enum for the computation. Either a familiarity with template metaprogramming or with functional programming is enough to understand the following code.
If you’re familiar with any scheme of functional recursion, or recursion in its mathematical sense, you’ll get it quite easily. Mathematically, we’re somehow defining a recursive function generate_id this way :
Which, in C++, becomes :
template <typename T> struct id_generator; template <typename T> struct id_generator<T*> { enum { result = id_generator<T>::result*2 }; }; template <typename T> struct id_generator<T&> { enum { result = id_generator<T>::result*3 }; }; template <typename T> struct id_generator< std::vector<T> > { enum { result = id_generator<T>::result*11 }; }; template <> struct id_generator<int> { enum { result = 5 }; }; template <> struct id_generator<char> { enum { result = 7 }; };
And a minimal example of use :
int main() { std::cout << "int : " << id_generator< int >::result << std::endl << "char**** : " << id_generator< char**** >::result << std::endl << "vector<int> : " << id_generator< std::vector<int> >::result << std::endl; return 0; } /* Output : int : 5 char**** : 112 vector<int> : 55 */
To make it really usable, you’ll have to add much (much much much) more :
- base types, like int and char here, which help for terminating the recursive call
- composition rules, like vector, references and pointers here, which help for propagating the recursion
To ensure the uniqueness here, I use prime numbers, simply [1]. Indeed, for the base types, I give a value being a prime number. For the different compositions, I multiply by a different prime number for each. However, most of you may have noticed that the id only lets you know about what type compositions and base types are used, but gives nothing about the order. If we add a rule for std::list, multiplying by 13 for example, then a list of vectors of ints will have the same id as a vector of lists of int. It’d need additional code and workarounds to take the order of the compositions in account — I guess it is possible though. If any reader here comes up with a solution, let us know. A possible solution would be to drop prime numbers, since they rely on a commutative (abelian) ring [2].
[1] http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
[2] http://en.wikipedia.org/wiki/Commutative_ring
Look at Boost.Typeof.
http://www.boost.org/doc/libs/1_39_0/doc/html/typeof.html
It uses something similar yet different so you can use it with your own types and not only primitive 🙂
I didn’t know (so far) boost.typeof has been using a similar mechanism. Thanks !
Anyway, this technique can work with our own types too.
It seems you assign the same ID to vector* and vector. Obviously, this encoding doesn’t work. You might want to approach the mapping a bit differently. You can think of the type as a tree. Encoding and decoding that tree as a sequence of “symbols” is straightforward. Mapping the sequence of symbols to integers is straightforward, too. I just don’t see the point in all this. What do you need IDs for?
I always forget about worpress eating angle brackets. What I ment to say was you get the same ID for vector<int*> and vector<int>*.
The tree is a nice idea.
I don’t have a particular need for that, it’s rather a little challenge.
I know I get the same ID for these two types — see the end of my post — but connecting such things with math-related stuffs is pretty interesting.
Hello Alp.
Here is my propposal for a unique type ID :
generateid(int) = 1
generateid(char) = 2
generateid(float) = 3
∀T, generateid(pointer to T) = 4 × generateid(T) + 0
∀T, generateid(ref to T) = 4 × generateid(T) + 1
∀T, generateid(vector of T) = 4 × generateid(T) + 2
∀T, generateid(list of T) = 4 × generateid(T) + 3
Indeed, I thought about such a solution since I wrote this blog post. The problem is that this doesn’t not scale for new containers, like, say, std::set. The “4” and the offset have to scale when adding new “type compositions” AND new types.
Powerful post.
Navy maintains no such experiment occurred.
Only in the final decade has there been an explosion on solar conversion technologies.
I’m truly enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more enjoyable for
me to come here and visit more often. Did yoou hire outt a developer to create your
theme? Fantastic work!
Today, while I was at work, mmy cousin stole my apple ipad and tested to
see if it can survive a twenty five foot drop,
just so she can be a youtube sensation. My iPad is now destroyed and she hhas 83 views.
I know this is entirely off topic but I had to share it with someone!
Hello! This is kind of off topic but I need some help from aan established
blog. Is it tough to set up your own blog? I’m not very techincal but I
can figure things out peetty fast. I’m thinking about setting uup my own but I’m not sure where to start.
Do you have any ideas or suggestions? Cheers
Howdy! This blog post couldn’t be ritten much
better! Going through thgis article reminds me of my previous roommate!
He constantly kept talking about this. I’ll send
this article tto him. Pretty sure he’ll have a good read.
Thanks for sharing!
Remarkable! Its genuinely amazing article, I
have got much clear dea on the topic of from this paragraph.
Great blog here! Also your site loads uup very fast! What host are you using?
Can I get your affiliate link to your host? I wish my site
loaddd up as fast as yours lol
What’s up, of course this article is genuinely pleasant and I have learned
lot of things from it regarding blogging. thanks.
There is a HEPA filter, and the air doesn’t smell dusty when cleaning.
Traditional vacuums use bags to capture dirt and pet fur prior to exhausting air.
If you have carpet in your home you will need a vacuum with a beater brush.
Hello, i read your blog occasionally and i own a similar one and i was
just curious if you get a lot of spam comments? If so how do
you reduce it, any plugin or anything you can suggest? I get
so much lately it’s driving me insane so any help is very much
appreciated.
I’ll immediately take hold of your rss as
I can not find your e-mail subscription hyperlink or newsletter service.
Do you have any? Please permit me understand so that I may subscribe.
Thanks.
you’re truly a excellent webmaster. The site loading pace is incredible.
It seems that you’re doing any distinctive trick. Moreover, The contents are masterwork.
you have performed a excellent activity in this topic!
When some one searches for his required thing, thus he/she wants to be available that in detail, therefore that
thing is maintained over here.
At this time it seems like Drupal is the top blogging platform
out there right now. (from what I’ve read) Is that
what you’re using on your blog?
Howdy just wanted to give you a quick heads up and let
you know a few of the pictures aren’t loading correctly.
I’m not sure why but I think its a linking issue. I’ve tried it in two different internet browsers and both show the
same outcome.
Others” tend to be porches in which appear sporadically, perhaps not
anticipated because of the size and can carry
on to snag numerous obtain streaks.