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.