KBiAssociativeContainer. Erm, huh?

What?

A while ago I wrote the KBiHash for encapsulating the content of two symmetrically updated QHash containers. The motivation for it was to be able to implement mapToSource and mapFromSource in proxy models sanely. By maintaining a mapping from parents in the source model to indexes in the proxy model, it was fairly clear how to map from one to the other.

It turns out it’s not so simple though. Sometimes I want a QHash on one side and a QMap on the other. I didn’t want to just copy, paste and replace QHash with QMap, so I made KBiHash even more generic to allow you to specify the associative container to use for each direction of the mapping.

That way, it is possible to use the same class to implement bi-directional QMap, bi-directional QHash, and QHash->QMap relations.

Why?

It turns out that mappings in proxy models are not always simple. If the purpose of the proxy is to change the structure of the model, there needs to be some way to quickly find the mapping closest to what you’re looking for.

What is the first number above 17 in this list:

(5, 20, 34, 12, 1, 7, 6, 21, 3, 19)

How did you find it? You looked left to right keeping track of the lowest number found so far which is greater than 17. Try again:

What is the first number above 13 in the sorted list:

(1, 3, 5, 6, 7, 12, 19, 20, 21, 34)

How did you find it? You might have looked first somewhere in the middle, see if that’s above or below 13, and then known whether to keep looking left or right. When you found it, you didn’t have to keep looking through the rest of the list because you knew all the numbers to the right are larger. When computers do this kind of thing, the first one is called linear search, and the second one is called binary search. Binary search is far faster, particularly on large lists, but only works if the list is sorted.

This is a problem I hit while writing KDescendantsProxyModel. That proxy maintains a mapping of the last item in the list in the source model to the row that item appears in in the proxy model. However, the mapToSource method also has to be able to map between intermediate items too.

KDescendantProxyModel maintains mappings to flatten a tree.

For example, if trying to map the row “8” from the proxy to the source, I need to know that the closest row below it which has a mapping is row “10”.

When mapping a row to the source, the proxy requires the first mapping that appears below the target row. To find that mapping in a QHash or KBiHash is always O(N). You have to look through each mapped row to see if it is the one closest to the target. The reason for that is that items in a QHash are accessible only in an unordered way. Items in a QMap are stored in sorted order though, which means that a computer can use a binary search algorithm, upperBound to find the mapping closest to the target, but above it. The complexity of that operation in a QMap is O(log N) in the worst case and average case, which is far faster. By storing the row numbers as keys in a QMap the speed of mapping to the source model is far faster.

How?

KBiHash was already a template class, just like QHash and QMap, but the logical leap was to make the template arguments to the class be not the key_type and mapped_type of the container, but the containers themselves.


class KBiAssociativeContainer<LeftC, RightC>
{
typedef RightC::mapped_type left_type;
typedef LeftC::mapped_type right_type;

void insert(left_type t, right_type u)
{
_leftToRight.insert(t, u);
_rightToLeft.insert(u, t);
}

private:
LeftC _leftToRight;
RightC _rightToLeft
};

Because both QMap and QHash contain typedefs for their key_type and map_type, have the same API for insert and lookup, and the same nested classes for iteration, both of those classes can be used in KBiAssociativeContainer. If Qt gets another new associative container in the future, that will work too if it has the same API. Those reading closely will notice that KBiAssociativeContainer is an associative container, but it doesn’t meet the static polymorphism requirements to be used in a KBiAssociativeContainer itself. That wouldn’t provide any benefit anyway.

KHash2Map provides fast bounds checking on elements on the right.

KBiHash and KHash2Map then becomes simple subclasses of KBiAssociativeContainer, ready to use.


template<typename T, typename U>
class KBiHash
: KBiAssociativeContainer <QHash<T, U>, QHash<U, T> >
{
};

template<typename T, typename U>
class KHash2Map
: KBiAssociativeContainer <QHash<T, U>, QMap<U, T> >
{
};

Where?

The code is in kdeui KDE SVN as private API.

Exercises for the reader

Why are the typedefs in the class flipped around? Why doesn’t the class use something like


typedef LeftContainer::key_type left_type;
typedef RightContainer::key_type right_type;

KSelectionProxyModel maintains mappings of parents, and of first child items in the list. Why does KDescendantsProxyModel maintain a mapping to the last items in the source lists instead?

9 Responses to “KBiAssociativeContainer. Erm, huh?”

  1. Thorsten Zachmann Says:

    You should have a look at boost multi_index http://www.boost.org/doc/libs/1_43_0/libs/multi_index/doc/index.html . It offers functionality like above with some benefits like not storing the data twice.

  2. steveire Says:

    Thanks for the pointer. I forgot to mention boost::multiindex in the blog. I only discovered it after I wrote the class actually. It’s something I should look into indeed.

  3. André Says:

    Having to specify the types inside the inner stores twice is not very nice API. This can be solved way more elegant, where you would end up with an API that you could use like this:

    KBiAssociativeContainer // results in using two QHash-es being used internally
    KBiAssociativeContainer // results in using two QMapss being used internally, or, equaly valid API choice, a QMap and a QHash.
    KBiAssociativeContainer // results in using two QMaps being used internally

    That is, you can make the container types to be used optional arguments for the template. There are a few good template books out there that tell you all about this kind of tricks.

    In Boost, you can find this kind of thing being used. For instance in Boost::Graph.

    Still, I think Thorstens comment is important: that class in Boost is much more efficient for storing large sets, where containers like these are most important. Either look at how they did it, and implement that yourself, or perhaps you could make KBiAssociativeContainer just a thin wrapper around the Boost::multi_index class to make the API more Qt-ish.

    • André Says:

      Everything between angled brackets has disapeared from my comment… Hmmm…

      • steveire Says:

        I would be interested if you could post those lines again. Post with round brackets maybe? KBiAssociativeContainer(T, U).

    • André Says:

      KBiAssociativeContainer [T, U] // results in using two QHash-es being used internally (so using QHash as a default)
      KBiAssociativeContainer [T, U, QMap] // results in using two QMapss being used internally, or, equaly valid API choice, a QMap and a QHash.
      KBiAssociativeContainer [T, U, QMap, QMap] // results in using two QMaps being used internally

      Replace the square brackets [] by angled ones

      • steveire Says:

        Ah I see. Actually I tried that and couldn’t make it work. I guess I should get a book on this stuff.

        Thanks for the feedback.

      • André Says:

        Google for template template parameters as a starter. I don’t have access to my books on this at the moment, sorry.

  4. azrdev Says:

    Would you mind proposing this for inclusion into Qt? The library is IMHO still very basic in terms of useful containers.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: