const Correctness: Difference between Foo* const ptr, const Foo*
ptr, const Foo* const ptr
Posted by tekpool on January 10, 2007
- Foo* const ptr: ptr is a const pointer to a Foo Object. The Foo object can be changed using the pointer ptr, but you can’t change the pointer ptr itself.
- const Foo* ptr: ptr points to a Foo object that is const. The Foo object can’t be changed via ptr.
- const Foo* const ptr: ptr is a const pointer to a const Foo object. Neiher can the pointer ptr be changed, nor can you change the Foo object using ptr.
Reading the declaration right to
left is a easy way to remember what they mean.
Posted in C++, General, Microsoft, Progamming
Languages, Technical Interview Questions
| 8 Comments »
Constructors: Copy Constructors, What, Why, How, When … (C++)
Posted by tekpool on December 22, 2006
As the name suggests, a copy
constructor is called whenever an object is copied. This happens in the
following cases:
- When an object is create from another object during initialization (Class a = b)
- When an object is created from another object as a parameter to a constructor (Class a(b))
- When an object is passed by value as an argument to a function (function(Class a))
- When an object is return from a function (Class a; … return a;)
- When an exception is thrown using this object type (Class a; …. throw a;)
Whenever an object copying scenario
like the ones above is encountered, the copy constructor is invoked. A copy
constructor can be either user defined or compiler defined. If the user does
not define a copy constructor, then the default compiler defined copy
constructor will be invoked during object copy scenarios. The default copy
constructor is a bit-by-bit (member wise) copy. But often you will encounter situations
where this is not desirable since this is just a shallow copy and sometimes you
do not want an exact copy or you may want to do some custom resource
management.
Class
t1;
Class
t2=t1; // Copy Constructor is invoked
Class
t3;
t3=t1;
// Assignment Operator is invoked
In the Code snippet above, the
constructor is invoked twice, during the creation of objects t1 and t3.
(Creation of t2 invokes the copy constructor). The destructor is invoked 3
times though. In cases like these, if the constructor allocates memory and the
destructor frees it, you will see the t2’s destructor will try to delete
already deleted memory, if t1 is destroyed before t2 or vice-versa. Meaning,
you are hosed. To prevent this, a user defined copy constructor needs to be
provided. which doesn’t do a simple bit-by-bit but rather assigns memory
specifically for the object and does a deep copy if required.
To define a copy constructor for a
class T, a constructor of the following format needs to be defined.
Class
T
{
…
T(const T& t)
…
}
You need a reference because if it
were T(T t), it would end in a infinite recursion. (Was that an oxymoron?).
const because you are not changing the object in the constructor, you are just
copying its contents
Some Rules of Thumb:
- Don’t write a copy constructor if a bit-by-bit copy works for the class
- If you defined your own copy constructor, it probably because you needed a deep copy or some special resource management, in which case, you will need to release these resources at the end, which means you probably need to define a destructor and you may also want to think of overloading the assignment operator (beware of self-assignment)
Posted in C++, General, Microsoft, Progamming
Languages | 12 Comments »
Constructors: Error / Exception Handling in Constructors
Posted by tekpool on December 8, 2006
Constructors do not have return type
and so they cannot return error codes. How are errors or exceptions handled in
constructors? What if the calls that you make in the constructor can actually
throw exceptions? How do you let the caller know something bad happened in a
constructor?
There are a few ways to do robust
error/exception handling in constructors
- Do as little in the constructor has you can. Then provide an Init() function in the constructor, which does the normal initialization stuff. The user can then call this function after creating an object. The problem here is, its up to the user to actually call the Init() function. The user could potentially miss this step, making this method error prone. However, there are a lot of places where this methodology is used. You are trying to eliminate error handling in the constructor by using this method
- Another way to do this is by putting the object in a Zombie state. This is one approach you can take especially if you do not have the option of using exceptions. When you go with this option, you will also to do provide a function that will check the state of the object after construction. The downsides to this option is that, its up to the user to do these checks and the users will need to do this every time one attempts to create an object. It’s usually always better and cleaner to throw an exception instead. Use the Zombie option as a last resort.
- The downsides to the above methods can be reduced by making the constructor private or protected, expose a CreateInstance() public method, and do all the error handling here rather than leave it to the user. But sometimes, its not possible to handle all the error conditions in a generic manner and you will need to throw an exception.
- If an exception is thrown in the constructor, the destructor will not get called. So you need to handle and clean up as much as you can before you leave the constructor. The best way to do this is using the “resource allocation is initialization” technique. I will cover this topic separately in a future post. But the basic idea is to assign resource allocation and cleanup to other objects. Basically, you are trying to get allocation out of the way (indirect) so that you don’t have to do it explicitly. When you don’t allocate something directly, you don’t have to release it either because it will be done by the component or class who deals with it. E.g. If you need to allocate some memory or open up a file, You can use smart objects (smart pointer, auto_ptr, smart file handlers etc..) instead of calling new or fopen directly. When you do this, and if an exception is thrown in your constructor, the smart objects will automatically release the resources it acquired, as the stack unwinds. If you do not use the “resource allocation is initialization” technique, the user will need to wrap the statements in try/catch block and rethrow after cleaning up the mess, something like what the finally block does in Java or C#. Although this works in theory, it’s up to the user to make this work and it also always a source of errors and bugs (esp. memory and handle leaks) and is messy
As you have seen, there is no “one
size fits all” rule to do error/exception handling in constructors. I have
listed the most commonly used methods and one of these should work most of the
time.
Posted in C++, General, Progamming Languages | 3 Comments »
Swapping variables without additional space
Posted by tekpool on December 3, 2006
Swapping variables is a very common
operation used it tons of algorithms like sorting etc. The most common and
obvious technique is using of a temporary variable to swap values between two
variables
void
swap(int &i, int &j)
{
int temp = i;
i = j;
j = temp;
}
Instead of writing a separate
function for each data type, you could write a MACRO or templatize the
function.
Swapping without using a temporary
variable is an age old trick and there are a few ways to do this. You could use
of the basic arithmetic operations like +,-,/,*
1:
void swap(int &i, int &j)
2:
{
3: i=i+j;
4: j=i-j;
5: i=i-j;
6:
}
The technique involves storing the
sum of variables in one of them and then extracting it back by subtracting the
other number. There are different variants to this technique. E.g, instead of
starting by storing the sum, you could store the difference, product or the
quotient. The last two could lead you to round-off and integer division errors.
However all of them have one fundamental flaw. Its in line 3, and the issue is
that this could lead to an overflow error.
This is another technique the gets
you around these issues; the XOR Swapping technique
void
swap(int &i, int &j)
{
i = i ^ j;
j = j ^ i;
i = i ^ j;
}
This is an elegant technique and should
work well with any primitive data type and you could write a simple MACRO like
#define
SWAP(i, j) (((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))
Although, the XOR technique gets rid of the other issues like overflow and round off errors that we encountered in the previous technique, the lands in into yet another issues; This does not work when you try to swap the same memory location. However if can get around this by a simple ‘if’ check or a more elegant OR check like
#define
SWAP(i, j) ( (i==j) || ((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))
The first OR condition (i == j) is checked before the actual SWAP. (You do not need a SWAP if the both memory locations hold the same data)
Posted in Algorithms, Bit Fiddling,
C++, General
| 7 Comments »
Binary Tree Searching: Improving Search Performance
with Sentinels
Posted by tekpool on November 16, 2006
A normal search across a BST (Binary
Search Tree) would look like this
bool BinaryTree::Search (int data )
{
Node *current = this->root;
{
Node *current = this->root;
while ( current
!= NULL )
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}
return false;
}
}
You keep going down the tree, until
you find a node whose value is equal to one you are looking for, or you bail
out when you hit a leaf (NULL) node. If you look at the number of statements,
there is one conditional check on the while, and an average of 1.5 conditional
checks inside the loop. That makes it a total of 2.5 checks every iteration. On
a tree with a 1000 nodes, that’s 2500 checks.
Let’s see how we can improve this. I
am using the sentinel node technique for this purpose. In this case static Node
* Leaf;
This is how the search will look
like
static Node* Leaf;
static Node* Leaf;
bool BinaryTree::Search (int data )
{
Node *current = this->root;
{
Node *current = this->root;
Leaf->data =
data;
while (
current->data != lead->data )
{
if (current->data < data)
{
current = current->left;
}
else
{
current = current->right;
}
}
{
if (current->data < data)
{
current = current->left;
}
else
{
current = current->right;
}
}
return (current
!= Leaf);
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.
This is extremely useful with large
trees or when you are searching the tree several times or any other scenario
where this call happens in a hot section.
Posted in Algorithms, Binary Trees,
C++, Data
Structures, General, Microsoft | 13
Comments »
Binary Tree Traversal: Breadth First aka Width First aka
Level Order
Posted by tekpool on November 4, 2006
Binary Tree Traversal: Breadth First
aka Width First aka Level Order
This is the lesser know of the
different kinds of binary tree traversals. Most beginner books and articles
only cover the depth first searches. Breadth first traversals are an extremely
important tool when working with Binary Trees. The idea is pretty nifty.
Basically you work with a Queue, and push the root node into the Queue. Then do
the following until you have visited all nodes in the tree.
Visit and Dequeue each element
(node) in the queue, and as you visit the node, enqueue it’s left and right
child (if present). Continue this until there are no more nodes in the queue.
At this point you have finished a breadth order traversal of the binary tree.
Let’s work this out with an example.
Here’s a small perfectly balanced
tree that I going to be working with. The idea of doing a breadth first
traversal is visit the nodes in the following order 1,2,3,4,5,6,7. Initially,
you start of with an empty queue and enqueue the root node into the queue. I
will display the contents of the queue as we move along.
-------------------------------------------
| 1
--------------------------------------------
Visit each element int the queue,
enqueue its left and right nodes and dequeue itself. Once the elements are
dequeued, I will put them to the left of the queue.
Visit Node 1, enqueue 2 and 3 and
dequeue 1
-------------------------------------------
1 | 2, 3
--------------------------------------------
Visit Node 2, enqueue 4 and 5 and
dequeue 2
-------------------------------------------
1,
2 | 3, 4, 5
--------------------------------------------
Visit Node 3, enqueue 6 and 7 and
dequeue 3
-------------------------------------------
1,
2, 3 | 4, 5, 6, 7
--------------------------------------------
Visit Node 4, dequeue 4 Nothing to
enqueue since 4 has no child nodes
-------------------------------------------
1,
2, 3, 4 | 5, 6, 7
--------------------------------------------
Visit Node 5, dequeue 5, Nothing to
enqueue since 5 has no child nodes
-------------------------------------------
1,
2, 3, 4, 5 | 6, 7
--------------------------------------------
Visit Node 6, dequeue 6, Nothing to
enqueue since 6 has no child nodes
-------------------------------------------
1,
2, 3, 4, 5, 6 | 7
--------------------------------------------
Visit Node 7, dequeue 7, Nothing to
enqueue since 6 has no child nodes
-------------------------------------------
1,
2, 3, 4, 5, 6, 7 |
--------------------------------------------
We have just finished a breadth
order traversal of a binary tree
Here’s a pseudo-code snippet that of
the solution.
BreadthOrderTraversal(BinaryTree
binaryTree)
{
Queue queue;
queue.Enqueue(binaryTree.Root);
while(Queue.Size > 0)
{
Node n = GetFirstNodeInQueue();
queue.Enqueue(n.LeftChild);
//Enqueue if exists
queue.Enqueue(n.RightChild);
//Enqueue if exists
queue.Dequeue(); //Visit
}
}
Posted in Algorithms, Binary Trees,
C++, Data
Structures, General, Microsoft, Progamming
Languages | 10 Comments »
Singleton Pattern: Part 2 Thread-Safe implemenation
Posted by tekpool on October 27, 2006
Singleton Pattern: Part 2
Thread-Safe implemenation
We looked into a trivial
implementation of the singleton pattern in the previous post. The
implementation was both lazy and non-thread safe. It’s lazy, because the
singleton instance is created only when it’s required. The implementation was
also not thread safe. So, if several calls were made into this method from a
multi-threaded program, you could end up creating multiple instances of the
class, and also mess up seriously since the system expects to have only one
instance.
The problem is at the place, where
you check if the instance is null. This is how it could go all wrong. In a
multithread environment, lets say 2 threads T1 and T2 are calling the
CreateInstance() function. T1 executes the ‘if’ condition and then loses its
time-slice, Meanwhile T2 gets its chance to execute code. At this point the
singleton instance is not yet created. T2 then creates the object and returns
the caller an instance of the newly created object. When T1 gets back another
time-slice, it creates another object and returns that instance to its caller.
Since it’s a static instance, T2 will lose it’s the state of the object it
acquired and then hell breaks loose.
class Singleton
{
private:
static Singleton instance;
protected Singleton()
{
}
public static Singleton CreateInstance()
{
// Use a mutex locking mechanism
//
that suits your system
LockCriticalSection();
if (instance == null)
{
instance = new Singleton();
}
UnLockCriticalSection();
return instance;
}
}
}
Posted in C++, Design Patterns, General, Microsoft,
Progamming Languages | 175 Comments »
Singleton Pattern: Part 1 Trivial implemenation
Posted by tekpool on October 19, 2006
Singleton Pattern: Part 1 Trivial
implemenation
The purpose of a singleton pattern
is to ensure a unique instance of the class and to provide global access to
this. It falls under the Creational patterns category.
The class implementing the singleton
pattern will have to do the following items:
- Provide an Instance Creation Method to the user.
- Maintain the unique instance throughout the life of the program(s) in which this class is created.
To maintain the unique instance, the
class will have to remove the normal object creation procedure away from the
user. The normal object creation is through the constructor. Taking this away
from the user would mean, making the constructor as private or protected. With
the absence of a public constructor, the class now can take total control on
how its instances are created. The only way to do this, is to provide a static
method (say CreateInstance). Why static? Because, the user can actually call
this method without creating an object (which is obviously out of the user’s
control).
The logic of the CreateInstance
method is pretty straightforward. Check, if any instance has already been
created, if yes, return the instance, else create and store the instance and
return it. It is obvious here again, storing the instance has to be done in a
private static variable, static because, you are doing this in a static method,
private because, you need to do the maintenance of the singleton instance
creation.
Here’s the code sample to
demonstrate this. I am going to promote Test Driven Development in my examples.
The TestApp::TestSingleton() method
is the test code that I wrote even before writing the actual Singleton class. I
will discuss Test Driven Development in detail in another series.
class TestApp
{
public:
static void TestSingleton()
{
Singleton s1 = Singleton.Instance();
Singleton s2 = Singleton.Instance();
if (s1 == s2)
{
printf("PASSED:
Objects are of the same
instance");
}
else
{
printf("FAILED:
Objects do not point to the same
instance");
}
}
}
//
WARNING: DO NOT USE THIS CODE ANYWHERE.
//
THIS IS A VERY TRIVIAL IMPLEMENATION. WE WILL
//
DISCUSS THE ISSUES WITH THIS IN FUTURE POSTS.
class Singleton
{
private:
static Singleton instance;
protected Singleton()
{
}
public static Singleton CreateInstance()
{
if (instance == null)
{
instance = new Singleton();
}
return instance;
}
}
}
Posted in C++, Design Patterns, General, Microsoft,
Progamming Languages | 1 Comment »
String Pattern Matching: Write a function that checks for a given
pattern at the end of a given string
Posted by tekpool on October 15, 2006
String Pattern Matching: Write a
function that checks for a given pattern at the end of a given string
In other words, Write a function, a
variant of strstr that takes in 2 strings str1 and str2 and returns true if
str2 occurs at the end of the string str1, and false otherwise.
bool
str_str_end(char * str1, char * str2)
{
// Store the base pointers of both
strings
char* beginStr1 = str1;
char* beingStr2 = str2;
// Move to the end of the strings
while(*str1++);
while(*str2++);
for(; *str1 == *str2; str1--, Str2--)
{
If( str2 == beginStr2
|| str1 == beingStr1)
{
break;
}
}
return
If(*str1 == *str2
&& str2 ==
beginStr2
&& *str1 != 0);
}
Save the base addresses of the
strings and then traverse to the end of the stings. To check if the string str2
occurs at the end of the string str1, start comparing characters from the end
of the strings and move backwards. The function returns true when
- All the characters in str1 match all the characters in str2 from the end.
- The pointer str2 reaches back at the beginning of the string, which means there is nothing more to be compared
- The strings are not empty.
The above conditions are required so
that the loops do not run in an infinite loop.
Posted in Algorithms, C++, General, Microsoft,
Pattern Matching, Progamming Languages, Strings
| 1 Comment »
Rectangle Intersection – Find the Intersecting Rectangle
Posted by tekpool on October 12, 2006
Q: Rectangle Intersection – Find the
Intersecting Rectangle
In the last
post, we looked into methods to determine whether or not two given
rectangles intersect each other. Lets go one step ahead this time and find the
intersecting rectangle.
As in the previous post, I am basing the struct off of the Windows
co-ordinate space, where the origin is on the top left of the screen. The
x-axis moves towards the right and the y-axis moves towards the bottom.
bool
Intersect(RECT* r3, const RECT * r1, const RECT * r2)
{
bool fIntersect = ( r2->left right
&&
r2->right > r1->left
&&
r2->top bottom
&&
r2->bottom > r1->top
);
if(fIntersect)
{
SetRect(r3,
max(r1->left,
r2->left),
max(r1->top,
r2->top),
min( r1->right,
r2->right),
min(r1->bottom,
r2->bottom));
}
else
{
SetRect(r3, 0, 0, 0, 0);
}
return fIntersect;
}
First, determine whether or not the two Rectangles intersect each other, Then use the
SetRect method (which basically creates a RECT with the given points) and
create the intersecting Rectangle
SetRect(r3,
max(r1->left, r2->left),
max(r1->top, r2->top),
min( r1->right, r2->right),
min(r1->bottom, r2->bottom));
Since the algorithm is pretty
straightforward, I am not going to include more detailed analysis in this post,
unless I get enough request comments or email 
NOTE: For all invalid rectangles
passed to the function, the return value is always [0,0,0,0]. You can also
choose to return error codes after checking for validity.
Posted in Algorithms, C++, General, Graphics,
Microsoft, Progamming
Languages | 10 Comments »
« Previous Entries
Blog at WordPress.com. | Theme: Andreas09
by Andreas Viklund.
Follow
Follow
Technical Interview Questions
Get every new post delivered to your
Inbox.
Powered by WordPress.com
