11.3. Sorted Map Example

11.3. Sorted Map Example
	Chapter 11. Generics and Containers

[ 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.

Figure 11.3. TextbookMap

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

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;
}

More Than One Way to Traverse a Map

Another way to write the same method:

void TextbookMap::showAll() const {
    foreach (QString key, keys()) {
        Textbook* tb = value(key);
        cout << '[' << key << ']' << ":"
             << tb->toString() << endl;
    }
}

when you remove() a pointer from the TextbookMap you also remove its responsibility for managing that pointer.
By making use of QMap member functions (e.g., remove(), take(), etc.) client code can produce memory leaks.
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);
    {                              
        TextbookMap m;
        m.add(t1);
        m.add(t2);
        m.add(t3);
        m.add(t4);
        qDebug() << m.toString();
        m.remove (t3->getIsbn());  
    }                              
    qDebug() << "After m has been destroyed we still have:\n" 
        << t3->toString();
    return 0;
}

	Inner block for demonstration purposes
	Removed but not deleted
	End of block - local variables destroyed

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>


11.2.1. Exercises: Generics, Algorithms, and Operators		11.4. Function Pointers and Functors