STL set with custom data type

Discussion in 'C++' started by cata.1972@hotmail.com, Feb 24, 2009.

  1. Guest

    Hi,

    I have structure representing a 2 dimesional point:

    struct K2dCoords
    {
    K2dCoords(void):m_x(0), m_y(0){};
    K2dCoords(double x, double y):m_x(x), m_y(y){};
    K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
    double getX() const {return m_x;}
    double getY() const {return m_y;}
    double m_x;
    double m_y;
    };

    I want to store pointers to instances of this in a STL set.
    So I define the sorting criterion, such that two points are considered
    equal
    if the distance between them is negligeble (less than a tolerance):

    struct eq
    {
    bool operator() (const K2dCoords* p1, const K2dCoords* p2) const
    {
    const double tol = 0.25 / 1E3;
    return sqrt((p1->getX() - p2->getX()) * (p1->getX() - p2->getX
    ()) + (p1->getY() - p2->getY()) * (p1->getY() - p2->getY())) > tol;
    }
    };

    The problem is that after I've inserted some point in my set, I cannot
    find them:

    // some initialisation data
    const double inc = 0.25;
    const double deckLength = 1.0;
    const double deckWidth = 0.48;
    double x = 0;
    double y = 0;
    const double PI = 3.1415926;
    std::set<K2dCoords*, eq> stlMap;

    // create some points and add them to my set
    while (x <= deckLength)
    {
    while (y <= deckWidth)
    {
    const double xSp = x * cos(30.0 * PI / 180.0) - y * sin
    (30.0 * PI / 180.0);
    const double ySp = x * sin(30.0 * PI / 180.0) + y * cos
    (30.0 * PI / 180.0);
    stlMap.insert(new K2dCoords(xSp, ySp));
    y += inc;
    }
    x += inc;
    y = 0;
    }

    // check if I've got them; the test point are created in the same
    way as they were created for insertion
    x = 0;
    y = 0;
    while (x <= deckLength)
    {
    while (y <= deckWidth)
    {
    const double xSp = x * cos(30.0 * PI / 180.0) - y * sin
    (30.0 * PI / 180.0);
    const double ySp = x * sin(30.0 * PI / 180.0) + y * cos
    (30.0 * PI / 180.0);
    std::set<K2dCoords*, eq>::iterator it = stlMap.find(new
    K2dCoords(xSp, ySp));
    if (it == stlMap.end())
    {
    ASSERT(FALSE); // suerly this should not assert, but
    it does (when x=0.25 and y=0)!!!
    }
    y += inc;
    }
    x += inc;
    y = 0;
    }

    What am I doing wrong? Thanks.
    , Feb 24, 2009
    #1
    1. Advertising

  2. Guest

    On Feb 24, 7:16 am, wrote:
    > Hi,
    >
    > I have structure representing a 2 dimesional point:


    > I want to store pointers to instances of this in a STL set.
    > So I define the sorting criterion, such that two points are considered
    > equal
    > if the distance between them is negligeble (less than a tolerance):
    >
    > struct eq
    > {
    >     bool operator() (const K2dCoords* p1, const K2dCoords* p2) const
    >     {
    >         const double tol = 0.25 / 1E3;
    >         return sqrt((p1->getX() - p2->getX()) * (p1->getX() - p2->getX
    > ()) + (p1->getY() - p2->getY()) * (p1->getY() - p2->getY())) > tol;
    >     }


    > What am I doing wrong? Thanks.


    Your sorting criteria doesn't allow for proper sorting. It just
    returns if two elements are near each other. std::set relies on a
    strict weak ordering. Your function therefore should never return A
    < B is true as well as B < A is also true.
    For elements that you want to consider equal, operator(A,B) and
    operator(B,A) should both return false. For elements not equal,
    operator(A,B) _must_ return the logically opposite value of operator
    (B,A).

    HTH,
    Joe
    , Feb 24, 2009
    #2
    1. Advertising

  3. On Feb 24, 1:16 pm, wrote:
    > Hi,
    >
    > I have structure representing a 2 dimesional point:
    >
    > struct K2dCoords
    > {
    >     K2dCoords(void):m_x(0), m_y(0){};
    >     K2dCoords(double x, double y):m_x(x), m_y(y){};
    >     K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
    >     double getX() const {return m_x;}
    >     double getY() const {return m_y;}
    >     double m_x;
    >     double m_y;
    >
    > };
    >
    > I want to store pointers to instances of this in a STL set.
    > So I define the sorting criterion, such that two points are considered
    > equal
    > if the distance between them is negligeble (less than a tolerance):
    >

    <snip>
    > What am I doing wrong? Thanks.


    You are using a sorting criterion that std::set<> can't handle.
    std::set<> does not care about the equality of two points, it wants to
    know if P1 comes before P2 or not. Only if neither P1 comes before P2
    nor P2 comes before P1, then P1 and P2 are considered to be equal.

    Another problem is your use of tolerances. std::set<> also requires
    that the following equation holds:
    if P1 == P2 && P2 == P3 then P1 == P3
    When using tolerances, there is a big chance that this equation does
    not hold for all points in the set, and that is bad.

    Bart v Ingen Schenau
    Bart van Ingen Schenau, Feb 24, 2009
    #3
  4. SG Guest

    wrote:
    > Hi,
    >
    > I have structure representing a 2 dimesional point:
    >
    > struct K2dCoords
    > {
    >     K2dCoords(void):m_x(0), m_y(0){};
    >     K2dCoords(double x, double y):m_x(x), m_y(y){};
    >     K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
    >     double getX() const {return m_x;}
    >     double getY() const {return m_y;}
    >     double m_x;
    >     double m_y;
    > };
    >
    > I want to store pointers to instances of this in a STL set.
    > So I define the sorting criterion, such that two points are considered
    > equal
    > if the distance between them is negligeble (less than a tolerance):
    >
    > struct eq


    As others have pointed out std::set needs a "strict weak order"-
    predicate.

    Also, why do you go through the trouble of using pointers? Is there a
    need for pointers here?

    > stlMap.insert(new K2dCoords(xSp, ySp));


    You know that you could also write

    set<K2dCoords> myset;
    myset.insert(K2dCoords(3.14,23.0));

    Right?


    The problem you want to solve is to detect whether a new point is
    "close enough" to another point that's already in the data structure
    ("set") and if not, to add the point to the data structure, right?
    This usually calls for something like a kd-tree:

    http://en.wikipedia.org/wiki/Kd-tree
    http://en.wikipedia.org/wiki/Nearest_neighbour_search

    The alternative is to use a lexical ordering and to compare the new
    point with every other point of the set's relevant subrange. Of
    course a NNS won't be as fast as with a kd-tree but for 2D it's
    probably still ok to do it that way (assuming the number of points is
    not too big). You could write a functions like this:

    /// any simple p-metric for p=1...infinity
    double distance(const K2dCoords& a, const K2dCoords& b);

    /// checks whether the set contains a point q with
    /// distance(q,pnew) < epsilon
    bool has_neighbour(const set<K2dCoords>& points,
    const K2dCoords& pnew, double epsilon)
    {
    typedef set<K2dCoords>::const_iterator iter_t;
    const K2dCoords corner1 (pnew.getX()-epsilon, pnew.getY()-
    epsilon);
    const K2dCoords corner2 (pnew.getX()+epsilon, pnew.getY()
    +epsilon);
    iter_t beg = points.lower_bound(corner1);
    iter_t end = points.upper_bound(corner2);
    while (beg!=end) {
    if (distance(pnew,*beg) < epsilon) return true;
    ++beg;
    }
    return false;
    }

    This should work for a lexical ordering and an epsilon>0. I didn't
    test it, though. You get the idea.


    Cheers!
    SG
    SG, Feb 24, 2009
    #4
  5. Guest

    On 24 Feb, 14:31, SG <> wrote:
    > wrote:
    > > Hi,

    >
    > > I have structure representing a 2 dimesional point:

    >
    > > struct K2dCoords
    > > {
    > >     K2dCoords(void):m_x(0), m_y(0){};
    > >     K2dCoords(double x, double y):m_x(x), m_y(y){};
    > >     K2dCoords(const K2dCoords& rhs): m_x(rhs.m_x), m_y(rhs.m_y){};
    > >     double getX() const {return m_x;}
    > >     double getY() const {return m_y;}
    > >     double m_x;
    > >     double m_y;
    > > };

    >
    > > I want to store pointers to instances of this in a STL set.
    > > So I define the sorting criterion, such that two points are considered
    > > equal
    > > if the distance between them is negligeble (less than a tolerance):

    >
    > > struct eq

    >
    > As others have pointed out std::set needs a "strict weak order"-
    > predicate.
    >
    > Also, why do you go through the trouble of using pointers?  Is there a
    > need for pointers here?
    >
    > > stlMap.insert(new K2dCoords(xSp, ySp));

    >
    > You know that you could also write
    >
    >    set<K2dCoords> myset;
    >    myset.insert(K2dCoords(3.14,23.0));
    >
    > Right?
    >
    > The problem you want to solve is to detect whether a new point is
    > "close enough" to another point that's already in the data structure
    > ("set") and if not, to add the point to the data structure, right?
    > This usually calls for something like a kd-tree:
    >
    >  http://en.wikipedia.org/wiki/Kd-tree
    >  http://en.wikipedia.org/wiki/Nearest_neighbour_search
    >
    > The alternative is to use a lexical ordering and to compare the new
    > point with every other point of the set's relevant subrange.  Of
    > course a NNS won't be as fast as with a kd-tree but for 2D it's
    > probably still ok to do it that way (assuming the number of points is
    > not too big).  You could write a functions like this:
    >
    >   /// any simple p-metric for p=1...infinity
    >   double distance(const K2dCoords& a, const K2dCoords& b);
    >
    >   /// checks whether the set contains a point q with
    >   /// distance(q,pnew) < epsilon
    >   bool has_neighbour(const set<K2dCoords>& points,
    >     const K2dCoords& pnew, double epsilon)
    >   {
    >     typedef set<K2dCoords>::const_iterator iter_t;
    >     const K2dCoords corner1 (pnew.getX()-epsilon, pnew.getY()-
    > epsilon);
    >     const K2dCoords corner2 (pnew.getX()+epsilon, pnew.getY()
    > +epsilon);
    >     iter_t beg = points.lower_bound(corner1);
    >     iter_t end = points.upper_bound(corner2);
    >     while (beg!=end) {
    >       if (distance(pnew,*beg) < epsilon) return true;
    >       ++beg;
    >     }
    >     return false;
    >   }
    >
    > This should work for a lexical ordering and an epsilon>0.  I didn't
    > test it, though.  You get the idea.
    >
    > Cheers!
    > SG- Hide quoted text -
    >
    > - Show quoted text -


    Thank you all.
    That's right, I want a data structure able to return me a point that's
    close enough to a given point. I see now why the STL set won't work
    and this problem is a lot more complicated than I initially thought.
    There's no chance of getting one of this data structure into STL or
    Boost in future, is there?
    , Feb 24, 2009
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. luna
    Replies:
    1
    Views:
    6,817
  2. Eric
    Replies:
    13
    Views:
    702
    verec
    Jul 13, 2005
  3. Replies:
    1
    Views:
    685
    mlimber
    Jun 2, 2006
  4. Replies:
    3
    Views:
    405
    n2xssvv g02gfr12930
    Jul 4, 2006
  5. liam_herron
    Replies:
    1
    Views:
    333
    Jim Langston
    Apr 8, 2008
Loading...

Share This Page