templating vs pointers, array object vs primitive storage, and the glory of STL vectors in C++

This post shall be rather short in its nature as it is already past due and I am still trying to finish up my workload that I had on my “break”. Two weeks ago in OOP we took some time to observe the nuances of array initialization with a high point being demonstrated by quiz 20, namely showing that an array of type A instantiated with Bs would create the invocation pattern: B constructor, A constructor, A copy Constructor, B destructor and lastly when the Array exited the function scope of invocation A destructor would be called.We also looked at templating examples and pointers. The high point there being that templating allowed for more types of iterators than pointers, but that some iterators imposed restrictions on the order in which their functions were called, namely the read iterator, and the * and == operators. We also briefly discussed why the STL was nice, and the fact that vectors are similar but much faster than java ArrayLists. The high points being attempt to use STL or Boost to save some troubles and a reference to the fact that C++ vectors subscript([]) operator did not suffer from the linear time look-up like java’s List interface does, however there is some overhead on the .at operator.


Arrays and Pointers galore

This week in OOP, we spent most of our time iterating over the different types of pointers in C++ and motivating some examples, the discussion stems from the fact that there are 4 varients of pointers in c++ which can be summed up by the following code and comments:

int c;

int* b; // read/write, many locations

cont int* pc; // read only, many locations

int* const cp = &c; // read/write one location (same as doing int& cp = c;)

const int* const cpc = &c; // read only, one location

We took some time later on to discuss the fact that in java arrays are allocations of values only if the data members are primitive types and for all non-primitives the array holds references to the type, unlike in c++ where the arrays contain the values themselves and can either be stack allocated or heap allocated, unlike java where all stack values reside on the heap.We finished up the week by looking at pointers vs. arrays in c++ noting that pointers are rvalues where arrays seem to be lvalues.

Heap Emulation

This week in OOP we began focusing on type casting in C++ as well as allocation strategies and data storage strategies.

The type casting of C++ is a bit more verbose than it is in most other languages, the reason being is that often when typecasting data is truncated and latter we find that this data was needed, so since errors sometimes result C++ has taken to making typecasting easy to spot by giving it an overly verbose form. An example of this is the following:

