1

Due to using a library that I don't want to edit the code of, I find myself requiring the use of std::map<Identifier, String>.

struct compareIdentifiers
{
    bool operator()(const Identifier& a, const Identifier& b) const
    {
        // return a < b;
        return true;
    }
};

typedef std::map<Identifier, String, compareIdentifiers> IdentifierMap;

Should I return true or false? No comparison needs to be made. I imagine returning true or returning false would be wildly different in efficiency because one will cause the map to re-order, the other won't... right?

I tried to use std::unordered_map<Identifier, String> but got error:

Error C2280 'std::hash<_Kty>::hash(void)': attempting to reference a deleted function

Elan Hickler
  • 1,099
  • 1
  • 11
  • 28
  • 2
    Why not use `std::unordered_map` if that's what you want? Or copy to an unordered map? What is the actual problem you need to solve? Why do you need to treat the ordered `std::map` as unordered? – Some programmer dude May 22 '19 at 05:47
  • 2
    As for the error message, you need to specialize `std::hash` for your key type if you want to use `std::unordered_map`. There are plenty of tutorials and examples all over the Internet if you just search a little. – Some programmer dude May 22 '19 at 05:48
  • 1
    If you must return a constant value, that constant can't be `true`, because it's invalid for `comp(x,x)` to be true for any object. You can always return `false`, which means the `map` can contain at most one key-value pair. This is probably not the way to do what you want to do. – aschepler May 22 '19 at 06:01
  • 1
    Why wouldn't you just implement a simple comparison function? I don't know what `Identifier` is, but I bet it has a numerical or string representation that would be worthy of applying a `<` operator to. – selbie May 22 '19 at 06:03
  • I finally had a mental breakthrough. My solution is `IdentifierA.getCharPointer().getAddress() < IdentifierB.getCharPointer().getAddress()` The reason I didn't do this before is because I thought the only way to compare Indentifier classes was with a slow string comparison method. – Elan Hickler May 22 '19 at 11:27

4 Answers4

7

Always returning true is invalid. It would mean (for instance) that A < B and B < A would both be true. This contradicts the requirements of a std::map comparator, which are that it imposes a strict weak ordering. It's entirely possible returning true would crash your program.

Always returning false is valid, it effectively means that all keys are considered equal. So only one key could be added to the map (thanks aschepler for the correction).

What stops you writing a sensible comparator?

john
  • 85,011
  • 4
  • 57
  • 81
  • Identifier class has no `<` operator – Elan Hickler May 22 '19 at 06:10
  • 1
    Why is that a problem? Just make up something that satisfies a strict weak ordering and put it in your comparator. The ordering you use can be completely arbitrary, – john May 22 '19 at 06:15
  • Why not just return false? Edit: It's a problem because it's expensive to compare the class... at first glance. – Elan Hickler May 22 '19 at 06:19
  • @ElanHickler Just a free-standing `bool operator<(Identifier const& x, Identifier const& y) { return /* comparison as needed */; }` and you have one... – Aconcagua May 22 '19 at 06:23
  • then why do we have 5 upvotes for "Always returning false is valid"? This answer should be deleted or downvoted. – Elan Hickler May 22 '19 at 06:28
  • 1
    @ElanHickler Remind me not to try and help you again. Apart from the ungrateful tone, I can see that you haven't read my answer properly (or haven't understood it). To be clear, returning false doesn't break any rules of C++ (unlike returning true). In that sense it's valid. It's not useful though. – john May 22 '19 at 06:34
  • I withdraw my comment ... didn't think. – Ted Lyngmo May 22 '19 at 06:48
  • @john whaaat? I read it perfectly clear. Ted said your answer was wrong, not me. I don't know any better, that's why I'm here asking questions?!?!? – Elan Hickler May 22 '19 at 06:52
  • 1
    @ElanHickler using the `return true` compare with `std::map` is undefined behaviour. using the `return false` compare is *not* undefined behaviour, but means that the map can only contain at most one element, as every potential element compares the same as every other potential element. – Caleth May 22 '19 at 10:36
  • Thank you for explaining Caleth, now I get it. Ohhhhhhhhhhh!!!!!!!!!!!!!!!! I just had another idea. Instead of using an unordered_map, I can do a hash comparator like `this_hash < that_hash` if I want to go back to using a map. p.s. Identifier is essentially a hash already. I previously thought I had to compare those classes using a slower string compar method. – Elan Hickler May 22 '19 at 11:22
