Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualRobot Ninja

Posted 09 December 2012 - 04:19 PM

It has no definition, but you can specialize it for types that need to work with the hash table:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<>
struct HashTraits
{
static std::size_t Hash(const std::string &s) { /* ... */ }
static bool Equal(const std::string &s1, const std::string &s2) { /* ... */ }
};

template<>
struct HashTraits
{
static std::size_t Hash(int i) { /* ... */ }
static bool Equal(int i1, int i2) { /* ... */ }
};

// and so on...
EDIT: changed use of uintptr_t to std::size_t.

Then, if the hash table needs to hash an object it does so by calling "HashTraits::Hash(key)". A similar thing is done for equality comparisons when searching buckets for matching keys. If there's no HashTraits specialization for the Key type available you get a compiler error, indicating that you need to write one. There are some other options in the design space, here. You might have two separate traits templates, one for the hash and one for equality. Or you might forgo the equality part altogether and just rely on the existence of an operator==.

Now, rather than using traits, you could also simply have the requirement that the user must ensure that there's a Hash() function that takes a Key and returns a hash value, rather like you have the operator< requirement for your SortedList. However, some care must be taken as e.g. Hash(const std::string &) might get called even if the Key type is "const char *", due to C++ overload resolution. This may not be the desired behaviour. Using the traits stuff avoids this problem because there has to be a template specialization for the exact type.

So there's a tradeoff between simplicity and correctness.

Thanks for the explanation on traits, it seems like a very useful strategy. Also I'm assuming you're saying that the more correct way is to require that there is an existing hash function for their key type? Would using a function pointer parameter with the hash function help solve issues with custom types, or is using traits the more common approach?

Quote
e‍dd, on 08 December 2012 - 07:18 PM, said:
/** Getter function.
* Returns a ptr to the object stored in the node.
*/
T* Data() const { return &m_data; }
IMHO, this should return a reference. In situations where it's possible for there not to be a value, I can understand the choice to return a pointer. But that's not the case here.
Wouldn't I have to feed the function an external variable then? I can't think of any other way to avoid making the function more complicated. Is the extra parameter just a necessary evil?
I Think we're getting our wires crossed. All I'm really suggesting is that the function be changed to "const T &Data() const { return m_data; }" or "T &Data() { return m_data; }". Actually, now that I look at it again, I'm surprised that the original function even compiles (as there should be a 'const' before the 'T *'). Is this Data() function used anywhere, at present?

I see. I didn't realize that doing something like T& Data() { return m_data; } was legal. From what I recalled about returning by reference, I thought that you had to do something like:
T& Data( T &data )
{
data = m_data;
return data;
}
I must have missed something...
Also, I haven't actually started compiling yet (bad idea?). I've just been designing the data structures I need for my assignment, so no, the Dat() function is not being used anywhere yet.

Quote
by explicit constructors you mean things like the copy and assignment constructors?
No, there's a C++ keyword, "explicit".

At present, I can do weird stuff like this:
?
1
2
3
4
5
void foo(const ChainedHashTable &tab); // suppose this function exists

// ...

foo(42); // compiler allows this, as ChainedHashTable's constructor is not explicit!

This is the same mechanism that allows you to pass a "const char *" to a function that takes an std::string. For your constructor, the automatic conversion is probably not wanted!

Posted Image The compiler allows that? So this is basically a concern for any custom type, huh? Does the explicit keyword only apply to the constructor, including the copy constructor and assignment operator?

Presumably the number of buckets is going to change during the life of a hash table, either automatically, or at the user's request(?).

Honestly now that I think about it, resizing the hash table after data has been added is probably a bad idea. It screws up the distribution of the data that the hashing algorithm is trying to avoid. So maybe I should just not include that option.

Well, let me put is this way. You hand me a hash table, which you say is const. Should I be able to change its content (without resorting to nasty hacks)?

The idiomatic answer for C++ is no, I should not be able to change its content. Sure, the contents of the hash table aren't direct members of the structure, but that sounds like you're just trying to weasel your way out of keeping things const-correct ;)

What often happens is that two overloads are provided for things like this:
?
1
2
const Data* LookUp( Key key ) const;
Data* LookUp( Key key );

Okay, so why would anyone include an overloaded function that grants access to the data if there is a similar function that is trying to protect the data? It seems counter-intuitive to me.

Up until this point you've got something approaching a very general hash table. So it's a bit weird to have something this specific here, IMHO. Is there any way you can move this specific function outside of the hash table?

Like I mentioned before in this post, my first inclination is to use function pointers, but your traits concept seems like a good solution as too.

Thanks again for replying to my questions. These changes will be very helpful. Using std::size_t instead of unsigned int or regular int for some reason was mind-blowing. Posted Image The same goes for traits. +50 more to you!

*EDIT* What's with the quotes in my post? Unlike yours, the code boxes never copy over right. I've been using the "selective quote" feature.

