Containers of Pointers

Recall the linked-list class template we defined previously:

template <typename T>
class List {
public:
  List();

  void empty() const;

  T & front();

  void push_front(const T &datum);

  void pop_front();

  void push_back(const T &datum);

  void pop_back();

  ...

private:
  struct Node {
    T datum;
    Node *prev;
    Node *next;
  };

  Node *first;
  Node *last;
};

We declared the parameters of push_front() and push_back() to be passed by reference, avoiding making a copy of the argument value. However, a Node stores a value of type T, so a copy is made when a node is created:

template <typename T>
void List<T>::push_back(const T &datum) {
  Node *node = new Node{ datum, last, nullptr };
  ...
}

With this in mind, consider the following example that inserts local objects into a list:

int main() {
  Llama paul("Paul");
  Llama carl("Carl");

  List<Llama> todo;
  todo.push_back(paul);
  todo.push_back(carl);

  for (auto &llama : todo) {
    llama.feed();
  }
}

The code creates two local Llama objects and inserts them into a list. It then iterates over the list to feed each llama. However, as shown in Figure 99, the llamas in the list are copies of the local objects, so feeding them does not affect the original llamas, which go hungry.

_images/23_llama_copies.svg

Figure 99 Inserting objects into a container creates copies of those objects.

We can use indirection to avoid making a copy, storing pointers to llamas in a list rather than llamas themselves:

int main() {
  Llama paul("Paul");
  Llama carl("Carl");

  List<Llama *> todo;
  todo.push_back(&paul);
  todo.push_back(&carl);

  for (auto lptr : todo) {
    lptr->feed();
  }
}

The code iterates over the list by value rather than by reference; however, the values are pointers, so they still indirectly refer to the appropriate Llama objects when they are copied. Figure 100 illustrates the result in memory. Our llamas are properly fed and no longer go hungry.

_images/23_llama_pointers.svg

Figure 100 Storing pointers in a container.

By storing pointers in a container, we avoid making copies of the underlying objects.

Containers of pointers are also useful for keeping track of multiple orderings of the same objects. For instance, we may want to store our llamas both in order of age as well as alphabetically by name. The following code creates Llama objects in dynamic memory and stores pointers to them in two different lists:

int main() {
  List<Llama *> by_age;
  by_age.push_back(new Llama("Paul"));
  by_age.push_back(new Llama("Carl"));

  List<Llama *> by_name;
  by_name.push_back(by_age.back());
  by_name.push_back(by_age.front());
}

Figure 101 shows the resulting storage.

_images/23_containers_of_dynamic_objects.svg

Figure 101 Two containers that store pointers to the same objects.

The code above, however, has a memory leak; the destructors for the lists only free the memory for the Node objects, so the Llama objects do not get deleted. We need to manually delete them before the lists that we are using to track them go away:

int main() {
  List<Llama *> by_age;
  by_age.push_back(new Llama("Paul"));
  by_age.push_back(new Llama("Carl"));

  List<Llama *> by_name;
  by_name.push_back(by_age.back());
  by_name.push_back(by_age.front());

  for (auto llama : by_age) {
    delete llama;
  }

  for (auto llama : by_name) {
    delete llama;                // UNDEFINED BEHAVIOR
  }
}

This code is erroneous: it deletes each Llama object twice, resulting in undefined behavior. We need to be careful to avoid memory errors when we have multiple containers referring to the same dynamic objects. What we should do is designate one container as the canonical “owner” of the objects, only deleting them when that container is about to die:

int main() {
  List<Llama *> by_age;                  // "owner" of llama objects
  by_age.push_back(new Llama("Paul"));
  by_age.push_back(new Llama("Carl"));

  List<Llama *> by_name;
  by_name.push_back(by_age.back());
  by_name.push_back(by_age.front());

  for (auto llama : by_age) {  // delete llamas when by_age is dying
    delete llama;
  }
}

Alternatively, we can store the objects directly in the container that “owns” them, so that the destructor for the container does the work of reclaiming those objects:

int main() {
  List<Llama> by_age;                  // "owner" of llama objects
  by_age.push_back(Llama("Paul"));
  by_age.push_back(Llama("Carl"));

  List<Llama *> by_name;
  by_name.push_back(&by_age.back());
  by_name.push_back(&by_age.front());
}                     // llamas die automatically when by_age dies

Here, we construct the Llama objects as temporaries when passing them to push_back(). Standard-library containers have emplace_back() functions that avoid creating temporaries, and we pass the constructor arguments directly to that function:

int main() {
  List<Llama> by_age;                  // "owner" of llama objects
  by_age.emplace_back("Paul");
  by_age.emplace_back("Carl");

  List<Llama *> by_name;
  by_name.push_back(&by_age.back());
  by_name.push_back(&by_age.front());
}                     // llamas die automatically when by_age dies

The result in memory is shown in Figure 102.

_images/23_pointers_to_elements.svg

Figure 102 Storing pointers to elements of a different container.

The llamas die automatically when the container in which they reside dies, at the end of main() in the code above.

Sorting Containers of Pointers

The following code stores pointers to llamas in a container and then sorts them:

int main() {
  vector<Llama *> llamas = { new Llama("Paul"), new Llama("Carl") };
  std::sort(llamas.begin(), llamas.end());
  ...
}

While this code compiles, it sorts the pointers in the container by the address values they store, not by some property of the Llama objects. This is because std::sort() uses the < operator by default, which for pointers just compares the addresses they contain. The result depends on where the two Llama objects were placed in memory, which is implementation-dependent.

Instead, we need to supply our own comparator to std::sort(), and the comparator can use whatever property we choose of the underlying Llama objects:

class LlamaPointerNameLess {
public:
  bool operator()(const Llama *l1, const Llama *l2) const {
    return l1->get_name() < l2->get_name();
  }
};

Here, we have chosen to sort llamas by name. The comparator operates on pointers to Llamas, since that is what the container stores. We then call std::sort() as follows:

std::sort(llamas.begin(), llamas.end(), LlamaPointerNameLess());

The third argument is a default-constructed, temporary LlamaPointerNameLess object. Now std::sort() will use that to compare the Llama * elements, resulting in them being ordered by the names of the respective llamas.

We can use different comparators to maintain different orderings of the same objects:

vector<Llama> llamas = { Llama("Paul"), Llama("Carl") };

vector<Llama *> by_age;
for (auto &llama : llamas) {
  by_age.push_back(&llama);
}
std::sort(by_age.begin(), by_age.end(), LlamaPointerAgeLess());

vector<Llama *> by_name = by_age;
std::sort(by_name.begin(), by_name.end(), LlamaPointerNameLess());

Containers of Polymorphic Objects

Keeping track of polymorphic objects, meaning objects of different derived classes of the same base class, requires indirection as we saw previously. Containers of pointers enable this indirection:

int main() {
  vector<Animal *> zoo;
  zoo.push_back(new Gorilla("Colo"));
  zoo.push_back(new Llama("Paul"));
  zoo.push_back(new Panda("Po"));

  for (auto animal_ptr : zoo) {
    animal_ptr->talk();   // prints different messages for each animal
  }

  ...
}

As long as the talk() function is virtual, dynamic binding will be used, and each animal will print its own sound.

When we are done with the objects, we need to delete them ourselves, since they are in dynamic memory:

for (auto animal_ptr : zoo) {
  delete animal_ptr;
}

As we saw previously, this requires the Animal destructor to be declared as virtual so that dynamic binding is used to call the appropriate destructor for each object.