CPP Coding Questions

<title>C/C++ | Lingfa Yang </title>

C/C++: Basic to Advanced

When my friends consulted me C/C++ problems, I found some of their questions are great. So I collect them, and put answers together to share with you. If you have nice questions, or elegant codes to share, doesn't matter which levels, email me please. Playing codes is my hobbit.

Sample questions:

Swap: (warm-up questions)
Function pointer:
const:
C-style string:
- How do you assign a string?
```
<li>Instead using functions in string.h, implement your own functions:
```
How do you reverse a string without duplicating memory cost?
How do you reverse a sentence without reversing letters in words? (use two pointers)
Write a function, count how many words in a sentence.
Write a function to extract words from a sentence into an array.
Write a function to replace all space-char by "%20".
Which character is the most continuously occurring char in a string?
String representation of a number, for example, -3.6 => "negative three point six".

QString (16 bit unicode character string)

Initializing a String
Indexing/searching, indexOf, lastIndexOf
Extract substring: left(), mid(), and right()
Manipulating String Data: append(), prepend(), insert(), replace(), and remove(); trimmed(), simplified(), chop()
Converting: toInt(), toDouble(), toLower(), toUpper(), toUtf8(), toAscii()
Querying String Data: startsWith() or endsWith(); contains(), count(), isNull(), isEmpty()
Split and join

Array:

Does C/C++ allow a negative index?
Two ways of passing an array to a function as a parameter | Three ways of an element indexing
When do you use *& ?
constant pointers v.s. pointer variable
How do you merge two sorted arrays?
Multidimensional arrays
Spiral initialization | Magic Square

List:

How do you reverse a list?
How do you count nodes in a linked list?
How do you get the last node of a linked list?
How do you duplicate a list?
How do you delete 2nd last occurrence of a integer from a singly linked list
How do you merge two lists?

Looped list:

How do you detect a list is looped or not? (two solutions at least)
How do you get the last node (tail) of a list in general?
(Beyond a normal list, it can be empty, or looped. Two solutions at least)
How do you know the total length a looped list?
How do you know how many nodes on the loop?
How do you break up a looped list into a normal list without losing any node?

A doubly linked list:

Advantage and disadvantage?
How do you insert a new node before a given node in a doubly linked list?
How do you appendix a new node to a doubly linked list?
How do you use a doubly linked list for sorting?

Binary Trees:

Insertion sorting, complexity concern.
Find the minimum value of a tree.
Find the maximum value of a tree.
Check a tree is sorted or not?

Multiple children tree:

Query methods: Query methods: parent(); name(); empty(); size(); child(); firstChild(); lastChild(); nextSibling(); previousSibling(); node(); nodes(); contains(); ==(); !=()
Manipulation Methods: subtract(); del(); prepend(); rotate(); chop(); adopt();
Sort | Save | Walk

Sorting algorithm:

Bubble sort | Binary tree sort | Quicksort
Sorting methods comparison

Iterator:

What are iterators?
What is the key difference between Java-style and STL-style iterators? Which one do you like?
Is there any difference between prefix ++i and postfix i++ operators?

OOP:

What is a constructor? What is a desconstructor? inline initialization in constructor
What is the difference between a copy constructor and an overloaded assignment operator?
Inheritance, modularity(abstraction, separation between interface and implementation), polymorphism, and encapsulation
Why inheritance? | "Diamond problem" / virtual inheritance
Casting in C/C++, upCast and downCast; static and dynamic
Virtual function | pure virtual function | abstract class => interface =>coclass => COM => IDispatch
virtual destructor? | virtual constructor? | public, protected, or private constructors?
overload, override, overload-and-override
struct | union | class | enum | namespace
(new and delete) vs (malloc and free)
namespace
What do you mean by inline function?
try, catch, and throw, Exception Handling
UML design

Multithread:

thread and process | Difference between a thread and a process | Multithread Synchronization | CMultiLock
Singleton | thread safety | double-checked locking ...

3D Math: (In mathematics you don't understand things. You just get used to them. --Johann von Neumann)

vector basic | point template
Distance of a point to a line
Distance of a point to a line segment
Distance between two lines
How do you know 4 points are coplane or not?
Square Matrix: Determinant, Transpose, Adjoint, Inverse, Eigenvalues
Affine Transformations: Translation, Rotation, Scaling, Reflection, and Shear
Trackball rotation controller: quaternion algebra, convert to rotation matrix
Parametric Curves
NURBS | Voxel (Volumetric and pixel) | Mesh

Shader:

What is the difference of a point and a vertex? (location + render info)
Vertex shaders v.s. pixel shaders
Z buffer (depth) | Alpha blending | light and material, surface models
fixed-function pipeline (FFP) | color(vector) pipe and alpha (scalar) pipe

Bitwise logical operator:

Give a one-line C expression to test whether a number is a power of 2
divide (multiply) by seven without the use of the divide (multiply ) operators

Others:

Check if a number is prime or not.
Given the time, devise an algorithm to calculate the angle between the hour and minute hands of an analog clock. [ (60h-11m)/2 ]
How to draw an analog clock?
Recursion functions: Factorial | Fabonacci

Unicode | UTF-8 | GB 2312

</li><li>	
<a href="#APIs">Win32 APIs, GDI, GDI+</a>

</li><li>	
<a href="http://en.wikipedia.org/wiki/Grid_computing">Grid computing</a>: 
The key distinction between clusters and grids is mainly lie in the way resources are managed. 
In case of clusters, the resource allocation is performed by a centralised resource manager and 
all nodes cooperatively work together as a single unified resource. In case of Grids, each node has its 
own resource manager and don't aim for providing a single system view. 
| Desktop Bus (<a href="http://en.wikipedia.org/wiki/D-Bus">D-Bus</a>) is the 
new Inter-process communication (<a href="http://en.wikipedia.org/wiki/Inter-process_communication">IPC</a>) system


</li></ul>

Automation:
- What is Automation?
I/O
- What is CRT? What does "deprecated" mean? How to eliminate deprecation warnings? Security Enhancements?
- Use secure version fopen_s, _wfopen_s intead of fopen, _wfopen
- Encoding: ANSI, UTF-8, and UTF-16LE; Byte Order Mark (BOM)

How do you swap two variables?

Swap two integers:

swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }

