Daniel Beer Atom | RSS | About

Summary map

7 Dec 2012

Overview

A summary map is a drop-in replacement for std::map with the additional property that it supports efficient computation of aggregate functions over contiguous ranges.

This is achieved by arranging the stored items in an augmented red-black tree and then caching partially computed aggregates over subtrees.

Any aggregate function can be selected for an instance, but it is fixed and it must satisfy the following properties:

Examples of suitable aggregates are:

The easiest way to define an aggregate is to declare a type with three constructors:

For example, suppose we have been keeping word counts in an std::map<std::string, int>. Each key corresponds to some word in a block of input text, with the mapped value being the number of times that word occurs.

Now want to be able to count the number of times words within a given range occur – for example, how many words in the original text fall alphabetically between “apple” and “banana”? We could define a summing aggregate as follows:

struct word_sum {
    int total;

    // Identity
    word_sum() : total(0) { }

    // Aggregate over a single value
    word_sum(const std::pair<const std::string, int>& v) :
        total(v.second) { }

    // Combination of two aggregates
    word_sum(const word_sum& a, const word_sum& b) :
        total(a.total + b.total) { }
};

Then, rather than using std::map<std::string, int>, we instantiate a compatible summary map instead:

summary_map<std::string, int, word_sums> my_map;

If we’ve filled it with word counts, we can then answer our original question with the sum() operation, giving two iterators to specify a range:

const word_sum answer =
    my_map.sum(my_map.lower_bound("apple"),
               my_map.lower_bound("banana"));

There is also an overload of sum() which takes no arguments, and returns the aggregate computed over the entire tree contents. Aggregate computation is done lazily and cached at each node (the value cached at each node represents the sum of the subtree rooted at the same node). The sum call may require examination of the entire tree, but subsequent calls will reuse previously computed partial aggregates (this is why sum() and sum(a, b) are not const methods).

Query efficiency

If all partial aggregates are cached, a call to sum() takes O(1) time, and sum(a, b) takes O(log n) time. If no partial aggregates are cached, then sum() takes O(n) time, and sum(a, b) takes O(m) time, where m is the number of elements in the range [a, b].

It gets more complicated if modifications are made between summation requests. A single element insertion/deletion will invalidate O(log n) cached values, and cause the next sum() call to run in O(log n) time. A sum(a, b) call will also run in O(log n) time.

The expected run time gets worse if more modifications have been made since the last sum() call, but the runtime will never be worse than linear – which is what you’d get by calculating the aggregate from scratch anyway.

If you need to avoid worst-case query times and are willing to trade some constant-factor efficiency to get it, you can call sum() after each modification to the map. This causes all invalidated summaries to be recalculated, and ensures that any subsequent summation requests will make full use of cached values. Note that sum() itself will run in O(log n) time if you call it after single-element modifications, so it doesn’t change the asymptotic time complexity of insert/erase to do this.

Note that dereferencing a mutable iterator will invalidate some summaries. This is necessary because aggregates may depend on mapped data.

Customization

The full template specification for summary_map is:

template <class Key, class Data, class Summary,
  class Compare = std::less<Key>,
  class Aggregate = aggregator<std::pair<const Key, Data>, Summary>,
  class Allocator = std::allocator<std::pair<const Key, Data> > >
class summary_map;

In addition to the usual ways that an std::map can be customized (comparison, allocation), you can also specify a custom set of aggregation operations.

In the examples shown above, we defined an aggregate value which was computed through its constructors. This works fine for ad-hoc aggregates, but what if you want to reuse the same data type with different aggregation operations, or if you want to use a simple type like int as an aggregate? You can do this by supplying an aggregator other than the default. An aggregator must supply three methods:

Summary nothing() const;
Summary summarize(Value v) const;
Summary combine(Summary a, Summary b) const;

The default aggregator template implements these by passing the values on to the constructor of the Summary type. Here’s how we could implement the word-count aggregate shown above, but using int as a summary type:

struct int_aggregator {
    int nothing() const { return 0; }
    int summarize(const std::pair<const std::string, int>& v)
        { return v.second; }
    int combine(int a, int b) { return a + b; }
};

We could then instantiate and use our summary_map without having to use the word_sum type:

summary_map<std::string, int, int,
            std::less<std::string>, int_aggregator> my_map;

const int answer =
    my_map.sum(my_map.lower_bound("apple"),
               my_map.lower_bound("banana"));

Method list

All methods and typedefs usually found in std::map are available. There are two additional typedefs:

typedef Summary                     summary_type;
typedef Aggregate                   aggregator_type;

The following additional methods are provided:

aggregator_type get_aggregator() const;
summary_type sum();
summary_type sum(const_iterator first, const_iterator last);

A free-standing swap() function is provided which implements an efficient no-throw swap of two containers (by forwarding to the swap() member function).

Unless the preprocessor symbol SUMMARY_MAP_NO_CPP11 is defined, the following features are enabled:

If the preprocessor symbol SUMMARY_MAP_DEBUG is defined, an additional member function is provided:

void check();

This function scans the data structure and verifies that all the invariants of an red-black tree are satisfied (red-black balancing rules and ordering). It runs in O(n) time and is intended for debugging purposes only.

Exceptions

The summary_map class throws no exceptions directly, but it invokes operations on user-supplied types which might throw exceptions. In any case, certain guarantees are made (some conditional). The conditions required are:

These conditions are met for the default types. Given these, the following guarantees are made:

Download

The source code is available from the git repository:

To build and run tests, type “make test” in the source directory. To use the code in your own application, just add the file summary_map.hpp to your project. There is no need to link against any external library binary.

License

Copyright (C) 2012 Daniel Beer <>

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.