Topic 2

C++ Review Part II:

More on Functions, Variables, Classes
資料結構與程式設計
Data Structure and Programming
09.26.2018

Part I: Understanding “Functions”

u Global vs. member functions

u Function signature, prototype , definition

u Function parameters, arguments

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 2

1
 Key Concept #1:
Global vs. Member Functions

u Global functions are defined in global

scope
l void f(…) { … }
l There is no so-called local functions

u Member functions are defined in class

scope
l void A::f(…) { … }
l A member function is called by an object of
its class type

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 3

Key Concept #2: Function Signature

u 4 things to define “function signature”
1. Function name
2. Number of parameters
3. Types of parameters
4. Order of parameters
function names is neither in function
è No “return type” (why?) signature.
u There cannot be functions with the same
function signature, unless ---
1. Separated by different name spaces
2. Defined as “static” in different file scopes
u However, functions can have the same name,
but different signature (overloading)

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 4

"it's a good practice adding 'static' in front of functions that you're sure only you would use it"

2
Key Concept #3: Function Prototype
vs. Function Definition
u Think, which one is better?
1. void f() {
…
}
int main() {
…
f();
}
2. void f(); ç function prototype
int main() {
…
f();
}
void f() {
… ç function definition
}
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 5

Key Concept #4: Default Argument

u Note:
l void f(int x) { … } // x is f’s parameter
l f(10); f(a); // 10, a as arguments to f()
u Parameters with default assignments è function
with default arguments
l Can be skipped when calling the function
l e.g.
void f(int x, int y = 0);
…
f(10);
l Can only appear towards the end of parameter list
l (Not OK) void f(int x = 0, int y);
u Given a function, its default argument can only be
defined ONCE
l void f(int x = 0);
…
void f(int x = 0) { ... } è Compilation ERROR
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 6

