Tree Container Library: Associative Trees

The Tree Container Library

A C++ generic tree container library which, not only works much like the STL, but is also compatible with the STL algorithms. The Tree Container Library is used worldwide in thousands of industries and organizations. It is completely free to use, and is licensed under the zlib/libpng license.

The associative trees consist of tree, multitree, and unique_tree. These trees are categorized as associative trees, because they all use associative containers (std::set) as their internal node containers. The forth tree container, sequential_tree, is a sequential type of tree, because it uses a std::vector as it's internal node container.

The associative trees have many operations and properties in common. These operations are grouped below according to the type of operation. The documentation below applies to TCL versions 3.50 and higher. The latest version of the TCL can be downloaded from the TCL download page.

Removing Nodes

  • bool erase(stored_type& element)
    This function varies slightly depending on the tree container which it's called. For a tree, the immediate children are searched. The return result indicates it's success. For a multitree, the immediate children are searched, and all occurences of the object are erased. The return result indicates if any node was erased. For a unique_tree, all descendants are searched. The return result indicates it's success.
    Complexity: Logarithmic

Searching nodes

  • iterator find(const stored_type& element)
    Searches child nodes for the element. Returns an iterator pointing to the found node, or the end node if unsuccessful. There is a slight variances in the behavior of the multitree container. Since multitree can have multiple occurences in a single parent, the iterator will return a pointer to the first found occurrence, or the end iterator if not found. Remember that when searching nodes, the node_compare_type will determine the equality of the node that's being sought.
    Complexity: Logarithmic
  • const_iterator find(const stored_type& element) const
    Same as the above function, but returning a const_iterator rather than iterator.
    Complexity: Logarithmic
  • size_type count(const stored_type& element)
    Returns the number of element's within the nodes children. Does not search in descendants.
    Complexity: Logarithmic
  • iterator lower_bound(const stored_type& element)
    const_iterator lower_bound(const_stored_type& element) const
    Returns the first position where a copy of element would be inserted.
    Complexity: Logarithmic
  • iterator upper_bound(const stored_type& element)
    const_iterator upper_bound(const stored_type& element) const
    Returns the last position where a copy of element would be inserted.
    Complexity: Logarithmic
  • std::pair<iterator, iterator> equal_range(const stored_type& element)
    std::pair<const_iterator, const_iterator> equal_range(const stored_type& element) const
    Returns a pair which specify the first and last position where a copy of element would be inserted.
    Complexity: Logarithmic