int& view(char& c) const{
return *reinterpret_cast<int*>(&c);

The allocation and data storage strategies we reviewed were the following:

  • in C++ most systems interpret a char as 1 byte, as such it is a lightweight way to store general byte data.
  • to denote free space in a heap we can create sentinel values as int values(aka: 4 bytes), often these values might get overwritten accidentally, so to provide some minor error checking store two copies of each sentinel required.
  • to denote active/taken blocks use a negative value to distinguish between free blocks(positive values)

By using this information as well as some unit tests developed on the native heap manager we hope to achieve a similar heap manager that allows us more granular control of the data it has allocated, this is stricly for educational purposes of course.

performance and backing of data structures and c++ iterators

In the days that lead up to the test I found that most of my time was spent trying to chase down an off-by-one bug and in class brushing up on data structures and iterators. The earlier problem was resolved by spending roughly 5 hours running through the code inserting statements to help us see how the code was breaking and then exploring how to get GDB working with the eclipse CDT plugin. The latter was an exercise in note taking.

To recap the 5 common C++ iterators and the operators they provide are:

  • Input: !=, ==, *(read only), ++
  • Output: *(write only), ++
  • Forward: all of input’s and it can read or write on *
  • Bidirectional: all of forward’s and —
  • Random Access: all of bidirectional’s and [], +, -, <, >, <=, >=

As such if you want to make a method which accepts the most iterators you should only expect the operators provided by input or output and no others. However, < tends to be more robust as it will terminate in the case of the begining and the end iterator getting mixed up where inputs != won’t.

In the data structures discussed we looked at cost of selecting, removing, and adding elements which belong to various structures…. most of this discussion was review to me but the discussion continued to the different underlying data structures that could be used to build stacks, queues, and priority structures and this was something that I had not thought about. In summary the subcomponents were vectors, linked lists, and tree structures and stacks can use any of these, queues can use any but vectors, and priority queues can use any but linked lists.

Exceptions, Pointers, and Reference

As my weeks seem to grow increasingly short I find myself this week between interviews and assignments brushing up on some of the old lecture notes from the classes previous two weeks in the hopes that I will be ready for the test. I felt in terms of value the last week has been one of the more enlightening in terms of long term impact. The focus had been on Exceptions and C++: pointers, and references.

Exceptions had been mostly a review but I found several fine points which I had yet to encounter. One of the first points was that in Java you can catch the exception if the heap/stack overflows where as C++ there is no nice way to do this. Another point that I hadn’t considered was in the case that you caught an exception but found you couldn’t handle the exception, in this case you can re-throw the exception caught and it will propagate up the call stack until the same exception is caught in the callers.

On the pointer/reference side of things I had always found that these constructs had been the source of many a bug in my code so it was nice to go through them again. The highlights were:

  • pointers can have the address they point to changed references can not(although both can have the value they point to changed if it is mutable)
  • pointers must be dereferenced(use * to access the value they point to rather than the address) to have there value manipulated where references do not need to be dereferenced
  • references are useful as aliases in the same function scope this does not serve much purpose but this proves useful to abstract out the complexity from the programmer in function argument passing(as compared to pass by pointer)
  • non-dynamic arrays are much like pointers, in fact you can dereference the pointer and select its zero-th value to prove this, however the sizeof function will return the total size of a non-dynamic array where as it will only return the size of the pointer argument on a dynamic array/pointer. In addition the allocations of the stack(non-dynamic arrays) must only have one name for the reference.
  • dereferencing the array + n is the same as a[n] if a is the array(aka: *(a+n) == a[n] for all integer values of n in which n is less than  the array length)

Second Week in OOP

Motivated by my lack of understanding of the all too common buzz word ‘eXtreme Programing(XP) ‘and Jeff’s Post from last week, I figured I would follow suite and provide a synopsis of Kent Beck’s Episode 37: eXtreme Programming Pt 1. I found that overall XP is a set of best practices for working effectively and feeling valued as a team member. The collective opinion was that XP is the ‘least amount you should do in any given project’, I assume the opinion is derived from the fact that XP promotes productivity, error free code, and the value of the team members.

In expressing what XP is the conceivers found that it was necessary to separate the ideas into categories: values, principles, and practices — with the values being the most abstract, the principles admittedly having the potential to be contradictory, and the practices being concrete and implementable. The values of the XP discipline have remained unchanged from their original authoring but the principles have been elaborated on and changed, as such this summary will largely focus on the first rendition of the principles as the secondary principles seem more open to interpretation as they ranged from equality to economics.

The values of XP where:

  • Communication – traditionally thought to be the managers job, XP encourages the whole team to take ownership of this role.
  • Feedback  – promoted by good testing and involvement of the whole team
  • Simplicity – implement the simplest solution that solves the problem
  • Courage – largely be courageous in adopting XP, but also know when to scrap a solution that is not making progress in favor of one that will.

The principles of XP:

  • quality work – enforced by Pair Programing and required for any non-trivial task to find a resolution.
  • incremental changes(babby steps) – re-enforced by unit testing
  • embrace change – because the business requirements can be rapidly changing

Practices of XP:

  • Sit together – makes it easy to communicate about a problem, although this requires restraint from all team members as this can easily lead to rogue conversations and idle chat/jokes.
  • whole team together – often times teams become seperated by function, XP encourages small teams and heterogeneous mixing of managers and all positions on the team to provide accessibility to the members.
  • organize workspace – use resources as best as possible, encourages constructing whiteboards if they are lacking and use of post-it notes
  • energized work(40 hr week) – work at a sustainable pace, don’t over-exert.
  • Pair Programming – as discussed in class and in Pair Programming A and Pair Programming B with the basics being: have 2 programmers taking turns at one keyboard with the non-driver critiquing the code written to reduce the bugs introduced, and the driver should change every couple of hours. This reduces ‘cowboy programming’ (aka: reduces the acquisitions and finger-pointing) as well as increasing the ‘truck factor'(how many people can get hit by a truck before the project goes under)
  • Test First(Test Driven Development[TDD])- write a failing test for code and then implement the code to cause the test to pass. Similarly when a bug is found write a test that fails because of the bug then fix the bug. Advocated as a way to design a system not only regression test.

After realizing that I already followed many of the practices of XP I found that I was no longer in the dark and glad that I had a name to put to the collective set of skills that I had been using. As such I look forward to my future XP experiences in this class.


First Days In OOP

The first weeks of my last semester here at the University of Texas have gotten off to a running pace. During this time in my Object Oriented Programming(OOP) course I have begun to  learn about the differences in C++ and Java, how to become a great programmer by being a better communicator, and how to approach the Collatz conjecture in the hopes that a fast/optimal solution is reached.

In learning about the usefulness of effective communication from the post Advice for Computer Science [for] College Students by Joel Spolsky, I  noted that he attributed the success of Linux, Extreme Programming(XP), and great programmers in general to there expressive ability; and not due to there ability to master all programming languages known to man. Prompted by this, and the potential that my attempt to better myself might have some benefit to my career and more immediately a small impact on my class grade, I evoked on the adventure of writing my first blog. With respect to this please pardon my style as I learn how to best express myself within the time constraints.

The aforementioned Collatz conjecture is a theory that says for any natural number you can find a path from that number to 1 given you apply the following conditional transformations to the original number(n): if n is odd then take 3n+1, else divide n by 2. The steps it takes to get from the original number to 1 are referred to as cycles, and as of today there is no proof that this algorithm will terminate in a finite amount of cycles although it is widely believed that this algorithm does in fact terminate. The optimizations to the Collatz conjecture that we have looked at involve simple caches and bit shifting (vs. arithmetic operations on the values). In the coming days I hope to produce an optimal solution and have sphere verify my solution.