How to write a Comparator when the order of elements does not matter
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: How to write a Comparator when the order of elements does not matter

  1. #1
    Join Date
    Dec 2010
    Posts
    97

    How to write a Comparator when the order of elements does not matter

    Code:
    bool Edge::operator<(const Edge& e) const
    {
    	return std::tie(this->v0, this->v1) < std::tie(e.v0, e.v1);
    }
    also when this->v0 == e.v1 && this->v1 == e.v0
    How do I rewrite this comparator?
    Thanks
    Jack

  2. #2
    Join Date
    Feb 2017
    Posts
    165

    Re: How to write a Comparator when the order of elements does not matter

    Well I don't quite understand what you mean by "the order doesn't matter". Maybe you mean that both elements of this should be smaller than both elements of e?

    In that case you can do this,
    Code:
    return std::max(this->v0, this->v1) < std::min(e.v0, e.v1);

  3. #3
    Join Date
    Dec 2010
    Posts
    97

    Re: How to write a Comparator when the order of elements does not matter

    Hello,

    I actually meant that
    when I add the elements
    in case 1: v0==v1 and v1==v0
    and case 2: v0==v0 and v1==v1
    , the items are deemed to be the same, and they won't add to the container as two separate items....
    Thanks
    Jack

  4. #4
    Join Date
    Feb 2017
    Posts
    165

    Re: How to write a Comparator when the order of elements does not matter

    Quote Originally Posted by luckiejacky View Post
    in case 1: v0==v1 and v1==v0
    and case 2: v0==v0 and v1==v1
    , the items are deemed to be the same
    That can easily be translated into code. This and e are equal when:
    Code:
    return ((this->v0==e.v1) && (this->v1==e.v0)) || ((this->v0==e.v0) && ((this->v1==e.v1));
    An example. Say this holds (1,2) in any order and e also holds (1,2) in any order and they are to be considered equal regardless of order. Then you have these four cases of equality,

    1: (1,2) (1,2)
    2: (1,2) (2,1)
    3: (2,1) (1,2)
    4: (2,1) (2,1)

    The equality in cases 1 and 4 can be detected with a "straight" component-wise comparison and cases 2 and 3 with a "crosswise" comparison. This is what the code snippet I supplied does.

    Note that you can reduce the four cases to 1 by keeping the components of Edge sorted. Ensuring that v0 <= v1 already in the Edge constructor is likely to save you lots of trouble later on.
    Last edited by wolle; March 28th, 2017 at 05:42 AM.

  5. #5
    Join Date
    Dec 2010
    Posts
    97

    Re: How to write a Comparator when the order of elements does not matter

    Thanks for helping....
    I just received a crash with this code.... (Comparator changed)
    And sometimes, when the 3 edges are different in the first place, I just got one of them actually added into the container after all.
    Code:
    std::vector<Face>& faces = GetFaces();
    	const std::vector<D3DXVECTOR3>& verts = GetVertices();
    
    	std::set<Edge> newEdges;
    
    	for (int i = 0; i < faces.size(); i++)
    	{
    		Edge newEdge0, newEdge1, newEdge2;
    		newEdge0.v0 = faces[i].v0;
    		newEdge0.v1 = faces[i].v1;
    		newEdge1.v0 = faces[i].v1;
    		newEdge1.v1 = faces[i].v2;
    		newEdge2.v0 = faces[i].v2;
    		newEdge2.v1 = faces[i].v0;
    
    		D3DXVECTOR3 v0pos = verts[faces[i].v0];
    		D3DXVECTOR3 v1pos = verts[faces[i].v1];
    		D3DXVECTOR3 v2pos = verts[faces[i].v2];
    
    		newEdge0.v0_pos = v0pos;
    		newEdge0.v1_pos = v1pos;
    		newEdge0.faceId = faces[i].id;
    
    		newEdge1.v0_pos = v1pos;
    		newEdge1.v1_pos = v2pos;
    		newEdge1.faceId = faces[i].id;
    
    		newEdge2.v0_pos = v2pos;
    		newEdge2.v1_pos = v0pos;
    		newEdge2.faceId = faces[i].id;
    
    		newEdges.insert(newEdge0);
    		newEdges.insert(newEdge1);
    		newEdges.insert(newEdge2);
    
    		faces[i].m_edges.push_back(newEdge0);
    		faces[i].m_edges.push_back(newEdge1);
    		faces[i].m_edges.push_back(newEdge2);
    		
    
    	}
    Could you please shed some lights on this?
    Thanks
    Jack
    Last edited by luckiejacky; March 28th, 2017 at 10:21 PM.

  6. #6
    Join Date
    Feb 2017
    Posts
    165

    Re: How to write a Comparator when the order of elements does not matter

    Quote Originally Posted by luckiejacky View Post
    Could you please shed some lights on this?
    You want to store edges in an std::set and for that you need to define a < (less) relation between the edges. The set will keep the edges sorted according to the < relation but it will also use it to establish equality to prevent edges from being inserted more than once. Say we have two edges e1 and e2. Equality is established like so: e1==e2 when !(e1<e2) && !(e2<e1).

    The edges e1 and e2 are line segments, each with endpoints v0 and v1. First we assume v0 <= v1. We look at the left endpoints and state that e1<e2 when e1.v0<e2.v0. But if we stop here, due to the way equality is established, we can get a false equality when e1.v0==e2.v0. To resolve this we also involve the right endpoints and state that in the case that e1.v0==e2.v0 then e1<e2 when e1.v1<e2.v1.

    This essentially means we have used both the position and length of line segments to establish the < relation. Position as primary criterion and length as secondary. In code,
    Code:
    boolean less(Edge e1, Edge e2) {
        return (e1.v0<e2.v0) || ((e1.v0==e2.v0) && (e1.v1<e2.v1));
    }
    As I've said, it pays off to to keep v0 and v1 presorted according to v0 <= v1 but if you for some reason cannot have that there is no way around a sort (in one way or another, explicit or implicit). This is one way,
    Code:
    boolean less(Edge s1, Edge s2) {
        Edge e1,e2;
        e1.v0 = std::min(s1.v0, s1.v1);
        e1.v1 = std::max(s1.v0, s1.v1);
        e2.v0 = std::min(s2.v0, s2.v1);
        e2.v1 = std::max(s2.v0, s2.v1);
        return (e1.v0<e2.v0) || ((e1.v0==e2.v0) && (e1.v1<e2.v1));
    }
    It's not tested but it should work, at least in principle
    Last edited by wolle; March 29th, 2017 at 08:11 AM.

  7. #7
    Join Date
    Dec 2010
    Posts
    97

    Re: How to write a Comparator when the order of elements does not matter

    Good. It works. Thanks, I've learnt something.... Really thanks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)