C++ Primer, Fifth Edition

Appearance

15.8. Containers and Inheritance

Fundamental

When we use a container to store objects from an inheritance hierarchy, we generally must store those objects indirectly. We cannot put objects of types related by inheritance directly into a container, because there is no way to define a container that holds elements of differing types.

As an example, assume we want to define a vector to hold several books that a customer wants to buy. It should be easy to see that we can’t use a vector that holds Bulk_quote objects. We can’t convert Quote objects to Bulk_quote (§15.2.3, p. 602), so we wouldn’t be able to put Quote objects into that vector.

It may be somewhat less obvious that we also can’t use a vector that holds objects of type Quote. In this case, we can put Bulk_quote objects into the container. However, those objects would no longer be Bulk_quote objects:

c++
vector<Quote> basket;
basket.push_back(Quote("0-201-82470-1", 50));
// ok, but copies only the Quote part of the object into basket
basket.push_back(Bulk_quote("0-201-54848-8", 50, 10, .25));
// calls version defined by Quote, prints 750, i.e., 15 * $50
cout << basket.back().net_price(15) << endl;

The elements in basket are Quote objects. When we add a Bulk_quote object to the vector its derived part is ignored (§15.2.3, p. 603).

WARNING

Because derived objects are “sliced down” when assigned to a base-type object, containers and types related by inheritance do not mix well.

Put (Smart) Pointers, Not Objects, in Containers

When we need a container that holds objects related by inheritance, we typically define the container to hold pointers (preferably smart pointers (§12.1, p. 450)) to the base class. As usual, the dynamic type of the object to which those pointers point might be the base-class type or a type derived from that base:

c++
vector<shared_ptr<Quote>> basket;
basket.push_back(make_shared<Quote>("0-201-82470-1", 50));
basket.push_back(
    make_shared<Bulk_quote>("0-201-54848-8", 50, 10, .25));
// calls the version defined by Quote; prints 562.5, i.e., 15 * $50 less the discount
cout << basket.back()->net_price(15) << endl;

Because basket holds shared_ptrs, we must dereference the value returned by basket.back() to get the object on which to run net_price. We do so by using -> in the call to net_price. As usual, the version of net_price that is called depends on the dynamic type of the object to which that pointer points.

It is worth noting that we defined basket as shared_ptr<Quote>, yet in the second push_back we passed a shared_ptr to a Bulk_quote object. Just as we can convert an ordinary pointer to a derived type to a pointer to an base-class type (§15.2.2, p. 597), we can also convert a smart pointer to a derived type to a smart pointer to an base-class type. Thus, make_shared<Bulk_quote> returns a shared_ptr<Bulk_quote> object, which is converted to shared_ptr<Quote> when we call push_back. As a result, despite appearances, all of the elements of basket have the same type.

INFO

Exercises Section 15.8

Exercise 15.28: Define a vector to hold Quote objects but put Bulk_quote objects into that vector. Compute the total net_price of all the elements in the vector.

Exercise 15.29: Repeat your program, but this time store shared_ptrs to objects of type Quote. Explain any discrepancy in the sum generated by the this version and the previous program. If there is no discrepancy, explain why there isn’t one.

15.8.1. Writing a Basket Class

Advanced

One of the ironies of object-oriented programming in C++ is that we cannot use objects directly to support it. Instead, we must use pointers and references. Because pointers impose complexity on our programs, we often define auxiliary classes to help manage that complexity. We’ll start by defining a class to represent a basket:

c++
class Basket {
public:
    // Basket uses synthesized default constructor and copy-control members
    void add_item(const std::shared_ptr<Quote> &sale)
        { items.insert(sale); }
    // prints the total price for each book and the overall total for all items in the basket
    double total_receipt(std::ostream&) const;
private:
    // function to compare shared_ptrs needed by the multiset member
    static bool compare(const std::shared_ptr<Quote> &lhs,
                        const std::shared_ptr<Quote> &rhs)
    { return lhs->isbn() < rhs->isbn(); }
    // multiset to hold multiple quotes, ordered by the compare member
    std::multiset<std::shared_ptr<Quote>, decltype(compare)*>
                  items{compare};
};

Our class uses a multiset (§11.2.1, p. 423) to hold the transactions, so that we can store multiple transactions for the same book, and so that all the transactions for a given book will be kept together (§11.2.2, p. 424).

The elements in our multiset are shared_ptrs and there is no less-than operator for shared_ptr. As a result, we must provide our own comparison operation to order the elements (§11.2.2, p. 425). Here, we define a private static member, named compare, that compares the isbns of the objects to which the shared_ptrs point. We initialize our multiset to use this comparison function through an in-class initializer (§7.3.1, p. 274):

c++
// multiset to hold multiple quotes, ordered by the compare member
std::multiset<std::shared_ptr<Quote>, decltype(compare)*>
              items{compare};

This declaration can be hard to read, but reading from left to right, we see that we are defining a multiset of shared_ptrs to Quote objects. The multiset will use a function with the same type as our compare member to order the elements. The multiset member is named items, and we’re initializing items to use our compare function.

Defining the Members of Basket

The Basket class defines only two operations. We defined the add_item member inside the class. That member takes a shared_ptr to a dynamically allocated Quote and puts that shared_ptr into the multiset. The second member, total_receipt, prints an itemized bill for the contents of the basket and returns the price for all the items in the basket:

