Outline
Other Material
Object-Oriented programming holds encapsulation as an ideal, bundling all actions in one place. Can make for ``fat'' classes.
The STL separates data structures and algorithms. The data structures are relatively small. The algorithms are many. Can be mixed and matched.
Allows for a much smaller class library.
By convention, containers return a starting value in response to begin(), and a past-the-end value in response to end().
For example, to shuffle a vector of values:
random_shuffle (aVector.begin(), aVector.end(), randomInteger);
To see what iterators must do, consider a typical algorithm:
template <class T>
iterator find
(iterator first, iterator last, T & value)
{
while (first != last && *first != value) ++first;
return first;
}
Could be used to find values in an array, or in a list:
int data[100]; ... int * where = find(data, data+100, 7); list<int>::iterator where = find(aList.begin(), aList.end(), 7);
What makes iterators possible is that all of these can be overloaded.
In C++ even the function call operator (parenthesis operator) can be overloaded. Allows for creation of objects that can be used like functions.
class biggerThanThree {
public:
bool operator () (int v)
{ return v > 3; }
};
Can be used to find the first value bigger than 3, for example.
Objects can take arguments computed at run-time, specialize functions in a way that simple functions cannot:
class biggerThan {
public:
biggerThan (int x) : testValue(x) { }
const int testValue;
bool operator () (int val)
{ return val > testValue; }
};
list<int>::iterator firstBig =
find_if (aList.begin(), aList.end(), biggerThan(12));
A business, WorldWideWidgetWorks, manufactures widgets.
class Widget {
public:
// constructors
Widget () : id_number (0) { }
Widget (int a) : id(a) { }
// operations
int id () { return id_number; }
void operator = (Widget & rhs)
{ id_number = rhs.id_number; }
bool operator == (Widget & rhs)
{ id_number == rhs.id_number; }
bool operator < (Widget & rhs)
{ id_number < rhs.id_number; }
protected:
int id_number; // widget identification number
};
Inventory is two lists - items on hand, items on back order.
class inventory {
public:
// process order for widget type wid
void order (int wid);
// receive widget of type wid
// in shipment
void receive (int wid);
protected:
list <Widget> on_hand;
list <int> on_order;
};
void inventory::receive (int wid)
// process a widget received in shipment
{ cout << "Received shipment of widget type " << wid << endl;
list<int>::iterator we_need =
find (on_order.begin(), on_order.end(), wid);
if (we_need != on_order.end()) {
cout << "Ship " << Widget(wid) << " to fill back order" << endl;
on_order.erase(we_need);
}
else
on_hand.push_front(Widget(wid));
}
void inventory::order (int wid)
// process an order for a widget with given id number
{ cout << "Received order for widget type " << wid << endl;
list<Widget>::iterator we_have =
find_if(on_hand.begin(), on_hand.end(), WidgetTester(wid));
if (we_have != on_hand.end()) {
cout << "Ship " << *wehave << endl;
on_hand.erase(we_have);
}
else {
cout << "Back order widget of type " << wid << endl;
on_order.push_front(wid);
}
}
Created like an instance of a class, works like a function.
class WidgetTester {
public:
WidgetTester (int id) : test_id(id) { }
int test_id;
// define the function call operator
bool operator () (Widget & wid)
{ return wid.id() == test_id; }
};
typedef map<string, int> stringVector;
typedef map<string, stringVector> graph;
string pendleton("Pendleton");
string pensacola("Pensacola");
string peoria("Peoria");
string phoenix("Phoenix");
string pierre("Pierre");
string pittsburgh("Pittsburgh");
string princeton("Princeton");
string pueblo("Pueblo");
graph cityMap;
cityMap[pendleton][phoenix] = 4;
cityMap[pendleton][pueblo] = 8;
cityMap[pensacola][phoenix] = 5;
cityMap[peoria][pittsburgh] = 5;
cityMap[peoria][pueblo] = 3;
cityMap[phoenix][peoria] = 4;
cityMap[phoenix][pittsburgh] = 10;
cityMap[phoenix][pueblo] = 3;
cityMap[pierre][pendleton] = 2;
cityMap[pittsburgh][pensacola] = 4;
cityMap[princeton][pittsburgh] = 2;
cityMap[pueblo][pierre] = 3;
struct DistancePair {
unsigned int first;
string second;
DistancePair() : first(0) { }
DistancePair(unsigned int f, string & s)
: first(f), second(s) { }
};
bool operator < (DistancePair & lhs, DistancePair & rhs)
{ return lhs.first < rhs.first; }
void shortestDistance(const graph & cityMap,
const string & start, stringVector & distances)
{
// process a priority queue of distances to cities
priority_queue<DistancePair, vector<DistancePair> ,
greater<DistancePair> > que;
que.push(DistancePair(0, start));
while (! que.empty()) {
// pull nearest city from queue
int distance = que.top().first;
string city = que.top().second;
que.pop();
// if we haven't seen it already, process it
if (0 == distances.count(city)) {
// then add it to shortest distance map
distances[city] = distance;
// and put values into queue
stringVector::iterator start, stop;
start = cityMap[city].begin();
stop = cityMap[city].end();
for (; start != stop; ++start)
que.push(DistancePair(distance + (*start).second,
(*start).first));
}
}
}
Given that the STL is not OO, does this mean that OOP is dead?
No, only that inspiration can come from a number of sources, and not all problems are best solved in an OOP fashion.
However, many problems ARE best approached in an OOP manner.
Bottom line - know as much as you can about as many styles of programming as you can, and use the style most appropriate to the problem.