c++ - 删除列表中的结构元素

Question

我想做的是从列表中删除一个元素。元素是结构。我很难过。在线示例不适用于结构元素。我试图将键/值设置为默认值，但是一旦我遍历数据，它就会打印一个空白，这意味着该元素仍然存在。我需要完全删除它。下面是我的代码。

.H文件

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

这是我要实现的删除功能。

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 1

key 是一个 std::string，但列表包含 Node。
此外，data[i].back() 是列表的最后一个元素，而不是 *it。

您可以使用erase 删除迭代器对应的元素:

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

如今，使用 C++11，以下内容应该就足够了:

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

但由于这是一个散列表，data 中的索引大概是 key 的散列，因此您可以将其变成单行代码:

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

或者，因为你只需要找到一个元素(你的键只映射到一个值)，你可以稍微长一点但效率更高:

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