我应该避免在这里使用 goto 吗？如果是这样，如何？

Question

我正在编写一个函数，该函数需要一只手并检查配对：

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;
}

当它在第 10 行找到对时，我想删除它找到对的手中的牌，然后用删除的牌重新开始整个循环以找到第二对（如果有的话）。对我来说，goto 是最直观的方法，但在这种情况下，是这样吗？

Answer 1

我个人会把这两个循环放在一个 lambda 中，而不是 goto 将从这个 lambda 中 return 指示循环应该重新启动，并在循环中调用 lambda。类似的东西：

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

while (iterate());

小补充：我不认为这是在一副牌中找到成对牌的最佳算法。有更好的选择。我宁愿回答一个无处不在的问题，即如何同时将控制权移入或移出两个循环。

Answer 2

如果你真的想避免 goto，那么你可以递归调用该函数，goto [label] 行所在的位置，传入任何你想将其状态保存为参数的变量。但是，我建议坚持使用 goto。

Answer 3

我可能会这样做：

特点：

3个不是一对
returns 一个卡片向量，按照面的降序排列，表示手中的面是对的。

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;
}

用法：

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

Answer 4

goto 的一个问题是标签往往会在错误的重构上走动。 这就是我不喜欢它们的根本原因。就您个人而言，如果您需要保持算法不变，我会将 goto 滚动到递归调用中：

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;
}

创建堆栈帧的开销可以忽略不计。 std::vector 操作。这可能不切实际，具体取决于调用站点：例如，您不能再使用匿名临时函数调用该函数。但确实有更好的配对识别方法：为什么不更优化地排序手牌？

Answer 5

试试这个：

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;
}

这几乎就是你的版本，唯一的区别是没有goto，而是i--; break;。这个版本比你的效率更高，因为它只做了一次双循环。

是不是更清楚了？嗯，这是个人喜好。我完全不反对goto，我认为它目前的"never use it"状态应该修改。有时 goto 是最佳解决方案。

这是另一个更简单的解决方案：

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;
}

基本上，当它找到一对时，它只移除更远的牌，并打破循环。所以没有必要对 i.

狡猾

Answer 6

一个（稍微）更快的算法也避免了 goto

从 std::vector 中删除永远不会很快，应该避免。复制 std::vector 也是如此。通过避免两者，您也可以避免 goto。例如

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;
}

对于大手，这个算法仍然很慢，因为 O(N^2)。排序会更快，之后对必须是相邻的卡片，给出 O(N logN) 算法。

然而 更快，O(N)，是使用 unordered_set 不是成对的卡片，而是所有其他卡片：

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;
}

对于足够小的 hand.size()，这可能不会比上面的代码快，这取决于 sizeof(Card) and/or 其构造函数的成本。类似的方法是使用 distribution，如 :

中所建议

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;
}

当然，如果 Card 可以简单地映射到一个小整数，则这些方法可以更简单地实现，而无需散列。

Answer 7

是否允许更改向量中元素的顺序？如果是，只需在单个循环中使用 adjacent_find 算法。

因此，您不仅可以摆脱 goto，而且可以获得更好的性能（目前您有 O(N^2)）并保证正确性：

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 8

如果可以并允许按面对卡片进行分类，我们可以只使用一次传递来计算对数，而不会擦除任何内容：

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 9

为了好玩，这里有另外两种方法，我提出了一种稍微更有效的方法，没有中断或转到。然后，我提出了一种效率较低的方法，该方法首先进行排序。

这两种方法都易于阅读和理解。

这些实际上只是为了展示其他答案的替代方案。我拥有的第一个 containsPairs 方法要求卡片值在 0 到 13 的范围内，如果不是这样，它就会中断，但它比我见过的任何其他答案都稍微高效一些。

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;
}

注意：其他几个答案会将一手牌中的 3 张相似牌视为 2 对。上面的两种方法考虑到了这一点，而只会计算 1 对 3 种。如果有4张相似的牌，他们会把它当作2对。

Answer 10

goto 只是一个问题。另一个大问题是你的方法效率低下。

你的方法

您当前的方法基本上是查看第一张卡片，遍历其余卡片并寻找相同的值。然后它返回到第二张卡片并将其与其余卡片进行比较。这是 O(n**2).

排序

在现实生活中你会如何数数？您可能会按价值对卡片进行排序并寻找成对的卡片。如果你有效率地排序，它将是 O(n*log n).

分发

最快的方法是在一张table上准备13个格子，按面值分配。分发完每张牌后，您可以清点每个插槽中的牌，看看是否有任何插槽至少有 2 张牌。它是 O(n)，它还会检测到三种或四种。

当然，当 n 为 5 时，n**2 和 n 之间没有太大区别。作为奖励，最后一种方法简洁、易于编写并且 goto-free。

Answer 11

#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 12

您的实现不工作，因为它将三种算作一对，四种算作两对。

这是我建议的实施方式：

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)

通过调整 2.

Answer 13

到目前为止，其他答案解决了如何从根本上重构代码的问题。他们指出你的代码一开始并不是很有效，当你修复时你只需要跳出一个循环，所以你不需要 goto 无论如何。

但我要回答如何在不从根本上改变算法的情况下避免goto的问题。答案（通常是避免 goto 的情况）是将部分代码移动到一个单独的函数中，并使用早期的 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;
}

请注意，我通过引用内部函数传递 hand 和 pairs，以便可以更新它们。如果你有很多这样的局部变量，或者你必须将函数分成几个部分，那么这会变得很笨拙。解决方案是使用 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 14

是的，你应该避免在这里使用 goto。

这是不必要的使用 goto 具体来说，因为算法不需要它。顺便说一句，我倾向于不使用 goto，但我并不像许多人一样坚决反对它。 goto 是打破嵌套循环或在接口不支持 RAII 时干净地退出函数的好工具。

您当前的方法存在一些低效问题：

找到匹配对时，没有理由从头重新搜索列表。您已经搜索了所有先前的组合。移除卡片不会改变未移除卡片的相对顺序，此外，它不会为您提供更多对。
不需要删除 hand 中间的项目。对于这个问题，从 std::vector 的中间移除可能代表一手 5 张牌不是问题。然而，如果卡的数量很大，这可能是低效的。在这样的问题中你应该问问自己，元素的顺序重要吗？答案是否定的没关系。我们可以洗牌任何尚未配对的卡片，但仍然会得到相同的答案。

这是您的代码的修改版本：

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;
}

如果需要，您可以改进上述方法以使用迭代器。您还可以使用 const 引用 std::vector 并使用 std::reference_wrapper 对容器重新排序。

为了整体上更好的算法，建立每个面值的频率 table 及其对应的计数。

Answer 15

正如其他人所说，您不仅应该避免 goto，还应该避免在有可以完成这项工作的标准算法的地方编写自己的代码。我很惊讶没有人建议 unique，它是为此目的而设计的：

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;
}

（Whosebug 上的第一个回答 - 对任何失礼表示歉意！）

Answer 16

虽然 goto 如果您需要它并没有那么糟糕，但在这里没有必要。由于您只关心对的数量，因此也没有必要记录这些对是什么。您可以 xor 浏览整个列表。

如果您使用的是 GCC 或 clang，则以下内容将起作用。在 MSVC 中，您可以改用 __popcnt64()。

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;
}

我应该避免在这里使用 goto 吗？如果是这样，如何？

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

c++

loops

for-loop

goto

function

你的方法

排序

分发