CODEWITHSUNDEEP
c++
Hypnoz
Hypnoz

Reputation: 1136

Why this function is causing no error?

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

Initially I thought there would be an error. Because in free(runner), if i free the memory, i can not access runner->Next. But GCC compiler ran successfully.

Actually if i change free to delete runner, it is also correct. can i ask the reason may be free or delete just tell you the memory is available no actually clear data inside, so you can also access Next. And can i ask how to improve it?

Upvotes: 1

Views: 161

Answers (3)

Barney Szabolcs
Barney Szabolcs

Reputation: 12514

Your program can work fine since free() only marks some memory as free, but it does not actually overwrite it. Owing to this, the chances are your solution will run correctly most of the time as in your function you are not using any new memory. (At least in single threaded environment.)

On the other hand, I would go and fundamentally change the function like this:

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

You can even go as far as writing this:

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

But I think that can be a bit too much, as it does not reflect that we need to go one element after an other.

My reasons for the fundamental change:

  1. In C++ free() is called delete. It is used in pair with new (which is used in c++ instead of malloc() or calloc()). delete is used like this:

    delete runner;
    // and new is used like this:
    Some_type *p = new Some_type();

  2. STL has already a LinkedList, so it makes sense to use that. It is called std::forward_list. You want to use erase_after, with a nice example.

  3. You want to use std::unsorted_map instead of hash_map (again, since it is in STL). The best is always the std solution.

  4. One of the main purpose of classes is to hide away necessary pointer activity, so in function headers I would rather use references instead of pointers, so at least your function should be

    void removeDuplicateWithHashtable(LinkedListElement<char>& head)

Upvotes: 1

mathematician1975
mathematician1975

Reputation: 21351

It is not a compilation error but the problem (undefined behaviour) will manifest itself at runtime. If you choose to call free on unallocated memory the compiler will not stop you.

Upvotes: 4

Armen Tsirunyan
Armen Tsirunyan

Reputation: 132984

Such logical errors cannot be detected by a compiler! Instead, the program has undefined behavior, which can include running seemingly OK, crashing, or producing all sorts of garbage. There are a lot of (and I can't stress that enough, like, a LOT) situations that result in undefined behavior

Upvotes: 4

Related Questions