When using algorithms in C++, such as
sort(), etc., you might wonder why you need to specify both the beginning and the end of the container, and not just a reference to the container itself. See for instance:
vector<int> v; //Assume it also has some elements sort(v.begin(), v.end());
Wouldn’t it be better if we could just write
and let sort call
If this was the case, algorithms would only work on containers that define
end(). Algorithms in C++ do however work on any type that has an iterator. And an iterator is not a type, it is pure abstraction. Anything that behaves like an iterator is an iterator. If a type has a concept of the element currently pointed to, pointing to the next element and equality, it can be an iterator.
One important example is pointers. C++ algorithms work with standard arrays, because pointers behave as iterators. It would be impossible to do this:
int a; // sort(a);
How would sort get a hold of iterators (pointers) to the beginning and end of the array? The beginning is easy, but since the length of the array is lost when passed to a function, the end is not in sight. For this to work, one would have to have special versions of all algorithms, taking the size of the array as an extra argument. This would lead to a loss of generality, and double the amount of algorithms.
Passing two iterators however preserves generality, and can be used with anything that behaves like an iterator.
Note that algorithms are not defined to take a specific iterator type, like this:
void sort(iterator begin, iterator end); //All iterators inherit from iterator
Instead, they are defined like this:
template <class It> void sort(It begin, It end); //The type of It can be whatever
First, this lets us use pointers as iterators. Pointers of course do not inherit from an
iterator type. Second, this relieves us of runtime polymorphism (which could negatively impact both speed and size). If you try use a type that does not provide the necessary iterator operators, the compiler will catch it when
sort() tries to use them.
This is typical for templates; with compile time polymorphism, anything that provides the interface used by the templated function is acceptable, regardless of what (if anything) it inherits from. This is often referred to as duck typing: “when I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.” This is also what allows you to make a
vector of any type. Note that this is different from for instance Java, which uses inheritance for collections instead of duck typing. In Java, all classes inherit from
Object, and you can only have collections of objects, not primitive types.