CODEWITHSUNDEEP
c++stliterator
niro
niro

Reputation: 977

problem with updating a map by removing some keys and also some elements

I have a map. lets say map<int, vector<int> > mymap1. I want to update mymap1 by deleting some “keys” and also removing unwanted “elements” from the vector part of the selected keys. The “key’ or the “element” going to be deleted is given from another vector, known as “mylabel”. Actually, What I need to remain in my map is the values whose label is equal to 1. (At the end, keys must have the elements whose label are 1 only.)

I have implemented this (see code below), but got some compiler errors.

map<int, vector<int> > mymap1;
map<int, vector<int> >::iterator map1;
for (map1=mymap1.begin();map1!=mymap1.end();map1++){
       int key = map1->first;
       if (mylabel[key].Label() != 1){ mymap1.erase(key);
       }

       else{
            vector<int> &myvec = map1->second;
            for (vector<int>::iterator rn=myvec.begin(); rn!=myvec.end(); rn++){
                 if (mylabel[*rn].Label() != 1) myvec.erase(myvec.begin()+(*rn));
            }                        
       }
}

for you to get an idea, i am showing some example of my map.

0 1 2 6 10
1 0 2 4 3 6
2 0 1 3 5 8
3 1 2 4 5 7
4 1 3 6 7
5 2 3 8 7 9
6 1 0 7 4
7 6 4 3 5 9 11 10 13 12
8 2 5 9 11 18 15 19 20 22
9 5 7 11 8
10 0 7 14 16
11 9 7 8 13
12 7 13 14
13 7 12 11 14 15
14 12 10 16 13 15 17
15 13 14 8 17 19
16 14 10 17 21
17 14 16 15 21 18
18 8 20 19 17 26 27
19 8 15 18
20 8 18
21 16 17 23 24
22 8
23 25 21 24 26
24 23 21
25 23 26
26 23 25 18
27 18 28
28 27

if i show you my mylabel, it is as follows.

for(int c=0;c<mylabel.size();c++){
    cout<<c<<" : "<<"label "<<mylabel[c].Label()<<endl;
}
0 : label 0
1 : label 0
2 : label 0
3 : label 0
4 : label 0
5 : label 1
6 : label 0
7 : label 1
8 : label 0
9 : label 1
10 : label 0
11 : label 1
12 : label 0
13 : label 0
14 : label 1
15 : label 1
16 : label 1
17 : label 1
18 : label 0
19 : label 0
20 : label 0
21 : label 1
22 : label 0
23 : label 0
24 : label 0
25 : label 1
26 : label 1
27 : label 0
28 : label 0

When I am deactivating the else part and running above code I got an output. But, I want to say you that it is a wrong result. I am getting extra keys that should be deleted. I can’t figure out why I got this fault result. if i show the list of keys what i got, 

5
7
9
11
14
15
16
17
20 - wrong
21
24 - wrong
25
26

could you please help me to rectify my code in order to get my modified map. thanks in advance.

Upvotes: 0

Views: 297

Answers (2)

Kerrek SB
Kerrek SB

Reputation: 477110

Your erasing logic is wrong, and you end up using invalid iterators. (You're literally pulling the rug out from under your feet if you erase an iterator and then keep using that iterator.)

For node-based containers (list, map, set, unordered), you typically erase as follows:

for (auto it = c.begin(); it != c.end(); )
{
  if (must_delete(*it))  // or it->first
  {
    c.erase(it++); // advance first, then erase previous
  }
  else
  {
    ++it;
  }
}

(This patterns is my favourite justification for the post-fix increment operator.)

For contiguous containers (vector, deque), erasing one element at a time is inefficient, because it incurs repeated moves. The preferred idiom here is "remove/erase", but it requires that you supply a suitable predicate if you don't just want to remove straight by element value. Here's an example with lambdas, for brevity:

std::vector<int> v;
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int n)->bool{return some_criterion(n);}),
        v.end());

In your situation, you could write the lambda as [mylabel&](n)->bool{ return mylabel[n].Label() != 1; }; or write a traditional predicate object if you don't have lambdas:

struct LabelFinder
{
  LabelFinder(const LabelVector & lv) : label(lv) { }

  inline bool operator()(int n) const
  {
    return label[n].Label() != 1;
  }

private:
  const LabelVector & label;
};

Now use:

v.erase(std::remove_if(v.begin(), v.end(), LabelFinder(mylabel)), v.end());

Upvotes: 2

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361492

The problem is in the for loop. std::vector<T>::erase() returns iterator to the new position followed by the erased item. So the loop should be written as:

for (vector<int>::iterator rn=myvec.begin(); rn!=myvec.end();)
{
       if (mylabel[*rn].Label() != 1) 
             rn = myvec.erase(rn);
       else
             ++rn;
}

Read the doc:

By the way, I doubt on this:

 rn = myvec.erase(myvec.begin()+(*rn));
            Vs
 rn = myvec.erase(rn);

Are you sure you want the first one?

An idiomatic way to erase elements which are not equal to one is this:

 //Define this function
 bool isNotOne(int n) {  return n != 1; }

//then do this instead of writing manual loop
 myvec.erase( remove_if(myvec.begin(), myvec.end(), isNotOne), myvec.end() );

It's called :

Upvotes: 1

Related Questions