Preference of reference over pointer: A defense mechanism

Today I am going to discuss some advantages of using reference instead of pointer as a function parameter in C++.

Less typing:
– You have to use arrow (->) operator to access member of a pointer.
– You can access member of a reference with dot (.) operator.
Typing is reduced to 50%. 😀

Catch crash at its source:
– Take reference instead of a pointer as parameter of function where NULL or nullptr are not expected. This will require caller of the function to supply a valid object. If the caller retrieves a pointer from another function and forget to verify if it is valid (not NULL) it will crash when caller will attempt to dereference the NULL pointer before passing it to your function. This gives your caller realization of his own mistake.

– Instead if you take a pointer as parameter and caller of the function supplies a NULL pointer directly or indirectly (retrieving it from somewhere else) then it becomes your responsibility to check for validity. If you don’t then it will crash inside of your function and call stack in the crash dump will show your function at the top. Or in worst case you can store the pointer in a member of your object and later you pass the pointer to some system function. Then the program crashes inside the system function. After the crash you attach the program with debugger and you see in the call stack some hexadecimal numbers are laughing at you. The most recent known function in the call stack is one of your functions. Who is to blame? Intuitively it’s you.

So, take the advice. Beware, it’s not the best advice to use reference, it’s just a good defense mechanism. Use this iff NULL is not expected at all. Otherwise, this type of design can make your client to write ugly code.

Let’s see an example of how can it make the client code ugly –

You declare the following function

void Somefunction(someclass& ref);

Now your client wants to call it with a pointer s/he creates –

SomeClass *p = new SomeClass;
	if(p)
		Somefunction(*p);

If you had declared the function as –

void Somefunction(SomeClass* ptr)
{
	if(!ptr)
		return;
	// Do something
}

Your client could wirte the following –

Somefunction(new someclass);

If your client calls this function frequently then you are making your client to duplicate the NULL pointer check. Which is not only bad, but very very bad.

Feel free to comment about any drawback you see in this technique and suggest any improvement.

union in action: Save some space without compromising readability

In the previous post we met union. This post is about an interesting and practical use of union. Use of Vector (it’s not std::vector) is very common in computational geometry. Lets say we have a 3 dimensional Vector object and we want to access its components with its members x, y and z. But we also want to iterate through its elements. Which is useful when we want to apply some common operations on each of the components like in scalar multiplication of a Vector we multiply a scalar value with each of its components.

Following is an implementation of such a Vector

struct Vector3D
{
 double coord[3];
 double &x, &y, &z;

 Vector3D() : x(coord[0]), y(coord[1]), z(coord[2]) {}
 Vector3D(double a, double b, double c) : x(coord[0]), y(coord[1]), z(coord[2])
 {
     x = a; y = b; z = c;
 }
 // This copy ctor is necessary. With default copy ctor x, y, z of the new copy will be referring the old object's coord
 Vector3D(const Vector3D& vec3) : x(coord[0]), y(coord[1]), z(coord[2])
 {
     std::copy(vec3.coord, vec3.coord + 3, coord);
 }

 Vector3D operator *(double s) // scalar multiplication
 {
     Vector3D vec3(*this);

     for(int i = 0; i < 3; i++)
         vec3.coord[i] *= s;

     return vec3;
 }
};

 

Here we have an array of 3 doubles and 3 double references. In each of the constructors of Vector3D we’ve made sure that they refer to the correct element in the array. x refers to coord[0], y refers to coord[1] and z refers to coord[2]. We can access the components of Vector3D with x, y and z. We can also iterate through them with coord array. We have a nice interface for Vector3D object. But its not free. Each reference added some memory overhead. In 32 bit system it’s 4 bytes and in 64 bit system it’s 8 bytes for each reference. If that is not a big deal then you are fine with this implementation. But in applications where there will be millions of such vectors this small amount of memory does matter.

So, how can we get rid of this memory overhead and get the same interface for our vector object. Hmm, tough one. Lets see if we can use our knowledge from the previous post here. We have learned that we can share the same memory for different variables using union. Can we make the coord array and x, y, z share the same memory? Of course we can.

Lets have a look at the following implementation Vector3d

struct Vector3d
{
 union
 {
     double coord[3];
     struct
     {
         double x, y, z;
     };
 };

 Vector3d(double a, double b, double c) : x(a), y(b), z(c) {}

 Vector3d operator *(double s) // scalar multiplication
 {
     Vector3d vec3(*this);

     for(int i = 0; i < 3; i++)
         vec3.coord[i] *= s;

     return vec3;
 }
};

 

