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

ciste 发布于 2019-11-06 c++ 最后更新 2019-11-06 20:00 22 浏览

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

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

xqui

赞同来自:

虽然如果你需要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;
}

caut

赞同来自:

如果可以按面部对牌进行分类并允许我们只使用一次传球就可以计算对,而不会删除任何东西:

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

peum

赞同来自:

我可能会这样做: 特征:

  • 3种不是一对
  • 按照下降的顺序返回卡片矢量,表示手中哪些脸是成对的。
&NBSP;
std::vector<Card> reduceToPair(std::vector<Card> hand)
{
    auto betterFace = 
    {
        return cardl.getFace() > cardr.getFace();
    };
std::sort(begin(hand), end(hand), betterFace);
auto first = begin(hand);
    while (first != end(hand))
    {
        auto differentFace = &
        {
            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();
  }
}

tut

赞同来自:

你的实现不起作用,因为它有三对作为一对,四种作为两对。 这是我建议的实现:

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,可以推广它不仅可以计算对,还可以计算n种。

avelit

赞同来自:

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

taut

赞同来自:

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

taut

赞同来自:

尝试这个:

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,我认为应该修改其当前的“从不使用它”状态。在某些情况下,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无需苛刻。

hquae

赞同来自:

(略微)更快的算法也避免了gotostd::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'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;
}
当然,如果不需要散列,Card可以简单地映射到一个小整数,这些方法可以更简单地实现。

reos

赞同来自:

为了好玩,这里有两种方法,我提出了一种稍微有效的方法,没有休息或转到。然后我提出一种效率较低的方法,首先进行排序。 这两种方法都易于阅读和理解。 这些只是为了显示其他答案的替代方案。第一个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对。

sesse

赞同来自:

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

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

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

分发 最快的方法是在桌子上准备13个插槽并根据其面值分配卡片。分发每张卡后,您可以统计每个插槽上的卡,看看是否有任何插槽至少有2张卡。这是O(n),它还可以检测到三种或四种。 当然,当n是5时,n**2n之间没有太大区别。作为奖励,最后一种方法将是简洁,易于编写和goto免费。

nodio

赞同来自:

我个人会把这两个循环放在一个lambda中,而不是goto会从这个lambda返回,表明循环应该重启,并且会在循环中调用lambda。像这样的东西:

auto iterate = &hand, &pairs {
             {
              ... // your two loops go here, instead of goto return true
             }
             return false;
}
while (iterate());
小补充:我不认为这是在甲板上找到成对卡的最佳算法。有更好的选择。我宁愿回答无所不在的问题,即如何同时将控制转入或转出两个循环。

weos

赞同来自:

是的,你应该避免在这里使用gotogoto是不必要的,因为算法不需要它。顺便说一句,我倾向于不使用goto,但我并没有像许多人那样坚决反对。当界面不支持RAII时,goto是一个很好的工具来打破嵌套循环或干净地退出函数。 您当前的方法存在一些效率低下的问题:

  • 找到匹配对时,没有理由从头开始重新搜索列表。您已搜索过所有先前的组合。删除卡不会改变未移除卡的相对顺序,此外,它不会再为您提供任何配对。
  • 无需从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对容器进行重新排序。 对于整体更好的算法,建立每个面值及其对应计数的频率表。

gsint

赞同来自:

您是否可以更改向量中元素的顺序?如果是,只需在单个循环中使用adjacent_find算法。 因此,您不仅可以摆脱goto,还可以获得更好的性能(目前您有O(N^2))并保证正确性:

std::sort(hand.begin(), hand.end(), 
     { return p1.getFace() < p2.getFace(); });
for (auto begin = hand.begin(); begin != hand.end(); )
{
  begin = std::adjacent_find(begin, hand.end(), 
         { 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;
  }
}

isunt

赞同来自:

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

fnam

赞同来自:

#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), { return entry.second == 2; });
}

et_ea

赞同来自:

正如其他人所说,你不仅应该避免使用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;
}
(有关StackOverflow的第一个回答 - 为任何失礼道歉!)