CTI Csc309 Lecture Notes 8, Object-Oriented Programming in C++

Week 8 Lecture Summary for CSC 309

These notes are not intended to be complete. They serve as an outline to the class and as a supplement to the text.

STL `Map` Class

A map stores key / value pairs.
The operations insertion, lookup, deletion are all based on the key.
The map class may look like a hash table but typically is implemented as a balanced binary search tree.
A map is referred to as a sorted associative container
The map stores its elements in sorted order, based on the keys.
The placement of the object in a map are determined by the key's operator< function.
Insertion, lookup and deletion take at most logarithmic time.
Can only change the value in a map not the key

Creating a Map

Must specify the type of the key and the value when constructor a map object.

Consider counting words in a file.

#include <map>
using namspace std;

map<string, int> wordCount;

Inserting Elements into a Map

Map class overloads operator[]
What actually gets created is a pair object.
Class pair is a C++ built in class.
The pair class has two public fields first and second

 wordCount["guitar"] = 1;
 wordCount["java"];

The first line creates a pair object with key (first field) "guitar" and value(second field) 1
The second line creates a pair object with key "java" and value 0. For object types the default constructor would be called.

Traversing a Map

for(map<string,int>::iterator it = wordCount.begin(); it != wordCount.end(); ++it){
       cout <<"(" << it -> first <<", " << it -> second << ")" << endl;
 }

Note: when dereferencing the iterator you get a reference to the pair object.

Search, Find and Lookup

Lookup, find and search are done based on the key.
Using operator[].
operator[] returns a reference to the value (second field of the pair object).

++wordCount["guitar];  // now value is 2
++wordCount["java"];   // now value is 1

if( wordCount["guitar"] > 2) {
    :
    :
}

If the key does not exist, operator[] will insert the key into the list.

Use method find to determine if a key is in the map.

Method find returns an iterator to the pair object if the key exists, else returns end()

map<string, int>::iterator isIt = wordCount.find("java");

if(isIt != wordCount.end()){
   cout << "its there, and the value is " << isIt -> second << endl;
}

Remove

wordCount.erase("java");

Another Way to Insert

wordCount.insert(make_pair("piano",5));

The insert method returns a pair object whose key is an iterator to the inserted object and whose value is a boolean indicating if the pair was actually inserted.

To check for insertion, we do

pair< map<string, int>::iterator, bool> returnPair;
returnPair = wordCount.insert(make_pair("bassoon",50));

if(returnPair.second){
   cout << "insert accomplished";
}

BookStore Program

Write a program that allows the user to interact with a collection of Books. Insert books, find books, remove books etc.. The books will be loaded and saved to the file books.txt

Two solve this program we will use the following two user define classes.

Notes:

The program will divided into 4 files.

books.txt - This file contains the data.
bookstore.cpp
booklist.h
booklist.cpp - Contains the implementations for the member functions and global functions from file booklist.h

To Run Programs Using Multiple User Defined Files in DEV-C++

Make sure you close all previous files and projects. File -> Close all, Close projects.

Create a new project. File -> New - > Project.
From the new project window dialog box select Empty Project Not Console Application
Next you want to add the files to the project. Project -> Add to Project.(To add a new file Project -> New File)
Compile, you can only Compile cpp files NOT .h files
When compiling the .cpp file that does not have a main you can ignore the @win32 link error.

To Run Programs Using Multiple User Defined Files under Linux

Create a directory called book.
Move all 4 files to the book directory.
Want to first compile booklist.cpp

g++ -c BookList.cpp

This will create a file booklist.o
Compile bookstore.cpp but must also link to file booklist.o

g++ -o book bookstore.cpp booklist.o

This will create an executable called book
To run book

./book

Macro Guards

Function Templates

C++ allows the programmer to write generic code.
Function templates allow the parameter types to be parameterized in addition to the values.
Consider the function to swap to integers

void swap(int &first, int &second){ int temp = first; first = second; second = temp; }

Suppose we wanted to swap two characters.

void swap(char &first, char &second){ char temp = first; first = second; second = temp; }

Notice the above two swap functions are similar. They differ in their parameter types.
With function templates we can define a type independent function.
The function template then becomes a proto-type for creating type-specific functions.

template <typename T>
void swap(T &first, T &second){
   T temp = first;
   first = second;
   second = temp;
}

When we use the template, the compiler will instantiate an instance of the function template substituting for the template parameter the types of the arguments.

int x(5), y(10);
char let1('a'), let2('z');
string s1("tuesday"), s2("sunday");

swap(x,y);         
swap(let1,let2);
swap(s1,s2):

For the three function calls, the compiler will instantiate three different swap functions. One that replaces T with int, the second replaces T with char, the third T with string.
In the template definition, T is just a parameter it can be called.
The template parameter T is a name chosen by the programmer.
The above template could be of been defined using a different parameter.
The following two definitions are equivalent to the original swap.

template <typename Type>
void swap(Type &first, Type &second){
   Type temp = first;
   first = second;
   second = temp;
}

OR

template <typename G>
void swap(G &first, G &second){
   G temp = first;
   first = second;
   second = temp;
}

typename is a keyword and needs to occur before the parameter.
Keyword class can be used instead of typename.

template <class T>
void swap(T &first, T &second){
   T temp = first;
   first = second;
   second = temp;
}

Object-Oriented Programming in C++