unexpected error in unordered_map iterator comparison

Question

I have a simple map std::map<string, my_namespace::MyType>, I am using c++11 so I replaced it with unordered_map for performance reasons. I got the following error when comparing an iterator with end().

auto cit = str_map_.find(str);
if (cit != str_map_.end()) {
   ...
}

In instantiation of 'bool my_namespace::operator!=(const T1&, const T2&) [with T1 = std::__detail::_Node_iterator<std::pair<const std::__cxx11::basic_string, my_namespace::MyType, false, true>; T2 = std::__detail::_Node_iterator<std::pair\ <const std::__cxx11::basic_string, my_namespace::MyType, false, true>]': no matching function ...

I debugged it down to my rather creative comparison operators for my_namespace::MyType:

template <class T>
struct MyType {
    T* mt_;
};

struct MyTempClass {
    std::string mtc_;

    static int Compare(MyType<MyTempClass> const& lhs, MyType<MyTempClass> const& rhs) {
        return lhs.mt_->mtc_.compare(rhs.mt_->mtc_);
    }

    static int Compare(std::string const& lhs, MyType<MyTempClass> const& rhs) {
        return lhs.compare(rhs.mt_->mtc_);
    }

    static int Compare(MyType<MyTempClass> const& lhs, std::string const& rhs) {
        return lhs.mt_->mtc_.compare(rhs);
    }
};

template <class T1, class T2>
bool operator !=(T1 const& lhs, T2 const& rhs) {
    int res = MyTempClass::Compare(lhs, rhs);
    return (res != 0);
}

template <class T1, class T2>
bool operator ==(T1 const& lhs, T2 const& rhs) {
    int res = MyTempClass::Compare(lhs, rhs);
    return (res != 0);
}

static std::unordered_map<std::string, MyType<MyTempClass>> my_map;

But I am still puzzled why it did happen: the same code works fine with a plain map, and values type should not be involved in iterator comparisons?

Muhammad Mohsin Khan · Accepted Answer · 2022-01-03 12:43:12Z

2

You defined an operator!= overload that takes any type as an argument. That overload is in the same namespace as the type MyType. Therefore, it can potentially be found via ADL.

As the error message indicates, the std::unordered_map iterator used by the standard library is a class template specialization, specialized on the std::unordered_map template arguments. As such, when you compare iterators with !=, ADL is performed on the arguments and the namespaces searched by ADL also include the namespaces of type template arguments of the types of the arguments. Therefore, your operator!= overload in the namespace of MyType will also be found and participate in overload resolution.

Assuming you are using libstdc++ as standard library implementation based on the error message, you can have a look at it's implementation of the operator!= for hash table iterators and you will see that it uses a base class for these iterators, and defines the comparison operators for references to the base class objects.

As a consequence, the standard overload for the iterator comparison requires a derived-to-base reference conversion in its arguments, while your overload does not.

Therefore your overload is better and will be chosen to do the cit != str_map_.end() comparison. Your overload tries to pass the arguments MyTempClass::Compare which clearly doesn't work, because these functions don't expect std::unordered_map iterators.

The solution is not to overload operators for pairs of types that do not depend on user-defined types. Restrict your overloads to your own types:

template <class T1, class T2>
bool operator !=(MyType<T1> const& lhs, T2 const& rhs) {
    int res = MyTempClass::Compare(lhs, rhs);
    return (res != 0);
}

template <class T1, class T2>
bool operator !=(T1 const& lhs, MyType<T2> const& rhs) {
    int res = MyTempClass::Compare(lhs, rhs);
    return (res != 0);
}

(equivalently for operator==).

As far as I know, it is not forbidden to overload the operators for standard library type pairs, but I also don't think that the standard library is required to account for conflicts this generates as in your code.

With std::map the standard library implementation might have chosen a different way of implementing the iterator comparison, which made it a better fit in overload resolution or avoided that ADL finds your overload by not making the iterator a template specialized on the key/value type.

edited Jan 3, 2022 at 12:43

Muhammad Mohsin Khan

1,4767 gold badges18 silver badges24 bronze badges

answered Jan 2, 2022 at 20:06

user17732522

78.1k3 gold badges82 silver badges147 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

uuu777 Over a year ago

Thank you, but I really surprised that value type is playing any part in iterator comparisons.

user17732522 Over a year ago

@zzz777 It doesn't. The short version of my explanation is that you just replaced the meaning of != by declaring a operator!= overload that claims to accept any type. This is more obvious if you use the expression containing != in the same namespace in which the overload is declared. In your case it is just a bit roundabout because of C++ argument dependent lookup rules.

uuu777 Over a year ago

Sorry for being annoying. I had this issue resolved, thank you. But I still do not get it, I did not override anything for the keys, the key is still simple std::string whatever is the value it should have no effect on maps??? Say I have values that are not comparable at all or have some out of whack ordering, I believe that maps with these values should still work?

user17732522 Over a year ago

@zzz777 The key and value type don't really matter. It only matters that your custom type appears in them as template argument. The comparison cit != str_map_.end() compares iterators, not keys. The comparison should choose an operator!= overload defined in the standard library for them. But normal overload resolution applies to every use of an operator. C++ overload resolution has the argument dependent lookup rule (ADL), which says that also overloads, not usually found by direct name lookup, but defined in namespaces associated with the types of the arguments are found.

user17732522 Over a year ago

Your overload is found that way (details in the answer) and happens to be a better fit in overload resolution. Instead of using the operator!= overload defined by the standard library that should be used for iterators your function is called, which is obviously nonsense. This could have happened comparing any types from the standard library that take your custom type as template argument. It is not specific to std::unordered_map or its iterators or anything.

|

Collectives™ on Stack Overflow

unexpected error in unordered_map iterator comparison

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related