These problems will give you some experience using components of the STL other than the containers. (http://www.sgi.com/tech/stl is a handly online reference to the STL.)

1. Consider the following program fragment, where you have a choice of four possible statements in the main function.

   	void f1(string& s)
   	{
   	    if (s.empty())
   	        s = "EMPTY";
   	}
   
   	string f2(string s)
   	{
   	    return s.empty() ? "EMPTY" : s;
   	}
   
   	struct F3
   	{
   	    F3(list<string>::iterator p) : it(p) {}
   	    string operator()()
   	    {
   	        string s = *it++;
   	        return s.empty() ? "EMPTY" : s;
   	    }
   	    list<string>::iterator it;
   	};
   
   	int main()
   	{
   	    list<string> a;
   	    ... fill a with some values, then do one of the following ...
   	    /* 1 */ for_each(a.begin(), a.end(), f1);
   	    /* 2 */ transform(a.begin(), a.end(), a.begin(), f2);
   	    /* 3 */ generate(a.begin(), a.end(), F3(a.begin()));
   	    /* 4 */ replace_if(a.begin(), a.end(), mem_fun_ref(&string::empty), "EMPTY");
   	    ...
   	}
   

   What interesting (well, interesting in a nerdy sort of way) observation can be made about the four choices?

2. For the parts of this problem, you may not write any loops or recursive functions, and you may not write code that is just an unwinding of a loop or recursion, such as

   	double t = 0;
   	t += p[0];
   	t += p[1];
   	t += p[2];
   

   Simplification: Since we haven't talked about std::iterator_traits<Iter>::value_type, you may have a tough time obeying the requirement above for part c. So for part c, you may write a loop. If you're ambitious enough to do a little research, see if you can do part c without writing a loop.

   If you need to use an STL algorithm that requires that a function be passed to it, pass a function object instead of a pointer to a function. (Hint: the header <numeric> defines the inner_product algorithm, which should be the only STL algorithm you need for the parts of this problem.)

   1. Suppose p is an array of n doubles representing the coordinates of a point in n-space. (If n is 2, these are the customary (x,y)-coordinates; if n is 3, (x,y,z)-coordinates, etc.) Replace expr with an expression that computes the Euclidean distance from p to the origin:

      	double distance_from_origin(double p[], int n) // Assume p has n elements
      	{
      	   return expr;
      	}
      

   2. Write a function name dist that takes two points in n-space (as in part a above) and returns the Euclidean distance between them. (You'll need to declare a functor class and/or use one already in the library.)

   3. Implement a template function named count_matches that takes three parameters: the first two denote a range in one sequence, and the third is an iterator pointing to the beginning of a sequence that must be at least as long as the first sequence (you don't have to check for that). The function returns the number of corresponding positions in the two sequences where the items are equal. For example,

      	list<int> a;
      	a.push_back(10); a.push_back(30); a.push_back(20); a.push_back(40);
      	int b[4] = { 10, 90, 30, 40 };
      	assert(count_matches(a.begin(), a.end(), b) == 2);  // 10 and 40
      	assert(count_matches(b+1, b+4, a.begin()) == 1);    // 30
      	assert(count_matches(b+2, b+3, a.begin()) == 0);
      

   4. Implement a template function named count_matches that takes four parameters: the first two denote a range in one sequence, the third is an iterator pointing to the beginning of a sequence that must be at least as long as the first sequence (you don't have to check for that), and the last is a binary predicate. The function returns the number of corresponding positions in the two sequences for which the predicate returns true when called with the item at that position in the first sequence as its first argument, and the item at that position in the second sequence as its second argument. For example,

      	list<int> a;
      	a.push_back(10); a.push_back(30); a.push_back(20); a.push_back(40);
      	int b[4] = { 10, 90, 30, 40 };
      	assert(count_matches(a.begin(), a.end(), b, less<int>()) == 2);
      	        // 30 < 90 and 20 < 30
      

3. David Letterman has announced the topic of a Top Ten list and invited his audience to send in gag lines. Each gag is assigned a funniness ranking (a double between 0 (unfunny) and 100 (hilarious), inclusive). Your job is to find the ten funniest gags, ranked in order from least funny of the ten to most funny. Here's the (simplified) Gag type:

   	struct Gag
   	{
   	   Gag(string t, double f) : text(t), funniness(f) {}
   	   string text;
   	   double funniness;
   	};
   

   Here's what you are to do:

   1. Declare vector of Gags and populate it with 100,000 Gags, using an STL algorithm that calls a function or function object to generate each Gag. In the real world, this function would take an envelope from the mailbag and return a Gag constructed from the information in the viewer's letter and a writer's rating of the funniness. What you will do instead is generate a random string of 6 lower case letters as the text, and a random double in the range 0 through 100 as the funniness.

   2. Output the text and funniness of the ten funniest Gags, in order from least funny to most funny, e.g.,

      	10. bwyqzx 99.9987
      	 9. ypfuie 99.9989
      	 8. aehhsw 99.9991
      	 7. pewigb 99.9991
      	 ...
      	 1. pchedj 99.9998
      

      If two gags have the same funniness, their relative order is irrelevant.

   Try to write as few loops as possible; with appropriate use of functors and careful selection of algorithms, you can solve this without writing any loops at all. Don't do significantly more computation than necessary.

4. The following is a skeleton of a solution to Jolly Jumpers. Finish the solution, subject to the following caveat: You may not write any loops other than the one shown, and may not write any recursive functions. You may add headers, functions, and functor classes if you need to.

   	#include <iostream>
   	#include <sstream>
   	#include <string>
   	#include <vector>
   	#include <algorithm>
   	#include <iterator>
   	
   	using namespace std;
   	
   	int main()
   	{
   	    int n;
   	    while (cin >> n)
   	    {
   		vector<int> v;
   		v.reserve(n);  // not necessary, just a minor optimization
   		string s;
   		getline(cin,s);
   		istringstream iss(s);
   		copy(istream_iterator<int>(iss), istream_iterator<int>(),
   							back_inserter(v));
   		  // Now v has all the integers on the input line (except the
   		  // count).
   
   		// You finish it
   	    }
   	}
   

Turn it in

Turn in this homework at the CS 188 submission site. Turn in a Word document or a text file that contains your solutions to the homework problems.