void main() { int a=2,b=3; swap(a,b); // result in a=3 and b=2 }

Wrong swap due to Call-by-Value!

void swap(int i, int j) { int tmp = i; i = j; j = tmp; }

void main() { int a=2,b=3; swap(a,b); // nothing change }

Tricky question: Do you know how to swap two integers without declaring a third interger?

swap(int &a, int &b) { a += b; b = a - b; a -= b; }

void main() { int a=2,b=3; swap(a,b); // result in a=3 and b=2 }

In general, you can use template for swapping (swap by using reference parameters):

template <class T> void swap(T &a, T &b) { T tmp = a; a = b; b = tmp; }

void main() { int a=2,b=3; swap(a,b); // result in a=3 and b=2 }

Using pointer parameters for swapping.

template <class T> void swap(T a, T b) { T tmp = a; a = b; b = tmp; }

void main() { int a=2,b=3; swap(&a,&b); // result in a=3 and b=2 }

Is there any difference between the two versions of swapping by using the pointer and reference parameters? Which one do you like?

How to swap two objects?

class A // base { public: A(){m=0;n=2;}; // constructor protected: int m,n; // members };

class B : public A // derived { public: B(){m=1;n=3;}; // constructor };

void main() { A ptrA = new A; A ptrB = new B; `swap(ptrA,ptrB); delete ptrA; delete ptrB;` }

// Both work, but addresses after swap will be different!

Case 1: by pointer parameters	Case 2: by reference parameters
template <class T > void swap(T a, T b) { T tmp = a; a = b; b = tmp; }	template <class T> void swap(T &a, T &b) { T tmp = a; a = b; b = tmp; }
Before: - ptrA 0x00780eb0 m 0 n 2 - ptrB 0x00780e70 m 1 n 3 After: ptrA 0x00780eb0 m 1 n 3 ptrB 0x00780e70 m 0 n 2	Before: - ptrA 0x00780eb0 m 0 n 2 - ptrB 0x00780e70 m 1 n 3 After: ptrA 0x00780e70 m 1 n 3 ptrB 0x00780eb0 m 0 n 2
& tmp is an address which hold the member values. - & tmp 0x0065fd60 m 0 n 2	tmp itself is an address which has two members. - tmp 0x00780eb0 m 0 n 2
Compare with: int a=2,b=3;
Usage: swap(&a,&b);	Usage: swap(a,b);
Same role: where "tmp" is a third integer, holding "a" temporally

Wrong!

void main() { A objA; B objB; // swap(&objA,&objB); // compiler fail: template parameter 'T' is ambiguous swap(&objA,&(A)objB); // result is not correct ! See below. }

// Output

Before: - objA {...} m 0 n 2 - objB {...} - A {...} m 1 n 3 After: - objA {...} m 1 n 3 - objB {...} - A {...} m 1 n 3

Wrong assignment

Fail to compile:

char s1[] = "Hello"; char s2[20]; s2 = s1; // error C2440: '=' : cannot convert from 'char [6]' to 'char [20]' // Because s2 is a pointer constant, not a pointer variable!

How about this?

	char *s1 = new char [20];
	char *s2 = new char [20]; 
strcpy(s1,"Hello");
s2 = s1; // be careful !

delete []s1;
// Now how about s2 ?

Make a true copy by memcpy:

	char *s1 = new char [20];
	char *s2 = new char [20]; 
strcpy(s1,"Hello");
memcpy(s2,s1,20);	

//	void *memcpy( void *dest, const void *src, size_t count );
//	returns the value of dest.

Some string copy problems:

True copy or not?

char s1[] = "Hello world."; char *s2 = new char[20]; // s2 = s1; // true copy or not? strcpy(s2,s1); // This is a true copy

memcpy, a true copy.

	int a1[] = {1,3,5,7,9};
	int a2[10];
//	a2 = a1; // Wrong
memcpy(a2,a1, 2*sizeof(int)); // first 2 elements of a1 to a2

memcpy(a2+5,a1+2, 3*sizeof(int)); 
// from 3th of a1 copy three to a2[5],a2[6], and a2[7]

strcpy for string initialization

char string[80]; strcpy( string, "Hello world from " );

An interview question: Is there anything wrong with the following code?

void Test() 
{
	char s1[5], s2[5]; 
	for(int i=0; i < 5; i++) 
	{
		s1[i] = 'a' + i; 
	}
	strcpy(s2, s1);
	int n = strlen(s1);
// Question 1: s1=?, n=?
// Question 2: s2=?, why ?
// Question 3: Rewrite the code for a 5-character string
}

Answer 1: I am pretty sure that the first five characters in s1 are "abcde", but follows by junk. n is unknown.
Answer 2: s2 is unpredictable. The key point is s1 should end by �\0'. Without �\0' strcpy cannot work properly, and it may cause program crash.

Answer 3:

void Test() { char s1[6], s2[6]; s1[5] = '\0'; for(int i=0; i<5; i++) { s1[i] = 'a' + i; } int n = strlen(s1); // =5 strcpy(s2, s1); // s1=s2="abcde"; }

Is there a boundary error of this for-loop?

std::string s1 = "abc"; std::string s2; s2.reserve(s1.size()); for (unsigned int i = s1.size() - 1; i > 0; -- i) { s2 += s1[i]; }

(remove unsigned)

Your own version of strcpy

char * strcpy( char dest, const char src ) { ASSERT( (dest != NULL) && (src != NULL) ); char tmp = dest; while( (dest++ = *src++) != '\0' ); return tmp; }

Length of a string

strlen in "string.h"

char buffer[61] = "How long am I?"; int len = strlen( buffer ); // output is 14

If you wish to count the length by yourself,

int strlen(char s) { char s0 = s; while(*s != '\0') // symbol of end a string s ++; return s - s0; }

Question: Does this counting work? Yes.

strcmp in "string.h"

int strcmp( const char string1, const char string2 ); < 0 string1 less than string2 0 string1 identical to string2 0 string1 greater than string2

If on your own

int strcmp(char s1, char s2) { while (s1 == s2) { if(s1 == '\0') return 0; // Identical s1++; s2++; } return s1 - *s2; }

QString:

Initializing a String

QString str = "Hello QString"; QString space(5, ' '); // 5 white-space

Indexing: The at() function can be faster than operator[](), because it never causes a deep copy to occur.

	str.at(0) == 'H'; 
	str[0] == 'H'; 
	int ll = str.indexOf("ll"); // 2
QString s = "the minimum";
s.indexOf(QRegExp("m[aeiou]"), 0); // 4 for mi

QString x = "crazy azimuths";
QString y = "az";
x.lastIndexOf(y);           // returns 6
x.lastIndexOf(y, 6);        // returns 6
x.lastIndexOf(y, 5);        // returns 2
x.lastIndexOf(y, 1);        // returns -1

Extract substring:

QString left = str.left(5); // "Hello"; QString right = str.right(3); // "ing"; QString mid = str.mid(4,3); // "o Q" take (pos and len=-1)

Manipulating String Data: append(), prepend(), insert(), replace(), and remove().

	QString str = "and";
	str.prepend("rock ");	// str == "rock and"
	str.append(" roll");	// str == "rock and roll"
	str.replace(5, 3, "&");	// str == "rock & roll" 
QString x = "Say yes!";
QString y = "no";
x.replace(4, 3, y); // x == "Say no!" 

QString eng = "colour behaviour flavour neighbour";
eng.replace(QString("ou"), QString("o"));
// str == "color behavior flavor neighbor" 

QRegExp rx("&amp;(?!amp;)");      // match ampersands but not &amp;
QString line2 = "His &amp;amp; hers &amp; theirs";
line2.replace(rx, "&amp;amp;");
// line2 == "His &amp;amp; hers &amp;amp; theirs"

trimmed() (Returns a string that has whitespace removed from the start and the end. )
simplified() (Returns a string that has whitespace removed from the start and the end, and that has each sequence of internal whitespace replaced with a single space. )
chop() (Removes n characters from the end of the string.)

	QString s1 = "  lots\t of\nwhitespace\r\n ";
	s1 = s1.trimmed(); // "lots\t of\nwhitespace"
QString s2 = "  lots\t of\nwhitespace\r\n ";
s2 = s2.simplified();// "lots of whitespace"; 

QString str("LOGOUT\r\n");
str.chop(2); // "LOGOUT"

Distinction Between Null and Empty Strings

	QString().isNull();               // returns true
	QString().isEmpty();              // returns true
QString("").isNull();             // returns false
QString("").isEmpty();            // returns true

QString("abc").isNull();          // returns false
QString("abc").isEmpty();         // returns false

split and join

	QString str; QStringList list;
str = "Some  text\n\twith  strange whitespace.";
list = str.split(QRegExp("\\s+")); // matches a whitespace
// list: [ "Some", "text", "with", "strange", "whitespace." ] 

str = "This time, a normal English sentence.";
list = str.split(QRegExp("\\W+"), QString::SkipEmptyParts); //  matches a non-word character
// list: [ "This", "time", "a", "normal", "English", "sentence" ] 
QString newStr = list.join(" ");

Implement itoa() to compute the string equivalent of an integer number. For example,
value=-1234, string="-1234".
// Test
void main() { int value = -1234; char *s = itoa(value); printf("value=%d, string=\"%s\".", value, s); delete []s; }
Implementation idea: value % 10 + '0' changes the last digit to a char, then divided by 10 and repeat to get a reverse string, then, reverse the string into normal ( Solved. ask for optimized code )

Write a function to replace all space-char by "%20". (Assume that there is enough free memory at the end of the string.) ( Solved. Idea is backward shift and replacement)

void charReplace(char *s, char ch, char *wedge)
{
	int n = strlen(s);
	int count = 0;
	char *ptr=s;
	while(*ptr != '\0') // char end
	{
		if(*ptr == ch)
			count ++;
		ptr ++;
	}
if(count == 0) return; // not found any

int m = strlen(wedge);
int j = n + (count-1)*m;
    for(int i=n; i &gt;= 0; i--)
{	// s+n is '\0'
	if( *(s+i) != ch)
	{
		// shift
		*(s+j) = *(s+i);
		j --;
		continue;
	}

	// replace
            for(int k = m-1; k &gt;= 0; k--)
	{
		*(s+j) = *(wedge+k);
		j --;
	}	
}

}

// Test case

void main()
{
	char *s = new char [128];
	strcpy(s,"This is my laptop.");
	cout <<  s << endl;
charReplace(s,' ', "%20");
cout &lt;&lt;  s &lt;&lt; endl;

delete []s;

}

// output

This is my laptop. This%20is%20my%20laptop.

Which character is the most continuously occurring char in a string? Return the frequency count, and a pointer which points to the 1st char. For example,

Within string:"aaabbbbcddeddddddfg", the most continuously occurring char is 'd', count 6 times. The location index is 11

// Test case

void main()
{
	char s[]="aaabbbbcddeddddddfg";
	char *ptr = NULL; 
	int n = charFreq(s, ptr);
	int index = ptr-s; // gives the location index
	cout << "Within string:\"" << s << "\"," << endl;
	cout << "the most continuously occurring char is '" << *ptr 
		<< "', count " << n << " times." << endl;
	cout << "The location index is " << index << endl;
}

// Implementation

int charFreq(char *s, char *&p)
{
	p = s;		// target location
	int n=0;	// target length
	char *p0;	// potential location
	int count;	// potential length
while(*s != '\0')	// end of the string
{
	count = 0;	// initial
	p0 = s;
	while(*s == *p0)
	{
		count ++;
		s ++;
	}

            if(count &gt; n)   // update
	{
		p = p0; 
		n = count;
	}
}
return n;

}

Reverse a string (Idea: two pointers point to the two ends, swap char, and move toward the center)

#include "stdafx.h"
#include "string.h"
void reverse(char *s, int len=-1)
{
if(*s == '\0') return;
if(len == -1) len = strlen(s);
char *start=s;
char *end = s + len - 1;
char tmp;
    while(end&gt;start)
{
	tmp = *end;
	*end = *start;
	*start = tmp;
	start++;
	end--;
}

}
void main()
{
char str[]="hello";
reverse(str); // "olleh"
}

Does C/C++ allow a negative index? Of course!

int a[]={1,3,5,7,9}, *b=&a[2]; `int c = b[-1]; // 3 int d = b[0]; // 5 int e = b[1]; // 7`

Two ways of passing an array to a function, for example *a, or a[],

void sort1(int *a, int len); void sort2(int a[], int len);

Three ways of an element indexing, for example,

int value = a[2]; int value = *a + 2; int value = 2[a];

When do you use *& ?

Can you please write a set function calculate one period of y=sin(x), bring back x and y in 1-dimensional array, and number of points which you decide to use for calculation?

Answer 1: (General mistake, Wrong Version, Credit: 0%)

int set(double x, double y) { int n = 100; x = new double [n]; y = new double [n]; for(int i=0; i<n; i++) { x[i] = i/n23.14; y[i] = sin(x[i]); } return n; }

Answer 2: (Ok version, Credit: 60%)

Answer 3: (Perfect version, Credit: 100%)

bool set(double *&x, double *&y, int &n)
{
	n = 100;
	x = new double [n]; if(!x) return false;
	y = new double [n]; if(!y) {delete []x; return false;}
	for(int i=0; i<n; i++)
	{
		x[i] = i*2*3.14/n;
		y[i] = sin(x[i]);
	}
	return true;
}

Test case:

void main() { double x, y; int n; if(set(x,y,n)) { delete []x; delete []y; } }

Say their difference between a1, a2 and a3.

void modify(int *a)
{
	a[0] += 1;
}
void main()
{
	int a1[]={1,3,5,7};
	int a2[4]; 
	int *a3 = new int [4];
memcpy(a2,a1,4*sizeof(int));
memcpy(a3,a1,4*sizeof(int));

modify (a1); // a1[0] = 2;
modify (a2); // a2[0] = 2;
modify (a3); // a3[0] = 2;

*(a3+2) = 4; // a3[2] = 4
*(a2+2) = 4; // a2[2] = 4
*(a1+2) = 4; // a1[2] = 4

delete []a3;

}

a1 and a2 are constant pointers, but a3 is not. a3 is a pointer variable.
Memory of a3 is allocated dynamically. It must be freed explicitly (delete []a3;). Otherwise, a memory leak would result.

ADT?
Abstract data type (ADT) is a mathematical specification of a set of data or data operations. ADTs include String, List, Stack, Queue, Binary search tree, Priority queue, Complex number.

List

A linked list

Declaration a list node:

class list { public: list(int i, list* l):value(i), next(l){}; int value; list *next; };

Insert(push) a node on top.

list push(int i, list l) { return new list(i,l); }

How do you reverse a list? (this is a good interview question! If you have good one to share with me please email me.)

list *reverse(list *l)
{
	list *last = NULL;
	list *next;
	while(l)
	{
                next = l->next; // temp store 
            l-&gt;next = last; // modify
	last = l;	// update

	l = next; // Move on
}
return last;

}

Test run:

void main()
{
	// build a sample of list
	list *l = NULL;
	for(int i=0; i<5; i++)
		l = push(i,l);
printList(l);	// [4, 3, 2, 1, 0, ]
l = reverse(l); 
printList(l);	// [0, 1, 2, 3, 4, ]
l = reverse(l);
printList(l);	// [4, 3, 2, 1, 0, ]

empty(l); // Release all

}

How do you duplicate a list?

list *listCopy(list * l)
{
	if(!l) return NULL;
//	Should have at least one node.
	list *newList  NULL;
	while(l)
	{
                newList = push(l->value, newList); 
                // a deep copy of all attributes should be concerned here.
                l=l->next;
	}
	return reverse(newList);
}

How do you print out a list?

void printList(list*l) { printf("["); while(l) { printf("%d, ",l->value); l = l->next; } printf("]\n"); }

How do you dump a list?

list* pop(list l) { list top = l; l = l->next; // move down delete top; // release memory return l; } void empty(list *l) { while(l) l = pop(l); }

Count how many nodes in a list.

int size(list *l) { int count=0; while(l) { count ++; l = l->next; } return count; }

How do you count the distance between two given nodes?

int LengthBetween(list *node1, list *node2=NULL)
{
	int count=0;
	while(node1 != node2)
	{
		count ++;
                node1 = node1->next;
	}
	return count;
}
// Notice that if the second argument is skipped, 
which is exactly the same above.

How do you get the last node of a linked list? [A list ends up with NULL. A challenge question is if the list is looped, where the last node points certain previous node (which can be, but not necessary to be, the head node), How do you find the last node? ]
list *getTail(list *l) { while(l->next) l = l->next; return l; }

How do you delete 2nd last occurrence of a integer from a singly linked list?

void secondLastDel(list *&head, int key) { // Solved }

// Test cases

void main()
{
	list *l = NULL;
	l = push(0,l);
	l = push(1,l);
	l = push(2,l);
	l = push(3,l);
	l = push(2,l);
	l = push(4,l);
	l = push(2,l);
printList(l);

secondLastDel(l,2);
printList(l);

secondLastDel(l,2);
printList(l);

secondLastDel(l,2);
printList(l);

empty(l); // Release all

}

// Output

[2, 4, 2, 3, 2, 1, 0, ] [2, 4, 3, 2, 1, 0, ] [4, 3, 2, 1, 0, ] [4, 3, 2, 1, 0, ]

How do you merge two lists?

void list::merge(list l) { list tail = this->getTail(this); tail->next = l; }; // Test // L1=[4, 3, 2, 1, 0, ] // L2=[6, 4, 2, ] L1.merge(L2); // L1=[4, 3, 2, 1, 0, 6, 4, 2, ]

How do you sort a list? Time complexity is O(nlogn). (worse than tree) The sorting criterion is the operator < defined for the elements.
Deletion from a linked list
Insertion into a linked list

Looped list: the last node (tail), instead of points to NULL, points back to a preceding, but not necessarily the first, node. Interesting questions are:

How do you detect a list is looped or not? Two elegant implimentations: 1. two-pointer chase:

// Test a list is looped or not.
// Idea: two pointers, one moves faster than the other.
//	If looped, there is always a chance of catching up, and
//	return a node on the loop, otherwise, 
//	return NULL, which means the list is none-looped.

//code:

list *isLooped(list *l)
{
	list *p1=l, *p2=l;
        while(p1 && p2)
        {
                p1 = p1->next;
                if(!p2->next) 
                        return NULL;
            p2 = p2-&gt;next-&gt;next;
	if(p1 == p2) 
		return p1;

}
return NULL;

}

2: one-pointer cut and count:

// Return NULL if none-looped, 
// otherwise, return the tail node.
list *isLooped1(list *l)
{
	list *head=l; 
	int m=0, n; 
	while(l)
	{
                n = LengthBetween(head,l->next);
                if(m<n)
                {
                        l = l->next;
			m = n;
		}
		else
			return l;
	}
	return NULL;
}

How do you count how many nodes on the loop?

// Count how many nodes on the loop
int loopCount(list *l)
{
	list *node = isLooped(l);
	if(!node)  // none-looped
		return 0;
//	be aware that 'node' is on the loop.
list *ptr = node->next;
int count = 1;  // initial
while(ptr != node)
{
ptr = ptr->next;
count++;
}
return count;
}

How do you get the last node (tail) of a list in general? (Beyond a normal list, it can be empty, or looped)

list *Tail(list *l)
{
	if( !l ) return NULL; // screen, void empty
list *node = isLooped1(l); // check
if(node) return node; // in case of looped

    while(l-&gt;next)
            l = l-&gt;next;

return l; // in case of none-looped

}

How do you know the total length the list?

// Count from head to tail, return length of a list.
// It doesn't matter if the list is looped or not.
int Length(list *l)
{	if(!l) return 0;
list *tail = Tail(l);
int count=1;
while(l != tail)
{
	count++;
            l = l-&gt;next;
}
return count;

}

How do you break up a looped list without losing any node?

// Break up a looped list. There is no harm if 
//  you call this, but the list has no loop.
void breakLoop(list *l)
{	if(!l) return;
        list *tail = Tail(l); // retrieve tail
        if( tail->next) 
                tail->next = NULL;
}

Others? (pending)

A doubly linked list: Advantage: operations are easily to implement; both directions. Disadvantage: one additional reference is required.

class LinkListNode
{
public:
//	Constructor:
	LinkListNode(LinkListNode* prev, char *str, LinkListNode *next)
		: prev(prev), next(next)
	{
		s = new char [strlen(str)+1];
		strcpy(s,str);
	};
//	Destructor:
~LinkListNode(){delete []s;};
//	Attribute:
char *s;
LinkListNode *next, *prev;
};
typedef struct LinkList
{
LinkListNode *head,
LinkListNode *tail;
} LinkList;

How do you insert a new node before a given node in a doubly linked list?

void insertBefore(LinkList *ll, char *s, LinkListNode *node)
{
        LinkListNode *newNode = new LinkListNode(node->prev, s, node);
        if(! node->prev)
                ll->head = newNode;
        else
                node->prev->next = newNode;
        node->prev = newNode;
}

How do you appendix a new node to a doubly linked list?

void insertEnd(char s, LinkList ll) { LinkListNode *newNode = new LinkListNode(ll->tail, s, NULL); ll->tail->next = newNode; ll->tail = newNode; }

How do you insert the first node to a doubly linked list?

void insertNULL(char s, LinkList ll) { LinkListNode *newNode = new LinkListNode(NULL, s, NULL); ll->head = newNode; ll->tail = newNode; }

How do you use a doubly linked list for sorting?

void insertSort(char *s, LinkList *ll)
{
        LinkListNode *node = ll->head;
        if(!node)
        {
                insertNULL(s,ll);
                return;
        }
    while(node)
    {
            int n = strcmp(s,node-&gt;s);
            if(n &gt; 0)
            {
                    node = node-&gt;next;
                    continue;
            } else
            {
                    insertBefore(ll,s,node);
                    return;
            }
    } 

    insertEnd(s,ll); // Appendix after the tail

}

// Test

void main()
{
	LinkList *ll = new LinkList;
        ll->head = NULL;
        ll->tail = NULL;
char words[][8]={"mouse","dog","quiet",
	"pan","house","raven","zoo","tree"};

for(int i=0;i&lt;8;i++)
{
	insertSort(words[i],ll);
	printList(ll);
}

}

// Output

[mouse, ]
[dog, mouse, ]
[dog, mouse, quiet, ]
[dog, mouse, pan, quiet, ]
[dog, house, mouse, pan, quiet, ]
[dog, house, mouse, pan, quiet, raven, ]
[dog, house, mouse, pan, quiet, raven, zoo, ]
[dog, house, mouse, pan, quiet, raven, tree, zoo, ]

// For sorting method, please see another implementation (binary tree), which gives the similar result. // where the print function is:

void printList(LinkList l) { printf("["); LinkListNode node = l->head; while(node) { printf("%s, ",node->s); node = node->next; } printf("]\n"); }

How do you remoe a node from a doubly linked list? Removing a node is easier, only requiring care with the head and tail.

void remove(LinkListNode *node, LinkList *list)
{
        if(!node->prev)
                list->head = node->next;
        else
                node->prev->next = node->next;
    if(!node-&gt;next)
            list-&gt;tail = node-&gt;prev;
    else
            node-&gt;next-&gt;prev = node-&gt;prev;

    delete node;

}

A double circular linked list

Stack Model: A stack is a list with the restriction that insertion s and deletions can be performed in only one position, namely, top, based on the principle of Last In First Out (LIFO).

template<class Object >
class Stack  
{
public:
        virtual ~Stack();       // Default destructor
        Stack():top(NULL){};    // Default constructor
        Stack(const Stack &rhs); // Copy constructor
        const Stack & operator = (const Stack &rhs);
    bool isEmpty() const;
    void makeEmpty() const;

    void push(const Object &amp;x);
    void pop();

private:
struct ListNode
{
Object element;
ListNode *next;
ListNode(const Object &e, ListNode *n=NULL)
:element(e), next(n){};
};
ListNode *top;

};

Stack.cpp

Queue Model: Queues are lists, where insertion is done at one end, but deletion is performed at the other end.
Hash table: is a data structure that associates keys with values. It supports efficiently loop up. It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value. Hash tables store data in pseudo-random locations, so accessing the data in a sorted manner is a very time consuming operation.

#include <map> 
#include <string>
int main()
{
std::map<std::string, std::string> phone_book;
// insert
phone_book["Sally Smart"] = "555-9999";
phone_book["John Doe"] = "555-1212";
phone_book["J. Random Hacker"] = "553-1337";

// loop-up
std::string phone = phone_book.find("John Doe")-&gt;second;

// iteration
std::map&lt;std::string, std::string&gt;::const_iterator i;
std::list&lt;std::string&gt; names;
for(i = phone_book.begin(); i != phone_book.end(); ++ i)
	names.push_back(i-&gt;first);
unsigned int count = names.size();
return 0;

}

There are two main efficient data structures used to represent associative arrays, the hash table and the self-balancing binary search tree. Hash tables have faster average lookup and insertion time.

Recursion:

Factorial: 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

long factorial(long n) { if(n<1) return 1; // we set 0! = 1 return n*factorial(n-1); }

Fabonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... f(n) = f(n-2)+f(n-1)

int fibonacci(int n) { if(n == 1 \|\| n == 2) return 1; return fibonacci(n-1) + fibonacci(n-2); }

The Binary Trees Data Structure:

List-like structures (list, stack, or queue) are excellent if you have a relative small data volume, and you need sequential record-processing capabilities.

Hash tables provide lightning-fast record access. However, the keys are in no particular order. Therefore, we cannot use hash tables if we are going to do sequential record processing. The binary tree makes possible rapid data access(not quite as good as hash tables, but close enough!) and allows for sequential record processing.

class NODE
{
public:
	NODE(char *w)
		:left(NULL), right(NULL),count(1)
	{
		word = new char [strlen(w)+1];
		strcpy(word,w);
	};
	~NODE(){delete []word;}
char *word; int count;
NODE *left, *right;

};

// insertion

NODE *insert(char *word, NODE *tree)
{
        NODE **ptr = &tree;
    while(*ptr)
    {
            int compare = strcmp(word,(*ptr)-&gt;word);
            if(compare &gt; 0)
                    ptr = &amp;(*ptr)-&gt;right;
            else if(compare &lt; 0)
                    ptr = &amp;(*ptr)-&gt;left;
            else
            {
                    (*ptr)-&gt;count ++; // repeat
                    return tree;
            }
    }

    *ptr = new NODE(word);
    return tree;

}

Comment: The reference used during the insertion is beautiful (advanced level). The iteration loop is stopped while the reference refers to a NULL address. This null address is exactly where the new word should be inserted.

// print

void printTree(NODE *tree)
{
        if(!tree) return;
    printTree(tree-&gt;left);

    if(tree-&gt;count&gt;1)
            printf("%s(%d), ",tree-&gt;word,tree-&gt;count);
    else
            printf("%s, ",tree-&gt;word);

    printTree(tree-&gt;right);

}

// release

void empty(TreeNode *tree) { if(!tree) return; empty(tree->left); empty(tree->right); delete tree; }

// Test code

void main()
{
	char words[][11]={"mouse","dog","quiet",
		"pan","house","raven","zoo","tree","abc","pen","dog"};
NODE *tree = NULL;
for(int i=0;i&lt;11;i++)
	tree = insert(words[i],tree);

printTree(tree);
empty(tree); // Release memory

}

////// output is ordered /////////

abc, dog(2), house, mouse, pan, pen, quiet, raven, tree, zoo,

(click to download an executable file to play)

Check a tree is sorted or not?

Let us assume that each node in a binary tree contains an integer value and two pointers to next-level nodes: "left" and "right". We call a tree sorted if for each node the following statement is correct: "All values in the left subtree are less than or equal to the value of the node, and all values in the right subtree are greater than the value of the node." Write a function that takes a pointer to a root of a tree and checks whether the tree is sorted.

Find the minimum value of a tree.

void findMin(NODE *t, int &mi)
{
        if(!t) return; 
    findMin(t-&gt;left, mi);

    if(mi &gt; t-&gt;value)
            mi = t-&gt;value;

    findMin(t-&gt;right, mi);

}

Find the maximum value of a tree.

void findMax(NODE *t, int &ma)
{
        if(!t) return; 
    findMax(t-&gt;left, ma);

    if(ma&lt;t-&gt;value)
            ma = t-&gt;value;

    findMax(t-&gt;right, ma);

}

How do you detect whether a tree is sorted?

bool isSorted(NODE *t)
{
        if(!t) return true; // trivial, no violation 
    if(t-&gt;left)
    {
            int tmp = t-&gt;left-&gt;value; // initial
            findMax(t-&gt;left, tmp);
            if(tmp &gt; t-&gt;value)      // Violate 
                    return false;
    }

    if(t-&gt;right)
    {
            int tmp = t-&gt;right-&gt;value; // initial
            findMin(t-&gt;right, tmp);
            if(tmp &lt;= t-&gt;value)  // Violate 
                    return false;
    }

    return true;

}

// Test code

Quicksort:

is the fastest sorting algorithms in practice. The average computational complexity is O(n log n). The strategy is called "Divide and conquer" (D&C)

Steps are:

Pick an element, called a pivot.
Reorder the list into two sub-list, less and greater.
Recursively sort each sub-list.

There are several versions of omplimentation. Here is one called in-place partition.

void swap(int &a, int &b){int t=a; a=b; b=t;}
// "a" is an 1D array, len = end - start;
void qSort(int *a,  int end, int start=0)
{
if (end -1 <= start) return;
int pivot = (a[start] + a[end-1] + a[end-start])/3,
left = start, right = end-1;
while (left<right)
{
if (a[left] <= pivot)
left ++;
else
{
right --;
swap(a[left], a[right]);
}
}
left --;
swap(a[left], a[start]);
qSort(a, left, start);
qSort(a, end, right);
}
void main()
{
int a[9]={1,7,9,3,4,8,5,2,6};
qSort(a,9);
}

Note: The pivot choosing is flexible. Actually, by choosing a good pivot, one can achieve O(log n) space use on average.

Bubble sort:

is a straightforward and simplistic method of sorting. It needs O(n^2) comparisons to sort n items and can sort in-place.

void BubbleSort(int *a, int len) { int i, j; for(i=0; i<len; i++) { for(j=i+1; j<len; j++) { if(a[j]<a[i]) swap(a[j],a[i]); } } } void main() { int a[9]={1,7,9,3,4,8,5,2,6}; BubbleSort(a,9); }

Sorting methods comparison:

Name	Best	Average	Worst	Memory	Stable	Method
Bubble sort	O(n)	---	O(n²)	O(1)	Yes	Exchanging
Binary tree sort	O(nlog(n))	O(nlog(n))	O(nlog(n))	O(1)	Yes	Insertion
Quicksort	O(nlog(n))	O(nlog(n)	O(n²)	O(log n)	No	Partitioning

Multidimensional arrays

	int a[2][3]={{0,1,2},{3,4,5}}; // 2D array, [row][col]
    int *pt = &amp;a[0][0]; // 1D array, for example, pt[4] is 4
    int *pt0 = a[0];        // exactly the same above, pt0[4] = 4
    int *pt1 = a[1];        // 1D array, start from the second row

    memset(&amp;a[0][0], 0, 9*sizeof(int)); // Uniform initial 

//	memset(a, 0, 9*sizeof(int)); // Wrong !
//	nonuniform, dynamic declaration
int *b = new int [2]; // Two rows
b[0] = new int[3]; // This row has 3 elements
b[1] = new int[5]; // This row has 5 elements
delete []b[0];
delete []b[1];
delete []b; // Only this is not enough! Without above two, memory leek!

Spiral initialization:

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

Write a routine that initializes an N×N matrix like a spiral, for examples, N=4 and 5 the matrixes should be.
void SpiralIni(int **A, int N) { // (Solved. email me asking for code ) }

Magic Square: A magic square is a square of side s can be represented by an s×s 2-dimensional array. What makes this square magical is that when you fill each cell with an integer from 1 to s^2 (no duplicates), the sums of all rows, columns, and diagonals are equal.

Magic square of size 3 Magic Sum = 15
8	1	6
3	5	7
4	9	2

Magic square of size 5 Magic Sum = 65
17	24	1	8	15
23	5	7	14	16
4	6	13	20	22
10	12	19	21	3
11	18	25	2	9

Magic square of size 7 Magic Sum = 175
30	39	48	1	10	19	28
38	47	7	9	18	27	29
46	6	8	17	26	35	37
5	14	16	25	34	36	45
13	15	24	33	42	44	4
21	23	32	41	43	3	12
22	31	40	49	2	11	20

Want make a check?

Magic Square Check for size = 7:
Row Check:
        sum(30,39,48,1,10,19,28) = 175
        sum(38,47,7,9,18,27,29) = 175
        sum(46,6,8,17,26,35,37) = 175
        sum(5,14,16,25,34,36,45) = 175
        sum(13,15,24,33,42,44,4) = 175
        sum(21,23,32,41,43,3,12) = 175
        sum(22,31,40,49,2,11,20) = 175
Column Check:
        sum(30,38,46,5,13,21,22) = 175
        sum(39,47,6,14,15,23,31) = 175
        sum(48,7,8,16,24,32,40) = 175
        sum(1,9,17,25,33,41,49) = 175
        sum(10,18,26,34,42,43,2) = 175
        sum(19,27,35,36,44,3,11) = 175
        sum(28,29,37,45,4,12,20) = 175
Diagonal Check:
        sum(30,47,8,25,42,3,20) = 175
Off-diagonal Check:
        sum(22,23,24,25,26,27,28) = 175

>

Magic square of size 17 Magic Sum = 2465
155	174	193	212	231	250	269	288	1	20	39	58	77	96	115	134	153
173	192	211	230	249	268	287	17	19	38	57	76	95	114	133	152	154
191	210	229	248	267	286	16	18	37	56	75	94	113	132	151	170	172
209	228	247	266	285	15	34	36	55	74	93	112	131	150	169	171	190
227	246	265	284	14	33	35	54	73	92	111	130	149	168	187	189	208
245	264	283	13	32	51	53	72	91	110	129	148	167	186	188	207	226
263	282	12	31	50	52	71	90	109	128	147	166	185	204	206	225	244
281	11	30	49	68	70	89	108	127	146	165	184	203	205	224	243	262
10	29	48	67	69	88	107	126	145	164	183	202	221	223	242	261	280
28	47	66	85	87	106	125	144	163	182	201	220	222	241	260	279	9
46	65	84	86	105	124	143	162	181	200	219	238	240	259	278	8	27
64	83	102	104	123	142	161	180	199	218	237	239	258	277	7	26	45
82	101	103	122	141	160	179	198	217	236	255	257	276	6	25	44	63
100	119	121	140	159	178	197	216	235	254	256	275	5	24	43	62	81
118	120	139	158	177	196	215	234	253	272	274	4	23	42	61	80	99
136	138	157	176	195	214	233	252	271	273	3	22	41	60	79	98	117
137	156	175	194	213	232	251	270	289	2	21	40	59	78	97	116	135

( MagicSq.exe )

( email me asking for code )

One way to generate a magic square

Place the number 1 in the middle column of row 0.
From this starting position (original position) go up one cell and to the right one cell and place the next integer in that cell. If moving up forces you out of bounds, wrap around and continue from the corresponding cell in the bottom row.
Do the same thing if you go out of bounds when moving right.
If the cell you are moving to has already been filled, drop down one cell from your original position and place the integer there instead.
Do this until all the cells are filled.

The Magic Sum can be calculated:

int calculateMagicSum(int s) { return sumDownToOne(s*s)/s; } int sumDownToOne(int positiveNumber) { if(positiveNumber <= 1) return 1; return positiveNumber + sumDownToOne(positiveNumber-1); }

Write a function, count how many words in a sentence.

#include "string.h"
#include "ctype.h"
int wordCount(char *s)
{
	unsigned int pos=0,count=0,len=strlen(s);
	while(pos<len)
	{
                while(isspace( *(s+pos)) && pos<len) 
                        pos ++; // go through space
            if(pos&lt;len) count ++;
            while(!isspace( *(s+pos)) &amp;&amp; pos&lt;len)
		pos ++; // go through non-space
}
return count;

}

Write a function to extract words from a sentence into an array.

int wordExtract(char *s, char **word, unsigned int size)
{
	unsigned int pos=0,count=0,len=strlen(s);
	char buffer[128]; // long enough for a single word, if not, not safe!
	while(pos<len)
	{
                while(isspace( *(s+pos)) && pos<len) 
			pos ++;	// go through space
	if(pos&lt;len)
	{
		sscanf(s+pos, "%s", buffer);
		int l = strlen(buffer); // 
		word[count] = new char [l+1];
		strcpy(word[count],buffer);
		count ++;
                    if(count &gt; size-1) return count; // full

		pos += l;
	}
}
return count; // return number of words

}
void main()
{
char s[]={" I'd like to see a red fox. "};
int n = wordCount(s); 
char **word = new char* [n];
int m = wordExtract(s,word,n);

for(int i=0;i&lt;m;i++) delete []word[i];
delete []word;
return 0;

}

Reverse a sentence without reversing letters in words, for example:

// I'd like to see a red fox. // fox. red a see to like I'd

void main()
{
	char s[]={" I'd like to see a red fox. "};
int n = wordCount(s); 
char **word = new char* [n];
int m = wordExtract(s,word,n);

list *l = NULL;
for(int i=0; i&lt;m; i++)
	l = push(word[i], l);

printList(l); // [fox. red a see to like I'd ]
l = reverse(l);
printList(l); // [I'd like to see a red fox. ]

for(i=0;i&lt;m;i++) delete []word[i];
delete []word;

empty(l);

}

(If you have a better solution, please send me an email)

Use two pointers to reverse a sentence in situ without additional memory cost.

void reverseSentance(char *s)
{
	reverse(s); // click here for implementation 
	char *start=s;
	char *end;
do{
	while(isspace(*start)) 
		start++;	// skip space

	if(*start == '\0')
		break;		// reach the end

	end = start;
	while(!isspace(*end))
		end++;		// skip none-space

            if(end-start &gt; 1)
		reverse(start,end-start); // reverse a word

	start = end;
}while(1);

}

struct | class | union | enum

struct: In C++, a structure is the same as a class except that its members are public by default.

union:A union is a user-defined data type. A C union type can contain only data members. A C++ union is a limited form of the class type. It can contain member data, and member functions, including constructors and destructors. It cannot contain virtual functions or static data members. It cannot be used as a base class, nor can it have base classes. Default access of members in a union is public. In C++, the union keyword is unnecessary.

enum: An enumerated type is a user-defined type consisting of a set of named constants called enumerators. By default, the first enumerator has a value of 0, and each successive enumerator is one larger than the value of the previous one, unless you explicitly specify a value for a particular enumerator.

// Example of the enum keyword
enum Days		// Declare enum type Days
{
   saturday,	// saturday = 0 by default
   sunday = 0,	// sunday = 0 as well
   monday,		// monday = 1
   tuesday,		// tuesday = 2
   wednesday,	// 3
   thursday,	// 4
   friday		// 5
} today;		// Variable today has type Days

namespace: A namespace declaration identifies and assigns a name to a declarative region. For example:
namespace foo { int bar;}
Within this block, identifiers can be used exactly as they are declared. Outside of this block, the namespace specifier must be prefixed. However, with
using namespace foo;
to a piece of code, the prefix foo:: is no longer needed. (Namespace resolution in C++ is hierarchical, like food::soup::chicken )

What is a constructor? What is a desconstructor?
A member function with the same name as its class is a constructor function. Constructors cannot return values.
Destructor is a function which is called when objects are destroyed (deallocated).
Designate a function as a class's destructor by preceding the class name with a tilde (~). The destructor is commonly used to "clean up" when an object is no longer necessary.

Using inline initialization in constructor in the same order of your variable declarations. If not, vs2005 is OK, gcc show complain. If no reference, no pointer, the order does not matter; otherwise, the order is important.

What is the difference between a copy constructor and an overloaded assignment operator?

A copy constructor constructs a new object by using the content of the argument object.

X(X const&);

The compiler invokes a copy constructor wherever it needs to make a copy of the object. If you do not provide a (explicit) copy constructor, the compiler creates a (implicit) member-by-member shallow copy constructor for you.

An implicit shallow copy constructor is ok if there is no pointer types of members. For example,

class A { public: A(int m, int n):v0(m),v1(n){}; private: int v0, v1; };

void main() { A a1(1,2); A a2(a1); // invoke implicit shallow constructor A a3 = a2; }

If there are pointer members, create an explicit deep copy contructor to make sure the storage get copied as well.

class X { public: X(int row, int col); X(X const&); // explicit copy constructor ~X(){delete m_array;}; int index(int i)const; bool set(int i, int value); private: int m_row, m_col; int *m_array; };

X::X(int row, int col)
: m_row(row), m_col(col)
{
	m_array = new int [m_row*m_col];
	int index;
	for(int i=0; i<m_row; ++i)
	{
		for(int j=0; j<m_col; ++j)
		{
			index = i*m_row + j;
			m_array[index] = index;
		}
	}
};

X::X(X const&x) // explicit copy constructor
{
	m_row = x.m_row;
	m_col = x.m_col;
	m_array = new int [m_row*m_col];
	int index;
	for(int i=0; i<m_row; ++i)
	{
		for(int j=0; j<m_col; ++j)
		{
			index = i*m_row + j;
			m_array[index] = x.m_array[index];
		}
	}
};

int X::index(int i)const { if(i<0 \|\| i>m_row*m_col-1) // out-of-range return -1; return m_array[i]; }

bool X::set(int i, int value) { if(i<0 \|\| i>m_row*m_col-1) // out-of-range return false; `m_array[i] = value; return true;` }

void main()
{
	X x1(2,3);
	X x2(x1);
	X x3 = x1;
int a = x1.index(3);
int b = x2.index(3);
int c = x3.index(3);

x1.set(3, 30);
a = x1.index(3);
b = x2.index(3);
c = x3.index(3);

}

An overloaded assignment operator assigns the contents of an existing object to another existing object of the same class. You can write overloaded assignment operators that take arguments of other classes, but that behavior is usually implemented with implicit conversion constructors. If you do not provide an overloaded assignment operator for the class, the compiler creates a default member- by-member assignment operator.

X::X(X const&x) // explicit copy constructor
{
	*this = x; // invoke overloaded assignment operator
};
X& X::operator = (const  X&x)
{
	if (this == &x) 
		return *this; // needn't
// deep copy
m_row = x.m_row;
m_col = x.m_col;
m_array = new int [m_row*m_col];
int index;
for(int i=0; i&lt;m_row; ++i)
{
	for(int j=0; j&lt;m_col; ++j)
	{
		index = i*m_row + j;
		m_array[index] = x.m_array[index];
	}
}
return *this;

}

void main() { X x1(2,3); X x2(x1); // invoke copy constructor X x3 = x1; // invoke copy constructor x3 = x1; // invoke overloaded assignment operator }

Why inheritance?
- To separate abstract data type (ADT) programming from OO programming (abstract base class/interface)
- To reuse/share code (implementation inheritance.)
- To categorize (generalize), for example, a "fruit" is a generalization of "apple", "orange", "mango" and many others.

"Diamond problem" | virtual inheritance

class A
{
public:
	void foo(){};
};
class B : public A
{
};
class C : public A
{
};
class D : public  B, public  C
{
};
int main(int argc, char *argv[])
{
D *d = new D;
d->foo(); // ambiguous!
delete d;
return 0;
}

class A
{
public:
void foo(){};
};
class B : virtual public A
{
};
class C : virtual public A
{
};
class D : public  B, public  C
{
};
int main(int argc, char *argv[])
{
D *d = new D;
d->foo(); // fine!
delete d;
return 0;
}

class A
{
public:
	virtual void foo()=0;
};
class B : virtual public A
{
public:
void foo(){};
};
class C : virtual public A
{
public:
void foo(){};
};
class D : public B, public  C
{
}; // ambiguous!!
int main(int argc, char *argv[])
{
D *d = new D;
d->foo(); // ambiguous!
delete d;
return 0;
}

class A
{
public:
virtual void foo()=0;
};
class B :  public A
{
public:
void foo(){};
};
class C :  public A
{
public:
void foo(){};
};
class D : public  B, public  C
{
public:
void foo(){};
};
int main(int argc, char *argv[])
{
D *d = new D;
d->foo(); // fine!
delete d;
return 0;
}

Casting in C/C++

Four casting operators:

static_cast const_cast dynamic_cast, and reinterpret_cast

class B {};
class C : public B {};
class D : public C {};
void upCast(D* pd)
{
C* pc = dynamic_cast<C* > (pd);

// ok: C is a direct base class
// pc points to C subobject of pd
B* pb = dynamic_cast<B* > (pd);

// ok: B is an indirect base class
// pb points to B subobject of pd
}
void downCast()
{
B* pb = new D;
B* pb2 = new B;
D* pd = dynamic_cast<D*>(pb);
D* pd2 = dynamic_cast<D*>(pb2);
//	error C2683: dynamic_cast : 'B' is not a polymorphic type
}

Virtual function: a function that when overridden by a subclass will be used by the base class. For example, a base class Animal could have a virtual function eat. Subclass Fish would implement eat differently than subclass Wolf, but you can invoke eat on any base class instance, and get the behavior of the specific subclass --- this is the beauty of polymorphism from the virtual function.

class Animal{public:virtual int eat(){return 0;};};
class Fish : public Animal{public:	int eat(){return 1;};};
class Wolf : public Animal{public:	int eat(){return 2;};};
class Cat : public Animal{};
class Dog : public Animal{public:	virtual int eat(int amont=0){return 4;};};
class Puppy : public Dog{public:	int eat(){return 5;};};
void main()
{
Animal *fish = new Fish;
Animal *wolf = new Wolf;
Animal *cat = new Cat;
Animal *dog = new Dog;
Animal *puppy = new Puppy;
    int i = fish-&gt;eat(); // 1
    int j = wolf-&gt;eat(); // 2
    int k = cat-&gt;eat(); // 0  
    int l = dog-&gt;eat(); // 0
    int m = puppy-&gt;eat(); // 5

delete fish; delete wolf; delete cat; delete dog; delete puppy;

}

Comments:

To receive run-time operator identification treatment must have exactly the same signature! (1) Cat has no overriding, so Animal::eat is invoked. (2) Dog does have a function named eat, but with a different signature. This is NOT an overridden function. (3) Though Dog has a vertual function 'eat', and Puppy is derived directly from Dog (not directly from Animal), due to signature difference, actually Puppy does not override 'eat' from his daddy, instead, it does override its grandpa!
A virtual function is to be chosen at run-time. Run-time operator identification applies only to references or pointers to class object.
What is VTABLE? which is an array of function pointers for looking up virtual functions' connection.
Pure Virtual Functions by placing = 0 at the end of its declaration.

An abstract class contains at least one pure virtual function. You cannot declare an instance of an abstract base class; you can use it only as a base class when declaring other classes.

An interface is a class which contains only pure virtual functions, and has no data members. A client use pointer to the interface, and won't need to count the size of an interface. All data are hidden from the client; all data are implemented in the inherited classes. In naming convention, an interface class starts with "I".

A co-class(coclass) supplies concrete implementation(s) of one or more interfaces. C++ does not allow to create an instance of an interface or abstract class because of the pure virtual function(s).

COM (Component Object Model) is a language-neural way of implementing objects so they can be used in different environment from where they were created in. COM has a well-defined interfaces which separate from the implementation. Follow one uniform interface, provide multiple implementation to perform different ways at runtime - this is the power of polymorphism.

IDispatch is one of the standard interfaces that can be exposed by COM. IDispatch derives from IUnknown, extends three methods (AddRef, Release, QueryInterface),adds four more methods(GetTypeInfoCount, GetTypeInfo, GetIDsOfNames, and Invoke).

For example,

class XXX_EXPORT ITableAx : public QAxObject { public: ITableAx(IDispatch subobject = 0, QAxObject parent = 0) : QAxObject((IUnknown*)subobject, parent) { ... } }

where,

QAxObject::QAxObject ( IUnknown * iface, QObject * parent = 0 )

Creates a QAxObject that wraps the COM object referenced by iface. parent is propagated to the QObject contructor.

In PowerPoint wrapper, to add an activeX control and custimize it needs IDispatch interface,

PowerPoint::Shape *shape = slide->Shapes()
	->AddOLEObject(l, t, w, h, className, false);
if(shape)
{
	PowerPoint::OLEFormat* fmt = shape->OLEFormat();
	IDispatch *idispatch = fmt->Object();
	if(idispatch)
	{
		XXXLib::ITableAx iobj(idispatch);
		iobj.dynamicCall("setFileName(QString)", path );
	}
}

Can a destructor be virtual? Can a constructor be virtual? A destructor can be virtual, even pure virtual. It is quite often used in inheritance, for example regarding memory release. But a constructor cannot be virtual.

Can a virtual function be private? Yes. It works well, and it does not block anything.

class A { public: void foo() { bar();} private: virtual void bar() { ...} }; class B: public A { private: virtual void bar() { ...} };

Where does it reach if a virtual function is called from its constructor or destructor? Its own one, never go beyond.

class A
{
public:
	A() { foo();} 	// invoke A::foo
	~A() { foo();}	// invoke A::foo
	virtual void foo(){};
};
class B: public A
{
public:
	void foo(){};
};
void main(int argc, char* argv[])
{
A * a = new B; // never reach B::foo
delete a;
}

overload, override, overload-and-override
1. override: A derived class overrides a virtual function in the base class.
2. overload: Same function name but different signature.
  int addup(int i, int j){return i+j;}; int addup(int i, int j, int k){return i+j+k;}; void main() { int m = addup(1,2); int n = addup(1,2,3); }
3. overload-and-override example

Exception handling: Exception handling is designed to handle the occurrence of some condition that changes the normal flow of execution. The condition is called an exception. Here is an example.

#include "stdafx.h"
#include <iostream.h>
class CTest
{
public:
CTest(){cout << "5: Constructing CTest." << endl;};
~CTest(){cout << "6: Destructing CTest." << endl;};
const char *ShowReason() const { return "9: Exception in CTest class."; }
};
class D
{
public:
D();
~D();
};
D::D(){cout << "3: constructing class B." << endl;}
D::~D(){cout << "7: destructing class B." << endl;}
void MyFunc()
{
cout << "2: enter MyFunc()" << endl;
D d;
cout << "4: still in MyFunc()" << endl;
throw CTest();
cout << "skipped !" << endl;
}

void main()
{
    cout << "1: start in main()" << endl;
    try
    {
        MyFunc();
	    cout << "skipped !" << endl;
    }
    catch( CTest E )
    {
        cout << "8: In catch handler." << endl;
        cout << E.ShowReason() << endl;
    } // Destructing E and ?
    catch( char *str )
    {
        cout << "Caught some other exception: " << str << endl;
    }
    cout << "10: Back in main. Execution resumes here." << endl;
}

// The output

1: start in main()
2: enter MyFunc()
3: constructing class B.
4: still in MyFunc()
5: Constructing CTest.
6: Destructing CTest.
7: destructing class B.
8: In catch handler.
9: Exception in CTest class.
6: Destructing CTest.
6: Destructing CTest.
10: Back in main. Execution resumes here.

Exception classes in MFC:

CFileException

	CString filename="";
	try
	{
		CFile f( filename, CFile::modeRead );
	}
	catch( CFileException* e )
	{
/*
		char msg[256];
                e->GetErrorMessage(msg,256);
                AfxMessageBox(msg);
*/
                switch(e->m_cause)
		{
		case CFileException::fileNotFound:
			AfxMessageBox("The file could not be located.");
			break;
		case CFileException::badPath:
			AfxMessageBox("All or part of the path is invalid.");
			break;
		case CFileException::accessDenied:
			AfxMessageBox("The file could not be accessed.");
			break;
		default:
			AfxMessageBox("unlisted cause.");
			break;
		}
                e->Delete(); // should delete explicitly, otherwise, memory leaks!
	}

// Test

// Input filename="" 
// cause = CFileException::badPath,	
// msg = "an unnamed file contains an invalid path."
// Input filename="sdjhf"
// cause = CFileException::fileNotFound,
// msg = "sdjhf was not found."

CMemoryException

        int size = -10;
        try
        {
                double *ptr = new double [size]; // Throw CMemoryException
//              int *ptr = new int [size]; // crash anyway
        }
        catch( CMemoryException* e )
        {
                char msg[256];
                e->GetErrorMessage(msg,256);
                AfxMessageBox(msg);
//              e->Delete();
        }
// Output message: msg="Out of memory."

namespace [identifier] { namespace-body } A namespace declaration identifies and assigns a name to a declarative region. The identifier must be unique.

class dog { public: dog(){strcpy(name, "Clifford");}; private: char name[20]; };

namespace ur { class dog { public: dog(){strcpy(name, "Cajun");}; private: char name[20]; }; };

namespace my { class dog { public: dog(){strcpy(name, "Cleo");}; private: char name[20]; }; };

void main() { dog Dog = new dog; my::dog mine = new my::dog; ur::dog *your = new ur::dog; `delete Dog; delete your; delete mine;` }

What do you mean by inline function?
The idea behind inline functions is to insert the code of a called function at the point where the function is called. If done carefully, this can improve the application's performance in exchange for increased compile time and possibly (but not always) an increase in the size of the generated binary executables.
(new and delete) vs (malloc and free)

new/delete an object (C++ style) => allocate/release memory + call its constructor/destructor.

malloc/free (C style) => the destructor and constructor do not get called.
Multithread Programs:
1. A thread is basically a path of execution through a program. It is also the smallest unit of execution that Win32 schedules.
2. A process consists of one or more threads. Each thread in a process operates independently.
3. Difference between a thread and a process:
  - A process has one or more than one threads.
  - Different threads of the same process can share resources, but different processes do not.
  - Thread is lighter, but process is heavier.
4. Multithread Synchronization classes in MFC:
  - Use CEvent if the application have to wait for something to happen before it can access the resource.
  - Use CSemaphore if more than one thread within the same application access this resource at one time
  - Use CMutex if more than one application can use this resource, otherwise use CCriticalSection
5. CMultiLock: represents the access-control mechanism used in controlling access to resources in a multithreaded program. Use CMultiLock when there are multiple objects that you could use at a particular time. Use CSingleLock when you only need to wait on one object at a time.
Singleton | thread safety | double-checked locking ..
Singleton means a single object restriction to a class - The constructor is hidden (private or protected). To create an instance is by a method, through which the first time call creates a new instance and returns, then, later call returns a reference of the existing object.
class Sgt { public: static Sgt *i(); // instance method private: Sgt(){}; // private empty constructor static Sgt *sgt; // Singleton };
The instance method is:
Sgt *Sgt::sgt = NULL; // initial Sgt *Sgt::i() { if(!sgt) sgt = new Sgt; // creation return sgt; }
The above creation method works fine in a single-threaded environment. In multithreaded applications, this method is not thread-safe.

The danger comes from the new method may cost time. Let's assume the first thread is in the process of creating object but not yet assigned the pointer, meanwhile, the second thread passes the check point, then what ???

To make the method thread-safe, a lock is needed.
Sgt *Sgt::i() { MutexLocker lock; // lock in constructor, unlock in destructor if(!sgt) sgt = new Sgt; // creation return sgt; }
Then, the argument is the cost. The lock is needed only for the first call, why all later calls carry the burden - this where the Double-Checked Locking Pattern (DCLP) comes.
Sgt *Sgt::i() { if(!sgt) // 1st check { MutexLocker lock; if(!sgt) // 2nd check sgt = new Sgt; } return sgt; }
Is DCLP safe? See "C++ and the Perils of Double-Checked Locking" here
Template: myPoint

vector basic

Coordinate: v[3]={vx,vy,vz}

Length:

double vecLen(const double v) { return sqrt(v[0] v[0] + v[1] * v[1] + v[2] * v[2]); }

Normalize:

void vecNormalize(double *v) { double len = vecLen(v); if(len == 0) return; `for(int i=0; i<3; i++) v[i] /= len;` }

Addition:

// v = v1+ v2 void vecAdd(const double v1, const double v2, double *v) { v[0] = v1[0] + v2[0]; v[1] = v1[1] + v2[1]; v[2] = v1[2] + v2[2]; }

Subtraction:

// v = v2 - v1 void vecSub(const double v2, const double v1, double *v) { v[0] = v2[0] - v1[0]; v[1] = v2[1] - v1[1]; v[2] = v2[2] - v1[2]; }

Multiplication:

A vector is multiplied by a number (scalar multiplication):

Dot product of two vectors: (length of a times projection of b on a)

// Dot productions of two vectors, v1.v2 = v2.v1 double vecDot(const double v1, const double v2) { return v1[0]v2[0] + v1[1]v2[1] + v1[2]*v2[2]; }

Cross product of two vectors: (its direction follows the right-hand-rule, its length gives an area)

// Cross production of two vectors, i.e. v = v1 x v2 = - v2 x v1
void vecCross(const double *v1, const double *v2, double *v)
{
    v[0] = (v1[1] * v2[2]) - (v1[2] * v2[1]);
    v[1] = (v1[2] * v2[0]) - (v1[0] * v2[2]);
    v[2] = (v1[0] * v2[1]) - (v1[1] * v2[0]);
}

Distance of a point to a line:

double Dist2Line(double *v0, const double *v1, const double *v2)
{
	double u[3]; vecSub(v2,v1,u);
	double w[3]; vecSub(v0,v1,w);
	double x[3]; vecCross(u,w,x);
return vecLen(x) / vecLen(u);

}

or, you can get the foot first, then, return distance.

// get the foot point
// Input: v0 is a 3D point, v1, v2 are two points on a line
void vecFoot(const double *v0, const double *v1, const double *v2, double *v)
{
	double v12[3]; vecSub(v2,v1,v12);
	double v10[3]; vecSub(v0,v1,v10);
	double c = vecDot(v12,v10)/vecDot(v12,v12);
	for(int i=0; i<3; i++)
		v[i] = v1[i] + c*(v2[i]-v1[i]); // or *v12[i]
}
// get the distance of a point to a line
// Input: v0 is a 3D point, v1, v2 are two points on a line
double verticalDist(double *v0, const double *v1, const double *v2)
{
double foot[3]; vecFoot(v0,v1,v2,foot);
return vecDist(v0,foot);
}

Distance of a point to a line segment:

// Get the distance of a point to a segment
// Input: v0 is a 3D point, v1, v2 are two ends of a segment
// Return: the shortest distance between a point to a segment
double Dist2Seg(double *v0, const double *v1, const double *v2)
{
	double v12[3]; vecSub(v2,v1,v12);
	double v10[3]; vecSub(v0,v1,v10);
	double dotp = vecDot(v12,v10); // Dot product
	double L = vecLen(v12); // Length of the segment
if( dotp&lt;0)
	return vecDist(v0,v1);

    if( dotp &gt; L*L)
	return vecDist(v0,v2);

// the vertical distance is the shortest
double vcr[3]; vecCross(v12,v10,vcr);
return vecLen(vcr) / L;

}

or, you can prersent as this:,

double Dist2Seg(double *v0, const double *v1, const double *v2)
{
	double v12[3]; vecSub(v2,v1,v12);
	double v10[3]; vecSub(v0,v1,v10);
double c = vecDot(v12,v10) / vecDot(v12,v12);
if(c&lt;0)
	return vecDist(v0,v1);
    else if(c&gt;1)
	return vecDist(v0,v2);

//	projection of v10 stays between two ends of the segment
double foot[3];
for(int i=0; i<3; i++)
foot[i] = v1[i] + c*(v12[i]); // v1->2 = v2-v1
return vecDist(v0,foot);

}

Distance between two lines. (none-parallel)

// Get the shortest distance btween two lines.
// Input: lines are presented by two points, respectively.
double Dist2Lines(const double *v1, const double *v2, 
                  const double *v3, const double *v4)
{
	double u[3],v[3],w[3],x[3];
	vecSub(v2,v1,u);
	vecSub(v4,v3,v);
	vecSub(v3,v1,w);
	vecCross(u,v,x);
	return fabs(vecDot(w,x)) / vecLen(x);
}

How do you calculate the distance between a point and a plane?

How do you know 4 points are coplane or not?

if(Dist2Plane(v1,v2,v3,v4) == 0) // coplane

How do you know 2 segments are coplane or not?(The same above)

Square Matrix

Determinant: a scalar quantity, the absolute value of a 3x3 matrix is equal to the volume of a parallelpiped basic vectors.

double SquareMatrix::determinant( void) const 
{
	if(m_order == 1) 
		return m_element[0];
	double d = 0;
	for ( int i = 0; i<m_order; ++i) 
	{
		int sgn = ( i % 2) ? -1 : 1;
		SquareMatrix cf(m_order -1);
                cf = this->Cofactor(i,0);
		d += sgn * m_element[i*m_width + 0] * cf.determinant();
     }
     return d;
}

Transpose:

void Matrix::transpose()
{
	Matrix T(*this);
	swap(m_width,m_height);
int i,j;
for(i=0; i&lt;m_height; i++)
{
	for(j=0; j&lt;m_width; j++)
	{
		m_element[i*m_width+j] = T.m_element[j*T.m_width+i];
	}
}

}

Adjoint:

SquareMatrix SquareMatrix::adjoint( void) const
{
     SquareMatrix b(m_order);
 for ( int i = 0; i&lt;m_order; i++)
 {
	 for ( int j = 0; j&lt;m_order; j++) 
	 {
		int sgn = ( (i+j)%2) ? -1 : 1;
                    SquareMatrix sq(this-&gt;Cofactor(i,j));
		b.m_element[i*m_width + j] = sgn * sq.determinant();
	 }
 }
b.transpose();
return b;

}

Inverse:

SquareMatrix SquareMatrix::inverse( void)const
{
 SquareMatrix b(m_order);

 for ( int i = 0; i&lt;m_order; i++)
 {
	 for ( int j = 0; j&lt;m_order; j++) 
	 {
		int sgn = ( (i+j)%2) ? -1 : 1;
                    SquareMatrix sq(this-&gt;Cofactor(i,j));
		b.m_element[i*m_width + j] = sgn * sq.determinant();
	 }
 }
b.transpose();
    b /= this-&gt;determinant();
return b;

}

Eigenvalues:

void SquareMatrix::eigenvalue(double *v)const
{
        int N = this->m_order;
	double* Qv = new double [N*N];
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
			Qv[i*N+j] = 0;
		Qv[i*N+i] = 1;	// The diagonal
	}
Hessenberg(Qv);
QR(v);
delete []Qv;

}

Standard Affine Transformations:
1. Translation
2. Rotation
3. Scaling
4. Reflection
5. Shear

Trackball rotation controller:

Quaternions: {x,y,z; w} for rotation axis, and the rotation angle to void Gimbal-lock.

How do you normalize a quaternion?

void TrackBall::normalize_quat(float q[4]) const { float mag = (q[0]q[0] + q[1]q[1] + q[2]q[2] + q[3]q[3]); for (int i = 0; i<4; i++) q[i] /= mag; }

How do you convert a rotation axis and angle to a quaternion?

void TrackBall::axis_to_quat(float a[3], float phi, float q[4]) { vnormal(a); vcopy(a,q); vscale(q,(float)sin(phi/2.0)); q[3] = (float) cos(phi/2.0); }

How do you convert a quaternion to a rotation axis and angle?

void TrackBall::quat_to_axis(float a[3], float &phi, const float q[4])const
{
	float c = q[3];
	phi = (float)(acos(c)*2.);
	float s = (float) sqrt(1.0 - c*c);
	if ( fabs(s)<0.0005 ) s = 1;
	vcopy(q,a);
	vscale(a,s);
}

How do you convert a quaternion to a rotation matrix?

void TrackBall::build_rotmatrix()
{
	float	*q = _currentQuat; // Alias
_m[0][0] = (float) (1.0 - 2.0 * (q[1] * q[1] + q[2] * q[2]));
_m[0][1] = (float) (      2.0 * (q[0] * q[1] - q[2] * q[3]));
_m[0][2] = (float) (      2.0 * (q[2] * q[0] + q[1] * q[3]));
_m[0][3] = 0.0f;


_m[1][0] = (float) (      2.0 * (q[0] * q[1] + q[2] * q[3]));
_m[1][1] = (float) (1.0 - 2.0 * (q[2] * q[2] + q[0] * q[0]));
_m[1][2] = (float) (      2.0 * (q[1] * q[2] - q[0] * q[3]));
_m[1][3] = 0.0f;

_m[2][0] = (float) (      2.0 * (q[2] * q[0] - q[1] * q[3]));
_m[2][1] = (float) (      2.0 * (q[1] * q[2] + q[0] * q[3]));
_m[2][2] = (float) (1.0 - 2.0 * (q[1] * q[1] + q[0] * q[0]));
_m[2][3] = 0.0f;

_m[3][0] = 0.0f;
_m[3][1] = 0.0f;
_m[3][2] = 0.0f;
_m[3][3] = 1.0f;

}

How do you convert a rotation matrix to a quaternion?

void TrackBall::Matrix2Quaternion(double *m, double *q)const
{
        double T = 1 + m[0] + m[5] + m[10];
        if(T > 0.00000001) // to avoid distortions.
        {
                double S = sqrt(T) * 2;
                q[0] = ( m[9] - m[6] ) / S;
                q[1] = ( m[2] - m[8] ) / S;
                q[2] = ( m[4] - m[1] ) / S;
                q[3] = 0.25 * S;
        } else // who is the major diagonal.
                if (m[0] > m[5] && m[0] > m[10] )       // max=0
        {
                double S  = sqrt( 1.0 + m[0] - m[5] - m[10] ) * 2;
                q[0] = 0.25 * S;
                q[1] = (m[4] + m[1] ) / S;
                q[2] = (m[2] + m[8] ) / S;
                q[3] = (m[9] - m[6] ) / S;
        } else if (m[5] > m[10])
        {
                double S = sqrt( 1.0 + m[5] - m[0] - m[10] ) * 2;
                q[0] = (m[4] + m[1] ) / S;
                q[1] = 0.25 * S;
                q[2] = (m[9] + m[6] ) / S;
                q[3] = (m[2] - m[8] ) / S;
        } else
        {
                double S  = sqrt( 1.0 + m[10] - m[0] - m[5] ) * 2;
                q[0] = (m[2] + m[8] ) / S;
                q[1] = (m[9] + m[6] ) / S;
                q[2] = 0.25 * S;
                q[3] = (m[4] - m[1] ) / S;
        }
}

( Trackball demo )

Parametric Curves: A parametric curve is a function Q(u) that maps a set of real values to a set of points.
1. Hermite Curves: (cubic)
2. Bezier Curves (cubic)
3. B-Splines
4. Rendering Curves
NURBS: Non-uniform, rational B-spline (NURBS) is a mathematical model commonly used in computer graphics for generating and representing smooth, freeform, curves and surfaces (Bezier curves and Bezier surfaces, credit for the French pioneer engineer Pierre Bezier).
Shader
1. Z-buffering: is the management of image depth coordinates in 3D graphics to decide which objects are visible, and which are hidden. Usually, the graphics card stores in the z-buffer as a 2D array (x-y) with one element for each screen pixel. It compares and chooses the one closer to the observer. The chosen depth is then saved to the z-buffer, replacing the old one.
2. Alpha blending: alpha=0.0 represents a fully transparent color, and 1.0 represents a fully opaque color. Draw Value1 over a background color Value0 is given by: Value = Value0(1.0 - Alpha) + Value1(Alpha).
3. Vertex shaders allow us to manipulate the data that describes a vertex, such as it position, normal, colour, texture coordinate and so on.
4. Pixel shaders

How to draw an analog clock?

An analog clock has three hands (coordinate -100 to 100 in x and y). Rotate painter by 360/12*(h+m/60.), 360/60*(m+s/60.) and 360/60*s, then draw.

	static const QPoint hourHand[3] = 
	{
		QPoint(7, 8),
		QPoint(-7, 8),
		QPoint(0, -40)
	};
	static const QPoint minuteHand[3] = 
	{
		QPoint(7, 8),
		QPoint(-7, 8),
		QPoint(0, -70)
	};
	static const QPoint secondHand[2] = 
	{
		QPoint(0, 0),
		QPoint(0, -85)
	};

The clock center is the widget center. Resize recalculate

int side = qMin(width(), height()); painter.translate(width() / 2, height() / 2); painter.scale(side / 200.0, side / 200.0);

To draw ticks, the smart way is DO NOT calculate where we should draw, instead, draw constantly at a fixed location with a painter rotated.

for (int i = 0; i < 12; ++i) { painter.drawLine(88, 0, 96, 0); painter.rotate(30.0); }

Styles:

With Frame	Frameless	setMask

To make frameless:

: QWidget(parent, Qt::FramelessWindowHint)

To set a mask:

void AnalogClock::resizeEvent(QResizeEvent * /* event */)
{
    int side = qMin(width(), height());
    QRegion maskedRegion(width()/2 - side/2,
		height()/2 - side/2,side,side,QRegion::Ellipse);
    setMask(maskedRegion);
}

Click here to see the whole implementation.

String representation of a number, for example, -3.6 => "negative three point six".

template <class T> stringRep(T a, char *s, int accuracy=2) { // Solved }

Here are some test cases:

#include "stdafx.h"
#include "string.h"
#include "math.h"
#include "iostream.h"
void main()
{
        char s[128];
        int number = 4312;
        stringRep(number, s, 0);
        printf("%d => %s\n", number, s);
        cout << number << " => " << s << endl;
    double a = -123456789.678;
    stringRep(a, s,4);
    printf("%16.4f =&gt; %s\n",a,s);

}

// Output
4312 => four thousand, three hundred twelve
4312 => four thousand, three hundred twelve
-123456789.6780 => negative one hundred twenty three million, four hundred fifty six thousand, seven hundred eighty nine point six seven eight zero

How do you merge two sorted arrays?
For example, "a" is an sorted array, length n; "b" is an array, length 2n, with the first half is sorted, and the second half is empty.

template <class T> SortedArrayMerg(T a, int n, T b) { // Solved }

// Test

void main() { int a[]={ 4, 5,16,27}; int b[]={10,20,30,40, 0,0,0,0}; SortedArrayMerg(a,4,b); // mixed // output: 4, 5, 10, 16, 20, 27, 30, 40 }

Bitwise patterns

// Binary AND (&) Operation; OR (|);       XOR (^)
//  0 AND 0 = 0        0 | 0 = 0             0 ^ 0 = 0
//  0 AND 1 = 0        0 | 1 = 1             0 ^ 1 = 1
//  1 AND 0 = 0        1 | 0 = 1             1 ^ 0 = 1
//  1 AND 1 = 1        1 | 1 = 1             1 ^ 1 = 0
// (both 1 give 1)    (1 if there is 1)    (1 if they are different)
//	Example:
int a=2,b=3,c;
//	a = 0000000000000010
//	b = 0000000000000011
c = a & b; // 2
c = a | b; // 3
c = a ^ b; // 1
//	Shift 2 bits left
c = a<<2; // 8=0000000000001000=2^3

Give a one-line C expression to test whether a number is a power of 2.
bool PowerOfTwo(unsigned a) { return !( a&(a-1) );}
exp= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 30 31

2^exp= 1 2 4 6 8 16 32 64 128 256 512 1024 2048 4096 16384 ... 1073741824 2147483648
multiply a number by 7 = (x << 3) - x (Multiply by 8 (left shift by 3 bits) and then subtract the number)

const to specify an object or a variable is not modifiable.

Constant values: reassign causes a compiling error.

const int n=0; // Tell the compiler to prevent from modification // n=1; // compiling error !

Constant pointer: You can change its contents, but you cannot change its address.

	char *const cPtr = new char[3]; 
//	cPtr = new char [4]; // Error ! You cannot modify a constant pointer
	*cPtr = 'a'; // the same as cPtr[0] = 'a';
	*(cPtr+1) = 'b'; // the same as cPtr[1] = 'b';
	*(cPtr+2) = '\0'; // end of a string
	int len = strlen(cPtr); // =2
	delete []cPtr;

Constant data: You can not change its content directly, but you can change its address.

char hug[]="hug"; const char *bug = hug; // point to const data // bug[0] = 'b'; // Error hug[0] = 'b'; // bug is "bug"; char s[]="beetle"; bug = s; // bug points to s, which is "beetle";

Constant object: When an object is decleared as constant:
const A *aptr = new A;
You can call constant member functions only to ensure that the object is never modified.
// aptr->set(2); // Error aptr->get(); // allow only if it is a const method.
Constant Member Functions: A constant member function cannot modify any data members or call any member functions that aren't constant.
class A { public: void set(int m){value=m;}; int get()const{return value;}; // a constant method ! private: int value; };

volatile: = allow to modify. For example, a constant member function cannot modify any data members except for volatile members.

class A { public: int get()const // a constant method { value = 0; // it is ok to modify a volatile member ! return value; }; private: volatile int value; };

Unicode | UTF-8 | GB 2312

Unicode, Universal Character Set(UCS), a single unified character set, are first of all just code tables that assign integer numbers to characters.

Unicode started to replace ASCII, ISO 8859 and EUC at all levels.

With the UTF-8 encoding, Unicode can be used in a convenient and backwards compatible way in environments that were designed entirely around ASCII, like Unix.

UTF-8 (8-bit Universal Character Set/Unicode Transformation Format) is a variable-length character encoding for Unicode.

GB 2312 is the registered internet name for a key official character set of the People's Republic of China, used for simplified Chinese characters.

Win32 APIs, GDI, GDI+

Windows API is Microsoft's core set of application programming interfaces (APIs) available in the Microsoft Windows operating systems.

Win32 APIs categories:

kernel32.dll and advapi32.dll for file systems, devices, processes and threads, access to the Windows registry, and error handling.
Graphics Device Interface (GDI) gdi32.dll for output devices, such as monitors, speakers, and printers.
user32.dll for User Interface (UI), such as buttons and scrollbars to receive mouse and keyboard input.
comdlg32.dll for Common Dialog Box Library, such as status bars, progress bars, toolbars and tabs.
shlwapi.dll for Windows Shell
Network Services such as NetBIOS (Network Basic Input/Output System) on TCP/IP, Winsock (Windows Sockets API), RPC (Remote procedure call)

GDI has a Device Context (DC) output to screen or printer. A DC, like most GDI objects, is opaque.

GDI+ is an improved 2D graphics environment, adding advanced features such as anti-aliased 2D graphics, floating point coordinates, gradient shading, more complex path management, intrinsic support for modern graphics-file formats like JPEG and PNG, and general support for composition of affine transformations in the 2D view pipeline.

GDI+ uses ARGB values to represent color.

Windows Vista has Desktop Window Manager (DWM). DWM requires graphics cards supporting DirectX 9.0 and Shader Model 2.0. DWM uses DirectX to perform the function of compositing and rendering in the GPU, freeing the CPU of the task of managing the rendering from the off-screen buffers to the display. However, it does not affect applications painting to the off-screen buffers.

What is Automation?

Automation is a technology that allows you to take advantage of an existing program's functionality and incorporate it into your own applications. This technology can greatly simplify and speed up your development.

Automation is based on COM
Automation makes it possible for one application to manipulate objects implemented in another application, or to "expose" objects so they can be manipulated
Automation can be performed by a program written using COM-aware language, for example, VC++, Microsoft® Visual Basic® (VB), and so on

More ...

Iterator

What are iterators? Iterators provide a uniform means to access items in a container. Qt's container classes provide two types of iterators: Java-style iterators and STL-style iterators.
What is the key difference between Java-style and STL-style iterators? Java-style iterators point between items, STL-style iterators point directly at items.
Which one do you like? Java-style iterators are more convenient to use than the STL-style iterators, at the price of being slightly less efficient.
Is there any difference between prefix ++i and postfix i++ operators? The ++ and -- operators are available both as prefix (++i, --i) and postfix (i++, i--) operators in case of STL-Style iterators. The prefix versions modify the iterators and return a reference to the modified iterator; the postfix versions take a copy of the iterator before they modify it, and return that copy. In expressions where the return value is ignored, using (++i, --i) are recommended, as these are slightly faster.

Example:

QList<QString&gt list; list << "A" << "B" << "C" << "D";

	Java-style	STL-Style
Declear	QListIterator<QString> i(list);	QList<QString>::iterator i;
Iterate	while (i.hasNext()) s << i.next();	for (i = list.begin(); i != list.end(); ++i) s << *i;
Backward	i.toBack(); while (i.hasPrevious()) s << i.previous();	i = list.end(); while (i != list.begin()) { --i; s << *i; }
Key different	point between items	point directly at items
Compare	more convenient slightly less efficient	less convenient more efficient

Function pointer

A function pointer is a type of pointer in C/C++ which points to the address of a function. Just like the normal function, a function pointer has type and zero or more arguments as signature.

It is a programming technique used to simplify code (replace switch-statement) or impliment a callback function.

Example 1: use function pointer to replace switch-statement.

// same signature functions:
double plus(double a, double b) { return a+b; }
double minus(double a, double b) { return a-b; }
double multiply(double a, double b) { return a*b; }
double divide(double a, double b) { return a/b; }

// switch implimentation
double f(double a, double b, char op)
{
  switch(op)
  {
  default:
  case '+': return plus(a, b);
  case '-': return minus(a, b);
  case '*': return multiply(a, b);
  case '/': return divide(a, b);
  }
}

// function pointer implimentation double func(double a, double b, double (*fpt)(double, double)) { return fpt(a, b); //save switch-statement! }

int main(int argc, char *argv[])
{
  // test:
  double a=1, b=2;
  double x1 = plus(a, b);
  double x2 = minus(a, b);
  double x3 = multiply(a, b);
  double x4 = divide(a, b);
double y1 = f(a, b, '+');
double y2 = f(a, b, '-');
double y3 = f(a, b, '*');
double y4 = f(a, b, '/');
double z1 = func(a, b, plus);
double z2 = func(a, b, minus);
double z3 = func(a, b, multiply);
double z4 = func(a, b, divide);
Q_ASSERT(x1 == y1 && y1 == z1);
Q_ASSERT(x2 == y2 && y2 == z2);
Q_ASSERT(x3 == y3 && y3 == z3);
Q_ASSERT(x4 == y4 && y4 == z4);
}

Example 2: callback. We can think a Reader in a library (low-level) in reading a Source file. The call to Reader::read() is made from an application (top level). Meanwhile, the application has a progress bar which is expected the Reader call back to update the reading status. This callback can be implemented by using a function pointer.

bool Reader::read(wchar_t &ch) { if (!src) return false; ++ m_readCount; if (m_readCount % m_interval == 0) { display(); if (!src) return false; } return src->get(ch); }

void Reader::display() { if (m_handler) (*m_funcptr)(src->position(), src->size(), m_handler); }

The above function pointer is defined as:

class Reader { public: typedef bool (funcptr)(int position, int totalSize, void progress); bool registerProgress(funcptr f, void h); private: Source src; void *m_handler; funcptr m_funcptr; };

A static function can be registrated:

Reader reader; reader.registerProgress(Progress::progressDisplay, &progress);

and the progress can be simply printing out the bytes:

class Progress
{
public:
  static bool progressDisplay(int pos, int total, void *);
private:
  bool display(int pos, int total);
};
bool Progress::progressDisplay(int pos, int total, void *p)
{
  return ((Progress *)p)->display(pos, total);
}
bool Progress::display(int pos, int total)
{
  printf("Read %d out of %d bytes\n",  pos, total);
  return true;
}

If you expect the callback will drive a progress bar in the same thread, you will finally get in trouble. Updating Windows is done main thread. Heavy duty job should be run in separate thread. More on this topic ...

Basic functions

isspace:
```
  std::vector<int> spaces;
  for (int i = 0; i < 128; ++ i) {
    if (isspace(i)) spaces.push_back(i);
  }
  // 9, 10, 11, 12, 13, 32
```
Standard white-space characters are:

' ' (0x20) space (SPC)

'\t' (0x09) horizontal tab (TAB)

'\n' (0x0a) newline (LF)

'\v' (0x0b) vertical tab (VT)

'\f' (0x0c) feed (FF)

'\r' (0x0d) carriage return (CR)

ispunct:

  fstring punctuations;
  for (int i = 0; i < 128; ++ i) {
    if (ispunct(i)) punctuations += char(i);
  }
  int n = punctuations.size(); // 32
  // !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

If you have nice questions, or elegant codes to share, doesn't matter which levels, email me please. Playing codes is my hobbit.

|

|| My Qt | Qt C++

CPP Coding Questions

C/C++: Basic to Advanced

Sample questions:

QString:

The Binary Trees Data Structure:

Check a tree is sorted or not?

Find the minimum value of a tree.

Find the maximum value of a tree.

How do you detect whether a tree is sorted?

Quicksort:

Bubble sort:

Multidimensional arrays

What is a constructor? What is a desconstructor?

What is the difference between a copy constructor and an overloaded assignment operator?

Why inheritance?

"Diamond problem" | virtual inheritance

Casting in C/C++

What do you mean by inline function?

(new and delete) vs (malloc and free)

Multithread Programs:

Singleton | thread safety | double-checked locking ..

Template: myPoint

vector basic

Normalize:

Addition:

Subtraction:

Multiplication:

How to draw an analog clock?

Unicode | UTF-8 | GB 2312

Win32 APIs, GDI, GDI+

What is Automation?

Iterator

Function pointer

Basic functions

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!