Is it possible to have two keys in unordered_combination that are considered equal?
Hence :
Pred: The unordered_set object uses this expression to determine whether two item keys are equivalent. None of the two elements in the unordered_set container can have keys that evaluate to true using this predicate.
And also from 23.5.6.1/1:
Unordered_set is an unordered associative container that supports unique keys ( unordered_set contains at most one value for each key ), and in which the keys of the elements are the elements themselves. The unordered_set class supports forward iterators.
But I can get around this if I define my own hasher and equivalent operation that use different class type functions.
#include <iostream>
#include <unordered_set> //for unordered_set and unordered_multiset
using namespace std;
struct A{
A() = default;
A(int a, int b): x(a), y(b) {}
int x = 0, y = 0;
};
size_t hasher(const A &sd){
return hash<int>()(sd.x);
}
bool eqOp(const A &lhs, const A &rhs){
return lhs.y == rhs.y;
}
int main(){
unordered_set<A, decltype(hasher)*, decltype(eqOp)*> unorderedA(10, hasher, eqOp);
unorderedA.emplace(2,3);
unorderedA.emplace(3,3);
for(const auto& c : unorderedA)
cout << c.x << " " << c.y << endl;
}
Outputs;
3 3
2 3
I understand what's going on: the hasher puts each key in a different bucket because of their x value. However, these two keys should have been considered equal by my eqOp function because of their y value, but they are never checked for equivalence as they fit in different buckets. So it is normal functionality that an unordered container can hold two equivalent keys if they come in different buckets. Or is it the coder's responsibility to make sure the hasher and predicate are written to put the equivalent keys in the same bucket? Or maybe my eqOp function is breaking a rule that the compiler doesn't detect?
It's clear in the set and map: the predicate provided by the topic defines a strong weak ordering, so the two equivalent keys only have one element associated with them. In an unordered map, it's not so clear to me: two equivalent keys can have different elements associated with them, as long as those keys are in different buckets. But these sources above feel like they are telling me differently.
source to share
No, It is Immpossible. Your example is not valid because the standard requires you to return the same hash value for equivalent keys:
23.2.5 Unordered associative containers
- Two values k1 and k2 of type Key are considered equivalent if the containers key_equal function returns true when passing these values. If k1 and k2 are equivalent, the hash function will return the same value for both. [Note: Thus, when an unordered associative container is created with a custom Pred parameter, it usually requires the default Hash parameter as well. - end note]
The library user could not ensure that the values fall into different buckets, since it is not defined how all possible hash values are mapped to bucket indices or how map operations change the number of buckets.
source to share