1 
void removeDuplicateWithHashtable(LinkedListElement<char> *head)
{
    LinkedListElement<char> *runner = head;
    LinkedListElement<char> *previous = nullptr;
    hash_map<char, bool> record;
    while (runner) {
        if (record.count(runner->Data) == 0) {
            pair<char, bool> item(runner->Data,true);
            record.insert(item);
        }else
        {
            free(runner);
            previous->Next = runner->Next;
        }
        previous=runner;
        runner=runner->Next;
    }
}

一开始我以为会有错误。因为在free(runner)，如果我释放内存，我无法访问 runner->Next。但是 GCC 编译器运行成功。

实际上，如果我更改为免费删除跑步者，那也是正确的。请问原因可能是空闲还是删除，只是告诉你内存可用，里面没有实际清除数据，所以你也可以访问Next。我能问一下如何改进吗？

4

3 回答 3

4

这不是编译错误，但问题（未定义的行为）将在运行时表现出来。如果您选择调用free未分配的内存，编译器不会阻止您。

于 2012-12-06T09:13:12.723 回答
4

编译器无法检测到此类逻辑错误！相反，该程序具有未定义的行为，其中可能包括看似正常的运行、崩溃或产生各种垃圾。有很多（我不能强调足够多，比如很多）情况会导致未定义的行为

于 2012-12-06T09:13:18.620 回答
1

您的程序可以正常工作，因为free()只是将一些内存标记为空闲，但实际上并没有覆盖它。因此，您的解决方案很可能在大多数情况下都能正确运行，因为在您的函数中您没有使用任何新内存。（至少在单线程环境中。）

另一方面，我会像这样从根本上改变函数：

template<typename _Tp>
void unique(forward_list<_Tp>& list)
{
  unordered_map<_Tp, bool> record;
  auto la=list.before_begin();
  for(auto it=list.begin(); it!=list.end(); ++it) 
  {
    if(record.find(*it)==record.end())
      record[*++la] = true;
    else
      list.erase_after(la);
  }
}

你甚至可以写这个：

template<typename _Tp>
void unique(forward_list<_Tp>& list)
{
  unordered_map<_Tp, bool> record;
  auto la=list.before_begin();
  for(auto e: list) 
  {
    if(record.find(e)==record.end())
      record[*++la] = true;
    else
      list.erase_after(la);
  }
}

但我认为这可能有点过分了，因为它并不反映我们需要一个接一个地进行。

我做出根本改变的原因：

  1. 在 C++free()中称为delete. 它与new（在 c++ 中用于代替malloc()or calloc()）成对使用。delete像这样使用：

    删除跑步者；
    // 并且 new 是这样使用的：
    Some_type *p = new Some_type();

  2. STL 已经有一个 LinkedList，所以使用它是有意义的。它被称为std::forward_list。你想用erase_after，用一个很好的例子。

  3. 您想使用 std::unsorted_map 而不是 hash_map （同样，因为它在 STL 中）。最好的总是标准解决方案。

  4. 类的主要目的之一是隐藏必要的指针活动，所以在函数头中我宁愿使用引用而不是指针，所以至少你的函数应该是

    void removeDuplicateWithHashtable(LinkedListElement<char>& head)

于 2012-12-06T10:16:37.350 回答