The Tree Container Library

Modifying STL algorithms include algorithms which 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()
• copy()
• copy_backward()
• transform()
• swap_ranges()
• fill()
• fill_n()
• generate()
• generate_n()
• replace()
• replace_if()
• replace_copy()
• replace_copy_if()

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 modifying 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()

This algorithm was also demonstrated with the non-modifying algorithms. In this example, the algorithm will be used to modify the elements it traverses, by raising the rents of all rentals in the range. Here, the range will consist of all rentals in a particular building.

struct RaiseRent
{
   RaiseRent(double& _incr) : incr(_incr) {}

   void operator() (Rental& rental)
   {
      rental.setRentAmount(rental.getRentAmount() + incr);
   }

   double& incr;
}

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

   // find a specific rental building
   tcl::unique_tree<Rental>::iterator bldg_it = rentalTree.find_deep(Rental(73461));
   if ( bldg_it != rentalTree.end() ) {
      // raise rent for all units in building
      std::for_each(bldg_it.node()->begin(), bldg_it.node()->end(), RaiseRent(20.00));
   }

   return 0;
}

copy()

Although all four containers in the TCL include assignment operations, this algorithm can be very useful for copying a particular range, or for copying elements from STL containers to TCL containers, or vice-versa. The example below shows how all elements in a tree can be copied to a STL vector container. The order of the elements in the vector will depend on the type of descendant iterator used in the algorithm.

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

   std::vector<Rental> rentalVec;
   std::copy(rentalTree.pre_order_begin(), rentalTree.pre_order_end(), std::back_inserter(rentalVec));

   return 0;
}

copy_backward()

This algorithm is much like the algorithm above, but the source is traversed in reverse, and the third parameter specifies the end of the destination rather than the start. An example will not be given for this algorithm.

transform()

This algorithm has two forms. The first form performs an operation on each element of the range, and copies the elements to a destination range. The second form merges elements from two input ranges to an output range. A good application for this algorithm is shown below. Here we modify and copy all apartment units from one building to another. The modification involves changing the address of the units to reflect the new address of the destination building. Notice the example below inserts nodes into a destination node using std::back_inserter(). This iterator adapter accepts a reference to a container, which we supply by passing the dereferenced node() operation of the TCL iterator.

struct ChangeAddress
{
   ChangeAddress(const std::string& _newAddr) : newAddr(_newAddr) {}

   Rental operator() (Rental& rental)
   {
      // operations which change the address to the new address
      // operation returns a Rental object, which is copied to the dest
   }

private:
   const std::string& newAddr;
}

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

   // find source building
   tcl::unique_tree<Rental>::iterator src_it = rentalTree.find_deep(Rental(36745));

   if ( src_it != rentalTree.end() ) {
      tcl::unique_tree<Rental> dest_it = rentalTree.find_deep(Rental(39645));

      if ( dest_it != rentalTree.end()) {
         dest_it.node()->clear(); // clear current children from dest
         std::transform(src_it.node()->begin(), src_it.node()->end(), std::back_inserter(*it.node()), ChangeAddress());
      }
   }
}

swap_ranges

This algorithm does just what it's name inplies. An example is show below, which swaps the units of one building with another.

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

   // look for source building
   tcl::unique_tree<Rental>::iterator it1 = rentalTree.find_deep(23456);

   if (it1 != rentalTree.end()) {
      tcl::unique_tree<Rental>::iterator it2 = rentalTree.find_deep(56789);
      if (it2 != rentalTree.end()) {
         // swap units of first building with second
         std::swap_range(it1.node()->begin(), it1.node()->end(), it2.node()->begin());
      }
   }
}

fill(), fill_n()

This algorithm, along with fill_n(), is used with sequential containers. They can be used to fill nodes within a parent, with all the nodes containing the same element specified in the operation. An example will not be given of this algorithm.

generate(), generate_n()

This algorithm, along with generate_n() generates new child nodes within a parent node. A user defined operation can return the element to be inserted in the generated nodes. A very simple example is given below, which shows how generic units can be generated for a particular building. The example shows how the inserter iterator adapter can be used with TCL iterators.

struct GenRentals
{
   GenRentals(int _startRentalNo) : startRentalNo(_startRentalNo) {}

   Rental operator() () { return Rental(startRentalNo++); }
private:
   int startRentalNo;
}

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

   // insert new building.  Here, getNextRentalNo() returns the next issued rental number
   unique_tree<Rental>::iterator it = rentalTree.insert(getNextRentalNo());

   // insert 10 apt units in new building
   std::generate_n(std::inserter(*it.node(), it.node()->end()), 10, GenRentals(getNextRentalNo()));
}

replace(), replace_if(), replace_copy(), replace_copy_if()

These algorithms are very similar, and are more useful for sequence containers. An example will not be shown for these algoritms. An example is given, however, in the TCL Test Suite.