The problem with integer indices

In the previous chapter, we implemented several generic algorithms that operated on containers. Consider one of those algorithms again:

    template<typename Container>
    void double_each_element(Container& arr) 
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

This algorithm is defined in terms of the lower-level operations .size() and .at(). This works reasonably well for a container type such as array_of_ints or std::vector, but it doesn't work nearly so well for, say, a linked list such as the previous chapter's list_of_ints:

    class list_of_ints {
      struct node {
        int data;
        node *next;
      };
      node *head_ = nullptr;
      node *tail_ = nullptr;
      int size_ = 0;
    public:
      int size() const { return size_; }
      int& at(int i) {
        if (i >= size_) throw std::out_of_range("at");
        node *p = head_;
        for (int j=0; j < i; ++j) {
          p = p->next;
        }
        return p->data;
      }
      void push_back(int value) {
        node *new_tail = new node{value, nullptr};
        if (tail_) {
          tail_->next = new_tail;
        } else {
          head_ = new_tail;
        }
        tail_ = new_tail;
        size_ += 1;
      }
      ~list_of_ints() {
        for (node *next, *p = head_; p != nullptr; p = next) {
          next = p->next;
          delete p;
        }
      }
    };

The implementation of list_of_ints::at() is O(n) in the length of the list--the longer our list gets, the slower at() gets. And particularly, when our count_if function loops over each element of the list, it's calling that at() function n times, which makes the runtime of our generic algorithm O(n2)--for a simple counting operation that ought to be O(n)!

It turns out that integer indexing with .at() isn't a very good foundation on which to build algorithmic castles. We ought to pick a primitive operation that's closer to how computers actually manipulate data.