简单的方法来检查项目是否在列表中？

Question

我正在用C++编写一个搜索算法，我需要做的事情之一是有几条if语句来检查上面，下面，左边和右边的单元格。

每次发现一个单元格打开并添加到堆栈中时，我希望它将其添加到已检查过的单元格列表中。我想在if语句中说if(thisCell is not in checkedCells)。

任何简单的想法？

谢谢！

Answer 1

为此，最好使用std::set容器，因为它使您能够以比列表更快的速度搜索项目。那么你可以写：

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

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

一个更大的例子可以通过谷歌搜索。例如，here。

Answer 2

如果项目的数量是几百，您可以使用简单的顺序搜索。该算法是内置到C++作为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); 
} 

确保Cell已operator<覆盖。

如果该列表是非常大的，你可能需要使用二进制搜索，其中还带有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); 
}