# Alp Mestanogullari's Blog

## Templates for unique id generation for types : a beginning

Posted in Uncategorized by alpmestan on 2009/10/31

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 :

$generateid(int) = 5$
$generateid(char) = 7$
$\forall T,\, generateid(\textit{pointer to T}) = 2 \cdot generateid(T)$
$\forall T,\, generateid(\textit{ref to T}) = 3 \cdot generateid(T)$
$\forall T,\, generateid(\textit{vector of T}) = 11 \cdot generateid(T)$

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].

Tagged with: , ,

### 24 Responses

1. NN said, on 2009/11/01 at 12:43 pm

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🙂

2. alpmestan said, on 2009/11/01 at 2:23 pm

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.

3. pizer said, on 2009/11/01 at 6:54 pm

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?

4. pizer said, on 2009/11/01 at 6:56 pm

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>*.

5. alpmestan said, on 2009/11/01 at 10:58 pm

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.

6. SpiceGuid said, on 2009/11/09 at 2:21 pm

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

7. alpmestan said, on 2009/11/09 at 2:32 pm

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.

8. car credit loan said, on 2010/09/11 at 5:31 pm

Powerful post.

9. http://www.youtube.com/ said, on 2013/07/25 at 7:53 am

Navy maintains no such experiment occurred.
Only in the final decade has there been an explosion on solar conversion technologies.

10. Ervin said, on 2014/02/17 at 2:37 am

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!

11. 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!

12. zumba instructor dvd said, on 2014/04/23 at 2:39 pm

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

13. Howdy! This blog post couldn’t be ritten much
better! Going through thgis article reminds me of my previous roommate!

Thanks for sharing!

14. Georgianna said, on 2014/05/04 at 2:59 am

Remarkable! Its genuinely amazing article, I
have got much clear dea on the topic of from this paragraph.

15. Great blog here! Also your site loads uup very fast! What host are you using?
loaddd up as fast as yours lol

lot of things from it regarding blogging. thanks.

17. Lucinda said, on 2014/05/28 at 8:11 pm

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.

18. free ecard said, on 2014/06/23 at 5:39 pm

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.

Do you have any? Please permit me understand so that I may subscribe.
Thanks.

20. شركة نقل عفش said, on 2014/07/23 at 7:58 pm

It seems that you’re doing any distinctive trick. Moreover, The contents are masterwork.
you have performed a excellent activity in this topic!

21. عزل اسطح said, on 2014/08/04 at 1:09 pm

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.

22. clash of clans gems generator said, on 2014/08/13 at 4:16 am

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?

23. Thousand Oaks Low Cost Locksmith said, on 2014/09/21 at 7:49 am

Howdy just wanted to give you a quick heads up and let