Hands-On High Performance Programming with Qt 5

Trees

Trees organize their elements in a hierarchical branched structure (hence the name) and are very good when we are searching for items. Due to their hierarchical organization, the search has the O(log n) complexity (assuming a well-balanced, nondegenerate tree). However, the same caveats as with lists apply—there are bad memory locality and dynamic allocations.

But the search times are very nice indeed. Could we keep them, somehow? Well, if we wanted to maintain this search speed, we could replace a tree structure with a sorted array, assuming we won't be changing it often. For a more general case, there is a Boost implementation of flat_map which projects the tree structure onto an array, preserving the hierarchies but improving the ...