C++ map not deleting elements

Question

Given a target K, and an array of distinct elements, the task is to remove all pairs from the array which sums to K.

This is the approach I followed

for(i=0;i<N;i++)
    cin>>array[i];
cin>>K;
map<int, int> mp;
for(i=0;i<N;i++)
{
    if(mp.find(array[i])==mp.end())
        mp[array[i]] = 1;
    else
        mp[array[i]]++;
}

Logic for deletion

for(i=0;i<N;i++)
{
   if(mp[K-array[i]]>0)
   {            
       mp.erase(K-array[i]);
       mp.erase(array[i]);
    }
}

Print output :

cout<<mp.size();

Input :

array = 6 5 4 2 1 0
K = 6

Program output

Expected Output

Does this answer your question? [How to remove from a map while iterating it?](https://stackoverflow.com/questions/8234779/how-to-remove-from-a-map-while-iterating-it) — NutCracker, Jan 20 '20 at 10:40
I am sorry, I am a beginner I did not understand what mistake am I making — , Jan 20 '20 at 10:42
Please, make a minimal example so we can reproduce the problem (so include `main` function, all `include` statements etc) — NutCracker, Jan 20 '20 at 10:42

P0W · Accepted Answer · 2020-01-20T11:44:52.367

0

if(mp[K-array[i]]>0)

std::map::operator::[] will add if element doesn't exists

You will have to find and remove like following:

for(int i=0;i<N;i++)
{
   if(mp.find(K-array[i]) != mp.end()  && 
      K-array[i] != array[i])
      //~~~~~~~~~~~~~~~~~~~~~ check required to see k/2 = array[i]
      // Note: all numbers are distinct 
   { 
       mp.erase(K-array[i]);
       mp.erase(array[i]);
   }
}

A better strategy would be to use remove elements during scanning using std::unordered_set

std::unordered_set<int> s;

for(const auto& ele: array) {
    auto it =  s.find( K - ele);
    if ( it == s.end() ) {
     s.insert(ele);   
    } else {
        s.erase(it);
    }
}

std::cout << s.size();

See here

edited Jan 20 '20 at 11:44

answered Jan 20 '20 at 11:24

P0W

46,614
9
72
119

Downvoters please explain. I will be happy to update and remove. – P0W Jan 20 '20 at 11:26
First solution is wrong!! For Array [6, 0] it will remove 6 and 0 – cosmos Jan 20 '20 at 11:27
1

@user2407394 https://rextester.com/ROM44551 _"the task is to remove all pairs from the array which sums to K."_ isn't 6+0 =6 ? – P0W Jan 20 '20 at 11:30
In first solution you need to take into account the number of occurrence of same element. – cosmos Jan 20 '20 at 11:35
Only use `erase` when the `m[elem]` becomes 0. Otherwise, decrement the counters of both elements by the minimum of them and erase the minimum. Also, erase all occurrences of `K/2` except one if exists. – Mohammed Deifallah Jan 20 '20 at 11:44

C++ map not deleting elements

1 Answers1