Recitation notes for Essential Data Structures in C/C++.

These notes are the notes used for the Teaching Assistant-conducted recitations for the Fall 2013 section of this course taught by Jae Woo Lee.

Much of the notes in this repository were compiled from the Spring 2013 repository found here: github.com/donyu/cs3136-recitations

The notes in the above repository were written by the Spring 2013 TAs Louis Croce (Head TA) (@ljc2154), Don Yu (@donyu), and Etan Zapinsky (@etanzapinsky)

For more information about the class, visit the course homepage.

Contents:

• Recitation 4: Selection Sort and Merge Sort
• Recitation 5: Pointers on Pointers on Pointers
• Recitation 6: Malloc
• Recitation 7: size_t. File IO, including reading, writing, and seeking in files.
• Recitation 8: C++
• Recitation 9: Trees

(a) Writing selection sort code and create a Makefile for the relevant code.

In a nutshell, your selection sort should do the following.

Given an array you will loop through each element. 
Find the minimum element seen past the element you are at in the loop.
Replace the element you are at in the loop with the minimum found.

Be sure to look back at Jae's code if you are stuck. For the Makefile, I highly encourage you to use the example one used by Jae (refer to recitation #2 for Makefile explanations).

(b) Write merge() function for mergesort().

/*
 * Merge-sort an array a, which contains n elements.
 */
void merge_sort(char a[], int n)
{
    // BASIS: if a has only 1 element, there is nothing to do.
    if (n <= 1) {
        return;
    }

    // INDUCTION: merge_sort the 1st half and merge_sort the 2nd half 
    // so that we have 2 half-size sorted arrays, and then merge them 
    // into a single sorted list.

    int m = n / 2;

    // merge_sort the 1st m elements of a
    merge_sort(a, m);

    // merge_sort the remaining n - m elements of the array "a + m",
    // which is a way to take a sub-array of "a" where a[m] is the new 
    // 0th element (i.e., (a+m)[0] is the same as a[m]).
    merge_sort(a + m, n - m);

    // allocated a temporary array into which the merge function will 
    // put the merged array.
    char temp[n];

    // merge a (for which we are looking at only the 1st m elements)
    // and a+m (which has n-m elements from (a+m)[0] to (a+m)[n-m-1],
    //          which are really the same as a[m] to a[n-1])
    // into the temp array.
    merge(a, m, a + m, n - m, temp);

    // copy the temp array back into a.
    int i;
    for (i = 0; i < n; i++) {
        a[i] = temp[i];
    }
}

A mergesort() function has 3 sections

a base case (an array of 1 or 0 elements is already sorted)
a split step (split unsorted array into two unsorted arrays)
call mergesort() on both unsorted sub arrays step
a merge() step (merges the now sorted sub arrays into one array)
(in our example, we have a 5th step, setting the values of array a to the values of the sorted array temp)

You will only be coding up the merge() step which is in fact not recursive. The basis for merge() is explained below in my own pseudocode. *Note merge() is such a common function that you can find pseudocode for it everywhere online. (but the below should be sufficient)

define function merge (array1, array2) {
    array1_index = 0
    array2_index = 0
    return_array = array of size (array1.size + array2.size)

    for i from (0, return_array.size) {
        if array1_index >= array1.size {
            return_array[i] = array2[array2_index++]
            continue on with loop
        }
        if array2_index >= array2.size {
            return_array[i] = array1[array2_index++]
            continue on with loop
        }
        return_array[i] = lesser of array1[array1_index] and array2[array2_index]
        increment index of lesser of array1[array1_index] and array2[array2_index]
    }

    return return_array
}

Merge() is actually exactly what you would reasonably do if you were given two sorted decks and asked to combine it into one sorted deck.

(c) Add a print stack trace to mergesort_main.c

The main trick to this part is understanding where to put each distinct print statement and how to keep track of indentation. It is a lot easier if you use Jae's already included print_array() function to print the array, and you may decide to use multiple printf statements to get a single line to print out.

Back to Contents

A pointer is a data type whose value is an address in memory. The value "points" to another value stored in that memory location.

Here is an example of a declaration of a pointer c which points to a char.

    char *c;

The * in the declaration lets us know that we are working with a pointer. The data type before the * indicates the data type or structure that the pointer points to.