We can use an object of Vector3d exactly the same way we have used an object of Vector3D. We can access its components either with x, y and z or coord array. But this time x, y and z does not incur any memory overhead at all. Also notice that we have less code in this implementation. With this you don’t pay for what you don’t use. This saves us some space still our code reads the same. So, union is the hero here who is saving our back. Here we have declared an anonymous union and struct. We have not used any name for them so that we can access the member variables inside them directly. In this implementation the array coord shares the same memory with the anonymous stuct of x, y and z. So, when we access the Vertor with x, y, and z they refer to coord[0], coord[1] and coord[2] respectively.

Lets see their use in a program –

int main()
{
    Vector3D V(1.0, 2.0, 3.0);

    printf("Vector3D:\n");
    printf("sizeof(Vector3D): %d\n", sizeof(Vector3D));

    printf("Accessing with x, y, z: %lf %lf %lf\n", V.x, V.y, V.z);

    printf("Accessing with coord array:");
    for(int i = 0; i < 3; i++)
        printf(" %lf", V.coord[i]);

    puts("\n");

    Vector3d v(10.0, 20.0, 30.0);
    printf("Vector3d:\n");
    printf("sizeof(Vector3d): %d\n", sizeof(Vector3d));

    printf("Accessing with x, y, z: %lf %lf %lf\n", v.x, v.y, v.z);

    printf("Accessing with coord array:");
    for(int i = 0; i < 3; i++)
        printf(" %lf", v.coord[i]);

    puts("\n");

    return 0;
}

 

Here is the output  –

Untitled

Comparison of two implementation of Vector, notice their size

Note: This code is tested in Visual Studio and g++ (MinGW) on windows 32bit and 64bit. I hope this will work in any compiler and platform. But if anyone find any problem in the code please let me know.

Perception: types and our old friend union

Meaning of Perception (from google search) –
1. the ability to see, hear, or become aware of something through the senses.
2. the way in which something is regarded, understood, or interpreted.

The first meaning does not go with this discussion, second one is of my today’s interest. “the way in which something is regarded, understood, or interpreted”. Lets talk more about it-

We all know the meaning of thumbs-up. It means I liked your work, I appreciate your thought. But not always. If you show thumbs-up to someone not from (or familiar with) western culture s/he may interpret it differently. S/he may consider it equivalent to what middle finger mean in western culture. I know if you had shown thumbs up to my grand father he would slap you in the face. Meaning of thumbs-up changes as it is interpreted [0]. More on thumbs-up

Here is another. You found a note on your desk with two vertical parallel lines drawn on it, underneath that written “number of people going to attend the meeting”[1]. This is a note form your boss to prepare yourself for the presentation. Your boss knew you are little nervous speaking in front of large number of people and he did not want you to be surprised when you enter the meeting room. So, he left you this note for your mental preparation. But, he could not have done a great job. You are still confused about the number of people going to be there. Because, meaning of these two vertical lines can be quite diverse. You are at least sure that these lines represent a number. But, what number is that? Answer to this question totally depends on your perception. Depending on how you interpret it can represent two, three, nine, eleven, seventeen and lots of other possibilities[2]. So, the same two vertical lines can represent two in roman number system, three in binary (of our interest), nine in octal, eleven in decimal, seventeen in hexadecimal. (are you a nerd? that’s eleven, go with it.)

The meaning of same thing can be different depending on ones perception. Same is true for data stored in computer memory. Data are stored in computer memory as strings of 1s and 0s. But, what these strings of 1s and 0s mean totally depend on how you (your program) interpret them. Here data type comes in. You might wonder why some programming languages have data types and what are they for. Well, if you are a “OOP” guy then you are probably thinking about data type as an interface (or class) that specifies what operations are allowed on them. But, that is a high level interpretation of data type. As I understand it, in low level (the level of our interest) data types are indication of how the data should be read/written from/to the memory and interpreted – number of bytes, signed/unsigned etc.

From here on I will assume you have some understanding of the C programming language. I am not assuming you understand pointers. Discussing pointer would be totally appropriate in this article. But, it will make the article too long. I also assume you have some understanding of computer memory and how it can be accessed randomly with addresses. You also understand that computer does not actually understand any of the programming languages available including assembly [3].

So, what happens when we declare a variable of a particular type. Like –

int i;

Actually nothing happens. This line of C code will not contribute a single line of code in our compiled program. Then, why do we write it if our program does not need it. Well, we write it for ourselves. We need it. We can’t keep track of all memory addresses for all our variables and functions. Compiler assigns addresses to all the variables declared in a program and then uses corresponding addresses wherever we use these variables. Lets say our variable i declared earlier is assigned address 0x002FC2 (some arbitrary address). Then

i = i + 1;

will be translated to ‘add 1 to the value at memory location 0x002FC2 and put the result back at memory location 0x002FC2’[4]. Well, that does not seem like we need a type for that. Compiler could assign unique addresses to every variable without a type. But, compiler won’t know how many bytes from address 0x002FC2 to be interpreted as the value of i. We tell the compiler that 4 bytes starting from address 0x002FC2 should be considered as the value of i. We tell it by specifying its type as int.

