tree

The tree container is so named because it can represent a general hierarchical collection of elements using a tree-like structure.  Examples of things which use such general tree-like structures include file systems, XML elements in an XML document or the items in a GUI tree control or menu. The C++ Standard Library includes ordered containers which use a binary (2-ary) search tree as their underlying data structure (std::set, std::multiset, std::map and std::multimap) but their interfaces are designed for accessing the elements as an ordered sequence of elements with no hierarchy and do not provide direct access to the underlying tree data structure; tree on the other hand is an unordered container that provides an interface for accessing the (non-fixed-ary) tree directly allowing siblings to be iterated, parent elements to be determined etc.

You can download the implementation here (v1.3) (changelog).

Example of use:

#include <iostream>
#include <string>
#include <algorithm>
#include <neolib/tree.hpp>

int main()
{
	typedef neolib::tree<std::string> names_t;
	names_t names;
	names.push_back("colours");
	names.push_back("animals");
	names.push_back("people");
	names_t::const_iterator colours = std::find(names.sibling_begin(), names.sibling_end(), "colours");
	names.push_back(colours, "red");
	names.push_back(colours, "green");
	names.push_back(colours, "blue");
	names_t::const_iterator animals = std::find(names.sibling_begin(), names.sibling_end(), "animals");
	names.push_back(animals, "dolphin");
	names.push_back(animals, "kitteh");
	names.push_back(animals, "hedgehog");
	names_t::const_iterator people = std::find(names.sibling_begin(), names.sibling_end(), "people");
	names.push_back(people, "Michael Phelps");
	names.push_back(people, "Larisa Latynina");
	names.push_back(people, "Paavo Nurmi");
	std::cout << "Unsorted:-" << std::endl;
	for (names_t::const_iterator i = names.begin(); i != names.end(); ++i)
	{
		std::cout << std::string(names.depth(i) * 4, ' ') << *i << std::endl;
	}
	std::cout << "Sorted:-" << std::endl;
	names.sort();
	for (names_t::const_iterator i = names.begin(); i != names.end(); ++i)
	{
		std::cout << std::string(names.depth(i) * 4, ' ') << *i << std::endl;
	}
	std::cout << "Just top-level elements:-" << std::endl;
	for (names_t::const_sibling_iterator i = names.sibling_begin(); i != names.sibling_end(); ++i)
	{
		std::cout << std::string(names.depth(i) * 4, ' ') << *i << std::endl;
	}
	std::cout << "Just Olympians:-" << std::endl;
	for (names_t::const_sibling_iterator i = names.sibling_begin(people); i != names.sibling_end(people); ++i)
	{
		std::cout << std::string(names.depth(i) * 4, ' ') << *i << std::endl;
	}
	return 0;
}

The output of which is:

Unsorted:-
colours
    red
    green
    blue
animals
    dolphin
    kitteh
    hedgehog
people
    Michael Phelps
    Larisa Latynina
    Paavo Nurmi
Sorted:-
animals
    dolphin
    hedgehog
    kitteh
colours
    blue
    green
    red
people
    Larisa Latynina
    Michael Phelps
    Paavo Nurmi
Just top-level elements:-
animals
colours
people
Just Olympians:-
    Larisa Latynina
    Michael Phelps
    Paavo Nurmi

You can e-mail comments to the author.

Back to project page