6.10. Containers of Pointers

6.10. Containers of Pointers
	Chapter 6. Inheritance and Polymorphism

[ fromfile: inheritance-intro.xml id: containersofpointers ]

In Section 1.15.1 you saw that all pointers are the same (small) size. That is just one of the reasons that you should prefer to work with containers of pointers rather than containers of objects. In the remaining parts of this book, many of the classes that you will use are members of inheritance trees – especially the classes used for GUI programming. As you saw in several examples in this chapter, a base class pointer can hold the address of a derived object. So, a container of base class pointers can hold addresses of any derived objects. Polymorphism then enables the appropriate functions to get called through these pointers at runtime. To use polymorphism there must be a prototype in the base class for each function that you may want to call - even if it cannot be defined in the base class. That is why pure virtual functions are sometimes needed. The base class provides the interface that can work with the concrete, derived objects.

Containers of pointers require careful destruction procedures to avoid memory leaks. Also, access to and maintenance of the pointers must be carefully controlled so that no attempt to dereference a null or undefined pointer is ever made. This is not as difficult as it might sound.

When you add a pointer to the container, make sure that it is initialized immediately. If that is not possible it should be assigned a value of 0.
When an individual pointer is no longer needed, remove it and delete it. If immediate removal is not convenient for some reason, the deleted pointer should be reassigned or set to 0.
When it is time to destroy a Qt container of pointers, call qDeleteAll().
- qDeleteAll() is a generic algorithm that works with all Qt container classes.
- Each specific Qt container class has its own clear() member function.

Copies, Copies, Copies

Using pointers gives rise to another important issue, which is magnified when working with containers of pointers. Always keep in mind that bad things can happen if you allow an object that contains pointers to be copied. One almost guaranteed recipe for disaster is letting the compiler supply the copy constructor and the copy assignment operator, both of which simply duplicate the host object's pointers. With that approach, if a container of pointers (or an object with a pointer member) were passed as an argument for a value parameter in a function call, the function would have a local copy of that object that would be destroyed when it returned. Assuming that the destructor properly deleted the pointers, the original object would then contain one or more pointers to deleted memory, leading to the kind of memory corruption that is notoriously difficult to trace.

One way to avoid that problem is to make sure that the copy constructor and the copy assignment operator each make a deep copy of the host object; i.e., pointers in the new copy address new memory that contains exact copies of the data addressed by the host object's pointers. Unfortunately, this approach can be prohibitively expensive in terms of system resources and is generally avoided. Section 11.5 discusses a more efficient approach that uses resource sharing.

The QObject class mentioned earlier, which can possess a container of pointers, deals with this issue by having a private copy constructor and a private copy assignment operator so that any attempt to make a copy would result in a compile error. ^[50]

In Chapter 8 and subsequent chapters, there are several opportunities to work with containers of various types of pointers. There you will work with containers of QObject pointers that can hold the addresses of an enormous variety of objects, including all the "widgets" that you will use for Graphical User Interfaces. In Chapter 9, when you write GUI programs using many different kinds of widgets and layouts, all of which are QObjects, containers of base class pointers play a crucial role.

Extended Example: A Simple Library.

For the purposes of this example, we regard a library as a collection of various kinds of reference materials. First, we define classes to implement a simplified library as suggested by the abbreviated UML diagram in Figure 6.8.

Figure 6.8. Reference Library UML Diagram

The base class definition is shown in Example 6.30. Because all its constructors are protected, no RefItem object can be constructed by client code. Thus, RefItem is an abstract base class.

Example 6.30. src/pointer-container/library.h

[ . . . . ]
                                                                                           
class RefItem {                                                                              
public:   
   virtual ~RefItem();
   QString getItemType() const;
   QString getISBN() const;
   QString getTitle() const;
   int getNumberOfCopies() const;
   virtual QString toString(QString sep="[::]") const;
   void setNumberOfCopies(int newVal);
protected:
   RefItem(QString type, QString isbn, QString title, int numCopies=1);
   RefItem(QStringList& proplist);
private:                                                                                     
   QString m_ItemType, m_ISBN, m_Title;
   int m_NumberOfCopies;
};

