3-4) Standard Template Library Examples

Standard Template Library
C++ general purpose library based on templates rather than inheritance and dynamic binding (for performance).
C++ community took a long time to accept a standard library. Those based on inheritance and dynamic binding were rejected by the C++ committee.

General Philosophy:
Containers with complexity guarantees (cost of insertion, retrieval, and deletion)
    Sequence containers: Vector, List, Deque
        -single type, linear sequence of elements
    Associative Containers: Set, Multiset, Map, Multimap
        -sorted, associative containers
        -allow fast retrieval of data based on keys
    All STL containers:
        -allocates and manages its own storage
        -have constructors for creating containers
        -provide member access functions
        -provide insertion and deletion member functions
 
template <class T, class Allocator = allocator>
class vector;		 fast random access
fast append
O(n) prepend, middle insert		 Array-like container
template <class T, class Allocator = allocator>
class list;		 O(n) sequential access
fast append, prepend, middle insert		 Linked List-type container
template <class T, class Allocator = allocator>
class deque;		 fast random access
fast append, prepend
O(n) middle insert		 Array-Like container open at both ends
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class set;		 fast retrival of key Set of unique keys
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class multiset;		 fast retrival of keys Set of possibly duplicate keys
template <class Key, class, T, class Compare = less<Key>, class Allocator = allocator>
class map;		 fast retrieval of value based on key Associates unique keys of type K with values of type T
template <class Key, class, T, class Compare = less<Key>, class Allocator = allocator>
class multimap;		 fast retrieval of values based on keys Associates possibly duplicate keys, of type K, with values of type T

The standard template library makes much use of function objects both in containers and in algorithms.
For example the function object less or greater is used to compare items when sorting is required either by a container such as set which keeps things in sorted order or an algorithm like sort which sorts elements of a sequential container.

Definition of less<T> used for compare objects (from Visual C++)

template<class _A1, class _A2, class _R>
     struct binary_function //#include <functional>
     {
         typedef _A1 first_argument_type;
         typedef _A2 second_argument_type;
         typedef _R result_type;
     };

template<class T>
    struct less : public binary_function<T, T, bool> {
    result_type operator()(const first_argument_type& x,
                           const second_argument_type& y) const;
    //i.e. bool operator()(const T& x, const T& y) const;
    };

less<T>::result_type less<T>::operator()(const less<T>::first_argument_type& x,
                               const less<T>::second_argument_type& y){
   return x < y;
}
 
 

Types common to all containers
X::value_type type of values the container holds
X::reference reference to value_type objects  (i.e. X::value_type &)
X::const_reference const X::value_type &
X::iterator iterator type for traversing elements of container
X::const_iterator iterator type for traversing constant elements of container
X::reverse_iterator iterator type for reverse traversal of container
X::const_reverse_iterator iterator type for reverse traversal of constant elements
X::difference_type type of the difference between to X::iterator types
X::size_type type that can represent the size of container X

Types for Associative Containers
X::key_type type of key with which X is created
X::key_compare type of  comparision object of X::key_type
X::value_compare type of comparison objects for X::value_type

Algorithms which operate on container elements without knowing the kind of container
Iterators to traverse container elements in a general way. Algorithms use iterators, so they don't directly know what kind of container is being traversed.
Utility classes: String, auto_ptr, locales
Standard Exception Classes.

The STL  uses advanced (more recent) features of C++ such as templates and exception handling.

Example 1: Basic Container, Algorithm, and Iterator


//STL example #1, Basic container, algorithm, iterator

#include <string>
#include <algorithm>
#include <vector>
#include <iostream.h>
 

class BankAccount {
 float balance_;
public:
 BankAccount (float amount = 0.0) : balance_(amount){}
 float balance() {return balance_;}
 void printOn(ostream & out) {out << "$ " << balance_;}
 bool operator<(BankAccount & b) {return (this->balance_ < b.balance_);}

};
ostream & operator<<(ostream & out, BankAccount & b) {
 b.printOn(out);
 return out;
}
istream & operator>>(istream & in, BankAccount & b) {
 int i;
 in >> i;
 b = BankAccount(i);
 return in;
}

//must be after BankAccount so ostream symbol conflict does not arrise
using namespace std;
int main ()
{
  vector<BankAccount> v;  // use STL vector of BankAccounts
  BankAccount input;
  cout << "enters integers/cr cntr d/cr to end \n";
  while (cin >> input) {   // while not end of file (<enter> ^d)

    v.push_back (input); //append to vector
  }
  // sort bank accounts using generic STL sort
  // sort uses two iterators to sort between

  sort(v.begin(), v.end());

  //use begin() and end() iterators to print contents of vector
  //end() refers to location one PAST the last element

  //notice below the container type is mentioned and not the actual class of
  //the iterator. (i.e. vector<T>::iterator)

  for(vector<BankAccount>::iterator itr = v.begin(); itr != v.end(); itr++)
   cout << *itr << "\n";

  return 0;
}