Lets consider another example –

unsigned int x = -1;
unsigned int y = 0;

Now the condition x < y is false. If you are thinking, -1 is assigned to an unsigned integer so it will lose the minus sign and x becomes 1. You are completely wrong. This reminds me of a junior from my university who needed to calculate absolute difference of two numbers (UVA 10055. Hasmot the brave warrior, if you remember). He then wrote something like –

unsigned int diff = a - b; // a and b were declared as int.
printf("%u", diff);

Then he asked me why the program shows ‭4294967291 for a = 10 and b = 15.
Here x < y is false because binary representation of -1 is a string of thirty two 1s [5]. The most significant bit (the leftmost bit) of these 32 bits is the sign bit[6]. This sting of thirty two 1s is then copied into the 4 bytes of memory starting at the address assigned to x by the compiler. similarly 0 is represented as a string of thirty two 0s and copied into the 4 bytes of memory starting at the address assigned to y. When comparing x < y you are instructing the computer to read content of x as an unsigned integer (again, indicated by the data type of x). In C that means read 4 bytes from the memory address assigned to x and there is no sign flag, all 32 bits represent data. So, the value of x becomes 4294967295. The value of y is read similarly which is 0 and the condition x < y being false now make more sense.

Data types gives compiler a way to know how to interpret memory. It also provides a way for the compiler to warn the programmer if they unintentionally use incompatible types. If you pass a double value to a function where int is expected you will get a warning message. Your program will run but the result may not be correct. Beside primitive data types C allows programmers to define their own compound data types with struct construct. If try to place one type of these user defined variable where some other type is expected you will get an error. No mercy, this is not allowed at all.

Lets meet union, our old forgotten friend. These days people usually do not use it that much. But it has its place in linux kernel, Microsoft Foundation Class (MFC) framework and probably in some other places. When we have two or more heterogeneous types of data and only one of which will be needed at any instance we can share the same memory for all of them. We can do it by telling our compiler to assign same address to a group of variables united as union. Lets see some example.

union and struct are declared similarly.

union my_union
{
    int x;
    double y;
    char z;
};

Now my_union becomes a new type of which we can declare new variables.

my_union u;

u has three members u.x, u.y and u.z unlike struct we can use only one of them at a time. All the three member share the same address. If you don’t trust me try printf(“%p %p %p”, &u.x, &u.y, &u.z). If we use u.x we can put an integer in it and use it for a while. When we need a double we use u.y and use it as long as we need it. You are probably think about how much memory is reserved for u. It is the width of the widest member in the union. In this case it is sizeof(double).

Now that you’ve met old friend ‘union’ you are think about its usefulness. Is it really worth using? Or is there any use case for this? Well, of course there’s use case for it. Someday I will tell you how it is used in MFC for dispatching messages to corresponding handler function of varying signature, and when I will be able to understand linux kernel code I will tell you how and why they keep using it.

Footnotes:

[0] Analogies always fail, don’t count on them.
[1] I could not come up with something more interesting line.
[2] To be specific infinite number of possibilities, if you can come up with enough symbols to represent all the digits in any number system.
[3] Assembly is the lowest level human readable programming language.
[4] Actually it will be translated to machine code. I am saying it in English for you.
[5] Negative numbers are represented in two’s complement form.
[6] Unless otherwise specified, numeric literals are signed in C.

To the students of future.

Exact definition of student is unknown to me. Hence, what follow are my personal understandings and opinions.

Student is a person who wants to learn and attend an institution for this purpose. There is a difference between a student and a learner. Every student is a learner, but every learner is not necessarily a student. It is necessary for a student to be a learner. So, learner seems to be more general term to discuss.

As a learner of a particular subject, topic or matter you must be aware of the fact – you will make mistakes during your learning. It is natural. Sometimes you will also find what you are learning is not actually what you wanted to learn. Don’t be frustrated about it. Knowing what you need to learn is part of your learning. In this particular case the wise decision is to move to the thing you want to learn. It’s never late to start learning from the beginning and there will be situations when this will be the only choice for you to achieve your goal.

Yes, as a learner you should have a goal toward which you will approach. Fixing a goal is the most important and hard thing. There will be times when you will not see a clear path to your goal. This is not unusual. It’s because you have fixed long term goal which is beyond your current vision. As you move forward the distance between your goal and you decreases and your imagination gets filled with details of reality. Of course, this has a negative impact on you, you will lose the power of crazy imagination that you had. Hence, it is important to fix a goal as early as possible. Otherwise you will not be able to think of a goal that seems impossible to you.