Example 6.31 shows a few derived class definitions. The base class and each of the derived classes has a constructor that takes a single QStringList reference parameter. This greatly simplifies and facilitates the creation of objects when reading data from a file or taking information from the user. RefCategory, an enum type defined publicly within ReferenceBook, is intended to enumerate categories such as Literature, Music, Math, Science, Art, Architecture, etc. There are no I/O operations in any of these classes. For this example, all I/O is handled by client code, leaving improvements as exercises for you.

Example 6.31. src/pointer-container/library.h

[ . . . . ]

class Book : public RefItem {
public:
   Book(QString type, QString isbn, QString title, QString author, 
        QString pub, int year, int numCopies=1);
   Book(QStringList& proplist);
   virtual QString toString(QString sep="[::]") const;
   QString getAuthor() const;
   QString getPublisher() const;
   int getCopyrightYear() const;
private:
   QString m_Author, m_Publisher;
   int m_CopyrightYear;
};

class ReferenceBook : public Book {
public:
   enum RefCategory {NONE = -1, Art, Architecture, ComputerScience,
                     Literature, Math, Music, Science};
   ReferenceBook(QString type, QString isbn, QString title, 
                 QString author, QString pub, int year, 
                 RefCategory refcat, int numCopies=1);
   ReferenceBook(QStringList& proplist);
   QString toString(QString sep="[::]") const;
   RefCategory getCategory() const;
   QString categoryString() const;         
   static QStringList getRefCategories();  
private:
   RefCategory m_Category;
};

	Returns string version of m_Category.
	Returns a list of categories.

Much of the implementation code is quite routine and need not be displayed here. We focus instead on the techniques we use to facilitate transmitting and receiving data. Because that can happen in a variety of ways (e.g., to/from files, across networks), we provide two kinds of conversions: Object to QString and QStringList to Object. Specific details regarding I/O are kept outside of these classes. Example 6.32 shows the first of these conversions.

Example 6.32. src/pointer-container/library.cpp

[ . . . . ]

QString RefItem::toString(QString sep) const {
   return
   QString("%1%2%3%4%5%6%7").arg(m_ItemType).arg(sep).arg(m_ISBN)
                            .arg(sep).arg(m_Title).arg(sep)
                            .arg(m_NumberOfCopies);
}
[ . . . . ]

QString Book::toString(QString sep) const {
   return QString("%1%2%3%4%5%6%7").arg(RefItem::toString(sep))
               .arg(sep).arg(m_Author).arg(sep).arg(m_Publisher)
               .arg(sep).arg(m_CopyrightYear);
}
[ . . . . ]

QString ReferenceBook::toString(QString sep) const {
   return QString("%1%2%3").arg(Book::toString(sep)).arg(sep)
                          .arg(categoryString());
}
[ . . . . ]

QString ReferenceBook::categoryString() const {
   switch(m_Category) {
     case Art: return "Art";
     case Architecture: return "Architecture";
     case ComputerScience: return "ComputerScience";
     case Literature: return "Literature";
     case Math: return "Math";
     case Music: return "Music";
     case Science: return "Science";
   default: return "None";
   }
}

QString provides a convenient way to transmit data. If a QString consists of several pieces of data and has been carefully put together, it can easily be repackaged as a QStringList using the function, QString::split(QString separator). In this example, the order of data items and the separator are determined by the toString(QString sep) functions. Make a careful study of Example 6.33 and think carefully about the use of a non-const reference parameter in each constructor. Everything happens in the member initialization lists.

Example 6.33. src/pointer-container/library.cpp

[ . . . . ]

RefItem::RefItem(QStringList& plst) : m_ItemType(plst.takeFirst()), 
         m_ISBN(plst.takeFirst()), m_Title(plst.takeFirst()),
         m_NumberOfCopies(plst.takeFirst().toInt()) 
{ }
[ . . . . ]

