C++ Fundamentals: Template operator- overloading Failed - "template argument deduction/substitution failed"

Question

I have been trying to write my own vector class to better understand C++ templates and iterators, but have been stuck with this error for a while and would really appreciate the help.

The code fails at the second to last line where I call the overloaded operator -.

Code: (Simplified)

#include <memory>

template <typename T>
struct MyVector {
    struct iterator {
        T* ptr;
        iterator(T* p) : ptr(p) {}
    };

    std::unique_ptr<T[]> data;    
    size_t size;

    MyVector() : data(nullptr), size(0) {}
    MyVector(size_t sz) : size(sz) {
        data = std::make_unique<T[]>(size);
    }
    iterator begin() {
        return iterator(data.get());
    }
    iterator end() {
        return iterator(data.get() + size);
    }
};

template <typename T>
int operator-(typename MyVector<T>::iterator a, typename MyVector<T>::iterator b) {
    return a.ptr - b.ptr;
}

int main() {
    MyVector<int> mv(3);
    mv.end() - mv.begin(); // fails
}

Error:

so.cpp: In function ‘int main()’:
so.cpp:32:14: error: no match for ‘operator-’ (operand types are ‘MyVector<int>::iterator’ and ‘MyVector<int>::iterator’)
   32 |     mv.end() - mv.begin();
      |     ~~~~~~~~ ^ ~~~~~~~~~~
      |           |            |
      |           |            iterator<[...]>
      |           iterator<[...]>
so.cpp:26:5: note: candidate: ‘template<class T> int operator-(typename MyVector<T>::iterator, typename MyVector<T>::iterator)’
   26 | int operator-(typename MyVector<T>::iterator a, typename MyVector<T>::iterator b) {
      |     ^~~~~~~~
so.cpp:26:5: note:   template argument deduction/substitution failed:
so.cpp:32:25: note:   couldn’t deduce template parameter ‘T’
   32 |     mv.end() - mv.begin();
      |               

Havoc

I think the better question here is "Why can't T be deduced?" The answer you get for that will serve you a lot longer and further. – Midinette

@Midinette Thanks 273K posted a link on template argument deduction that I'm going to take a look at as I'm still confused even after resolving this issue. I've been using Stoustrup's "A Tour of C++" and he really barely goes into it. – Havoc

A tour of C++ is terse as hell. When I'm spinning up a new C++ hire at work, I get them up to C++11 with Stroustrup's Programming Practice and Principles and use Tour to get them up to, well almost up to, date. Now, it's been years since I read the sucker, so I can't remember how deep into argument deduction Principles gets, but for most details, the extra love Principles gives puts it well above Tour. – Midinette

Answer 1

first of all, I have done this exact thing before, and I would recommend using a class over a struct, either way, if you want the operator - to work on MyVector.end() - MyVector.begin() it has to go in the iterator struct, and in this case, the operator should have 1 argument, the target. The error mainly came from the compiler not being able to resolve the template because you put one above the operator - function which meant that it expected a type when the function was called, I didn't modify any of your code other than what was required to make this work, because you said that it was a project to learn, here's the fixed and running code:

#include <iostream>
#include <memory>

template <typename T>
struct MyVector {
    struct iterator {
        T* ptr;
        iterator(T* p) : ptr(p) {}

        int operator - (const iterator tgt) const {
            return this->ptr - tgt.ptr;
        }
    };

    std::unique_ptr<T[]> data;
    size_t size;

    MyVector() : data(nullptr), size(0) {}
    MyVector(size_t sz) : size(sz) {
        data = std::make_unique<T[]>(size);
    }

    iterator begin() {
        return iterator(data.get());
    }

    iterator end() {
        return iterator(data.get() + size);
    }
};

int main() {
    MyVector<int> mv(3);
    int thing = mv.end() - mv.begin();
    std::cout << thing << std::endl;
}

Convertite

Thanks, this helped a lot.: "The error mainly came from the compiler not being able to resolve the template because you put one above the operator - function which meant that it expected a type when the function was called," Also yeah my actual code is wrapped in a class, private/public seperated, etc. I just simplified it here. – Havoc

Answer 2

You should not overload operator- in the global namespace.

#include <cstddef>
#include <memory>

template <typename T>
struct MyVector {
  struct iterator {
    T* ptr;
    ptrdiff_t operator-(const iterator& b) const { return ptr - b.ptr; }
  };

  std::unique_ptr<T[]> data;
  size_t size = 0;

  MyVector() = default;
  MyVector(size_t sz) : size(sz) { data = std::make_unique<T[]>(size); }
  iterator begin() const { return {data.get()}; }
  iterator end() const { return {data.get() + size}; }
};

int main() {
  MyVector<int> mv(3);
  mv.end() - mv.begin();  // fails
}

See Template argument deduction. T in typename MyVector<T>::iterator is not deductible, iterator is a dependent type.

Heterochromatin

"You should not overload operator- in the global namespace" is a big statement, given that our most canonical resource says something opposite. – Koweit

An explanation why your version works but the global templated one doesn't would not go amiss, seeing as the asker says they're trying to learn fundamentals. – Flophouse

This is true, when you need operator-(U, iterator). Here it is operator-(iterator, iterator) and a member-function is preferable. – Heterochromatin

Thanks @273K I was a had seen the link on operator overloading previously and was using it, but did not realize it did not apply to templates. I now understand why I've seen recommendations to make overloaders friend functions defined within the class to avoid this issue though. – Havoc

Answer 3

I can't explain the rules behind template deduction, it's probably something that deduction only happens on object passed as argument, not on the nesting type. One way to solve it (and one that is used e.g. by gcc's standard library) is to make iterator a non-nested class, only exposing it as nested name alias (see it online):

namespace detail {
template <typename T>
struct MyIterator {
    T* ptr;
    MyIterator(T* p) : ptr(p) {}
};

template <typename T>
int operator-(MyIterator<T> a, MyIterator<T> b) {
    return a.ptr - b.ptr;
}
}  // namespace detail

template <typename T>
struct MyVector {
    using iterator = detail::MyIterator<T>;
    // ... rest of implementation
};

int main() {
    MyVector<int> mv(3);
    mv.end() - mv.begin();  // fails
}

Whether this is better than just making it a member function, I'd say it's disputable.
The upsides are that it follows the recommendation of basic rules and idioms of overloading operators, which is a well known wiki for C++ and people tend to stick to that (though it also specifically accepts the case of making such operator member in nested class). It also allows you to reuse this iterator type in other containers (e.g., in std::array-like container).
The downside is that you lose possibility to make it truly private and people will have access to detail::MyIterator anyway.

Koweit

thanks for the help. I wasn't sure if one of the two ways was correct. I've stuck with the other answers mentioned just because I'm done with this exercise but going forward yours definitely looks much cleaner and understandable if its the way the STL does it. – Havoc