Inheritance in C++

// base.h
class base {
public:
  void f1();              // f1 cannot be overwritten
  virtual void f2();      // f2 can be overwritten
  virtual void f3() = 0;  // f3 is a pure virtual function and 
                        // must be overwritten
};
// derived.h
class derived : public base {
public:
  void f1();
  virtual void f2();
  virtual void f3();
};

Notes about derived class:

  • Relationship = “derived is a kind of base”
  • A derived class is first of all a base class.
  • A derived class can access only the protected and the public members of the base class.
  • If a class contains a pure virtual function, such a class cannot be instantiated and is called an abstract class. (e.g. base cannot be instantiated)
base* b = new derived(…);

Static type of (*b) is base.

Dynamic type of (*b) is derived.

b->f1() invokes base::f1()

b->f2() invokes derived::f2()

b->f3() invokes derived::f3()

Constructor Destructor Copy constructor Assignment operator
base::base()
{
// Initialize base members
}
virtual base::~base()
{ 
// Cleanup base members
}
base::base(const base& 
           other)
{
 ...
}
base& base::operator=
(const base& other)
{
 if (this != &other) 
 {
   ...
 }
 return *this;
}
derived::derived() 
: base()//executes first
{
// Initialize derived members
}
virtual derived::~derived()
{
// Clean-up derived
// Clean-up base
}
derived::derived
(const derived& other)
: base(other)
{
 ...
}
derived& derived::operator=
(const derived& other)
{
 if (this != &other) 
 {              
  base::operator=(other);
  ...
 }
 return *this;
}

 

Slicing => Information loss

void func(base b) { … }
derived d;
func(d);  // Invokes the copy constructor for base

Lossless ways of passing the derived class

Passing by pointer

void func(base* b) { … }
derived* d;
func(d);

Passing by reference

void func(base& b) { … }
derived d;
func(d);
Posted in C++ | Leave a comment

Review Questions – C++

1. What do you understand by a declaration, a definition, and an instantiation?

2. What are the four basic member functions of a C++ class that are defined by the compiler by default?

3. What does the default constructor do (when you don’t write one)? When would you need to redefine a constructor for a class?

4. What are the scenarios when a copy constructor is invoked?

5. How do you decide whether to pass an argument by a pointer or a reference?

6. When you are implementing an operator overloading, how do you decide whether you want it to be a member function or a non-member function?

7. Could you point out a flaw in the following class declaration?

class A {
public:
    void erase() { delete this; }
private:
    int data;
};

8. Discuss the different usages of const keyword in C++.

9. Why do you need the following wrapper around a class declaration in the header file?

#ifndef BLAHBLAH_H
#define BLAHBLAH_H
class ...
#endif

10. When do you need to implement a destructor?

Posted in C++, Review | Leave a comment

The world of C++

[PDF Copy]

Defining and using a class

Header:

// A.h

#ifndef A_HEADER

#define A_HEADER

class A {

public:

// Exposed member functions or Methods

void foo1(); // Declaration

// Inlined function: foo2

void foo2() {

}

private:

// Private member functions

void foo3();

// Data member(s)

int data;

};

#endif

Source:

#include “A.h”

void A::foo2() { … }

void A::foo3() { … }

Usage:

Static allocation of object:

{

A a;  // Default constructor invoked

a.foo2();

a.foo3(); // Error: Private member function

} // Destructor for a invoked

Dynamic allocation of object:

A* a = new A(); // Default constructor invoked

// Use a

a->foo1();

a->foo2();

delete a; // Destructor invoked

A* a = new A[n]; // Calls the default constructor n times

delete [] a;

4 default methods of a class

class A{

public:

// No member functions defined

private:

int mInt;           // Data member of type int

int* mPointerToInt; // Data member of type pointer to int

B mb;                // Data member of type class B

};

This is equivalent to the following:

class A {

public:

// Default constructor (can be overwritten or overloaded)

A() : mb() {

// mb is initialized through its constructor

// No initialization for data member of type int

// No initialization for data member of type int*

}

// Default destructor (can be overwritten)

~A() {

mb.~B();

}

// Default copy constructor

A(const A& other) : mb(other.mb) {

mInt = other.mInt;

mPointerToInt = other.mPointerToInt;

}

// Default assignment operator

A& operator=(const A& other) {

mInt = other.mInt;

mPointerToInt = other.mPointerToInt;

mb(other.mb);

return *this;

}

};