Book::Book(QStringList& plst) : RefItem(plst), 
      m_Author(plst.takeFirst()), m_Publisher(plst.takeFirst()),
      m_CopyrightYear(plst.takeFirst().toInt())
{ }
[ . . . . ]

ReferenceBook::ReferenceBook(QStringList& plst) : Book(plst), 
     m_Category(static_cast<RefCategory>(plst.takeFirst().toInt()))
{ }

Example 6.34 shows the class definition for Library. Because Library is publicly derived from QList<RefItem*> it is a container of pointers. The copy constructor and copy assignment operator are private. That prevents the compiler from supplying public versions (the recipe for disaster that mentioned earlier) and, hence, guarantees that no copies can be made of a Library object. It also prevents the compiler from supplying a default constructor, so we must provide one.

Example 6.34. src/pointer-container/library.h

[ . . . . ]

class Library : public QList<RefItem*> {
public:
   Library() {}
   ~Library();                             
   void addRefItem(RefItem*& refitem);
   int removeRefItem(QString isbn);
   QString toString(QString sep="\n") const;
   bool isInList(QString isbn);
   QString getItemString(QString isbn);
private:
   Library(const Library&);
   Library& operator=(const Library&);
   RefItem* findRefItem(QString isbn);
};

A container of pointers must have a destructor!

The implementations of the Library class member functions are listed next. The first chunk, in Example 6.35, shows the implementations of the copy constructor and the copy assignment operator and also how to add and remove items from the Library. The copy constructor and copy assignment operator will never be used, but we supplied just enough implementation to prevent the compiler from issuing warnings about not initializing the base class in the constructor or not returning anything in the assignment operator.

Before adding an item to the list, check to see if it is already there. If the item is already in the list, simply increment its m_NumberOfCopies. To remove an item, decrement its m_NumberOfCopies. If the result of decrementing is zero, remove it from the list and delete the pointer.^[51]

Example 6.35. src/pointer-container/library.cpp

[ . . . . ]

Library::~Library() {
   qDeleteAll(*this);
   clear();
}

Library::Library(const Library&) : QList<RefItem*>() {}

Library& Library::operator=(const Library&) {
   return *this;
}

void Library::addRefItem(RefItem*& refitem) { 
   QString isbn(refitem->getISBN());
   RefItem* oldItem(findRefItem(isbn));
   if(oldItem==0)
      append(refitem);
   else {
      qDebug() << isbn << " Already in list:\n"
               << oldItem->toString()
               << "\nIncreasing number of copies " 
               << "and deleting new pointer." ;
      int newNum(oldItem->getNumberOfCopies() + refitem->getNumberOfCopies());
      oldItem->setNumberOfCopies(newNum);
      delete refitem;                         
      refitem = 0;                             
   }
}

int Library::removeRefItem(QString isbn) {
   RefItem* ref(findRefItem(isbn));
   int numCopies(-1);
   if(ref) {
      numCopies = ref->getNumberOfCopies() - 1;
      if(numCopies== 0) {
         removeAll(ref);
         delete ref;
      }
      else
         ref->setNumberOfCopies(numCopies);
   }
   return numCopies;
}

	Parameter is a pointer reference so that null assignment after delete is possible.
	Not in a managed container.
	Reference parameter!

For a more realistic application, Library and the RefItem classes would need more data and function members. Example 6.36 provides a few more Library member functions for inspiration. Library::findRefItem() is private because it returns a pointer and, as mentioned earlier, it is generally not a good idea to let client code work with pointers.

Example 6.36. src/pointer-container/library.cpp

[ . . . . ]


RefItem* Library::findRefItem(QString isbn) {
   for(int i = 0; i < size(); ++i) {
      if(at(i)->getISBN().trimmed() == isbn.trimmed())
         return at(i);
   }
   return 0;
}


