is it possible to using std::pair as key of std::set without any duplicates each element?

user_12093262 0
Viewed 101

I'm trying to store struct in std::set using two integers in struct as key. I know that is possible to using std::pair as key of std::set.

struct TYPE{
  pair<int, int> nums;
  ... // some other things

  TYPE(){}
  TYPE(int first, int second) { nums = make_pair(first, second); }
  bool operator<(const TYPE &rhs) const{
    return nums < rhs.nums;
  }
};
set<TYPE> nums_set;
nums_set.insert(TYPE(1, 2));
nums_set.insert(TYPE(1, 4));
nums_set.insert(TYPE(5, 2));
// size of set : 3, (1,2)(1,4)(5,2)
auto it = nums_set.find(TYPE(1, 2)); // find return (1,2)

However, I want searchable and no duplicates std::set, regardless of the order of the elements in std::pair. like this :

nums_set.insert(TYPE(1, 2));
nums_set.insert(TYPE(1, 4)); // failed. duplicate 1
nums_set.insert(TYPE(4, 2)); // failed. duplicate 2
nums_set.insert(TYPE(4, 1)); // failed. duplicate 1
nums_set.insert(TYPE(3, 4));
// size of set : 2, (1,2)(3,4)
auto it = nums_set.find(TYPE(2, 7));  // find return (1,2).

easiest solution so far is use std::vector instead and do duplicate check before inserting into the vector like this:

auto fn = [](const TYPE& e, const TYPE&& t){
    return e.nums.first == t.nums.first ||
            e.nums.first == t.nums.second ||
            e.nums.second == t.nums.first ||
            e.nums.second == t.nums.second;
};
vector<TYPE> nums_vec;
nums_vec.push_back(TYPE(1, 2));
if(nums_vec.end() == find_if(nums_vec.begin(), nums_vec.end(), 
  bind(fn, placeholders::_1, TYPE(1,4))))
{  nums_vec.push_back(TYPE(1,4)); }

However, I feel it's not a good idea to do this for every insert to avoid duplication. So, my question is, is it possible to implement these features with std::set too?

c++11 stl c++
2 Answers

The comparison used for a set must satisfy the Compare named requirement. Among these requirements is transitivity of the induced equivalence relation:

If equivalent(a,b) and equivalent(b,c) then equivalent(a,c).

A concrete case:

  • Let a be {1,2}, b be {1,4}, and c be {3,4}.
  • Transitivity: if {1,2} is equivalent to {1,4} and {1,4} is equivalent to {3,4} then {1,2} is equivalent to {3,4}.

Another way to express that X is equivalent to Y is that the presence of X in your set prevents Y from being added. You want {1,2} to prevent {1,4} from being added to the set. You want {1,4} to prevent {3,4} from being added to the set. To have the required transitivity, it is required that {1,2} prevent {3,4} from being added to the set, which is something you do not want.

No, your goal cannot be achieved solely by the ordering used by the set.

user_98373010

There is no strict weak ordering that you can use, so you cannot use std::set.

However, you can use std::unordered_set which only requires to provide equality.

user_93053980
Related