Need for overwriting the 4 default methods

Data member type Need to overwrite constructor Need to overwrite destructor Need to overwrite copy constructor Need to overwrite assignment operator
Non-pointer built-in (int, float, double, char, bool) Yes (for initialization) No No No
Pointer Yes (for allocation) Yes (for deallocation) Yes (for deep copy) Yes (for deep copy)
Class No No No No

 

Const-correctness

Naming values

const float g = 9.8;

g = … // Error: Illegal to modify

const -> property of the path, not of the variable

Example:

A a;

a = …; // Fine

foo(a);

void foo(const A& b) {

b = … // Error

}

Const Member function -> Member variables cannot be modified by this function

Class A {

Public:

void foo() const; // equivalent to void foo(A* const this);

};

Since const applies to the “this” pointer (which is a pointer to the self-object), member variables cannot be modified.

Choosing function interface

Speed?(copy constructor is not invoked) Is it safe?(Callee cannot modify the caller’s actual parameter) Can it be NULL?(to indicate the absence of a value)
Void A(      B  b) Slow Yes No
Void A(      B* b) Fast No Yes
Void A(const B* b) Fast Yes Yes
Void A(      B& b) Fast No No
Void A(const B& b) Fast Yes No

 

Namespaces

// A.h

class foo { … };

// B.h

class foo { … };

// use.cpp

#include “A.h”

#include “B.h” // Clash of class definitions!

Solution:

// A.h

namespace A { // Global scoping

class foo { … };

}

// B.h

namespace B { // Global scoping

class foo { … };

}

// use.cpp

#include “A” // No suffix “.h” when the header contains a namespace

#include “B” // No clash!

A::foo objectFoo1;

B::foo objectFoo2;

Operator overloading

(x + y) is equivalent to

x.operator+(y) // Member function

OR

operator+(x,y) // Non-member function

Chaining of operators is also possible:

x + y + z is equivalent to ((x + y) + z)

OR (x.operator+(y)).operator+(z)

Signature:

A operator+(const A& other);

x = y = z is equivalent to x = (y = z)

OR x.operator=(y.operator=(z))

Signature:

A& operator=(const A& other);

std::cin >> x >> y is equivalent to

operator>>(operator>>(std::cin, x), y)

Signature (must be a non-member function):

std::istream& operator>>(std::istream& s, A& a)

std::cout << x << y is equivalent to

operator<<(operator<<(std::cout, x), y)

Signature (must be a non-member function):

std::ostream& operator<<(std::ostream& s, const A& a)

Prefix/postfix operators:

++x is equivalent to x.operator++()

x++ is equivalent to x.operator++(0) // 0 is irrelevant but used for function overloading


++(++x) is equivalent to x.operator++().operator++().

(x++)++ is NOT legal.

A& operator++() // Prefix

{

// Increment logic

return *this;

}

A operator++(int) // Postfix

{

A result(*this); // Copy constructor called

++(*this);  // Prefix operator function invoked

return result;

}

Subscripting:

A a;

MemberType m;

a[i] = m; // equivalent to a.operator[](i) = m

const A a;

a[i] = m; // illegal

Signatures:

const MemberType& operator[](int index) const; // Receiver is a const

MemberType& operator[](int index); // Receiver is a not const

 

Posted in C++ | Leave a comment

Pointers and Arrays

Pointers to values

// value (of type int) stored in a memory location

int value;    

// avalue: pointer to a value of type int

// avalue: address of a memory location containing a value of type int

int* avalue;    

// Extracting the address of value

avalue = &value;

Pointer to value

// Extracting value from address/pointer

int val = *avalue;

1-dimensional arrays

// One dimensional array A of size 6

int A[6];

pic2_1darrays

A: Value of &A[0] OR pointer to the value at 0-th index

A[i]: Value stored in the i-th index, where 0 <= i < 6