3
Key Concept #5:
Parameters in a function
u When a function is called, the caller
performs “=“ operations on its arguments to
the corresponding parameters in the
function
l void f(int a, char c, int *p) { ... }
...
int main() {
f(i, cc, pp); // int a = i;
// char c = cc;
// int *p = pp;
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 8

Key Concept #6:

Passed by Object, Pointer, and Reference
u // passed by object
void f(int a) { …}
int main() { int b; ...; f(b); }
u // passed by object
void h(A a) { …}
int main() { A aa; ...; f(aa); }
u // passed by pointer
void g(int *p) { ... }
int main() { int *q = …; f(q); }
u // passed by reference
void k(A& a) { …}
int main() { A aa; ...; k(aa); }
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 9

4
 Passed by Object, Pointer, and Reference
[Rule of thumb] Making an ‘=’ (i.e. copy) from the passed
argument in the caller, to the parameter of the called function.
void f1(int a) main()
{ a = 20; } {
void f2(int& a) int a = 10;
{ a = 30; } int* p = &a;
void f3(int* p) int a1,a2,a3,a4,a5;
{ *p = 40; } f1(a); a1 = a;
void f4(int* p) f2(a); a2 = a;
{ p = new int(50); } f3(p); a3 = *p;
void f5(int* & p) f4(p); a4 = *p;
{ p = new int(60); } f5(p); a5 = *p;
}
a1 = 10;
What are the values of a1, a2, a3, a4, and a5 at the end? a2 = 30;
a3 = 40;
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 10 a4 = 40;
a5 = 60;

Summary #1:
Passed by pointer or passed by reference
1. If you have some data to share among functions,
and you don’t want to copy (by ‘=‘) them during
function calling, you can use “passed by pointers”
class A {
int _i; char _c; int *_p; ...
};
void f(A *a) { ... }
...
int main() {
A *a = ...;
f(a);
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 11

5
Summary #1:
Passed by pointer or passed by reference
2. However, if originally the data is not a pointer
type, “passed by pointers” is kind of awkward.
You should use “passed by references”
class A {
int _i; char _c; int *_p; ...
};
void f(A *a) { ... }
void g(A& a) { ... }
...
int main() {
A a = ...; // an object, not a pointer
f(&a); // Awkward!! C style L
g(a); // Better!!
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 12

Summary #1:
Passed by pointer or passed by reference
3. But, sometimes we just want to share the
data to another function, but don’t want it to
modify the data.
int main() {
A a = ...;
g(a);
}
void g(A& a) { ... }
// “a” may get modified by g()
è Using “const” to constrain !!

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 13

6
Part II: More on “Variables”

u “const” keyword

u Array vs. pointers

u Pointer arithmetic

u Memory sizes of variables

u Return value of a function

u Compilation issues

u Compiler preprocessors
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 14

Key Concept #1: Const

u Const is an adjective
l When a variable is declared “const”, it means it is
“READ-ONLY” in that scope.
è Cannot be modified
u Const must be initialized
l const int a = 10; // OK
l const int b; // NOT OK const variables must be initialized!!
l int i; // Not initialized…
const int j = i; // Is this OK?
const int& k = i; // Is this OK?
f(j); // f(int m) { … }; Is this OK?
i = 10; // will j, k be changed? Is this OK?
u “const int” and “int const” are the same
u “const int *” and “int * const” are different !!

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 15

7
 What? const *& #$&@%#q
u Rule of thumb
l Read from right to left
1. f(int* p)
l Pointer to an int (integer pointer)
2. f(int*& p)
l Reference to an integer pointer
3. f(int*const p)
l Constant pointer to an integer
4. f(const int* p) = f(int const * p)
l Pointer to a constant integer
5. f(const int*& p)
l Reference to a pointer of a constant int
6. f(const int*const& p)
l Reference to a constant pointer address, which points
to a constant integer

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 17

Passed in a reference to a constant object ‘c’

classes could use const method operator
è ‘c’ cannot be modified in the function
() to serve as functors, as long as it don't
modify its own data fields.

const A& B::blah (const C& c) const {...}

Return a reference to a This is a constant method,

constant object meaning this object is treated as only classes could have
constant methods.
è The returned object a constant during this function
can then only call è None of its data members
constant methods can be modified

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 18

8
Key concept #2: The Impact of const
u Supposed “_data” is a data member of class MyClass
void MyClass::f() const
{
_data->g();
}
l Because this object is treated as a constant, its data field
“_data” is also treated as a constant in this function
è “g()” must be a constant method too!!
l Compiler will signal out an error if g() is NOT a const method

u [Coding tip] If we really want a member function to be a read-

only one (e.g. getXX()), putting a “const” can help ensure it

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 19

Const vs. non-const??

u Passing a non-const argument to a const
parameter in a function
void f(const A& i) { ... }
void g(const A j) { ... }
int main() {
A a; ...
f(a); // a reference of “a” is treated const in f()
g(a); // a copy of “a” is treated const in g()
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 20

9
Const vs. non-const??
u Passing a const argument to a non-const
parameter in a function
void f(A& i) { ... }
void g(A j) { ... }
int main() {
const A a(...);
f(a); // Error à No backdoor for const
g(a); // a copy of “a” is treated non-const in g()
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 21

Const vs. non-const??

u Non-const object calling a const method
T a;
a.constMethod(); // OK
l “a” will be treated as a const object within
“constMethod()”

u Const object calling non-const method

const T a;
a.nonConstMethod(); // not OK
l A const object cannot call a non-const method
è compilation error

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 22

10
Casting “const” to “non-const”
const T a;
a.nonConstMethod(); // not OK
Trying...
1. T(a).nonConstMethod();
l Static cast; OK, but may not be safe (why?)
explicitly calling copy constructor, so it's the newly build
l Who is calling nonConstMethod()? instance of the class calling nonConstMethod(), so
2. const_cast<T>(a).nonConstMethod(); compile okay.
l Compilation error!!
l “const_cast” can only be used for pointer,
reference, or a pointer-to-data-member type
3. const_cast<T *>(&a)->nonConstMethod();
l OK, but kind of awkward

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 23

const_cast<T>() for pointer-to-const object

const T* p;
p->nonConstMethod(); // not OK

è const_cast<T*>(p)->nonConstMethod();
A const object can now call non-const method

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 25

11
const class object (revisited)
u Remember:
const A& B::blah (const C& c) const {...}
l When an object of class B calls this
member function, this object will become a
“const class object”.
l That is, the B’s data members will be
treated as const (i.e. can’t be modified) in
this function.
l Also, “this” cannot call non-const functions
in “blah()”, nor can the data members call
non-const functions.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 26

Key Concept #3:

“mutable” --- a back door for const method
u However, sometimes we MUST modify the
data member in a const method
l void MyClass::f() const

{
_flags |= 0x1; // setting a bit of the _flags
}
l In such case, declare “_flag” with “mutable”
keyword often used in graph traversals, such
that it could be modified even in const
§ e.g. methods.

mutable unsigned _flag;

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 27

12
 Key Concept #4: Array vs. Pointer
u An array variable represents a “const pointer”
l int a[10]; ç treating “a” as an “int * const”
a = anotherArr; // Error; can’t reassign “a”
l int *p = new int[10];
p = anotherPointer; // Compile OK, but memory leak！
p = new int(20); // also compile OK, but memory leak！
u An array variable (the const pointer) must be initialized
l Recall: “const” variable must be initialized
l Key: the size of the array must be known in declaration
l int a[10]; // OK, as the memory address is assigned.
int a[10] = { 0 }; // Initialize array variable and its content
int a[ ]; // NOT OK; array size unknown
int a[ ] = { 1, 2, 3 }; // OK array size determined by RHS

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 28

Const pointer vs. pointer to a const

u int a = 10;
const int c = 10;
a = c; // OK
c = a; // NOT OK; even though 10 = 10
u int a[10] = { 0 };
int b[10];
int *c;
const int *d; // This is OK!
int *const e; // Error: uninitialized
b = a; // Error
c = a; d = a; // OK
e = a; // Error
u void f(const int* i) { ... }
int main() {
int * const a = new int(10);
f(a); // Any problem? it's okay...
}
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 29

13
More about int [] and int*
u int a[10] = { 0 }; // type of a: “int *const”
int *p = new int[10];
*a = 10;
*p = 20; // OK
*(a + 1) = 20;
*(a++) = 30; // Compile error; explained later
a = p; // Compile error; non-const to const
p = a; // OK, but memory leak...
*(p++) = 40; // OK, but what about “delete [] p”?
int *q = a;
q[2] = 20;
*(q+3) = 30;
*(q++) = 40; // OK
delete a; // compile error/warning; runtime crash...
delete []p; // compile OK, but runtime crash (p = a)
delete []q; // compile OK, but may get fishy result
u What about:
int a = 10; int *p = &a; ... delete p;

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 30

Key Concept #5: Pointer Arithmetic

u ‘+’ / ‘-’ operator on a pointer variable points
to the memory location of the next /
previous element (as in an array)
l int *p = new int(10);
int *q = p + 1; // memory addr += sizeof(int)
l A *r = new A;
r -= 2; // memory addr -= sizeof(A) * 2
u For an array variable “arr”, “arr + i” points to
the memory location of arr[i]
l int arr[10];
*(arr + 2) = 5; // equivalent to “arr[2] = 5”

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 31

14
(Recapped) Key Concept #6: Memory Sizes

u Basic “memory size” unit è Byte (B)

1 Byte = 8 bit
l
u 1 memory address è 1 Byte
l Like same sized apartments
u Remember: the variable type determines
the size of its memory
l char, bool: 1 Byte(addr += 1)
l short, unsigned short: 2 Bytes(addr += 2)
l int, unsigned, float: 4 Bytes (addr += 4)
l double: 8 Bytes (addr += 8)
l long long: 8 Bytes(addr += 8)

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 32

Key Concept #7: Size of a Pointer

u Remember:
A pointer variable stores a memory address
l What is the memory size of a memory
address?
u The memory size of a memory address
depends on the machine architecture
l 32-bit machine: 4 Bytes
l 64-bit machine: 8 Bytes
u Remember: 1 memory address è 1 Byte
è The memory content of the pointer variables
: For 32-bit machine, the last 2 bits are 0’s
: For 64-bit machine, the last 3 bits are 0’s
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 33

15
Key Concept #8: Memory Alignment
u What are the addresses of these variables?
int *p = new int(10); // let addr(p) = 0x7fffe84ff0e0
char c = 'a';
int i = 20;
int *pp = new int(30);
char cc = 'b';
int *ppp = pp;
int ii = 40;
char ccc = 'c';
char cccc = 'd';
int iii = 30;
è Given a variable of predefined type with memory
size S (Bytes), its address must be aligned to a
multiple of S
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 34

Key Concept #9:

Return value of a function
u Every function has a return type. At the end
of the function execution, it must return a
value or a variable of the return type.
l “void f()” means no return value is needed
1. Return by object
l MyClass f(...) {
MyClass a;...; return a; }
MyClass b = f(...);okay
MyClass& c = f(...); error
// What’s the diff? Is it OK?
// The referenced object must have a
// valid memory addr outside f()

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 36

16
Return by Object, Pointer, and Reference
2. Return by pointer
l MyClass* f(...) { MyClass* p;...; return p; }
MyClass* q = f(...);
// Should we “delete q” later?
3. Return by reference (reference to whom?)
l MyClass& f(...) {...; return r; }
// r cannot be local (why?)
MyClass& s = f(...); // <------------|
MyClass t = f(...); // What’s the diff?
// Is it OK?
l [NOTE] Should NOT return the reference of a
local variable
è int& f() { int a; ...; return a; }
è compilation warning need to check it's valid;
often used with "return (*this)" such that
l MyClass& MyClass::f(...) we could easily concatenate operator and
{...; return (*this); } functions.
MyClass s;
MyClass& t = s.f(...); // <------------|
MyClass v = s.f(...); // What’s the diff?

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 37

When is “return by reference” useful?

u template<class T> class Array
{
public:
Array(size_t i = 0) { _data = new T[i]; }
T& operator[] (size_t i) { return _data[i]; }
const T& operator[] (size_t i) const {
return _data[i]; }
Array<T>& operator= (const Array& arr) {
... return (*this); }
private:
T *_data;
};
int main()
{
Array<int> arr(10); // declare an array of size 10
int t = arr[5]; // <---------|
arr[0] = 20; // Which one will be called?
Array<int> arr2; arr2 = arr;
} // Why not “Array<int> arr2 = arr;”?

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 38

17
Remember in a software project...
u Your program may have many classes...
u You should create multiple files for different
class definitions ---
l .h (header) files
è class declaration/definition, function
prototype
l .cpp (source) files
è class and function implementation
l Makefiles
è scripts to build the project

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 39

Key Concept #10:

Define classes in header files
// a.cpp Why should we include
// a.h #include "a.h" “a.h” and “b.h”?
class A #include "b.h"
{ void A::f() {
public: B b; // main.cpp
void f(); b.g(); #include "a.h"
}; ... int main()
} {
// b.h A a;
class B a.f();
{ // b.cpp }
public: #include "b.h"
void g(); void B::g() {
}; ... Why don’t we include
} both “a.h” and “b.h”?

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 40

18
Key Concept #11: “#include”
u A compiler preprocessor
l Process before compilation
l Perform copy-and-paste
u This is NOT OK
l // no #include “b.h”
class A {
B _b;
};
u This is OK
l // no #include “b.h”
class B; // forward declaration
class A {
B *_b;
};
è The rule of thumb is “need to know the size of the class”!!

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 41

Key Concept #12: #include “ ” or <> ?

u Standard C/C++ header files
l Stored in a compiler-specified directory
§ e.g. /usr/local/include/c++/8.2.0/
u #include <> will search it in the standard
header files
u #include “” will search it in the current
directory (‘.’), or the directories specified by
“-I” in g++ command line.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 42

19
 Key Concept #13:
Undefined or Redefined Issues
an object file only contains information u Undefined errors for variable/class/type/function
in which .cpp or .cc it's compiled from. l The following will cause errors in compiling a source file ---
so there exist a "jump place holder" for
int i = j; // If j is not declared before this point
the object file to find the actual
function, i.e. linking. A a; // If class A is not defined before this point
A *a; // If class A is not declared before this point
goo(); // If no function prototype for goo() before this point
l The following is OK when compiling each source file, but will
cause error during linking if goo() is NOT defined in any other
source file --
int goo(); // forward declaration
...
int b = goo();
u Redefined errors
l Variable/class/function is defined in multiple places
l May be due to multiple inclusions of a header file

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 43

Declare, Define, Instantiate, Initialize, Use

1. Declare a class identifier / function prototype
l class MyClass;
l void goo(int, char);
2. Define a class / function / member function
l class MyClass { ... };
l void goo() { ... }
l void MyClass::goo2() { ... }
3. Instantiation (= Declaration + definition) (variable / object)
l int a;
l MyClass b;
4. Initialization (during instantiation) (variable / object)
l int a = 10;
l MyClass b(10);
5. Used (variable / object / function)
l a = ...; or ... = a;
l goo();
l b.goo2();
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 44

20
 Key Concept #14: “extern” in C++
u Remember, static variables and functions can only be
seen in the file scope è cannot be seen in other file

u What if we want to access (global) variables or functions

across other .cpp files?
e.g.
// file1.cpp
in this case, file1.cpp would int a = 0;
compile-okay, but two errors as void f(int i) { ... }
shown would appear when linking. -------------------------------
// file2.cpp
int a; // Error: multiple definition during linking
void g()
{
f(a); // Error: f(int) not defined
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 45

Using External Variables and Functions

e.g.
// file1.cpp
int a = 0;
void f(int i) { ... }
-------------------------------
// file2.cpp
extern int a; // a is an external variable
void f(int); // f() is an external function
// “extern” can be omitted
here
void g()
{
f(a);
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 46

結論是util.h的全部extern都拔掉也沒關係呢
extern的用意是為了不要重複定義一個variable
function 只是重複declare的話是沒關係der
所以可以看到p.cpp多declare了一次，那只是個f
orward-declaration
總之對於一般的只有declaration的function來說
，實際上extern都是可以丟掉的，儘管實作的cp
p、obj可能根本沒有include到
最後linker有放在一起讓它能夠跳就好惹
21
the point of include/forward-declaration is,
compiler need to know what memory size
shall it give to the variable, and how to
initialize it if needed.

Key Concept #15: Forward Declaration

[Bottom line]
Sometimes we just want to include part of the header file,
or refer to some declarations
è We don’t want to include the whole header file
è To reduce:
1. Executable file size
2. Compilation time due to dependency
e.g.
// MyClass.h
class HisClass; // forward declaration
class HerClass; // forward declaration
class MyClass
{
HisClass* _hisData; // OK
HerClass _herData; // NOT OK; why?
};
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 47

Key Concept #16: Namespace

u e.g.
namespace MyNameSpace {
int a;
void f();
class MyClass;
} // Note: no ‘;’
u namespace MyNS = MyNameSpace; // alias
u Must declare in global scope
l int main()
{
namespace XYZ { ... } // Error!!
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 48

22
Using namespace
1. void g() {
MyNameSpace::a = 10;
} // “::” is the scope operator

2. using MyNameSpace::a;
void g() {
a = 10;
}

3. using namespace MyNameSpace;

void g() {
a = 10;
f();
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 49

More about namespace declaration

u namespace P {
namespace A { void f(); }
void A::f() { } // ok
void A::g() { } // Error!! g() is not
// yet a member of A
namespace A { void g(){ ... } }
}
è
1. Can be nested...
2. The definition of a namespace can be split over several
parts (e.g. ‘A’ above)
3. Order matters!! (e.g. A::g())
4. Functions or classes can be defined either inside (e.g. g())
or outside (e.g. f()) “namespace {...}.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 50

23
Summary #2: Declare, Define, & Use
u If something is declared, but not defined or used,
that is fine. (Compilation warning)
u If something is used before it is defined or
declared è compile (undefined) error.
u If something is defined in other file, you can use it
only if you forward declare it in this file. BUT you
cannot define it again in this file è compile
(redefined) error.
l Variable è “extern”
l Function è prototype, with or without “extern”
u If something is declared, but not defined, in this
file, you can use it and the compilation is OK. BUT
if it is not defined in any other file è linking
(undefined) error.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 51

Key Concept #17: #define

u #define is another compiler preprocessor
l All the compiler preprocessors start with “#”
◆ “#define” performs pre-compilation inline
string substitution
u “#define” has multiple uses in C++
1. Define an identifier (e.g. #define NDEBUG)
2. Define a constant (e.g. #define SIZE 1024),
or substitute a string
3. Define a function (Macro)

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 52

24
“#define” for an Identifier
1. To avoid repeated definition of a header file in multiple
C/C++ inclusions
l #ifndef MY_HEADER_H
#define MY_HEADER_H
// header file body...
// ... command line define something in gcc/g++:
#endif -D<some flags>

2. Conditional compilation eg: g++ -c --std=c++11 -Wall -DNDEBUG

l #ifndef NDEBUG
// Some code you want to compile by default
// (i.e. debug mode)
// For optimized mode,
// define “NDEBUG” in Makefile.
#endif CFLAGS

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 54

“#define” for a Constant or a String

u #define <identifier> [tokenString]
e.g.
l
#define SIZE 1024
#define CS_DEFAULT true
#define HOME_DIR “/home/ric”
(why not /home/ric?)
u Advantage of using “#define”when used to substitute string, generally we
add quotation marks to it, for sake of cout
l Correct once, fix all simplicity.
u What’s the difference from “const int xxx”, etc?
l Remember: “#define” performs pre-compilation
inline string substitution
l “const int xxx” is a global variable
è Fixed memory space
è Better for debugging!!

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 55

25
“#define” for a MACRO function
u #define <identifier>(<argList>) [tokenString]
l e.g.
#define MAX(a, b) ((a > b)? a: b)
// Why not “((a > b)? a: b)” ?

l e.g.
// Syntax error below!! Why??
#define MAX(int a, int b) ((a > b)? a: b)

u Disadvantage
l “#define” MACRO function is difficult to debug!!
è Cannot step in the definition (Why??)
l Use inline function (i.e. inline int max(int a, int b)) instead

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 56

Part III: More on “Classes”

u Class, struct, union, enum

u Bit-slicing

u Class wrapper

u “static” keyword

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 57

26
Key Concept #1: “struct” in C++
u [Note] “struct” is a C construct used for
“record type” data
l Very similar to “class” in C++, but in C,
there is no private/public, nor member
function, etc.
u However, “struct” in C++ inherits all the
in c++, struct is only a class
features of the “class” construct with all methods and data
l Can have private/public, member functions,
members set to "public";

and can be used with polymorphism many stl functions actually

uses struct to save its data
l The only difference is: the default access fileds.
privilege for “struct” is public

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 58

Key Concept #2: “union” in C++

u At any given time, contains only one of its data
members
l To avoid useless memory occupation
l i.e. data members are mutual exclusive
§ Use “union” to save memory
l size = max(size of its data members)
u A limited form of “class” type
l Can have private/public/protected, data
members, member functions
§ default = public
l Can NOT have inheritance or static data
member

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 59

27
Example of “union” often used to save some memory.
union U int
{ main()
private: {
int _a; U u;
char _b; u.setB('a');
public: cout << u.getA()
U() { _a = 0; } << endl;
int getA() const return 0;
{ return _a; } }
void setA(int i)
{ _a = i; }
char getB() const u What is the output???
{ return _b; } int('a'); 97.
void setB(char c)
{ _b = c; }
};

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 60

Anonymous union
u Union can be declared anonymously
l i.e. Omit the type specifier
u main() class A {
{ union T {
union { int _a;
int _a; double _b;
char _b; };
}; T _t;
int i = _a; void f() {
char j = _b; if (_t._a >
} 10)...
è used as non-union variables } it's my (I'm A) data field, why am I still using operator "." to
access it?
è What if it is NOT anonymous? }; anonymous union is more easy and institutive to use.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 61

28
 Key Concept #3: Another ways to save
memory: memory alignment and bit slicing
u Note: in 64-bit machine, data are 8-byte aligned
What are “sizeof(A)” below ? this is true for both pointers and classes,
that is, an instance of a class is also
l class A { char _a; }; 8-byte aligned.
l class A { int _i; bool _j; int* _k; }
l class A { int _i; bool _j; int* _k; char _l; }
u Recommendation
l Pack the data in groups of “sizeof(void*)”, or ---
l Use bit-slicing to save memory
class A {
int _id: 30;
int _gender: 1;
int _isMember: 1;
void f() { if (_isMember) _id += ...; }
};

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 62

How about bit-slicing for pointers?

using size_t, notice that pointers
must have its last 3 (for 64-bits ◆ No, size of pointers is fixed. You cannot bit slice them.
machine) or 2 (for 32-bits
machine) bits as zero, so we could ◆ One “tricky” way to save memory is to use the fact that
use size_t to save pointer and
some boolean information in a
pointer addresses are multiple of 8’s (for 64-bit machines)
size_t.
Yep, size_t always have the size #define BDD_EDGE_BITS 3 bool isNegEdge() const {
same as that of a pointer. #define BDD_NODE_PTR_MASK return (_nodeV &
((~(size_t(0)) >> BDD_NEG_EDGE); }
BDD_EDGE_BITS) << };
BDD_EDGE_BITS)
class BddNode { class BddNodeInt
{
private:
BddNode _left;
size_t _nodeV;
BddNode _right;
// Private functions size_t _level : 32;
BddNodeInt* getBddNodeInt() size_t _refCount : 31;
const { return size_t _visited : 1;
(BddNodeInt*)(_nodeV & };
BDD_NODE_PTR_MASK); }

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 63

29
A Closer Look at the Previous Example
class BddNode { // wrapper class for BddNodeInt
private:
size_t _nodeV;
};
class BddNodeInt { // as pointer variables
…
};
◆ Important concepts:
● No extra memory usage when wrapping a pointer variable with a
class
● However, you gain the advantages in using
constructor/destructor, operator overloading, etc, which are not
applicable for pointer type variables.
è BddNode a, b, c;… ; c = a & b;
● The LSBs can be used as flags or stored other information.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 65

Summary #2: “class”, “struct”, & “union”

u In C++, data members are encapsulated by the
keywords “private” and “protected”
l Make the interface between objects clean
§ Reduce direct data access
l Using member functions: correct once, fix all
u Struct and class are basically the same, except for
their default access privilege
u Union: no inheritance nor static data member

class struct union

Default
private public public
access
u Enum: user-defined type for named constants

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 66

30
Key Concept #4: Enum
u A user-defined type consisting of a set of named
constants called enumerators
l e.g.
class T {
enum COLOR {
RED, // value = 0
BLUE, // value = 1
GREED = 5,
YELLOW // value = 6
};
};
u By default, first enumerator’s value = 0
u Each successive enumerator is one larger than the
value of the previous one, unless explicitly specified
(using “=“) with a value
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 67

Scope of “enum”
u Enumerators are only valid within the scope it is
defined
l e.g.
class T {
enum COLOR { RED, BLUE };
};
è RED/BLUE is only seen within T
l To access enumerator outside of the class, use
explicit class name qualification
§ e.g. void f() { int i = T::RED; }
è But in this case, the enum must be defined as
public
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 68

31
 Common usage of “enum”
1. Used in function return type
meaningful variables make code more readable.
l Color getSignal() { ... }

2. Used as “status” and controlled by “switch-case”

l ProcState f() { ...; return ...; }
...
ProcState state = f();
switch (state) {
case IDLE : ...; break;
case ACTIVE: ...; break;
} // What’s the advantage??
3. Used as “bit-wise” mask

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 69

Bitwise Masks
u To manipulate multiple control “flags” in a single integer
u enum ErrState {
NO_ERROR = 0,
DIV_ZERO = 0x1, // 001
OVERFLOAT = 0x2, // 010
INTERRUPT = 0x4, // 100
BAD_STATUS= DIV_ZERO | OVERFLOAT |
INTERRUPT
};
int ErrState status = NO_ERROR; // This line is OK
// To set the error status
status |= OVERFLOAT;
// To unset the error status
status &= ~DIV_ZERO;
// To test the error status
if ((status & INTERRUPT) != 0)
... we have no operator "|=" and "&="
also, enum is not
overload-able with any
è Compilation error... WHY??? defined yet @@ operator.
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 70

32
Key Concept #5: “#define” vs. “enum”
1. #define RED 0
#define BLUE 1
#define GREEN 5
2. enum COLOR {
RED, // value = 0
BLUE, // value = 1
GREED = 5
};
u What’s the difference in terms of debugging?
l Using “#define” è Can only display “values”
l Using “enum” è Can display “names”
Recommendation: using “enum”

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 71

Recall: Size of a Class

u The size of a class (object) is equivalent to the
summation of the sizes of its data members
class A {
B _b; _a._b
C *_c; A _a
}; _a._c

è sizeof(A) = sizeof(B) + sizeof(C*);

C
u Wrapping some variables with a class
definition DOES NOT introduce any memory
overhead!!

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 72

33
 Key Concept #6: Class Wrapper
1. To create a “record” type with a cleaner
interface
l e.g. When passing too many parameters to
a function, creating a class to wrap them
up.
è Making sure data integrity (checked in
constructor)
è Creating member functions to enact
assumptions, constraints, etc.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 73

Key Concept #6: Class Wrapper

2. To manage the memory allocation/deletion of
pointer variables
l Recap: pointer data member will not be explicitly
constructed in class constructor
l Memory allocation/deletion problems for pointer
variables
§ There may be many pointer variables pointing to the same
piece of heap memory
§ The memory should NOT be freed until the “last” pointer it's troublesome to store bidirectional
variable become useless (HOW DO WE KNOW!!?) pointer information, so the class
pointed to usually only have a
§ What about the pointer (re-)assignment? reference count instead.
l Recap: The memory of an object variable is
allocated when entering the scope, and released
when getting out.
l Recap: The heap memory must be explicitly
allocated and deleted.

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 74

34
 Object-Wrapped Pointer Variables
If your program contains pointer-pointed memory that
is highly shared among different variables
uKeep the reference count
uPointer à internal class (e.g. class NodeInt)
Object à user interface (e.g. class Node)
class NodeInt { // a private class
friend class Node;
Data _data; Data _data
size_t _refCnt
Node _left;
Node _right; _left _right
size_t _refCnt; *_node
};
Data _data Data _data
class Node { size_t _refCnt size_t _refCnt
NodeInt *_node;
};
*_node *_node
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 75

class "Node" acts as a wrapper for class

"NodeInt", s.t. we could overload the
Object-Wrapped Pointer Variables
operators for class "Node" to achieve
reference count functionality, and Node::Node(...) {
auto-destruct those who have # ref = 0,
merely by simply calling operator "=" as
...
usual, etc. if (!_node) _node = newNode(...);
_node->increaseRefCnt();
}
Node::~Node() { resetNode(); }
Node::resetNode() {
if (_node) {
_node->decreaseRefCnt();
if (_node->getRefCnt() == 0) delete _node;
}
}
Node& Node::operator = (const Node& n) {
resetNode();
_node = n._node;
_node->increaseRefCnt();
}

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 76

35
Key Concept #6: Class Wrapper
3. To keep track of certain data/flag changes and
handle complicated exiting/exception conditions
void f() {
x1.doSomething();
if (...) x2.doSomething();
else { x1.undo(); return; }
...
x2.undo(); x1.undo();
}
èVery easy to miss some actions...
void f() {
XKeeper xkeeper; // keep a list in xkeeper
xkeeper.doSomething(x1);
if (...) xkeeper.doSomething(x2);
else return;
} // ~XKeeper() will be called
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 77

Key Concept #7: “static” in C++

u As the word “static” suggests, “static xxx” should be
allocated, initialized and stay unchanged throughout the
program
è Resides in the “fixed” memory

However,
u The keyword “static” is kind of overloaded in C++
1. Static variable in a file
2. Static variable in a function
3. Static function
4. Static data member of a class
5. Static member function of a class

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 78

36
So, what does “static” mean anyway?
u “static” here,
refers to “memory allocation” (storage class)
l The memory of “static xxx” is allocated
before the program starts (i.e. in fixed
memory), and stays unchanged throughout
the program
[cf] “auto” storage class
§ Memory allocated is controlled by the execution
process (e.g. local variables in the stack memory)

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 79

Key Concept #8:

Visibility of “static” variable and function
1. Static variable in a file impossible for other files to use "extern" to use the variable in this code.
l It is a file-scope global variable
l Can be seen throughout this file (only)
l Variable (storage) remained valid in the entire execution
2. Static variable in a function
l It is a local variable (in terms of scope)
l Can be seen only in this function
l Variable (storage) remained valid in the entire execution
3. Static function
l Can only be seen in this file

u Static variables and functions can only be seen in the

defined scope
l Cannot be seen by other files
l No effect by using “extern”

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 80

37
[Note] Storage class vs. visible scope
u Remember, “static” refers to static “memory
allocation” (storage class)
l We’re NOT talking about the “scope” of a variable
u The scope of a variable is determined by where
and how it is declared
l File scope (global variable)
l Block scope (local variable)
è However, the “static” keyword does constrains the
maximum visible scope of a variable or function to
be the file it is defined

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 81

Key Concept #9:

“static” Data Member in a Class
u Only one copy of this data member is maintained
for all objects of this class
l All the objects of this class see the same copy of
the data member (in fixed memory)
l (Common usage) Used as a counter

class T
{
static int _count;
public:
T() { _count++; }
~T() { _count--; }
};
------------------------------------------------
int T::_count=0;
// Static data member must be initialized in some
// cpp file ==> NOT by constructor!!! (why?)
Data Structure and Programming Prof. Chung-Yang (Ric) Huang 82

38
 Key Concept #10:
“static” Member Function in a Class
u Useful when you want to access the “static” data member but do
not have a class object (when there's no explicit instance exist, we could still modify the static data field of the
class)
l Calling static member function without an object
§ e.g. T::setGlobalRef();
l No implicit “this” argument (no corresponding object)
l Can only see and use “static” data members , enum, or
nested types in this class
§ Cannot access other non-static data members
u Usage
l T::staticFunction(); // OK
l object.staticFunction(); // OK
l T::staticFunction() { ... staticMember... } // OK
l T::staticFunction() { ... this... } // Not OK
l T::staticFunction() { ... nonStaticMember... } // Not OK
l T::nonstaticFunction() { ... staticMember... } // OK

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 83

Example of using “static” in a class

class T
{
static unsigned _globalRef;
unsigned _ref;
_ref is used to check if traversed or not.
by modifying global static, we could
have a single operation s.t. all the
public:
nodes have different _ref as the global T() : _ref(0) {}
static one, thus we rendered everyone bool isGlobalRef(){ return (_ref == _GlobalRef); }
not traversed in just one variable
assignment. void setToGlobalRef(){ _ref = _global Ref; }
static void setGlobalRef() { _globalRef++; }
}

u Use this method to replace “setMark()” functions in

graph traversal problems
(How??)

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 84

39
Key Concept #11:
static_cast<T>(a)... Cast away static?? L
u Convert object “a” to the type “T”
l No consistency check (i.e. sizeof(T))
è static implies “compile time”
è May not be safe
è cf. dynamic_cast<T>(a)
l (Common use) // more safer use
// Parent-class pointer object wants to
// call the child-only method
class Child : public Dad { ... };
----------------------------------
void f()
{
Dad* p = new Child;
...
static_cast<Child *>(p)->childOnlyMethod();
};

Data Structure and Programming Prof. Chung-Yang (Ric) Huang 87

40