CODEWITHSUNDEEP
c++setg++
madhur4127
madhur4127

Reputation: 336

How does set works with unique keys but with equivalent value of keys in C++?

vector< pair<int,int> > v; 
    // using indices for comparing pairs
auto func = [&](int i, int j) { return v[i] > v[j]; };
    // set which will store the indices and compare keys using
    // func based on values in v
set<int, decltype(func)> index_set(func);

If I have two same values v[0]={1,2} and v[1]={1,2} and I insert them into the index_set, i.e.

index_set.insert(0);
index_set.insert(1);

Reality: I will have only 1 element in index_set (index_set.size()=1), which is only index 0 and index 1 is not inserted.

Expectations: Both 0 and 1 must be inserted.

Rationale: According to cplusplus, it says:

Unique keys
    No two elements in the container can have equivalent keys.

Because keys are not equivalent (0 != 1) so set should contain both 0 and 1. Why is this behaviour justified? I think I am confusing for values of keys for literal values of keys.

Minimal, Complete, Verfiable example: Try this code on ideone!

Upvotes: 0

Views: 1128

Answers (2)

R Sahu
R Sahu

Reputation: 206637

The compare function you are using is not very intuitive. The way it's been implemented, 0 and 1 are considered equivalent. If you insert 1 first, 0 will not be inserted.

If you have 

v[0] = {1, 2};
v[1] = {1, 2};
v[2] = {2, 2};
v[3] = {1, 2}

Then, 0, 1, and 3 will be considered equivalent as far as the set is concerned.

Upvotes: 0

jamesdlin
jamesdlin

Reputation: 90025

cplusplus.com states further down on the page:

Compare ... 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.

You've specified a custom comparison function that states that elements 0 and 1 should be considered equal. Therefore your std::set will keep only one of them.

Upvotes: 1

Related Questions