We also use a * when accessing the data that the pointer points to.

    char b;
    b = *c;

Here, b would take on the value on what ever was pointed to by the char pointer c.

To access the address of a variable, we use an &.

    int x = 5;
    int *y;
    y = &5;

This tells y to point to the address of the int x.

Legendary Professor Alfred Aho once compared data types to people and pointers to where they live. Hopefully the analogy will make pointers easier to understand for you as well!

Imagine that I have a person named Joe who is represented by an int. Let's say his value is 13.

    int person = 13;

He lives somewhere (in this case in your computer) and you can ask him for his address in the computer (just like you could ask a person his home address) and store it somewhere. *Note we use & to ask a variable for its address.

    int *persons_address = &person;

It's been a while and I want to vist Joe again and see how he's doing. Good thing I have his address.

    printf("%d", *persons_address);

*Note that here we use * to travel to a pointers address and get the contents. It's kind of like traveling to Joe's house and asking for him.

And that's pointers in a nutshell.

Walk through the following program, keeping track of what pointers point to what, and what's happening at each step.

#include <stdio.h>

int main(int argc, char **argv)
{
    int i,j;
    int *x;
    int *y;
    char a,b;
    char *k;

    i = 7;
    j = 97;
    x = i;
    y = &j;
    a = 'a';
    *k = a;
    b = *k;
    a = 'c';
    a = (char)j;

    if (a == b)
    {
        printf("a and b are equal!\n");
    }

    printf("i equals %d\n", i);
    printf("j equals %d\n", j);
    printf("the value stored in y equals %d\n", *y);
    printf("a equals %c\n", a);
    printf("b equals %c\n", b);
    printf("the value stored in k equals %c\n", *k);
    printf("the value of x equals %d\n", x);
    printf("the value stored in x equals %d\n", *x);

    return 0;
}

A NULL pointer holds the memory address 0.

It cannot be dereferenced.

It can be initialized with NULL or 0 as done in the below example.

  char *c = NULL;
  int *p = 0;
  if (p)  // same as "if (p != 0)" or "if (p != NULL)"
    printf("p is not a NULL pointer.\n");
  if (!p) // same as "if (p == 0)" or "if (p == NULL)"
    printf("p is a NULL pointer.\n");

When you pass a parameter into a function by value, any changes made to the parameter inside the body of the function do not affect the parameter outside the scope of the function.

To address this, C++ has a "call-by-reference" where the changes made to a parameter hold after the function's execution.

C does not allow for call-by-reference, but it can simulate it by passing values by pointers. By passing by pointers, the address of the value is passed into the function and thus the actual value can be changed.

See how this is done in the following program which features pass-by-value and pass-by-pointer double functions.

#include <stdio.h>

/* A function that doubles an integer where a is the value of the actual integer */
void doubleItV(int a);
/* A function that doubles an integer where a is the pointer to an integer */
void doubleItP(int *a);

int main(int argc, char **argv)
{
  int a = 2;
  printf("The value of a is originally %d.\n", a); // a is 2
  
  doubleItV(a);
  printf("The value of a after passing by value to the double function is %d.\n", a); // should still be 2
  
  doubleItP(&a); //passing the address of a to the function
  printf("The value of a after passing by pointer (address) to the double function is %d.\n", a); // should be 4
  
  return 0;
}

/* A function that doubles an integer where a is the value of the actual integer */
void doubleItV(int a)
{
  a = 2 * a;
}

/* A function that doubles an integer where a is the pointer to an integer */
void doubleItP(int *a)
{
  *a = *a * 2;
}

sizeof() is a built-in function in c that returns the size of a given variable or type in bytes as a long unsigned integer.

The size of a char is 1 byte. The size of an int is 4 bytes. The size of a pointer is 8 bytes. The size of an array is equal to the array size times the size of the data inside of it. If you are taking the sizeof() of a dereferenced pointer, the size is the size of the type after dereferencing.

#include <stdio.h>

int main(int argc, char **argv)
{
  int x;
  char *c;
  int a[20];
  
  printf("%lu\n", sizeof(x));        // should be 4.  note the %lu for long unsigned int
  printf("%lu\n", sizeof(c));        // should be 8
  printf("%lu\n", sizeof(a));        // should be 80 (4 * 20)
  printf("%lu\n", sizeof(*c));       // should be 1
  printf("%lu\n", sizeof(a[1]));     // should be 4
  
  return 0;
}

