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?
Steveire's Blog 