Can iter_swap be specialised?

Question

If I have a container std::vector<T*> items, I can create an IndirectIterator which wraps std::vector<T*>::iterator and allows iterating over T's rather than T*'s.

Can I specialise iter_swap for IndirectIterator to make standard algorithms (such as std::sort) swap items by pointer?

i.e., if I write the following, will it have any effect on standard algorithms?

namespace some_namespace
{
    template <typename IterT>
    class IndirectIterator
    {
            IterT m_base;
        public:
            typedef IterT base_iterator;
            typedef /* ... */ reference;

            /* ... */

            reference operator*() const { **m_base; }

            const base_iterator& base() const { return m_base; }
            base_iterator& base() { return m_base; }
    };

    template <typename T>
    void iter_swap(IndirectIterator<T>& a, IndirectIterator<T>& b)
    {
        using std::iter_swap;
        iter_swap(a.base(), b.base());
    }
}

The benefit of this specialisation is that it swaps pointers rather than full T instances, so it's faster (potentially).

Answer 1

Starting in C++20, the answer is unambiguously "yes, you can customize your own ADL iter_swap." STL algorithms should use it, but aren't required to, and there is implementation divergence in practice.

For customizing a customization point, you should use the "hidden friend idiom":

namespace some_namespace {
    template <class IterT>
    class IndirectIterator {
        IterT m_base;
    public:
        /* ... */

        reference operator*() const { return **m_base; }
        const base_iterator& base() const { return m_base; }

        // "It's not a member, it's just a friend" 
        friend void iter_swap(IndirectIterator a, IndirectIterator b) {
            using std::iter_swap;
            iter_swap(a.base(), b.base());
        }
    };
}

Subtle change here: your iter_swap had been taking its arguments by mutable reference! That wouldn't work, e.g. if it were passed an IndirectIterator that was const, or that was an rvalue. Iterator parameters should always be taken by value. Similarly, there's no sense in providing a non-const version of base(). Your base() is a getter, not a setter; it should be a const member function for the same reason vector::size() is a const member function.

Finally, the big caveat here is that you must never customize iter_swap to do anything observably different from swapping the targets of the iterators. If you do that, then it's undefined behavior — all bets are off — the program could do anything. Formally, this requirement is given in [iterator.cust.swap]:

If the [iter_swap] function selected by overload resolution does not exchange the values denoted by E1 and E2, the program is ill-formed, no diagnostic required.

I believe your idea of having iter_swap swap the "first-level" targets rather than the "second-level" targets is perfectly kosher, as long as you're never going to rely on observing the difference. The standard library is still allowed to bypass iter_swap and just do swap(*it, *kt) if it feels like it; your code must be able to cope with that, or else "the program is ill-formed, no diagnostic required." (I.e., you must fully commit to the idea that swapping those first-level targets is tantamount to "exchanging the values of E1 and E2," and thus interchangeable with any other method of exchanging the values. You can't rely on your own method getting used.)

Here is a complete C++20 example on Godbolt. As of February 2023, here's where I see the customized iter_swap actually getting used:

Algorithm	libstdc++	libc++	Microsoft
std::ranges::partition	Yes	Yes	Yes
std::ranges::sort	No	No	Yes
std::partition	No	No	No
std::sort	No	No	No

UPDATE, 2024-12-24: Here's what I see now (Godbolt):

Algorithm	libstdc++	libc++	Microsoft
std::ranges::make_heap	—	—	—
std::ranges::sort_heap	—	—	—
std::ranges::partition	iter_swap	iter_swap	iter_swap
std::ranges::reverse	iter_swap	iter_swap	iter_swap
std::ranges::partial_sort	iter_swap	iter_swap	—
std::ranges::sort	swap	iter_swap	iter_swap
std::make_heap	—	—	—
std::partition	swap	swap	swap
std::reverse	swap	swap	swap
std::partial_sort	—	swap	—
std::sort	swap	swap	swap

where "—" means it doesn't even call the value type's own ADL swap. (This can happen in several ways; e.g. sort with a very small number of elements does an insertion sort, which doesn't use any kind of swapping, just assignment. For large numbers of elements it uses the swap/iter_swap shown in the table above. That said, I don't know what's the deal with any of the "—" entries above.)