An array is pretty much a glorified pointer. You can do very similar things with both of them.

In the following example, we move pointers around the array to access elements.

#include <stdio.h>

int main(int argc, char **argv)
{
  int a[] = {23, 5, 4, 20, 39, 88, 6, 25, 92, 1};
  int *p = a;

  printf("%d is the same as %d\n", *p, a[0]);
  printf("%d is the same as %d\n", *(p + 4), a[4]);
  printf("%d is the same as %d is the same as %d\n", *(p + 6), a[6], *(a + 6));
  printf("%d is the same as %d is the same as %d is the same as %d\n", *(p + 9), a[9], *(a + 9), *(9 + a));

  /* you can also increment a pointer with p++! */
  int i;
  for (i = 0; i < 10; i++)
    printf("element number %d: %d\n", i, *p++);
  /* but you can't do this with an array :( */

  /* observe that now p points to one past the last element of the array */
  printf("last element: %d\nwhat p points to (not defined by us): %d\n", *(p - 1), *p);

  return 0;
}

As you have heard by now, C does not come with a string data type like java, python, and c++.

Instead, strings are represented as an array of chars.

You can set a char pointer or char array to a string literal, or characters surrounded by ""'s like "boat". It is important to note that you cannot manipulate string literals like you can a normal array of characters.

C comes with a <string.h> library of functions for string literal manipulation. You can find more details here: http://www.cs.cf.ac.uk/Dave/C/node19.html

Because there is no string data type, there is no == operator for string literals. Below is the strncmp function. It is used to evaluate whether the first n characters of 2 strings are the same. It returns 0 if the first n characters of the strings are the same (or if the first string has less than n characters and they all match up). It returns -1 or 1 otherwise depending on the first character mismatch.

int strncmp(const char *s1, const char *s2, int n)
{
	int i;
	for (i = 0; n > 0; i++)
  		if (*(s1 + i) != *(s2 + i))				// dereference pointers
  		{
  			if (*(unsigned char *)(s1 + i) < *(unsigned char *)(s2 + i)) //the cast is to get rid of warnings
  				return -1;
  			else
  				return 1;
  		}
		else if (*s1 == '\0')
	    	return 0;
  	return 0;
}

Sometimes you want a bit more than a local variable, but less than a static variable.
Sometimes, you want a dynamic AND persistant array. Who you gonna call? -> Heap allocation. How you gonna call it? -> with malloc(). A variable allocated on the heap will stay there until free() is called. Wow! Example:

#include <stdio.h> // look!  a new library for malloc and free!
#include <stdlib.h>

int *allocateIntArray()
{
  int *p = (int *)malloc(3 * sizeof(int));
  return p;
}

void callNumber(int *p, int n)
{
  printf("Calling ");
  int i;
  for (i = 0; i < 3; i++)
  {
    printf("%d", *(p + i));
  }
  printf("\n");
}

void freeIntArray(int *p)
{
  free(p);
}

int main(int argc, char **argv)
{
  int *emergency = allocateIntArray();
  *(emergency) = 9;
  *(emergency + 1) = 1;
  *(emergency + 2) = 1;
  callNumber(emergency, 3);
  freeIntArray(emergency);
  return 0;
}

When you run valgrind on your programs, you will have memory errors if you allocated memory on the heap that wasn't freed. Don't forget to free()! Memory errors will lose you points on labs!

Back to Contents

Sometimes you want a bit more than a local variable, but less than a static variable.
Sometimes, you want a dynamic AND persistant array. Who you gonna call? -> Heap allocation. How you gonna call it? -> with malloc(). A variable allocated on the heap will stay there until free() is called. Wow! Example:

#include <stdio.h> // look!  a new library for malloc and free!
#include <stdlib.h>

int *allocateIntArray()
{
  int *p = (int *)malloc(3 * sizeof(int));
  return p;
}

void callNumber(int *p, int n)
{
  printf("Calling ");
  int i;
  for (i = 0; i < 3; i++)
  {
    printf("%d", *(p + i));
  }
  printf("\n");
}

void freeIntArray(int *p)
{
  free(p);
}

