4
\$\begingroup\$

I solved this question on LeetCode.com:

Alice has a hand of cards, given as an array of integers. Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards. Return true if and only if she can. For e.g., for hand=[1,2,3,6,2,3,4,7,8] and W=3, the answer should be true.

as:

class Solution { public: bool isNStraightHand(vector<int>& nums, int k) { if(nums.size()%k!=0) return false; map<int, int> _m; for(int num: nums) _m[num]++; while(_m.size()) { auto it=_m.begin(); int count=1; int prev=it->first; while(count<=k) { it->second--; if(count>1 && it->first-prev!=1) return false; else prev=it->first; count++; if(it->second==0) { auto backupIt=it; _m.erase(backupIt); //am I causing UB here? } it++; } } return true; } }; 

This works, but it doesn't look like a sturdy solution. I am curious to know if I am causing Undefined Behavior (UB) when erasing the element above. Earlier, I just had _m.erase(it);, but that wasn't good either. I think so, since the official website says:

References and iterators to the erased elements are invalidated.

so, when I do a it++ in the following line, isn't that invalid? That part in particular can probably be improved.

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

The answer is "yes" it is UB. To fix it just rewrite the part as:

if(it->second==0) { it = _m.erase(it); } else { it++; } 
\$\endgroup\$
3
  • \$\begingroup\$ @ALX23z, I am not sure it helps. If I don't it++ after erasing the element, I wouldn't be pointing to the next one in the next iteration of the inner while loop. \$\endgroup\$ Commented Jun 12, 2020 at 1:59
  • 1
    \$\begingroup\$ @J.Doe lookup reference for map::erase en.cppreference.com/w/cpp/container/map/erase it returns following iterator. What I wrote is basically from their example of use of erase. \$\endgroup\$ Commented Jun 12, 2020 at 7:19
  • \$\begingroup\$ good point! Thank you! :) \$\endgroup\$ Commented Jun 13, 2020 at 18:00

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.