Topic:

We saw in the last article that it is desirable sometimes to have different implementations of the same conceptual task. In particular, we wrote a function getNthElement, which returns the element at position N of a container (not to be confused with std::nth_element, which has entirely different behavior). We wrote two overloads of this templated getNthElement function, one so that it worked with all C++ STL containers, and another "optimized" overload for vector so that it would use a faster implementation for that case. In particular, we noticed that we can get to a vector's Nth element quite easily in O(1) time by saying myVector[2] rather than walking through the iterators, one element at a time.

In this next article, we're going to take things a step further. We noticed a problem last time: calling getNthElement with a deque should probably also use our faster O(1) implementation, but it doesn't, it uses an O(N) version to step through the iterators. The subject of the next article is fixing this problem (and generalizing our solution for other containers).

So, for next time:

1) A lemma to Q2: What features of a container determine whether or not you can get the Nth element of that container in O(1) time? What commonalities would I expect in the interfaces of such containers?

2) How can I write [only] two getNthElement function overloads so that containers that can perform the task in O(1) time, do, and those that can't, still compile and output the same conceptual result, but take O(N) time?

3) Bonus points: How could I implement one overload of getNthElement that also optimized for containers like vector and deque by making use of a C++ STL function? Is this implementation better than our answer to Q2? Why?

Review:

By this point in the series, you should be able to answer these fundamental code reuse questions:
1) How do I reuse the same implementation code with different types? (Review here)
2) How do I use the same code to invoke different fundamental implementations selected by type? (Review here)

If you struggle with these concepts, I highly recommend going back and (re)reading the relevant articles, then playing around with the concepts in your own code until they start to click and make sense.