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.

Answer 3

For fun here are two more ways, I present a slightly more efficient method with no breaks or goto. I then present a less efficient method which sorts first.

Both of these methods are simple to read and understand.

These are really just meant to show alternatives to the other answers. The first containsPairs method I have requires card values be in the range of 0 to 13 and will break if that is not true, but is very slightly more efficient than any of the other answers I've seen.

int containsPairs(const vector<int> &hand)
{
    int pairs{ 0 };
    std::vector<int> counts(14); //note requires 13 possible card values
    for (auto card : hand){
        if(++counts[card] == 2){
            ++pairs;
            counts[card] = 0;
        }
    }
    return pairs;
}

int containsPairs(const vector<int> &hand)
{
    int pairs{ 0 };

    std::sort(hand.begin(), hand.end());
    for (size_t i = 1;i < hand.size();++i){
        if(hand[i] == hand[i - 1]){
            ++i;
            ++pairs;
        }
    }
    return pairs;
}

Note: several of the other answers will treat 3 similar cards in a hand as 2 pairs. The two methods above take this into account and instead will only count 1 pair for 3 of a kind. They will treat it as 2 pairs if there are 4 similar cards.

Answer 4

goto is only one problem. Another big problem is that your method is inefficient.

Your method

Your current method basically looks at the first card, iterates over the rest and look for the same value. It then goes back to the second card and compares it to the rest. This is O(n**2).

Sorting

How would you count pairs in real life? You'd probably sort the cards by value and look for pairs. If you sort efficiently, it would be O(n*log n).

Distributing

The fastest method would be to prepare 13 slots on a table and distribute the cards according to their face value. After distributing every card, you can count the cards on each slot and see if any slot holds at least 2 cards. It's O(n) and it would also detect three of a kind or four of a kind.

Sure, there's not much difference between n**2 and n when n is 5. As a bonus, the last method would be concise, easy to write and goto-free.

Answer 5

If you really want to avoid goto, then you can just call the function recursively, where the goto [label] line would be, passing in any variables whose state you want to save as parameters. However, I would recommend sticking to the goto.

Answer 6

I would personally put those two loops in a lambda, instead of goto would return from this lambda with indication that the loops should restart, and would call the lambda in a loop. Something like that:

auto iterate = [&hand, &pairs]() {
             {
              ... // your two loops go here, instead of goto return true
             }
             return false;
}

while (iterate());

Small addition: I do not think this is the best algorithm to find pairs of card in a deck. There are much better options for that. I rather answer the omnipresent question of how to transfer control in or out of two loops at once.

Answer 7

Yes you should avoid using goto here.

It is an unnecessary use of goto specifically because the algorithm does not need it. As an aside, I tend not to use goto, but I am not in staunch opposition of it like many. goto is a great tool to break nested loops or to exit a function cleanly when an interface does not support RAII.

There are a few inefficiencies with your current approach:

• There is no reason to re-search the list from the beginning when you find a matching pair. You have already searched all prior combinations. Removing cards does not change the relative order of non-removed cards and additionally, it does not provide you any more pairs.
• There is no need to remove items from the middle of hand. For this problem removing from the middle of an std::vector presumably representing a hand of 5 cards is not a problem. If the number of cards is large however, this can be inefficient. In problems like this you should ask yourself, does the order of elements matter? The answer is no it does not matter. We can shuffle any cards that have not already been paired and still achieve the same answer.

Here is a modified version of your code:

int countPairs(std::vector<Card> hand)
{
    int pairs{ 0 };

    for (decltype(hand.size()) i = 0; i < hand.size(); ++i)
    {
        // I assume getFace() has no side-effects and is a const
        // method of Card.  If getFace() does have side-effects
        // then this whole answer is flawed.
        const Card& c1 = hand[i];
        for (auto j = i + 1; j < hand.size(); ++j)
        {
            const Card& c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                // We found a matching card for card i however we
                // do not need to remove card i since we are
                // searching forward.  Swap the matching card
                // (card j) with the last card and pop it from the
                // back.  Even if card j is the last card, this
                // approach works fine.  Finally, break so we can
                // move on to the next card.
                pairs++;
                std::swap(c2, hand.back());
                hand.pop_back(); // Alternatively decrement a size variable
                break;
            }
        }
    }
    return pairs;
}

