CPP Accessing a map with a non-existing key

Question

In this function, a vector of integers and an integer is given as "nums" and "target"

I tried created a hash table with a key as target-nums[i] and a value as # of that keys

for example, if nums = [3, 3, 4, 5], target = 7

 key -> value

   |  4  ->   2

   |  3  ->   1

   |  2  ->   1

and code for function is,

vector<int> twoSum(vector<int>& nums, int target) {
    int first=0;
    int second=0;
    map<int, int> HT;
    vector<int> sol;

    for(vector<int>::iterator i=nums.begin(); i<nums.end();i++){
        if(HT[target-*i]==NULL)
            HT.insert(pair<int, int>(target - *i, 1));
        else
            HT[target-*i]++;

    }
}

However, it gives an error message of

==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000060 at pc 0x0000004193d5 bp 0x7ffe5e3cd950 sp 0x7ffe5e3cd948
READ of size 4 at 0x602000000060 thread T0
    #2 0x7f66b38802e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)"

Under the for loop, the if condition HT[target-*i]==NULL seems like it's never true.

I thought in CPP, if I access a non-existing key, it immediately initializes with a value NULL.

If so, that condition must be true whenever it sees a new key.

Which part am I wrong?

Are you saying the else part is generating the message? if I test it with a vector like [1,2,3] where no value overlaps, thus HT[target-*i] is always a new key, it still generates the same error message — shawnlee, Jan 03 '20 at 04:51
@parktomatomi But OP is inserting into `HT` which is a map though. The vector `sol` is never touched. — SacrificerXY, Jan 03 '20 at 04:55
@SacrificerXY yup, totally misread it. Will delete my comment to avoid confusion. — parktomatomi, Jan 03 '20 at 04:57
Suggestion: You can simplify the for loop by using a [ranged-based for loop](https://www.cprogramming.com/c++11/c++11-ranged-for-loop.html) — SacrificerXY, Jan 03 '20 at 05:07
I tested your code and it doesn't crash/error https://godbolt.org/z/mkdCpn — SacrificerXY, Jan 03 '20 at 05:09
Ah, but it doesn't crash if you add `return {};` to return a valid vector. I wonder that's the OP's issue. — parktomatomi, Jan 03 '20 at 05:19
Just a suggestion: Instead of `if(HT[target-*i]==NULL)`, a much better alternative is to use `map.count(target-*i)` function which returns 1 if the key is present in the map and returns 0 if not. — Ajay Dabas, Jan 03 '20 at 05:24
I guess the `if-else` is unnecessary altogether. OP can just do `HT[target-*i]++;` for all cases since it will default to zero when the key doesn't exists. — SacrificerXY, Jan 03 '20 at 05:28
Is there any reason [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) wouldn't work for you out-of-the-box? — David C. Rankin, Jan 03 '20 at 06:25

score 0 · Answer 1 · answered Jan 03 '20 at 05:24

0

if(HT[target-*i]==NULL)

This is a nonsense. This will always add a new key. Use count instead http://www.cplusplus.com/reference/map/map/count/

if(HT.count(target-*i) == 0)

or,

if(HT.find(target-*i) == HT.end())

answered Jan 03 '20 at 05:24

robthebloke

9,331
9
12

score 0 · Answer 2 · answered Jan 03 '20 at 06:13

A function which fails to return a value when it should(i.e the twoSum function) will result in undefined behavior. So anything can happen (Can undefined behavior erase the hard drive?).

The compiler will normally give a warning about this but you can promote it into an error by using the -Werror=return-type compiler flag.

See this post for more info: Why does this C++ snippet compile (non-void function does not return a value)

Remy Lebeau · Accepted Answer · 2020-01-03T17:05:14.427

In if(HT[target-*i]==NULL), the [] operator of std::map automatically inserts the requested key if it is not found. Your map holds int values, not pointers, so comparing them to NULL is wrong.

The correct way to detect if a given key is present in the map is to use the map::find() method and the iterator that it returns, eg

map<int, int> HT;
vector<int> sol;

for(vector<int>::iterator i = nums.begin(); i != nums.end(); ++i){
    map<int, int>::iterator found = HT.find(target - *i);
    if (found == HT.end())
        HT.insert(make_pair(target - *i, 1));
    else
        found->second++;
}

// populate and return sol as needed...

However, there is no need to manually search and insert keys. It would be easier to just let the map auto-insert new keys for you. The default value of an auto-inserted value will be 0, which you would then increment to 1 when you call the ++ operator on a newly inserted value, eg:

map<int, int> HT;
vector<int> sol;

for(vector<int>::iterator i = nums.begin(); i != nums.end(); ++i){
    HT[target - *i]++;
}

// populate and return sol as needed...

If you are using C++11 or later, use a range-based for loop to simply the loop:

map<int, int> HT;
vector<int> sol;

for(int i : nums){
    HT[target - i]++;
}

// populate and return sol as needed...

Thank you! this was what I was looking for – shawnlee Jan 03 '20 at 15:53 — shawnlee, Jan 03 '20 at 15:53

CPP Accessing a map with a non-existing key

3 Answers3