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:

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

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.

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.

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