A multivector is a a generic container that behaves just like a std::vector
except its iterators also behave just like std::vector.
And since std::vector is used in the underlying representation, we can make
hierarchies that benefit from both cache friendly locality of reference and
move semantics provided by modern C++.
A multivector is ideally suited to represent trees that we often encounter in software: document object models, window hierarchies, protocol messages, configurators, filesystems, online shopping carts, multiple choice tests, user lists, etc.
A simple multivector of integers can be conveniently created with an initializer list:
#include <wythe/multivector.h>
auto m = wythe::multivector<int>{1, 2, {10, 11, 12, {100}}, 3};and displayed using the to_text convenience function:
std::cout << wythe::to_text(m);resulting in:
1
2
10
11
12
100
3
There are 3 vectors in the above multivector: { 1, 2, 3 }, { 10, 11, 12 }, and { 100 }. Let’s call them subvectors.
In tree terminology, items within subvectors are siblings.
2 is the parent of { 10, 11, 12 }, and 12 is the parent of { 100 }. Since this is a tree structure, the parent of { 1, 2, 3 } is considered the root.
Iterators for multivectors are called cursors and are the means of navigation.
They are random access within the same vector.
Unlike regular iterators they have the vector functions you would expect:
begin(), end(), emplace(), etc.
For cursors, begin() and end() behave like std::vector iterators.
Multivectors, however, can have many different begin() and end() cursors.
The above example has 3 each.
All cursors that are part of the same multivector are comparable.
So the end() of the { 10, 11, 12 } vector is comparable (and not equal) to the
begin() of the { 100 } vector.
Cursors can also navigate up the tree using the parent() member function.
|
Warning
|
The implementation currently includes a subset of the features found std::vector.
|
The multivector is a totally ordered container class for hierarchies.
There is an additional constructor that takes a cursor:
multivector(cursor c)c will become the root of a new multivector, its contents will be copied.
The multivector implementation is contained entirely in multivector.h.
and can be found at https://github.com/wythe/multivector.
There are no dependencies other than the STL.
Building is only required to run the tests and examples.
Compilation times will not be noticably impacted when used in your own projects.
Cursors share both the properties of std::vector and a std::vector’s iterator.
This in effect makes a cursor behave like a multivector.
There are three kinds of cursors, described in the following sections.
In addition to normal random-access iterator operations, cursors also support the
std::vector member functions.
Additional cursor navigation operations are available:
bool is_first_child() const // return true if this is the first child
cursor parent() const // return a cursor to parent
bool is_root() const // true if this is the root cursorCursor validity is similar to that of vectors. If a vector gets resized, then all its cursors are invalidated. But any parent cursor is still valid.
A precursor is a forward cursor.
operator++ just goes up and to the left until the root.
For example:
auto m = wythe::multivector<int>{1, {10, { 100, 101, 102}}, 2, 3, 4};
auto n = m.begin().begin().end(); // n points to one past 102
--n; // n points to 102
auto last = wythe::multivector<int>::precursor(n); // convert to a precursor
while (!last.is_root()) {
std::cout << *last << '\n';
++last;
}will print out
102 101 100 10 1
The above code segment could be written more concisely using the
to_precursor() function:
auto last = wythe::to_precursor(--m.begin().begin().end());precursor currently supports the following subset of vector operations:
// vector operations
bool empty() const
size_t size() const
cursor begin()
cursor begin() const
cursor cbegin() constAdditional precursor operations:
bool is_root() constA linear cursor is also a forward iterator. It traverses a multivector in a depth-first order.
The following code:
auto m = wythe::multivector<int>{1, { 2, { 3 }, 4}};
for (auto i = wythe::to_linear(m.begin()); i!=m.end(); ++i)
std::cout << *i << '\n';will output:
1 2 3 4
Notice the automatic conversion from one type of cursor to another.
There are no operations for the linear cursor other than those of an input iterator.
The multivector functions act upon one or more template cursor parameters that must satisfy the cursor definition above.
template <typename Cursor>
Cursor get_root(Cursor start)Return the root cursor of a multivector given a cursor. This is a log2(n) operation.
template <typename Cursor>
Cursor previous(Cursor self)Return the previous cursor, either a sibling or parent.
template <typename Cursor, typename Action>
void recurse(Cursor parent, Action action)Recursively descend and perform an action on each item. The action must have a signature of:
void action(Cursor current, Cursor parent)
current is the current item visited, and parent is its parent.
The following example will print out all the items in a multivector:
typedef wythe::multivector<int>::cursor int_cursor;
auto m = wythe::multivector<int>{1, { 2, { 3 }}};
wythe::recurse(m.root(), [](int_cursor c, int_cursor) { std::cout << *c << '\n'; }template <typename Cursor, typename Action>
void recurse(Cursor parent, Action action_down, Action action_up, int level = 0)This version of recurse is similar to the above, except it also performs and action on
the way up.
Also, the current depth in the tree will be provided.
The to_text function is written using this.
inline std::string compact_string(Cursor parent);
inline std::string compact_string(const multivector<T> & tree);Conveniently return a compact string representation of a multivector. It uses the above recurse method.
auto m = wythe::multivector<int>{1, { 2, { 3 }}};
std::cout << wythe::compact_string(m.root());prints:
{1 {2 {3}}}
inline std::string to_text(Cursor parent)
inline std::string to_text(const multivector<T> & tree)Convert to a table string. An example is provided in the introduction.
inline void promote_last(Cursor parent)
Replace the last child with the children of the last child.
This should be rewritten to not be so specific.
Perhaps a detach() ability that removes a subtree as a multivector.
template <typename Cursor>
inline typename Cursor::precursor_type to_precursor(Cursor c)Convert a cursor to precursor.
inline typename Cursor::linear_type to_linear(Cursor parent)
Convert a cursor to a linear cursor.
template <typename Cursor, typename ConstCursor>
void append(Cursor parent, ConstCursor first, ConstCursor last)
template <typename Cursor, typename ConstCursor>
void append(Cursor parent, ConstCursor from_parent)Append (i.e., copy) the children of one cursor to the children of another. The the children will be appended to any existing children.
I originally wrote this as a purpose built data structure for a project. And it turned out to be tremendous simplification over the previous node based system. Hopefully, you will find it usefull too.
But admittedly there are some questionable design decisions. Not all vector functions are supported yet. And some of the functions included seem a bit random.
Pull requests are welcome, and hopefully together we can make this more useful.
Below are other tree implementations and papers I looked at while developing multivector. In general, they provide more capability than the multivector, but are node based.
-
multivector has some commonalty with the boost property tree: boost property tree
-
Hierarchical Data Structures and Related Concepts for the C++ Standard Library