/*
enters integers/cr cntr d/cr to end
50
100
34
6000
.
$ 34
$ 50
$ 100
$ 6000
*/


//STL example #1B, Basic list container, and iterator
#include <list>

#include <iostream.h>
 

class BankAccount {
 float balance_;
public:
 BankAccount (float amount = 0.0) : balance_(amount){}
 float balance() {return balance_;}

 void printOn(ostream & out) {out << "$ " << balance_;}
 bool operator==(const BankAccount & b) {return (this->balance_ == b.balance_);}
 bool operator!=(const BankAccount & b)  {return (this->balance_ != b.balance_);}
 bool operator<(const BankAccount & b) {return (this->balance_ < b.balance_);}
 bool operator<=(const BankAccount & b) {return (this->balance_ <= b.balance_);}
 bool operator>(const BankAccount & b) {return (this->balance_ > b.balance_);}
 bool operator>=(const BankAccount & b) {return (this->balance_ >= b.balance_);}

};
ostream & operator<<(ostream & out, BankAccount & b) {
 b.printOn(out);
 return out;
}

bool getRidOf5(BankAccount  b) { return b == BankAccount(5);}

//must be after BankAccount so ostream symbol conflict does not arrise
using namespace std;
void main ()
{
//  vector<BankAccount> v;  // use STL list of BankAccounts

  list<BankAccount> accounts;

  int x=5,y=6,z=7;


  BankAccount b1(z);
  BankAccount b2(y);
  BankAccount b3(x);

  accounts.push_back(b1);
  accounts.push_back(b2);
  accounts.push_back(b3);


  list<BankAccount> accounts2;
  accounts2 = accounts;
  accounts2.merge(accounts);
 
  accounts.sort();


  
  //use begin() and end() iterators to print contents of vector
  //end() refers to location one PAST the last element

  //notice below the container type is mentioned and not the actual class of
  //the iterator. (i.e. list<T>::iterator)


  for(list<BankAccount>::iterator itr = accounts2.begin(); itr != accounts2.end(); itr++)
   cout << *itr << "\n";

  cout << "===\n";

  accounts2.remove(b1);

  for(list<BankAccount>::iterator itr2 = accounts2.begin(); itr2 != accounts2.end(); itr2++)
   cout << *itr2 << "\n";



}

/*
$ 7
$ 6
$ 5
$ 7
$ 6
$ 5
===
$ 6
$ 5
$ 6
$ 5
*/

//example using STL set keep in sorted order

#include <string>
#include <algorithm>
#include <set>
#include <iostream.h>
 

class BankAccount {
 float balance_;
public:
 BankAccount (float amount = 0.0) : balance_(amount){}
 float balance() {return balance_;}
 void printOn(ostream & out) {out << "$ " << balance_;}
 bool operator<(const BankAccount & b) const {return (this->balance_ < b.balance_);}
 //operator< must be of const type
 bool operator>(const BankAccount & b) const {return (this->balance_ > b.balance_);}
};
ostream & operator<<(ostream & out, BankAccount & b) {
 b.printOn(out);
 return out;
}
istream & operator>>(istream & in, BankAccount & b) {
 int i;
 in >> i;
 b = BankAccount(i);
 return in;
}

//must be after BankAccount so ostream symbol conflict does not arrise
using namespace std;
int main ()
{
  set<BankAccount> s;  // use STL set of BankAccounts
  set<BankAccount, greater<BankAccount> > s2;  // use STL set of BankAccounts
  BankAccount input;
  cout << "enters integers/cr cntr d/cr to end \n";
  while (cin >> input) {   // while not end of file (<enter> ^d)

    s.insert(input); //insert into set
 s2.insert(input);
  }
 

  //notice below the container type is mentioned and not the actual class of
  //the iterator. (i.e. vector<T>::iterator)

  for(set<BankAccount>::iterator itr = s.begin(); itr != s.end(); itr++)
   cout << *itr << "\n";
  for(set<BankAccount, greater<BankAccount> >::iterator itr2 = s2.begin(); itr2 != s2.end(); itr2++)
   cout << *itr2 << "\n";
 

  return 0;
}

/*
enters integers/cr cntr d/cr to end
400
50
2
36
1
.
$ 1
$ 2
$ 36
$ 50
$ 400
$ 400
$ 50
$ 36
$ 2
$ 1
*/


