ansaurus

Question

Will C++0x provide hashing functions for std::type_info?

Answer 1

+6 A:

The fact that type_info is not less-than comparable isn't as much a problem for using it as a map key as the fact that type_info is non-copyable. :-)

In C++03, type_info has a before() member function that provides an ordering of type_info objects.

In C++0x, type_info has a hash_code() member function (C++0x FCD §18.7.1/7):

size_t hash_code() const throw();
Returns: an unspeciﬁed value, except that within a single execution of the program, it shall return the same value for any two type_info objects which compare equal.

Remark: an implementation should return different values for two type_info objects which do not compare equal.

type_info objects resulting from the typeid operator exist until the end of the program, so it is safe to use a type_info* as a map key. However, to the best of my knowledge, there is no guarantee that if you apply typeid to two objects of the same type you will get two references to the same type_info object.

If you do use type_info* as a map key, I'd use a custom comparator that dereferences the pointers and compares the type_info objects themselves (using the aforementioned before() or hash_code() for ordering).

James McNellis 2010-08-23 22:32:31

@James: D'oh! Perhaps I can use `std::type_info *` (because there's only once instance of a particular type_info class?) ?

Billy ONeal 2010-08-23 22:34:30

@Billy: That should be safe (see my edit for caveats).

James McNellis 2010-08-23 22:39:31

@James: That could be difficult because `std::type_info` objects don't provide an efficient way to compare themselves. Looks like it's back to the home brew solution for me :/

Billy ONeal 2010-08-23 22:56:28

@Billy: Wait, what? They have `operator==`, and although two objects of the same type may not return the same instance of a `type_info` object, they must compare equal (and generated the same hash).

GMan 2010-08-23 23:03:06

@GMan: Yes, but std::map requires `operator<`, not `operator==`. I suppose I can use `std::unordered_map` but I'm trying to leave as much in C++03 as reasonably possible. (That said, if there was an off the shelf way to solve this in C++0x I'd consider that, hence the question :) )

Billy ONeal 2010-08-23 23:08:46

@Billy: You can, however, write a `bool compare(const type_info* x, const type_info* y) { return x->before(*y); }`, or compare the hash codes returned by `hash_code()` using `operator<`.

James McNellis 2010-08-23 23:12:24

However, upon re-reading the text from the C++0x FCD, I don't think I'd rely on `hash_code()` returning a unique value for two different `type_info` objects... that "should" word makes me very, very nervous. I'd stick with `before()`.

James McNellis 2010-08-23 23:24:31

@James: Ah, that 'should' is dubious. Makes sense though; in the same way `name()` can `return 0;`, so can `hash_code()`. I think `before()` is the best option here.

GMan 2010-08-23 23:26:14

@James + @GMan: Then the real question is why the standard does not define `std::type_info::operator<` ...

Billy ONeal 2010-08-24 01:04:46

@Billy: Likely because, semantically, it shouldn't. What does it mean to say one type is less than another?

Dennis Zickefoose 2010-08-24 01:15:33

@Billy: I'd guess it's because while the ordering is guaranteed to be consistent within a single execution of a program, the ordering is not guaranteed to be consistent across separate executions. I don't think it's typical for objects to compare differently in different executions of a given program. However, that's kind of lame and I just made that up. I could be completely wrong. :-)

James McNellis 2010-08-24 01:23:34

@Dennis: I don't know but apparently they have already thought of one, because there is a `before` member. In this case I don't even care about whether the objects are really less than -- I just need equivalence tests to work.

Billy ONeal 2010-08-24 01:25:07

The hash function isn't *required* to return unique values because it's a hash function. A hashing container must deal with hash collisions. Ideally, the compiler would generate a perfect hash function for the typeinfo objects as they're all known at compile time. The standard isn't requiring it, possibly because it could be non-trivial.

caspin 2010-08-24 01:53:37

@caspin: the compiler could do so (perfect hash) for a single library, but how would you coordinate multiple libraries, knowing that template types are shared among them while other types will only appear in one ? It gets tricky...

Matthieu M. 2010-08-24 06:15:34

@Matthieu: Well, the `type_info` objects for different types must be distinct (they cannot compare equal to each other), so they must occupy different locations in memory and if you are on a platform where `sizeof (size_t) == sizeof (uintptr_t)`, then you can simply cast the address of the `type_info` struct and use that as its hash code. This works for most (but certainly not all) systems.

James McNellis 2010-08-24 12:14:20

@James McNellis: I am not that confident, would a `basic_string<char, allocator<char> >` have one instance per library, and thus possibly one `typeinfo` per library... and thus a variety of possible addresses (one per library) ? I really think templates could mess things up here...

Matthieu M. 2010-08-24 16:31:40

@Matthieu: Oops; you're right. I was neglecting what I said earlier, that applying `typeid` to two instances of a type might yield different `type_info` instances that compare equal.

James McNellis 2010-08-24 17:04:45

ansaurus

tags:

views:

answers:

Will C++0x provide hashing functions for std::type_info?

related questions