The Tree Container Library

Nonmodifying STL algorithms include algorithms which do not modify the elements in the container, an include the algorithms in the list below. For a detailed description of these algorithms, please consult a STL source. A popular choice is The C++ Standard Library by Nicolai Josuttis.

• for_each()
• count()
• count_if()
• min_element()
• max_element()
• find()
• find_if()
• search_n()
• search()
• find_end()
• find_first_of()
• adjacent_find()
• equal()
• mismatch()
• lexicographical_compare()

As with all the STL algorithms, these algorithms can be used with either TCL child iterators or TCL descendant iterators. The for_each() operation can be especially useful. Indeed, before the TCL was STL compatible, all containers provided a for_each() member function. These member functions were removed after STL compatibility was achieved.

In the following examples, as well as all STL algorithm pages, objects of the following Rentalclass will be used for the TCL containers. In a practical example, Rental would serve as a base class for other real estate rental types, such as Property, Building, Unit, ParkingLot, and ParkingSpot. Only the full definition will be given for the Rental class.

class Rental
{
public:
   // constructors/destructor
   Rental(long _rentalNo) : rentalNo(_rentalNo), rentAmount(0.00), tenantNo(0) {}
   Rental(long _rentalNo, const std::string& _rentalName )
      : rentalNo(_rental_no), rentalName(_rentalName), rentAmount(0.00), tenantNo(0)  {}
   virtual ~Rental() {}

   // the < operator will be used to set the order in associative trees of this type
   // and also will be used for the sequential_tree sort() and sort_descendants() operations.
   friend bool operator <(const Rental& lhs, const Rental& rhs) const
        { return lhs.getRentalNo() < rhs.getRentalNo(); }

   // interface
   long getRentalNo() const { return rentalNo; }
   std::string getRentalName() const { return rentalName; }
   double getRentAmount() const { return rentAmount; }
   void setRentAmount(double _rentAmount) { rentAmount = _rentAmount; }
   bool isRented() const { return tenantNo > 0; }
   void leaseRental(long _tenantNo) { tenantNo = _tenantNo; }
   void vacateRental() { tenantNo = 0; }

private:
   // data
   long rentalNo;
   std::string rentalName;
   double rentAmount;
   long tenantNo;
};

The following examples illustrate how to use the nonmodifying algorithms, using the example classes above. Some operations may be called for illustrative purposes, such as populate_tree(). These operations are not implemented here, but are used only to convey that a populate operation is performed on the tree. It should be noted that all algorithms which return an iterator, return the same type of iterator which was used to specify the iterator range for that algorithm.

for_each()

When you need to perform a specific action on/for children or descendants of a node, this operation can make the work much easier. for_each() can actually be considered a modifying algorithm as well as a non-modifying algorithm. for_each() accepts an iterator range as the first two arguments, and a function pointer/object for the third argument. if using a function pointer with the algorithm, it must have the following signature.
void operation(const stored_type& element)
Here, stored_type is the type you are storing in each node of the tree. The function signature does not need to specify a const stored_type, but since we are illustrating it here on the non-modifying page, we will present it as such. The example below illustrates how we can calculate the basic net worth of the rentals.

struct getTotPossRent
{
   getTotPossRent(double& _total) : total(_total) {}

   operator()(const Rental& rental)
   {
      total += rental.getRentAmount();
   }

private:
   double& total;
};


int main(int argc, char* argv[])
{
   tcl::unique_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   double rentTot = 0.00;
   std::for_each(rentalTree.pre_order_begin(), rentalTree.pre_order_end(), getTotPossRent(rentTot));

   return 0;
}

count()

count() is a handy algorithm only if all the nodes in the tree are not unique. count(), by nature, would have no purpose being used for a unique_tree. Much more useful in these situations would be the algorithm, count_if, discussed further below. This algorithm will count the specified child nodes, if child iterators are used, and count the specified descendant nodes if descendant iterators are used. An example is shown below of the count() algorithm used with our example Rental class. Since every node in our Rental tree is unique, we would not ordinarily use the count() algorithm in this manner, but the example does show how to use the algorithm.

