Should I avoid using goto here? If so, how?

Question

I am coding for a function that takes a hand and checks for pairs:

int containsPairs(vector<Card> hand) {     int pairs{ 0 };      loopstart:     for (int i = 0; i < hand.size(); i++)     {         Card c1 = hand[i];         for (int j = i + 1; j < hand.size(); j++)         {             Card c2 = hand[j];             if (c1.getFace() == c2.getFace())             {                 pairs++;                 hand.erase(hand.begin() + i);                 hand.erase(hand.begin() + (j - 1));                 goto loopstart;             }         }     }     return pairs; } 

When it finds pair on line 10, I want to delete the cards in the hand it found the pair with and then restart the whole loop with the deleted cards to find a second pair, if there is one. For me, goto was the most intuitive way to do this, but in this case, is that true?

Answer 1

Try this:

int containsPairs(vector<int> hand) {     int pairs{ 0 };      for (int i = 0; i < hand.size(); i++)     {         int c1 = hand[i];         for (int j = i + 1; j < hand.size(); j++)         {             int c2 = hand[j];             if (c1 == c2)             {                 pairs++;                 hand.erase(hand.begin() + i);                 hand.erase(hand.begin() + (j - 1));                 i--;                 break;             }         }     }     return pairs; } 

This is almost your version, the only difference is that instead of goto, there is i--; break;. This version is more efficient than yours, as it only does the double-loop once.

Is it more clear? Well, that's a personal preference. I'm not against goto at all, I think its current "never use it" status should be revised. There are occasions where goto is the best solution.

---

Here's another one, even simpler solution:

int containsPairs(vector<int> hand) {     int pairs{ 0 };      for (int i = 0; i < hand.size(); i++)     {         int c1 = hand[i];         for (int j = i + 1; j < hand.size(); j++)         {             int c2 = hand[j];             if (c1 == c2)             {                 pairs++;                 hand.erase(hand.begin() + j);                 break;             }         }     }     return pairs; } 

Basically, when it finds a pair, it removes only the farther card, and breaks the loop. So there is no need to be tricky with i.

Answer 2

A (slightly) faster algorithm also avoids the goto

Erasing from a std::vector is never fast and should be avoided. The same holds for copying a std::vector. By avoiding both, you also avoid the goto. For example

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand {     size_t num_pairs = 0;     std::unordered_set<size_t> in_pair;      for(size_t i=0; i!=hand.size(); ++i)     {         if(in_pair.count(i)) continue;         auto c1 = hand[i];         for(size_t j=i+1; j!=hand.size(); ++j)         {             if(in_pair.count(j)) continue;             auto c2 = hand[j];             if (c1.getFace() == c2.getFace())             {                 ++num_pairs;                 in_pair.insert(i);                 in_pair.insert(j);             }         }     }     return num_pairs; } 

For large hands, this algorithm is still slow, since O(N^2). Faster would be sorting, after which pairs must be adjacent cards, giving a O(N logN) algorithm.

Yet faster, O(N), is to use an unordered_set not for the cards in pairs, but for all other cards:

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand {     size_t num_pairs = 0;     std::unordered_set<Card> not_in_pairs;     for(auto card:hand)     {         auto match = not_in_pairs.find(card));         if(match == not_in_pairs.end())         {             not_in_pairs.insert(card);         }         else         {             ++num_pairs;             not_in_pairs.erase(match);         }        }     return num_pairs; } 

For sufficiently small hand.size(), this may not be faster than the code above, depending on the sizeof(Card) and/or the cost of its constructor. A similar approach is to use distribution as suggested in Eric Duminil's answer:

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand {     std::unordered_map<Card,size_t> slots;     for(auto card:hand)     {         slots[card]++;     }     size_t num_pairs = 0;     for(auto slot:slots)     {         num_pairs += slot.second >> 1;     }     return num_pairs; } 

Of course, these methods can be implemented much more simply if Card can be trivially mapped into a small integer, when no hashing is required.