Chapter 51. Sorted and range vectors


Vectors of ranges
#include <x/sorted_vector.H>

class metadata_t;

typedef x::sorted_vector<size_t, metadata_t> metadata_vector_t;

metadata_vector_t metadata_vector;

metadata_vector.insert_value(0, metadata_t());

metadata_vector.insert_value(10, metadata_t());

metadata_vector_t::iterator iter=metadata_vector.find(5);

if (iter != metadata_vector.end())
    std::cout << metadata_vector->;

The x::sorted_vector template implements a subclass of a std::vector with some std::set-like semantics. Its intended to maintain ordered key/value metadata for some larger object, which can grow and shrink, with the ordered metadata getting adjusted accordingly. It's optimized for a medium-sized collection of metadata, with a logarithmic lookup, and linear complexity for key adjustment.

The first x::sorted_vector template parameter is a key type, the second template parameter is a value type. The x::sorted_vector's values are a tuple whose first member is not modifiable, and can only be casted to the key type; the second member is an instance of the value type. An optional third template parameter specifies the comparator class for the key type, defaulting to a std::less.

A second template parameter of void results in a vector of a tuples containing only a first member.

The values in the x::sorted_vector are always kept sorted according to each value's key. Insertion takes linear complexity. find() searches the x::sorted_vector for the requested key, and returns an iterator to either the value for the key, if it exists, or to the immediately preceding key, if the specified key value does not exist. In the example above, find() returns the iterator for the value of the 0 key, since there is no value with the key of 5, and this is the immediately preceding key in the x::sorted_vector.

x::sorted_vector exports all methods and members of its std::vector superclass, except for modifiers. Only x::sorted_vector's methods must be used to modify the sorted list.



duplicate() searches for the value with the given key. If one does not exist, the value for the nearest lower key gets copied for the specified key. duplicate() returns true if the key already existed, or was created by copying the value from the nearest lowest key. duplicate() returns false if the requested key does not exist because the sorted vector is empty, or the key was less than the first value's key.


uniq() removes consecutive equal values from the sorted vector. uniq() takes an optional comparator parameter, which defaults to std::equal_to that compares two consecutive values in the sorted vector. Only consecutive equal values are removed, equal values with non-equal intervening values, in key order, are not removed. The first value that compares equal to the following value is kept, all subsequent, consecutive values, in key order, are removed from the sorted vector.

metadata_vector.remove(lower_bound, upper_bound);

remove() removes values whose keys are equal or greater than lower_bound, but less than upper_bound. remove() returns false in two situations, indicating invalid parameters: lower_bound is greater than upper_bound, or upper_bound is not greater than the first key in the sorted vector (this is automatically the case when the sorted vector is empty).

Otherwise any values with the keys in the given range are removed from the sorted vector.

metadata_vector.remove_range(lower_bound, upper_bound);

remove_range() is similar to remove(), but with the following differences. Before removing any keys, duplicate() gets invoked, ensuring that the upper_bound key exists. Then, in addition to removing the keys in the given range, the difference upper_bound-lower_bound gets subtracted from all key values after the range (including the upper_bound key).

For example, the sorted vector contains values with these keys: 0, 5, 10, 15, 20. remove_range(3, 14) results in a sorted vector with the following keys: 0, 3, 4, 9. Before removal, 10's value gets copied to the 14 key, then the keys 5 and 10 get removed, and the keys 14, 15, and 20 get 11 subtracted from them (the difference 14-3).

remove_range() returns false indicating an error if the given upper bound is less than the lower bound, or the upper bound is not greater than or equal to the first key in the sorted vector (which is also case when the sorted vector is empty). If the lower bound and the upper bound are equal, remove_range() returns true without doing anything. Otherwise remove_range() returns true after finishing the removal of the specified range.

metadata_vector.insert_range(lower_bound, range, value);

insert_range() calls duplicate() to create a key for the given lower_bound, if needed, then range gets added to all keys in the sorted vector that are equal to or greater than lower_bound (including the newly-duplicated key, possibly). Finally, the specified value gets added to the sorted vector, with the key of lower_bound.

For example, the sorted vector contains values with these keys: 0, 5, 15, 20. remove_range(8, 2, value) results in a sorted vector with the following keys: 0, 5, 8, 10, 17, 20. The value for the key 5 gets initially duplicated with the key of 8, then 2 gets added to it, and the following keys; becoming 10, 17, and 20; finally the new value gets inserted with the key of 8.

insert_range() returns false indicating an error if range is less than 1, or if lower_bound was less than the first value in the sorted vector. Otherwise, insert_range() returns true after completing the insert.