int main(int argc, char* argv[])
{
   // create and populate tree. (use a multitree in this example)
   tcl::multitree<Rental> rentalTree;
   populateRentals(rentalTree);

   // find descendant node with rental number = 45332
   int foundElements = std::count(rentalTree.post_order_begin(), rental_tree.post_order_end(), Rental(45332));

   return 0;
}

count_if()

The count_if() algorithm works much like count(). The difference is that with count_if() you can define the criteria in which an element will be counted. You do this by specifying a function pointer/object as the third parameter. A much more useful example for count_if() is shown below, which counts the vacant rentals.

struct checkForVacancy
{
   bool operator()(const Rental& rental) { return !rental.isRented(); }
};

int main(int argc, char* argv[])
{
   tcl::unique_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   int vacantRentals = std::count_if(rentalTree.pre_order_begin(), rentalTree.pre_order_end(), checkForVacancy());

   return 0;
}

min_element()

There are two forms of this algorithm. The first form accepts an iterator range, and uses the < operation to compare two elements. The second form accepts a third argument which specifies the comparison operation. Since the normal < operation for Rental compares the rental number of the two nodes, and that wouldn't be very useful to find the Rental with the lowest rental number, we will use the second form in this example. We'll use min_element() to find the rental with the lowest rent.

bool compRentAmt(const Rental& lhs, const Rental& rhs)
{
   return lhs.getRentAmount() < rhs.getRentAmount();
}


int main(int argc, char* argv[])
{
   tcl::tree<Rental> rentalTree;
   populateRentals(rentalTree);

   tcl::tree<Rental>::iterator it = std::min_element(rentalTree.pre_order_begin(), rentalTree.pre_order_end(), compRentAmt);
   double minRent = it->getRentAmount();

   return 0;
}

max_element()

The max_element() algorithm works much like min_element(). Below, we will use the second form of this algorithm to find the rental with the highest rent. Here, we'll use a function object instead of a binary predicate function.

struct compRentAmt
{
   bool operator()(const Rental& lhs, const Rental& rhs) { return lhs.getRentAmount() < rhs.getRentAmount(); }
}

int main(int argc, char* argv[])
{
   tcl::unique_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   tcl::unique_tree<Rental>::iterator it = std::max_element(rentalTree.pre_order_begin(), rentalTree.pre_order_end(), compRentAmt());
   double maxRent = it->getRentAmount();

   return 0;
}

find()

This algorithm is very handy for sequential_tree, which doesn't have it's own find() member operation. It's also handy for the associative trees. Even though the associative trees have their own find() operation, this operation searches only the immediate children of a node. The STL find() algorithm can search all descendants of a node, by using descendant iterators. Unfortunately, the complexity of this algorithm is linear. The examples below show how this algorithm is used for TCL containers.

int main(int argc, char* argv[])
{
   tcl::sequential_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   // find rental 3479
   tcl::sequential_tree<Rental>::pre_order_iterator it
          = std::find(rentalTree.pre_order_begin(), rentalTree.pre_order_end(),  Rental(3479));
   if (it != rentalTree.pre_order_end()) {
      it->leaseRental(1234); // found rental, lease out to tenant 1234
   }

   return 0;
}

find_if()

Find if gives more versatility than the find() algorithm, as it allows the user to specify the find criteria. The example below makes use of the find_if() algorithm, by finding a rental with a specific name. A function object will be used in this example, although a predicate function can also be used.

struct chkRentalName
{
   chkRentalName(const std::string& _rentalName) : rentalName(_rentalName) {}

   bool operator() (const Rental& rental) const { return rental.getRentalName() == rentalName; }

   private:
      std::string& rentalName;
}

int main(int argc, char* argv[])
{
   tcl::unique_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   // find rental with name "Fenlon Place"
   tcl::unique_tree<Rental>::pre_order_iterator it = std::find_if(
            rentalTree.pre_order_begin(), rentalTree.pre_order_end(), chkRentalName("Fenlon Place"));
   if ( it != rentalTree.pre_order_end()) {
      it->leaseRental(1234);
   }

   return 0;
}

search_n()

