Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actuale‍dd

Posted 08 December 2012 - 09:26 PM

My hash table contains a sorted linked list class that I also created for a previous assignment,

Does it need to be sorted? If the load factor is low enough (or adaptive/user-modifyable), this is quite possibly a performance pessimization. It shouldn't affect correctness though, but it does mean any key that is put in to the table needs to support operator<, std::less, or whatever your sorted list uses. This requirement is abnormal for a hash table, at least in my experience.

but I'm trying to figure out how I would deal with a look up in the hash table.

Well, you need a generic function of some kind that returns a hash for a key. You might use a traits mechanism to allow custom hashing for arbitrary types. Sensible default traits could be provided for common key types (strings, integers, etc). If you don't know what a "traits mechanism" is, feel free to ask.

The other thing you need is an equality comparison for the keys. operator== should suffice for starters, as it can be overloaded for arbitrary types.

My first idea was to implement a find function in my list class, but I can't figure out how to design it so that it is flexible enough for my hash table to use (i.e. if my hash table decided to do a look up with a string rather instead of a number, and vice versa).

Well you only need to find by comparing keys. Again, using operator== is probably a good starting point. Although, presumably you'll need to keep a sorted list of something like std::pair<Key, Value> and using operator== on a pair won't do the right thing.

If your list wasn't sorted, you could expose an iterator interface, like std::list, so that you can use std::find_if() with an appropriate predicate. But because it is sorted, I can see the benefit of providing a find_if() method. It could take a predicate, like the generic std::find_if() function.

Here is my list class. My get function should be returning a ptr to the data object, right?:

Which get function? I don't see one.

I skim-read the code. Here are some comments.

template <typename T, typename Node = ListNode<T>>
class SortedList
{
public:
[...]
Node* Front();


Do you want to expose the nodes? Or just the values they contain? By returning Node objects, the user can "accidentally" modify any next/prev pointers.

The only reason I can think of to provide my own node type would be for "intrusive links", but your SortedList doesn't seem to allow that (which is fine). Is the Node template parameter necessary?

int Size() const;

Is int the best type to use here?

T Pop();

I'm just going to post this slightly insidious link. It's probably a bit mean at this stage, but if you can follow it and realise why I've posted it after your Pop() method, you're doing well :)

I note that you haven't provided a copy constructor or assignment operator. If you don't want to do that at this stage, you should explicitly make your class uncopyable. The way you do this in C++98 (private, unimplemented methods) and C++11 (putting "= delete" at the end of the method declarations) is different though the former way will still work.

template <typename T, typename Node>
inline bool SortedList<T, Node>::IsEmpty() const
{
if (m_count == 0)
  return true;
else
  return false;
}


Personally, I find "return m_count == 0;" to be more idiomatic, but that's a minor thing.

template <typename T, typename Node>
void SortedList<T, Node>::Print() const
{
if (m_count == 0)
{
  std::cout << "There are no items in the list.\n";
}
else
{
  Node* pCurrentNode = m_pFront;
  for (unsigned int i = 0; i < m_count; i++)
  {
   std::cout << *(pCurrentNode->Data()) << std::endl;
   pCurrentNode = pCurrentNode->Next();
  }
}
}

Useful for debugging I suspect, but slightly odd (though maybe it was a requirement for the assignment?).

What if I want to comma-separate my output? What If I want to print it to a string or a file? If you provided an iteration interface, I could do this.

Here is my default node structure for my list (Is it overkill to encapsulate the data members of the node?):

