Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Easy way to check if item is in list?

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?

like image 929
Befall Avatar asked Apr 20 '10 04:04

Befall


People also ask

How do you check if item is present in list or not?

We can use the in-built python List method, count(), to check if the passed element exists in the List. If the passed element exists in the List, the count() method will show the number of times it occurs in the entire list. If it is a non-zero positive number, it means an element exists in the List.

How do you check if a string is in the list?

Python Find String in List using count() We can also use count() function to get the number of occurrences of a string in the list. If its output is 0, then it means that string is not present in the list. l1 = ['A', 'B', 'C', 'D', 'A', 'A', 'C'] s = 'A' count = l1.


2 Answers

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.

like image 181
Eli Bendersky Avatar answered Sep 20 '22 03:09

Eli Bendersky


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);
}
like image 34
Vijay Mathew Avatar answered Sep 19 '22 03:09

Vijay Mathew