c++ - goto用法 - 我应该避免在这里使用goto吗? 如果是这样,怎么样?




c++ goto用法 (11)

我正在编写一个函数,它需要一只手并检查对:

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是最直观的方式,但在这种情况下,这是真的吗?


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操作。 这可能是不切实际的,具体取决于调用站点:例如,您不能再使用匿名临时函数调用该函数。 但是对于对识别确实有更好的选择:为什么不更优化地订购手?


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

你的方法

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

排序

你怎么算现实生活中的对子? 您可能会按价值对卡片进行排序并寻找配对。 如果你有效排序,它将是O(n*log n)

分发

最快的方法是在桌子上准备13个插槽并根据其面值分配卡片。 分发每张卡后,您可以统计每个插槽上的卡,看看是否有任何插槽至少有2张卡。 它是O(n) ,它也可以检测到三种或四种。

当然,当n为5时, n**2n之间没有太大差别。 作为奖励,最后一种方法将是简洁,易于编写和无转义。


(稍微)更快的算法也避免了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)和/或其构造函数的成本。 类似的方法是使用Eric Duminil答案中建议的分布

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简单地映射为小整数,这些方法可以更简单地实现。


为了好玩,这里有两种方法,我提出了一种稍微有效的方法,没有休息或转到。 然后我提出一种效率较低的方法,首先进行排序。

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

这些只是为了显示其他答案的替代方案。 第一个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对。 上面两种方法考虑到了这一点,而只计算了3对的3对。 如果有4张类似的牌,他们会把它当作2对。


到目前为止,其他答案解决了如何从根本上重构您的代码。 他们指出你的代码开始时效率不高,当你修复它时你只需要打破一个循环,所以你无论如何都不需要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;
}

请注意,我通过引用传递handpairs ,以便可以更新它们。 如果你有很多这些局部变量,或者你必须将函数分成几个部分,那么这可能会变得难以处理。 那么解决方案就是使用一个类:

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

如果你真的想避免goto,那么你可以递归地调用函数,goto [label]行将在那里传入你想要保存为参数的状态的任何变量。 但是,我建议坚持使用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() + i);
                hand.erase(hand.begin() + (j - 1));
                i--;
                break;
            }
        }
    }
    return pairs;
}

这几乎是你的版本,唯一的区别是,而不是goto,有i--; break; i--; break; 。 这个版本比你的更高效,因为它只进行一次双循环。

它更清楚了吗? 嗯,这是个人偏好。 我根本不反对goto ,我认为它当前的“从不使用它”状态应该修改。 有时候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很棘手。


您是否可以更改向量中元素的顺序? 如果是,只需在单个循环中使用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;
  }
}

我可能会这样做:

特征:

  • 3种不是一对
  • 按照下降顺序返回卡片矢量,表示哪些脸部是手中的对。

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

正如其他人所说,你不仅应该避免使用goto,还应该避免在有标准算法可以完成工作的情况下编写自己的代码。 我很惊讶,没有人提出独特的,这是为此目的而设计的:

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

(有关的第一个回答 - 为任何失礼道歉!)


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




goto