One thing you must remember – there are only two types of people in this world one is dead and another is learner. It does not matter if you are a student or not you will be learning from your birth to death. As a future student of the world you must learn how to learn, what to learn and learn it yourself.

To learn how to learn you have to be self learner and for that you will have to explore unknowns. So, to be a learner you have to be an explorer. Tim Cahill said in his book Jaguars Ripped My Flesh, “The explorer is the person who is lost”. If you find yourself lost in somewhere then you are in the right place. You are an explorer. Keep exploring ….

Given, x ≡ a (mod m) and x ≡ b (mod n), m and n are relatively prime. What is the minimum value of xϵN that satisfies these relations for given a, b, m and n?

Answer:

x a (mod m)

x b (mod n)

Let, p = n.k1 a (mod m) and q = m.k2 ≡ b (mod n), k1, k2 ϵ N, so x = p + q – k.m.n, k is the maximum integer such that p + q > k.m.n

Proof:

p + q n.k1 + m.k2        (mod m)

p + q a + 0                  (mod m)    [hypothesis]

p + q a                         (mod m)

Now,

x p + q – k.m.n                    (mod m)

x a – k.m.n                 (mod m)

x a – 0                        (mod m)

x a                              (mod m)

Similarly we can show this for x b (mod n).

Now let’s say there exists a

x’ = p + q – k’.m.n < p + q – k.m.n = x

-k’ < -k

k’ > k. which contradict our hypothesis k is maximum integer such that p + q > k.m.n.

So, x is the minimal.

Download PDF of this post.

Prove that x-S(x) is always divisible by 9. Where, x ϵ N and S(x) is sum of digits of x.

Proof:

It would be enough to show that x ≡ S(x) (mod 9) to conclude 9 | (x-S(x)).

Let, x be a n digit number dndn-1dn-2 … d3d2d1, where di ϵ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} for all i ϵ [1 n].

So,

x = 10n-1.dn + 10n-2.dn-1 + 10n-3.dn-2 + … + 102.d3 + 10.d2 + d1            …… (1)

S(x) = dn + dn-1 + dn-2+ … + d3+d2+d1                                                  ……  (2)

So, we can write –

x ≡ 10n-1.dn + 10n-2.dn-1 + 10n-3.dn-2 + … + 102.d3 + 10.d2 + d1   (mod 9)

x ≡ 1.dn + 1.dn-1 + 1.dn-2 + … + 1.d3 + 1.d2 + d1                          (mod 9)[1]

x ≡ S(x)                                                                                         (mod 9)     [proved]


[1] 10n ≡ 1 (mod 9).

10n ≡ (9 + 1)n ≡ 9n + nC1.9n-1 + nC2.9n-2 + … + nCr.9n-r + … + nCn-2.92 + nCn-1.9 + 1 ≡ 1(mod 9)

You can download this post from here.

Efficiently count number of elements of a list (array) in a range

You are given an array of some type of values (say ‘int’) you will have to answer some queries regarding how many elements are there in the array between a and b (inclusive). For example given A = { 1, 2, 3, 5, 5, 7, 9, 11, 13, 15, 15, 16 }, tell me how many elements are in the range from 3 to 9. The answer should be 5.

To solve this problem first find out the first instance of a or smallest element larger than a and first instance of the element that is larger than in the array. Let, posA be the position where a or smallest element larger than a is first encountered. and posB is the position where the smallest element larger than b is first encountered, if b is the largest element of the array than posB is one past the last element, That is posB = postion of last element + 1. 

So the number of elements in the range from a to b will be (posB-posA). Oh, yes to make searching efficient use binary search. And of course sorted array is prerequisite of binary search.

During a contest it is necessary to write efficient and effective (correct) code fast. If you are good at typing and you know efficient binary search algorithm you can write your own function, that is great. But I am pretty much sure a slow typist will beat you with C++ STL. As it is only two function calls.

lower_bound(start, end, n) – returns an iterator (you can say this a position) to the first instance of n or smallest element larger than n (if n is absent) in the range [start, end)

upper_bound(start, end, n) – returns an iterator to the first instance of the smallest element larger than n or one past the last element that is end if n is the largest element of the range [start, end)

#include <iostream>
#include <algorithm>

#define maxn 100

int A[maxn];

template <class T>
void input(int n, T* L){
    int i;
    for(i = 0; i < n; i++){
        cin >> L[i];
    }
}

int main()
{
    int n, a, b, cnt;

    while(cin >> n){
        //input must be sorted in non decreasing order
        input(n,A);
        cin >> a >> b;
        // this line is all about the post
        cnt = (int)(upper_bound(A,A+n,b)-lower_bound(A,A+n,a));
        cout << "there are " << cnt << " elements between " << a << " and " << b << endl;
    }
	return 0;
}