X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fintroduction.html;fp=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fintroduction.html;h=b3ccbd76aee49f79262c3bbd838df56c97b948fb;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libstdc++-v3/doc/html/ext/pb_ds/introduction.html b/libstdc++-v3/doc/html/ext/pb_ds/introduction.html new file mode 100644 index 00000000..b3ccbd76 --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/introduction.html @@ -0,0 +1,120 @@ + + + + + + + Introduction + + + + +
+

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

+ +
    +
  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. + +
  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>
+  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. +

    3. +
+ +

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. + +
  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. + +
  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.

    4. +
+
+ +