¿Manera fácil de verificar si el artículo está en la lista?

Question

Estoy escribiendo un algoritmo de búsqueda en C++, y una de las cosas que debo hacer es tener algunas declaraciones if que verifiquen las casillas arriba, abajo, izquierda y derecha de.

Cada vez que se encuentra que una celda está abierta y se agrega a la pila, quiero que se agregue a una lista de las celdas ya marcadas.

Quiero poder decir en la declaración if if(thisCell is not in checkedCells).

¿Alguna idea simple?

Gracias!

Answer 1

Para este propósito, es mejor usar el contenedor std::set, porque le proporciona la capacidad de buscar elementos más rápido que una lista. Luego puede escribir:

std::set<itemType> myset; 
... 

if (myset.find(item) != myset.end()) { 
    // item is found 
} 

Puede encontrar un ejemplo más grande en Google. Por ejemplo, here.

Answer 2

Si la cantidad de elementos es de cientos, puede usar la búsqueda secuencial simple. Este algoritmo está incorporado en C++ como la función find():

#include <algorithm> // for find() 

typedef std::vector<Cell> CellList; 
CellList checked_cells; 
// ..... 

Cell cellToSearch; 
if (is_in_checked_cells (cellToSearch, cells)) 
{ 
    // ..... 
} 

// Makes a sequential search using find(). 
static bool 
is_in_checked_cells (const Cell &cell, const CellList &cells) 
{ 
    CellList::const_iterator end = cells.end(); 
    CellList::const_iterator item = std::find (cells.begin(), end, cell); 
    return (item != end); 
} 

Asegúrese Cell ha anulado operator<.

Si la lista es muy grande, es posible que desee utilizar la búsqueda binaria, que también viene incluido con C++:

#include <algorithm> // for sort() and binary_search() 

CellList checked_cells; 
// Make sure the cells are sorted. 
checked_cells.sort (checked_cells.begin(), checked_cells.end()); 

Cell cellToSearch; 
if (is_in_checked_cells (cellToSearch, cells)) 
{ 
    // ..... 
} 

// Searches using binary_search(). 
static bool 
is_in_checked_cells (const Cell &cell, const CellList &cells) 
{ 
    return std::binary_search (cells.begin(), cells.end(), cell); 
}