CODEWITHSUNDEEP
c++unordered-map
uuu777
uuu777

Reputation: 891

unexpected error in unordered_map iterator comparison

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?

Upvotes: 2

Views: 682

Answers (1)

user17732522
user17732522

Reputation: 76829

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.

Upvotes: 2

Related Questions