std::set foreign key using custom comaprator

user_1912594 0
Viewed 87
std::vector<int> v = {1,1,1,1,2,2};
auto cmp = [&v](size_t a, size_t b){return v[a] < v[b];};
std::multiset<int, decltype(cmp)> s(cmp);

Vector v's contents is just an example. It could be any array of ints, but can have repeating values.

I'm using a multiset because I want to be able to traverse over all the values by-order, and because values in v are not unique.

Also, I'd like to be able to know if a certain value is in it or not. For example after inserting:

s.insert(1);
s.insert(1);
s.insert(2);
s.insert(2);

I'd expect for the value of present in this test to be false:

auto iter = s.find(3);
bool present = iter != s.end();

However, it is true, I guess it's due to the internal implementation of set (AVL/RB-tree?) and how it searches for values inside using the comparator. Although, I'd think it should compare the last value to make sure it is what it thinks it is.

Is there an elegant way (without additional helper data structures) to make it "understand" it doesn't hold the value?

stl c++
2 Answers

auto cmp = [&v](size_t a, size_t b){return v[a] < v[b];};

You're comparing the value of v[a] and v[b], not a and b, in the cmp function.

So, if you have a = 2 and b = 1, the cmp function will compare v[2] and v[1], which is 1 and 1, then it will return false, which is not what you want.

For example, if you want to write a function that compares v[a] and v[b] using a function, what will you write?

bool compare(int a, int b)
{
    return v[a] < v[b];
}

or

bool compare(int a, int b)
{
    return a < b;
}

So, you should change it to this:

auto cmp = [](int a, int b){return a < b;};

edit: Here is a demo from Ted Lyngmo

user_141937970

According to your cmp comparator,1, 2 and 3 are all equivalent keys (since v[1], v[2] and v[3] are all 1), so s.find(3) != s.end() is correct and not implementation specific.

It sounds like you want ordering to happen according to cmp, but membership tests according to the default std::less<int>. In that case, std::multiset alone cannot accommodate you as it uses one comparator for both.

user_15540200
Related