Introduction
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 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.
- 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>
void
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 are useful when one needs to efficiently
access a minimum (or maximum) value as the set of values
changes.
- 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...
- 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.
- 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.