This algorithm searches for the first consecutive n elements which match a value, or particular criteria. There are two forms, with the second form accepting a binary predicate used for the comparison of the operation. Although not a widely used algorithm, it may have it's use, as shown in the example below, which defines a function to find n consecutive rentals under xxx.xx dollars. Because the request comes from a party which would like the adjoining rentals in the same building, we must perform the algorithm on child nodes rather than descendant nodes. We will used descendant nodes, however, to iterate over all the building nodes to perform the algorithm on.

bool rentAmtLessThan( const Rental& lhs, const Rental& rhs)
{
   return lhs.getRentAmount() < rhs.getRentAmount();
}

// function finds n consecutive rentals in the same building less than the specified amount
// returns an iterator pointing to the first element matching the criteria, or end()
typename tcl::unique_tree<Rental>::iterator findnConsecutiveUnitsUnderAmt(unique_tree<Rental>& rentalTree, const int n, const double amount)
{
   // create a level order iterator to span rental hierarchy
   tcl::unique_tree<Rental> lvl_it = rentalTree.level_order_begin();
   for ( ; lvl_it != rentalTree.level_order_end(); ++lvl_it ) {
      // use search_n() on this node to find n consecutive child elements matching the criteria
      tcl::unique_tree<Rental>iterator it = std::search_n(lvl_it.node()->begin(), lvl_it.node()->end(), rentAmtLessThan );
      if ( it != lvl_it.node()->end()) // check if n elements found
         return it;   // found them
   }

   // not found.  return end element of the node which this was called on
   return rentalTree.end();
}

search()

This algorithm searches for a subset range. The subset range can be a range from either STL containers or TCL containers. One good application of this algorithm to check if a sub-range of a node is the same condition as another, as shown in the example below.

struct chkRentalName
{
   chkRentalName(const std::string& _rentalName) : rentalName(_rentalName) {}

   bool operator() (const Rental& rental) const { return rental.getRentalName() == rentalName; }

   private:
      std::string& rentalName;
}

int main(int argc, char* argv[])
{
   // create and populate first rental tree
   tcl::unique_tree<Rental> rentalTree1;
   populateRentals(rentalTree1);

   // create and populate second rental tree
   tcl::unique_tree<Rental> rentalTree2;
   populateAltRentals(rentalTree2);

   tcl::unique_tree<Rental>::const_iterator srch_it = rentalTree1.find_deep(Rental(14678));
   if ( srch_it != rentalTree1.end() ) {
      // found specified rental in rental tree 1
      tcl::unique_tree<Rental>::pre_order_iterator it
          = std::search(rentalTree2.pre_order_begin(), rentalTree2.pre_order_end(),
              srch_it.node()->pre_order_begin(), srch_it.node()->pre_order_end(), chkRentalName);

      if ( it != rentalTree2.pre_order_end() ) {
         // perform action on found range
      }
   }

   return 0;
}

find_end()

This algorithm is very much like the search() algorithm described above, but finds the last range subset. This algorithm was plainly ill-named as it does not conform to the naming scheme of it's counterpart algorithm. An example will not be given for this algorithm, as it so closely resembles the search() algorithm described above.

find_first_of()

This algorithm finds the first element which is also in the specified search range. The following example uses this algorithm to nd a rental in one tree which has the same name as a rental in a sub-range of another tree.

struct chkRentalName
{
   chkRentalName(const std::string& _rentalName) : rentalName(_rentalName) {}

   bool operator() (const Rental& rental) const { return rental.getRentalName() == rentalName; }

   private:
      std::string& rentalName;
}

int main(int argc, char* argv[])
{
   // create and populate first rental tree
   tcl::unique_tree<Rental> rentalTree1;
   populateRentals(rentalTree1);

   // create and populate second rental tree
   tcl::unique_tree<Rental> rentalTree2;
   populateAltRentals(rentalTree2);

   tcl::unique_tree<Rental>::const_iterator srch_it = rentalTree1.find_deep(Rental(14678));
   if ( srch_it != rentalTree1.end() ) {
      // found first rental in rental tree 2 which is also in the sub-range
      tcl::unique_tree<Rental>::pre_order_iterator it =
          std::find_first_of(rentalTree2.pre_order_begin(), rentalTree2.pre_order_end(),
              srch_it.node()->pre_order_begin(), srch_it.node()->pre_order_end(), chkRentalName);

      if ( it != rentalTree2.pre_order_end() ) {
         // perform action on found rental
      }
   }

   return 0;

}