(A+i): Value of &A[i] OR pointer to the data at i-th index

*(A+i): Same as A[i]

Multi-dimensional arrays

Once the pointer arithmetic is clear in the context of one-dimensional arrays, we can now easily extend the logic to the pointer arithmetic in multi-dimensional arrays.

// A is a 3-dimensional array with the dimensions 4, 3 and 2, and having values of type int

int A[4][3][2];

pic3_3darrays

A: Value of &A[0]

A[i]: Value of &A[i][0], where 0 <= i < 4

A[i][j]: Value of &A[i][j][0], where 0 <= i < 4, 0 <= j < 3

A+i: Same as &A[i]

*(A+i): Same as A[i] OR value of &A[i][0]

*(A+i)+j: Value of &A[i][j]

*(*(A+i)+j): Same as A[i][j] OR value of &A[i][j][0]

*(*(A+i)+j)+k: Value of &A[i][j][k], where 0 <= i < 4, 0 <= j < 3, 0 <= k < 2

*(*(*(A+i)+j)+k): Same as A[i][j][k]

Generalization

int A[i_1][i_2]…[i_n];

Value of A[i_1][i_2]…[i_k] = &A[i_1][i_2]…[i_k][0]

Difference between A[k] and *pA

int A[50];

  • Array A allocated for 50 elements, each of which is of type int
  • Assignment A = 25 is not allowed

int *pA;    

  • a pointer to an int
  • pA can be changed at any time

 

 

Posted in C++ | Leave a comment

Some Helpful Materials – Mike Shah

Links for reseting your password, and ssh’ing from home:
http://www.eecs.tufts.edu/~mshah08/faq.html

Reseting Your Passwords
For Unix Password resets, send an e-mail to staff@eecs.tufts.edu explaining that your Unix account/password is inactive or not working.
For resetting Windows passwords visit tuftstools.tufts.edu or walk into Eaton Hall to have your password reset.

Parking at Tufts
-You may park on the street of Boston Avenue for free if you have a Medford sticker.
-You may also park in the Dowling Parking Garage for $5.

Computer Labs
- You are encouraged to work at the Anderson Hall computer laboratory.
-There is another computer lab at Eaton Hall that has Windows computers you can work from (I believe they have tools you can ssh into)

-You can work at Halligan Hall although because of the construction this is discouraged.  My office is located here(In the extension office#002c), feel free to stop by.

- Mike Shah

 

Posted in Information | Leave a comment

Lecture 1 – Introduction to Data Structures (notes from Mike)

Data Structures:

    Goal: Given a problem, how do we solve it efficiently?

What we want to do as computer scientists is automate the process of solving specific problems.

Problem Solving Steps

    1.) Generate an initial naive solution.  Do this to validate your correctness.

    2.) Refine your initial solution(if possible).

        1.) Efficiency (Time and Space)

        2.) Algorithm Design (Number of Steps)

        3.) Data Structure Design (Organization of Data)

Exercises

Exercise 1: How would you find the maximum number from a given list of integers that are arranged in a random order(Example: {5,3,2,5,7,12,0} )

