2

我对 C++ 很陌生，我正在使用 HashTables 创建一个程序。这是为了家庭作业。这是我第一次使用和创建 HashTables，所以请提前原谅我，因为我不完全知道我在做什么。我现在遇到的主要问题是合并我的remove()功能。我可以编译代码，但是当我运行测试程序时，它崩溃了。我收到的错误是

列表迭代器不可递减

我的删除功能基于我的教授提供给我们的插入功能。只是改变了一些东西。这是我的课HTable和我的remove()功能。

class HTable
{
public:
    HTable(int size);
    void insert(  const string &s);
    void remove(string key);

private:
    vector<list<string>> List;
    int currSize;
    int tableSize;
    int hash(const string &key);
    int hashFunction(string key);
    int HTableSize;
    int *status_arr;
    ostream &   operator <<( ostream &);
};

remove()功能

inline void HTable::remove(string key)
{
    list<string> List;

    if( find( List.begin( ), List.end( ), key )  ==  List.begin( ) )
    {
        List.pop_back();
    }
}
4

3 回答 3

0 
inline void HTable::remove( string key)
{
   list<string> List;

   if( find( List.end( ), List.begin( ), key )  ==  List.begin( ) )
   {         //^^^^^^^^^^^^^^^^^^^^^^^^^
     List.pop_back();
   }

}

如果根据 find 的原型使用算法，则应该放在List.begin()前面：List.end()find

template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)

同时：

first, last Input iterators to the initial and final positions in a sequence. The range searched is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

此外，您的查找条件是错误的：

 if( find( List.begin( ), List.end( ), key )  !=  List.end( ) )
 {                                            //^^^^^
    //if key exist, remove
 }

在您的代码中，它将继续删除，直到本地List为空。

您的删除功能应如下所示：

 inline void HTable::remove( string key)
 {
   vector<list<string> >::iterator it;
   for ( it = List.begin(); it != List.end(); it ++)
   {

     if( find( (*it).begin( ), (*it).end( ), key )  !=  (*it).end( ) )
     {
        (*it).pop_back();
     }
   }
}
于 2013-04-10T23:43:51.337 回答
0

如果您想向后遍历列表，请使用 rbegin 和 rend 获取反向迭代器（如果您需要这个，是的 - 有时它可能会更好，更快：取决于上下文）：

for (std::list<...>::reverse_iterator it=list.rbegin(); it!=list.rend(); ++it)

你也可以使用自动：

for( auto it=list.rend(); it!=list.rbegn(); ++it ) {...}

于 2013-04-10T23:49:18.517 回答
0

由于您通过查找精确值从列表中删除，因此让标准模板库帮助您更容易。

对于 C++98，创建一个谓词对象来检查对象的相等性：

struct string_equal
{
   string_equal(const std::string& tgt) : target(tgt)
   {}

   bool operator()(const std::string& key) const
   {
      return key == target;
   }

   const std::string& target;
};

void remove(const std::string& key)
{
   // find the appropriate list in your vector
   list<string>& List = get_correct_list_for_key(key);

   list<string>::iterator new_end = std::remove_if(List.begin(), List.end(), string_equal(key));

   List.erase(new_end, List.end());
}

在 C++11 中，您可以使用 lambda 更轻松地做到这一点：

void remove(const std::string& key)
{
   list<string>& List = get_correct_list_for_key(key);

   auto new_end = std::remove_if(List.begin(), List.end(),
     [&] (const std::string& target) -> bool { return target == key; });

   List.erase(new_end, List.end());
}
于 2013-04-11T01:56:58.297 回答