int main(int argc, char **argv)
{
  int *emergency = allocateIntArray();
  *(emergency) = 9;
  *(emergency + 1) = 1;
  *(emergency + 2) = 1;
  callNumber(emergency, 3);
  freeIntArray(emergency);
  return 0;
}

When you run valgrind on your programs, you will have memory errors if you allocated memory on the heap that wasn't freed. Don't forget to free()! Memory errors will lose you points on labs!

A struct is a collection of variables. Some may say "it's like a class in C". Actually, there were structs well before there were classes in C++ and Java. A class is an expansion of a struct. One of the key differences between a struct and a class is that the variables in a struct are inherently public while the variables in a class are inherently private. But you don't have to worry about classes for the time being, cause we're still in C.

A struct can be declared in a few ways:

// way 1
struct Dog {
	char *name;
};
struct Dog d1;

// way 2
struct {
	char *name;
} d1;

// way 3
typdef struct {
	char * name;
} Dog;
Dog d1;

Here, we create a struct for a contact that might appear in your phone.

#include <stdio.h>
#include <stdlib.h> // for malloc

struct Contact {
	char *first;
	char *last;
	int number;
};

/* Met a cute girl at Mel's, gotta add her */
struct Contact *createContact(char *_first, char *_last, int _number)
{
	struct Contact *new = (struct Contact *)malloc(sizeof(struct Contact));
	if (new == NULL)
	{
		printf("malloc failed");
		return NULL;
	}
	new -> first = _first;
	new -> last = _last;
	new -> number = _number;
	return new;
}

/* And now she's making out with my friend, forget her */
void deleteContact(struct Contact *c)
{
	free(c);
}

void printContact(struct Contact *c)
{
	printf("%s %s's number is %d\n", c -> first, c -> last, c -> number);
}

int main(int argc, char **argv)
{
	struct Contact *c1 = createContact("Don", "Yu", 1234567890);
	printContact(c1);
	deleteContact(c1);
	return 0;
}

You use arrows to access a struct's variables when you are obtaining the variables from a pointer to a struct. You use dots to access a struct's variables when you are obtaining the varaibles from the struct itself.

Sometimes, it may make sense for a function to take another function as a parameter. This is seen in a lot of sorting, where a sorting function, like quicksort or mergesort, takes in a comparison function. C has a built-in function called qsort in stdlib.h. It's declaration looks like this:

 void qsort(void *baseAddress, size_t numElem, size_t sizeElem,
  int (*compareFn)(const void *, const void *));

Let's update our contact example to use qsort and a compare function:

#include <stdio.h>
#include <stdlib.h> // for malloc and qsort()

struct Contact {
	char *first;
	char *last;
	int number;
};

/* Met a cute girl at Mel's, gotta add her */
struct Contact *createContact(char *_first, char *_last, int _number)
{
	struct Contact *new = (struct Contact *)malloc(sizeof(struct Contact));
	if (new == NULL)
	{
		printf("malloc failed");
		return NULL;
	}
	new -> first = _first;
	new -> last = _last;
	new -> number = _number;
	return new;
}

/* And now she's making out with my friend, forget her */
void deleteContact(struct Contact *c)
{
	free(c);
}

/* prints a contact info */
void printContact(struct Contact *c)
{
	printf("%s %s's number is %d\n", c -> first, c -> last, c -> number);
}

// void qsort(void *baseAddress, size_t numElem, size_t sizeElem,
//  int (*compareFn)(const void *, const void *));

int compareContacts(const void *c1, const void *c2)
{
	int val;
	if ((val = strncmp(((struct Contact *)c1) -> last, ((struct Contact *)c2) -> last, 20)) == 0)
		return strncmp(((struct Contact *)c1) -> first, ((struct Contact *)c2) -> first, 20);
	return val;
}

int main(int argc, char **argv)
{
	struct Contact myContacts[3];	//our array of contacts that will be sorted

	// allocate memory on heap
	struct Contact *c1 = createContact("Don", "Yu", 1234567890);
	struct Contact *c2 = createContact("Etan", "Zapinsky", 1867877234);
	struct Contact *c3 = createContact("Louis", "Croce", 1555555555);

	// assign contacts
	myContacts[0] = *c1;
	myContacts[1] = *c2;
	myContacts[2] = *c3;

	// call qsort
	qsort(myContacts, 3, sizeof(struct Contact), compareContacts);

	int i;
	for (i = 0; i < 3; i++)
	{
		printContact(&myContacts[i]);
	}

	// free space allocated on heap
	deleteContact(c1);
	deleteContact(c2);
	deleteContact(c3);
	return 0;
}

