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

Question

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.

You're erasing an item while looping on the list. The iterator is probably losing its right order. — Yochai Timmer, Sep 15 '11 at 17:34

Kerrek SB · Accepted Answer · 2011-09-16T13:24:41.957

2

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());

edited Sep 16 '11 at 13:24

answered Sep 15 '11 at 17:47

Kerrek SB

464,522
92
875
1,084

thank you for giving me solutions. now i am able to delete unwanted keys of my map. but, i cant solve vector element deletion. when i am using idiomatic way as you given, i got the following errors. –DetectR.cpp expected primary-expression before '[' token DetectR.cpp expected primary-expression before ']' token DetectR.cpp expected unqualified-id before "bool" . i want to say, i am using DevC++. also, my compiler didnt recognise your given "auto". so i used normal way. – niro Sep 16 '11 at 12:51
@g_niro: You probably don't have support for lambdas. You can write the lambda as a completely equivalent predicate. Do you need help with that? – Kerrek SB Sep 16 '11 at 13:06
@g_niro: Added. I don't actually know the type of your `mylabel` container, so you have to fill that in for `LabelVector`. Just add the class definition somewhere above your code. – Kerrek SB Sep 16 '11 at 13:25
thanks. i will try to follow your way. actually, mylabel is a vector of another class objects. if i say that, base class = Feature, contains some attributes of polygons. derived class = Features. so, Features = vector is equal to mylabel object. so, i want to know whether this struct code should be written inside my program .cpp itself or inside the class where Features (or mylabel) is defined? me, i am using somebody else customised library. so i am confusing. make clear please. – niro Sep 16 '11 at 13:57
@g_niro: You can put the predicate struct directly inside your function, or perhaps inside your own header -- it doesn't matter, as long as it's visible when you call `remove_if`. If you have use for it later, maybe put it in a relevant local header. – Kerrek SB Sep 16 '11 at 14:05
sorry, it didnt work. i got this error. D:DetectR.cpp no matching function for call to `remove_if(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, LabelFinder, __gnu_cxx::__normal_iterator > >)'. if i ask – niro Sep 16 '11 at 15:28
@g_niro: are you including ``? – Kerrek SB Sep 16 '11 at 15:47
yes yes.. i have already included it. if i ask what this LabelFinder(mylabel)does? does it return true or false (according to the Label()!=1) for all elemant inside mylabel one after the other? then, does it automatically go one after the other? is it done by bool operator()? may be, plz tell me other way (not the idiomatic way) to solve this....thanks – niro Sep 16 '11 at 16:16
`LabelFinder(mylabel)` constructs a temporary instance, which binds the reference to `mylabel`, and which provides `operator()`, which in turn returns a bool. If you post your code on ideone or pastebin or something like that, I'll take a look what's wrong. – Kerrek SB Sep 16 '11 at 16:26

Nawaz · Answer 2 · 2011-09-15T17:51:19.130

1

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:

vector::erase()

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 :

Erase-Remove Idiom

edited Sep 15 '11 at 17:51

answered Sep 15 '11 at 17:40

Nawaz

353,942
115
666
851

Hmmm... this is a very poor way to erase from a vector. – Kerrek SB Sep 15 '11 at 17:42
@Kerrek: Agree; there are idiomatic way to erase items from a vector. But I don't exactly know what he wants to remove, and how he makes that decision. – Nawaz Sep 15 '11 at 17:45
@Nawaz: i am not sure what it would be, but, i want to remove all the elments whose label is not equal to 1. – niro Sep 15 '11 at 17:46
He has the exact same problem erasing from the map. You should add that to your answer. – Mooing Duck Sep 15 '11 at 17:48
@Nawaz: thanks for the comments. i solved the "key" deletion. but, vector elements, inside map cant solve. it took very long time even to run the way you pointed out (not the idiomtic way) and i got exe error at the end. i tried idiomatic way. it also didnt work for me. – niro Sep 16 '11 at 12:58

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

2 Answers2

Linked