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: , ,

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


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: