Reputation: 646
I'm creating the 8-puzzle in C++. I take the puzzle based on input, then create a set containing the puzzle. The set uses a struct to hold the x,y coordinates along with the id. This is my struct:
struct tile {
int id;
int xCord;
int yCord;
tile(int a, int b, int c) :
id(a),
xCord(b),
yCord(c) {}
bool operator<(const tile& Rhs) const {
if (xCord < Rhs.xCord)
return true;
else if (xCord > Rhs.xCord)
return false;
else if (xCord == Rhs.xCord) {
if (yCord < Rhs.yCord)
return true;
else if (yCord < Rhs.yCord)
return false;
else
return false;
}
}
void print() const {
cout << "Node - id=" << id << " Coordinates=(" << xCord << "," << yCord << ")" << endl;
}
};
At this point, I need to shuffle the puzzle, which involves finding the the empty tile, which has an id of 0
. I can't figure out how to use the find
function with how I have setup my set.
So far I have used this, but there is a syntax error:
set<tile>::iterator it = puzzleSet.find(0);
Here is my set declaration:
set<tile> puzzleSet;
Could anybody help me on this? Thanks in advance.
Upvotes: 0
Views: 892
Reputation: 19223
The syntax error is because the set<tile>::find
expects another tile
, not an int
. C++14 added new overloads that allow searching by another type, see ref. That source also says that to enable them, set
's comparator must be transparent. Default comparator is std::less<tile>
that to my knowledge is not explicitly said to be transparent. So the solution is to define custom comparator:
struct comp
{
public:
using is_transparent = void;//Can be anything, just needs to be defined.
constexpr bool operator()(const tile &lhs, const tile &rhs) const
{
return lhs < rhs;//You should reimplement to create proper ordering.
}
constexpr bool operator()(const tile &lhs, int ID) const
{
return lhs.ID < ID;//You should reimplement to create proper ordering.
}
constexpr bool operator()(int ID, const tile &rhs) const
{
return ID < rhs.ID;//You should reimplement to create proper ordering.
}
};
#include <set>
int main() {
std::string buffer = "a s d f ";
std::cout << "Before " << buffer << std::endl;
std::set<tile, comp> set;
set.find(0);//Should compile and find the tile with zero ID
}
Note the comparator must create the same weak-ordering for all overloads to work correctly. Your implementation of operator<
does not, because as @Alexander pointed out in their answer, your tiles are not sorted by IDs.
EDIT: So don't use the comp as it is now, you should change the implementation to create the ordering correctly.
Upvotes: 1
Reputation: 758
your set is ordered by coordinates so your set cannot help you to find by id.
possible solution:
std::find_if(puzzleSet.begin(), puzzleSet.end(), [id](puzzleSet const & item){ return item.id == id; });
if the linear search is too expensive. you can add another set that is ordered by id. or try to order your set by id and coordinats (if applicable)
a small typo in your code:
if (yCord < Rhs.yCord)
return true;
else if (yCord < Rhs.yCord) // here should be >
return false;
Upvotes: 1