//STL example #3 Function objects used for comparison

#include <string>
#include <algorithm>
#include <vector>
#include <functional>  //to get less<T> and greater<T> in visual C++
                       //could also #include <set>
#include <iostream.h>
 

class BankAccount {
 float balance_;
public:
 BankAccount (float amount = 0.0) : balance_(amount){}
 float balance() {return balance_;}
 void printOn(ostream & out) {out << "$ " << balance_;}
 bool operator<(const BankAccount & b) const {return (this->balance_ < b.balance_);}
 //operator< must be of const type
 bool operator>(const BankAccount & b) const {return (this->balance_ > b.balance_);}
};

ostream & operator<<(ostream & out, BankAccount & b) {
 b.printOn(out);
 return out;
}
istream & operator>>(istream & in, BankAccount & b) {
 int i;
 in >> i;
 b = BankAccount(i);
 return in;
}

//must be after BankAccount so ostream symbol conflict does not arrise
using namespace std;

//function that does compare of bank accounts
bool isLessThan(const BankAccount & x, const  BankAccount & y) {
 return x < y;
}

//template function that compares two T objects
template <class T>
bool lessThan(const T & x, const  T & y) {
 return x < y;
}

// function object that does the compare
template <class T>
class lessThanFunctor{
public:
 bool  operator()(const T & x, const T & y) {
   return x < y;
    }
};

// binary_function function object to do compare
template <class T>
class binaryLessComparator : public binary_function<T,T, bool>{
public:
    result_type operator()( first_argument_type& x,
   second_argument_type& y) const {
     return x < y;
 }
};
 

int main ()
{
  vector<BankAccount> v;  // use STL vector of BankAccounts
  BankAccount input;
  cout << "enters integers/cr cntr d/cr to end \n";
  while (cin >> input) {   // while not end of file (<enter> ^d)

    v.push_back (input); //append to vector
  }
  // sort bank accounts using generic STL sort
  // sort uses two iterators to sort between

  // using ordinary function
  // sort(v.begin(), v.end(), isLessThan );

  // using template function -does not work in Visual C++ 6.0
  // sort(v.begin(), v.end(), lessThan<BankAccount> );

  // using a function object
  // sort(v.begin(), v.end(), lessThanFunctor<BankAccount>() );

  // using a function object based on binary_function struct
     sort(v.begin(), v.end(), binaryLessComparator<vector<BankAccount>::value_type>() );
 
 

  // Iteration
  //use begin() and end() iterators to print contents of vector
  //end() refers to location one PAST the last element

  //notice below the container type is mentioned and not the actual class of
  //the iterator. (i.e. vector<T>::iterator)

  for(vector<BankAccount>::iterator itr = v.begin(); itr != v.end(); itr++)
   cout << *itr << "\n";

  return 0;
}


//STL vectors stores copied objects
//Demonstration of the fact that the STL containers store object copies

#include <string>
#include <algorithm>
#include <vector>
#include <functional>  //to get less<T> and greater<T> in visual C++
                       //could also #include <set>
#include <iostream.h>
 

class BankAccount {
 float balance_;
public:
 BankAccount(void) :balance_(0.0) {cout << "BankAccount()\n";}
 BankAccount (float amount) : balance_(amount){}
 BankAccount (const BankAccount & b) {
  balance_  = b.balance_;
  cout << " copy constructor\n";
 }
 ~BankAccount(void) {cout << "BankAccount destructor\n";}
 float balance() {return balance_;}
 void printOn(ostream & out) {out << "$ " << balance_;}
 bool operator<(const BankAccount & b) const {return (this->balance_ < b.balance_);}
 //operator< must be of const type
 bool operator>(const BankAccount & b) const {return (this->balance_ > b.balance_);}
};

ostream & operator<<(ostream & out, BankAccount & b) {
 b.printOn(out);
 return out;
}
istream & operator>>(istream & in, BankAccount & b) {
 int i;
 in >> i;
 b = BankAccount(i);
 return in;
}

//must be after BankAccount so ostream symbol conflict does not arrise
using namespace std;

//function that does compare of bank accounts
bool isLessThan(const BankAccount & x, const  BankAccount & y) {
 return x < y;
}

//template function that compares two T objects
template <class T>
bool lessThan(const T & x, const  T & y) {
 return x < y;
}

// function object that does the compare
template <class T>
class lessThanFunctor{
public:
 bool  operator()(const T & x, const T & y) {
   return x < y;
    }
};

