Write an analysis function to call optimistic_median.
This is covered under my Solution to Exercise 6-0 (Part 5 / 7). The analysis function is called optimistic_median_analysis (stored in the source file optimistic_median_analysis.cpp). It essentially parses the (pointer or memory address of the) optimistic_median function as an argument to another (transform) function. For this to work the optimistic_median function must not be overloaded.
Correct the program you wrote in the previous exercise to copy from u into v. There are at leaset two possible ways to correct the program. Implement both, and describe the relative advantages and disadvantages of each approach.
In the previous exercise (See my Solution to Exercise 6-3), it contains the following statement which will crash the system due to attempt to copy additional elements to an empty vector without dynamically growing the vector size up-front (with the like of back_inserter or inserter).
copy(u.begin(), u.end(), v.begin());
As we have already mentioned, we can fix this by using back_inserter or inserter to grow the vector size dynamically.
copy(u.begin(), u.end(), back_inserter(v));
copy(u.begin(), u.end(), inserter(v, v.begin()));
This table summarises my “educational guess” regarding relative advantages and disadvantages of back_inserter and inserter in the context of being used within the copy function.
| back_inserter | inserter | |
| Advantages | Relatively faster element appending (to the back of the base vector) as this is what it is designed to do. | capable of inserting elements at the beginning or middle of the base vector. |
| Disadvantages | Not capable of inserting elements at the beginning or middle of the base vector. | Relatively slower element appending (to the back of the base vector) as it is designed for flexibility over performance. |
We can perform a test by submitting the following program.
#include <iostream> // cout, endl
#include <vector> // vector
#include <algorithm> // copy
using std::vector;
using std::cout;
using std::endl;
int main()
{
vector<int> u(10, 100);
cout << "vector<int> u looks like this:" << endl;
for (vector<int>::const_iterator i = u.begin(); i != u.end(); ++i)
cout << (*i) << endl;
vector<int> v1;
copy(u.begin(), u.end(), back_inserter(v1)); // use back_inserter to grow v
cout << "vector<int> v1 looks like this (back_inserter):" << endl;
for (vector<int>::const_iterator i = v1.begin(); i != v1.end(); ++i)
cout << (*i) << endl;
vector<int> v2;
copy(u.begin(), u.end(), inserter(v2, v2.begin())); // use inserter to grow v2
cout << "vector<int> v2 looks like this (inserter):" << endl;
for (vector<int>::const_iterator i = v2.begin(); i != v2.end(); ++i)
cout << (*i) << endl;
return 0;
}
Submitting the Revised Program gives us the following, which is as expected (and resolved the system crash issue discovered in previous exercise).
vector<int> u looks like this: 100 100 100 100 100 100 100 100 100 100 vector<int> v1 looks like this (back_inserter): 100 100 100 100 100 100 100 100 100 100 vector<int> v2 looks like this (inserter): 100 100 100 100 100 100 100 100 100 100
What does this program fragment do?
vector<int> u(10, 100) vector<int> v; copy(u.begin(), u.end(), v.begin());
Let’s look at the 3 lines one-by-one.
Starting with the first line:
vector<int> u(10, 100);
This statement creates a vector<int> container named u. It allocates system memory and give the container a size of 10 as defined by the first argument (i.e. having the ability to store 10 int elements), and immediately create 10 int elements each has an initial value of 100, as defined by the second argument. i.e. We expect u to contains 10 int elements, each has a value of 100.
I can test this out easily via a simple program like this:
#include <iostream> // cout, endl
#include <vector> // vector
using std::vector;
using std::cout;
using std::endl;
int main()
{
vector<int> u(10, 100);
for (vector<int>::const_iterator i = u.begin(); i != u.end(); ++i)
cout << (*i) << endl;
return 0;
}
Running this program gives the followings as expected.
100 100 100 100 100 100 100 100 100 100
Note that if I change the statement slightly to instead:
vector<int> u(10);
This statement would create 10 elements for u with the default initial value of 0 (determined by the <int> part).
This second line is very easy:
vector<int> v;
This statement creates a vector<int> container v with no elements (and a size of zero).
Now the third line:
copy(u.begin(), u.end(), v.begin());
Though at first sight this statement appears to copy all the elements from the vector<int> container u, to the beginning of the empty vector<int> container v, this line will crash the program. Why? Because v initially has zero elements and has a container size of zero. In order to copy additional elements to this empty container v, we must first have a means to grow the container size dynamically by using utilities like back_inserter or inserter (page 121 of the book). In fact, in the next Exercise we shall correct this program using these utilities.
For now, let me illustrate that running the following program as it is will indeed crash the system:
#include <iostream> // cout, endl
#include <vector> // vector
#include <algorithm> // copy
using std::vector;
using std::cout;
using std::endl;
int main()
{
vector<int> u(10, 100);
cout << "vector<int> u looks like this:" << endl;
for (vector<int>::const_iterator i = u.begin(); i != u.end(); ++i)
cout << (*i) << endl;
vector<int> v;
//copy(u.begin(), u.end(), v.begin()); // program crashes!
cout << "vector<int> v looks like this:" << endl;
for (vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
cout << (*i) << endl;
return 0;
}
Program crashes! (on my Vista system it gives a return code of -1073741819 (0xC0000005) )
This exercises illustrates that in order for the copy function to work, we must have a means to grow the vector dynamically, such as using the utilities back_inserter or inserter, as we shall see in my Solution to Exercise 6-4.
Write a program to test the find_urls function.
This is covered under my Solution to Exercise 6-0 (Part 4 / 7).
Reimplement the frame and hcat operations from S5.8.1/93 and $5.8.3/94 to use iterators.
The ask for this exercise is to reimplement the frame.cpp and hcat.cpp (as seen in Chapter 5 / my Solution to Exercise 5-0 (Part 3/3)), from index-base access iterator-base access.
I personally think this is a very good exercise to enable us to practice a bit on accessing vector elements by either index or iterator. This is summarised by the diagram below:
Bearing this in mind, it is in fact not that difficult, to convert frame and hcat operations from using index to iterators.
All the source and header files are essentially the same as my Solution to Exercise 5-0 (Part 3/3). In this exercise we, however, amend the frame.cpp and hcat.cpp to use iterator (instead of using index). I have also updated the main.cpp to enable us to test out the change easily. (i.e. use the Project structure as per Exercise 5-0 (Part 3/3) but use the new main.cpp, frame.cpp, and hcat.cpp. Then run the program to test.
#include <iostream> // cin, cout, endl, getline
#include <vector> // vector
#include <string> // string
#include "frame.h" // frame
#include "hcat.h" // hcat
#include "vcout.h" // vcout
using std::cin;
using std::cout;
using std::endl;
using std::getline;
using std::string;
using std::vector;
int main()
{
string s; // line
vector<string> p; // paragraph
// read multiple lines to make a paragraph
while (getline(cin, s))
p.push_back(s);
// have a play, manipulate and display paragraph (p) in multiple ways
cout << "-----------------------------------------------------\n"
"Display: hcat(p, frame(p)) \n"
"-----------------------------------------------------\n";
vcout(hcat(p,frame(p)));
cout << "-----------------------------------------------------\n"
"Display: hcat(frame(p), p) \n"
"-----------------------------------------------------\n";
vcout(hcat(frame(p),p));
return 0;
}
#include <string> // string
#include <vector> // vector
#include <algorithm> // max
using std::string;
using std::vector;
using std::max;
string::size_type width(const vector<string>& v)
{
string::size_type maxlen = 0;
for(vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
maxlen = max(maxlen, i->size());
return maxlen;
}
vector<string> frame(const vector<string>& v)
{
vector<string> ret;
string::size_type maxlen = width(v);
string border(maxlen + 4, '*');
// write the top border
ret.push_back(border);
// write each interior row, bordered by an asterisk and a space
for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
ret.push_back("* " + (*i) + string(maxlen - i->size(), ' ') + " *");
// write the bottom border
ret.push_back(border);
return ret;
}
#include <string> // string
#include <vector> // vector
#include "frame.h" // width
using std::string;
using std::vector;
vector<string> hcat(const vector<string>& left, const vector<string>& right)
{
vector<string> ret;
// add 1 to leave a space between pictures
string::size_type width1 = width(left) + 1;
// indices to look at elements from left and right respectively
vector<string>::const_iterator i = left.begin();
vector<string>::const_iterator j = right.begin();
// continue until we've seen all rows from both pictures
while (i != left.end() || j != right.end())
{
// construct new string to hold characters from both pictures
string s;
// copy a row from the left-hand side, if there is one
if (i != left.end())
s = *(i++);
// pad to full width
s += string(width1 - s.size(), ' ');
// copy a row from teh right-hand side, if there is one
if (j != right.end())
s += *(j++);
// add s to the picture we are creating
ret.push_back(s);
}
return ret;
}
Running the program gives us the output as expected. This effectively demonstrates that, if the code is written correctly, there is virtually no difference between accessing vector elements by index or by iterators.
Hello world
how are
we today?
^Z
-----------------------------------------------------
Display: hcat(p, frame(p))
-----------------------------------------------------
Hello world ***************
how are * Hello world *
we today? * how are *
* we today? *
***************
-----------------------------------------------------
Display: hcat(frame(p), p)
-----------------------------------------------------
*************** Hello world
* Hello world * how are
* how are * we today?
* we today? *
***************