bool Library::isInList(QString isbn) {
   return findRefItem(isbn);
}

QString Library::toString(QString sep) const {
   QStringList reflst;
   for(int i = 0; i < size(); ++i)
      reflst << at(i)->toString();
   return reflst.join(sep);
}

QString Library::getItemString(QString isbn) {
   RefItem* ref(findRefItem(isbn));
   if(ref)
      return ref->toString();
   else
      return QString();
}

	Note
	We did not have the option to use the `foreach()` macro in the implementations of `Library::findRefItem()` and `Library::toString()` because the `foreach()` macro needs to make a copy of the container that it traverses. Because the copy constructor is private, that is not possible. Keep this in mind when you work with QObjects in later chapters.

We wrote some client code to test these classes. Because we are using standard I/O, we introduced some enums to make it easier to set up a menu system, as you see in Example 6.37.

Example 6.37. src/pointer-container/libraryClient.cpp

[ . . . . ]

QTextStream cout(stdout);
QTextStream cin(stdin);
enum Choices {READ=1, ADD, FIND, REMOVE, SAVE, LIST, QUIT};
enum Types {BOOK, REFERENCEBOOK, TEXTBOOK, DVD, FILM, DATADVD};
const QStringList TYPES = (QStringList() << "BOOK" << "REFERENCEBOOK"
   << "TEXTBOOK" << "DVD" << "FILM" << "DATADVD");
bool saved(false);

Example 6.38 shows how the enums can be used.

Example 6.38. src/pointer-container/libraryClient.cpp

[ . . . . ]

Choices nextTask() {
   int choice;
   QString response;
   do {
      cout << READ << ". Read data from a file.\n"
           << ADD << ". Add items to the Library.\n"
           << FIND << ". Find and display an item.\n"
           << REMOVE << ". Remove an item from the Library.\n"
           << SAVE << ". Save the Library list to a file.\n"
           << LIST << ". Brief listing of Library items.\n"
           << QUIT << ". Exit from this program.\n"
           << "Your choice: " << flush;
     response = cin.readLine();
     choice = response.toInt();
   } while(choice < READ or choice > QUIT);
   return static_cast<Choices>(choice);
}

void add(Library& lib, QStringList objdata) {
   cout << objdata.join("[::]") << endl;
   QString type = objdata.first();
   RefItem* ref;
   switch(static_cast<Types>(TYPES.indexOf(type))) {
   case BOOK: 
      ref = new Book(objdata);
      lib.addRefItem(ref);
      break;
   case REFERENCEBOOK: 
      ref = new ReferenceBook(objdata);
      lib.addRefItem(ref);
         break;
[ . . . . ]

   default: qDebug() << "Bad type in add() function";
   }
}

You see in Example 6.39 how simple it is to save data to a file.

Example 6.39. src/pointer-container/libraryClient.cpp

[ . . . . ]

void save(Library& lib) {
   QFile outf("libfile");
   outf.open(QIODevice::WriteOnly);
   QTextStream outstr(&outf);
   outstr << lib.toString();
   outf.close();
}

In Example 6.40 we read data from a file, one line at a time. This approach works only if Library::toString() uses the newline character to separate one object's data from the next.

Example 6.40. src/pointer-container/libraryClient.cpp

[ . . . . ]

void read(Library& lib) {
   const QString sep("[::]");
   const int BADLIMIT(5); //max number of bad lines
   QString line, type;
   QStringList objdata;
   QFile inf("libfile");
   inf.open(QIODevice::ReadOnly);
   QTextStream instr(&inf);
   int badlines(0);
   while(not instr.atEnd()) {
      if(badlines >= BADLIMIT) {
         qDebug() << "Too many bad lines! Aborting.";
         return;
      }
      line = instr.readLine();
      objdata = line.split(sep);
      if(objdata.isEmpty()) {
         qDebug() << "Empty Line in file!";
         ++badlines;
      }
      else if(not TYPES.contains(objdata.first())) {
         qDebug() << "Bad type in line: " << objdata.join(";;;");
         ++badlines;
      }
      else
         add(lib, objdata);
    }
}

