11.3.  Sorted Map Example

[ fromfile: generics.xml id: sortedmapexample ]

As mentoned earlier, QMap is an associative array that maintains key sorting-order as items are added and removed. Key-based insertions and deletions are fast (log(n)) and iteration is done in key order.

QMap is a value container, but pointers are simple values, so you can use a QMap to store pointers to heap allocated QObjects. By default, however, value containers do not manage heap objects so, to avoid memory leaks, you must ensure they are deleted at the proper time. Figure 11.3 describes a class that extends a QMap to contain information about textbooks. By deriving from QMap, the entire public interface of QMap becomes part of the public interface of TextbookMap. We added only a destructor plus two convenience functions to facilitate adding and displaying Textbooks in the container. This convenience also creates some problems as you can see next.

Figure 11.3.  TextbookMap

TextbookMap

TextbookMap consists of <key,value> pairs with ISBN numbers as keys and Textbook pointers as values. Example 11.8 shows the class definitions.

Example 11.8. src/containers/qmap/textbook.h

#ifndef _TEXTBOOK_H_
#define _TEXTBOOK_H_

#include <QObject>
#include <QString>
#include <QMap>

class Textbook : public QObject {
    Q_OBJECT
  public:
    Textbook(QString title, QString author, QString isbn, uint year);
[ . . . . ]
private:
    QString m_Title, m_Author, m_Isbn;
    uint m_YearPub;
};

/* Managed collection of pointers */
class TextbookMap : public QMap<QString, Textbook*> {
  public:
    ~TextbookMap();
    void add(Textbook* text);
    QString toString() const;

};
#endif

<include src="src/containers/qmap/textbook.h" href="src/containers/qmap/textbook.h" id="textbookh" mode="cpp"/>


In Example 11.9, the destructor uses qDeleteAll() on the values() of the QMap, deleting each pointer. This is necessary for a value container to manage its objects.

Example 11.9. src/containers/qmap/qmap-example.cpp

[ . . . . ]

TextbookMap::~TextbookMap() {
    qDebug() << "Destroying TextbookMap ..." << endl;
    qDeleteAll(values());
    clear(); 
}

void TextbookMap::add(Textbook* text) {
    insert(text->getIsbn(), text);
}

QString TextbookMap::toString() const {
    QString retval;
    QTextStream os(&retval);
    ConstIterator itr = constBegin();
    for ( ; itr != constEnd(); ++itr)
        os << '[' << itr.key() << ']' << ": "
        << itr.value()->toString() << endl;
    return retval;
}

<include src="src/containers/qmap/qmap-example.cpp" mode="cpp" href="src/containers/qmap/qmap-example.cpp" id="qmapexamplecpp" segid="impl"/>


It is important to understand, as you can see in the client code shown in Example 11.10, that when you remove() a pointer from the TextbookMap you also remove its responsibility for managing that pointer. Once you remove it, you have the responsibility for deleting that pointer! In other words, client code can easily produce memory leaks. The same problem arises with other QMap member functions (e.g., QMap::erase() and QMap::take()). You can diminish these particular problems by hiding the dangerous QMap functions with TextbookMap versions that remove and delete or reparent no longer needed Textbook pointers. Another (perhaps safer) option would be to use private derivation instead of public derivation. Then the TextbookMap public interface would contain only safe public member functions that you (carefully) defined.

Example 11.10. src/containers/qmap/qmap-example.cpp

[ . . . . ]

int main() {
    Textbook* t1 = new Textbook("The C++ Programming Language",
        "Stroustrup", "0201700735", 1997);
    Textbook* t2 = new Textbook("XML in a Nutshell", 
        "Harold","0596002920", 2002);
    Textbook* t3 = new Textbook("UML Distilled", 
        "Fowler", "0321193687", 2004);
    Textbook* t4 = new Textbook("Design Patterns", "Gamma",
        "0201633612",1995);
    {                              1
        TextbookMap m;
        m.add(t1);
        m.add(t2);
        m.add(t3);
        m.add(t4);
        qDebug() << m.toString();
        m.remove (t3->getIsbn());  2
    }                              3
    qDebug() << "After m has been destroyed we still have:\n" 
        << t3->toString();
    return 0;
}

1

Inner block for demonstration purposes

2

Removed but not deleted

3

End of block - local variables destroyed

<include src="src/containers/qmap/qmap-example.cpp" mode="cpp" href="src/containers/qmap/qmap-example.cpp" id="qmapexampleclient" segid="client"/>


When TextbookMap::ShowAll() iterates through the container, you can see from the output in Example 11.11 that the Textbooks have been placed in order by ISBN (the key).

Example 11.11. src/containers/qmap/qmap-example-output.txt

src/containers/qmap> ./qmap
[0201633612]:Title: Design Patterns; Author: Gamma; ISBN: 0201633612;
Year: 1995
[0201700735]:Title: The C++ Programming Language; Author: Stroustrup;
ISBN: 0201700735; Year: 1997
[0321193687]:Title: UML Distilled; Author: Fowler; ISBN: 0321193687;
Year: 2004
[0596002920]:Title: XML in a Nutshell; Author: Harold; ISBN:
0596002920; Year: 2002
Destroying TextbookMap ...
After m has been destroyed we still have:
Title: UML Distilled; Author: Fowler; ISBN: 0321193687; Year: 2004
src/containers/qmap>

<include src="src/containers/qmap/qmap-example-output.txt" href="src/containers/qmap/qmap-example-output.txt" id="qmapexampleoutput" mode="text"/>