4

I tried to use std::unordered_map but got error:

Error C2280 'std::hash<_Kty>::hash(void)': attempting to reference a deleted function

This is due to the unordered map using an instance of std::hash, but its specialisation for your Identifier class has a deleted operator(). You now have two options:

  1. specialise std::hash for your type:

    namespace std
{
template<>
class hash
{
public:
std::size_t operator()(Identifier const&) const
{
    return /* whatever is appropriate */;
    // best is if you can base the hash code on already defined
    // hashes of its members
}
};
}

  2. write your own hash class (again providing operator()) and provide it as third template parameter to your unordered map: std::unordered_map<Identifier, String, MyHash>

Aconcagua
  • 24,880
  • 4
  • 34
  • 59
1

I was able to create a custom hash for this class by looking at its implementation and its return types and the return types of its return types until I found an efficient series of methods that returns a standard type I could return that std::hash has as a type-specific specialization. The list is found here: http://www.cplusplus.com/reference/functional/hash/

struct IdentifierHash {
    size_t operator()(const juce::Identifier& v) const
    {
        std::hash<char*> hash;
        return hash(v.getCharPointer().getAddress());
    }
};

typedef std::unordered_map<Identifier, String, IdentifierHash> IdentifierMap;

If I want to use std::map then I can create a comparator like this:

struct IdentifierComparator
{
    bool operator()(const Identifier& left, const Identifier& right) const
    {
        return left.getCharPointer().getAddress() < right.getCharPointer().getAddress();
    }
};

typedef std::map<Identifier, String, IdentifierComparator> IdentifierMap;
Elan Hickler
  • 1,099
  • 1
  • 11
  • 28
-4

Call your binary operators' parameters lho and tho (left hand operand and right hand operand), it will make immediately clear what you are expected to return. (True in case lho https://en.cppreference.com/w/cpp/named_req/Compare

It is so easy to break one, I just learned the hard way.

m2c

Giuseppe Puoti
  • 130
  • 8
  • What has this to do with the *actual* question? – Aconcagua May 22 '19 at 06:20
  • He was asking what to return from the compare. Reading other answer better than mine, now I realize that he was asking for a safe value to return making actually no comparison. I'm glad I wrote the advice to follow the compare requirements because as some other people said, returning constantly true or false has quite big side effects. – Giuseppe Puoti May 22 '19 at 09:31
  • If there aren't any comparisons done anyway, one could even leave out the names entirely to indicate that the parameters actually are not used at all (some recommend to add names in comments then). Might your proposed names be better or not (I won't qualify, actually, that's quite subjective – first argument stands on the left, so must be left-hand, analogously for right, so self-explaining anyway), it remains totally irrelevant to the question itself. – Aconcagua May 22 '19 at 10:07
  • Onestly I don't see big differences between this answer and the accepted one. At least in the spirit. Anyway sorry for the garbage I wrote in this page. – Giuseppe Puoti May 22 '19 at 10:25
  • Difference to accepted answer? Well, you don't lose any word about the consequences of constantly returning true or false, do you? But that's what the question is about. If the author used the identifiers you propose, the question wouldn't change the least bit, would it? That's why your answer is unrelated (counter example: it would have be appropriate if the author had mixed up the variables in his code due to badly selected names). – Aconcagua May 22 '19 at 18:56
  • "Garbage"? You're judging far too strict. Indeed it *is* important to choose good, self-explaining identifiers, solely that *this* question is not the right place for the topic – at least if standing alone as in your answer. But don't get discouraged – next answer sure will match better... – Aconcagua May 22 '19 at 18:58