CODEWITHSUNDEEP
c++structset
Matthew Vanlandingham
Matthew Vanlandingham

Reputation: 646

Finding an element in a set that uses a struct C++

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

Answers (2)

Quimby
Quimby

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

Alexander
Alexander

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

Related Questions