How does an STL algorithm identify the container?

Question

How does an STL algorithm identify on what kind of container it is operating on?
For example, sort accepts iterators as arguments.
How does it know what kind of container it has to sort?

Answer 1

It doesn't :-) That's the whole point of iterators -- the algorithms that work on them don't need to know anything about the underlying container, and vice versa.

How does it work then? Well, the iterators themselves have a certain set of well-known properties. For example, 'random-access' iterators allow any algorithm to access an element offset from iterator by a constant:

std::vector<int> vec = { 1, 2, 3, 4 };
assert(*(vec.begin() + 2) == 3);

For a sort, the iterators need to support random access (in order to access all the elements between the first and end iterators in an arbitrary order), and they need to be writable (in order to assign or otherwise swap values around), otherwise known as 'output' iterators.

Example of an output iterator vs. an input (read-only) one:

std::vector<int> vec = { 1, 2, 3, 4 };
*vec.begin() = 9;
assert(vec[0] == 9);

*vec.cbegin() = 10;    // Does not compile -- cbegin() yields a const iterator
                       // that is 'random-access', but not 'output'

Answer 2

It doesn't need to know the type of the container, it just needs to know the type of iterator.

Answer 3

As mentioned earlier, STL uses iterators, not containers. It uses the technique known as "tag dispatch" to deduce proper algorithm flavor.

For example, STL has a function "advance" which moves given iterator it by given n positions

template<class IteratorType,
    class IntegerDiffType> inline
    void advance(IteratorType& it, IntegerDiffType n)

For bidirectional iterators it has to apply ++ or -- many times; for random access iterators it can jump at once. This function is used in std::binary_search, std::lower_bound and some other algorithms.

Internally, it uses iterator type traits to select the strategy:

template<class IteratorType,
        class IntegerDiffType> 
        void advance(IteratorType& it, IntegerDiffType n)
{
    typedef typename iterator_traits<IteratorType>::category category;
    advance_impl(it, n, category());
}

Of course, STL has to implement the overloaded "impl" functions:

template<class IteratorType,
        class IntegerDiffType> 
        void advance(IteratorType& it, IntegerDiffType n, bidirectional_iterator_tag)
{   // increment iterator by offset, bidirectional iterators
for (; 0 < n; --n)
    ++it;
for (; n < 0; ++n)
    --it;
}

template<class IteratorType,
        class IntegerDiffType> 
        void advance(IteratorType& it, IntegerDiffType n, random_access_iterator_tag)
{   // increment iterator by offset, random-access iterators
    it += n;
}