Easy way to check if item is in list?

Question

I'm writing a search algorithm in C++, and one of the things I need to do is have a few if statements that check cells above, below, left of, and right of.

Each time a cell is found to be open and added to the stack, I want it added to a list of cells already checked.

I want to be able to say in the if statement if(thisCell is not in checkedCells).

Any simple ideas?

Solution 1

For this purpose it's better to use the std::set container, because it provides you with the ability to search for items faster than a list. Then you can write:

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

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

A larger example can be found by googling. For example, here.

Solution 2

If the number of items are in the hundreds, you can use simple, sequential search. This algorithm is built-into C++ as the find() function:

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

Make sure Cell has operator< overridden.

If the list is very large, you may want to use binary search, which also comes bundled with 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);
}