1

The following codes are to remove duplicates from a sorted list. It runs OK on my computer. My question is about using

head = head->next;

after

delete head;

below. Is it illegal? The codes generate correct results on my compiler. Will it depend on compiler? Or it complies with C++11 standards?

struct ListNode {
    int val;
    ListNode *next;
    explicit ListNode(int x) : val(x), next(nullptr) { }
};


class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head && (head->next = deleteDuplicates(head->next)) && head->next->val == head->val){
            delete head;
            head = head->next;
        }
        return head;
    }
};


int main() {
    ListNode *h = new ListNode(0);
    auto cur=h;
    cur->next= new ListNode(1);
    cur=cur->next;
    cur->next= new ListNode(2);
    cur=cur->next;
    cur->next= new ListNode(2);
    cur=cur->next;

    Solution sol;
    auto xx=sol.deleteDuplicates(h);
    return 0;
}
drbombe
  • 609
  • 7
  • 15
  • 2
    you are entering *undefined behavior*. – Daniel A. White Dec 26 '17 at 01:53
  • 1
    Completely undefined. The data at that position in memory is garbage as soon as you delete it. – Silvio Mayolo Dec 26 '17 at 01:54
  • But there is no warning on my compiler ... – drbombe Dec 26 '17 at 01:54
  • 6
    It's not your compiler's responsibility to warn you against every possible UB. If it was possible to do so, we wouldn't have runtime errors nearly as often. – Silvio Mayolo Dec 26 '17 at 01:54
  • @drbombe *The codes generate correct results on my compiler.* -- And fails miserably on Visual Studio in debug mode. A big, ugly message box pops up saying `Exception thrown. Read access violation. head->next was 0xDDDDDDDD`. – PaulMcKenzie Dec 26 '17 at 02:10
  • Thanks for letting me know! It does depending on compiler as we suspected! So I change the codes to "auto oldhead=head; head = head->next; delete oldhead;". Many thanks for your help ~ – drbombe Dec 26 '17 at 02:15
  • 1
    @drbombe -- Change compiler options such as optimizations, and you may see a different story. The bottom line is that the behavior is undefined. – PaulMcKenzie Dec 26 '17 at 02:30
  • @drbombe You could run the same compiled program twice and get different results each time. It is undefined. – Galik Dec 26 '17 at 03:34

2 Answers2

2

No, it is not illegal. It is Undefined Behaviour when you try to access a pointer that had recently been deleted and wasn't assigned new value. Keep in mind that results of UB may seem correct at first, but it is not specified (defined) when they suddenly 'stop working'.

EDIT:

Since there are questions about whether or not the compiler should warn us about UB, let's take a look at this example:

int main()
{
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    int position;
    std::cin >> position;
    std::cout << arr[position];
}

We are simply inputting a number and outputting a value of that position in our array. Seems like a straightforward program, but what happens when position > 4 or position < 0? We are then accessing an invalid index (Array access out of bounds) resulting in Undefined Behaviour.

Should compiler warn us about it? Maybe, but image how many warnings a simple code could then produce. Maybe if we added some checkings and then tried to access the array, the warning could go away, but keep in mind that this is a very simple example. Not always a compiler can predict when UB may occur, thus they generally don't warn us about it.

Fureeish
  • 12,533
  • 4
  • 32
  • 62
1

No, it is not "illegal". The behaviour (dereferencing a deleted pointer) is undefined according to C++ standards and, when behaviour is undefined, the compiler is not required to issue any diagnostic at all.

When behaviour is undefined, the results may vary with compiler, with choice of compiler flags (e.g. optimisation settings), only emerge with some inputs to the program and not others, or vary with phase of the moon (e.g. because the code causes the program to access the system clock).

In simple cases, compilers may be able to detect the concern, and issue warnings. Most modern compilers are configured to NOT do that by default (sadly, as a historical result of lobbying by programmers who were required to produce code that compiled without warnings and cared more about that metric than about whether their code worked as required) but can be forced to do so with compilation options (e.g. warning flags).

In complicated cases, the compiler is simply not able to detect instances of undefined behaviour.

A lot of undefined behaviour results from edge cases - undefined behaviour only occurs on very specific sets of input values, so cannot be detected unless the compiler evaluates ALL possible sets of inputs the program might receive at run time.

Another class of undefined behaviour arises due to compiler optimisation - the compiler does a large number of transformations of code (or intermediate representation of code) in order to optimise performance (or size, or some other metric). To date, no compiler exists that can give a warning something like "As a result of 100 distinct code transformations by the optimiser, it was found that there MIGHT be one or more instances of undefined behaviour somewhere between lines 20 and 40 of the original source." Even if there was a compiler that COULD do that, such messages would not be particularly helpful to programmers.

Peter
  • 35,646
  • 4
  • 32
  • 74