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

[1] http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
[2] http://en.wikipedia.org/wiki/Commutative_ring

About these ads
Tagged with: , ,

23 Responses

Subscribe to comments with RSS.

  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!

    He constantly kept talking about this. I’ll send
    this article tto him. Pretty sure he’ll have a good read.
    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?
    Can I get your affiliate link to your host? I wish my site
    loaddd up as fast as yours lol

  16. What’s up, of course this article is genuinely pleasant and I have learned
    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.

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

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

    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!

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 251 other followers

%d bloggers like this: