This section describes what problems the library attempts to solve. Motivation describes the reasons we think it solves these problems better than similar libraries.

Associative Containers

  1. Associative containers depend on their policies to a very large extent. Implicitly hard-wiring policies can hamper their performance and limit their functionality. An efficient hash-based container, for example, requires policies for testing key equivalence, hashing keys, translating hash values into positions within the hash table, and determining when and how to resize the table internally. A tree-based container can efficiently support order statistics, i.e., the ability to query what is the order of each key within the sequence of keys in the container, but only if the container is supplied with a policy to internally update meta-data. There are many other such examples.

  2. Ideally, all associative containers would share the same interface. Unfortunately, underlying data structures and mapping semantics differentiate between different containers. For example, suppose one writes a generic function manipulating an associative container Cntnr:
    template<typename Cntnr>
      some_op_sequence(Cntnr& r_cnt)
    then what can one assume about Cntnr? The answer varies according to its underlying data structure. If the underlying data structure of Cntnr is based on a tree or trie, then the order of elements is well defined; otherwise, it is not, in general. If the underlying data structure of Cntnr is based on a collision-chaining hash table, then modifying r_Cntnr will not invalidate its iterators' order; if the underlying data structure is a probing hash table, then this is not the case. If the underlying data structure is based on a tree or trie, then r_cnt can efficiently be split; otherwise, it cannot, in general. If the underlying data structure is a red-black tree, then splitting r_cnt is exception-free; if it is an ordered-vector tree, exceptions can be thrown.

Priority Queues

Priority queues are useful when one needs to efficiently access a minimum (or maximum) value as the set of values changes.

  1. Most useful data structures for priority queues have a relatively simple structure, as they are geared toward relatively simple requirements. Unfortunately, these structures do not support access to an arbitrary value, which turns out to be necessary in many algorithms. Say, decreasing an arbitrary value in a graph algorithm. Therefore, some extra mechanism is necessary and must be invented for accessing arbitrary values. There are at least two alternatives: embedding an associative container in a priority queue, or allowing cross-referencing through iterators. The first solution adds significant overhead; the second solution requires a precise definition of iterator invalidation. Which is the next point...

  2. Priority queues, like hash-based containers, store values in an order that is meaningless and undefined externally. For example, a push operation can internally reorganize the values. Because of this characteristic, describing a priority queues' iterator is difficult: on one hand, the values to which iterators point can remain valid, but on the other, the logical order of iterators can change unpredictably.

  3. Roughly speaking, any element that is both inserted to a priority queue (e.g., through push) and removed from it (e.g., through pop), incurs a logarithmic overhead (in the amortized sense). Different underlying data structures place the actual cost differently: some are optimized for amortized complexity, whereas others guarantee that specific operations only have a constant cost. One underlying data structure might be chosen if modifying a value is frequent (Dijkstra's shortest-path algorithm), whereas a different one might be chosen otherwise. Unfortunately, an array-based binary heap - an underlying data structure that optimizes (in the amortized sense) push and pop operations, differs from the others in terms of its invalidation guarantees. Other design decisions also impact the cost and placement of the overhead, at the expense of more difference in the the kinds of operations that the underlying data structure can support. These differences pose a challenge when creating a uniform interface for priority queues.