c++
double Basket::total_receipt(ostream &os) const
{
    double sum = 0.0;   // holds the running total
    // iter refers to the first element in a batch of elements with the same ISBN
    // upper_bound returns an iterator to the element just past the end of that batch
    for (auto iter = items.cbegin();
              iter != items.cend();
              iter = items.upper_bound(*iter)) {
        // we know there's at least one element with this key in the Basket
        // print the line item for this book
        sum += print_total(os, **iter, items.count(*iter));
    }
    os << "Total Sale: " << sum << endl; // print the final overall total
    return sum;
}

Our for loop starts by defining and initializing iter to refer to the first element in the multiset. The condition checks whether iter is equal to items.cend(). If so, we’ve processed all the purchases and we drop out of the for. Otherwise, we process the next book.

The interesting bit is the “increment” expression in the for. Rather than the usual loop that reads each element, we advance iter to refer to the next key. We skip over all the elements that match the current key by calling upper_bound (§11.3.5, p. 438). The call to upper_bound returns the iterator that refers to the element just past the last one with the same key as in iter. The iterator we get back denotes either the end of the set or the next book.

Inside the for loop, we call print_total (§15.1, p. 593) to print the details for each book in the basket:

c++
sum += print_total(os, **iter, items.count(*iter));

The arguments to print_total are an ostream on which to write, a Quote object to process, and a count. When we dereference iter, we get a shared_ptrthat points to the object we want to print. To get that object, we must dereference that shared_ptr. Thus, **iter is a Quote object (or an object of a type derived from Quote). We use the multiset count member (§11.3.5, p. 436) to determine how many elements in the multiset have the same key (i.e., the same ISBN).

As we’ve seen, print_total makes a virtual call to net_price, so the resulting price depends on the dynamic type of **iter. The print_total function prints the total for the given book and returns the total price that it calculated. We add that result into sum, which we print after we complete the for loop.

Hiding the Pointers

Users of Basket still have to deal with dynamic memory, because add_item takes a shared_ptr. As a result, users have to write code such as

c++
Basket bsk;
bsk.add_item(make_shared<Quote>("123", 45));
bsk.add_item(make_shared<Bulk_quote>("345", 45, 3, .15));

Our next step will be to redefine add_item so that it takes a Quote object instead of a shared_ptr. This new version of add_item will handle the memory allocation so that our users no longer need to do so. We’ll define two versions, one that will copy its given object and the other that will move from it (§13.6.3, p. 544):

c++
void add_item(const Quote& sale);  // copy the given object
void add_item(Quote&& sale);       // move the given object

The only problem is that add_item doesn’t know what type to allocate. When it does its memory allocation, add_item will copy (or move) its sale parameter. Somewhere there will be a new expression such as:

c++
new Quote(sale)

Unfortunately, this expression won’t do the right thing: new allocates an object of the type we request. This expression allocates an object of type Quote and copies the Quote portion of sale. However, sale might refer to a Bulk_quote object, in which case, that object will be sliced down.

Simulating Virtual Copy
Tricky

We’ll solve this problem by giving our Quote classes a virtual member that allocates a copy of itself.

c++
class Quote {
public:
    // virtual function to return a dynamically allocated copy of itself
    // these members use reference qualifiers; see §13.6.3 (p. 546)
    virtual Quote* clone() const & {return new Quote(*this);}
    virtual Quote* clone() &&
                        {return new Quote(std::move(*this));}
    // other members as before
};
class Bulk_quote : public Quote {
    Bulk_quote* clone() const & {return new Bulk_quote(*this);}
    Bulk_quote* clone() &&
                   {return new Bulk_quote(std::move(*this));}
    // other members as before
};

Because we have a copy and a move version of add_item, we defined lvalue and rvalue versions of clone (§13.6.3, p. 546). Each clone function allocates a new object of its own type. The const lvalue reference member copies itself into that newly allocated object; the rvalue reference member moves its own data.

Using clone, it is easy to write our new versions of add_item:

c++
class Basket {
public:
    void add_item(const Quote& sale) // copy the given object
      { items.insert(std::shared_ptr<Quote>(sale.clone())); }
    void add_item(Quote&& sale)      // move the given object
      { items.insert(
          std::shared_ptr<Quote>(std::move(sale).clone())); }
    // other members as before
};

Like add_item itself, clone is overloaded based on whether it is called on an lvalue or an rvalue. Thus, the first version of add_item calls the const lvalue version of clone, and the second version calls the rvalue reference version. Note that in the rvalue version, although the type of sale is an rvalue reference type, sale (like any other variable) is an lvalue (§13.6.1, p. 533). Therefore, we call move to bind an rvalue reference to sale.

Our clone function is also virtual. Whether the Quote or Bulk_quote function is run, depends (as usual) on the dynamic type of sale. Regardless of whether we copy or move the data, clone returns a pointer to a newly allocated object, of its own type. We bind a shared_ptr to that object and call insert to add this newly allocated object to items. Note that because shared_ptr supports the derived-to-base conversion (§15.2.2, p. 597), we can bind a shared_ptr<Quote to a Bulk_quote*.

INFO

Exercises Section 15.8.1

Exercise 15.30: Write your own version of the Basket class and use it to compute prices for the same transactions as you used in the previous exercises.