template <typename T>
class ListNode
{
public:
/** Class constructor.
  * @param item  Object to store inside the node.
  * @param pNext Ptr to the following node.
  */
ListNode(const T &amp;item, ListNode *pNext = nullptr)
  : m_data(&amp;item), m_pNext(pNext) {}

/** Class destructor
  * Deallocates heap memory generated by the class in addition to
  * destroying the class instance.
  */
~ListNode() {}

Technically a destructor call doesn't release the memory associated with *this, so the comment isn't entirely accurate.

/** Getter function.
  * Returns a ptr to the object stored in the node.
  */
T* Data() const { return &amp;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.

protected:
T m_data;   ///< Stores node's value.
ListNode *m_pNext; ///< Points to next node, if any.

Prefer 'private' to 'protected', for a couple of reasons.

First, it's easier to change things from private to protected than the other way around. If something starts out protected and later you decide you really did mean private, then you might have other code depending on that member which you'll now have to modify. However, if you start out with private, switching to protected won't break any other code. But do you ever envision that someone will actually inherit your ListNode class, which is afterall the only reason we'd ever want to make something protected? If the answer is 'no', then private is definitely the way to go. If that assumption is wrong (and I doubt it is), we can easily change to protected later. However...

'protected' is really much closer to 'public' than it is to 'private', as it still allows access to parts of your class. The code that's actually accessing the protected stuff is probably a different audience, but that's the only difference. So you shoud still try provide a well-thought-out interface, just like you do with public stuff, where implementation details are hidden to a practical degree.

In this particular case, you can already access the data through Data() and get/set the next node, so there's really no need for protected at all.

I think ListNode should probably be un-copyable.

template <typename Data, typename Key>
class ChainedHashTable

It's more common to have the key appear first, though no biggie.

{
public:
ChainedHashTable( int size = 11 );

11?
Is int the best type for the size?
Do you know about explicit constructors?

int Hash( Key key ) const;

Is int the best type for the return value?
Should key be passed by reference-to-const?

void Insert( const Data &amp;data, Key key );

Again, it's normal for the key to come first.
Should key be passed by reference-to-const?

Data* LookUp( Key key ) const;

Should key be passed by reference-to-const?
Should the return type be const-qualified?

private:
std::vector<SortedList> *m_pTable;

Perhaps a typo, but do you really want a pointer to a vector, here?

/** Collision resolution func.
  * Inserts data into the hashed chain, in order.
  * @param index Value of the index where the collision occurred.
  */
void Resolve( int index ) const;

I don't understand this function, or its description. Inserts what data into the hashed chain? Missing a parameter, perhaps?
Should the method be const?

#1e‍dd

Posted 08 December 2012 - 09:18 PM

My hash table contains a sorted linked list class that I also created for a previous assignment,

Does it need to be sorted? If the load factor is low enough (or adaptive/user-modifyable), this is quite possibly a performance pessimization. It shouldn't affect correctness though, but it does mean any key that is put in to the table needs to support operator<, std::less, or whatever your sorted list uses. This requirement is abnormal for a hash table, at least in my experience.

but I'm trying to figure out how I would deal with a look up in the hash table.

Well, you need a generic function of some kind that returns a hash for a key. You might use a traits mechanism to allow custom hashing for arbitrary types. Sensible default traits could be provided for common key types (strings, integers, etc).

The other thing you need is an equality comparison for the keys. operator== should suffice for starters, as it can be overloaded for arbitrary types.

My first idea was to implement a find function in my list class, but I can't figure out how to design it so that it is flexible enough for my hash table to use (i.e. if my hash table decided to do a look up with a string rather instead of a number, and vice versa).

Well you only need to find by comparing keys. Again, using operator== is probably a good starting point. Although, presumably you'll need to keep a sorted list of something like std::pair<Key, Value> and using operator== on a pair won't do the right thing.

If your list wasn't sorted, you could expose an iterator interface, like std::list, so that you can use std::find_if() with an appropriate predicate. But because it is sorted, I can see the benefit of providing a find_if() method. It could take a predicate, like the generic std::find_if() function.

Here is my list class. My get function should be returning a ptr to the data object, right?:

Which get function? I don't see one.

I skim-read the code. Here are some comments.

template <typename T, typename Node = ListNode<T>>
class SortedList
{
public:
[...]
Node* Front();


Do you want to expose the nodes? Or just the values they contain? By returning Node objects, the user can "accidentally" modify any next/prev pointers.

The only reason I can think of to provide my own node type would be for "intrusive links", but your SortedList doesn't seem to allow that (which is fine). Is the Node template parameter necessary?

int Size() const;

Is int the best type to use here?

T Pop();

I'm just going to post this slightly insidious link. It's probably a bit mean at this stage, but if you can follow it and realise why I've posted it after your Pop() method, you're doing well :)

I note that you haven't provided a copy constructor or assignment operator. If you don't want to do that at this stage, you should explicitly make your class uncopyable. The way you do this in C++98 (private, unimplemented methods) and C++11 (putting "= delete" at the end of the method declarations) is different though the former way will still work.

template <typename T, typename Node>
inline bool SortedList<T, Node>::IsEmpty() const
{
if (m_count == 0)
  return true;
else
  return false;
}


Personally, I find "return m_count == 0;" to be more idiomatic, but that's a minor thing.

template <typename T, typename Node>
void SortedList<T, Node>::Print() const
{
if (m_count == 0)
{
  std::cout << "There are no items in the list.\n";
}
else
{
  Node* pCurrentNode = m_pFront;
  for (unsigned int i = 0; i < m_count; i++)
  {
   std::cout << *(pCurrentNode->Data()) << std::endl;
   pCurrentNode = pCurrentNode->Next();
  }
}
}

Useful for debugging I suspect, but slightly odd (though maybe it was a requirement for the assignment?).

What if I want to comma-separate my output? What If I want to print it to a string or a file? If you provided an iteration interface, I could do this.

Here is my default node structure for my list (Is it overkill to encapsulate the data members of the node?):

template <typename T>
class ListNode
{
public:
/** Class constructor.
  * @param item  Object to store inside the node.
  * @param pNext Ptr to the following node.
  */
ListNode(const T &item, ListNode *pNext = nullptr)
  : m_data(&item), m_pNext(pNext) {}

/** Class destructor
  * Deallocates heap memory generated by the class in addition to
  * destroying the class instance.
  */
~ListNode() {}

Technically a destructor call doesn't release the memory associated with *this, so the comment isn't entirely accurate.

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

protected:
T m_data;   ///< Stores node's value.
ListNode *m_pNext; ///< Points to next node, if any.

Prefer 'private' to 'protected', for a couple of reasons.

First, it's easier to change things from private to protected than the other way around. If something starts out protected and later you decide you really did mean private, then you might have other code depending on that member which you'll now have to modify. However, if you start out with private, switching to protected won't break any other code. But do you ever envision that someone will actually inherit your ListNode class, which is afterall the only reason we'd ever want to make something protected? If the answer is 'no', then private is definitely the way to go. If that assumption is wrong (and I doubt it is), we can easily change to protected later. However...

'protected' is really much closer to 'public' than it is to 'private', as it still allows access to parts of your class. The code that's actually accessing the protected stuff is probably a different audience, but that's the only difference. So you shoud still try provide a well-thought-out interface, just like you do with public stuff, where implementation details are hidden to a practical degree.

In this particular case, you can already access the data through Data() and get/set the next node, so there's really no need for protected at all.

I think ListNode should probably be un-copyable.

template <typename Data, typename Key>
class ChainedHashTable

It's more common to have the key appear first, though no biggie.

{
public:
ChainedHashTable( int size = 11 );

11?
Is int the best type for the size?
Do you know about explicit constructors?

int Hash( Key key ) const;

Is int the best type for the return value?
Should key be passed by reference-to-const?

void Insert( const Data &data, Key key );

Again, it's normal for the key to come first.
Should key be passed by reference-to-const?

Data* LookUp( Key key ) const;

Should key be passed by reference-to-const?
Should the return type be const-qualified?

private:
std::vector<SortedList> *m_pTable;

Perhaps a typo, but do you really want a pointer to a vector, here?

/** Collision resolution func.
  * Inserts data into the hashed chain, in order.
  * @param index Value of the index where the collision occurred.
  */
void Resolve( int index ) const;

I don't understand this function, or its description. Inserts what data into the hashed chain? Missing a parameter, perhaps?
Should the method be const?

PARTNERS