You could touch up the above approach to use iterators if desired. You could also take in a const reference std::vector and use std::reference_wrapper to re-sort the container.

For an overall better algorithm build a frequency table of each face value and its corresponding count.

Answer 8

I'd probably do it this way:

Features:

• 3 of a kind is not a pair
• returns a vector of cards in order of descending Face indicating which faces are pairs in the hand.

 

std::vector<Card> reduceToPair(std::vector<Card> hand)
{
    auto betterFace = [](auto&& cardl, auto&& cardr)
    {
        return cardl.getFace() > cardr.getFace();
    };

    std::sort(begin(hand), end(hand), betterFace);

    auto first = begin(hand);
    while (first != end(hand))
    {
        auto differentFace = [&](auto&& card)
        {
            return card.getFace() != first->getFace();
        };
        auto next = std::find_if(first + 1, end(hand), differentFace);
        auto dist = std::distance(first, next);
        if (dist == 2)
        {
            first = hand.erase(first + 1, next);
        }
        else
        {
            first = hand.erase(first, next);
        }
    }

    return hand;
}

usage:

pairInfo = reduceToPair(myhand);
bool hasPairs = pairInfo.size();
if (hasPairs)
{
  auto highFace = pairInfo[0].getFace();
  if (pairInfo.size() > 1) {
    auto lowFace = pairInfo[1].getFace();
  }
}

Answer 9

If sorting of cards by face is possible and allowed we can count pairs using just a single pass without erasing anything:

bool Compare_ByFace(Card const & left, Card const & right)
{
    return(left.Get_Face() < right.Get_Face());
}

size_t Count_Pairs(vector<Card> hand)
{
    size_t pairs_count{0};
    if(1 < hand.size())
    {
        sort(hand.begin(), hand.end(), &Compare_ByFace);
        auto p_card{hand.begin()};
        auto p_ref_card{p_card};
        for(;;)
        {
           ++p_card;
           if(hand.end() == p_card)
           {          
               pairs_count += static_cast< size_t >((p_card - p_ref_card) / 2);
               break;
           }
           if(p_ref_card->Get_Face() != p_card->Get_Face())
           {
               pairs_count += static_cast< size_t >((p_card - p_ref_card) / 2);
               p_ref_card = p_card;
           }
        }
    }
    return(pairs_count);
}

Answer 10

#include <vector>
#include <unordered_map>
#include <algorithm>

std::size_t containsPairs(const std::vector<int>& hand)
{
    // boilerplate for more readability
    using card_t = std::decay_t<decltype(hand)>::value_type;
    using map_t = std::unordered_map<card_t, std::size_t>;

    // populate map and count the entrys with 2 occurences
    map_t occurrences;
    for (auto&& c : hand) { ++occurrences[c]; }
    return std::count_if( std::cbegin(occurrences), std::cend(occurrences), [](const map_t::value_type& entry){ return entry.second == 2; });
}

Answer 11

One problem with goto is that the labels tend to go walkies on errant refactoring. That's fundamentally why I don't like them. Personally, in your case, if you need to keep the algorithm as it is, I'd roll the goto into a recursive call:

int containsPairs(vector<Card>&/*Deliberate change to pass by reference*/hand)
{
    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())
            {
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                return 1 + containsPairs(hand); 
            }
        }
    }
    return 0;
}

The overhead in the stack frame creation is negligible cf. the std::vector manipulations. This might be impractical depending on the call site: you can no longer call the function with an anonymous temporary for example. But really there are better alternatives for pair identification: why not order the hand more optimally?

Answer 12

Are you allowed to change the order of elements in a vector? If yes, just use an adjacent_find algorithm in a single loop.

Thus you will not only get rid of goto, but get better performance (currently you have O(N^2)) and guaranteed correctness:

std::sort(hand.begin(), hand.end(), 
    [](const auto &p1, const auto &p2) { return p1.getFace() < p2.getFace(); });