// binary_function function object to do compare
template <class T>
class binaryLessComparator : public binary_function<T,T, bool>{
public:
    result_type operator()( first_argument_type& x,
   second_argument_type& y) const {
     return x < y;
 }
};
 

int main ()
{
  vector<BankAccount> v;  // use STL vector of BankAccounts
  BankAccount b1 = 30;
  BankAccount b2 = 50;
  BankAccount b3 = 15;
  cout << "put accounts in vector\n";
  v.push_back (b1); //void push_back(const T& x)
  v.push_back (b2);
  v.push_back (b3);
  cout << "get accounts from vector\n";
  cout << v[0] << "\n";
  cout << b1 << "\n";
  if (&b1 == &v[0])
   cout << "vector returns same object"  << "\n";
  else
      cout << "vector returns copied object" << "\n";
  // using a function object based on binary_function struct
  //   sort(v.begin(), v.end(), binaryLessComparator<vector<BankAccount>::value_type>() );
 
 

  // Iteration
  //use begin() and end() iterators to print contents of vector
  //end() refers to location one PAST the last element

  //notice below the container type is mentioned and not the actual class of
  //the iterator. (i.e. vector<T>::iterator)
  cout << "iterating over vector\n";
  for(vector<BankAccount>::iterator itr = v.begin(); itr != v.end(); itr++)
   cout << *itr << "\n";

  return 0;
}

/* OUTPUT
put accounts in vector
 copy constructor
 copy constructor
 copy constructor
BankAccount destructor
 copy constructor
 copy constructor
 copy constructor
BankAccount destructor
BankAccount destructor
get accounts from vector
$ 30
$ 30
vector returns copied object
iterating over vector
$ 30
$ 50
$ 15
BankAccount destructor
BankAccount destructor
BankAccount destructor
BankAccount destructor
BankAccount destructor
BankAccount destructor
*/


//Generating values and transformations using STL generic algorithms
//and function objects

#include <string>
#include <algorithm>
#include <vector>
#include <functional>  //to get less<T> and greater<T> in visual C++
                       //could also #include <set>
#include <iostream.h>
 

class BankAccount {
 float balance_;
public:
 BankAccount(void) :balance_(0.0) {}
 BankAccount (float amount) : balance_(amount){}
 BankAccount (const BankAccount & b) {balance_  = b.balance_;}
 ~BankAccount(void) {}
 float balance() const {return balance_;}
 void printOn(ostream & out) {out << "$ " << balance_;}
 bool operator<(const BankAccount & b) const {return (this->balance_ < b.balance_);}
 //operator< must be of const type
 bool operator>(const BankAccount & b) const {return (this->balance_ > b.balance_);}
};

ostream & operator<<(ostream & out, BankAccount & b) {
 b.printOn(out);
 return out;
}
istream & operator>>(istream & in, BankAccount & b) {
 int i;
 in >> i;
 b = BankAccount(i);
 return in;
}

struct payInterest{
 float interest_rate;
 payInterest(float rate) : interest_rate(rate){}
 float operator() (const BankAccount & b) {
  return b.balance() * (1.0 + interest_rate);
 }
};

struct fibonacci{
 int i,j;
 fibonacci() : i(0), j(1){}
 float operator() (void) {
  int temp = i + j;
  i = j;
  j = temp;
  return temp;
 }
};

//must be after BankAccount so ostream symbol conflict does not arrise
using namespace std;
 
 

int main ()
{
  vector<BankAccount> v;  // use STL vector of BankAccounts
  vector<int> vfib(10);
  BankAccount b1 = 50;
  BankAccount b2 = 100;
  BankAccount b3 = 200;

  v.push_back (b1); //void push_back(const T& x)
  v.push_back (b2);
  v.push_back (b3);

  cout << "accounts before interest\n";
  for(vector<BankAccount>::iterator itr = v.begin(); itr != v.end(); itr++)
   cout << *itr << "\n";
 

  transform(v.begin(), v.end(), v.begin(), payInterest(10.0));

  cout << "accounts after interest\n";
  for(itr = v.begin(); itr != v.end(); itr++)
   cout << *itr << "\n";

  generate(vfib.begin(), vfib.end(), fibonacci());

  cout << "some fibonacci numbers\n";
  for(vector<int>::iterator itr2 = vfib.begin(); itr2 != vfib.end(); itr2++)
   cout << *itr2 << "  ";
  cout << "\n";
 
 
 

  return 0;
}

/* OUTPUT
accounts before interest
$ 50
$ 100
$ 200
accounts after interest
$ 550
$ 1100
$ 2200
some fibonacci numbers
1  2  3  5  8  13  21  34  55  89

*/