Week 10 - Last week :(

This week.. and sadly the last week.. we were wrapping up the course material. We did a review of the material covered after the second test, in addition to new stuff about manipulators (endl, setw) and other adapters (ptr_fun, mem_fun_ref). We looked into how ostream's operator << is overloaded to account for functions as well. The ptr_fun helps in converting a function into a function object, and similarly mem_fun_ref converts an object's method into a method object. These are helpful where functions like bind2nd are used, as they require a function object as their argument.

It is strange, and I am quite surprised that I would feel nostalgic by the end of this summer session. I guess, it's partly because I am about to leave Austin, and about to start upon a new venture in an entirely different world. Initially, it seemed as if the summer session was to remain forever, and now it appears as if it got finished the moment it started.

By the end of this course, I can definitely say that this course has increased my aptitude for programming, and expanded my understanding of the C++.

Week 9

This week we work upon the Project 9 - Graph; the task was to reverse engineer the Boost Graph Library and implement a Graph class which will bear the functionality of adding vertices and directed edges. It also provides methods to determine whether the graph is Directed Acyclic Graph (DAG), and if it is, it provide function to topologically sort the vertices. The most daunting task was to have a firm and robust design for the data structure to be used for the implementation. We ended up using a vector of sets, where the index of the vector would determine the vertex, and the corresponding set elements will represent the vertices that are connected to this vertex. As discussed in the class, there are other standard implementation of the graphs: adjacency lists (for graphs that are sparse), and adjacency matrix (for dense graph). Another challenging task was to write the algorithm for the topological sorting. Having done a bit of research, showed that it could be done using depth first traversal. We implemented a recursive function, and a three color scheme to traverse the graph (depth first). The colors determined whether the vertex has been visited, is yet to visit, or has its traversal completed.

In the class, we went over important iterators such as front_insert_iterator (/back_insert_iterator) and their corresponding function objects front_inserter (/back_inserter). These iterators conform to the STL conventions, and could be used with other STL algorithms such as copy. These come in handy when there is a situation such as,


vector x(10,2);
list y(5,3);

std::copy(x.begin(), x.end(), back_inserter(y));


This will result into copying of all the elements of x into y, after which y.size() == 15. However, to have the copy() and other STL algorithms work, the front and back inserters have a peculiar design. The operator *(), operator ++ () return *this of the same type as the class, while operator = (const T& v) also returns itself, but does x.push_front(v) (or x.push_back(v)). A similar design is followed by the ostream_iterator and istream_iterator. However, istream_iterator do maintain data member istream* in to consider the !=EOF criteria.

We learned about few more subtleties of C++ (rather I should say, very important subtleties that if not aware of can lead to programmer's frustration). We studied as to when an argument is taken as a function pointer, and when it's not. For eg.


A x(2,3,4); //constructor
A t; //default constructor

A z(); //function declaration whose return type is A



//LEGAL function declarations
int f(int);
int g(int x); //argument with a name
int h(int (x));

int q((int x)); //ILLEGAL


Likewise, few other examples,

int f(int (*p) ()); //named parameter, with a pointer notation
int g(int p()); //named parameter
int h(int ()); //no name
//all of above mean the same



int m (int (int)); valid
int n (int (int x)); probably unreasonable


In case of ambiguity, the declaration of function wins.

Week 8

The week had been full of design making decisions, and most importantly regrets and realizations. I have been working with my partner on the project 7. The project is about implementing a Deque, that would imitate most of the functionality of the standard library's deque (std::deque). We started off with constructors, and tested our deque side by side with the standard deque. Happy with our results, we jumped into coding the methods -- insert, erase, push_front, push_back, etc. Compiling the program without any tests didn't give us any errors/warnings and was a motivation in itself. The realization time started as we started to write the test cases for these methods. Some would result into segfault, and for some the assertions would fail; and some wouldn't even compile. Yet, withstanding all the errors, and resolving those we had our "Deque.h" ready with all of our tests passing. The time was 6:00p on a Sunday (today).

Something struck on us suddenly, the motif behind implementing a deque; shouldn't it have an amortized constant time complexity for push_front() and push_back(). But too late to realize, that we had implemented a vector :(. A few minutes ago I was thinking of all the good stuff I would had for the dinner, and a few minutes later... I could think nothing except the program. But I realized, that some times (or most of the time in my case) when under pressure, brain functions better and productively (though, often it turns into a numb state). And so happened with us, the idea had to click (which hadn't for the whole week) and we had the real deque implemented. Thanks to the partnership again!