Custom key_comp with a class that takes an argument for a c++ set

Question

I've been trying to create a set of Vector3ds (from the Eigen Library). The set, furthermore, will take a key_comp from a custom class which happens to take an argument too. So the following is my code

#include <set>
#include <Eigen/Core>

using namespace std;
using namespace Eigen;

class Vector3dNormCompareClass {
public:
        Vector3dNormCompareClass(const double prec) {
                _prec = prec;
        }
        bool operator ()(const Vector3d lhs, const Vector3d rhs) const;
private:
        double _prec;
};

bool Vector3dNormCompareClass::operator ()(const Vector3d lhs,
                const Vector3d rhs) const {    
        if (lhs.norm() < rhs.norm())
                return true;

        for (int i = 0; i < 3; ++i) {
                if (abs(lhs(i) - rhs(i)) > _prec)
                        return lhs(i) < rhs(i);
        }
        return false;
}

class Tan {    
    set<Vector3d,Vector3dNormCompareClass> _transList;
    public:
    void setTransList(double foo);    
};


void Tan::setTransList(double foo) {
    Vector3dNormCompareClass comp(foo);
    _transList(comp);    
}

Here, _transList is the set I want to construct when the class Tan is declared and Vector3dNormCompareClass is the class for the key_comp that takes an argument for the precision of the comparison (since we're comparing the vectors of doubles). Furthermore, in my case I want to be able to reset the precision of the key_comp, i.e. Vector3dNormCompareClass, but with the current form my code, unfortunately, doesn't compile. Could anyone help me how to define the list such that it can take the custom key_comp with its argument (i.e. double prec)?

UPDATE Because some of you apparently are more concerned about the mathematical validity of my key_comp, I have added some code in it: if (lhs.norm() < rhs.norm()) return true; to fulfill the condition defined here, I quote:

The set object uses this expression to determine both the order the elements follow in the container and whether two element keys are equivalent (by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)). No two elements in a set container can be equivalent.

So, by checking (a<b) & (b>a), I believe my key_comp will fulfill the condition to determine equivalent keys. That said, the double prec here is now used to order the keys and I want to make it "flexible", meaning able to reset, perhaps, every time after I clear _transList, i.e. _transList.clear(). So my problem still exists, namely the code doesn't compile with the current form and I would appreciate it if someone could help me with this concern!

What's wrong with using a lambda expression and capture variables instead? — πάντα ῥεῖ, Dec 12 '18 at 14:23
When do you want to _reset the precision of `key_comp`_? After `_transList` has been constructed? That is not allowed I'm afraid. Imagine you would increase `_prec`. Then, two set elements that were originally different might become equal. — Daniel Langr, Dec 12 '18 at 14:36
@DanielLangr How about after I clear `_transList` up; i.e. `_transList.clear()`, is it possible to reset `_prec`? — rnels12, Dec 12 '18 at 14:49
@rnels12 It's even not possible to use floating-point comparator based on considering close number to be equal. See, e.g, https://stackoverflow.com/q/6684573/580083 for discussion. — Daniel Langr, Dec 12 '18 at 15:08
IMO you need to write your own container which will be some kind of [B-tree](https://en.wikipedia.org/wiki/B-tree). — Marek R, Dec 12 '18 at 15:10
Your modified comparator is wrong again. Consider `a=[-0.5,0,0]` and `b=[1,0,0]`. Then `a.norm()` is 0.5 and `b.norm()` is 1. Therefore `comp(a,b)` is `true`, but `comp(b,a)` is `true` as well, since `a(0) — Daniel Langr, Dec 14 '18 at 10:24
@DanielLangr with your example: if `comp(a,b)` is true, why is `comp(b,a)` true as well? With my code `comp(b,a)` is indeed `false`. After checking the norm, which is passed since `b.norm()` NOT < `a.norm()`, in the element-wise checking, nothing will yield `true` for `b(i) < a(i)` (btw it should be `b(i) < a(i)`) so it comes to the last line line which returns `false`. Did you do the analysis correctly? — rnels12, Dec 14 '18 at 12:50
You're right, my bad. I switched the signs. It should have been `a=[0.5,0,0]` and `b=[-1,0,0]`. `comp(a,b)==true` (the norms are the same independently of signs), but `comp(b,a)==true` as well, since `b(0)==-1<0.5==a(0)`. — Daniel Langr, Dec 14 '18 at 13:43
Also note that with your new comparator, any two vectors will be considered `equal` only if they have the very same norm. Therefore vectors `[1,0,0]` and `[1+_prec/2.0,0,0]` will not be considered equal (at least one comparison will be true, and equal will be consequently false), even if they are "closer" to each other than `_prec`. — Daniel Langr, Dec 14 '18 at 14:16

chtz · Accepted Answer · 2018-12-12T15:31:46.970

2

You can't just reset the comparator, since this would (likely) also change the internal order. You can however reset the set using a new comparator (and optionally insert the current values):

void Tan::setTransList(double foo) {
    Vector3dNormCompareClass comp(foo);
    set<Vector3d,Vector3dNormCompareClass> tmp(
        _transList.begin(), _transList.end(), // remove this line if you don't want to copy old entries
        comp); 
    _transList.swap(tmp);    
}

Edit: As Daniel pointed out, your comparator does not fulfill the necessary criteria for a set (namely being transitive), i.e., you will likely get unexpected results (depending on the order you insert values).

edited Dec 12 '18 at 15:31

answered Dec 12 '18 at 14:45

chtz

17,329
4
26
56

I have added some codes to fulfill the condition defined in: http://www.cplusplus.com/reference/set/set/, namely: keys are equivalent if !comp(a,b) && !comp(b,a). – rnels12 Dec 12 '18 at 15:39
Your solution seems to work; the code compiles. Now I'm gonna see if it works with my full code. I upvote your answer but will also wait a bit longer to accept this as the answer, in case some can come up with with a bit more elegant solution. Thanks anyway! :) – rnels12 Dec 12 '18 at 20:35

Daniel Langr · Answer 2 · 2018-12-12T14:54:24.097

1

I believe you cannot define a comparator for associative containers this way in case of floating-point keys. The C++ Standard requires that equality derived from comparator is transitive, such as: equiv(a, b) && equiv(b, c) implies equiv(a, c), where equiv(a, b) is defined as !comp(a, b) && !comp(b, a).

With floating-point keys and comparing with respect to some precision, you can get equiv(a, b) and equiv(b, c) being true (both differ of less than the precision) but equiv(a, c) being false (sum of the differences is higher than the precision).

Example for scalar keys

Consider _prec being 0.1 (it's high for exemplary purposes, you can make the same analysis for any value). Then comp(a, b) being defined as abs(a, b) < 0.1 will imply that equiv(1.10, 1.19) is true as well as equiv(1.19, 1.28), but equiv(1.10, 1.28) will be false.

edited Dec 12 '18 at 14:54

answered Dec 12 '18 at 14:48

Daniel Langr

22,196
3
50
93

That is true, although this is not the reason for the code not compiling. – chtz Dec 12 '18 at 15:29
I agree with @chtz, my main concern is about the code to compile. Also, according to this page: http://www.cplusplus.com/reference/set/set/, `a and b are equivalent if !comp(a,b) && !comp(b,a)).` How about I first check (a – rnels12 Dec 12 '18 at 15:36
@rnels12 If you read further, you'll see that the comparison also needs to fulfill "strict weak ordering" -- look up what that means, if you don't want to get surprised later. – chtz Dec 16 '18 at 11:21

Custom key_comp with a class that takes an argument for a c++ set

2 Answers2