Löschen eines Strukturelements in einer Liste

Question

Ich versuche, ein Element aus einer Liste zu entfernen. Die Elemente sind Strukturen. Ich habe eine schwierige Zeit damit. Die Online-Beispiele sind nicht für Strukturelemente. Ich habe versucht, den Schlüssel/die Werte auf die Standardwerte zu setzen, aber sobald ich die Daten durchlaufen habe, druckt es einen Leerraum, was bedeutet, dass das Element immer noch da ist. Ich muss es komplett entfernen. Unten ist mein Code.

.H Datei

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

Hier ist die Löschfunktion I umzusetzen versuchen.

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 ist ein std::string, aber die Liste enthält Node s.
Auch data[i].back() ist das letzte Element der Liste und nicht *it.

Sie könnten erase verwenden, um das Element zu entfernen der Iterator entspricht:

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

In diesen Tagen, mit C++ 11, sollte die folgende sein genug:

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

Aber da dies eine Hashtabelle, vermutlich ist der Index in data der Hash von key, so dass Sie dies in einen Einzeiler verwandeln könnten:

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

oder, da Sie nur ein Element finden müssen (Ihre Schlüssel nur auf einen Wert Karte), können Sie etwas länger erhalten, aber effizienter:

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

Answer 2

Der letzte Versuch mit dem remove() ist fast die richtige Lösung. Sie müssen nur den Iterator für das Entfernen verwenden:

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

Dies wird vorausgesetzt, dass "Schlüssel" eindeutig ist.

Answer 3

Rene wurde von Lösch denken, die einen Iterator braucht . list::remove Durchsucht die gesamte Liste nach dem angegebenen Wert und löscht alle Vorkommen. Also, versuchen Sie data[I].erase(it)