Download this source file

// An STL vector example.  In this program I will show many of the things
// that can be done to a vector.  This code *may* not work on older
// compilers.  In some cases they will work if you use non-standard
// header file names.
//
// Notes on vectors:
// The type of the elements of a vector must support (1) equality testing,
// (2) less-then testing, and (3) have a default value.  Note that pointers
// automatically support (1) and (3), but we will have to provide a
// less-then operation to support (2).  (If you create a vector of objects
// instead of object pointers, be sure to support operator==, operator<, and
// have a default constructor.)  If equality testing of pointers is not what
// you want (perhaps two objects are equal if they have the same name or
// id number), you must provide that too.
// The example was intended to show the use of lists not vectors, but in
// Borland C++ v5.02, you can't sort a list of object pointers!
//
// Notes on find:
// The find generic function takes three arguments: begin, end, and a value.
// It searches the vector for the first item that equals the value.
// As there is no way to say how to compare the value with another vector item,
// you must use the function "find_if" instead that does allow you to specify a
// function.  However, find_if doesn't allow you to specify the item to
// locate!  Instead, it returns the first item in the vector (or any container)
// that the function returns true on.  To make this work, you create a
// "function object".  The method is illustrated below, but if you want to
// use old-fashioned linked lists, or even an array you sort yourself, feel
// free to do so.  (This example is much more complicated than I had hoped!)
//
// (C) 1999 by Wayne Pollock, Tampa FL USA.  All Rights Reserved.

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>   // For sort, find, etc.

using namespace std;

class Person
{
	string name;
   int age;

public:
	Person ( string n, int a = 0 ) : name( n ), age( a ) {}
   int getAge() const { return age; }
   string getName() const { return name; }
   void setAge( int newAge ) { age = newAge; }
   void setName( string newName ) { name = newName; }

	// The following is used in sort.  It works, but is not efficient.  (The
	// preferred method is to use "function objects", see below!)
   // Note: the two arguments to less_than must be of the same type as your
   // vector elements.  This is easy to forget, and you get nasty, unhelpful
   // error messages if you use "... less_than(const Person&, const Person&)"!
   // Helpful tip:  You can use typedef to name the type, then use that
   // everywhere:  typedef Person* VectorType;
   //              vector< VectorType > people;
   //              ... less_then ( const VectorType p1, const VectorType p2);
   // The address of this static function is passed to sort like this:
   //              sort(people.begin(), people.end(), Person::less_than)
   static bool less_than ( const Person* p1, const Person* p2)
	{	return (p1->name < p2->name) ||                     // If names are the
             (p1->name == p2->name && p1->age < p2->age); // same, sort by age.
   }

   // The following function object is used in find_if.  In this case a member
   // function wouldn't work.  Here, a Person::Equal object is constructed
   // from a string.  When you pass a function object to any generic function
   // in the STL, it will invoke the operator() member function of that
   // object with one argument from your vector (or list or whatever).
   // You can always use a function object in place of a function address.
   class Equals
   {	string name;
   	public:
      	Equals( string n ) : name(n) {}
   		bool operator() (const Person* p1)
   		{	return (p1->getName() == name);
         }
   };
};

vector< Person* > people;  // people is a vector of Person pointers.

int main ()
{
	// Add some persons to the vector:
   people.push_back( new Person("Wayne", 41) );  // Add to end of vector.

   if ( people.empty() ) // Something must be wrong, there should be 1 person.
      cout << " error, people vector is empty!\n";

   // Add to front of vector:
   people.insert(people.begin(), new Person("Morty") );

   string name; int age;
   for (;;)
   {	cout << "Enter a name (no spaces) and age, end with EOF (^Z): ";
   	cin >> name >> age;
      if ( ! cin )  break;
      people.push_back( new Person(name, age) );
   }

   // Here's how to make a copy of a vector:
   vector< Person* > another_vector;
   another_vector = people;	 // You can also swap two vectors: v1.swap(v2);

   // Add a Person right after "Wayne".  First, locate Wayne:
   vector< Person* >::iterator it;  // There's also a ::const_iterater.
   it = find_if( people.begin(), people.end(), Person::Equals("Wayne"));

   if ( it == people.end() )			// This is how find indicates failure.
   	cout << "Wayne not found!\n"; // Probably should throw exception instead.

   // Next, insert a new Person in back of (just after) Person "Wayne":
   people.insert( it, new Person("Cher", 29) ); // insert is very flexible, you
                                                // can insert a whole vector!
   // The previous insert changed (*it) to point to "Cher".
   // Let's change it back:
   it = find_if( people.begin(), people.end(), Person::Equals("Wayne") );

   // Delete an element (or range of elements using two iterators):
   people.erase( it );  // Deletes person named "Wayne".

	// Lets sort the vector (note the use of a function pointer):
   sort( people.begin(), people.end(), Person::less_than );

	// Now print out the sorted vector.  Apparently a bug in Borland C++ 5.02
   // prevents string objects from printing correctly.  A work-around is:
   //     string s = "foo";  cout << setw(8) << s.c_str();
   cout << "\n\n\nName    Age\n";
   for ( it = people.begin(); it != people.end(); ++it )
   {	cout << left << setw(8);
   	cout << ((*it)->getName()).c_str() << " "; // Note tricky access!
      cout << right << setw(2);
      cout << (*it)->getAge() << endl; // (*it) is a Person*, not a Person.
   }

   // You can see the number of elements in a vector:
  	cout << "\nThe number of people is " << people.size() << endl;

	return 0;      // That's enough about vectors!
}

#ifdef COMMENT_SECTION

For the curious, here is how you can define a function object version of
less_then.  Note that either LessThan must be declared as a friend of Person,
or you must change p1->name to p1->getName(), etc.:

class Person
{
	...
   class LessThan
   {	public:
   		bool operator() (const Person* p1, const Person* p2)
   		{	return (p1->name < p2->name) ||
         			 (p1->name == p2->name && p1->age < p2->age);
         }
   };
};

And here is how you can use it.  (The parenthesis after LessThan invokes the
default constructor):

   sort( people.begin(), people.end(), Person::LessThan() );

The reason its better than a plain function is that the object function can be
expanded in-line, whereas you cannot expand in-line any function when you
have taken its address (say by passing a pointer to it).

#endif