Runtime error (Heap-buffer-overflow)

Dec 21, 2019 at 1:28pm
Question was to remove duplicates from a vector in place. Here is my code:-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
        if(nums.size()==1)
            return 1;
        auto i = nums.begin();
        auto j = nums.begin() + 1;
        while(j != nums.end())
        {
            while(*i==*j)
                ++j;
            i++;
            *i = *j;
        }
        return i - nums.begin();
    }
};


The online platform needs me to only write the body of the function "removeDuplicates". When I run this locally on codeblocks, it works fine. But when I run it on the platform , am getting this error

=================================================================
==30==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000003c at pc 0x000000405d32 bp 0x7ffe90a54ef0 sp 0x7ffe90a54ee8
READ of size 4 at 0x60200000003c thread T0
    #1 0x7f9b821472e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
0x60200000003c is located 0 bytes to the right of 12-byte region [0x602000000030,0x60200000003c)
allocated by thread T0 here:
    #0 0x7f9b83b6cce0 in operator new(unsigned long) (/usr/local/lib64/libasan.so.5+0xe9ce0)
    #3 0x7f9b821472e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa fd fd fa fa 00[04]fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==30==ABORTING

Can someone point out what the problem is.
Last edited on Dec 21, 2019 at 1:29pm
Dec 21, 2019 at 2:28pm
j becomes equal to nums.end() inside your loop, and then you try to dereference j. This is very bad.

Filling it with protection against that will fix it, but it's ugly and is clearly a horrible bodge:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeDuplicates(vector<int>& nums) {
		if (nums.empty())
			return 0;
		if (nums.size() == 1)
			return 1;
		auto i = nums.begin();
		auto j = nums.begin() + 1;
		while (j != nums.end())
		{
			while (j != nums.end()  &&  *i == *j)
				if (j != nums.end()) ++j;
			i++;

			if (j != nums.end()) *i = *j;
		}
		return i - nums.begin();
	}


I note that your code only works if the vector is sorted already. Is that expected?
Last edited on Dec 21, 2019 at 2:30pm
Dec 21, 2019 at 5:11pm
That worked just fine. Thank you @Repeater.

I note that your code only works if the vector is sorted already. Is that expected?

Yes, the given numbers are sorted.

Filling it with protection against that will fix it, but it's ugly and is clearly a horrible bodge

What would be a better way of doing it ?
Last edited on Dec 21, 2019 at 5:12pm
Dec 21, 2019 at 5:13pm
Change your loop so that inside the loop you never try to access j after incrementing it.
Dec 21, 2019 at 6:17pm
If you can use the <algorithm> library, std::remove can find and delete duplicates.

https://en.cppreference.com/w/cpp/algorithm/remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <algorithm>

void remove(std::vector<int>& v)
{
	auto end = v.end();

	for (auto it = v.begin(); it != end; ++it)
	{
		end = std::remove(it + 1, end, *it);
	}

	v.erase(end, v.end());
}

int main()
{
	std::vector<int> v = { 5, 2, 1, 3, 4, 2, 9, 2, 4, 5, 5, 6 };

	remove(v);

	for (const auto& it : v) { std::cout << it << ' '; }
	std::cout << '\n';
}


A std::set/std::unordered_set can't hold duplicates:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <unordered_set>

void remove(std::vector<int>&);

int main()
{
	std::vector<int> v = { 5, 2, 1, 3, 4, 2, 9, 2, 4, 5, 5, 6 };

	remove(v);

	for (const auto& it : v) { std::cout << it << ' ';  }
	std::cout << '\n';
}

void remove(std::vector<int>& v)
{
	// copy the vector to a set
	std::unordered_set<int> s(v.begin(), v.end());

	// copy the unique values back to the vector
	v.assign(s.begin(), s.end());
}

std::set would automatically sort the vector, std::unordered_set would retain the unsorted ordering.

https://en.cppreference.com/w/cpp/container/set
https://en.cppreference.com/w/cpp/container/unordered_set
Last edited on Dec 21, 2019 at 6:31pm
Dec 21, 2019 at 6:31pm
std::unique can remove duplicate consecutive elements:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>

void remove(std::vector<int>&);

int main()
{
	std::vector<int> v = { 5, 2, 1, 3, 4, 2, 9, 2, 4, 5, 5, 6 };

	remove(v);

	for (const auto& it : v) { std::cout << it << ' '; }
	std::cout << '\n';
}

void remove(std::vector<int>& v)
{
	std::sort(v.begin(), v.end());
	v.erase(std::unique(v.begin(), v.end()), v.end());
}


There are more methods to erase duplicate vector entries using C++ language features other than the 3 I used.

"Rolling your own solution" is a good learning exercise, though.

Dec 21, 2019 at 7:03pm
On the subject of rolling ones own, and drifiting off topic, I once found myself debugging some code that incorrectly sorted a vector, and then clumsily de-duplicated it.A BIG vector. I mean, this thing was huge. It was eating significant amounts of processor. That neatly taken care of, I idly looked ahead to see what was being done with all this vector that had been freshly de-duplicated.

It was being dumped into a set. I went to the pub.
Topic archived. No new replies allowed.