C++

Forum

 
Runtime error (Heap-buffer-overflow)

SOURABH PRAKASH PATI (30)
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
Repeater (3046)
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
SOURABH PRAKASH PATI (30)
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
Repeater (3046)
Change your loop so that inside the loop you never try to access j after incrementing it.
deleted account xyzzy (5768)
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
deleted account xyzzy (5768)
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.

Repeater (3046)
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.