for (auto begin = hand.begin(); begin != hand.end(); )
{
  begin = std::adjacent_find(begin, hand.end(), 
        [](const auto &p1, const auto &p2) { return p1.getFace() == p2.getFace(); });
  if (begin != hand.end())
  {
    auto distance = std::distance(hand.begin(), begin);
    std::erase(begin, begin + 2);  // If more than 2 card may be found, use find to find to find the end of a range
    begin = hand.begin() + distance;
  }
}

Answer 13

Your implementation is not working as it counts three of a kind as one pair, four of a kind as two.

Here is an implementation I'd suggest:

int containsPairs(std::vector<Card> hand)
{
    std::array<int, 14> face_count = {0};
    for (const auto& card : hand) {
        ++face_count[card.getFace()]; // the Face type must be implicitly convertible to an integral. You might need to provide this conversion or use an std::map instead of std::array.
    }
    return std::count(begin(face_count), end(face_count), 2);
}

(demo on coliru)

It can be generalized to count not only pairs but also n of a kind by tweaking the 2.

Answer 14

The other answers so far address how to fundamentally restructure your code. They make the point that your code wasn't very efficient to begin with, and by the time you fixed that you only need to break out of one loop, so you don't need the goto anyway.

But I am going to answer the question of how to avoid goto without fundamentally changing the algorithm. The answer (as is very often the case for avoiding goto) is to move part of your code into a separate function and use an early return:

void containsPairsImpl(vector<Card>& hand, int& pairs)
{
    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));
                return;
            }
        }
    }
    hand.clear();
}

int containsPairs(vector<Card> hand)
{
    int pairs{ 0 };
    while (!hand.empty()) {
        containsPairsImpl(hand, pairs);
    }
    return pairs;
}

Notice that I pass hand and pairs by reference to the inner function so that they can be updated. If you have a lot of these local variables, or you have to break the function into several pieces, then this can become unwieldy. The solution then is to use a class:

class ContainsPairsTester {
public:
    ContainsPairsTester(): m_hand{}, m_pairs{0} {}

    void computePairs(vector<Card> hand);

    int pairs() const { return m_pairs; }
private:
    vector<Card> m_hand;
    int m_pairs;

    void computePairsImpl(vector<Card> hand);
};

void ContainsPairsTester::computePairsImpl()
{
    for (int i = 0; i < m_hand.size(); i++)
    {
        Card c1 = m_hand[i];
        for (int j = i + 1; j < m_hand.size(); j++)
        {
            Card c2 = m_hand[j];
            if (c1.getFace() == c2.getFace())
            {
                m_pairs++;
                m_hand.erase(m_hand.begin() + i);
                m_hand.erase(m_hand.begin() + (j - 1));
                return;
            }
        }
    }
    m_hand.clear();
}

void ContainsPairsTester::computePairs(vector<Card> hand)
{
    m_hand = hand;
    while (!m_hand.empty()) {
        computePairsImpl();
    }
}

Answer 15

As others have remarked, you should not only avoid goto, but also avoid writing your own code where there is a standard algorithm that can do the job. I'm surprised that no-one has suggested unique, which is designed for this purpose:

bool cardCmp(const Card& a, const Card& b) {
    return a.getFace() < b.getFace();
}

size_t containsPairs(vector<Card> hand) {
    size_t init_size = hand.size();

    std::sort(hand.begin(), hand.end(), cardCmp);
    auto it = std::unique(hand.begin(), hand.end(), cardCmp);
    hand.erase(it, hand.end());

    size_t final_size = hand.size();
    return init_size - final_size;
}

(First ever answer on StackOverflow - apologies for any faux pas!)

Answer 16

While goto isn't really that awful if you need it, it is not necessary here. Since you only care about the number of pairs, it is also not necessary to record what those pairs are. You can just xor through the entire list.

If you are using GCC or clang, the following will work. In MSVC, you can use __popcnt64() instead.

int containsPairs(vector<Card> hand)
{
    size_t counter = 0;
    for ( Card const& card : hand )
        counter ^= 1ul << (unsigned) card.getFace();

    return ( hand.size() - __builtin_popcountll(counter) ) / 2u;
}