Cách dễ dàng để kiểm tra xem mục có nằm trong danh sách không?

Question

Tôi đang viết một thuật toán tìm kiếm trong C++ và một trong những điều tôi cần làm là có một vài câu lệnh nếu kiểm tra các ô ở trên, bên dưới, bên trái và bên phải.

Mỗi khi một ô được tìm thấy được mở và thêm vào ngăn xếp, tôi muốn nó được thêm vào danh sách các ô đã được chọn.

Tôi muốn có thể nói trong câu lệnh if if(thisCell is not in checkedCells).

Bất kỳ ý tưởng đơn giản nào?

Cảm ơn!

Answer 1

Vì mục đích này, tốt hơn nên sử dụng vùng chứa std::set, vì nó cung cấp cho bạn khả năng tìm kiếm các mục nhanh hơn danh sách. Sau đó, bạn có thể viết:

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

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

Ví dụ lớn hơn có thể được tìm thấy bằng cách googling. Ví dụ: here.

Answer 2

Nếu số mục nằm trong hàng trăm mục, bạn có thể sử dụng tìm kiếm tuần tự đơn giản. Thuật toán này được tích hợp vào C++ như find() chức năng:

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

Hãy chắc chắn rằng Cell đã operator< ghi đè.

Nếu danh sách là rất lớn, bạn có thể muốn sử dụng tìm kiếm nhị phân, mà cũng đi kèm với 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); 
}