adjacent_find()

This algorithm finds the first occurrence of two adjacent elements in a specified range. It has two forms, with the second form accepting a binary predicate as the third argument which specifies the criteria used to compare adjacent elements. The example function below uses this algorithm to find the first n rental elements which are both vacant and below a specified rent amount. To make this function practical, it should return only adjacent rental units which are in the same building, so we will use this algorithm with child iterators rather than descendant iterators, and use descendant iterators to traverse the building nodes.

struct ChkAvailableBelowAmt
{
   ChkAvailableBelowAmt(double& _maxAmount) : maxAmount(_maxAmount) {}

   bool operator ()(const Rental& lhs, const Rental& rhs)
   {
      return !(lhs.isRented() || rhs.isRented()) && lhs.rentAmount < maxAmount && rhs.rentAmount < maxAmount;
   }

   double& maxAmount;
}

iterator findAdjoiningVacantUnits(unique_tree<Rental>& rentalTree, const double maxRent)
{
   tcl::unique_tree<Rental>::level_order_iterator lvl_it = rentalTree.level_order_begin();
   for ( ; it != rentalTree.level_order_end(); ++lvl_it ) {
      tcl::unique_tree<Rental>::iterator it = std::adjacent_find(lvl_it.node()->begin(), lvl_it.node()->end(), ChkAvailableBelowAmt(maxRent));
      if ( it != lvl_it.node()->end() )
         return it;  2 adjacent nodes found
   }

   return rentalTree.end();  // no two adjacent nodes found

equal()

This algorithm checks two ranges for equality. Although all of the TCL tree containers contain an equality operator, this operator only allows the checking of equality of two nodes, which also checks the nodes's descendants. This algorithm can check a specified range, plus allows the compare range to be a range in another TCL container or STL container. The following example illustrates how this algorithm can be used to check if a range of elements in a std::set is equal to the range of elements in a particular rental node.

int main(int argc, char* argv[])
{
   std::set<Rental> rentalSet;
   populateRentalSet(rentalSet);

   tcl::unique_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   tcl::unique_tree<Rental>::iterator srch_it = rentalTree.find_deep(Rental(28462));
   if ( it != rentalTree.end() ) {
      bool isEqual = std::equal(srch_it.node()->begin(), srch_it.node()->end(), rentalSet.begin());
      if (isEqual) {
         // perform some ops on range
      }
   }

   return 0;
}

mismatch()

This algorithm finds the first mismatch while comparing 2 ranges of elements. The example below serves no useful purpose, but shows how this algorithm works.

struct CmpRentAmt
{
  bool operator()(const Rental& lhs, const Rental& rhs) const { return lhs.getRentAmount() < rhs.getRentAmount(); }
}

int main(int argc, char* argv[])
{
   tcl::sequential_tree<Rental> rentalTree;
   populateRentals(rentalTree);

   // create a duplicate of the first tree container
   tcl::sequential_tree<Rental> dupRentalTree(rentalTree);

   // use std::find() to find a specific rental in the tree
   tcl::sequential_tree<Rental>::pre_order_iterator change_it = std::find(dupRentalTree.pre_order_begin(), dupRentalTree.pre_order_end(), Rental(2345));
   if ( change_it != dupRentalTree.pre_order_end() ) {
      change_it->setRentAmount(change_it->getRentAmount + 100.00); // change the rent amount for this rental

      // now scan both trees for the first mismatch
      assert( std::mismatch(rentalTree.post_order_begin(), rentalTree.post_order_end(),
          dupRentalTree.post_order_begin(), dupRentalTree.post_order_end(), CmpRentAmt()).first->getRentalNo() == 2345);
   }

   return 0;
}

lexicographical_compare()

Although all four TCL containers contain a < operation which compares two trees or nodes lexicographically, this operation can be handy if you need to test a range of elements, rather than testing all the descendants of two particular nodes. No example will be given for this algorithm.