List-Update Containers

This section describes policies for list updates. It is organized as follows:

  1. The General Terms Subsection describes general terms.
  2. The Implementation in pb_assoc Subsection describes the implementation of these concepts in pb_assoc.

General Terms

Associative containers use some attributes of the keys of which they store: tree-based containers use the ability to compare keys; hash-based containers use the ability to map keys into numbers.

In the (rare) case where keys can only be checked for equivalence, these types of containers cannot be used. In such a case, storing the entries in a list is a reasonable solution. Clearly, the order of the elements within the list affects performance; ideally, frequently accessed elements should be at the front of the list.

Many remarkable (online competitive [motwani95random]) algorithms exist for reordering lists to reflect access prediction [andrew04mtf]. Some of these algorithms require storing metadata with each key, while others do not. Some of these algorithms require only the ability to move an element to the front of the list, while others require the ability to interchange an element and its predecessor.

For example, Figure -A The counter algorithm 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 in pb_assoc

The pb_assoc library allows instantiating lists with policies implementing any algorithm moving nodes to the front of the list (policies implementing algorithms interchanging nodes are currently unsupported).

Associative containers based on lists are parameterized 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.

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.

Additionally, the library contains implementations of the move-to-front and counter policies. These are described in Policy Classes.