c++ - while - ¿Debería evitar usar goto aquí? ¿Si es así, cómo?




while loop c++ (11)

Estoy codificando una función que toma una mano y busca pares:

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

Cuando encuentre el par en la línea 10, quiero eliminar las cartas en la mano con la que encontró el par y luego reiniciar todo el ciclo con las tarjetas eliminadas para encontrar un segundo par, si es que hay uno. Para mí, goto fue la forma más intuitiva de hacerlo, pero en este caso, ¿es cierto?


¿Se te permite cambiar el orden de los elementos en un vector? Si es así, simplemente use un algoritmo de búsqueda adjacent_find en un solo bucle.

Por lo tanto, no solo eliminará goto , sino que obtendrá un mejor rendimiento (actualmente tiene O(N^2) ) y una corrección garantizada:

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

Como han comentado otros, no solo debe evitar ir, sino también evitar escribir su propio código donde hay un algoritmo estándar que puede hacer el trabajo. Me sorprende que nadie haya sugerido que sea único, que está diseñado para este propósito:

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

(Primera respuesta en - ¡disculpas por cualquier paso de falsa!)


Para divertirse aquí hay dos formas más, presento un método un poco más eficiente sin interrupciones o goto. Luego presento un método menos eficiente que se ordena primero.

Ambos métodos son simples de leer y entender.

Estos solo tienen la intención de mostrar alternativas a las otras respuestas. El primer método containsPairs que tengo requiere que los valores de las tarjetas estén en el rango de 0 a 13 y se romperán si eso no es cierto, pero es un poco más eficiente que cualquiera de las otras respuestas que he visto.

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

Nota: varias de las otras respuestas tratarán 3 cartas similares en una mano como 2 pares. Los dos métodos anteriores tienen esto en cuenta y en su lugar solo contarán 1 par por 3 de un tipo. Lo tratarán como 2 pares si hay 4 cartas similares.


Personalmente pondría esos dos bucles en una lambda, en lugar de goto volvería de esta lambda con indicación de que los bucles deberían reiniciarse, y llamaría a la lambda en un bucle. Algo como eso:

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

while (iterate());

Pequeña adición : no creo que este sea el mejor algoritmo para encontrar pares de cartas en un mazo. Hay opciones mucho mejores para eso. Prefiero responder la pregunta omnipresente de cómo transferir el control dentro o fuera de dos bucles a la vez.


Prueba esto:

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

Esta es casi su versión, la única diferencia es que en lugar de goto, hay i--; break; i--; break; . Esta versión es más eficiente que la tuya, ya que solo hace doble bucle una vez.

¿Está más claro? Bueno, esa es una preferencia personal. No estoy en contra de goto , creo que su estado actual de "nunca lo use" debería ser revisado. Hay ocasiones en que goto es la mejor solución.

Aquí hay otra, incluso una solución más simple:

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

Básicamente, cuando encuentra un par, solo elimina la carta más lejana y rompe el ciclo. Entonces no hay necesidad de ser tramposo con i .


Si bien goto no es tan horrible si lo necesitas, no es necesario aquí. Como solo te importa el número de pares, tampoco es necesario registrar qué son esos pares. Puede simplemente recorrer toda la lista.

Si está utilizando GCC o clang, lo siguiente funcionará. En MSVC, puede usar __popcnt64() lugar.

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

Si realmente quiere evitar goto, puede llamar a la función recursivamente, donde estaría la línea goto [label], pasando cualquier variable cuyo estado desee guardar como parámetros. Sin embargo, recomendaría seguir con el goto.


Su implementación no está funcionando ya que cuenta tres de una clase como un par, cuatro de una clase como dos.

Aquí hay una implementación que sugeriría:

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 en coliru )

Se puede generalizar para contar no solo pares sino también n de un tipo ajustando el 2 .


goto es solo un problema. Otro gran problema es que su método es ineficiente.

Tu método

Su método actual básicamente mira la primera carta, itera sobre el resto y busca el mismo valor. Luego vuelve a la segunda carta y la compara con el resto. Esto es O(n**2) .

Clasificación

¿Cómo contarías los pares en la vida real? Probablemente clasifique las cartas por valor y busque pares. Si ordena de manera eficiente, sería O(n*log n) .

Distribuido

El método más rápido sería preparar 13 ranuras en una mesa y distribuir las tarjetas de acuerdo con su valor nominal. Después de distribuir cada carta, puedes contar las cartas en cada casilla y ver si alguna ranura contiene al menos 2 cartas. Es O(n) y también detectaría tres de una clase o cuatro de una clase.

Claro, no hay mucha diferencia entre n**2 y n cuando n es 5 . Como beneficio adicional, el último método sería conciso, fácil de escribir y libre de goto .


Sí, debes evitar usar goto aquí.

Es un uso innecesario de goto específicamente porque el algoritmo no lo necesita. Por otro lado, tiendo a no utilizar goto , pero no me opongo firmemente como a muchos. goto es una gran herramienta para romper bucles anidados o para salir de una función limpiamente cuando una interfaz no es compatible con RAII.

Hay algunas ineficiencias con su enfoque actual:

  • No hay ninguna razón para volver a buscar en la lista desde el principio cuando encuentre un par coincidente. Ya ha buscado todas las combinaciones anteriores. La eliminación de tarjetas no cambia el orden relativo de las tarjetas no eliminadas y, además, no le proporciona más pares.
  • No es necesario quitar elementos del centro de la hand . Para este problema, eliminar desde el medio de un std::vector presumiblemente representa una mano de 5 cartas no es un problema. Sin embargo, si el número de cartas es grande, esto puede ser ineficiente. En problemas como este, debería preguntarse, ¿importa el orden de los elementos? La respuesta es no, no importa. Podemos mezclar cualquier carta que no haya sido emparejada y aún así obtener la misma respuesta.

Aquí hay una versión modificada de tu código:

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

Puede retocar el enfoque anterior para usar iteradores si lo desea. También puede utilizar un std::vector referencia constante y usar std::reference_wrapper para volver a ordenar el contenedor.

Para un mejor algoritmo general construya una tabla de frecuencias de cada valor nominal y su conteo correspondiente.


#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