Exercise 2: Find the max and min of n integers.

    Hints:

    Questions to ask yourself: How many comparisons do you have to make to find just the max or just the min?

    Can we think of the max and min as “defeating” the other numbers in a tournament?

    Can you avoid checking if certain numbers are a min or max more than once? (How can we minimize the set of winners or losers in our set when checking if they “win” or “lose” as a min or max.

Exercise 3: Find the max and second max of n integers.

Posted in Class notes | Tagged | Leave a comment

Overview

Instructor: Partha Biswas (partha DOT biswas AT tufts.edu)

Teaching assistant: Michael Shah (Michael DOT Shah AT tufts.edu)

Description and Objective: This course is intended as an introduction to data structures, algorithms, and more advanced programming techniques. Students will be able to solve real-world problems by reasoning about data structure choices, choose appropriate implementations, and analyze the costs associated with those choices. Students will learn to write, debug, and test large programs systematically. We hope to achieve these goal by presenting higher level concepts in lecture and hands-on computer practices in the lab. The programming assignments will be in C++.

Topics Covered: The major topics within the course include: Abstraction, Problems Solving, Software Design, Sequences, Sets, Finite Maps, Linked Lists, Templates, Stacks, Queues, Trees, Heaps, Sorting Algorithms, Graphs, and Hashing, with exposure to complexity and algorithm analysis.

Prerequisites: COMP 11 or equivalent. Knowledge of C++. Students who have had only Java or Python programming experience should contact the professor.

Examples: All code samples shown in the class are posted here.

 

Posted in Information | Leave a comment

Quick Emacs Reference

M = Alt or Esc key

C = Control key

  1. The usage of - in the command description implies combination. E.g. M C-s means pressing Esc once followed by pressing Control and s together.
  2. For Meta-key-based (M) commands, the Alt key is generally combined with another following key stroke, while the Esc key is pressed once before the following key stroke. E.g. M-a could be achieved by pressing Alt and a together or Esc followed by a.
  3. The editing operations within Emacs happen in temporary buffers. Selecting a save operation transfers the buffer content to the file under consideration.
  4. One of the most powerful operations within Emacs is the ability to break a given window into multiple windows.
  5. Any mistake in typing down a command can be rectified by the quit operation (using C-g).
  6. If you don’t remember any command, the auto-completion mini-buffer in M-x mode is sometimes helpful. E.g. typing M-x comment and hitting TAB would give good hints about the possible command completion that you may like to do. I found out about M-x comment-region during latex editing by using this approach.

Basic Commands:

C-x C-f Create/open a file in buffer
C-x C-v Reload an existing open file
C-x C-s Save the file (from the buffer)
C-x C-w Save as
C-x k Kill buffer
C-x 0 Delete window
C-x 1 Delete all other windows (except the current one)
C-x 2 Split window row-wise
C-x 3 Split window column-wise
C-x o Shift focus to other (next) window
C-g Quit a command
C-x C-c Exit emacs

Navigation Commands:

M-x goto-line Go to a specified line number
C-a Go to the beginning of line
C-e Go to the end of line
M-< Go to the start of file
M-> Go to the end of file
C-v Page down
M-v Page up
C-M-n Go to the next parenthesis group
C-M-p Go to the previous parenthesis group
C-a Go to the beginning of line
C-e Go to the end of line

Editing Commands:

C-k Delete a line from the cursor position
C-/ Undo
SPACE C-/ Redo
C-SPACE Mark beginning of a region (for marking more than one line)
C-x h Select all
C-w Delete the marked region (or marked line)
M-w Copy the marked region (or marked line)
C-y Paste the copied region (through M-w) or deleted region (through C-w)
M-\ Delete all white-spaces around a point
M-SPACE Leave just one white-space around a point
M-% Query replace (Use ! for all following occurrences and ^ to go back to previous match)

Search Commands:

C-s I-search (incrementally search) string forward. To quit searching, press C-g.
C-r I-search (incrementally search) string backward. To quit searching, press C-g.
M-c In I-search mode (after invoking C-s or C-r), toggle case-sensitivity
C-w In I-search mode, add more characters to the search keyword on the fly
C-M-s Search (incrementally) regexp forward. To quit searching, press C-g.
C-M-r Search (incrementally) regexp backward. To quit searching, press C-g.
M-% Search and replace (Use y or n to control replacement for the current match; Use ! to replace all following occurrences; Use ^ to go back to previous match;)

Programming Commands:

M C-a Go to the beginning of a function
M C-e Go to the end of a function
M-C-f Match parenthesis forward
M-C-b Match parenthesis backward
C-c C-c Comment out marked area (marking done using C-SPACE)
C-u C-c C-c Uncomment marked area (marking done using C-SPACE)
TAB Indent the current line or marked region (marking done using C-SPACE)
M-x compile Prompts for compilation command. Type the following: g++ -g -o <file> <file>.cpp, where <file> is the generated debuggable executable, and <file>.cpp is the program being compiled.
M-x gdb Prompts for gdb command. Type the following: gdb <file>, where <file> is the executable generated by a debug build.

Shell Commands:

M-x shell Start a shell
M-! Run a shell command
Posted in Emacs | Tagged | Comments Off