`<algorithm>`: Audit divergence of difference types between wrapped and unwrapped iterators and correct the uses

[frederick-vs-ja]

Describe the bug

Currently, this program, when compiled with MSVC using -std:c++latest -W3, triggers warning C4244.

#include <algorithm>
#include <iterator>
#include <vector>

template <class T>
struct small_ator {
    using value_type = T;

    using size_type       = unsigned short; // !!!
    using difference_type = short; // !!!

    small_ator() = default;
    template <class U>
    constexpr small_ator(const small_ator<U>&) noexcept {}

    T* allocate(size_type n) {
        return std::allocator<T>{}.allocate(n);
    }

    void deallocate(T* p, size_type n) {
        return std::allocator<T>{}.deallocate(p, n);
    }

    friend bool operator==(const small_ator&, const small_ator&) = default;
    template <class U>
    friend constexpr bool operator==(const small_ator&, const small_ator<U>&) {
        return true;
    }
};

int main() {
    std::vector<int, small_ator<int>> v{1, 2, 3, 4};
    std::inplace_merge(v.begin(), std::next(v.begin(), 2), v.end());
}

There're probably other algorithms incorrectly triggering this warning.

The cause seems to be that MSVC STL generally assumes that a wrapped iterator type has the same difference type as its corresponding unwrapped one. The assumption is incorrect when the wrapped iterator is an iterator type of basic_string or vector or some iterator adapting it. In such a case, the difference type of the wrapped iterator is determined by the iterator, while the difference type of the unwrapped iterator is ptrdiff_t.

Command-line test case

https://godbolt.org/z/c99638j69

Expected behavior

No warning C4244 due to small difference_type/size_type of allocator types, for all algorithms.

STL version

Probably all existing versions where this program is accepted.

Additional context

Add any other context about the problem here.