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

List-Update Design

+ +

Overview

+ +

The list-based container has the following declaration:

+ 
+template<
+    typename Key,
+    typename Mapped,
+    typename Eq_Fn = std::equal_to<Key>,
+    typename Update_Policy = move_to_front_lu_policy<>,
+    typename Allocator = std::allocator<char> >
+class list_update;
+
+ +

The parameters have the following meaning:

+ +
    +
  1. Key is the key type.
    2. + +
  2. Mapped is the mapped-policy, and is explained in + Tutorial::Associative + Containers::Associative Containers Others than Maps.
    3. + +
  3. Eq_Fn is a key equivalence functor.
    4. + +
  4. Update_Policy is a policy updating positions in + the list based on access patterns. It is described in the + following subsection.
    5. + +
  5. Allocator is an allocator + type.
    6. +
+ +

A list-based associative container is a container that + stores elements in a linked-list. It does not order the + elements by any particular order related to the keys. + List-based containers are primarily useful for creating + "multimaps" (see Motivation::Associative + Containers::Avoiding Multiple Keys and Tutorial::Associative + Containers::Associative Containers Others than Maps). In + fact, list-based containers are designed in pb_ds + expressly for this purpose. This is explained further in + Use for "Multimaps".

+ +

List-based containers might also be useful for some rare + cases, where a key is encapsulated to the extent that only + key-equivalence can be tested. Hash-based containers need to + know how to transform a key into a size type, and tree-based + containers need to know if some key is larger than another. + List-based associative containers, conversely, only need to + know if two keys are equivalent.

+ +

Since a list-based associative container does not order + elements by keys, is it possible to order the list in some + useful manner? Remarkably, many on-line competitive [motwani95random] + algorithms exist for reordering lists to reflect access + prediction [andrew04mtf].

+ +

List + Updates

+ +

General Terms

+ +

Figure A simple list shows a + simple list of integer keys. If we search for the integer 6, we + are paying an overhead: the link with key 6 is only the fifth + link; if it were the first link, it could be accessed + faster.

+ +
no image
+ +
A simple list.
+ +

List-update algorithms reorder lists as elements are + accessed. They try to determine, by the access history, which + keys to move to the front of the list. Some of these algorithms + require adding some metadata alongside each entry.

+ +

For example, Figure The counter algorithm + -A shows the counter algorithm. Each node contains both a key + and a count metadata (shown in bold). When an element is + accessed (e.g. 6) its count is incremented, as shown in + Figure The counter algorithm -B. If the count + reaches some predetermined value, say 10, as shown in Figure + The counter algorithm -C, the count is set to + 0 and the node is moved to the front of the list, as in Figure + The counter algorithm -D.

+ +
+
+ +
The counter algorithm.
+ +

Implementation

+ +

pb_ds allows instantiating lists with policies + implementing any algorithm moving nodes to the front of the + list (policies implementing algorithms interchanging nodes are + unsupported).

+ +

Associative containers based on lists are parametrized by a + Update_Policy parameter. This parameter defines the + type of metadata each node contains, how to create the + metadata, and how to decide, using this metadata, whether to + move a node to the front of the list. A list-based associative + container object derives (publicly) from its update policy. + Figure A list and its update + policy shows the scheme, as well as some predefined + policies (which are explained below).

+ +
+
+ +
A list and its update policy.
+ +

An instantiation of Update_Policy must define + internally update_metadata as the metadata it + requires. Internally, each node of the list contains, besides + the usual key and data, an instance of typename + Update_Policy::update_metadata.

+ +

An instantiation of Update_Policy must define + internally two operators:

+ 
+update_metadata
+operator()();
+
+bool
+operator()(update_metadata &);
+
+ +

The first is called by the container object, when creating a + new node, to create the node's metadata. The second is called + by the container object, when a node is accessed (e.g., + when a find operation's key is equivalent to the key of the + node), to determine whether to move the node to the front of + the list.

+ +

The library contains two predefined implementations of + list-update policies [andrew04mtf]. The first is + counter_lu_policy, which + implements the counter algorithm described above. The second is + move_to_front_lu_policy, + which unconditionally move an accessed element to the front of + the list. The latter type is very useful in pb_ds, + since there is no need to associate metadata with each element + (this is explained further in Use for + "Multimaps").

+ +

Use for "Multimaps"

+ +

In pb_ds, there are no equivalents for the STL's + multimaps and multisets; instead one uses an associative + container mapping primary keys to secondary keys (see Motivation::Associative + Containers::Alternative to Multiple Equivalent Keys and + Tutorial::Associative + Containers::Associative Containers Others than Maps).

+ +

List-based containers are especially useful as associative + containers for secondary keys. In fact, they are implemented + here expressly for this purpose.

+ +

To begin with, these containers use very little per-entry + structure memory overhead, since they can be implemented as + singly-linked lists. (Arrays use even lower per-entry memory + overhead, but they are less flexible in moving around entries, + and have weaker invalidation guarantees).

+ +

More importantly, though, list-based containers use very + little per-container memory overhead. The memory overhead of an + empty list-based container is practically that of a pointer. + This is important for when they are used as secondary + associative-containers in situations where the average ratio of + secondary keys to primary keys is low (or even 1).

+ +

In order to reduce the per-container memory overhead as much + as possible, they are implemented as closely as possible to + singly-linked lists.

+ +
    +
  1. List-based containers do not store internally the number + of values that they hold. This means that their size + method has linear complexity (just like std::list). + Note that finding the number of equivalent-key values in an + STL multimap also has linear complexity (because it must be + done, e.g., via std::distance of the + multimap's equal_range method), but usually with + higher constants.
    2. + +
  2. Most associative-container objects each hold a policy + object (e.g., a hash-based container object holds a + hash functor). List-based containers, conversely, only have + class-wide policy objects.
    3. +
+ +

See also Associative-Container + Performance Tests::Observations::Mapping-Semantics + Considerations.

+
+ +