Why Algorithms Need two Iterators


When using algorithms in C++, such as find(), 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

sort(v);

and let sort call begin() and end()?

If this was the case, algorithms would only work on containers that define begin() and 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[42]; //
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.

2 Responses to “Why Algorithms Need two Iterators”

  1. Alf P. Steinbach Says:

    I find this macro sometimes useful:

        #define CPPX_ALL_OF( v )   \
            ::progrock::cppx::startOf( v), ::progrock::cppx::endOf( v )
    

    Cheers,

    – Alf

  2. Anders Schau Knatten Says:

    I am a bit skeptical towards macros like these. Once you start using clever macros, it can be hard to set the limit.

    And when you make up a name that you are sure won’t clash with whatever other libraries someone might use, the macro name itself approaches the ugliness of the code you are trying to avoid.

    Third, everyone who knows C++ will recognize v.begin() and v.end(), but when they see a new macro, they cannot be 100% sure nothing fishy is going on, and might get distracted to investigate.

    But then again, I have never really used macros much, as I have always been a skeptic. So I cannot really back this claim up with any real world war stories.

    (Totally unrelated, I find this macro really cute: )

    #define ever (;;)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: