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 コンパイラは正常に実行されました。

実際に無料でランナーを削除するように変更すれば、それも正しいです。理由を聞いてもよろしいですか? 空きまたは削除の可能性があります。メモリが使用可能であり、実際には内部のデータが消去されていないため、[次へ] にアクセスすることもできます。また、それを改善する方法を尋ねることはできますか?

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()calloc()delete

    ランナーを削除します。
    // そして new は次のように使用されます:
    Some_type *p = new Some_type();

  2. STL にはすでに LinkedList があるので、それを使用するのは理にかなっています。これはstd::forward_listと呼ばれます。erase_afterいい例でを使いたいと思います。

  3. hash_map の代わりに std::unsorted_map を使用します (STL にあるため)。最良の方法は、常に標準ソリューションです。

  4. クラスの主な目的の 1 つは、必要なポインター アクティビティを隠すことです。したがって、関数ヘッダーでは、ポインターの代わりに参照を使用することをお勧めします。したがって、少なくとも関数は

    void removeDuplicateWithHashtable(LinkedListElement<char>& head)

于 2012-12-06T10:16:37.350 に答える