CODEWITHSUNDEEP
c++struct
asmcriminal
asmcriminal

Reputation: 93

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
      }
    }
  }
}

Upvotes: 0

Views: 409

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

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);
    }
}

Upvotes: 2

Rene
Rene

Reputation: 2474

The last attempt with the remove() is almost the right solution. You just have to use the iterator for the removal:

   data[i].remove(it);
   break;  // found the element, iterator is invalid anyway: exit loop

This is assuming that 'key' is unique.

Upvotes: 0

Related Questions