#1Robot Ninja

Posted 09 December 2012 - 04:17 PM

It has no definition, but you can specialize it for types that need to work with the hash table:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<>
struct HashTraits
{
static std::size_t Hash(const std::string &s) { /* ... */ }
static bool Equal(const std::string &s1, const std::string &s2) { /* ... */ }
};

template<>
struct HashTraits
{
static std::size_t Hash(int i) { /* ... */ }
static bool Equal(int i1, int i2) { /* ... */ }
};

// and so on...
EDIT: changed use of uintptr_t to std::size_t.

Then, if the hash table needs to hash an object it does so by calling "HashTraits::Hash(key)". A similar thing is done for equality comparisons when searching buckets for matching keys. If there's no HashTraits specialization for the Key type available you get a compiler error, indicating that you need to write one. There are some other options in the design space, here. You might have two separate traits templates, one for the hash and one for equality. Or you might forgo the equality part altogether and just rely on the existence of an operator==.

Now, rather than using traits, you could also simply have the requirement that the user must ensure that there's a Hash() function that takes a Key and returns a hash value, rather like you have the operator< requirement for your SortedList. However, some care must be taken as e.g. Hash(const std::string &) might get called even if the Key type is "const char *", due to C++ overload resolution. This may not be the desired behaviour. Using the traits stuff avoids this problem because there has to be a template specialization for the exact type.

So there's a tradeoff between simplicity and correctness.

Thanks for the explanation on traits, it seems like a very useful strategy. Also I'm assuming you're saying that the more correct way is to require that there is an existing hash function for their key type? Would using a function pointer parameter with the hash function help solve issues with custom types, or is using traits the more common approach?

Quote
e‍dd, on 08 December 2012 - 07:18 PM, said:
/** Getter function.
* Returns a ptr to the object stored in the node.
*/
T* Data() const { return &m_data; }
IMHO, this should return a reference. In situations where it's possible for there not to be a value, I can understand the choice to return a pointer. But that's not the case here.
Wouldn't I have to feed the function an external variable then? I can't think of any other way to avoid making the function more complicated. Is the extra parameter just a necessary evil?
I Think we're getting our wires crossed. All I'm really suggesting is that the function be changed to "const T &Data() const { return m_data; }" or "T &Data() { return m_data; }". Actually, now that I look at it again, I'm surprised that the original function even compiles (as there should be a 'const' before the 'T *'). Is this Data() function used anywhere, at present?

I see. I didn't realize that doing something like T& Data() { return m_data; } was legal. From what I recalled about returning by reference, I thought that you had to do something like:
T& Data( T &data )
{
data = m_data;
return data;
}
I must have missed something...
Also, I haven't actually started compiling yet (bad idea?). I've just been designing the data structures I need for my assignment, so no, the Dat() function is not being used anywhere yet.

Quote
by explicit constructors you mean things like the copy and assignment constructors?
No, there's a C++ keyword, "explicit".

At present, I can do weird stuff like this:
?
1
2
3
4
5
void foo(const ChainedHashTable &tab); // suppose this function exists

// ...

foo(42); // compiler allows this, as ChainedHashTable's constructor is not explicit!

This is the same mechanism that allows you to pass a "const char *" to a function that takes an std::string. For your constructor, the automatic conversion is probably not wanted!

:o The compiler allows that? So this is basically a concern for any custom type, huh? Does the explicit keyword only apply to the constructor, including the copy constructor and assignment operator?

Presumably the number of buckets is going to change during the life of a hash table, either automatically, or at the user's request(?).

Honestly now that I think about it, resizing the hash table after data has been added is probably a bad idea. It screws up the distribution of the data that the hashing algorithm is trying to avoid. So maybe I should just not include that option.

Well, let me put is this way. You hand me a hash table, which you say is const. Should I be able to change its content (without resorting to nasty hacks)?

The idiomatic answer for C++ is no, I should not be able to change its content. Sure, the contents of the hash table aren't direct members of the structure, but that sounds like you're just trying to weasel your way out of keeping things const-correct ;)

What often happens is that two overloads are provided for things like this:
?
1
2
const Data* LookUp( Key key ) const;
Data* LookUp( Key key );

Okay, so why would anyone include an overloaded function that grants access to the data if there is a similar function that is trying to protect the data? It seems counter-intuitive to me.

Up until this point you've got something approaching a very general hash table. So it's a bit weird to have something this specific here, IMHO. Is there any way you can move this specific function outside of the hash table?

Like I mentioned before in this post, my first inclination is to use function pointers, but your traits concept seems like a good solution as too.

Thanks again for replying to my questions. These changes will be very helpful. Using std::size_t instead of unsigned int or regular int for some reason was mind-blowing. Posted Image The same goes for traits. +50 more to you!

PARTNERS