Section 4 - A Brief Introduction to Algorithms
8B.4.1 Encapsulating insert(), et. al., into a Derived STL list Class
This section serves to introduce another C++ concept, algorithms. Of course, you've been using algorithms for a long time, but C++ algorithms are special tools that have a certain syntax and purpose. In short, they work on iterator ranges, and do useful things on those ranges.
We will reprise our FloatList example, this time using the C++ sort() algorithm. Before we start, I want to give you a streamlined version of our last FloatList that encapsulates the insert(), remove() and showList() in a class. The result is a main() that is very similar to our old client that drove the custom FloatList class. You can compare this not only with the most recent STL float list, but also the older custom FloatList class example from a few sections back.
// Demo of STL List of Floats using Inheritance
#include <iostream>
#include <list>
using namespace std;
typedef list<float> BaseFloatList;
class FloatList : public BaseFloatList
{
public:
void showList();
void insert(float x);
bool remove(float x);
};
// main method ---------------------------------------
int main()
{
FloatList myList;
int k;
float x;
// build list of 10 floats, 2 at a time (1 random and 1 k*100)
for (k = 0; k < 5; k++)
{
x = 1000 * (float)rand()/(float)RAND_MAX; // bet 0 and 1000
myList.insert(x);
myList.insert(k*100);
}
// should be sorted
myList.showList();
// remove 5 nodes (and delete them!)
for (k = 0; k < 5; k++)
{
x = k*100;
if (myList.remove(x))
cout << x << " removed\n";
else
cout << x << " not found.\n";
}
myList.showList();
if (!myList.remove(-10)) // should have no effect
cout << " -10 not in list as expected. ";
myList.showList();
return 0;
}
// FloatList method definitions --------------------------
void FloatList::insert(float x)
{
list<float>::iterator iter;
for ( iter = this->begin() ; iter != this->end() ; iter++ )
if ( x <= *iter )
break;
BaseFloatList::insert(iter, x);
}
bool FloatList::remove(float x)
{
for (list<float>::iterator iter = this->begin(); iter != this->end(); iter++)
if ( x == *iter )
{
BaseFloatList::remove(*iter);
return true;
}
return false;
}
void FloatList::showList()
{
cout << endl << "_____Here's the List_______" << endl;
for (list<float>::iterator iter = this->begin(); iter != this->end(); iter++)
{
cout.setf(ios::fixed);
cout.precision(3);
cout << "[" << *iter << "] ";
}
cout << endl << "_____That's all!_______" << endl << endl;
}
8B.4.2 STL Algorithms
We will not attempt a full lesson on STL algorithms as a complete study requires several new concepts including functionals and functors (function objects). However, the basic idea is easy and you can explore the available algorithms as needed.
STL contains a set of template functions called algorithms that we can think of as acting on generic classes. (In truth, they act on an iterator range, i.e., all the objects between a starting iterator and an ending iterator). We can make these algorithms work by simply #include-ing <algorithm> and using the algorithms with appropriate parameter lists.
The classic example is the for_each() algorithm, which takes a range (say, from some_list.begin() to some_list.end()) and a predicate function which is just the name of any function that we choose. The algorithm then invokes (applies) the predicate function to the range of objects in the list. The range can be inside a list, vector or even a simple array.
We pick our method FloatList::showList() as a candidate that can benefit from an application of for_each(). (In theory, all of the FloatList methods use loops and might be improved from a for_each() style upgrade, but we have better plans for insert() and remove(), so we focus only on showList()). Here is showList() as it is currently - the "before" picture, as it were:
void FloatList::showList()
{
cout << endl << "_____Here's the List_______" << endl;
for (list<float>::iterator iter = this->begin(); iter != this->end(); iter++)
{
cout.setf(ios::fixed);
cout.precision(3);
cout << "[" << *iter << "] ";
}
cout << endl << "_____That's all!_______" << endl << endl;
}
The loop can be replaced by a single for_each() with the application of the appropriate function, which we temporarily call showOneFloatFormatted():
void FloatList::showList()
{
cout << endl << "_____Here's the List_______" << endl;
for_each(this->begin(), this->end(), &showOneFloatFormatted);
cout << endl << "_____That's all!_______" << endl << endl;
}
To complete the work, we must define (actually we must have defined!) the ShowOneFloatFromatted() function.
void showOneFloatFormatted(float x)
{
cout.setf(ios::fixed);
cout.precision(3);
cout << "[" << x << "] ";
}
In other words, by placing the name of the function, without parens, into the third position of the for_each() algorithm, we are passing a function pointer (or reference, actually) to the algorithm. We have not done this before, but one can pass function pointers around just like other variables. We like to avoid it if we can, as this smacks of how the old C language used to deal with method encapsulation before C++ was invented. However, with the advent of function objects (overloading the () operator) and STL algorithms, this has become a common practice once again, if restricted to this special environment.
8B.4.3 Applying Algorithms and List Helpers to our FloatList
We wind up by applying an algorithm, find(), as well as a new list member method, sort() to our FloatList method implementations. This will reduce the detail work even more, completely removing the need to manually search the list.
The insert() method now reduces down to practically nothing, tempting us to do away with it entirely and call it from main(), but I won't do that. The remove() could be likewise reduced if we opted to change the signature to void, thus removing its ability to return information about whether the argument was found in the list. It then becomes a one line function. However, I have preserved our bool return type for remove() and demonstrated how we use the algorithm find() to detect and send back this information.
I have also applied the simpler showList() that uses for_each(), but instead of making showOneFloatFormatted() a global function, I have encapsulated it into the FloatList class as a static method.
There is a behavioral difference between our manual remove() of the previous incarnation and this new remove() that incorporates list::remove(). Can anyone figure out what that difference is by playing around or researching the subject?
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
typedef list<float> BaseFloatList;
class FloatList : public BaseFloatList
{
public:
void showList();
void insert(float x);
bool remove(float x);
static void showOneFloatFormatted(float x);
};
// main method ---------------------------------------
int main()
{
FloatList myList;
int k;
float x;
// build list of 10 floats, 2 at a time (1 random and 1 k*100)
for (k = 0; k < 5; k++)
{
x = 1000 * (float)rand()/(float)RAND_MAX; // bet 0 and 1000
myList.insert(x);
myList.insert(k*100);
}
// should be sorted
myList.showList();
// remove 5 nodes (and delete them!)
for (k = 0; k < 5; k++)
{
x = k*100;
if (myList.remove(x))
cout << x << " removed\n";
else
cout << x << " not found.\n";
}
myList.showList();
if (!myList.remove(-10)) // should have no effect
cout << " -10 not in list as expected. ";
myList.showList();
return 0;
}
// FloatList method definitions --------------------------
void FloatList::insert(float x)
{
// since list starts out sorted, this sort probably is not
// as inefficient as it looks. An alternative would be to
// use iterators to find the correct location where x needs
// to be inserted, but this requires functionals and a "compareTo()"
// style predicate - too advanced for this section.
this->push_front(x);
this->sort();
}
bool FloatList::remove(float x)
{
// there is no find() in STL list. we use C++ algorithm find().
// or, we can remove this block entirely and change remove()
// to void, stripping it of its ability to report back to client.
list<float>::iterator found;
found = find(this->begin(), this->end(), x);
if (found == this->end())
return false;
BaseFloatList::remove(x);
return true;
}
void FloatList::showOneFloatFormatted(float x)
{
cout.setf(ios::fixed);
cout.precision(3);
cout << "[" << x << "] ";
}
void FloatList::showList()
{
cout << endl << "_____Here's the List_______" << endl;
for_each(this->begin(), this->end(), &FloatList::showOneFloatFormatted);
cout << endl << "_____That's all!_______" << endl << endl;
}
I want to give a gigantic disclaimer at this point. While it seems as though we have tossed aside our hand-made and more detail-oriented class inheritance techniques (Node, FloatNode, List, FloatList) for the more automated and elegant template/stl approach (list<float> and sort(), find()), there are serious dangers lurking here. Most importantly is one of efficiency. Not development efficiency, but execution efficiency. Wantonly using built-in STL template classes and algorithms can lead to very long running times and resource drains. It is for this reason that all programmers, in an effort to become true computer scientists, master data structures and algorithm analysis. When that is done, one can evaluate these decisions objectively. But it takes some training, math and computer science courses. CS 2C is where that all happens.