asmcriminal asmcriminal - 28 days ago 18
C++ Question

Erasing a struct element within a list

What I am trying to do is remove an element from a list. The elements are structs. I am having a difficult time with this. The examples online are not for struct elements. I tried to set the key/values to default values but once I iterate through the data it prints a white space meaning the element is still there. I need to remove it completely. Below is my code.

.H file

#include<list>
#include<queue>
using namespace std;

template <typename K, typename V, int CAP>
class HashTable {
public:
HashTable(int(*)(const K&));
bool HashTable<K, V, CAP>::containsKey(const K& key) const;
HashTable<K, V, CAP>& operator=(const HashTable<K, V, CAP>&);
V& operator[](const K&); // setter
V operator[](const K&) const; // getter
queue<K> keys() const;
int size() const {return siz;};
void deleteKey(const K&);

private:
int getIndex(const K& key) const;
struct Node{K key; V value;};
int(*hashCode)(const K&);
list<Node> data[CAP];
int cap;
int siz;
};


Here is the delete function I am trying to implement.

template<typename K, typename V, int CAP>
inline void HashTable<K, V, CAP>::deleteKey(const K & key)
{
typename list<Node>::iterator it; // getters need to use const_iterator
for (int i = 0; i < CAP; i++)
{
for (it = data[i].begin(); it != data[i].end(); it++)
{
if (it->key == key)
{
// these are a few things I tried, I know this is not right.
data[i].back().key = K();
data[i].back().value = V();
data[i].remove(key); // Error C2664 'void std::list<HashTable<std::string,int,100>::Node,std::allocator<_Ty>>::remove(const _Ty &)':
// cannot convert argument 1 from 'const std::string' to 'const HashTable<std::string,int,100>::Node &' 10HashTable
}
}
}
}

Answer

key is a std::string, but the list contains Nodes.
Also, data[i].back() is the last element of the list and not *it.

You could use erase to remove the element the iterator corresponds to:

template<typename K, typename V, int CAP>
inline void HashTable<K, V, CAP>::deleteKey(const K & key)
{
  for (int i = 0; i < CAP; i++)
  {
    typename list<Node>::iterator it = data[i].begin();
    while (it != data[i].end())
    {
      if (it->key == key)
      {
         // Make 'it' a valid iterator to the next element
         it = data[i].erase(it);
      }
      else
      {
         // Only increment if we didn't erase
         it++;
      }
    }
  }
}

These days, with C++11, the following should be enough:

template<typename K, typename V, int CAP>
inline void HashTable<K, V, CAP>::deleteKey(const K & key)
{
  for (auto& bucket: data)
  {
      bucket.remove_if([&] (auto& item) { return item->key == key; });
  }
}

But since this is a hashtable, presumably the index in data is the hash of key, so you could turn this into a one-liner:

template<typename K, typename V, int CAP>
inline void HashTable<K, V, CAP>::deleteKey(const K & key)
{
    data[hashCode(key)].remove_if([&] (auto& item) { return item->key == key; });
}

or, since you only need to find one element (your keys only map to one value), you can get slightly longer but more efficient:

template<typename K, typename V, int CAP>
inline void HashTable<K, V, CAP>::deleteKey(const K & key)
{
    auto& bucket = data[hashCode(key)];
    auto it = std::find_if(bucket.begin(), 
                           bucket.end(), 
                           [&] (auto& item) { return item->key == key; });
    if (it != bucket.end())
    {
        bucket.erase(it);
    }
}