#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`

`upper_bound`

`upper_bound`

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`

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`

`lower_bound`

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

`insert_range`

() returns
`true`

after completing the insert.