我正在用C++编写搜索算法,其中需要执行一些if语句来检查上下左右的单元格。
每次发现一个空单元格并将其添加到堆栈中时,我希望它被添加到已检查单元格列表中。
我想在if语句中使用这样的表达式if(thisCell不在checkedCells中)
。
有什么简单的想法吗?
我正在用C++编写搜索算法,其中需要执行一些if语句来检查上下左右的单元格。
每次发现一个空单元格并将其添加到堆栈中时,我希望它被添加到已检查单元格列表中。
我想在if语句中使用这样的表达式if(thisCell不在checkedCells中)
。
有什么简单的想法吗?
std::set
容器,因为它可以比列表更快地搜索项目。然后你可以写:std::set<itemType> myset;
...
if (myset.find(item) != myset.end()) {
// item is found
}
更详细的示例可以通过Google找到。例如,在这里。
如果项目数量在数百个左右,您可以使用简单的顺序搜索。这个算法已经内置在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);
}