Back to Contents

Back to Contents

  1. Object Oriented (like JAVA!)
    a) We can create our own data types with classes!
    b) Variables and functions can be polymorphic and we can use inheritance when creating classes.
  2. Use templates for more generic programming!
  3. Built-in Goodies
    a) containers like list, vector, queue
    b) functions like qsort (which you already had, but there's more good stuff like that)
  4. A STRING CLASS!!!!

char buf[100]

char *buf = (char *)malloc(100)

typedef struct {
  char *s;
  int len;
} String;

/* Note: here allocString() would take in a string literal,
 * allocate memory on the heap for a String, set s to "hello",
 * and length to strlen("hello") */
String *buf = allocString("hello");

String s = "hello";

A declaration tells the compiler the name and type/return type of a variable/function/class which is defined somewhere else. Header files in C/C++ contain many declarations (.h files). In a program file, global variables/functions/classes can be declared above the program's main function.

i.e.

void swap(int *a, int *b);

The definition defines. Defining could happen in the assignment of a variable or in the associated body of a function, struct, or class. For our purposes, the definition could be somewhere else in the same file or in a .c file of the same name.

i.e.

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

Stack allocations go away after the scope of the function has passed. Heap allocations persist beyond the scope of the function.

struct Pt {
  int x;
  int y;
};
In C:
        // stack allocation
        struct Pt p1;
        // p1 goes away at the end of its scope
        // heap allocation
        struct Pt *p2 = malloc(sizeof(struct Pt));
        ...
        free(p2);
In C++:
        // stack allocation
        struct Pt p3(0,0);
        // p3 gets destructed at the end of its scope
        // heap allocation
        struct Pt *p4 = new Pt(0,0);
        ...
        delete p4;

Available in both c and c++

  f(struct Pt p)

Available in both c and c++

  f(struct Pt *p)

Available only in c++

  f(struct Pt &p)

Four functions that make up the core of any class. If you do not write them, the compiler will generate them and they may not do what you want! I will write them as they appear in our MyString class. Our MyString class has two private variables: char *data and int len.

Initialize all variables of class. No return type. Can take any number of arguments to initialize the variables.

// In mystring.h:
  // default constructor.  Has no arguments.
  MyString();
  // constructor 1.  Takes in a char * to be assigned to data
  MyString(const char* p);
        
// In mystring.cpp
  // default constructor.  Allocate memory for empty string (just '\0' char).
  MyString::MyString()
  {
      data = new char[1];
      data[0] = '\0';
      len = 0;
  }
  // constructor 1
  MyString::MyString(const char* p)
  {
     if (p) {
          len = strlen(p);
         data = new char[len+1];
         strcpy(data, p);
     } else {
         data = new char[1];
         data[0] = '\0';
         len = 0;
     }
  }

Deallocates all memory allocated in the construction of the object. Should be a mirror image of sorts of the constructor. Note that the destructor gets called whenever a MyString object is deleted or removed from the Memory Stack.

// In mystring.h:
  ~MyString();
  
// In mystring.cpp:
  MyString::~MyString()
  {
    delete[] data; deallocate memory allocated in the constructor.
  }

The copy constructor is called automatically in certain situations. It is called when an object is returned by value. It is also called when an object is passed into a function by value.

// In mystring.h:
  MyString(const MyString& s);

// In mystring.cpp:
  MyString::MyString(const MyString& s)
  {
    len = s.len;
    data = new char[len+1];
    strcpy(data, s.data);
  }

Called in assignment operations.

// In mystring.h:
  MyString& operator=(const MyString& s);

// In mystring.cpp:
  MyString& MyString::operator=(const MyString& rhs)
  {
    if (this == &rhs) {
        return *this;
    }
    // first, deallocate memory that 'this' used to hold
    delete[] data;
    // now copy from rhs
    len = rhs.len;
    data = new char[len+1];
    strcpy(data, rhs.data);
    return *this;
  }

Back to Contents

A tree is a data structure with a set of linked nodes in a hierarchical tree-like structure.

The root of the tree is the top most node on the tree (Think of it like an upside down real tree). Two nodes can be related to each other as "parent" and "child" nodes. The parent node "points" to the child node. In a graphical represenatation of a tree, the parent is on top of the child. The leaves of the tree are the nodes that don't have any children. (If the tree consists of one node, that node is both a root and a leaf!) A "subtree" is a tree whose root is one of the children of a the node the subtree is being compared to.

The branching factor is the number of children at each non-leaf node. Think of it as the average fertility of a node (how many children it makes). This number is not always uniform and so the average branching factor is calculated.

We worked a lot with linked lists in HW2. Is a linked list a type of tree? Yes! A linked list is a tree with a branching factor of 1!

A binary tree is a tree in which every node has at most two children.

Directed edge: link from parent to child.
Depth(of a node): The length of the path from the root to a given node.
Level: The set of all nodes at a given depth.
Depth(of a tree): The depth of the deepest node.  Also called height.
Siblings: Nodes that share the same parent.
Size(of a node): Number of descendants it has including itself.

Let's see what different types of binary trees look like in the wild.

Full Binary Tree: Every node other than the leaves has 2 children.
Complete Binary Tree: Every level is completely filled except for possibly the last.
Perfect Binary Tree: Complete and Full.  (All leaves are at the same level).
Balanced Binary Tree: The depth of the left and right subtrees of every node differ by one or less.
Degenerate Tree: Is a tree where for each parent node, there is only one associated child node. (Performs like a linked list).

When we don't know the properties of a binary tree, performance can be poor in the worst case.

Note that in the following, n is the number of nodes in the tree.
space: O(n)
search(Node n): O(n) 
delete(Node n): O(n)
insert(Node n): O(n)
print_tree: O(n)
delete_Root: O(1)

A binary search tree (BST) is a binary tree where the left subtree contains all values less than the node, the right subtree contains values greater than the node for all nodes and there are no duplicate nodes.

We still don't know if the tree full/complete/perfect, so in the worst case, performance is still poor. Why? Because a binary tree could just be a linked list which we means we can't take advantage of the binary search capabilities.

space: O(n)
search(Node n): O(n) 
delete(Node n): O(n)
insert(Node n): O(n)
print_tree: O(n)
delete_Root: O(1)

However, if our tree is rougly balanced (and not just a linked list) then we get very good runtimes O(logn). This is what happens on average.

space: O(n)
search(Node n): O(logn) 
delete(Node n): O(logn)
insert(Node n): O(logn)
print_tree: O(n)
delete_Root: O(1)

Two general types of traversals: Depth First and Breadth first. In breadth first, we explore nodes by level. We care more about depth first, where we explore nodes by depth.

Here's what the different depth order traversal methods look like.

Pre-order: visit root, traverse left subtree, then traverse right subtree.
In-order: traverse left subtree, visit root, then traverse right subtree.
Post-order: traverse left subtree, then traverse right subtree, and then finally visit the root.

Confused? Maybe some animation will help. Go to https://www.khanacademy.org/cs/depth-first-traversals-of-binary-trees/934024358 for and watch the respective animations for pre-order, in-order, and post-order traversal.

Back to Contents

Function templates are special functions that can operate with generic types.

This allows us to create a function template whose functionality can be adapted to more than one type or class without repeating the entire code for each type.

Remember how we wrote mergesort for a char array in lab 1? What if we could write it for ANY kind of array?

template <typename T>
void merge_sort(T a[], int n)
{
  /* 
   * BASIS: if a has only 1 element, there is nothing to do.
   */
  if (n <= 1)
    return;
  
  
  /*
   * INDUCTION: merge_sort the 1st half and merge_sort the 2nd half
   * so that we have 2 half-size sorted arrays, and then merge them
   * into a single sorted array
   */
  int m = n / 2;
  
  /*
   * merge_sort the 1st m elements of a
   */
  merge_sort(a, m);
  
  /*
   * merge_sort the remaining n - m elements of the array "a + m",
   * which is a way to take a sub-array of "a" where a[m] is the new 
   * 0th element (i.e., (a+m)[0] is the same as a[m]).
   */
  merge_sort(a + m, n - m);

  /*
   * allocated a temporary array into which the merge function will
   * put the merged array.
   */
  T temp[n];

  /*
   * merge a (for which we are looking at only the 1st m elements)
   * and a+m (which has n-m elements from (a+m)[0] to (a+m)[n-m-1],
   *          which are really the same as a[m] to a[n-1])
   * into the temp array.
   */
  merge(a, m, a + m, n - m, temp);
  
  /*
   * copy the temp array back into a
   */
  for (int i = 0; i < n; i++)
    a[i] = temp[i];
}

template <typename T>
void merge(T a1[], int n1, T a2[], int n2, T output[])
{
  int i1 = 0;
  int i2 = 0;
  int j = 0;
  
  /*
   * go through the elements of a1 and a2,
   * copying the smaller one into the output array
   * until we reach the end of either a1 or a2.
   */
  while (i1 < n1 && i2 < n2) {
    /*
     * note that we take a1 if the two elements are the same.
     */
    if (a1[i1] <= a2[i2]) {
      output[j++] = a1[i1++];
    } else {
      output[j++] = a2[i2++];
    }
  }
  
  /*
   * copy over the remaining elements of a1, if any.
   */
  while (i1 < n1)
    output[j++] = a1[i1++];
  
  /*
   * copy over the remaining elements of a2, if any.
   */
  while (i2 < n2) 
    output[j++] = a2[i2++];
}

• Always need "template " before function declaration/definition.
• The function will only work with classes and types for which all functions/operators used in the function are defined.

• Templates enable generic programming for all types while void * enables a typless programming.
• With templates, the programming is type-safe, so the compiler will catch type mismatches (things to remember #2).
• With void *, the programming is not type-safe, so seg-faults catch type mismatches :(.
• Templates enable value semantics, but with void * you are forced to use pointer semantics.

The C++ Standard Template Library comes with built-in classes that contain data defined by templates.

These classes are based on different data structures and are called containers.

There are 3 different types of containers: sequence containers, container adapters, and associative containers.

We will focus on the 3 sequence containers: vector, deque, and list.

Good thing about these container fellas: they "contain" objects of type T "by value". Don't have to do too much garbage collecting. Elements of container are destroyed when container is destroyed. (so you can just delete the container and don't have to iterate through to delete all the elements).

• an array
• Provides efficient random access (operator[]) and adding/removing elements from the end of the vector (push_back()/pop_back()).
• Supports item additions & removals at positions other than the end of the vector (insert()/remove()), but they are inefficient because other items need to be moved.

Here an example of using a vector

#include <vector>
#include <string>
#include <iostream>
using namespace std;

int main(int argc, char **argv) {

  vector<string> str_vector;
  str_vector.push_back("hello");
  str_vector.insert(str_vector.begin(), "world");

  // print out contents now
  for (unsigned i = 0; i < str_vector.size(); i++) {
    cout << str_vector[i] << endl;
  }

  return 0;
}

• short for double-ended queue, pronounced "deck"
• similar to vector, but unlike vector, deque supports efficient addition & removal of elements from the beginning of the deque (push_front()/pop_front()).
• slower and/or wastes more memory than vector

• doubly linked list
• efficient insertion & removal of elements anywhere in the list
• no random access

The sequential containers have iterators to keep track of elements.

• "iterator" and "const_iterator" is a "type member" (i.e., a typedef defined inside a class)

• An iterator behaves like a pointer: ++it, it. Sometimes it’s actully a pointer (vector::iterator is just a typedef of T), but more often it’s not. (Think about what a list::iterator would have to do when you increment it.)

• Dereferencing an iterator gives you a T&, and dereferencing a const_iterator gives you a const T&.

• v.begin() returns an iterator that points to the first element in the vector.

• v.end() returns an iterator that points to ONE PAST THE LAST ELEMENT, not the last element. It is used as a marker for the end of the container, and it cannot be dereferenced.

• Note that we use "!=" rather than "<" in the for loop. This is recommended (especially if you’re writing template code) because not all iterators define operator<(). (list iterator does not, for example.)

• Note that we use ++it rather than it++. This is recommended because when the iterator is a class object rather than a native pointer, it’s usually less costly to call ++it than it++.

  Below is some sample code on using an iterator to print the contents of a vector v.

  typename vector<string>::const_iterator it;
  for (it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
  }