Простой способ проверить, находится ли объект в списке?
Я пишу алгоритм поиска в C++, и одна из вещей, которые я должен сделать, имеют некоторых, если операторы, которые проверяют ячейки выше, ниже, оставленный, и право на.
Каждый раз, когда ячейка, как находят, открыта и добавлена к стеку, я хочу добавленный к списку ячеек, уже проверенных.
Я хочу смочь сказать в если оператор if(thisCell is not in checkedCells).
Какие-либо простые идеи?
Спасибо!
2 ответа
Для этого лучше использовать контейнер 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);
}