3
\$\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
\$\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\$ – J. Doe Jun 12 '20 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\$ – ALX23z Jun 12 '20 at 7:19
  • \$\begingroup\$ good point! Thank you! :) \$\endgroup\$ – J. Doe Jun 13 '20 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.