4. Subtleties of the core::tree<>

The core::tree<> family consists of 4 generic trees:

core::tree - a tree that restricts element containment, like std::set
core::multitree - a tree with no element containment restriction, like std::multiset

core::tree_pair - a tree pair that restricts element containment, like std::map
core::multitree_pair - a tree pair with no element containment restriction, like std::multimap

Two trees of the core::tree family are not discussed in this article; tree_pair and multitree_pair. The functionality of core::tree_pair<> and core::tree_multipair<> is slightly more advanced than the core::tree<> and core::multitree<> and will be covered in later installments of the C++ tree series.

4.1 Differences between the tree container and the tree iterator

The basic functionality of core::tree<> containers and iterators are similar to that of STL's containers and iterators. A core::tree<> must be concretely constructed to store elements (as stated in 3.1). A core::tree<>::iterator must be created to iterate over those elements. Beyond these two definitions, the behavior begins to get a bit blurry.

When a core::tree<> is destroyed, its elements (its entire tree) are destroyed with it. When a core::tree<>::iterator is destroyed, only the iterator is destroyed, not the elements it currently points to.

For example, consider the following code:

int main()
{
  core::multitree<int> t;

  t.push_back(5);
  t.push_back(3);
  t.push_back(1);
  t.push_back(5);

  outputTree(t);

  return 0;
}

void outputTree(const core::multitree<int>& t)
{
  for (core::multitree<int>::iterator iter = t.begin(); iter != t.end(); ++iter)
  {
    std::cout << *iter << std::endl;
  }
}

When the core::multitree<int> t goes out of scope in main(), all elements within it (5, 3, 1, 5) are destroyed, including the entire tree structure contained within it. However, when the outputTree() function exits and the iterator iter goes out of scope, only the iterator is destroyed, not the tree it points to.

Thus, the conceptual use of the core::tree<> and the core::tree<>::iterator are quite similar to that of STL's containers and iterators. A core::tree<>::iterator is used to iterate through a core::tree<> (and perform additional actions), but never actually destroy memory of the tree when going out of scope. A core::tree<> stores the tree structure and at least one concrete tree is needed to create a tree structure (as stated in section 3.1). When a concrete core::tree<> is destroyed (a concrete one, not a pointer or reference to one), all elements contained within are destroyed as well.

The fundamental difference between STL concepts of containers and iterators and the core::tree's concept of containers and iterators is that core::tree container actions can be (and must be) performed through iterators.

To further explain the differences between the core::tree<> and the core:: tree<>::iterator through a working example, consider building the following tree:

Figure 4.1: Building an integer tree

The core::tree<> family was designed with the innate recursive definition of trees in mind and therefore allows container functionality within iterators. An example of this is the following code, building the above tree in Figure 4.1 (the following code is intentionally different from the code written in section 3.4 to show different ways of performing the same actions using the core::tree<> library):

core::tree<int> t; // one core::tree<> must always be concretely constructed
core::tree<int>::iterator iter;

*t = 1;                 // store 1 as the root
iter = t.push_back(2);  // insert 2 into the first level

// iter now points to the 2 tree, now 4, 5 and 6 can be pushed into it
iter.push_back(4);
iter.push_back(5);
iter.push_back(6);

iter = t.push_back(3);  // insert 3 into the first level

// iter now points to the 2 tree, now 7, 8 and 9 can be pushed into it
iter.push_back(7);
iter.push_back(8);
iter.push_back(9);

The above code shows a sample behavior of core::tree<> and core::tree<>::iterator interaction. Once the core::tree<> is defined, most of the remaining work is done from a core::tree<>::iterator (or several iterators). However, the core::tree<>::iterator will generally perform actions of both the iterator and container (any time you have a core::tree<>::iterator, you really have an iterator and a tree).

In summary, some of the fundamental differences between a core::tree<> and a core::tree<>::iterator:

1. When a core::tree<> goes out of scope (is destroyed) all elements from the tree are destroyed.
2. When a core::tree<>::iterator goes out of scope (is destroyed) no elements of the tree are destroyed.
3. A core::tree<>::iterator contains a pointer to the core::tree<> its currently pointing to. The tree contained within an iterator can be accessed directly from tree_ptr() or tree_ref() iterator functions.
4. A core::tree<> can be wrapped inside of a core::tree<>::iterator. The tree_iterator() function of the core::tree<> can be called to return any core::tree<> as a core::tree<>::iterator.
5. All insert, search and iteration functionality return iterators.
6. All insert, search and removal functionality are called from trees.

At this point, it becomes clear that tree container and tree iterator functionality are generally performed through a tree iterator (once a concrete core::tree<> is defined somewhere). Yet, much of the work a tree iterator performs is actually tree container work. The iterator is not actually performing the functionality itself, instead it is merely passing a function call on from the client to the tree container, acting as a middle-man.

From the initial rules of recursion in sections 3.2 - 3.4, it is important to remember, 1) whenever you have a tree iterator, you also have a tree container and 2) whenever you have a tree container, you also have a tree iterator. Outside of the encapsulation of tree container functionality within a tree iterator (i.e. calling "begin()" from a tree iterator, which is clearly a tree container piece of functionality), there are direct ways to get access to the contained tree container (and vice versa).

Given a tree iterator, pointing to a valid tree, you can call tree_ptr() or tree_ref() to return the pointer or reference of the tree the iterator is pointing to. Given a tree container, you can call tree_iterator() to return the tree's wrapping iterator.

In many cases, a tree iterator can perform tree container actions directly through its tree-container-encapsulated iterator interface. However, in some rare cases, certain functionality can only be achieved through tree containers directly. Because of this, the tree_ptr(), tree_ref() functionality was created to enable tree iterators to return their contained tree container when needed. Likewise, the tree_iterator() functionality was created for the same purpose, except when converting a tree container into a tree iterator.

4.2 Differences between core::tree<> and core::multitree<>

The fundamental difference between the core::tree<> and the core::multitree<> is similar to the difference between std::set and std::multiset:

core::tree<> - at any given level within the tree, no more than one equivalent element can exist

core::multitree<> - at any given level within the tree, any number of equivalent elements can exist

Other than the single difference listed above, the core::tree<> and the core::multitree<> behaviors are the same.

4.3 core::tree<> requirements

In order to use the core::tree<> with your own user defined type (i.e. classes, structs), a few pieces of functionality may be required.

For example, consider the following class:

class SomeClass
{
private:
  int someData_;
};

Before SomeClass can be contained within a core::tree as follows:

core::tree<SomeClass> someClassTree;

the following functionality may be required depending on how the core::tree<> is used with that class:

1. must be default constructible (which SomeClass already is)
2. may require operator<()
3. may require operator==()

For native types (int, char, bool, etc.), the above three requirements are always fulfilled, so no additional work must be done for a core::tree<> to contain native types.

Moreover, it is possible to use the core::tree<> without the definition of operator<() and operator==() for the contained object type, as long as a predicate [8] is used for any insert() functions used and for any find() functions used. If predicates are used for both inserts and finds, the core::tree will use those predicates in place of the default operator<() and operator==() behaviors, respectively. In conjunction, push_front() and push_back() functionality can be used in place of insert() functionality to add items to the tree in an unordered way that does not require the definition of operator<() for the contained class.

The core::tree<> API