Getting data from the keyboard is necessarily more complicated because each individual data item must be requested and, where possible, validated. In the client code, shown in Example 6.41, we have a prompt function for each RefItem class that returns a QStringList we can then pass along to the appropriate constructor for that class.

Example 6.41. src/pointer-container/libraryClient.cpp

[ . . . . ]

QStringList promptRefItem() {
   const int MAXCOPIES(10);
   const int ISBNLEN(13);
   int copies;
   QString str;
   QStringList retval;
   while(1) {
      cout << "ISBN ("<< ISBNLEN << " digits): " << flush;
      str = cin.readLine();
      if(str.length() == ISBNLEN) {
         retval << str;
         break;
      }
   }
   cout << "Title: " << flush;
   retval << cin.readLine();
   while(1) {
      cout << "Number of copies: " << flush;
      copies = cin.readLine().toInt();
      if(copies > 0 and copies <= MAXCOPIES) {
         str.setNum(copies);
         break;
      }
   }
   retval << str;
   return retval;
}

QStringList promptBook() {
   static const int MINYEAR(1900), 
                    MAXYEAR(QDate::currentDate().year());
   int year;
   QStringList retval(promptRefItem());
   QString str;
   cout << "Author: " << flush;
   retval << cin.readLine();
   cout << "Publisher: " << flush;
   retval << cin.readLine();
   while(1) {
      cout << "Copyright year: " << flush;
      year = cin.readLine().toInt();
      if(year >= MINYEAR and year <= MAXYEAR) {
         str.setNum(year);
         break;
      }
   }
   retval << str;
   return retval;
}

QStringList promptReferenceBook() {
   int idx(0);
   bool ok;
   QString str;
   QStringList retval(promptBook());
   QStringList cats(ReferenceBook::getRefCategories());
   while(1) {
      cout << "Enter the index of the correct Reference Category: ";
      for(int i = 0; i < cats.size(); ++i)
         cout << "\n\t(" << i << ") " << cats.at(i);
      cout << "\n\t(-1)None of these\t:::" << flush;
      idx = cin.readLine().toInt(&ok);
      if(ok) {
         retval << str.setNum(idx);
         break;
      }
   }
   return retval;
}
[ . . . . ]

void enterData(Library& lib) {
   QString typestr;
   while(1) {
      cout << "Library item type: " << flush;
      typestr = cin.readLine();
      if(not TYPES.contains(typestr)) {
         cout << "Please enter one of the following types:\n"
              << TYPES.join(" ,") << endl;
         continue;
      }
      break;
   }
   QStringList objdata;
   switch (TYPES.indexOf(typestr)) {
   case BOOK: objdata = promptBook();
         break;
   case REFERENCEBOOK: objdata = promptReferenceBook();
         break;
[ . . . . ]

   default:
         qDebug() << "Bad type in enterData()";
   }
   objdata.prepend(typestr);
   add(lib, objdata);
}

The main() function is shown in Example 6.42.

Example 6.42. src/pointer-container/libraryClient.cpp

[ . . . . ]

int main() {
   Library lib;
   while(1) {
      switch(nextTask()) {
      case READ: read(lib);
         saved = false;
         break;
      case ADD: enterData(lib);
         saved = false;
         break;
      case FIND: find(lib);
         break;
      case REMOVE: remove(lib);
         saved = false;
         break;
      case SAVE: save(lib);
         saved = true;
         break;
      case LIST: list(lib);
         break;
      case QUIT: prepareToQuit(lib);
         break;
      default:
         break;
      }
   }
}

You can refine and improve this application in Section 6.10.1.

^[50]Section 8.1

^[51]Why not delete first and then remove?


6.9.1. Exercises: Managed Containers, Composites and Aggregates		6.10.1. Exercises: Containers of Pointers