How does STL algorithm work independent of Iterator type?

Question

How does STL algorithm work independent of Iterator type?

Answer 1

Polymorphism

Answer 2

Every STL algorithm is a template function which takes iterator type as its template parameter.

Answer 3

Any STL algorithm is generated automatically by compiler for each iterator type you use it with.

It is called C++ templates or static polymorphism.

Answer 4

STL algorithm are template functions, which means they can be called with any type.

When calling the function with a specific type, the compiler will try to compile an instance of the function for this specific type and report any compilation error (missing methods, type check errors, etc.)

For STL algorithms, as long as the type used behaves like an iterator (supports ++, dereferencing), it will work. That's why those algorithms works with native pointers too, because they support the same type of operations than iterators (that is how they were designed in the first place).

Answer 5

Really, they just work. They use some pretty basic properties of templates, sometimes called static polymorphism. If you're familiar with the term, it is essentially a form of ducktyping. (If it looks like a duck, and it quacks like a duck, it must be a duck)

The trick is simple. Here's a very simple example:

template <typename T>
void say_hello(const T& t) {
  t.hello();
}

The say_hello function doesn't care which type its argument is. It doesn't have to derive from an interface or make any other kind of "promises" about what it is. All that matters is that the type works in this context. All we do with the type is call its hello function. Which means that this code will compile for any type that has a hello member function.

The STL algorithms work similarly. Here's a simple implementation of std::for_each:

template <typename iter_type, typename func_type>
void for_each(iter_type first, iter_type last, func_type f){
  for (iter_type cur = first; cur != last; ++cur) {
    f(*cur);
  }
}

This code will compile whenever the template types live up to the requirements placed on them; iter_type must have the pre-increment ++-operator. It must have a copy constructor, and it must have the != operator, and it must have the *-dereference-operator.

func_type must implement the function-call operator, taking an argument of the same type as you get by dereferencing an object of type iter_type. If I call for_each with types that satisfy these requirements, the code will compile. iter_type can be any type that satisifies these requirements. There is nothing in the code that says "this shall work with vector iterators and list iterators and map iterators". But as long as vector, list or map iterators implement the operators we use, it'll work.

Answer 6

Not all STL container/iterator algorithms have this independence. The ones that do are call Generic Algorithms, but these are usually just called STL algorithms.

With iterators only you can:

• inspect the sequence so you can do things like find, count, for_each,…
• change the value of the iterator references so you can do things like transform, copy, rotate, swap, replace, …
• reorder the values of the iterators, so you can do things like sort, merger, nth_element.

Some non-generic algorithms can be broken up into 2 stages, a STL Generic part and a container dependent part. So in order to destroy all values that are greater than 7 in a vector we can do a remove_if ( the generic part which only sorts the elements) followed by a erase ( the non-generic part that destroys the value).