The Tree Container Library

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