Простой способ проверить, есть ли товар в списке?

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
}

Более крупный пример можно найти в Google. Например, здесь .

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