======================================================================== Summary map -- std::map with efficient aggregation ======================================================================== Daniel Beer <dlbeer@gmail.com> 7 Dec 2012 ------------------------------------------------------------------------ Contents ------------------------------------------------------------------------ 1. Overview 2. Query efficiency 3. Customization 4. Method list 5. Exceptions ------------------------------------------------------------------------ 1. 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: - it must be computable with an associative binary function - it must have an identity value, which doesn't change the value that it's combined with Examples of suitable aggregates are: - sum: computed with + and having identity 0 - product: computed with * and having identity 1 The easiest way to define an aggregate is to declare a type with three constructors: - a no-argument constructor for producing an identity value - a constructor which takes std::pair<Key, Data>, and returns an aggregate over a single value - a constructor taking two aggregates and producing the combination of the two 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). ------------------------------------------------------------------------ 2. 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. ------------------------------------------------------------------------ 3. 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")); ------------------------------------------------------------------------ 4. 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: - initializer lists: summary_map(std::initializer_list<value_type>) - move constructor: summary_map(summary_map&&) - move assignment: operator=(summary_map&&) 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. ------------------------------------------------------------------------ 5. 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: * Any supplied allocator's deallocate() method must be no-throw. * User-supplied comparison, aggregation and allocation objects may throw exceptions in their assignment operators and constructors, but if so, they must also provide no-throw swap() functions that can be found via ADL. These conditions are met for the default types. Given these, the following guarantees are made: * sum(), sum(a, b) will propagate exceptions if the aggregator throws them, but it will not alter or corrupt the container in any case. Any partial summaries which are computed successfully will be kept cached. * The following operations are no-throw: - move construction and assignment - swap() - clear() - empty(), size(), max_size() - all iterator operations - find(), lower_bound(), upper_bound(), count(), equal_range() - erase(pos), erase(key), erase(first, last) * If an exception is thrown during insertion or modification of a single element, no change to the container will be effected. However, if an exception occurs during the range variant of insert, all inserted elements at the point the exception occurs will remain. That is, range insert is equivalent to a repeated single-element insert.