tree::tree - create


template <class k, class t, class compare, class less>
tree<,t,compare,less>::tree()

This constructor creates a tree.

Notes

A tree is a set with an extra comparer that compares the key (k) to the datatype (t). It then supports searches by that key (by k in other words). The comparers of a tree are shown in the following example.

import std.core;
import iplusplus;
using namespace standard;

struct t
{
	int i;
	string s;

	t() {}

	t(int _i, const string& _s) : i(_i), s(_s) {}
};

std::ostream& operator<<(std::ostream& s, const t& _t)
{
	s << "(" << _t.i << "," << _t.s << ")";
	return s;
}

bool operator<(const t& a, const t& b)
{
	if (a.i < b.i) return true;
	return false;
}

struct tree_compare
{
	int operator()(const int& key, const t& type) const
	{
		if (key < type.i) return -1;
		if (type.i < key) return 1;
		return 0;
	}
};

int main()
{
    tree<int, t, tree_compare> tree;
    tree << t(0, "hello") << t(1, "world");
    std::cout << tree << "\n";
    std::cout << tree[0] << "\n";
}

The output of the program is shown below.

{(0,hello),(1,world)}
(0,hello)

The structure t contains an integer and a string. We would like to form a set of these but enable keyed searches. The above program does this.

The class tree_compare contains a function operator that performs int to t comparisons. Note that this comparer returns <0 when the int is less that the t, >0 when the int is greater than the t and 0 when the int is equal to the t. This differs from the base set class which works off the less than operator for t.

Thus a tree requires two comparers whereas a set only requires one. The key to type comparer is a three way comparer whereas the set comparer returns a boolean.