#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->second.info();
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.
metadata_vector.duplicate(key);
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.
metadata_vector.uniq();
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.