Why does std::(multi)set provide non const iterator methods

Note that in [member.functions], it's expressed that:

For a non-virtual member function described in the C++ standard library, an implementation may declare a different set of member function signatures, provided that any call to the member function that would select an overload from the set of declarations described in this document behaves as if that overload were selected.

The standard defines behavior for each container in [container.requirements.general] which require that:

• a.begin() yields an iterator (or const_iterator for constant a)
• a.end() yields an iterator (or const_iterator for constant a)
• ...

The requirement for the implementations are that those types (C::iterator and C::const_iterator) exist and that those functions yield those types. The requirement is not specifically that those four overloads must exist (nor that the two iterator types must be different). The requirement is just the behavior.

The following would be a perfectly conforming implementation for set:

template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>>
class set {
public:
    struct iterator { ... };
    using const_iterator = iterator;

    iterator begin() const { ... };
    iterator end() const { ... };

    // other stuff
};    

With this implementation, all the requirements are satisfied. So it's sufficient. Indeed, this is how libstdc++ implements it - the two iterators are the same type and there is just one begin() and just one end().

Why introduce those extra overloads?

There aren't extra overloads. Or at least, there don't have to be. It's up to to the implementer.

While I can't say for certain, consistency (see comments by @yurikilochek) seems reasonable to me. "Can you give an example of general code that will fail if those non const iterators methods are not present?" The following code does not compile with libstdc++ (but does compile under Visual Studio) because set does not have the non-const methods. I acknowledge this is not code someone would write in the course of a day that is going well.

#include <iostream>
#include <vector>
#include <set>

template <class C> //C is some container
void f(C& c)
{
    typedef typename C::iterator iter;
    typedef iter (C::*fn)(); // note non-const method

    fn begin = &C::begin; // will fail with set if begin() is const only
    fn end = &C::end;

    for (iter i = (c.*begin)(), e = (c.*end)(); i != e; ++i)
        std::cout << *i << ' ';
    std::cout << '\n';
}

int
main()
{
    std::vector<int> v;
    std::set<int> s;

    f(v);
    f(s);

    return 0;
}