The Standard Template Library
Part of the C++ standard. The most important example for generic programming.
Generic programming: make more abstract routines without loosing efficiency
using parameterization (both data and algorithm).
Motivation:
int t[] = { 1, 3, 5, ... };
// find the first occurance of a value
int *pi = find( t, t+sizeof(t)/sizeof(t[0]), 55);
if ( pi )
{
*pi = 56;
}
A very specific implementation:
int *find( int *begin, int *end, int x)
{
while ( begin != end )
{
if ( *begin == x )
{
return begin;
}
++begin;
}
return 0;
}
Step1: generalization on type int -> T
template <typename T>
T *find( T *begin, T *end, const T& x)
{
while ( begin != end )
{
if ( *begin == x )
{
return begin;
}
++begin;
}
return 0;
}
Step2: Generalization on data structure
template <typename It, typename T>
It find( It begin, It end, const T& x)
{
while ( begin != end )
{
if ( *begin == x )
{
return begin;
}
++begin;
}
return end; // not 0
}
Uniform usage
int t[] = { 1, 3, 5, ... };
int *pi = find( t, t+sizeof(t)/sizeof(t[0]), 55);
if ( pi )
{
*pi = 56;
}
vector<int> v;
v.push_back(1); v.push_back(3); v.push_back(5); ...
vector<int>::iterator vi = find( v.begin(), v.end(), 55);
if ( vi != v.end() )
{
*vi = 56;
}
list<double> l;
l.push_back(1.1); l.push_back(3.3); l.push_back(5.5); ...
list<double>::iterator li = find( l.begin(), l.end(), 55.55);
if ( li != l.end() )
{
*li = 56.66;
}
Constant safety:
const int t[] = { 1, 3, 5, ... };
const int *pi = find( t, t+sizeof(t)/sizeof(t[0]), 55);
if ( pi )
{
// *pi = 56; Syntax error
cout << *pi;
}
vector<int> v;
v.push_back(1); v.push_back(3); v.push_back(5); ...
const list<double> cl( v.begin(), v.end());
list<double>::const_iterator cli = find( cl.begin(), cl.end(), 55.55);
if ( cli != cl.end() )
{
// *cli = 56.66; Syntax error
cout << *cli;
}
Be care: const_iterator != const iterator
More generalization. Find the 3rd occurance:
list<double> l; ...
list<double>::iterator li;
li = find( l.begin(), l.end(), 3.14);
li = find( li, l.end(), 3.14);
li = find( li, l.end(), 3.14);
// or:
li = find(find(find(l.begin(),l.end(),3.14),l.end(),3.14),l.end(),3.14);
It is obvious that this way there is a limitation. We have to change our
strategy here. Find the third element whis is less than 55.
template <typename It, typename Pred>
It find_if( It begin, It end, Pred p)
{
while ( begin != end )
{
if ( p(*begin) )
{
return begin;
}
++begin;
}
return end;
}
// Pred1: not too good
bool less55_3rd( int x)
{
static int cnt = 0;
if ( x < 55 )
++cnt;
return 3 == cnt;
}
vector<int> v; ...
vector<int>::iterator = find_if( v.begin(), v.end(), less55_3rd);
vector<int>::iterator = find_if( v.begin(), v.end(), less55_3rd); // ??
// Pred2
struct less55_3rd
{
less55_3rd() : cnt(0) { }
bool operator()(int x)
{
if ( x < 55 )
++cnt;
return 3 == cnt;
}
private:
int cnt;
};
vector<int> v; ...
less55_3rd pp;
vector<int>::iterator = find_if( v.begin(), v.end(), pp);
// or:
vector<int>::iterator = find_if( v.begin(), v.end(), less55_3rd());
// Pred3: more generic
template <typename T>
struct less_nth
{
less_nth( const T& t, int n) : t_(t), n_(n), cnt_(0) { }
bool operator()(const T& t)
{
if ( t < t_ )
++cnt;
return n_ == cnt;
}
private:
T t_;
int n_;
int cnt_;
};
vector<int> v; ...
vector<int>::iterator = find_if(v.begin(),v.end(),less_nth<int>(55,3));
Bit in longer term, it is better to avoid predicates with state.